A problem using Lagrange multiplier 3

My friend ask me to solve a problem for him, and he told me if I was gonna put it on MSE, I should say this is "dual problem of support vector machine"

Anyway, I can state the problem like this. Let $$f=x_1+x_2+x_3+x_4+x_5+x_6\\ -x_1^2-4x_2^2-2x_3^2-\frac{1}{2}x_5^2-\frac{1}{2}x_6^2\\-4x_1x_2-2x_1x_3-4x_2x_3 +x_1x_5+x_1x_6\\ +2x_2x_5+2x_2x_6+2x_3x_5$$ Find maximum and minimum of $f$ S.T. $x_i\geq0$ $\forall i$ and $x_1+x_2+x_3=x_4+x_5+x_6$.

I only know the Lagrange multipliers method and it seems not effective. So help me with this problem.

Thank you.

• This problem is much more complicated than you think. You have to maximize, resp. minimize, the function $f$ on a very intricate five-dimensional set embedded in ${\mathbb R}^6$. – Christian Blatter Mar 5 '17 at 16:54
• so do you have any suggestions? – chí trung châu Mar 6 '17 at 15:03
• The problem seems basic in principle no? It is asing for the max and min (not or) in the region bounded by $x_i$ greater than zero. The points will either be at the boundaries, ie. Where an $x_i$ is zero, infinite, or derivatives are zero. Consider the possibilities, but Lagrange multipliers should work if the expressions have sokutions, maybe approximation needs to be used like newton's method. – marshal craft Mar 10 '17 at 11:59
• @chítrungchâu: Why don't you replace $x_6$ by $x_1 + x_2 + x_3 - x_4 - x_5$ in $f$, to obtain a function of $5$ variables defined on the domain given only by $x_1, \dots, x_5 \ge 0$? – Alex M. Mar 10 '17 at 17:01
• @HandeBruijn: That is the quick part, corresponding to $x_i > 0, \ 1 \le i \le 5$. Next comes the annoying part, where you have to treat the boundary - and this is made of multiple cases (that's why I don't write an answer). – Alex M. Mar 12 '17 at 16:52

Minimization: By taking $x_1=x_4=t$, $x_2=x_3=x_5=x_6=0$ we get $$f(x)=2t-t^2\to -\infty,\quad \text{as }t\to +\infty,$$so the minimum does not exists.

Maximization: let's replace $g:=-2f$ and minimize it. We substitute also $x_4=x_1+x_2+x_3-x_5-x_6$ and complete some squares to get \begin{align} g(x)&=2(x_1+2x_2+x_3)^2+2x_3^2+x_5^2-2x_5(x_1+2x_2+2x_3)+x_6^2-2x_6(x_1+2x_2)-\\ &-4(x_1+x_2+x_3) \end{align} and $x_1+x_2+x_3\ge x_5+x_6$ plus positivity constraints.

1. Try minimization w.r.t. $x_5$ first. The minimum without constraints would be at $x_5=x_1+2x_2+2x_3$, but then $$x_1+x_2+x_3\ge x_5+x_6\quad\Leftrightarrow\quad 0\ge x_2+x_3+x_6,$$ which together with positivity yields $x_2=x_3=x_6=0$. It means that the minimization w.r.t. $x_5$ is always going to be when the constraint is active, that is $$x_1+x_2+x_3=x_5+x_6.$$ (Either it does not let $x_5$ come to $x_5=x_1+2x_2+2x_3$ and becomes active, or it does, but becomes active there anyway.)
2. Let's substitute now $x_5=x_1+x_2+x_3-x_6$ and try minimization w.r.t. $x_6$ \begin{align} g(x)&=x_1^2+4x_1x_2+5x_2^2+2x_2x_3+x_3^2+2x_6^2-2x_6(x_1+x_2-x_3)-\\ &\quad -4(x_1+x_2+x_3)=\\ &=(x_1+2x_2)^2+(x_2+x_3)^2+2x_6^2-2x_6(x_1+x_2-x_3)-\\ &\quad -4(x_1+x_2+x_3) \end{align} subject to the constraint $x_1+x_2+x_3\ge x_6$ plus positivity. We have two possibilities here.

Case 1: $x_1+x_2-x_3\le 0$. Then the minimum is at $x_6=0$.

