Augmented Lagrangian Method

July 17, 2015

Consider minimizing:

subject to equality constraints ​ for ​

Inequality constraints are ignored for simplicity

Assume ​ and ​ are smooth for simplicity

At a constrained minimum, the Lagrange multiplier condition

holds provided ​ are linearly independent

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

The penalty term ​ punishes violations of the equality constraints ​

Optimize the Augmented Lagrangian and adjust ​ in the hope of matching the true Lagrange multipliers

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

At convergence, the gradient ​ vanishes and we recover the standard multiplier rule

Algorithm

Take ​ initially large or gradually increase it; iterate

Find the unconstrained minimum ​

Update the multiplier vector ​

Intuition for updating ​

If ​ is the unconstrained minimum of ​, then the stationary condition says

For non-smooth ​, replace gradient ​ by sub-differential ​

Example: basis pursuit

Basis pursuit problem seeks the sparsest solution subject to linear constraints ​

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

Remarks

The augmented Lagrangian method dates back to 50s 33 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 Bertsekas44 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)

Augmented Lagrangian Method - July 17, 2015 - QU Xiaofeng