A problem using Lagrange multiplier 3

Question

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.

Answer 1

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.

Answer 2

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$.

3. 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. $$

4. 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$.

5. 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$.