1
$\begingroup$

I was working on a maximization problem that can be reduced to maximizing $$f(a,b,c,d)= ab + bc + cd $$ subject to the constraint $$a +b +c +d = 63 $$ I thought that this was a trivial and straightfoward problem for the method of lagrange multiplier, so I defined the Lagrangian as $$\mathcal{L}(a,b,c,d,\lambda) = ab + bc + cd - \lambda (a +b +c +d - 63) $$ and setting the derivatives equal to 0, I got $$ b - \lambda = 0 \\ a + c - \lambda = 0 \\ b +d - \lambda = 0 \\ c - \lambda = 0 \\ a +b +c +d = -63 $$ That is a linear problem that can be re-stated as finding the solution for the system $Ax = b$ with $$ A = \begin{bmatrix} 0 & 1 & 0 & 0 & -1 \\ 1 & 0 & 1 & 0 & -1 \\ 0 & 1 & 0 & 1 & -1 \\ 0 & 0 & 1 & 0 & -1 \\ 1 & 1 & 1 & 1 & 0 \end{bmatrix}$$ and $$ b = \begin{bmatrix} 0 & 0 & 0 & 0 & -63 \\ \end{bmatrix}^T$$ to my surprise, this system is determined with only one solution for $a,b,c$ and $d$ $$ x = \begin{bmatrix} 0 & 31.5 & 31.5 & 0 \\ \end{bmatrix}^T$$ But a direct evalution of the function to maximize and the constrains shows that, for example, the vector $$ x = \begin{bmatrix} 31.5 & 31.5 & 0 & 0 \\ \end{bmatrix}^T$$ yields the same result for the function and is also part of the constraint surface, so it should be a critical point too, more over, there are infinetly many critical points, so way is the lagrange multipliers just giving me one result?

$\endgroup$
4
  • $\begingroup$ Where did this maximation problem come from? Either the teacher set you up with a trap, or the nature of the optimization problem is in doubt, and there are no optimal points. $\endgroup$ Commented Jun 24, 2019 at 4:17
  • $\begingroup$ Not that it matters here but in general you should put an additional multiplier on the objective function. If the constraint function has the gradient that vanishes on the constrained set those points will also be critical, see abnormal case. $\endgroup$
    – Conifold
    Commented Jun 24, 2019 at 6:27
  • $\begingroup$ An alternative that occurred to me is that you forgot to tell us that $a,b,c,d$ are all supposed to be non-negative. These additional constraints turn the set of possible values of $(a,b,c,d)$ into a compact set $K$ (a 3-simplex), implying that maxima and minima exist. In that case the lack of local extrema means that the extrema are on the boundary of $K$, and you need to study several problems with two constraints (or, eliminate one variable as in my answer, and then study the values at the boundary). $\endgroup$ Commented Jun 24, 2019 at 6:41
  • $\begingroup$ This was actually a geometric trivia some friend showed me, where the values should not only be non-negative but also integers. I just approached the problem with this to see quickly what I could get (and indeed, by luck, point me to the right direction) $\endgroup$
    – diegobatt
    Commented Jun 24, 2019 at 11:52

1 Answer 1

2
$\begingroup$

There is only one critical point but it is indefinite. This is seen for example by eliminating $d$ and studying the Hessian of the resulting unconstrained problem (see below for the details). Therefore there are no local extrema.

Your function is unbounded. For example, if we set $c=0$, then the constraint is satisfied by $d=63-a-b$, but this will not affect the value of $f$. Take a look: $$ f(a,b,0,63-a-b)=ab. $$ Clearly we can make this as large or as small as we wish, and there is no global maximum or minimum.


IMHO it is usually easier to use a linear constraint simply to eliminate one of the variables. If we here solve $d=63-a-b-c$ from the constraint, we get the function in three variables $$ g(a,b,c)=f(a,b,c,63-a-b-c)=ab-ac-c^2+63c. $$ Its gradient is $$ \nabla g(a,b,c)=(b-c,a,63-a-2c), $$ and this vanishes only at the critical point $P_1=(a,b,c)=(0,63/2,63/2)$. The Hessian of $g$ at $P_1$ is $$ H(g,P_1)=\left(\begin{array}{ccc}0&1&-1\\ 1&0&0\\ -1&0&-2\end{array}\right). $$ Its characteristic polynomial is $$ \chi_H(x)=\det(x I_3-H)=x^3+2x^2-2x-2. $$ We could solve for the zeros using Cardano, but for our purposes it suffices to check that $\chi_H(x)$ has zeros in the intervals $\lambda_1\in(-3,-2)$, $\lambda_2\in(-1,0)$, $\lambda_3=(1,2)$. Both signs occur, so the Hessian form is indefinite. In other words, $P_1$ is a saddle point. You can use Sylvester's criterion to reach the same conclusion — $P_1$ is not a local extremum.

$\endgroup$
4
  • $\begingroup$ Because the objective function is a quadratic form, this question can probably be handled with linear algebra alone. $\endgroup$ Commented Jun 24, 2019 at 4:43
  • $\begingroup$ This makes perfect sense. The only thing is left for me is a geometric intuition. In two dimensions if a point is critical then every point in it's sorrounding goes either "up", "down" or both (saddle). In that case this couldn't happen right? The other points that share the same function output value than the found critical point should also be critical points if I am picturing it right $\endgroup$
    – diegobatt
    Commented Jun 24, 2019 at 11:50
  • $\begingroup$ I don't agree with your last point @diegobatt. Surely around a saddle point the same value is attained at non-critical points also? $\endgroup$ Commented Jun 24, 2019 at 13:27
  • $\begingroup$ I was getting confused. Nevermind $\endgroup$
    – diegobatt
    Commented Jun 24, 2019 at 14:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .