¿Funciona KKT también para problemas no convexos?

Question

Quiero asegurarme de que la siguiente afirmación es correcta. Por favor, dígame lo que piensa.

"Supongamos que tenemos un problema de minimización restringido no convexo y no lineal. La función objetivo y todas las restricciones son diferenciables. En primer lugar, puedo demostrar que la LICQ se mantiene en todos los puntos del espacio. Luego, aplico las condiciones necesarias de primer orden (KKT) y encuentro que todos los puntos satisfacen estas condiciones. Mi afirmación es que basta con comprobar el valor de la función objetivo en esos puntos (que satisfacen las condiciones KKT) y elegir el que conduzca al menor valor objetivo. Ese punto (o quizás puntos) sería el mínimo global del problema".

Editar : Supongamos que el problema tiene un mínimo.

¿Hay algún problema con esta afirmación? ¿La no-convexidad supone algún problema para utilizar las condiciones KKT? Por cierto, utilizo las condiciones KKT de esta página .

Answer 1

Es correcto si existe un óptimo (es suficiente si, por ejemplo, el conjunto factible es compacto). Las condiciones de primer orden son necesario condiciones, por lo que un óptimo global debe satisfacerlas. Si se tiene un número finito de puntos que satisfacen las condiciones necesarias, basta con comprobarlos todos.

Sin embargo, para los problemas convexos (y algunos otros), las condiciones también son suficiente lo que significa que cualquier punto que satisfaga las condiciones será necesariamente un óptimo global.

Answer 2

Esta afirmación no es cierta. Las condiciones KKT sólo son necesarias para la optimalidad. Ejemplo: considere el problema

$min\; f(x)=x^3,$ s.t $\;x\leq 1.$ Este problema satisface la LICQ en cada punto. Además, el problema es ilimitado, por lo que ningún punto KKT (x=0 es al menos uno de ellos) es un mínimo de la función.

$\textbf{EDIT:}$ Aunque la función esté acotada por abajo, la afirmación no es cierta. Ejemplo:

$min\; \frac{1}{x^2+1},$ s.t $x\leq 0.$

Por otro lado, las condiciones KKT son suficientes para la optimización cuando la función objetivo y las restricciones de desigualdad son convexas, y las restricciones de igualdad son afines.