¿Cómo resolver este problema de optimización polinómica utilizando las condiciones KKT?

Question

Estoy tratando de encontrar una receta general para un problema de optimización no lineal con restricciones. Por favor, corrijan los errores o las partes que faltan.

$$\begin{aligned} &\min &f(x,y)&=xy+y^3\\ &\text{such that }&x &\geq y^2\\ &&x+y&\leq 2 \end{aligned}$$

Escriba en forma de problema de maximización estándar

$$\begin{aligned} &\max &&-xy-y^3\\ &\text{such that }&y^2-x &\leq 0\\ &&x+y&\leq 2 \end{aligned}$$

Encuentre puntos factibles en los que no se cumpla la CQ (calificación de la restricción) de Kuhn-Tucker.

$$\text{gradient 1st constraint: } (-1, 2y)\\ \text{gradient 2nd constraint: } (1,1)$$

La primera restricción del gradiente nunca es linealmente dependiente. (nunca es igual a $(0,0)$ para cualquier $y$ )

La segunda restricción del gradiente nunca es linealmente dependiente.

Ambos gradientes de las restricciones son linealmente dependientes si $y=-\frac{1}{2}$

Tenga en cuenta que la segunda restricción en este caso es vinculante si $x=2\frac{1}{2}$ . Entonces la primera restricción no es vinculante: $y^2-x=\frac{1}{4}-2\frac{1}{2}\neq 0$ . Como la calificación CQ sólo se aplica a las restricciones vinculantes (y aquí no es vinculante), concluimos que CQ se mantiene para todos los puntos factibles.

¿Qué se hace si se encuentra un punto factible en el que no se cumple CQ? (donde el punto es vinculante para todas(?) las restricciones)

Si hay más de 2 restricciones, ¿se comprueban también por parejas?

Escriba las condiciones del KT

Primero escribe el Lagrangiano: $\mathcal{L}=-xy-y^3-\lambda(y^2-x)-\mu(x+y-2)$

Tomar las derivadas parciales, ponerlas igual a $0$

$$\begin{aligned} \text{KT conditions: }&-y +\lambda-\mu&=0\\\ &-x-3y^2-2\lambda y-\mu&=0\\ &\lambda,\mu&\geq 0\\ &\lambda(y^2-x)&=0\\ &\mu(x+y-2)&=0 \end{aligned}$$

Encuentra todos los puntos que satisfacen las condiciones KT

Especialmente la tercera restricción es importante, ya que induce 4 casos:

(a) $\lambda =0,\mu=0$

(b) $\lambda =0,\mu>0$

(c) $\lambda>0, \mu=0$

(d) $\lambda>0, \mu>0$

(a): $\lambda =0,\mu=0\stackrel{eq. 1}{\implies} y=0\stackrel{eq. 2}{\implies}x=0$ que satisfacen todas las condiciones.

(b): $\lambda =0,\mu>0\stackrel{eq. 5}{\implies}x+y=2\iff -x = y-2$ . También $eq. 1$ implica $y=-\mu$ . Lo sustituimos en la segunda ecuación. $y-2-3y^2+y=0$ , resolviendo esto da,

$$3y^2-2y+2=0\implies y=\frac{2\pm\sqrt{4-24}}{6}\notin\mathbb{R}\text{ contradiction}$$

(c) $\lambda>0, \mu=0\stackrel{eq. 4}{\implies} y^2-x=0\implies -x=-y^2$ . También $eq. 1$ implica $\lambda = y$ . Enchufa esto $eq. 2$ da,

$$-y^2-3y^2-2y^2=0\iff y=0, \text{ contradiction as }y=\lambda>0$$

(d) $\lambda>0, \mu>0$ implica $y^2-x=0\implies x=y^2$ y $x+y-2=0$ . Introduce aquí la primera en la segunda ecuación, $y^2 + y - 2=0$

$$y^2+y-2=0\implies y=\frac{1}{2}(-1\pm\sqrt{9})=1\text{ or } 2.$$

Entonces $x=1$ o $4$ . Así, $(x,y)=(1,1)\text{ or }(4,-2)$ .

Dejemos que $(x,y)=(1,1)$ , $\lambda-\mu=1\implies \lambda=1+\mu$ . Enchufe en $eq. 2$

$$-1-3-2\lambda-\mu=0\\ \mu=-2 \text{ contradiction as }\mu>0$$

Dejemos que $(x,y)=(4,-2)$ entonces $-\mu=-2-\lambda$ sustituyendo la ginebra $eq. 2$ da $\lambda=6,\mu=8$

Ahora tenemos 2 puntos: $(0,0)$ con $\lambda=0, \mu=0$ y $(4,-2)$ con $\lambda=6, \mu=8$

Aplicar el Teorema del Valor Extremo (EVT) si es posible

El conjunto factible es compacto y $xy+y^3$ es continua por lo que se aplica la EVT.

$$f(0,0)=0, \quad f(4,-2)=-16\implies \min \text{ at } (4,-2)$$

Hecho. (las preguntas están en cursiva )

Answer 1

Si $(x,y)=(4,-2)$ obtenemos un valor $-16$ .

Vamos a demostrar que es un valor mínimo.

De hecho, nuestras condiciones dan $$y+y^2\leq x+y\leq2,$$ que da $$-2\leq y\leq1.$$

Además, es obvio que $x\geq0.$

Así, $$xy+y^3\geq -2x+y^3\geq-2(2-y)+y^3=y^3+2y-4\geq-16$$ ¡y hemos terminado!

Answer 2

Al aplicar la condición de KKT necesaria hay que calcular lo siguiente:

1. Demuestre que el óptimo existe utilizando la EVT. A veces, cuando el conjunto no es compacto, se pueden hacer algunos trucos (cortando los puntos del conjunto que no son importantes para la optimización) para encontrar un problema equivalente con un conjunto compacto.
2. Enumerar todos los puntos "patológicos", es decir, los puntos en los que no se cumple la condición CQ.
3. Enumerar todos los puntos KKT.
4. Elige el candidato de 2,3 que da el valor óptimo de la función objetivo.

Por lo tanto, si encuentra un punto en el que los gradientes de las restricciones vinculantes no satisfacen la condición CQ, sólo tiene que añadirlos a la lista de candidatos a probar en 4. Si hay más de 2 restricciones, por ejemplo, si tiene tres restricciones, entonces tiene que probar $2^3-1$ casos: $3$ cuando sólo uno es vinculante, $3$ cuando dos de ellos son vinculantes y $1$ caso cuando los tres son vinculantes. Para $n$ limitaciones, es $2^n-1$ casos para comprobar, en general. Es aproximadamente el mismo procedimiento que utilizó en los casos KKT (a), (b), (c), (d).