拡張ラグランジュ関数法のソースを表示

{{Expand English|date=2025年3月}}

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

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

拡張ラグランジュ関数法は元々1970年代から1980年代にかけてペナルティ関数法の代替的手法として乗数法という名で知られていた。拡張ラグランジュ関数法は1969年に{{仮リンク|マグナス・ヘステネス|en|Magnus Hestenes}}と{{仮リンク|マイケル・J・D・パウエル|en|Michael J. D. Powell|label=マイケル・パウエル}}によって始めて議論された<ref>{{cite journal |first=M. R. |last=Hestenes |title=Multiplier and gradient methods |journal=Journal of Optimization Theory and Applications |volume=4 |year=1969 |issue=5 |pages=303–320 |doi=10.1007/BF00927673 }}</ref><ref>{{cite book |first=M. J. D. |last=Powell |chapter=A method for nonlinear constraints in minimization problems |title=Optimization |editor-first=R. |editor-last=Fletcher |publisher=Academic Press |location=New York |year=1969 |pages=283–298 |isbn=0-12-260650-7 }}</ref>。その後、{{仮リンク|ロッカフェラー, R・ティレル|en|R. Tyrrell Rockafellar}}によって[[フェンシェルの双対性定理|フェンツェル双対]]に関連して研究され、特に[[構造工学|構造最適化]]で用いられる近接点法、Moreau-Yoshida正則化、{{仮リンク|単調作用素|en|monotone operator}}最大化と併せて研究された。また{{仮リンク|ディミトリ・ベルツェカス|en|Dimitri Bertsekas}}が1982年に出版した著書に非二次正則化関数の項目（{{仮リンク|ブレグマンダイバージェンス|en|Bregman divergence|label=エントロピー正則化}}）で掲載された<ref>{{cite book |doi=10.1016/C2013-0-10366-2 |title=Constrained Optimization and Lagrange Multiplier Methods |date=1982 |isbn=978-0-12-093480-5 |first1=Dimitri P. |last1=Bertsekas |authorlink1=:en:Dimitri Bertsekas }}{{pn|date=2024-12}}</ref>。これらの研究から乗数法を指数型乗数法（exponential method of multipliers）に拡張することができ、二階微分可能な拡張ラグランジュ関数として扱えるようになった。

1970年代以降、拡張ラグランジュ関数法が一部の[[数値線形代数|数値解析]][[数値解析ソフトウェア|ライブラリ]]において[[疎行列]][[サブルーチン]]を容易に使用することが可能になり、{{仮リンク|自己整合障壁関数|en|self-concordant function}}理論による内点法の優れた大域的収束性の保証から、[[逐次二次計画法]]（SQP）および[[内点法]]（IPM）が研究されるようになった。拡張ラグランジュ関数法は[[:en:Galahad library|LANCELOT]]やALGENCAN<ref>{{cite journal |last1=Andreani |first1=R. |last2=Birgin |first2=E. G. |last3=Martínez |first3=J. M. |last4=Schuverdt |first4=M. L. |title=On Augmented Lagrangian Methods with General Lower-Level Constraints |journal=SIAM Journal on Optimization |date=2008-01 |volume=18 |issue=4 |pages=1286–1309 |doi=10.1137/060654797 }}</ref><ref name="BirginMartinez 2014">{{harvtxt|Birgin|Martínez|2014}}</ref>、AMPLなどの最適化システムに実装され、密行列をもつ問題を分割可能な問題によって行列を疎行列として扱えるようになり、注目されるようになった。このことから、拡張ラグランジュ関数法は現在でも使用されている
<ref name="Nocedal 2006">{{harvtxt|Nocedal|Wright|2006}}, chapter 17</ref>。

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

== 一般的な解法 ==
以下の制約付き最適化問題を考える:
:<math> \min f(\mathbf{x}) </math>
subject to
:<math> c_i(\mathbf{x}) = 0 ~\forall  i \in \mathcal{E}, </math>

ただし、<math>\mathcal{E}</math> は等式制約とする。この問題は無制約最小化問題の一種として解くことができる。参考までに、
''k''回目の反復における[[ペナルティ関数法]]の例を紹介する:
:<math> \min \Phi_k (\mathbf{x}) = f (\mathbf{x}) + \mu_k ~ \sum_{i\in \mathcal{E}} ~ c_i(\mathbf{x})^2. </math>
ペナルティ関数法では上記の問題を解いた後、次の反復ではより大きな <math>\mu_k</math> の下で問題を解き直す。このとき、前の反復で求まった解 <math>\mu_k</math> を使用することで問題の求解にてホットスタートすることができる。

