Lagrange Multipliers inconsistent system

[benorin]

Homework Statement

maximize f(a,d,h,p)= (4a+3d+3h+c1)c2 *(2+0.01*floor(50+0.0001p)) subject to the constraint 1439a+427d+9259+912/5*h=k.
This is not a homework problem but it may as well be: it comes from a game, the function f represents damage as a function of 4 stats and the constraint arises since the cost of adding each stat is weighted in terms of skill points=k.

Homework Equations

Lagrange multipliers: del(f)=lambda*del(g) and g=k, form a system of equations whose solutions are possible extrema of f.

The Attempt at a Solution

<4c2*(2+0.01floor(50+0.0001p)), 3c2*(2+0.01floor(50+0.0001p)), 3c2*(2+0.01floor(50+0.0001p)),0> = lambda*<1439,427,912/5,925> and g=k. The fourth vector component forces lambda=0 and this is inconsistent because c2 is a non-zero constant. Not really sure where that leaves me. Just a pointer will do, no lengthy solutions please. Thanks for your time.

 

[Ray Vickson]

Homework Statement

maximize f(a,d,h,p)= (4a+3d+3h+c1)c2 *(2+0.01*floor(50+0.0001p)) subject to the constraint 1439a+427d+9259+912/5*h=k.
This is not a homework problem but it may as well be: it comes from a game, the function f represents damage as a function of 4 stats and the constraint arises since the cost of adding each stat is weighted in terms of skill points=k.

Homework Equations

Lagrange multipliers: del(f)=lambda*del(g) and g=k, form a system of equations whose solutions are possible extrema of f.

The Attempt at a Solution

<4c2*(2+0.01floor(50+0.0001p)), 3c2*(2+0.01floor(50+0.0001p)), 3c2*(2+0.01floor(50+0.0001p)),0> = lambda*<1439,427,912/5,925> and g=k. The fourth vector component forces lambda=0 and this is inconsistent because c2 is a non-zero constant. Not really sure where that leaves me. Just a pointer will do, no lengthy solutions please. Thanks for your time.

(1) There is something seriously wrong with the problem formulation. The variable $p$ appears in the maximization objective, but appears nowhere in any constraint. So, assuming that the constants $c_2$ and $k$ are $>0$, we might as well take some feasible values of $a,d,h$ that ensures $4a+3d+3h+c_1 > 0,$ then let $p \to +\infty$ to get an "unbounded" problem, having no finite maximum.
(2) Even if you fix the issue in (1), your method is doomed to failure. The Lagrangian (or any type of method involving derivatives) will fail here because the floor function is discontinuous (even worse than simple non-differentiability). One way to do it would be to solve a series of separate problems, such as
$$ \begin{array}{rcl}
\text{P1:} & \max & (4a + 3d+ 3h + c_1)\cdot c_2 \cdot 2.5 \\
&\text{s.t.}& 1439 a +427 d + 9259 + (912/5) h = k \\
& & 0 \leq p \leq 1/0.0001\\
\text{P2:} &\max &(4a + 3d+ 3h + c_1)\cdot c_2 \cdot 2.51 \\
&\text{s.t.}& 1439 a +427 d + 9259 + (912/5) h = k \\
&& 1/.0001 \leq p \leq 2/.0001 \\
\text{P3:} &\max &(4a + 3d+ 3h + c_1)\cdot c_2 \cdot 2.52 \\
&\text{s.t.}& 1439 a +427 d + 9259 + (912/5) h = k \\
&& 2/.0001 \leq p \leq 3/.0001
\end{array}
$$
etc. Basically, in well-defined $p$-intervals the floor function is either 0 or 1 or 2 or ..., and each such problem can be solved separately. Unless you have bounds such as $a \geq 0$, $d \geq 0$, $h \geq 0$ (or some nonzero lower bounds, possibly negative) you will probably have unbounded problems again, having no finite maxima.

