Solución exacta a un problema de optimización no convexo

Question

Me gustaría minimizar $v+w+x+y+z$ con sujeción a lo siguiente:

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

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

He intentado introducir este problema en 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}]

Encontró un mínimo global en $(v,w,x,y,z)=(1,\sqrt{2},1,1,\sqrt{2})$ . ¿Qué técnicas podría utilizar WolframAlpha para encontrar esta solución?

Answer 1

• Simplificación de las restricciones . Establecer $$ t=\frac{x+y+z}{v+w}=\frac{z}{y}=\frac{x+y}{w}, $$ entonces $$ \left\{ \begin{array}{rcl} x+y+z&=&t(v+w),\\ z&=&ty,\\ x+y&=&tw \end{array}\right. \quad\Rightarrow\quad y=v, $$ y el problema se convierte en $$ \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{*} $$
• _La aplicación de la Condición necesaria de KKT_ . $$ \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. $$
• Solución . La ecuación (3) junto con la viabilidad (*) sólo deja dos posibilidades:
  Caso 1: $1-\mu_1\ge 0$ , $1-\mu_2\le 0$ o
  Caso 2: $1-\mu_1\le 0$ , $1-\mu_2\ge 0$ .

Considera esos casos.
Caso 1 . Tenemos $\mu_2>0$ y de (1) $\mu_3>0$ Por lo tanto, de (5) y (6) se deduce que $$y=1,\quad tw=1+y=2.$$ - Asumir $\mu_1=0$ . Entonces, a partir de (3) tenemos $(\mu_2-1)w=1$ y de (2) $\mu_4=1-t/w$ .
Si $\mu_4=0$ entonces $t=w=\sqrt{2}$ y el valor objetivo es $\color{red}{(1+\sqrt{2})^2}$ .
Si $\mu_4>0$ entonces a partir de (7) $w=1$ Por lo tanto $t=2$ y el valor objetivo es $\color{red}{6}$ .
- Asumir $\mu_1>0$ . Entonces, a partir de (4) obtenemos $1=ty=t$ Por lo tanto $w=2$ y el valor objetivo es $\color{red}{6}$ .

Caso 2 . Tenemos $\mu_1>0$ y de (2) $\mu_4>0$ Por lo tanto, de (4) y (7) se deduce que $$ w=1,\quad ty=1. $$ - Asumir $\mu_2=0$ . Entonces, a partir de (3) obtenemos $(\mu_1-1)y=1$ y de (1) $\mu_3=1-t/y$ .
Si $\mu_3=0$ entonces $t=y=1$ y el valor objetivo es $\color{red}{4}$ .
Si $\mu_3>0$ entonces a partir de (6) $y=1$ Por lo tanto, $t=1$ y el valor objetivo es $\color{red}{4}$ .
- Asumir $\mu_2>0$ . Entonces, a partir de (5) $1+y=tw=t$ . Da $1=ty=(1+y)y$ $\Rightarrow$ $y=\frac{1}{1+y}\le \frac12$ . No es posible ya que contradice $y\ge 1$ .

Comparando los valores de los objetivos rojos, está claro que el más pequeño es para $y=1$ , $t=w=\sqrt{2}$ . Finalmente, $x=tw-y=1$ , $z=ty=\sqrt{2}$ y $v=y=1$ .