增廣拉格朗日懲罰函數法

增广拉格朗日惩罚函数法（Augmented Lagrangian methods）是一类用来求解带约束优化问题的算法。与一般的惩罚函数法相比，相同处在于这类方法也会通过将限制条件化为目标函数的惩罚项，使原问题转变为一无约束优化问题；不同处在于，这类方法还会在目标函数中额外添加用来模仿拉格朗日乘子的一项，这一项与拉格朗日乘子不完全一样。

从另一个角度看，无约束目标函数是带约束问题的拉格朗日對偶再加上一个额外的惩罚项（或者称为“增广量”）。

这种方法曾被人们称为乘子法。在20世纪70到80年代曾被作为惩罚函数法的替代方法被大量研究过。这类方法首次由Magnus Hestenes^[1]、麦克尔·詹姆斯·大卫·鲍威尔^[2]在1969年提出。R. Tyrrell Rockafellar深入研究了其与Fenchel 对偶，尤其是与邻近点方法、Moreau–Yosida 正则化和单调算子之间的联系——这些方法被应用在结构工程领域。德梅萃·P. 博赛卡斯也对该方法做过研究，尤其是在他1982年的书^[3]中对涉及到非二次正则化函数的扩展，如熵正则方法，为后续的用来处理二阶可微增广拉格朗日惩罚函数的指数乘子方法奠定了基础。

自20世纪70年代起，逐步二次规划（SQP）与内点法逐渐兴盛。这种兴盛，很难说与这两种方法能巧妙利用当时数值计算软件库中的稀疏矩阵库函数不无关系，而内点法还有通过同伦函数理论被证明的复杂度分析。LANCELOT和AMPL的出现，使得增广拉格朗日惩罚函数法能被用于求解看似稠密但却部分可分的优化问题，为该方法注入了新的活力。^[4] 2007年前后，全变分降噪、压缩感知等领域中，该方法也再次被活跃运用。其中，一类运用了分部更新技巧（与求解线性方程组的Gauss-Seidel法类似）的算法变种——交替方向乘子法（ADMM）获得了较大的关注。

方法概述

考虑如下带约束优化问题

${\displaystyle \min f(\mathbf {x} )}$ 

s.t.

${\displaystyle c_{i}(\mathbf {x} )=0~\forall i\in I.}$ 

交替方向乘子法

交替方向乘子法（The alternating direction method of multipliers，ADMM）是增广拉格朗日惩罚函数法的一类变种，它交替更新对偶变量值。一般处理的问题形式如下

${\displaystyle \min _{x}f(x)+g(x).}$ 

上述表示等价于如下表示

${\displaystyle \min _{x,y}f(x)+g(y),\quad {\text{subject to}}\quad x=y.}$ 

软件

• Accord.NET
• ALGLIB
• PENNON

还有一些商业软件

• LANCELOT
• MINOS

参见

• 惩罚函数法
• 内点法
• 拉格朗日乘子

参考资料

1. M.R. Hestenes, "Multiplier and gradient methods", Journal of Optimization Theory and Applications, 4, 1969, pp. 303–320
2. M.J.D. Powell, "A method for nonlinear constraints in minimization problems", in Optimization ed. by R. Fletcher, Academic Press, New York, NY, 1969, pp. 283–298.
3. Dimitri P. Bertsekas, Constrained optimization and Lagrange multiplier methods, Athena Scientific, 1996 (first published 1982)
4. Nocedal & Wright (2006), chapter 17

相关文献

• Bertsekas, Dimitri P., Nonlinear Programming 2nd, Belmont, Mass: Athena Scientific, 1999, ISBN 1-886529-00-0 
• Nocedal, Jorge; Wright, Stephen J., Numerical Optimization 2nd, Berlin, New York: Springer-Verlag, 2006, ISBN 978-0-387-30303-1