¿Por qué las condiciones KKT son suficientes en este caso?

Question

Necesito resolver este problema:

minimizar $f(x,y)=5x-xy-50+10y$

con sujeción a:

$g_1(x,y)=18-xy\leq0$

$g_2(x,y)=x+y-11\leq0$

$x,y\geq0$

He encontrado la solución óptima: $(x,y)=(6,3)$ Pero la matriz hessiana de la función objetivo es indefinida. Mi pregunta es, ¿por qué las condiciones KKT son suficientes en este caso? O si no lo son, ¿conforme a qué condición suficiente es correcta la solución óptima?

Gracias de antemano.

Answer 1

Sugerencia: ¿puedes demostrar que es cuasi-convexo?

$$\forall h,\, Df(x)\cdot h = 0 \Longrightarrow h^T\cdot D^2f(x) \cdot h \ge 0$$

Es decir, sólo nos importan las direcciones $h$ que son ortogonales al gradiente.

$$f_x\cdot h_1+f_y\cdot h_2=(5-y)h_1+(10-x)h_2 = 0\Rightarrow h_2=\dfrac{5-y}{10-x}h_1$$ $$ h^T\cdot D^2f(x) \cdot h = -2h_1\cdot h_2$$ $$ -2\dfrac{5-y}{10-x}h_1^2 \ge 0\Leftrightarrow \mathrm{sign} \;y-5=\mathrm{sign}\, 10-x$$

Es decir, o bien $y> 5$ implica $x<10$ o $y<5$ implica $x>10$ .

¿Tal vez podríamos argumentar que esto ocurre en el conjunto de restricciones? No estoy seguro, de nuevo sólo una sugerencia demasiado larga para ser un comentario.

Answer 2

En la optimización cuadrática no convexa, a la que pertenece su problema, todo es posible. Una solución puede ser un punto KKT o no puede serlo. Esto depende de cada caso y es difícil de decir antes de resolver el problema. Sin embargo, para problemas cuadráticos pequeños con pocas restricciones. También probar que un punto KKT es un óptimo local puede ser extremadamente difícil.

En la programación cuadrática no convexa, una forma posible de demostrar la optimalidad de algún punto es resolver el problema dual. Si se resuelve el problema dual y el valor mínimo encontrado en el problema original coincide con el valor del problema dual, entonces se ha terminado. (Ver http://en.wikipedia.org/wiki/Quadratic_programming para la programación cuadrática y http://www.stanford.edu/class/ee392o/relaxations.pdf para la dualidad de Lagrange en la programación cuadrática).

Nótese que esta última estrategia no siempre es posible ya que puede existir la brecha de dualidad, es decir, no hay igualdad de los valores óptimos del problema dual y del primal.