¿Por qué la optimización Karush-Kuhn-Tucker no pudo encontrar la solución?

Question

Tengo el siguiente problema de maximización de la utilidad: $$\max (xy)$$ $$(x+y-2)^2 \leq 0$$ Condiciones: $$y-2\lambda (x+y-2) =0$$ $$x-2\lambda (x+y-2) =0$$ $$\lambda(x+y-2)^2=0$$

Cuando pongo $\lambda>0$ me sale: $$(x+y-2)^2=0 \Rightarrow (x+y-2) = 0$$ $$y-2\lambda (x+y-2) = y = 0$$ $$x-2\lambda (x+y-2) = x = 0$$

Pero la solución obvia es $x=y=1$ .

Cuando pongo $$\lambda=0$$ tampoco es un caso con una solución válida. ¿La restricción es demasiado baja? ¿Cuál es la explicación a esto?

Le agradecería mucho su ayuda.

Answer 1

Como señaló @user32416 las condiciones de estacionariedad de primer orden no son suficientes. En concreto parece que se viola La condición de Slater que establece que "la región factible debe tener un punto interior". No hay $x,y$ para lo cual $$(x+y-2)^2 < 0.$$

Si se replantea el problema a $$\max (xy)$$ $$x+y-2 = 0$$ $$x,y \geq 0$$ Se cumple la condición de Slater (para condiciones lineales no son necesarios puntos interiores) y se puede aplicar Karush-Kuhn-Tucker.

Answer 2

Esta es una pregunta mal planteada. Incluso sin pasar por KKT, su restricción $(x + y - 2)^2 \le 0$ , ya que el lado izquierdo es un cuadrado, significa que la única solución factible es aquella en la que la igualdad se une; es decir $(x + y - 2)^2 = 0$ o que $|x + y - 2| = 0$ -- de lo que dice que $x = y = 1$ es una solución.

Answer 3

Algunas confusiones y afirmaciones incorrectas en las respuestas ya dadas, incluida la respuesta "aceptada". (Por ejemplo, se confunden las distinciones obvias entre la necesidad y la suficiencia de diferentes condiciones para KKT).

Existen diferentes formulaciones del teorema de KKT. Los teoremas KKT que uno podría considerar para su ejemplo son los siguientes.

Para simplificar la anotación, $(x,y)$ será sustituido por $x$ . Para el problema de optimización con restricciones $$ \max_{g(x) \leq 0} f(x), \quad (*) $$ considerar las condiciones KKT

\begin{align} \mbox{(i) } \nabla f &= \lambda \nabla g, \; \mbox{for some } \lambda \geq 0 , \\ \mbox{(ii) } \lambda g &= 0 \mbox{ (complementary slackness) }. \end{align}

Teorema (KKT general) Si $x$ es un máximo local de $(*)$ donde $\nabla g(x) \neq 0$ entonces (i) y (ii) se cumplen en $x$ .

La condición $\nabla g(x) \neq 0$ se denomina condición de "calificación de la restricción". En otras palabras, las condiciones KKT (i) y (ii) son necesario condiciones para local máximos en los que se cumple la calificación de la restricción. No dice nada sobre los máximos globales.

Incluso un máximo local en el que falle la calificación de la restricción no tiene por qué estar en el conjunto de soluciones de (i) y (ii).

Para su ejemplo, la calificación de la restricción falla en los máximos globales $x^* = (1,1)$ , $\nabla g(x^*) = 0$ . Así que el KKT general no se aplica.

Teorema (KKT bajo concavidad) Supongamos que $f$ es cóncavo y $g$ es convexo. Si (i) y (ii) se cumplen en $x$ entonces $x$ es un máximo global de $(*)$ .

En otras palabras, cuando $f$ es cóncava y $g$ es convexo, entonces (i) y (ii) son suficiente condición para global máximo.

En su ejemplo, $f$ es cóncavo y $g$ es convexo. Pero el conjunto de soluciones de (i) y (ii), con $g \leq 0$ es vacía son condiciones vacías. Así que KKT bajo concavidad no se aplica.

Teorema (KKT bajo concavidad y condición de Slater) Supongamos que $f$ es cóncavo, $g$ es convexo, y la condición de Slater ( $\{g <0 \}$ es no vacía) se mantiene . Si (i) y (ii) se cumplen en $x$ entonces $x$ es un máximo global de $(*)$ .

En otras palabras, bajo la condición de Slater (i) y (ii) son ahora necesario para el máximo global.

En tu ejemplo, la condición de Slater no se cumple. De hecho, las condiciones de KKT (i) y (ii) no pueden ser necesarias - porque, sabemos (ya sea por Weierstrass, o simplemente por la inspección como lo has hecho) una solución a $(*)$ existe mientras que (i) y (ii) no tiene solución en $\{ g \leq 0 \}$ .

La condición de Slater es también una especie de calificación de restricciones. Es no relacionados con la holgura complementaria. Se puede convertir el problema original $(*)$ a una con restricción de igualdad y aplicar el Teorema de Lagrange, en lugar de KKT, pero entonces hace no tiene sentido hablar de la condición de Slater.

Tampoco es correcto decir que el problema está mal planteado. Un problema de maximización es mal planteado si no tiene solución. En este caso, $(*)$ está claramente bien planteada. La cuestión es la aplicabilidad de los teoremas KKT.

En resumen, la inspección de los enunciados precisos de varios teoremas de KKT le indica que los resultados de KKT no se aplican al (contra)ejemplo dado.

Answer 4

Como ya se ha señalado, la restricción es tal que se convierte en un igualdad restricción. Su problema se simplifica entonces a

$$\max_{x,y} (xy) \;\;\; s.t.\;\; x+y-2=0$$

Reordenar la restricción y sustituirla por $y$ para obtener el problema sin restricciones de una sola variable

$$\max_{x} (2x-x^2)$$

Esto proporciona inmediatamente la solución $x=1$ y así también $y=1$ .

Utilizar las condiciones de Karush-Kuhn-Tucker en el problema original, puede ser una buena práctica para comprobar que el holgura complementaria La condición de Slater también debe cumplirse (y la "condición de Slater" es una de las formulaciones de la misma), pero la navaja de Occam exigiría que el problema se resolviera realmente como en el caso anterior.