Algoritmos para Optimización con Resticciones

Penalización cuadrática, Lagrangiano Aumentado y el Direcciones Alternadas de los Multiplicadores de Lagrange (ADMM)

Mariano Rivera

septiembre 2018

Sea el problema de optimización con restricciones

(1)
$\min_x \;\; f(x) \;\;\;\;\;\\ \;\;\;\;\; s.a.\;\; Ax-b=0$

Entonces el Lagrangiano esta dado por
$\mathcal{L} (x,\lambda) = f(x) - \lambda^\top (Ax-b)$

y las KKTs serán
$(KKTa) \;\;\;\;\;\; \nabla_x \mathcal{L} (x,\lambda) = 0 \Rightarrow \;\;\nabla f(x) - A^\top \lambda=0\\ (KKTb) \;\;\;\;\;\; \nabla_\lambda \mathcal{L} (x,\lambda) = 0 \Rightarrow \;\;\;\;\;\;\;\;\;\; Ax-b=0$

Penalización Cuadrática

Una estrategia para resolver (1), es cambiar un la solución del problema de optimización con restricciones a la solución de una secuencia de problemas sin restricciones.

Los mas simple es cambiar la restricción por pona penalización, la cual se hace muy grande si se viola la factibilidad del punto actual.

Mediante método de penalización cuadrática (1) se transforma en

(2)
$\boxed{ \min_x \; q(x;\rho^{(k)}) = f(x) + \frac{\rho^{(k)}}{2} \| Ax-b \|^2 }$
para $k=1,2,\ldots$, y $\rho^{(k)}$ un parámetro que se incrementa conforme pasan las iteraciones $k$; lo representamos como $\rho \uparrow_k$.

La solución del problema (2) consiste en iterar:

1. Resolver $\nabla_x q (x; \rho^{(k)})=0$ para $x$ con $ \rho^{(k)}$ fija y como condición inicial para $x=x^{(k)}$. Esto es

$x^{(k+1)} = \underset{x}{\arg\min} \;q(x;\rho^{(k)})$

2. Actualizar $\rho$:
   $\rho^{(k+1)} = \eta \, \rho^{(k)} \;\;\;\;\;\;\;\;\;\;$
   con $\eta>1$, digamos $\eta=1.1$.

El propósito de no iniciar con un valor $\rho$ alto (sino irlo incrementandolo gradualmente) es que para una $\rho >>1$, el gradiente de la penalización puede dominar y algoritmo de descenso puede tener convergencia temprana muy lejos del mínimo local.

En el óptimo se cimple que gradiente de la función de penalización esta dado por

(3)
$\nabla_x q(x*;\rho^*) = \nabla f(x^*) + A^\top [\rho^* (Ax^*-b)] =0$

como el óptimo de la función de penalización debe ser el mismo que el óptimo del problema con restricciones, mediante la igualación de términos de (3) con la primera KKT (KKTa) notamos que

(4)
$\lambda^* \approx \rho^* (Ax^*-b)$

Desafortunadamente esta approximación es en general muy mala, la razón es que estamos multiplicando un termino muy grande ($\rho^*$) con uno muy pequeño ($(Ax^*-b)$). Si queremos estimar el multiplicador de Lagrange, es mejor resolver (KKTa) para $\lambda$ con $x^*$ fija y calculada como la solución de la secuencia de penalización cuadrática.

Lagrangiano Aumentado

El método del lagrangiano Aumentado se propuso con la finalidad de solventar la deficiencia de la Penalización Cuadrática para estimar los multiplicadores de Lagrange. La motivación es estimar simultáneamente $x$ y $\lambda$ en el proceso iterativo. Para ello debemos pedir que la (KKTa) también se satisfaga. Esto se logra combinando los términos que involucran a las restricción en el Lagrangiano y en la Penalización Cuadrática. La nueva función que optimizaremos iterativamente es

(5)
$\boxed{ \min_x \; \mathcal{L}_A (x; y^{(k)}, \rho^{(k)}) = f(x) + {y^{(k)}}^\top (Ax-b)+ \frac{\rho^{(k)}}{2} \| Ax-b \|^2 }$

donde hemos definido $y^{(k)} = - \lambda^{k}$ para simplificar el algebra.

Luego, resolvemos para $x$

