查看“︁增廣拉格朗日懲罰函數法”︁的源代码

{{Translating|time=2018-03-20}}

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

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

这种方法曾被人们称为乘子法。在20世纪70到80年代曾被作为惩罚函数法的替代方法被大量研究过。这类方法首次由[[Magnus Hestenes]]<ref>[[Magnus Hestenes|M.R. Hestenes]], "Multiplier and gradient methods", ''Journal of Optimization Theory and Applications'', 4, 1969, pp. 303–320</ref>、[[麦克尔·詹姆斯·大卫·鲍威尔]]<ref>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.</ref>在1969年提出。[[R. Tyrrell Rockafellar]]<!-- French applied mathematicians, at least one in Texas, whose names escape senile K.W. -->深入研究了其与[[Fenchel 对偶]]，尤其是与邻近点方法、Moreau–Yosida 正则化和单调算子之间的联系——这些方法被应用在结构工程领域。[[德梅萃·P. 博赛卡斯]]也对该方法做过研究，尤其是在他1982年的书<ref>Dimitri P. Bertsekas, ''Constrained optimization and Lagrange multiplier methods'', Athena Scientific, 1996 (first published 1982)</ref>中对涉及到非二次正则化函数的扩展，如[[Bregman 散度|熵正则方法]]，为后续的用来处理二阶可微增广拉格朗日惩罚函数的指数乘子方法奠定了基础。

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

== 方法概述 ==

考虑如下带约束优化问题
:<math> \min f(\mathbf{x}) </math>
s.t. 
:<math> c_i(\mathbf{x}) = 0 ~\forall  i \in I. </math>

== 交替方向乘子法 ==

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

<math> \min_x f(x) + g(x). </math>

上述表示等价于如下表示

<math> \min_{x,y} f(x) + g(y), \quad \text{subject to}\quad  x = y. </math>

== 软件 ==
* [[Accord.NET]]
* [[ALGLIB]]
* [[PENOPT|PENNON]]
还有一些商业软件
* [[Galahad library|LANCELOT]]
* [[MINOS (optimization software)|MINOS]]

== 参见 ==
* [[惩罚函数法]]
* [[内点法]]
* [[拉格朗日乘子]]

== 参考资料 ==
<references/>

== 相关文献 ==
* {{Citation | last1=Bertsekas | first1=Dimitri P. | title=Nonlinear Programming | publisher=[[Athena Scientific]] | location=Belmont, Mass | edition=2nd | isbn=1-886529-00-0 | year=1999}}
* {{Citation | last1=Nocedal | first1=Jorge | last2=Wright | first2=Stephen J. | title=Numerical Optimization | publisher=[[Springer-Verlag]] | location=Berlin, New York | edition=2nd | isbn=978-0-387-30303-1 | year=2006}}