增廣拉格朗日懲罰函數法

增廣拉格朗日懲罰函數法（Augmented Lagrangian methods）是一類用來求解帶約束優化問題的算法。與一般的懲罰函數法相比，相同處在於這類方法也會通過將限制條件化為目標函數的懲罰項，使原問題轉變為一無約束優化問題；不同處在於，這類方法還會在目標函數中額外添加用來模仿拉格朗日乘子的一項，這一項與拉格朗日乘子不完全一樣。

從另一個角度看，無約束目標函數是帶約束問題的拉格朗日對偶再加上一個額外的懲罰項（或者稱為「增廣量」）。

這種方法曾被人們稱為乘子法。在20世紀70到80年代曾被作為懲罰函數法的替代方法被大量研究過。這類方法首次由Magnus Hestenes、米高·詹姆斯·大衛·鮑威爾在1969年提出。R. Tyrrell Rockafellar深入研究了其與Fenchel 對偶，尤其是與鄰近點方法、Moreau–Yosida 正則化和單調算子之間的聯繫——這些方法被應用在結構工程領域。德梅萃·P. 博賽卡斯也對該方法做過研究，尤其是在他1982年的書中對涉及到非二次正則化函數的擴展，如熵正則方法，為後續的用來處理二階可微增廣拉格朗日懲罰函數的指數乘子方法奠定了基礎。

自20世紀70年代起，逐步二次規劃（SQP）與內點法逐漸興盛。這種興盛，很難說與這兩種方法能巧妙利用當時數值計算軟件庫中的稀疏矩陣庫函數不無關係，而內點法還有通過同倫函數理論被證明的複雜度分析。LANCELOT和AMPL的出現，使得增廣拉格朗日懲罰函數法能被用於求解看似稠密但卻部分可分的優化問題，為該方法注入了新的活力。 2007年前後，全變分降噪、壓縮感知等領域中，該方法也再次被活躍運用。其中，一類運用了分部更新技巧（與求解線性方程組的Gauss-Seidel法類似）的算法變種——交替方向乘子法（ADMM）獲得了較大的關注。

方法概述

考慮如下帶約束優化問題

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

s.t.

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

交替方向乘子法

交替方向乘子法（The alternating direction method of multipliers，ADMM）是增廣拉格朗日懲罰函數法的一類變種，它交替更新對偶變量值。一般處理的問題形式如下

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

上述表示等價於如下表示

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

軟件

• Accord.NET
• ALGLIB
• PENNON

還有一些商業軟件

• LANCELOT
• MINOS

參見

• 懲罰函數法
• 內點法
• 拉格朗日乘子

相關文獻

• 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