(6)
$\nabla_x \mathcal{L}_A = \nabla_x f(x) + A^\top y^{(k)} + \rho^{(k)} A^\top (Ax-b) \\ \;\;\;\;\;\;\;\;\;\;\; = \nabla_x f(x) + A^\top [ y^{(k)} + \rho^{(k)}(Ax-b) ] =0$

Comparamos (6) con (KKTa) y notamos que para mantener la factibilidad dual, debemos elegir elegir $y^{(k+1)}$ tal que satisfaga (KKTa). Por ello hacemos $y^{(k+1)} = y^{(k)} + \rho^{(k)}(Ax-b)$.

En resumen, debemos iterar hasta convergencia:

1. Asignar a $x^{(k+1)}$ la solución (aproximada) para $x$ de
   $\nabla_x f(x) + A^\top [ y^{(k)} + \rho^{(k)}(Ax-b) ] =0$

2. Actualizar la estimación del multiplicador de Lagrange con
   $y^{(k+1)} = y^{(k)} + \rho^{(k)}(Ax^{(k+1)}-b)$

3. Actualizar (incrementar) $\rho^{(k)}$ y poner $k=k+1$

Forma Aditiva del Lagrangiano Aumentado

La forma aditiva del Lagrangiano Aumentado se obtiene de podemos añadir términos constantes en $x$ al $\mathcal{L}^{(k)}_A$ sin mofdificar el óptimo $x^{(k+1)}$:

$\mathcal{L}_A (x; u, \rho) = f(x) + \frac{\rho}{2} \left[\| Ax-b \|^2 + 2 \frac{1}{\rho} y^\top(Ax-b) + \frac{1}{\rho^2} y^\top y \right]$

Donde para simplicar la notación hemos quitado la indicación de la iteración para $y$ y $\rho$. Luego podemos reescibir el lagrangiano aumentado como

(7)
$\boxed{ \mathcal{L}_A(x; y, \rho^{(k)}) = f(x) + \frac{\rho^{(k)}}{2} \| Ax-b + u \|^2 }$

y hemos redefinido

(8)
$u \overset{def}{=} \frac{y}{\rho^{(k)}}$

Luego

(9)
$\nabla_x \mathcal{L}_A = \nabla_x f(x) + \rho^{k} A^\top ( A x-b + u)=0$

Para mantener la factibilida dual, elegimos $y=\rho^{(k)} (A x -b +u)$ y sustituyendo $y$ de (8) en (9), tenemos:
$u = u + (A x -b)$

En este caso, el algoritmo consiste en iterar hasta convergencia

1. Asignar a $x^{(k+1)}$ la solución (aproximada) para $x$ de
   $\nabla_x f(x) + \rho^{(k)} A^\top [Ax-b + u^{(k)}] =0$

2. Actualizar la estimación del multiplicador de Lagrange con
   $u^{(k+1)} = u^{(k)} + (Ax^{(k+1)}-b)$

3. Poner $k=k+1$

Método de los Multiplicadores de Lagrange con Direcciones Alternadas (ADMM)

Si bien, la actualización de la forma aditiva del Lagrangiano Aumentado es legeramente mas simple, no se pueded apreciar, por el momento, una ventaja mayor de esta forma.

Sin ambargo, esta forma nos ayudará a escribir un algoritmo mas simple para el método ADMM.

Considere ahora el problema con función objetivo separable de la forma

(10)
$\min_x \;\; f(x) + g(x) \;\;\;\;\;\\ \;\;\;\;\; s.a.\;\; Ax-b=0$

Cuyo el Lagrangiano esta dado por
$\mathcal{L} (x,y) = f(x) + g(x) + y^\top (Ax-b)$

y con KKTs
$(KKTa_2) \;\;\; \nabla_x \mathcal{L} (x,y) = 0 \Rightarrow \;\;\nabla_x f(x) + \nabla_x g(x) + A^\top y=0 \\ (KKTb_2) \;\; \nabla_\lambda \mathcal{L} (x,y) = 0 \Rightarrow \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; Ax-b=0$

(note que estamos usando $y=-\lambda$).

La solución a (10) consiste en encotrar los vectores $x$ y $y$ que satisfagan las $KKTa_2$ y $KKTb_2$.

Ahora, reescribimos el problema (1) en usaremos una nueva variable $z$ que es equivalente.

(11)
$\min_x \;\; f(x) + g(z) \;\;\;\;\;\\ s.a. \;\;\;\;\;\;\;\;\\ \;\;\;\;\;\;\;\;\;\; Ax-b=0 \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\; x-z=0$