Case 2: $x_1+x_2-x_3\ge 0$. Then differentiation w.r.t. $x_6$ gives $$4x_6-2(x_1+x_2-x_3)=0\quad\Leftrightarrow\quad x_6=\frac12(x_1+x_2-x_3)\ge 0.$$ With this $x_6$ the constraint $x_1+x_2+x_3\ge x_6$ $\Leftrightarrow$ $x_1+x_2+3x_3\ge 0$ is satisfied. The function is convex in $x_6$ and we have found a feasible critical point, thus, it is the minimum w.r.t. $x_6$.

1. Continuing minimization in Case 1 above. We substitute $x_6=0$ and will have to minimize $$g_1(x)=(x_1+2x_2)^2+(x_2+x_3)^2-4(x_1+x_2+x_3)$$ subject to $x_1+x_2\le x_3$ plus positivity. Let's change the variables as $$y=x_1+2x_2,\quad z=x_2+x_3.$$ Then we need to minimize $$g_1=y^2+z^2-4(x_1+z)$$ subject to $0\le x_1\le y\le z$. Obviously, we have to take $x_1=y$ (as large as possible), hence $$g_1=y^2-4y+z^2-4z,\quad 0\le y\le z.$$ Differentiation gives the critical point $y=z=2$ which is feasible. The function is convex, thus, it is the minimum. Therefore, the minimization in Case 1 is solved as $$x=(2,0,2,0,4,0),\quad \min=-8.$$

2. Doing Case 2 above now. Substitute $x_6=\frac12(x_1+x_2-x_3)$ and minimize \begin{align} g_2&=\frac12x_1^2+3x_1x_2+\frac92x_2^2+x_1x_3+3x_2x_3+\frac12x_3^2-4(x_1+x_2+x_3)=\\ &=\frac12\left((x_1+3x_2+x_3)^2-8(x_1+x_2+x_3)\right) \end{align} subject to $x_1+x_2\ge x_3$ and positivity. The same change of variables $$y=x_1+2x_2,\quad z=x_2+x_3$$ gives $$2g_2=(y+z)^2-8x_1-8z,\quad 0\le x_1\le y,\ z\le y\le x_1+2z.$$ It is again obvious that minimization w.r.t. $x_1$ is done by $x_1=y$ (as large as possible), hence, $$2g_2=(y+z)^2-8(y+z),\quad 0\le z\le y,$$ and we get the minimum of $g_2$ as $-8$ when $y+z=4$.

3. Finally the maximization of $f$ has the parametric solution $$x=(2,0,2,0,4,0)+t(1,0,-1,0,-1,1),\quad 0\le t\le 2,$$ and the maximum is $4$.

• Looks interesting. I'll read through this to confirm validity to myself when I have time. +1 for now though, if only for the time you took to write this up. – Brevan Ellefsen Mar 16 '17 at 23:51
• I think the minimization not existing requires derivative tests even if the function does not have a global min on its domain it should on $x_i \ge 0$. – marshal craft Mar 17 '17 at 6:12
• @BrevanEllefsen Just for your information: I've used Maple to do substitutions, it is very cumbersome to do by hand. – A.Γ. Mar 17 '17 at 7:53
• @marshalcraft Derivative is a local information at a point, it cannot in general resolve existence of global minimum (if we do not have an assumption about a global structure of the function like convexity). A derivative test, e.g. KKT, is a necessary condition. It requires that the existence is verified in advance (usually it is done via Weierstrass theorem or its variants). – A.Γ. Mar 17 '17 at 7:58
• A.G. I did confused the plus minus infinities. Disregard my comment. – marshal craft Mar 17 '17 at 10:41

The three conditions on $x_i$'s can be replaced with two

$f(x_i)=2x_1+2x_2+2x_3-x_1^2-4x_2^2-2x_3^2-\frac{1}{2}x_5^2-\frac{1}{2}x_6^2-4x_1x_2-2x_1x_3-4x_2x_3+x_1x_5+x_1x_6+2x_2x_5+2x_2x_6+2x_3x_5$

and

$x_i \ge 0$.

A max or min of $f$ will occur either at a boundary or an extremum. One of these conditions will be met.

If $x_i$ is a local max or min then

I) $x_i=0$ for some $i$

II) $\nabla_ \mathbf v f(x_i) =0, \\ \forall {\mathbf v}$

$\nabla f_1=2-2x_1-4x_2-2x_3+x_5+x_6$

$\nabla f_2=2-8x_2-4x_1-4x_3+2x_5+2x_6$

