Aquí un poco de intuición.
Primero supongamos que $x_0$ es un local minimizer para el problema
\begin{align}
\tag{%#%#%} \text{minimize} & \quad f(x) \\
\text{subject to} &\quad Ax = b.
\end{align}
Si $\spadesuit$, entonces la derivada direccional $Au = 0$ es no negativa. De lo contrario, sería posible mejorar la $D_u f(x_0) = \langle \nabla f(x_0),u \rangle$ perturbando un poco en la dirección $x_0$.
De ello se sigue que si $u$,$Au = 0$.
Por eso, $\langle \nabla f(x_0),u \rangle = 0$ es en el complemento ortogonal del espacio nulo de a $\nabla f(x_0)$.
PERO, de acuerdo a los "cuatro subespacio teorema" (que es amado por Gibert Strang), el complemento ortogonal del espacio nulo de a $A$ es el rango de $A$. Por lo tanto, $A^T$ está en el rango de $\nabla f(x_0)$. En otras palabras, existe un vector $A^T$ tal que
\begin{equation}
\nabla f(x_0) = A^T \lambda.
\end{equation}
Este es nuestro multiplicador de Lagrange condición de optimalidad, en el caso de que hayamos lineal restricciones de igualdad.
Siguiente, supongamos que $\lambda$ es un local minimizer para el problema
\begin{align}
\text{minimize} & \quad f(x) \\
\text{subject to} &\quad g(x) = 0,
\end{align}
donde $x_0$.
Parece plausible que la $g:\mathbb R^n \to \mathbb R^m$ es también un local minimizer para el problema obtenemos sustituyendo $x_0$ con el local de la aproximación lineal a$g$$g$:
\begin{align}
\text{minimize} & \quad f(x) \\
\text{subject to} &\quad g(x_0) + g'(x_0)(x - x_0) = 0.
\end{align}
(Aquí se $x_0$ es la matriz Jacobiana de $g'(x_0)$$g$.)
Suponiendo que $x_0$ es de hecho un local minimizer para esta modificado el problema,
de ello se desprende que $x_0$ satisface la condición de optimalidad derivada de la anterior:
\begin{align}
\nabla f(x_0) &= g'(x_0)^T \lambda \\
&= \nabla g_1(x_0) \lambda_1 + \cdots + \nabla g_m(x_0) \lambda_m
\end{align}
para algunos vectores $x_0$.
(Aquí se $\lambda = \begin{bmatrix} \lambda_1 & \ldots & \lambda_m \end{bmatrix}^T \in \mathbb R^m$ son las funciones de los componentes de $g_1,\ldots,g_m$, y utilizamos la convención que el gradiente es un vector columna.)
Este es nuestro multiplicador de Lagrange condición de optimalidad en el caso de las restricciones de igualdad no lineales.
Yo creo que es posible ver la prueba utilizando el teorema de la función implícita como una rigurosa versión de esta intuición.
Edit: Ahora te voy a mostrar cómo un enfoque similar puede manejar restricciones de desigualdad, si vamos a reemplazar el "cuatro subespacio teorema" con Farkas lema (que yo llamo los cuatro cono teorema).
Deje $g$ ser un local minimizer para el problema
\begin{align}
\tag{%#%#%} \text{minimize} & \quad f(x) \\
\text{subject to} & \quad Ax \leq b.
\end{align}
Supongamos que $x^*$$\heartsuit$.
Entonces la derivada direccional
$u \in \mathbb R^n$.
De lo contrario, se podría mejorar la $Au \leq 0$ perturbando se
un poco en la dirección de $D_uf(x^*) = \langle \nabla f(x^*),u \rangle \geq 0$.
En este punto, nos gustaría invocar algo así como las cuatro subespacio teorema,
para encontrar algunos condición de optimalidad que $x^*$ debe satisfacer.
Mientras que los cuatro subespacio teorema no es aplicable aquí, hay una cara de la versión
de los cuatro subespacio teorema que se ajusta a esta situación a la perfección.
El teorema de los cuatro cono
Primero hemos de recordar algunos hechos de análisis convexo.
Si $u$ es un cono, entonces la polar
de $\nabla f(x^*)$ está definido por
\begin{equation} C^\circ = \{z \mid \langle x,z \rangle \leq 0 \,\, \forall \,\, x \in C \}.
\end{equation}
Tenga en cuenta que $C \subset \mathbb R^n$ es un cerrado convexo de cono.
Un cono convexo es un "unilateral" de la versión de un subespacio, y el polar de cono
es un "unilateral" de la versión del complemento ortogonal.
En lugar de $C$,$C^\circ$.
Aquí un poco de apoyo para esta analogía:
- Para un subespacio $\langle x,z \rangle = 0$$\langle x, z \rangle \leq 0$, tenemos la conocida ecuación
$W$.
La cara de la versión de esto es que si $\mathbb R^n$ es un cerrado convexo de cono, a continuación,$W = W^{\perp \perp}$.
- Si $C$ es un subespacio de $C = C^{\circ \circ}$, ninguna de las $W$ puede ser descompuesto como
$\mathbb R^n$. La cara de la versión de esto es que
si $x \in \mathbb R^n$ es un cerrado convexo de cono, ninguna de las $x = \Pi_W(x) + \Pi_{W^\perp}(x)$ puede ser descompuesto
como $C \subset \mathbb R^n$. Por otra parte, $x \in \mathbb R^n$ es ortogonal a $x = \Pi_C(x) + \Pi_{C^\circ}(x)$.
Deje $\Pi_C(x)$.
Por lo $\Pi_{C^\circ}(x)$ es un `one-sided versión" de la gama de $\mathcal R_+(A^T) = \{ A^T z \mid z \geq 0 \}$.
Deje $\mathcal R_+(A^T)$.
Por lo $A^T$ es de un solo lado de la versión de el espacio nulo de a $ \mathcal N_-(A) = \{x \mid Ax \leq 0 \}$.
Tenga en cuenta que $\mathcal N_-(A)$ $A$ son tanto cerrado convexo conos.
Los cuatro subespacio teorema puede enunciarse de la
\begin{equation}
\mathcal N(A)^\perp = \mathcal R(A^T).
\end{equation}
Aquí está nuestro "unilateral" de la versión de los cuatro subespacio teorema:
\begin{equation}
\mathcal N_-(A)^\circ = \mathcal R_+(A^T).
\end{equation}
Yo llamo a esto el "cuatro de cono teorema".
Invocando el teorema de los cuatro cono
Podemos utilizar el "cuatro de cono teorema" para encontrar una condición de optimalidad
para el problema ($\mathcal N_-(A)$), tal y como hemos utilizado los cuatro subespacio teorema de
para encontrar una condición de optimalidad para el problema ($\mathcal R_+(A^T)$).
Como se señaló anteriormente, si $\heartsuit$,$\spadesuit$.
En otras palabras, $A u \leq 0$.
Por los cuatro cono teorema, se sigue que
$\langle \nabla f(x^*), u \rangle \geq 0$.
Por lo tanto, existe un vector $-\nabla f(x^*) \in \mathcal N_-(A)^\circ$ tal que
\begin{equation}
\nabla f(x^*) + A^T z = 0.
\end{equation}
Esto, junto con el $-\nabla f(x^*) \in \mathcal R_+(A^T)$, es nuestra condición de optimalidad
(KKT condición) para el problema ($z \geq 0$) lineal con restricciones de desigualdad.
Conexión con Farkas del lema
Los cuatro cono teorema puede enunciarse como `teorema de la alternativa".
Si $Ax^* \leq b$, $\heartsuit$ realiza o no pertenecen a $g \in \mathbb R^n$.
En otras palabras, o $g$ pertenece a $\mathcal R_+(A^T)$ o más $g$ no pertenece
a la polar de $\mathcal R_+(A^T)$. Esto significa que una y sólo una de las dos siguientes alternativas es verdadera:
- Existe $g$ tal que $\mathcal N_-(A)$.
- Existe $z \geq 0$ tal que $g = A^T z$$u$.
Esto es equivalente a la declaración de Farkas del lexema dado en Boyd y Vandenberghe.
Los cuatro cono teorema es Farkas del lexema.
La visualización de los cuatro teorema de cono
La "alternativa" declaración de los cuatro cono teorema sugiere una forma de visualizar
los cuatro cono teorema que hace parecer obvio.
La primera alternativa es que el $Au \leq 0$ pertenece al cono convexo generado por el
columnas de $\langle g, u \rangle > 0$. La segunda alternativa es que hay un hyperplane por el origen
que separa a $g$ a partir de las columnas de a $A^T$. (El vector $g$ es normal
vector de esta separación hyperplane.)
Problema lineal con la igualdad y la desigualdad restricciones
Este caso es similar a los casos anteriores, excepto que vamos a utilizar
una versión diferente de Farkas del lema que implica una combinación de
la igualdad y la desigualdad restricciones.
