Minimización con multiplicadores de Lagrange y Newton-Raphson

Question

Estoy escribiendo un programa que minimiza una función no lineal de valor real de unas 90 variables reales sujeta a unas 30 restricciones no lineales. He encontrado una explicación práctica en el sitio web del CERN Libro breve de análisis de datos . Lo he puesto en práctica y funciona, pero no soy capaz de deducir cómo han obtenido las ecuaciones del fondo. Podría alguien explicar cómo se puede lograr?

Copiado del enlace:

Tratando de minimizar $f(x_1,...,x_n)$ con sujeción a $c_1(x_1,...,x_n) = ... = c_m(x_1,...,x_n) = 0$ .

Reformular como $$\partial F/\partial x_1 = \dots = \partial F/\partial x_n = \partial F/\partial\lambda_1 = \dots = \partial F/\partial\lambda_m = 0$$ para $$F(x_1,\dots,x_n,\lambda_1,\dots,\lambda_m) = f(x_1,\dots,x_n) - \lambda^T c(x_1,\dots,x_n)$$

Uso de multiplicadores de Lagrange $\lambda$ y Newton-Raphson, llegan a (1): $$A\Delta x - B^T\lambda = -a\\ B\Delta x = -c,$$ donde $A$ es el hessiano de $f$ , $a = (\nabla f)^T$ es el gradiente de $f$ y $B=\nabla c$ es el jacobiano de las restricciones.

Parece que no puedo seguirlos. Según entiendo, están aplicando Newton-Raphson para resolver $\nabla F = 0$ . Creo que $$\nabla F = \left(a - B^T \lambda \atop -c \right)$$ Entonces, tenemos que tomar la derivada de $\nabla F$ para Newton-Raphson. En primer lugar, me parece que sólo están tomando la derivada con respecto a. $x$ y no a $\lambda$ . ¿Por qué?

Aun así, esto llevaría a (1) si la derivada de $\nabla F$ fue $\left(A \atop -B\right)$ . Sin embargo, aunque es cierto que $\nabla a = A$ y $\nabla c = B$ No puedo entender dónde está el término $-B^T\lambda$ se desvaneció.

Muchas gracias a quien pueda arrojar algo de luz sobre esto.

Answer 1

También me interesaba una prueba del resultado del multiplicador de Newton-Raphson+Lagrange de la página del CERN. Aquí está mi derivación:

Answer 2

Consulta la Programación Cuadrática Secuencial en cualquier buen libro de optimización. Cuando sólo hay restricciones de igualdad, realmente se reduce a aplicar el método de Newton al sistema que has dado. Con $F(x,\lambda) := f(x) - \lambda^T c(x)$ (el Lagrangiano), diferenciando se obtiene $$\nabla F(x,\lambda) = \begin{bmatrix} \nabla f(x) - J(x)^T \lambda \\ - c(x) \end{bmatrix},$$ donde $$J(x) = \begin{bmatrix} \nabla c_1(x)^T \\ \vdots \\ \nabla c_m(x)^T \end{bmatrix}$$ es el jacobiano de $c$ en $x$ . Aplicando el método de Newton a $\nabla F(x,\lambda) = 0$ requiere que diferenciemos una vez más: $$\begin{bmatrix} H(x,\lambda) & J(x)^T \\ J(x) & 0 \end{bmatrix} \begin{bmatrix} \Delta x \\ -\Delta \lambda \end{bmatrix} = - \begin{bmatrix} \nabla f(x) - J(x)^T \lambda \\ - c(x) \end{bmatrix}.$$ Hay todo tipo de dificultades que se presentan, desde la necesidad de realizar una búsqueda de líneas para una función de mérito, hasta evitar el efecto Maratos. Un buen libro como Numerical Optimization (Nocedal & Wright, Springer) lo explicará todo.