拡張ラグランジュ関数法

この記事は英語版の対応するページを翻訳することにより充実させることができます。（2025年3月） 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。 英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Augmented Lagrangian method|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があります。

拡張ラグランジュ関数法（かくちょうラグランジュかんすうほう、英: Augmented Lagrangian methods）とは、数理最適化において制約付き最適化問題に対するアルゴリズムの一種である。拡張ラグランジュ関数法は制約付き最適化問題を無制約最適化問題として扱うペナルティ関数法に類似した解法で、制約を目的関数にペナルティ項として加える解法であるが、ラグランジュ乗数と組み合わせた解法である。拡張ラグランジュ関数法はラグランジュの未定乗数法と関連した解法であるが、異なったアルゴリズムである。

言い換えると、拡張ラグランジュ関数法は制約付き最適化問題に対するラグランジュ関数にペナルティ項を加えたものとみなすことができる。

拡張ラグランジュ関数法は元々1970年代から1980年代にかけてペナルティ関数法の代替的手法として乗数法という名で知られていた。拡張ラグランジュ関数法は1969年にマグナス・ヘステネス（英語版）とマイケル・パウエル（英語版）によって始めて議論された^[1][2]。その後、ティレル・ロッカフェラー（英語版）によってフェンシェル双対に関連して研究され、特に構造最適化で用いられる近接点法、Moreau-Yoshida正則化、単調作用素（英語版）最大化と併せて研究された。またディミトリ・ベルツェカス（英語版）が1982年に出版した著書において非二次正則化関数の項目（エントロピー正則化（英語版））で拡張ラグランジュ関数法について記載された^[3]。これらの研究から乗数法を指数型乗数法^{[注釈 1]}に拡張することができ、二階微分可能な拡張ラグランジュ関数として扱えるようになった。

1970年代以降、拡張ラグランジュ関数法が一部の数値解析ライブラリにおいて疎行列サブルーチンを容易に使用することが可能になり、自己整合障壁関数（英語版）理論による内点法の優れた大域的収束性の保証から、逐次二次計画法（SQP）および内点法（IPM）が研究されるようになった。拡張ラグランジュ関数法はLANCELOTやALGENCAN^[4][5]、AMPLなどの最適化システムに実装され、密行列をもつ問題を分割可能な問題によって行列を疎行列として扱えるようになり、注目されるようになった。このことから、拡張ラグランジュ関数法は現在でも使用されている ^[6]。

2007年ごろから、拡張ラグランジュ関数法は全変動ノイズ除去（英語版）や圧縮センシングの分野において使用されるようになった。特に、拡張ラグランジュ関数法の類似の解法によって連立方程式を解く解法のガウス＝ザイデル法のように行列の部分更新する際に使用されるようになり、これは交互方向乗数法（略称：ADMM）として知られている。

以下の制約付き最適化問題を考える:

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

subject to

${\displaystyle c_{i}(\mathbf {x} )=0~\forall i\in {\mathcal {E}},}$

ただし、${\displaystyle {\mathcal {E}}}$ は等式制約とする。この問題は無制約最小化問題の一種として解くことができる。参考までに、 k回目の反復におけるペナルティ関数法の例を紹介する:

${\displaystyle \min \Phi _{k}(\mathbf {x} )=f(\mathbf {x} )+\mu _{k}~\sum _{i\in {\mathcal {E}}}~c_{i}(\mathbf {x} )^{2}.}$

ペナルティ関数法では上記の問題を解いた後、次の反復ではより大きな ${\displaystyle \mu _{k}}$ の下で問題を解き直す。このとき、前の反復で求まった解 ${\displaystyle \mu _{k}}$ を使用することで問題の求解にてホットスタートすることができる。

拡張ラグランジュ関数法では以下の無制約の目的関数を用いる:

${\displaystyle \min \Phi _{k}(\mathbf {x} )=f(\mathbf {x} )+{\frac {\mu _{k}}{2}}~\sum _{i\in {\mathcal {E}}}~c_{i}(\mathbf {x} )^{2}+\sum _{i\in {\mathcal {E}}}~\lambda _{i}c_{i}(\mathbf {x} )}$

各反復において、${\displaystyle \mu _{k}}$ を更新し、${\displaystyle \lambda }$ も以下の式によって更新される:

${\displaystyle \lambda _{i}\leftarrow \lambda _{i}+\mu _{k}c_{i}(\mathbf {x} _{k})}$

ただし、${\displaystyle \mathbf {x} _{k}}$ はk番目の反復における問題を解いた解（例: ${\displaystyle \mathbf {x} _{k}={\text{argmin}}\Phi _{k}(\mathbf {x} )}$）である。

