从极大化基于增广Lagrange函数的对偶函数的角度，可将增广Lagrange方法的乘子的迭代解释为常步长的梯度方法。增广Lagrange方法的有效性可以通过分析对偶函数的二阶微分得到。给出等式约束优化问题和一般约束非线性规划问题的对偶函数的二阶微分估计，解释为什么常步长的梯度方法具有快的收敛速度。
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.
