KKT en pocas palabras gráficamente

Objetivo

Confirme si la comprensión de KKT es correcta o no. Busque más explicaciones y confirmaciones sobre KKT.

Antecedentes

Tratando de entender las condiciones de KKT, especialmente la complementaria, que siempre aparece de la nada en los artículos SVM. No necesito una lista de fórmulas abstractas, pero sí una explicación concreta, intuitiva y gráfica.

Pregunta

Si P, que minimiza la función de costo f (X), está dentro de la restricción (g (P)> = 0), es la solución. Parece que KKT no es relevante en este caso.

Parece que KKT dice que si P no está dentro de la restricción, entonces la solución X debería satisfacer a continuación en la imagen. ¿Se trata de KKT o extraño otros aspectos importantes?

Otras aclaraciones

¿Debería f (x) ser convexo para que se aplique KKT?
¿Debería g (x) ser lineal para que se aplique KKT?
¿Debería ser necesario λ en λ * g (X) = 0? ¿Por qué g (X) = 0 o g (Xi) = 0 no es suficiente?

Referencias

Actualización 1

Gracias por las respuestas, pero aún me cuesta entender. Concéntrese en la necesidad solo aquí:

¿Es la condición (2) en la respuesta de Matthew Gunn sobre el punto no óptimo (en círculo verde) y KKT no estará satisfecho allí? ¿Y el punto se identificaría mirando a Hessian como en la respuesta de Mark L. Stone?

Supongo que otra situación son los puntos de silla, pero ¿se aplica lo mismo?

usuario23658

svm optimization lagrange-multipliers Lun
fuente

Esta pregunta puede atraer más atención en el sitio de matemáticas; Las condiciones de KKT no son necesariamente "estadísticas". Los estadísticos toman prestados estos y otros resultados del análisis numérico para resolver problemas estadísticos interesantes, pero esto es más una cuestión matemática.

user23658

(1) Si las restricciones no se unen, el problema de optimización con las restricciones tiene la misma solución que el problema de optimización sin las restricciones. (2) Ni

necesita ser convexo ni

debe ser lineal para que las condiciones de KKT sean necesarias de manera óptima. (3) Usted necesita condiciones especiales (por ejemplo, un problema convexo donde se cumple la condición Slater) para que las condiciones KKT se mantengan como condiciones suficientes para un óptimo.

f

$f$

g

$g$

Matthew Gunn el

La idea básica de la condición de holgura complementaria (es decir,

donde

es una restricción) es que si la restricción esfloja(es decir,

) en la

óptima, entonces la penalización

por apretar la restricción es 0. Y si hay una penalización positiva

por apretar la restricción, entonces la restricción debe ser vinculante (es decir,

λ g (x) = 0

$\lambda g(\mathbf{x}) = 0$

g (x) \leq 0

$g(\mathbf{x}) \leq 0$

g (x) < 0

$g(\mathbf{x}) < 0$

x

$\mathbf{x}$

λ

$\lambda$

λ

$\lambda$

g (x) = 0

$g(\mathbf{x}) = 0$ ) Si el tráfico fluye suavemente, el peaje del puente

para otro automóvil es cero. Y si el peaje del puente

, entonces el puente debe estar en el límite de capacidad.

λ

$\lambda$

λ > 0

$\lambda > 0$

Matthew Gunn

El teorema básico de KKT dice que si las condiciones de KKT no se cumplen en un punto

, entonces el punto

no es óptimo. Las condiciones KKT son necesarias para un óptimo pero no suficiente. (Por ejemplo, si la función tiene puntos de silla de montar, mínimos locales, etc., las condiciones de KKT pueden cumplirse pero el punto no es óptimo). Para ciertas clases de problemas (por ejemplo, problema convexo donde se cumple la condición de Slater), el KKT las condiciones se convierten en condiciones suficientes .

x

$\mathbf{x}$

x

$\mathbf{x}$

Matthew Gunn el

Respuestas:

La idea básica de las condiciones KKT como condiciones necesarias para un óptimo es que si no se mantienen en un punto factible , entonces existe una dirección que mejorará el objetivo sin aumentar (y por lo tanto posiblemente violar) las restricciones. (Si las condiciones KKT no se mantienen en entonces $\mathbf{x}$ $\boldsymbol{\delta}$ $f$ $\mathbf{x}$ $\mathbf{x}$ no puede ser óptimo, por lo tanto, las condiciones KKT son necesarias para que un punto sea óptimo).

