La idea básica de las condiciones KKT como condiciones necesarias para un óptimo es que si no se cumplen en un punto factible $\mathbf{x}$ entonces existe una dirección $\boldsymbol{\delta}$ que mejore el objetivo $f$ sin aumentar (y, por tanto, sin violar) las restricciones. (Si las condiciones KKT no se cumplen en $\mathbf{x}$ entonces $\mathbf{x}$ no puede ser un óptimo, por lo que las condiciones KKT son necesarias para que un punto sea un óptimo).
Imagina que tienes un problema de optimización:
\begin {Ecuación} \begin {array}{*2{>{} \displaystyle }r}} \mbox {minimizar (sobre $\mathbf{x}$ )} & f( \mathbf {x}) \\ \mbox {sujeto a} & \forall_ {j \in \{1 \ldots k\}}; g_j( \mathbf {x}) \leq 0 \end {array} \end {Ecuación}
Dónde $\mathbf{x} \in \mathbb{R}^n$ y hay $k$ limitaciones.
Dejemos que $\nabla f(\mathbf{x})$ sea un vector columna que denote el gradiente de $f$ evaluado en $\mathbf{x}$ .
Aplicado a esta situación, El lema de Farkas establece que para cualquier punto $\mathbf{x} \in \mathbb{R}^n$ exactamente un de las siguientes afirmaciones es válida:
- Existe $\boldsymbol{\lambda} \in \mathbb{R}^k$ tal que $\sum_{j=1}^k \lambda_j \nabla g_j(\mathbf{x}) = -\nabla f(\mathbf{x})$ y $\boldsymbol{\lambda} \geq \mathbf{0}$
- Existe $\boldsymbol{\delta} \in \mathbb{R}^n$ tal que $\forall_j \boldsymbol{\delta}' g_j(\mathbf{x}) \leq 0$ y $ \boldsymbol{\delta}'\nabla f(\mathbf{x}) < 0$
¿Qué significa esto? Significa que para cualquier punto factible $\mathbf{x}$ Tampoco:
- La condición (1) se mantiene y las condiciones KKT se satisfacen.
- La condición (2) se cumple y existe una dirección factible $\boldsymbol{\delta}$ que mejora la función objetivo $f$ sin aumentar las restricciones $g_j$ . (por ejemplo, puede mejorar $f$ al pasar de $\mathbf{x}$ a $\mathbf{x} + \epsilon \boldsymbol{\delta}$ )
La condición (1) establece que existen multiplicadores no negativos $\boldsymbol{\lambda}$ tal que las condiciones KKT se satisfacen en el punto $\mathbf{x}$ . (Geométricamente, dice que el $- \nabla f$ se encuentra en el cono convexo definido por los gradientes de las restricciones).
La condición (2) establece que en el punto $\mathbf{x}$ existe una dirección $\boldsymbol{\delta}$ para moverse (localmente) tal que:
- Moviéndose en la dirección $\boldsymbol{\delta}$ reduce la función objetivo (porque el producto punto de $\nabla f(\mathbf{x})$ y $\boldsymbol{\delta}$ es menor que cero).
- Moverse en la dirección $\boldsymbol{\delta}$ no aumenta el valor de las restricciones (porque el producto punto de $\nabla g_j(\mathbf{x})$ y $\boldsymbol{\delta}$ es menor o igual a cero para todas las restricciones $j$ ).
(Geométricamente, la dirección factible $\boldsymbol{\delta}$ define un hiperplano de separación entre el vector $-\nabla f(\mathbf{x})$ y el cono convexo definido por los vectores $\nabla g_j(\mathbf{x})$ .)
(Nota: para mapear esto en El lema de Farkas definir 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 en un óptimo. Si las condiciones KKT no se satisfacen (y las calificaciones de las restricciones sí), es posible mejorar el objetivo sin violar las restricciones.
El papel de las calificaciones de las restricciones
¿Qué puede salir mal? Se pueden producir situaciones degeneradas en las que los gradientes de las restricciones no describan con exactitud las direcciones factibles de movimiento.
Hay una multitud de diferentes calificaciones de las restricciones para elegir que permitirá que el argumento anterior funcione.
La interpretación mínima y máxima (en mi opinión, la más intuitiva)
Formar el lagrangiano
$$ \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum_{j=1}^k \lambda_jg_j(\mathbf{x})$$
En lugar de minimizar $f$ con limitaciones $g_j$ Imagina que estás tratando de minimizar $\mathcal{L}$ mientras algún oponente intenta maximizarlo. Puedes interpretar los multiplicadores $\lambda_i$ como penalizaciones (elegidas por algún opositor) por violar las restricciones.
La solución del problema de optimización original es equivalente a:
$$ \min_x \max_\lambda \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) $$
Eso es:
- Primero eliges $\mathbf{x}$ para minimizar el Lagrangiano $\mathcal{L}$ ...consciente de que...
- Entonces elegiré $\boldsymbol{\lambda}$ para maximizar el Lagrangiano (habiendo observado su elección $\mathbf{x}$ ).
Por ejemplo, si se viola la restricción $g_2$ Puedo penalizarte fijando $\lambda_2$ hasta el infinito.
Dualidad débil
Para cualquier función $f(x, y)$ observa que:
$$ \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)$$
Dado que esto es válido para cualquier $\hat{x}$ y $\hat{y}$ también sostiene que: $$ \max_y \min_x f(x, y) \leq \min_x \max_y f(x, y)$$
En el entorno de Langrian, este resultado que $\max_\lambda \min_x \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) \leq \min_x \max_\lambda \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda})$ se conoce como dualidad débil.
El doble problema $\max_\lambda \min_x \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda})$ le da un límite inferior a la solución
Fuerte dualidad
Bajo ciertas condiciones especiales (por ejemplo, un problema convexo en el que se cumple la condición de Slater), se tiene una dualidad fuerte (es decir, la propiedad del punto de silla).
$$\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 se puede invertir el orden del problema.
-
Primero elijo los penaltis $\boldsymbol{\lambda}$ para maximizar el Lagrangiano.
-
A continuación, elige $\mathbf{x}$ para minimizar el Lagrangiano $\mathcal{L}$ .
El $\lambda$ Los precios que se fijan en este proceso son los precios por violar las restricciones, y los precios se fijan de manera que nunca se violen las restricciones.
usuario23658