拡張ラグランジュ関数法では以下の無制約の目的関数を用いる:
:<math> \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})</math>
各反復において、<math>\mu_k</math> を更新し、<math>\lambda</math> も以下の式によって更新される:
:<math>\lambda_i \leftarrow \lambda_i + \mu_k c_i(\mathbf{x}_k) </math>
ただし、<math>\mathbf{x}_k</math> は''k''番目の反復における問題を解いた解（例: <math>\mathbf{x}_k=\text{argmin} \Phi_k(\mathbf{x}) </math>）である。

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

拡張ラグランジュ関数法は不等式制約付き最適化問題に対して拡張されている<ref name="Nocedal 2006"/><ref name="BirginMartinez 2014"/>。

== 他の解法 ==
* [[逐次二次計画法]]
* [[逐次線形計画法]]
* {{仮リンク|逐次線形二次計画法|en|Sequential linear-quadratic programming}}

== ソフトウェア ==
以下はオープンソース、有償・商用版のソフトウェアにおいて拡張ラグランジュ関数法が実装されているものをまとめたものである:
* [[:en:Accord.NET|Accord.NET]]（拡張ラグランジュ関数法が C# によって実装されている。）
* [[ALGLIB]]（ソルバーの前処理に使用するために拡張ラグランジュ関数法が C# および C++ によって実装されている。）
* [[:en:PENOPT|PENNON]]（GPL 3, 商用ライセンス）
* [[:en:Galahad library|LANCELOT]]（内部使用ライセンスとして無償、あるいは商用ライセンスもオプションとして存在する。）
* [[:en:MINOS (optimization software)|MINOS]]（いくつかの最適化問題に対して拡張ラグランジュ関数法が使用可能。）
* コードは Apache 2.0 licensed REASON として利用可能<ref>{{Cite web|url=https://bitbucket.org/megaDataLab/reason2|title=Bitbucket|website=bitbucket.org |accessdate=2025-03-07 }}</ref>。
* ALGENCAN (拡張ラグランジュ関数法が Fortran によって実装されている。）オンライン上で使用可能<ref>{{Cite web|url=https://www.ime.usp.br/~egbirgin/tango/codes.php|title=TANGO Project|website=www.ime.usp.br |accessdate=2025-03-07 }}</ref>。
* NLOPT（C++ によって実装されているが、他のプログラミング言語からも呼び出し可能<ref>{{Citation |last=Stamm |first=Aymeric |title=nloptr |date=2022-07-15 |url=https://github.com/astamm/nloptr |access-date=2022-07-19}}</ref><ref>{{Citation |title=The NLopt module for Julia |date=2022-06-25 |url=https://github.com/JuliaOpt/NLopt.jl |publisher=JuliaOpt |access-date=2022-07-19}}</ref><ref>{{Citation |last=Johnson |first=Steven G. |title=stevengj/nlopt |date=2022-07-14 |url=https://github.com/stevengj/nlopt |access-date=2022-07-19 }}</ref>。）
* PyProximal（拡張ラグランジュ関数法が Python によって実装されている<ref>{{Cite web|url=http://pyproximal.readthedocs.io|title=PyProximal Project|website=www.github.com/PyLops/pyproximal |accessdate=2025-03-07 }}</ref>。）

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 参考文献 ==
* {{Citation |last1=Bertsekas |first1=Dimitri P. |title=Nonlinear Programming |publisher=[[Athena Scientific]] |location=Belmont, Mass |edition=2nd |isbn=978-1-886529-00-7 |year=1999 }}
* {{Citation |last1=Birgin |first1=E. G. |last2=Martínez |first2=J. M. |title=Practical Augmented Lagrangian Methods for Constrained Optimization |publisher=[[SIAM|Society for Industrial and Applied Mathematics]] |location=Philadelphia | isbn=978-1-611973-35-8 |year=2014 |doi=10.1137/1.9781611973365|doi-access=free }}
* {{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 }}

== 関連項目 ==
* [[バリア関数]]
* [[内点法]]
* [[ラグランジュの未定乗数法]]
* [[ペナルティ関数法]]

{{最適化アルゴリズム}}

{{DEFAULTSORT:かくちようらくらんしゆかんすうほう}}
[[Category:最適化アルゴリズムとメソッド]]
[[Category:数学に関する記事]]