Imagine que tiene el problema de optimización:

\begin{array}{llr} minimize (over x) & f (x) \\ subject to & \forall_{j \in {1 \dots k}} g_{j} (x) \leq 0 \end{array}

$\begin{equation} \begin{array}{*2{>{\displaystyle}r}} \mbox{minimize (over $\mathbf{x}$)} & f(\mathbf{x}) \\ \mbox{subject to} & \forall_{j \in \{1\ldots k\}}\; g_j(\mathbf{x}) \leq 0 \end{array} \end{equation}$

Donde y hay $\mathbf{x} \in \mathbb{R}^n$ $k$ restricciones.

Condiciones KKT y Farkas Lemma

Sea un vector de columna que denota el gradiente de evaluado en $\nabla f(\mathbf{x})$ $f$ $\mathbf{x}$ .

Aplicado a esta situación, Farkas Lemma afirma que para cualquier punto exactamente uno $\mathbf{x} \in \mathbb{R}^n$ cumple de las siguientes afirmaciones:

Existe tal que $\boldsymbol{\lambda} \in \mathbb{R}^k$ y $\sum_{j=1}^k \lambda_j \nabla g_j(\mathbf{x}) = -\nabla f(\mathbf{x})$ $\boldsymbol{\lambda} \geq \mathbf{0}$
Existe tal que $\boldsymbol{\delta} \in \mathbb{R}^n$ y $\forall_j \boldsymbol{\delta}' g_j(\mathbf{x}) \leq 0$ $\boldsymbol{\delta}'\nabla f(\mathbf{x}) < 0$

¿Qué significa esto? Significa que para cualquier punto factible , ya sea: $\mathbf{x}$

Se cumple la condición (1) y se cumplen las condiciones de KKT.
La condición (2) se mantiene y existe una dirección factible $\boldsymbol{\delta}$ que mejora la función objetivo sin aumentar las restricciones . (por ejemplo, puede mejorar moviéndose de a ) $f$ $g_j$ $f$ $\mathbf{x}$ $\mathbf{x} + \epsilon \boldsymbol{\delta}$

La condición (1) establece que existen multiplicadores no negativos modo que las condiciones KKT se satisfacen en el punto . (Geométricamente, dice que encuentra en el cono convexo definido por los gradientes de las restricciones). $\boldsymbol{\lambda}$ $\mathbf{x}$ $- \nabla f$

La condición (2) establece que en el punto , existe una dirección para moverse (localmente) tal que: $\mathbf{x}$ $\boldsymbol{\delta}$

Moverse en la dirección reduce la función objetivo (porque el producto de y es menor que cero). $\boldsymbol{\delta}$ $\nabla f(\mathbf{x})$ $\boldsymbol{\delta}$
Moviéndose en dirección no aumenta el valor de las restricciones (porque el producto de y es menor o igual a cero para todas las restricciones ). $\boldsymbol{\delta}$ $\nabla g_j(\mathbf{x})$ $\boldsymbol{\delta}$ $j$

(Geométricamente, dirección factible $\boldsymbol{\delta}$ $-\nabla f(\mathbf{x})$ $\nabla g_j(\mathbf{x})$

(Nota: para mapear esto en Farkas Lemma , defina la matriz $A = \begin{bmatrix} \nabla g_1, \nabla g_2, \ldots, \nabla g_k \end{bmatrix}$

Este argumento le da la necesidad (pero no la suficiencia) de las condiciones KKT de manera óptima. Si no se cumplen las condiciones de KKT (y se cumplen las calificaciones de restricción), es posible mejorar el objetivo sin violar las restricciones.

El papel de las calificaciones de restricción

¿Qué puede ir mal? Puede obtener situaciones degeneradas en las que los gradientes de las restricciones no describen con precisión las direcciones viables para moverse.

Hay una multitud de calificaciones de restricción diferentes para elegir que permitirán que funcione el argumento anterior.

La interpretación mínima, máxima (en mi opinión, la más intuitiva)

Forma el lagrangiano

L (x, λ) = f (x) + \sum_{j = 1}^{k} λ_{j} g_{j} (x)

$\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum_{j=1}^k \lambda_jg_j(\mathbf{x})$

$f$ $g_j$ $\mathcal{L}$ $\lambda_i$

La solución al problema de optimización original es equivalente a:

min_{x} max_{λ} L (x, λ)

$\min_x \max_\lambda \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda})$

