乗数法 (数理計画の)
拡張ラグランジュ関数法
 | この記事は英語版の対応するページを翻訳することにより充実させることができます。（2025年3月） 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
|
拡張ラグランジュ関数法（かくちょうラグランジュかんすうほう、英: Augmented Lagrangian methods）とは、制約付き最適化問題に対するアルゴリズムの一種である。拡張ラグランジュ関数法は制約付き最適化問題を無制約最適化問題として扱うペナルティ関数法に類似した解法で、制約を目的関数にペナルティ項として加える解法であるが、ラグランジュ乗数と組み合わせた解法である。拡張ラグランジュ関数法はラグランジュの未定乗数法と関連した解法であるが、異なった概念である。
言い換えると、拡張ラグランジュ関数法は制約付き最適化問題に対するラグランジュ関数にペナルティ項を加えたものとみなすことができる。
拡張ラグランジュ関数法は元々1970年代から1980年代にかけてペナルティ関数法の代替的手法として乗数法という名で知られていた。拡張ラグランジュ関数法は1969年にマグナス・ヘステネスとマイケル・パウエルによって始めて議論された[1][2]。その後、ロッカフェラー, R・ティレルによってフェンツェル双対に関連して研究され、特に構造最適化で用いられる近接点法、Moreau-Yoshida正則化、単調作用素最大化と併せて研究された。またディミトリ・ベルツェカスが1982年に出版した著書に非二次正則化関数の項目（エントロピー正則化）で掲載された[3]。これらの研究から乗数法を指数型乗数法（exponential method of multipliers）に拡張することができ、二階微分可能な拡張ラグランジュ関数として扱えるようになった。
1970年代以降、拡張ラグランジュ関数法が一部の数値解析ライブラリにおいて疎行列サブルーチンを容易に使用することが可能になり、自己整合障壁関数理論による内点法の優れた大域的収束性の保証から、逐次二次計画法（SQP）および内点法（IPM）が研究されるようになった。拡張ラグランジュ関数法はLANCELOTやALGENCAN[4][5]、AMPLなどの最適化システムに実装され、密行列をもつ問題を分割可能な問題によって行列を疎行列として扱えるようになり、注目されるようになった。このことから、拡張ラグランジュ関数法は現在でも使用されている [6]。
2007年ごろから、拡張ラグランジュ関数法は全変動ノイズ除去や圧縮センシングの分野において使用されるようになった。特に、拡張ラグランジュ関数法の類似の解法によって連立方程式を解く解法のガウス＝ザイデル法のように行列の部分更新する際に使用されるようになり、これは交互方向乗数法（略称：ADMM）として知られている。
一般的な解法
以下の制約付き最適化問題を考える:
Optimization computes maxima and minima.
| 一般 | |
|---|---|
| 微分可能 |
| 凸最小化 | |||||||
|---|---|---|---|---|---|---|---|
| 線形 および 二次 |
|
| 系列範例 (Paradigms) | |||||
|---|---|---|---|---|---|
| グラフ理論 |
| ||||
| ネットワークフロー (最大流問題) |