$\nabla f_3=2-4x_3-2x_1-4x_2+2x_5$

$\nabla f_5=-x_5+x_1+2x_2+2x_3$

$\nabla f_6=-x_6+x_1+2x_2$

$\nabla f_i =0$ because $\nabla \mathbf v f =0$ when $\nabla f \cdot \mathbf v =0$ for all $\mathbf v$.

This is five equations and five unknowns. Expressed best as a linear transformation similar to the comments.

$$\begin{bmatrix} -2 & -4 & -2 & 1 & 1 \\ -4 & -8 & -4 & 2 & 2 \\ -2 & -4 & -4 & 2 & 0 \\ 1 & 2 & 2 & -1 & 0 \\ 1 & 2 & 0 & 0 & -1 \\ \end{bmatrix}\begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_5 \\ x_6 \\ \end{bmatrix}=\begin{bmatrix} -2 \\ -2 \\ -2 \\ 0 \\ 0 \\ \end{bmatrix}$$

The inverse is sought as it allows to solve for $\mathbf x$ in $\mathbf A \mathbf x = \mathbf 0 + \mathbf c$

But typically you can just use Gaussian elimination method to reduce to upper diagonal with leading coefficient of $1$. Solving for the $x_i$.

These solutions will be possible max, min, or inflexion. Additional possible max or min in which will not be covered above are all the combinations of $x_i$ where at least one are zero. But $\nabla_{\mathbf v} f$ may not be zero here. One solution is to reduce $f$ by having combinations of $x_i$ be zero and minimizing the resulting function as above. Is it $5!$ possibilities or 121 equations to take derivitive of and check $f$ values?

You have

$$\begin{Bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{Bmatrix} \begin{Bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ x_5 \\ \end{Bmatrix} \begin{Bmatrix} 0 \\ 0 \\ 0 \\ x_4 \\ 0 \\ \end{Bmatrix}...$$

However this can be avoided by considering the entire domain for example, if we were so lucky that it only had one derivative having a value of zero while simultaneously the second derivative being constant; there would be no need to check the boundaries.

$\nabla (\nabla f \cdot \mathbf v) \cdot \mathbf v= \nabla^2 f \Vert \mathbf v \Vert ^2$

Edit

After some thought you do not have to test each of the combinations of $x_i$ as those points lay on the individual curves/hyper surfaces intersecting $f$ and $x_i=0$. Therefore there are give additional equations each the intersection of

$f(x_i)$ and $x_i=0$ for each $i$.

This gives each four equations and four unknowns. The max/min needs to be found and you proceed with the same procedures as before.

Simply compare these zeros with the earlier ones and select the max/ min respectively (throw away ones here less than zero).

Edit 2

You actually do have to test the 120 or however many points as well. Sorry.

Edit 3

Should be $5+4+3+2+1+1=16$ funtions to minimize not 121.

• As I commented to AlexM above: after you have substituted $x_4$ you cannot just forget that $x_4\ge 0$. The constraint $x_1+x_2+x_3-x_5-x_6\ge 0$ has to be considered as well. – A.Γ. Mar 16 '17 at 13:35
• After selection of potential max/min you could simply check the positivity of $x_4$. – marshal craft Mar 17 '17 at 10:46
• Unfortunately, it is not going to work. Example: minimize $4y+x^2$ subject to $x,y\ge 0$, $x+y=1$. If we substitute $y=1-x$ and minimize $4-4x+x^2$, $x\ge 0$ we get $x=2$ that corresponds to the infeasible $y=-1$. The trouble is that we neglect $y=1-x\ge 0$ $\Leftrightarrow$ $x\le 1$, which does affect the minimization. – A.Γ. Mar 17 '17 at 11:46
• There is a famous example of bad elimination by Fletcher: minimize $x^2+y^2$ subject to $(x-1)^3=y^2$. Elimination of $y^2$ totally changes the minimization problem as the constraint implicitly imposes the bound $x\ge 1$ that disappears after elimination. – A.Γ. Mar 17 '17 at 12:03
• Ok I think I understand what your saying. That having a second constraint equation imposes in this case an additional constraint because $x$ can not be between zero and one and satisfy everything here in the comments and similarly for $x_4$. That is fine though because I could get rid of a min/max that doesn't fit. But I see that it could completely miss cases when $x_4=0$? I'm not sure exactly how this is working? – marshal craft Mar 17 '17 at 15:23