From the point of view of maximizing the dual function based on augmented Lagrange function, the update of multiplier of augmented Lagrange method can be interpreted as a constant step gradient method. The effectiveness of augmented Lagrange method can be obtained by analyzing the second-order differential of dual function. In this paper, the second-order differentials of dual function for equality constrained optimization problem and general constrained nonlinear programming problem are estimated, which explains why the gradient method with constant step size has fast rate of convergence.
[1] Hestenes M R. Multiplier and gradient methods[J]. Journal of Optimization Theory and Applications, 1969, 4:303-320.
[2] Powell M J D. A method for nonlinear constraints in minimization problems[M]//Optimization. New York:Academic Press, 1969:283-298.
[3] Rockafellar R T. A dual approach to solving nonlinear programming problems by unconstrained optimization[J]. Mathematical Programming, 1973, 5:354-373.
[4] Rockafellar R T. The multiplier method of Hestenes and Powell applied to convex programming[J]. Journal of Optimization Theory and Applications, 1973, 12:555-562.
[5] Bertsekas D P. Constrained Optimization and Lagrange Multiplier Methods[M]. New York:Academic Press, 1982.
[6] Conn A R, Gould N I M, Toint Ph L. A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds[J]. SIAM Journal on Numerical Analysis, 1991, 28:545-572.
[7] Contesse-Becker L. Extended convergence results for the method of multipliers for non-strictly binding inequality constraints[J]. Journal of Optimization Theory and Applications, 1993, 79:273-310.
[8] Ito K, Kunisch K. The augmented Lagrangian method for equality and inequality constraints in Hilbert spaces[J]. Mathematical Programming, 1990, 46:341-360.
[9] Rockafellar R T, Wets R J-B. Variational Analysis[M]. New York:Springer-Verlag, 1998.
[10] Facchinei F, Pang J S. Finite-Dimensional Variational Inequalities and Complementarity Problems, Volumes I and II[M]. New York:Springer-Verlag, 2003.
[11] Sun D F, Sun J, Zhang L W. The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming[J]. Mathematical Programming, 2008, 114:349-391.