Assuming non-negativity constraints on the variables, each of these separate problems is a simple single-constraint linear programming problem, which can be solved in closed-form; Google "continuous knapsack problem". Furthermore, if the variable $p$ is not tangled up with the variables $a,d,h$ is a constraint, the only way that modifying $p$ changes the problem is to take the single objective $(4a+3d+h+c_1) \cdot c_2$ and multiply it either by 2 or 2.01 or 2.02,..., which would not affect the location of the maximum. In other words, if $p$ is not entangled with the other variables, just solving problem P1 is sufficient.
Note: I have assumed that $912/5 * h$ means $(912/5)h$, not $\frac{912}{5h}.$ If you mean the latter you need to use parentheses, like this: 912/(5h). If the $h$ is in the denominator, you have a nonlinear programming problem rather than a linear one, but it is still readily solved (using Lagrange multiplier methods, for example).

Note added in edit: for a problem of the form $\max (4a + 3d+ 3h + c_1)\cdot c_2$, subject to the constraints $1439 a +427 d + 9259 + (912/5) h = k$ and $a, d ,h \geq 0$ you cannot use the simple Lagrange-multiplier method (because some of the Lagrangian derivatives can be nonzero in the presence of bounds on the variables); instead, the presence of inequality-constrained variables forces you to use the so-called Karush-Kuhn-Tucker conditions. That is what the so-called Simplex method for linear programming is all about: doing it in a fast and easy way.

 

[benorin]

There was a typo in the constraint, so sorry:
1. Homework Statement
maximize f(a,d,h,p)= (4a+3d+3h+c1)c2 *(2+0.01*floor(50+0.0001p)) subject to the constraint 1439a+427d+925p+912/5*h=k.
This is not a homework problem but it may as well be: it comes from a game, the function f represents damage as a function of 4 stats and the constraint arises since the cost of adding each stat is weighted in terms of skill points=k.

 

[Ray Vickson]

There was a typo in the constraint, so sorry:
1. Homework Statement
maximize f(a,d,h,p)= (4a+3d+3h+c1)c2 *(2+0.01*floor(50+0.0001p)) subject to the constraint 1439a+427d+925p+912/5*h=k.
This is not a homework problem but it may as well be: it comes from a game, the function f represents damage as a function of 4 stats and the constraint arises since the cost of adding each stat is weighted in terms of skill points=k.

OK, so the constraint was incorrectly written in your first message (as I, in fact, suspected).

Now comes an extremely important question: do you allow some of the variables $a,d,h,p$ to be negative, or must they all be $\geq 0$? Please do not ignore this question; it makes the difference between an unsolvable problem and a very easy one, so if you are serious about wanting help you absolutely must deal with the issue.

Assuming that $a,d,h,p \geq 0$, you can eliminate the floor function entirely if $k < 9,\!250,\!000.$ That is, $\text{floor}(50 + 0.0001 p ) = 50$ for any feasible values of $p.$

 

[benorin]

OK, so the constraint was incorrectly written in your first message (as I, in fact, suspected).

Now comes an extremely important question: do you allow some of the variables $a,d,h,p$ to be negative, or must they all be $\geq 0$? Please do not ignore this question; it makes the difference between an unsolvable problem and a very easy one, so if you are serious about wanting help you absolutely must deal with the issue.

Assuming that $a,d,h,p \geq 0$, you can eliminate the floor function entirely if $k < 9,\!250,\!000.$ That is, $\text{floor}(50 + 0.0001 p ) = 50$ for any feasible values of $p.$

All variables are non-negative, yes. $p$ is in the millions, as are $a, d$, and $h$. Therefore it is not likely that $k < 9,\!250,\!000.$ so we must deal with the floor function I suppose. Any thoughts on this? I suppose I could solve the constraint for a variable and substitute that expression into the function to be maximized and look for extrema as usual but do I need to look at all points where the derivative of the floor function is undefined? Seems so: $\frac{d}{dp}\text{floor}(50 + 0.0001 p )$ is undefined whenever

$50 + 0.0001 p\in \mathbb{Z}^{+}\Rightarrow p\in \left\{ 10,\!000 j | j\in\mathbb{Z}^{+}\right\}$

and the constraint solved for $a$ is

$a=\frac{1}{1439}\left( k-427d-925p-\frac{912 h}{5}\right)$

substituting both these into the function we get