Cuyo el Lagrangiano esta dado por
$\mathcal{L} (x, z,y) = f(x) + g(z) + y^\top (Ax-b) + \gamma (x-z)$

y con KKTs
$(KKTa_3) \;\;\; \nabla_x \mathcal{L} (x,z,y) = 0 \Rightarrow \;\;\nabla_x f(x) + A^\top y +\gamma =0 \\ (KKTb_3) \;\;\; \nabla_z \mathcal{L} (x,z,y) = 0 \Rightarrow \;\;\;\;\;\;\;\;\;\;\; \nabla_z g(z) - \gamma =0 \\ (KKTc_3) \;\;\; \nabla_y \mathcal{L} (x,z,y) = 0 \Rightarrow \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; Ax-b=0 \\ (KKTc_4) \;\;\; \nabla_\gamma \mathcal{L} (x,z,y) = 0 \Rightarrow \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; x-z=0$

Aparentemente no hemos hecho nada, puesto que $x=z$. Pero la estrategia para resolver el problemas es alternar minimizaciónes con respecto a $x$ y $z$; pero usando Lagrangiano Aumentado.

Primero escribimos la formulación de Lagrangiano aumentado.

(12)
$\mathcal{L} (x, z, y) = f(x) + g(z) + \frac{\rho^{(k)}}{2} \| Ax-b + u\|^2 + \frac{\eta^{(k)}}{2} \| x-z + v\|^2$

Y calculamos los gradientes parciales:

De $\nabla_x \mathcal{L}_A=0$ tenemos

(13)
$\nabla_x f(x) + \rho^{(k)} A^\top (Ax-b+u) +\eta^{(k)} (x-z+v) = 0$

De $\nabla_z \mathcal{L}_A=0$ tenemos

(14)
$\nabla_z g(z) - \eta^{(k)} (x-z+v) =0$

Y las actualizaciones para $u$ y $v$ quedan:
$u^{(k+1)} = u^{(k)} + (A x - b)$
y
$v^{(k+1)} = v^{(k)} + (x-z)$

Luego, el algorimto consiste en iterar hasta convergencia

1. Asignar a $x^{(k+1)}$ la solución (aproximada) para $x$ de
   $\nabla_x f(x) + \rho^{(k)} A^\top (Ax-b+u^{(k)}) +\eta^{(k)} (x-z^{(k)}+v^{(k)}) = 0$

2. Asignar a $z^{(k+1)}$ la solución (aproximada) para $z$ de
   $\nabla_z g(z) - \eta^{(k)} (x^{(k+1)}-z+v^{(k)}) =0$

3. Actualizar $u$ y $v$:
   $u^{(k+1)} = u^{(k)} + (A x^{(k+1)} - b) \;\;\;\\ v^{(k+1)} = v^{(k)} + (x^{(k+1)}-z^{(k+1)})$

4. Poner $k=k+1$

Ejemplos de formulación con ADMM

Ejemplo 1, resticciones lineales factorizables mediante suma

(15)
$\min_x \;\; f(x) + g(x) \;\;\;\;\;\\ \;\;\;\;\; s.a.\;\; Ax+Bx-b=0$

Se transforma a
(11)
$\min_x \;\; f(x) + g(z) \;\;\;\;\;\\ s.a. \;\; Ax + Bz -b=0 \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; x-z=0$

con lagrangiano Aumentado

$\mathcal{L}_A (x,z; u,v) = f(x) + \frac{\rho}{2} \|Ax+ Bz-b+u\|^2 + \frac{\eta}{2} \| x-z+v) \|^2$

Se resuelve iterando

1. Asignar a $x^{(k+1)}$ la solución (aproximada) para $x$ de
   $\nabla_x \mathcal{L}_A (x,z^{(k)}; \; u^{(k)}, v^{(k)} ) =0$

2. Asignar a $z^{(k+1)}$ la solución (aproximada) para $z$ de
   $\nabla_z \mathcal{L}_A (x^{(k+1)},z \, ; \; u^{(k)}, v^{(k)} ) =0$

3. Actualizar $u$ y $v$:
   $u^{(k+1)} = u^{(k)} + (A x^{(k+1)} + B^{(z+1)} - b) \;\;\;\\ v^{(k+1)} = v^{(k)} + (x^{(k+1)}-z^{(k+1)})$

con $\rho, \eta \uparrow_k$