拡張ラグランジュ関数法

拡張ラグランジュ関数法（かくちょうラグランジュかんすうほう、英: 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]。）