Exact solution to nonconvex optimization problem

Question

I would like to minimize $v+w+x+y+z$ subject to the following:

$$\frac{v+w}{x+y+z}=\frac{y}{z}=\frac{w}{x+y}$$

where $v,w,x,y,z\ge 1$

I tried entering this problem in WolframAlpha:

Minimize[{v + w + x + y + z, (v+w)/(x+y+z) == y/z &&  y/z== w/(x+y)&& v >= 1 && x >= 1 && y >= 1 && w >= 1 && z >= 1}, {v, w, x, y, z}]

It found a global min at $(v,w,x,y,z)=(1,\sqrt{2},1,1,\sqrt{2})$. What techniques might WolframAlpha be using to find this solution?

Answer 1

• Simplifying the constraints. Set $$ t=\frac{x+y+z}{v+w}=\frac{z}{y}=\frac{x+y}{w}, $$ then $$ \left\{ \begin{array}{rcl} x+y+z&=&t(v+w),\\ z&=&ty,\\ x+y&=&tw \end{array}\right. \quad\Rightarrow\quad y=v, $$ and the problem becomes $$ \min\, (1+t)(y+w)\quad\text{subject to } \left\{ \begin{array}{rcl} 1&\le&ty,\\ 1+y&\le&tw,\\ 1&\le&y,\\ 1&\le&w. \end{array}\right.\quad\Leftrightarrow\quad \left\{ \begin{array}{rcl} 1-ty&\le&0,\\ 1+y-tw&\le&0,\\ 1-y&\le&0,\\ 1-w&\le&0. \end{array}\right.\tag{*} $$
• Applying the KKT necessary condition. $$ \left\{ \begin{array}{rcl} 1+t-\mu_1t+\mu_2-\mu_3&=&0,\\ 1+t-\mu_2t-\mu_4&=&0,\\ y+w-\mu_1y-\mu_2w&=&0,\\ \mu_1(1-ty)&=&0,\\ \mu_2(1+y-tw)&=&0,\\ \mu_3(1-y)&=&0,\\ \mu_4(1-w)&=&0,\\ \mu_k\ge 0\text{ and }(*) \end{array} \right.\quad\Leftrightarrow\quad \left\{ \begin{array}{rcl} 1+(1-\mu_1)t+\mu_2-\mu_3&=&0,\quad(1)\\ 1+(1-\mu_2)t-\mu_4&=&0,\quad(2)\\ (1-\mu_1)y+(1-\mu_2)w&=&0,\quad(3)\\ \mu_1(1-ty)&=&0,\quad(4)\\ \mu_2(1+y-tw)&=&0,\quad(5)\\ \mu_3(1-y)&=&0,\quad(6)\\ \mu_4(1-w)&=&0,\quad(7)\\ \mu_k\ge 0\text{ and } (*)&&\ \ \ \ \quad(8) \end{array} \right. $$
• Solution. Equation (3) together with feasibility (*) leaves only 2 possibilites:
  Case 1: $1-\mu_1\ge 0$, $1-\mu_2\le 0$ or
  Case 2: $1-\mu_1\le 0$, $1-\mu_2\ge 0$.

Consider those cases.
Case 1. We have $\mu_2>0$ and from (1) $\mu_3>0$, hence, from (5) and (6) it follows that $$y=1,\quad tw=1+y=2.$$ - Assume $\mu_1=0$. Then from (3) we have $(\mu_2-1)w=1$ and from (2) $\mu_4=1-t/w$.
If $\mu_4=0$ then $t=w=\sqrt{2}$ and the objective value is $\color{red}{(1+\sqrt{2})^2}$.
If $\mu_4>0$ then from (7) $w=1$, thus $t=2$ and the objective value is $\color{red}{6}$.
- Assume $\mu_1>0$. Then from (4) we get $1=ty=t$, thus $w=2$ and the objective value is $\color{red}{6}$.

Case 2. We have $\mu_1>0$ and from (2) $\mu_4>0$, hence, from (4) and (7) it follows that $$ w=1,\quad ty=1. $$ - Assume $\mu_2=0$. Then from (3) we get $(\mu_1-1)y=1$ and from (1) $\mu_3=1-t/y$.
If $\mu_3=0$ then $t=y=1$ and the objective value is $\color{red}{4}$.
If $\mu_3>0$ then from (6) $y=1$, hence, $t=1$ and the objective value is $\color{red}{4}$.
- Assume $\mu_2>0$. Then from (5) $1+y=tw=t$. It gives $1=ty=(1+y)y$ $\Rightarrow$ $y=\frac{1}{1+y}\le \frac12$. It is not possible as it contradicts $y\ge 1$.

Comparing the red objective values, it is clear that the smallest is for $y=1$, $t=w=\sqrt{2}$. Finally, $x=tw-y=1$, $z=ty=\sqrt{2}$ and $v=y=1$.