Es KKT condiciones necesarias y suficientes para cualquier problemas convexos?

Question

En Boyd Optimización Convexa, pp 243,

para cualquier problema de optimización ... para que la fuerte dualidad obtiene, cualquier par de primal y dual óptima puntos deben satisfacer las condiciones KKT

es decir, $\mathrm{strong ~ duality} \implies \mathrm{KKT ~ is ~ necessary ~ condition ~ for ~ optimal ~ solution}$

y en el pp 244,

(Cuando el primordial problema es convexo) si $\tilde{x}, \tilde{\lambda}, \tilde{\mu}$ son los puntos que satisfacen las condiciones KKT, a continuación, $\tilde{x}$ $(\tilde{\lambda}, \tilde{\mu})$ son primal y dual óptima, con cero de la dualidad de la brecha.

Si la dualidad de la brecha = 0, el problema satisface fuerte dualidad, y en el 3er párrafo:

Si un problema de optimización convexa ... cumple Slater condición, luego que las condiciones KKT de proporcionar las condiciones necesarias y suficientes de optimalidad

Para mí significa: (para cualquier convexo problemas de KKT, ya es suficiente para una óptima)

$$\mathrm{KKT} \implies \mathrm{optimal ~ with ~ zero ~ duality ~ gap} \implies \mathrm{strong ~ duality} \implies \mathrm{KKT ~ is ~ also ~ necessary}$$

así KKT es necesario y suficiente para cualquier problemas convexos? (Porque Slater condición puede ser satisfecho automáticamente para el cero de la dualidad de la brecha)

Answer 1

Las condiciones KKT no son necesarias para la optimalidad incluso para problemas convexos. Considere la posibilidad de $$ \min x $$ sujeto a $$ x^2\le 0. $$ La restricción es convexa. La única viable punto, por lo tanto el mínimo global, está dada por $x=0$. El gradiente de que el objetivo se $1$$x=0$, mientras que la pendiente de la restricción es cero. Por lo tanto, el KKT sistema no puede ser satisfecho.

Answer 2

Boyd y Vandenberghe considera convexo problemas de optimización de la forma \begin{align} \text{minimize} &\quad f_0(x) \\ \text{subject to} & \quad f_i(x) \leq 0 \quad \text{for } i = 1,\ldots, m \\ &\quad a_i^T x = b_i \quad \text{for } i = 1,\ldots, p, \end{align} donde $f_0,\ldots, f_m$ son funciones convexas. La optimización de la variable es $x \in \mathbb R^n$. (Véase la ecuación (4.15), pág. 136 en Boyd y Vandenberghe.)

Vamos $x \in \mathbb R^n$, $\lambda \in \mathbb R^m$, y $\nu \in \mathbb R^p$. A continuación, las dos sentencias siguientes son equivalentes:

1. $x$ $(\lambda,\nu)$ juntos satisfacer las condiciones KKT.
2. $x$ $(\lambda,\nu)$ son primal y dual óptima, y la fuerte dualidad se mantiene.

Si Slater se satisface la condición, luego fuerte dualidad está garantizado para mantener, y lo podemos hacer de una forma más simple y más útil declaración. En este caso, los siguientes son equivalentes:

1. $x$ $(\lambda,\nu)$ juntos satisfacer las condiciones KKT.
2. $x$ $(\lambda,\nu)$ son primal y dual óptima.

Advertencia: Si la fuerte dualidad no se sostiene, entonces es posible para $x$ $(\lambda,\nu)$ a primal y dual óptima sin la satisfacción de las condiciones KKT.

---

Por cierto, si Slater condición se mantiene, entonces duales óptimos de las variables de $(\lambda,\nu)$ se garantiza que existe. Así que si $x$ es primal óptima, a continuación, $x$ $(\lambda,\nu)$ juntos satisfacer las condiciones KKT.

Answer 3

Una muy buena explicación de su pregunta se puede encontrar aquí.

Una tabla al final de la explicación se resume cuando las condiciones KKT son necesarias y suficientes.