変数 ${\displaystyle \lambda }$ はラグランジュ乗数に対応しており、各反復において ${\displaystyle \lambda }$ が真のラグランジュ乗数に近づいていく。拡張ラグランジュ関数法の利点はペナルティ関数法とは異なり元の問題を解くために ${\displaystyle \mu \rightarrow \infty }$ とする必要が無いことが挙げられる。これは目的関数にラグランジュ乗数項が含まれていることから、${\displaystyle \mu }$ が小さい値の場合でも、ill-conditioning とならない^[6]。しかしながら、実用上では数値誤差を少なくすることと強い収束性を保証するために、高次元の有界な集合にラグランジュ乗数 ${\displaystyle \lambda }$ を射影する手法が用いられている^[5]。

拡張ラグランジュ関数法は不等式制約付き最適化問題に対して拡張されている^[6][5]。

• 逐次二次計画法
• 逐次線形計画法
• 逐次線形二次計画法

以下はオープンソース、有償・商用版のソフトウェアにおいて拡張ラグランジュ関数法が実装されているものをまとめたものである:

• Accord.NET（拡張ラグランジュ関数法が C# によって実装されている。）
• ALGLIB（ソルバーの前処理に使用するために拡張ラグランジュ関数法が C# および C++ によって実装されている。）
• PENNON（GPL 3, 商用ライセンス）
• LANCELOT（内部使用ライセンスとして無償、あるいは商用ライセンスもオプションとして存在する。）
• MINOS（いくつかの最適化問題に対して拡張ラグランジュ関数法が使用可能。）
• コードは Apache 2.0 licensed REASON として利用可能^[7]。
• ALGENCAN (拡張ラグランジュ関数法が Fortran によって実装されている。）オンライン上で使用可能^[8]。
• NLOPT（C++ によって実装されているが、他のプログラミング言語からも呼び出し可能^[9][10][11]。）
• PyProximal（拡張ラグランジュ関数法が Python によって実装されている^[12]。）

• Bertsekas, Dimitri P. (1999), Nonlinear Programming (2nd ed.), Belmont, Mass: Athena Scientific, ISBN 978-1-886529-00-7 
• Birgin, E. G.; Martínez, J. M. (2014), Practical Augmented Lagrangian Methods for Constrained Optimization, Philadelphia: Society for Industrial and Applied Mathematics, doi:10.1137/1.9781611973365, ISBN 978-1-611973-35-8 
• Nocedal, Jorge; Wright, Stephen J. (2006), Numerical Optimization (2nd ed.), Berlin, New York: Springer-Verlag, ISBN 978-0-387-30303-1 

• バリア関数
• 内点法
• ラグランジュの未定乗数法
• ペナルティ関数法

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形（無制約）	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 放物線補間 パウエル法 勾配法 収束性 信頼領域 ウルフ条件 準ニュートン法 BFGS法 ブロイデン法 L-BFGS法 DFP法 SR1法 BHHH法 その他の求解法 ガウス・ニュートン法 最急降下法（確率的） レーベンバーグ・マーカート法 共役勾配法（非線形共役勾配法） 打ち切りニュートン法 ドッグレッグ法 鏡像 座標 バルジライ・ボールウェイン法 … ヘッセ行列 最適化におけるニュートン法
非線形（制約付き）	一般 バリア関数 ペナルティ関数法 微分可能 ラグランジュの未定乗数法 拡張ラグランジュ関数法 逐次二次計画法 逐次線形計画法 逐次線形二次計画法
凸最適化	凸最小化 切除平面法 簡約勾配法 劣勾配法 近接勾配法 線形 および 二次 内点法 アフィンスケーリング法 カーマーカーの射影変換法 メロートラの予測子修正子法 基底-交換 単体法 改訂単体法 十文字法 レムケの相補掃き出し法 その他 カチヤンの楕円体法 有効制約法 列生成法 ベンダーズ分解法
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題（分枝限定法・分枝カット法・分枝価格法） グラフ理論 最小全域木 ブルーフカ法 クラスカル法 プリム法 逆削除法 　最短経路問題 ベルマン–フォード法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法 フローネットワーク 最大流問題 ディニッツ法 エドモンズ–カープ法 フォード–ファルカーソン法 プリフロープッシュ法 最小費用流問題 ネットワーク単体法 アウトオブキルタ法
メタヒューリスティクス	進化的アルゴリズム（進化戦略・遺伝的アルゴリズム） 山登り法 局所探索法 焼きなまし法 タブーサーチ 群知能（ACO・PSO） ベイスンホッピング法 量子焼きなまし法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア （一覧）