KKT y la condición de Slater

Question

Estaba estudiando el libro de texto de Stephen Boyd y me confundí en la parte de KKT. El libro dice lo siguiente:

"Para cualquier problema de optimización convexo con función objetivo y restricción diferenciables, cualquier punto que satisfaga las condiciones KKT es óptimo primario y dual y tiene una brecha de dualidad nula. "

Por lo tanto, parecía que si encuentro cualquier punto (x, $\lambda$ , $\nu$ ) que satisface la condición KKT, x será un óptimo primario. Entonces, más adelante dice lo siguiente

"Si un problema de optimización convexo con funciones objetivo y de restricción diferenciables satisface la condición de Slater, entonces las condiciones KKT proporcionan condiciones necesarias y suficientes para la optimalidad: La condición de Slater implica que la brecha de dualidad óptima es cero y que se alcanza el óptimo dual, por lo que x es óptimo si y sólo si existen ( $\lambda$ , $\nu$ ) que, junto con x, satisfacen la condición KKT".

La inclusión de la condición de Slater en la segunda frase me confunde. La primera frase suena como cualquier (x, $\lambda$ , $\nu$ ) que satisface las condiciones KKT (aunque la condición de Slater no se cumpla) es un óptimo primario. Entonces, la segunda frase dice que KKT se convierte en la condición necesaria y suficiente cuando se cumple la condición de Slater.

¿Puede alguien aclarar esto? Para encontrar un óptimo primario, ¿está bien encontrar sólo (x, $\lambda$ , $\nu$ ) que satisface la condición KKT? ¿O debo mostrar también la condición de Slater?

Answer 1

Creo que esto es lo que está diciendo (aunque podría estar equivocado):

(1) optimalidad + dualidad fuerte $\implies$ KKT (para todos los problemas)

(2) KKT $\implies$ optimalidad + dualidad fuerte (para problemas convexos/diferenciables)

(3) Condición de Slater + convexo $\implies$ dualidad fuerte, entonces tenemos, DADO que la dualidad fuerte se mantiene,

(3a) KKT $\Leftrightarrow$ optimalidad

Si, para un problema primal convexo/diferenciable, se encuentran puntos que satisfacen KKT, entonces sí, por (2), son óptimos con dualidad fuerte.

Answer 2

La respuesta de Ross B. me confunde. La respuesta de Zheng Jia es correcta pero no está clara. Permítanme elaborar un poco más.

El enunciado general no requiere diferenciabilidad, ya que la convexidad ya implica la existencia del subgradiente. La condición general de KKT puede enunciarse en términos de subgradiente. Para cualquier programa convexo, $(x,y)$ es un par de soluciones óptimas primarias y duales si es un punto de silla del Lagrangiano si satisface las condiciones KKT. Creo que a esto se le suele llamar el Teorema del punto de silla. Sin embargo, un programa convexo puede no tener una solución óptima dual. Pero, si el programa convexo satisface la condición de Slater, entonces existe una solución óptima dual. Esta es la historia detrás del comentario de Stephen Boyd.

La prueba es sorprendentemente sencilla. Véase la sección 28 Análisis convexo de Rockafellar.

Lo mejor,

Xiang

Answer 3

Supongamos que tenemos $C^1$ funciones implicadas en el problema de optimización:

En general, las condiciones KKT NO TIENEN QUE SER SATISFECHAS en una solución óptima. Sin embargo, las condiciones de Fritz John deben satisfacerse siempre. De hecho, la condición de Fritz John es una generalización de las condiciones KKT. Las condiciones de Fritz John se reducen a las condiciones KKT si se satisfacen algunas condiciones de regularidad en ese punto. La condición de Slater es una condición de regularidad que garantiza la reducción de las condiciones de Fritz John a las condiciones KKT, es decir, las condiciones KKT deben cumplirse si se satisface la condición de Slater.

Nótese que KKT no es necesario aunque tengamos un problema convexo. Pero, si se encuentra un punto que satisface las condiciones KKT de un problema convexo, entonces es uno de los optimizadores aunque no se cumpla ninguna de las condiciones de regularidad. En otras palabras, tenemos:

(1) Fritz John's DEBE mantenerse en un punto estacionario.

(2) Una condición de regularidad (como Slater) $\implies$ Condiciones KKT.

(3) KKT + convexidad $\implies$ optimalidad (con brecha de dualidad cero).

En consecuencia:

(4) Una condición de regularidad (como Slater) + convexidad $\implies$ optimalidad (con brecha de dualidad cero).

Answer 4

Sin la condición de Slater, KKT es una condición suficiente. Con la condición de Slater, KKT es una condición necesaria y suficiente. Referencia: página 537 del libro Lectures on Modern Convex Optimization. Este es un muy buen libro de referencia.