7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Christian Blatter Mar 5 '17 at 16:54
  • $\begingroup$ so do you have any suggestions? $\endgroup$ – chí trung châu Mar 6 '17 at 15:03
  • $\begingroup$ 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. $\endgroup$ – marshal craft Mar 10 '17 at 11:59
  • 1
    $\begingroup$ @chí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$? $\endgroup$ – Alex M. Mar 10 '17 at 17:01
  • 1
    $\begingroup$ @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). $\endgroup$ – Alex M. Mar 12 '17 at 16:52
3
+50
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Brevan Ellefsen Mar 16 '17 at 23:51
  • $\begingroup$ 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$. $\endgroup$ – marshal craft Mar 17 '17 at 6:12
  • $\begingroup$ @BrevanEllefsen Just for your information: I've used Maple to do substitutions, it is very cumbersome to do by hand. $\endgroup$ – A.Γ. Mar 17 '17 at 7:53
  • $\begingroup$ @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). $\endgroup$ – A.Γ. Mar 17 '17 at 7:58
  • $\begingroup$ A.G. I did confused the plus minus infinities. Disregard my comment. $\endgroup$ – marshal craft Mar 17 '17 at 10:41
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – A.Γ. Mar 16 '17 at 13:35
  • $\begingroup$ After selection of potential max/min you could simply check the positivity of $x_4$. $\endgroup$ – marshal craft Mar 17 '17 at 10:46
  • $\begingroup$ 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. $\endgroup$ – A.Γ. Mar 17 '17 at 11:46
  • 1
    $\begingroup$ 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. $\endgroup$ – A.Γ. Mar 17 '17 at 12:03
  • $\begingroup$ 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? $\endgroup$ – marshal craft Mar 17 '17 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.