Es decir:

$\mathbf{x}$ $\mathcal{L}$
$\boldsymbol{\lambda}$ $\mathbf{x}$

$g_2$ $\lambda_2$

Dualidad débil

Para cualquier función $f(x, y)$

\forall_{\hat{x}, \hat{y}} min_{x} f (x, \hat{y}) \leq f (\hat{x}, \hat{y}) \leq max_{y} f (\hat{x}, y)

$\forall_{\hat{x},\hat{y}} \quad \min_x f(x, \hat{y}) \leq f(\hat{x}, \hat{y}) \leq \max_y f(\hat{x}, y)$

$\hat{x}$ $\hat{y}$

max_{y} min_{x} f (x, y) \leq min_{x} max_{y} f (x, y)

$\max_y \min_x f(x, y) \leq \min_x \max_y f(x, y)$

$\max_\lambda \min_x \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) \leq \min_x \max_\lambda \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda})$

$\max_\lambda \min_x \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda})$

Fuerte dualidad

Bajo ciertas condiciones especiales (por ejemplo, un problema convexo donde se cumple la condición de Slater), tiene una fuerte dualidad (es decir, la propiedad del punto de silla de montar).

max_{λ} min_{x} L (x, λ) = min_{x} max_{λ} L (x, λ)

$\max_\lambda \min_x \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) = \min_x \max_\lambda \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda})$

Este hermoso resultado implica que puede revertir el orden del problema.

$\boldsymbol{\lambda}$
$\mathbf{x}$ $\mathcal{L}$

los $\lambda$

Matthew Gunn
fuente

Apreciamos la información y los enlaces para llenar los vacíos de comprensión. Permítame confirmarlo. La condición (1) significa que KKT dice que para que un punto X sea una solución, necesita satisfacer λ * g (X) = 0, λ> = 0, y la longitud del gradiente de g (X) es λ veces de el de f (X), de lo contrario encontraremos el gradiente de la dirección de los puntos f (X) donde se puede encontrar f (X ') más pequeño?

lun

La condición de Slater es (solo) una calificación de restricción que se puede aplicar a problemas de optimización convexa, es decir, hace que KKT sea necesario. La convexidad hace que KKT sea suficiente. Por lo tanto, la condición de Slater para el problema de optimización convexa en la que la función objetivo y las restricciones son convexas y continuamente diferenciables hace que KKT sea necesario y suficiente para un mínimo global. La condición de Slater es que hay al menos un punto factible (es decir, satisfacer todas las restricciones) que se encuentra en el estricto interior de todas las restricciones no lineales (todo vale con restricciones lineales, siempre que sea posible).

Mark L. Stone el

f (x) ser convexo es necesario para que KKT sea suficiente para que x sea mínimo local. Si f (x) o -g (x) no son convexas, x KKT satisfactorio podría ser mínimo local, punto de referencia o máximo local.

g (x) siendo lineal, junto con f (x) siendo continuamente diferenciable es suficiente para que las condiciones KKT sean necesarias para un mínimo local. g (x) ser lineal significa que se cumple la calificación de restricción de linealidad para que KKT sea necesario para el mínimo local. Sin embargo, hay otras calificaciones de restricción menos restrictivas que son suficientes para que las condiciones KKT sean necesarias para un mínimo local. Consulte la sección Condiciones de regularidad (o calificaciones de restricción) de https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions .

Si un mínimo local no tiene restricciones "activas" (por lo tanto, en el caso de una restricción de desigualdad, esa restricción no se satisface con la igualdad), los multiplicadores de Lagrange asociados con tales restricciones deben ser cero, en cuyo caso, KKT se reduce a la condición de que el gradiente del objetivo = 0. En tal caso, hay un "costo" cero para el valor objetivo óptimo de un ajuste épsilon de la restricción.

Informacion adicional :

La función objetiva y las restricciones son convexas y continuamente diferenciables implica que KKT es suficiente para un mínimo global.

Si la función objetivo y las restricciones son continuamente diferenciables y las restricciones satisfacen una calificación de restricción, KKT es necesario para un mínimo local.

Si la función objetivo y las restricciones son continuamente diferenciables, convexas y las restricciones satisfacen una calificación de restricción, KKT es necesario y suficiente para un mínimo global.

$Z$ $Z^T H Z$ $H$ $Z$

Mark L. Stone
fuente