$f\left( \frac{1}{1439}\left( k-427d-925p-\frac{912 h}{5}\right) , d, p, h\right) = \left[ \frac{4}{1439}\left( k-427d-9\!250\!000 j-\frac{912 h}{5}\right) +3d+3h+c1\right] c2 *\left( 2+ 0.01( 50+k) \right)$ for $j\in\mathbb{Z}^{+}$...

Oop, out of time right now to work on this, be back later: feel free to chime in, and thanks!

 

[Ray Vickson]

All variables are non-negative, yes. $p$ is in the millions, as are $a, d$, and $h$. Therefore it is not likely that $k < 9,\!250,\!000.$ so we must deal with the floor function I suppose. Any thoughts on this? I suppose I could solve the constraint for a variable and substitute that expression into the function to be maximized and look for extrema as usual but do I need to look at all points where the derivative of the floor function is undefined? Seems so: $\frac{d}{dp}\text{floor}(50 + 0.0001 p )$ is undefined whenever

$50 + 0.0001 p\in \mathbb{Z}^{+}\Rightarrow p\in \left\{ 10,\!000 j | j\in\mathbb{Z}^{+}\right\}$

and the constraint solved for $a$ is

$a=\frac{1}{1439}\left( k-427d-925p-\frac{912 h}{5}\right)$

substituting both these into the function we get

$f\left( \frac{1}{1439}\left( k-427d-925p-\frac{912 h}{5}\right) , d, p, h\right) = \left[ \frac{4}{1439}\left( k-427d-9\!250\!000 j-\frac{912 h}{5}\right) +3d+3h+c1\right] c2 *\left( 2+ 0.01( 50+k) \right)$ for $j\in\mathbb{Z}^{+}$...

Oop, out of time right now to work on this, be back later: feel free to chime in, and thanks!

How to deal with the floor function: already answered explicitly in post #2. Solve a sequence of problems without the floor function.

This process might involve searching thousands of formulations before finding the right $p$-interval $m/0.00001 \leq p \leq (m+1)/0.0001$ in which the floor function evaluates to the constant $50+m$ throughout.

