La generalización de multiplicadores de Lagrange para el uso de la subdifferential?

Question

Antecedentes: Este es un seguimiento a esta pregunta: Multiplicadores de Lagrange con los no-suave restricciones

Multiplicadores de Lagrange puede ser utilizado para problemas de optimización restringida de la forma

$\min_{\vec x} f(\vec x)$ s.t. $g(\vec x) = 0$.

Brevemente, el método funciona mediante la construcción de la Lagrangiana, $L(\vec x, \lambda) = f(\vec x) + \lambda g(\vec x)$, para luego encontrar los puntos donde la $\forall i, \frac{\partial L}{\partial x_i} L = 0$$\frac{\partial L}{\partial \lambda} L = 0$.

Como fue amablemente señaló en esta respuesta, el método falla al $g$ no es diferenciable (pero constante), ya que las derivadas parciales pueden no existir en los puntos de optimalidad. Por ejemplo, en el problema, minimizar $x_1$$g(x_1,x_2) = x_1 - |x_2| = 0$. El mínimo es de a $(0,0)$ donde $\frac{\partial g}{\partial x_2}$ no existe.

Pregunta: Parece que no debería ser natural de la generalización del método que utiliza subgradients y la subdifferential. Realiza las siguientes labores? Hay una referencia que se describe con más detalle?

Propuesta: construir el Lagrangiano como de costumbre, pero en lugar de buscar un punto donde todas las derivadas parciales son 0, buscar un punto donde 0 es en cada parcial subdifferential. Así, en el ejemplo anterior, el subdifferential con respecto a $x_2$ al $x_2=0$ es el intervalo de $[-\lambda, \lambda]$. Por lo tanto, si se da la solución a $x_1=0,x_2=0,\lambda=-1$, pudimos comprobar que es un punto crítico al señalar que $\frac{\partial L}{\partial \lambda} = x_1 - |x_2| = 0$, $\frac{\partial L}{\partial x_1} = 1 + \lambda = 0$, y un 0 en el subdifferential de $L$ w.r.t. $x_2$.

Es este argumento correcto? Mi justificación intuitiva es que para cualquier valor de $f'(x)$ en algunos de la variable subdifferential en $x$, debemos ser capaces de construir una función suave que ha $f'(x)$ como su derivada parcial en $x$, luego de resolver el alisado problema con un estándar de aplicación de los multiplicadores de Lagrange.

(Aparte: mi objetivo no es en realidad encontrar un método para optimizar la función. Tengo un método para la optimización de tales funciones, y estoy tratando de desarrollar algunos de comprensión teórica de las soluciones que se produce. En particular, estoy tratando de comprender si demostrando que una solución que satisface la condición descrita en la Propuesta de la sección es significativo.)

Answer 1

Creo que la dificultad con la subdifferential enfoque que usted describe se encuentra en la búsqueda de puntos críticos. Por ejemplo, con su ejemplo, la solución de las ecuaciones se obtiene mediante la configuración de parciales a $0$ rendimientos sólo$x_1 = | x_2 |$$\lambda = -1$. Este conjunto de ecuaciones es demasiado incierto para producir una solución. Como usted señala, si se da una solución $x_1 = x_2 = 0$, $\lambda = -1$, usted puede comprobar que es un punto crítico con la subdifferential enfoque, pero eso es muy diferente de la que derivan $x_1 = x_2 = 0$, $\lambda = -1$ como un punto crítico.

Recuerde, sin embargo, que la definición de un punto crítico de una función que incluye los puntos en los que la derivada no existe. Así que cuando usted está construyendo su conjunto de puntos críticos en el uso de multiplicadores de Lagrange, no sólo para los puntos en los que los parciales son cero, pero también para los puntos en el que un parcial no existe. Por ejemplo, está claro que en tu ejemplo, que el único punto en el que $\frac{\partial L}{\partial x_2}$ no existe es $x_2 = 0$. (Usted también consigue $\lambda = 0$$\frac{\partial L}{\partial x_2}= 0$, pero esto es incompatible con la $\lambda = -1$$\frac{\partial L}{\partial x_1}= 0$.) Incluyendo que con las ecuaciones de $\frac{\partial L}{\partial x_1} = 0$ $\frac{\partial L}{\partial \lambda} = 0$ rápidamente obtiene la solución $x_1 = x_2 = 0$, $\lambda = -1$.

De hecho, la búsqueda de los puntos donde un parcial no existe no es en general más difícil (y a veces es más fácil) que la búsqueda de los puntos donde un parcial es cero. No hay muchas maneras para que un punto en el dominio de una función continua de una parte, que no existe. (Además de que el valor absoluto de la situación, usted podría tener una división por cero con parciales de una expresión como $x^p$,$0 < p < 1$, en la función. Tal vez hay algunos otros que me estoy olvidando - tal vez las personas que lean este puede suministrar. También hay algunos casos patológicos, como la continua pero no diferenciable de Weierstrass de la función, pero los que no generalmente se manifiestan en la práctica).

Y, por supuesto, si usted tiene más de un par de variables, usted no desea utilizar multiplicadores de Lagrange de todos modos: la Resolución de un gran número de ecuaciones no lineales es demasiado difícil. En ese caso, es probable que desee un proceso iterativo de optimización no lineal método.

Answer 2

Otro problema aquí es que el subdifferential es el de la clásica útil para funciones convexas sólo. En tu ejemplo, la función de $x_2\mapsto F(x_1,x_2,\lambda)$ es cóncava cuando $\lambda>0$, y luego de su subdifferential está vacío en $x_2=0$. Y a menos que la función de $g$ es lineal, el conjunto de restricciones de no ser convexo, entonces usted no será capaz de construir un convexo de Lagrange-tipo de función.

Usted podría considerar la posibilidad de generalización de la subdifferential a nonconvex funciones, (o, con más precisión de generalización de la noción de estacionariedad), pero ninguno es perfecto. La más conocida es la de Clarke subdifferential [1], que es bastante simple, pero no gozan de plena cálculo.

[1] F. H. Clarke, Optimización y Nonsmooth Análisis, Wiley, Nueva York, 1983.