Augmented Lagrangian Method

July 17, 2015

Consider minimizing:

​$f({\bf x})$ subject to equality constraints ​$g_i({\bf x}) = 0$ for ​$i=1, \ldots ,q$

Inequality constraints are ignored for simplicity

Assume ​$f$ and ​$g_i$ are smooth for simplicity

At a constrained minimum, the Lagrange multiplier condition

​ $${\bf 0}=\nabla f({\bf x})+\sum^q_{i=1}\lambda_i\nabla g_i({\bf x})$$

holds provided ​$\nabla g_i({\bf x})$ are linearly independent

Augmented lagrangian ¹¹ 参考http://www.stat.ncsu.edu/people/zhou/courses/st810/notes/lect24final.pdf

​ $$\mathcal{L}_\rho ({\bf x},{\bf \lambda}) = f({\bf x}) + \sum^q_{i=1}\lambda_i g_i({\bf x}) + \frac{\rho}{2}\sum^q_{i=1}g_i({\bf x})^2$$

The penalty term ​$\frac{\rho}{2}\sum^q_{i=1}g_i({\bf x})^2$ punishes violations of the equality constraints ​$g_i({\bf \theta})$

Optimize the Augmented Lagrangian and adjust ​${\bf \lambda}$ in the hope of matching the true Lagrange multipliers

For ​$\rho$ large enough (finite), the unconstrained minimizer of the augmented lagrangian coincides with the constrained solution of the original problem

At convergence, the gradient ​$\rho g_i({\bf x})\nabla g_i({\bf x})$ vanishes and we recover the standard multiplier rule

Algorithm

Take ​$\rho$ initially large or gradually increase it; iterate

Find the unconstrained minimum ​ $${\bf x}^{(t+1)}\leftarrow \min_x\mathcal{L}_\rho ({\bf x},{\bf \lambda}^{(t)})$$

Update the multiplier vector ​${\bf \lambda}$ ​ $$\lambda^{(t+1)}_i \leftarrow \lambda^{(t)}_i + \rho g_i({\bf x}^{(t)}), \; i = 1, \ldots , q$$

Intuition for updating ​${\bf \lambda}$

If ​${\bf x}^{(t)}$ is the unconstrained minimum of ​$\mathcal{L}({\bf x},{\bf \lambda})$, then the stationary condition says

​ $$\begin{eqnarray*} {\bf 0} & = \nabla f({\bf x}^{(t)}) + \sum^q_{i=1} \lambda^{(t)}_i \nabla g_i({\bf x}^{(t)}) + \rho \sum^q_{i=1} g_i({\bf x}^{(t)}) \nabla g_i({\bf x}^{(t)}) \\ & = \nabla f({\bf x}^{(t)}) + \sum^q_{i=1} \left[ \lambda^{(t)}_i + \rho g_i({\bf x}^{(t)}) \right] \nabla g_i({\bf x}^{(t)}) \end{eqnarray*}$$

For non-smooth ​$f$, replace gradient ​$\nabla f$ by sub-differential ​$\partial f$

Example: basis pursuit

Basis pursuit problem seeks the sparsest solution subject to linear constraints ​ $$\begin{align} \text{minimize } & \|{\bf x}\|_1 \\ \text{subject to } & {\bf Ax} = {\bf b} \end{align}$$

Take ​$\rho$ initially large or gradually increase it; iterate according to

​ $$\begin{eqnarray*} {\bf x}^{(t+1)} & \leftarrow \min \|{\bf x}\| + \langle {\bf \lambda}^{(t)}, {\bf Ax} - {\bf b} \rangle + \frac{\rho}{2} \|{\bf Ax} - {\bf b}\|^2-2 \text{(lasso)} \\ {\bf \lambda}^{(t+1)} & \leftarrow {\bf \lambda}^{(t)} + \rho \left( {\bf Ax}^{(t+1)} - {\bf b} \right) \end{eqnarray*}$$

• Converges in a finite (small) number of steps ²² Yin, W., Osher, S., Goldfarb, D., and Darbon, J. (2008). Bregman iterative algorithms for l₁-minimization with applications to compressed sensing. SIAM J. Imaging Sci., 1(1):143-168. Online: http://www.caam.rice.edu/~wy1/paperfiles/Rice_CAAM_TR07-13.PDF

Remarks

The augmented Lagrangian method dates back to 50s ³³ Hestenes, M.R. (1969). Multiplier and gradient methods. J. Optimization Theory Appl., 4:303-320.
Powell, M. J. D. (1969). A method for nonlinear constraints in minimization problems. In Optimization (Sympos., Univ. Keele, Keele, 1968), pages 283-298. Academic Press, London. Monograph by Bertsekas⁴⁴ Bertsekas, D. P. (1982). Constrained Optimization and Lagrange Multiplier Methods. Computer Science and Applied Mathematics. Academic Press Inc. [Harcourt Brace Jovanovich Publishers], New York. provides a general treatment Same as the Bregman iteration (Yin etal., 2008) proposed for basis pursuit (compressive sensing) Equivalent to proximal print algorithm applied to the dual; can be accelerated (Nesterov)