A possible way to shorten the process would be to neglect the floor function entirely, and write $50+ .0001p$ instead of $\text{floor}(50+0.0001p)$. That will give you a standard linear optimization problem ("linear programming") that can be solved using the simplex method---but NOT the Lagrange multiplier method (because of non-negativity restrictions on the variables). This is a single-constraint linear programming problem having a simple closed-form solution. This will not be the exact solution to the exact problem, because it approximates $\text{floor}(x)$ by $x$ itself. However, with a bit of luck it might get you into the right ballpark, so you can examine the exact problem near the approximate solution. (That is, after figuring out an approximate value $p_{approx}$, you can home in on an appropriate $p$-interval $p_0 \leq p < p_1$, where $50 +0.0001 p_0 = \text{floor}(50+0.0001 p_{approx})$ and $50+0.0001 p_1 = 51 + 0.0001 p_0$. For all $p$ in the interval $p_0 \leq p < p_1$ we have that $\text{floor}(50 + 0.0001 p)$ is just the constant $50 + 0.0001 p_0$, so becomes a constant in your maximization objective. That is , you have the problem
$$ \begin{array}{cl}
\max & (4a + 3d+ 3h + c_1)\cdot \underbrace{ c_2 \cdot (2+0.01 (50+0.0001 p_0))}_{\text{constant}}\\
\text{s.t.}& 1439 a +427 d + 9259 p + (912/5) h = k \\
& p_0 \leq p \leq p_1 \\
& a,d,h \geq 0
\end{array}
$$
This is a simple linear programming problem with a single equality constraint and simple bound constraints on one of the variables. You can easily solve it manually, using the simplex method, or you can use an on-line linear solver or the EXCEL Solver tool to get a solution.

You might have to look at a few neigbouring formulations, with a few intervals above and below $[p_0,p_1]$ to get neighbouring values of the floor function. If you find that the $[p_0,p_1]$ problem gives the best maximum, that will probably be your true maximum solution.

I am not 100% sure that you are guaranteed to get the true optimimum in this way, but it is at least a sensible heuristic, and it is the way I would proceed if I were tackling the problem.

 

[Ray Vickson]

All variables are non-negative, yes. $p$ is in the millions, as are $a, d$, and $h$. Therefore it is not likely that $k < 9,\!250,\!000.$ so we must deal with the floor function I suppose. Any thoughts on this? I suppose I could solve the constraint for a variable and substitute that expression into the function to be maximized and look for extrema as usual but do I need to look at all points where the derivative of the floor function is undefined? Seems so: $\frac{d}{dp}\text{floor}(50 + 0.0001 p )$ is undefined whenever

$50 + 0.0001 p\in \mathbb{Z}^{+}\Rightarrow p\in \left\{ 10,\!000 j | j\in\mathbb{Z}^{+}\right\}$

and the constraint solved for $a$ is

$a=\frac{1}{1439}\left( k-427d-925p-\frac{912 h}{5}\right)$

substituting both these into the function we get

$f\left( \frac{1}{1439}\left( k-427d-925p-\frac{912 h}{5}\right) , d, p, h\right) = \left[ \frac{4}{1439}\left( k-427d-9\!250\!000 j-\frac{912 h}{5}\right) +3d+3h+c1\right] c2 *\left( 2+ 0.01( 50+k) \right)$ for $j\in\mathbb{Z}^{+}$...

Oop, out of time right now to work on this, be back later: feel free to chime in, and thanks!

I have found through an example that an optimal solution might not exist; that is, you can sometimes have a "supremum" but not a "maximum".

Since the constant $c_2$ just scales the maximization objective we can omit it. Furthermore, $c_1$ is an additive constant for each evaluation of the floor function, so we can drop it from the optimization---provided that we put it back later. That is, the constant $c_1$ appears as an additive constant $2.5 c_1$ in one subproblem, as another additive constant $2.51 c_1$ in the next neigboring subproblem, etc. After solving each subproblem we can add the appropriate constant in order to make a true comparision between them.

I took $k =416\,655\,000$, which allows five $p$-intervals $[0,10\,000), [10\,000, 20\,000), [20\,000, 30\,000), [30\,000, 40\,000)$ and $[40\,000, 50\,000).$ The first two subproblems are
$$
\begin{array}{rcl}
\text{P1:} & \max &Z_1 = 4a + 3d+ 3h\\
&\text{s.t.}& 1439 a +427 d + 9259 p + (912/5) h = 416\,655\,000\\
& & 0 \leq p \leq 10\,000\\
\text{P2:} & \max &Z_2 = 4a + 3d+ 3h\\
&\text{s.t.}& 1439 a +427 d + 9259 p + (912/5) h = 416\,655\,000\\
& & 10\,000 \leq p \leq 20\,000
\end{array}
$$
and the other three are similar.

The solutions to P1 and P2 (obtained using Maple's LPSolve package are):
$$\begin{array}{cl}
\text{P1:} & Z_1 = 900\,806.1154\\
& a = 225\,201.5288 \\
&d=0, \: h=0 \\
&p = 10\, 000\\
\text{P2:} & Z_2 = 643\,432.9395\\
&a = 160\,858.2349\\
& d = 0 \; h = 0 \\
& p = 20\,000
\end{array}
$$

The problem is that the actual $p$-intervals for the floor function are half-open $[0,10\,000), [10\,000, 20\,000)$ etc., but the linear programming formulations do not allow strict inequalities. Therefore, in subproblem P1 we use $p \leq 10\,000$ instead of $p < 10\,000$, etc. The solution of P1 is right at the upper end of the $p$-interval, where we would then be using the wrong value of the floor function! In other words, if we use a non-strict inequality such as $p \leq 9\,999.999\,999\,999\,999$ instead of the true $p < 10\,000$, the linear programming solution would be at $p = 9\,999.999\,999\,999\,999$. When we use $p = 10\,000$ we really ought to be looking at problem P2. However, the solution of P2 has $p = 20\,000$, nowhere near $10\,000$, and its maximum objective $Z_2$ is much worse than $Z_1$.

The "true" maximum for P1 is $2.5 Z_1 + 2.5 c_1,$ while the true maximum for P2 is $2.51 Z_2 + 2.51 c_2$. Thus, the interval $[0, 10\,000)$ is the true optimal $p$-interval (and 50 is the true best value of the floor function) as long as $2.5 Z_1 + 2.5 c_1 > 2.51 Z_2 + 2.51 c_1$. For $Z_1, Z_2$ as given in the solutions above, [0,10 000) is the best interval whenever $c_1 < 63\,699\ 861.$ I don't know what value of $c_1$ you intend to use, but as long as it does not exceed about 64 million, P1 is the best subproblem. However, in that case the value of $2.5 Z1 + 2.5 c_1$ is a supremum of the profit (or whatever you are trying to maximize). You can get withing a hair's breadth of that value, but cannot actually reach it exactly. But, as long as you are satisfied with 1000 decimal place accuracy, you might as well use the linear programming solution for P1 (safely using 10 000 in place of 9 999.999999999999999 ...).

The fact that there is no true maximum in this example should not come as a great surprise. The standard theorem---that a continuous function on a compact set has a maximum---does not apply in this problem You are attempting to maximize a discontinuous function over a compact set, so all bets are off. Your maximization objective has jump discontinuites, and that can sometimes lead to trouble as it does in the example above.

Finally: you will note that in the linear programming solutions some of the variables are zero in the optimal solution. That is characteristic of linear optimization: there are optimal solution in which the maximum number of nonzero variables is equal to the number of equality constraints. In our case we have five variables $a,d,h, p,s_1$, where $s_1$ is a slack variable for the upper bound on $p$. That is, we write the upper bound constraint on $p$ as an equality $p + s_1 = 10\, 000$ with $s_1 \geq 0.$ This means that our formulation actually has two equation constraints, so the solution has two positive variables $a>0$ and $p > 0$. The three zero variables are $d = h = s_1 = 0.$

That type of behavior will apply in any of the subproblems, so if you want all four of $a,d,h,p$ to be positive, you will need to impose additional constraints. Perhaps your formulation is incomplete in some way.

 

[benorin]

I think we can simplify this problem a bit before we go into all that linear programming, bear with me: Since we wish to maximize

$f \left( a,d,h,p\right) = (4a+3d+3h+c_1)c_2 *\left( 2+0.01*\text{floor} (50+0.0001p)\right)$

subject to the constraint $1439a+427d+925p+\frac{912h}{5}=k$, we know that from the nature of the floor function to be maximized that it will have the same value for all $10,\!000 j\leq p < 10,\!000 (j+1)$ and since $f$ is linear in $a,d,$ and $h$ and so is the constraint solved for $p$ we can tell that selecting the leftmost endpoint of our interval on $p$ will maximize $f$, hence $p\in \left\{ 10,\!000 j | j\in\mathbb{Z}^{+}\right\}$. Are you with me so far? Did I make a mistake?

 

[Ray Vickson]

I think we can simplify this problem a bit before we go into all that linear programming, bear with me: Since we wish to maximize

$f \left( a,d,h,p\right) = (4a+3d+3h+c_1)c_2 *\left( 2+0.01*\text{floor} (50+0.0001p)\right)$

subject to the constraint $1439a+427d+925p+\frac{912h}{5}=k$, we know that from the nature of the floor function to be maximized that it will have the same value for all $10,\!000 j \leq p < 10,\!000 (j+1)$ and since $f$ is linear in $a,d,$ and $h$ and so is the constraint solved for $p$ we can tell that selecting the leftmost endpoint of our interval on $p$ will maximize $f$, hence $p\in \left\{ 10,\!000 j | j\in\mathbb{Z}^{+}\right\}$. Are you with me so far? Did I make a mistake?

No. What you did is fine. The LP solutions I wrote in #7 are incorrect, as is the rest of the discussion! Somehow, I had entered some wrong data and so was solving the wrong problems. The solutions to the actual problems P1 and P2 in #7 are:
\begin{array}{cl}
\text{P1:} & Z_1 = 6,\!852,\!878.2895\\
& a = 0, \; d=0 \\
& h= 2,\!284,\!292.7632 \\
&p = 0 \\
\text{P2:} & Z_2 = 5,\!330,\!016.4474\\
&a = 0, \; d = 0\\
& h = 1,\!776,\!672.1491 \\
& p = 10,\!000
\end{array}
Anyway, we can get these in closed-form, and can actually develop a formula for the maximum profit $MP(j)$ in terms of your $j$-value; it is a quadratic function of $j$, so can be optimized easily for any given value of the right-hand-side $k$. Very large numbers tend to be involved, so you either need to scale the problem or else use double or triple (or higher) precision arithmetic.

Let $C_j = 2 + .01 (50+j) = 2.5 + 0.01 j,$ corresponding to $\text{floor}(50+0.0001 p)$ for $10,\!000 j \leq p < 10,\!000 (j+1).$ In that notation the $j$th problem becomes
$$\begin{array}{rcl}
\text{P}_j :& \max &Z_j = c_2 (4a + 3d+ 3h + c_1) C_j\\
&\text{s.t.}& 1439 a +427 d + 9259 p + (912/5) h = k\\
& & 10,\!000 j \leq p \leq 10,\!000(j+1) \\
& & a, d, h \geq 0
\end{array}
$$
Note that we have replaced the strict inequality $p < 10,\!000 (j+1)$ by the non-strict version, but that will turn out to not matter.

First, note that if $c_2 > 0$ remains constant throughout, it can be dropped, because it just scales the value of $Z_j$ without affecting the location of the maximum. Next, note that for fixed $j$ we can omit the positive constant multiplicative constant $C_j$ and the additive constant $c_1$ for the same reason: the solution $(a,d,h,p)$ will not change if we omit them.

So, for fixed $j$ we have the simple problem to maximize $z = 4a + 3d + 3h$, subject to $1439 a +427 d + 9259 p + (912/5) h = k$ and simple bounds $a, d, h \geq 0, 10,\!000 j \leq p \leq 10,\!000(j+1).$

Use the constraint equation to solve for $h$ in terms of the other variables:
$$h =\frac{5}{912} k -\frac{7195}{912} a-\frac{2135}{912} d- \frac{46295}{912} p $$
Substitute this into the $z$-equation:
$$ z = \frac{5}{530} k -\frac{5979}{304} a- \frac{1223}{304} d- \frac{46295}{304} p$$
Note that we obtain $z = 5 k/530$ if $a=d=p=0$, but it we increase $a$ or $d$ or $p$ to positive levels, we obtain a smaller value of $z$; that is because of the fact that all the coefficients of $a,p,d$ are $< 0$ in the re-written $z$-equation.

In other words, we maximize $z$ by making the right-hand-side variables $a,d$ and $p$ as close to 0 as we can. The solution will thus have $a = d = 0$ and $p$ as small as possible---that is, $p = 10,\!000 j.$ Therefore, the complete maximum profit function in problem $P_j$ is
$$MP(j) = c_2 \left( \frac{5}{530} k - \frac{46295}{304} 10,000 j + c_1 \right) (2.5 + 0.01 j ) .$$
This is valid as long as
$$h = \frac{5}{912} k -\frac{46295}{912} 10,\!000 j \geq 0.$$
So, for some values of $k$ only $j=0$ is allowed. For other values of $k$ both $j=0$ and $j=1$ are allowed, etc. Finding the best $j$ ought to be easy because $MP(j)$ is a quadratic function of $j$. That means we can set the derivative to zero, then compare the $z$ value at the two neighboring integer values of $j$. If that "solution" outside the allowed range of $j$ the optimal $j$ is at the limit of its range for the given $k$.

BTW: the linear-programming problem was easy to solve by inspection because we re-wrote it in an appropriate way. That is essentially how the simplex method of liner programming works: we figure out how to re-write the equations until the solution becomes obvious by inspection. Problems having tens of thousands of constraints and hundreds of thousands of variables are solved that way. Sometimes we can even solve real-world industrial problems having hundreds of thousands to some millions of constraints, and millions of variables in that way too, but often we would prefer good approximate solutions that can be obtained faster and more cheaply.