Multiplicadores de Lagrange y métodos cuasi-Newton

Question

Consideremos un problema de optimización de la forma $$ \begin{aligned} &\min f(x)\\ &\text{s.t. } g(x) = 0 \end{aligned} $$ con $f,g: \mathbb{R}^n \to \mathbb{R}$ convexo y dos veces continuamente diferenciable. Para los problemas de pequeña escala (es decir $n$ pequeño), un método sencillo para resolverlo es considerar el lagrangiano $$L(x, \lambda) = f(x) + \lambda g(x)$$ y resolver $\nabla_{x,\lambda} L(x,\lambda) = 0$ utilizando el método de Newton.

Para problemas de mayor escala esto se vuelve difícil porque en cada paso del método de Newton tenemos que resolver el sistema $$\nabla_{x,\lambda}^2 L(x_k,\lambda_k) (\Delta x,\Delta\lambda) = - \nabla_{x,\lambda} L(x_k,\lambda_k)$$ donde el hessiano $\nabla_{x,\lambda}^2 L(x_k,\lambda_k)$ es de forma $(n+1, n+1)$ . Para un problema no restringido es entonces común utilizar un cuasi-Newton método, como por ejemplo BFGS que construye iterativamente una estimación de la hessiana inversa, y así evita resolver el sistema grande.

Cuando intento utilizar el mismo enfoque para un problema con una restricción como el anterior, me encuentro con el problema de que la mayoría de los métodos de cuasi-Newton sólo son capaces de encontrar los mínimos del objetivo, ya que sus estimaciones del hessiano son definidas positivas. Pero la aproximación con el lagrangiano en realidad requiere que encontremos un punto de silla del lagrangiano. Si no me equivoco, el hessiano en el punto estacionario que buscamos tiene todos los valores propios positivos menos uno, por lo que es indefinido.

Pregunta

¿Qué métodos cuasi-Newton pueden encontrar el punto estacionario de la lagrangiana anterior, aunque el hessiano no sea definido positivo? ¿Por qué parece un enfoque poco popular? (A juzgar por el hecho de que los métodos de cuasi-Newton más populares tienen estimaciones del hessiano positivo definido)

Conozco el Rango simétrico uno no garantiza un hessiano positivo definido, pero esto suele considerarse un inconveniente de este método. ¿Debe este método ser capaz de encontrar el punto estacionario del Lagrangiano anterior? También hay El método de Broyden pero esto no aprovecha el hecho de que el hessiano es simétrico.

Answer 1

Gracias a la discusión en los comentarios y a las fuentes mencionadas he averiguado la respuesta. El hessiano del lagrangiano tiene la siguiente estructura matricial de bloques: $$ \begin{bmatrix} H & J\\ J^T & 0 \end{bmatrix} $$ donde $H = \nabla^2_{x}L(x, \lambda)$ y $J = \nabla_x g(x)$ . Efectivamente, no es positiva definida, pero el bloque $H$ es positiva definida debido a la convexidad de $f$ y $g$ . Para aprovechar esto, se pueden utilizar actualizaciones BFGS sólo en esta parte. Utilizando este enfoque, todo el hessiano del lagrangiano sigue siendo fácilmente invertible, porque si podemos calcular (la acción de) $H^{-1}$ el hessiano completo puede invertirse como $$ \begin{bmatrix} H & J\\ J^T & 0 \end{bmatrix}^{-1} = \begin{bmatrix} H^{-1} - sH^{-1} JJ^TH^{-1} & sH^{-1} J\\ sJ^TH^{-1} & -s \end{bmatrix} $$ donde el escalar $s$ viene dada por $s = \frac{1}{J^T H^{-1}J}$ .

Si tiene más de una restricción de igualdad, esto se vuelve más difícil, ya que el cálculo de $s$ ahora requiere la inversa de $J^T H^{-1} J$ también. Si esto es demasiado difícil, entonces puede aproximar $J$ utilizando el método de Broyden, combinado con BFGS para $H$ .