Mínimos cuadrados lineales con restricciones de desigualdad.

Question

Estoy tratando de seguir el viejo papel, página 19.

El objetivo es resolver: $\min \|Ax-b\|^2 s.t. Gx \ge h$ da $A, G, b, h$

Mediante la combinación de las ecuaciones en una sola LCP de la forma: $Mz + q = w$ s.t. $z \ge 0, w \ge 0, z \perp w$

Para ello, forman una sola gran ecuación: $f(r,w,x,y,z) = \frac{1}{2} r^Tr - y^T(r+Ax-b) - z^T(Gx-w-h)$

Y tomar las derivadas parciales con respecto a cada una de las variables para la construcción de un gran sistema de ecuaciones y trabajar desde allí. Estoy bien con sus matemáticas una vez que la ecuación anterior se construye, pero estoy confundido, donde algunas de las variables nuevas que vienen.

$r = Ax - b$, lo $r$ es sólo el vector residual que se desea minimizar (lo ideal es $0$), y afirman que en la parte superior de la sección. Presumiblemente $y$ e $z$ son algo similar, pero de dónde vienen, parece menos claro para mí.

Miré en secciones anteriores en el papel, pero no veo nada que lo explica.

Answer 1

Definiendo $r := b - Ax$, simplemente reformular el objetivo del problema como $\|r\|^2$ (de hecho, su función $f$ estados como $\tfrac{1}{2} \|r\|^2$, que es un equivalente objetivo de minimizar; el $\tfrac{1}{2}$ perfectamente cancela el $2$ que aparece cuando diferenciar). Pero ahora debe incluir esta definición de $r$ como una restricción del problema: $Ax + r = b$. A continuación, ellos no quieren lineal restricción de desigualdad, ellos sólo quieren que los límites simple. Así se introduce una variable de holgura $w \geq 0$ tal que $Gx - w = h$. Ahora está a la izquierda con el problema $$ \begin{aligned} \min_{x,r,w} & \tfrac{1}{2} \|r\|^2 \\ \text{s.t.} & Ax + r = b, \\ & Gx - w = h, \\ & w \geq 0. \end{aligned} $$ El Lagrangiano de este problema es $$ L(x,r,w,y,z,u) = \tfrac{1}{2} \|r\|^2 - y^T (Ax + r - b) - z^T (Gx - w - h) - u^T w. $$ Los vectores $y$, $z$ y $u$ son llamados vectores de multiplicadores de Lagrange (o, a veces, de doble variables). El primer orden de optimalidad de condiciones (que son necesarias y suficientes aquí) exigir que las derivadas parciales de $L$ con respecto a $x$, $r$, $y$ y $z$ a desaparecer y que $$ u \geq 0, \quad w \geq 0, \quad u^T w = 0. $$ Ahora la derivada parcial de $L$ w.r.t $w$ es $z -u$. Dado que debe desaparecer, debemos tener $z=u$ y recuperar la formulación de Golub y Saunders.

Si usted no sabe acerca de los multiplicadores de Lagrange, tome el libro de "Optimización Numérica" por Nocedal y Wright (Springer) y buscar el capítulo sobre de primer orden de las condiciones de optimalidad (también llamado condiciones KKT).