拡張ラグランジアン法

拡張ラグランジュ法は、制約付き最適化問題を解くためのアルゴリズムの一種です。制約付き最適化問題を一連の制約なしの問題に置き換え、目的関数にペナルティ項を追加するという点でペナルティ法と類似していますが、拡張ラグランジュ法では、ラグランジュ乗数を模倣するように設計された別の項が追加されます。拡張ラグランジュ法は、ラグランジュ乗数法と関連していますが、同一ではありません。

別の見方をすると、制約のない目的関数は、制約のある問題のラグランジアンであり、追加のペナルティ項（増加）が含まれます。

この方法はもともと乗数法として知られ、1970年代と1980年代にペナルティ法の潜在的な代替として研究されました。この方法は最初にマグナス・ヘステネス^[1]によって議論され、次に1969年にマイケル・パウエル^{[2]によって議論されました。この方法は、}フェンシェル双対性、特に近点法、モロー–ヨシダ正則化、最大単調演算子との関連でR・ティレル・ロカフェラーによって研究されました。これらの方法は構造最適化で使用されました。この方法は、ディミトリ・ベルツェカスによっても研究され、特に1982年の著書^{[3]では、非二次正則化関数（}エントロピー正則化など）を含む拡張とともに研究されました。この複合研究から、2回微分可能な拡大ラグランジアン関数で不等式制約を処理する「指数乗数法」が生まれました。

1970年代以降、逐次二次計画法（SQP）と内点法（IPM）が注目されるようになった。これは、数値ソフトウェアライブラリの疎行列 サブルーチンをより簡単に使用できることと、自己一致関数の理論によってIPMが証明された計算量結果を持っていることが理由である。拡張ラグランジュ法は最適化システムLANCELOT、ALGENCAN ^{[4] [5]}、AMPLによって活性化され、一見密だが「部分的に分離可能な」問題に疎行列技術を使用できるようになりました。この方法は、いくつかの問題で今でも有用です。^[6]

2007 年頃、全変動ノイズ除去や圧縮センシングなどの分野で拡張ラグランジュ法が復活しました。特に、標準的な拡張ラグランジュ法の変形で部分更新を使用するもの (線形方程式を解くガウス・ザイデル法に類似) である交互方向乗数法( ADMM) が注目を集めました。

次の制約付き最適化問題を解くことを考えてみましょう。

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

対象となる

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

ここで、は等式制約のインデックスを表します。この問題は、一連の制約のない最小化問題として解くことができます。参考までに、ペナルティ法アプローチのk番目のステップを最初に示します。 ${\displaystyle {\mathcal {E}}}$

${\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 \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})}$

ここで、 は制約のない問題のk番目のステップでの解です(つまり)。 ${\displaystyle \mathbf {x} _{k}}$${\displaystyle \mathbf {x} _{k}={\text{argmin}}\Phi _{k}(\mathbf {x} )}$

変数はラグランジュ乗数の推定値であり、この推定値の精度はステップごとに向上します。この方法の主な利点は、ペナルティ法とは異なり、元の制約問題を解くために を取る必要がないことです。ラグランジュ乗数項が存在するため、 ははるかに小さいままにすることができ、悪条件を回避できます。^[6]ただし、実際の実装では、乗数の推定値を大きな境界セット（セーフガード）に投影するのが一般的であり、これにより数値的不安定性が回避され、強力な理論的収束につながります。^[5]${\displaystyle \lambda}$${\displaystyle \mu \rightarrow \infty }$${\displaystyle \mu}$

この方法は不等式制約を扱うために拡張することができる。実用的な改善については文献^{[6] [5]を参照のこと。}

交互方向乗数法（ADMM）は、双対変数の部分更新を使用する拡張ラグランジュ法の変形です。この方法は、次のような問題を解くためによく適用されます。

${\displaystyle \min_{x}f(x)+g(x).}$

これは制約問題と同等であり、

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

この変更は些細なことのように思えるかもしれませんが、制約付き最適化の方法 (特に、拡張ラグランジュ法) を使用して問題に取り組むことができるようになり、目的関数はxとyで分離可能になりました。デュアル更新では、 xとyで近接関数を同時に解く必要があります。ADMM 手法では、最初にyを固定してxを解き、次にx を固定してyを解くことで、この問題を近似的に解くことができます。収束するまで反復するのではなく (ヤコビ法のように)、アルゴリズムは直接デュアル変数を更新し、その後プロセスを繰り返します。これは正確な最小化と同じではありませんが、いくつかの仮定の下では、この方法は正しい解に収束します。この近似のため、アルゴリズムは純粋な拡張ラグランジュ法とは異なります。

ADMM は Douglas-Rachford 分割アルゴリズムの応用と見なすことができ、Douglas-Rachford アルゴリズムは Proximal point アルゴリズムのインスタンスです。詳細については、参考文献^[7]を参照してください。 YALL1 ^[8] (2009)、SpaRSA ^[9] (2009)、SALSA ^[10] (2009) など、 ADMM を使用して基底追求法とその変形を解く最新のソフトウェア パッケージがいくつかあります。 ADMM を使用してより一般的な問題を解くパッケージもあり、その一部は複数のコンピューティング コアを活用できます (例: SNAPVX ^[11] (2015)、parADMM ^[12] (2016))。

確率的最適化では、関数のノイズ サンプル (勾配) にアクセスして損失関数を最小化する問題を検討します。目標は、新しいサンプルごとに最適なパラメーター (最小化器) を推定することです。いくつかの変更を加えると、ADMM を確率的最適化に使用できます。確率的設定では、勾配のノイズ サンプルのみにアクセスできるため、ラグランジアンの不正確な近似が使用されます。

${\displaystyle {\hat {\mathcal {L}}}_{\rho ,k}=f_{1}(x_{k})+\langle \nabla f(x_{k},\zeta _{k+ 1}),x\rangle +g(y)-z^{T}(Ax+By-c)+{\frac {\rho }{2}}\Vert Ax+By-c\Vert ^{2}+{\frac {\Vert x-x_{k}\Vert ^{2}}{2\eta _{k+1}}},}$

ここで、は時間によって変化するステップサイズである。^[13]${\displaystyle \eta_{k+1}}$

ADMMは正規化された問題を解決するために適用されており、関数の最適化と正規化を局所的に実行し、制約を介してグローバルに調整することができます。^{[14] [15] [16] [17]}

正規化は不適切性を克服し、最適解の節約（例えば、スパース性や低ランク）を促進する自然なメカニズムであるため、正規化最適化問題は高次元領域で特に重要です。正規化問題を解くためのADMMの有効性は、高次元の確率的最適化問題を解決するのに有用である可能性があることを意味している可能性があります。^[18]

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

拡張ラグランジアン法のオープンソースおよび非フリー/商用実装:

• Accord.NET (拡張ラグランジュ最適化の C# 実装)
• ALGLIB (前処理付き拡張ラグランジアン ソルバーの C# および C++ 実装)
• PENNON (GPL 3、商用ライセンス利用可能)
• LANCELOT (無料の「社内使用」ライセンス、有料の商用オプション)
• MINOS (一部の種類の問題では拡張ラグランジュ法も使用します)。
• Apache 2.0ライセンスのREASONのコードはオンラインで入手可能です。^[19]
• ALGENCAN（セーフガード付き拡張ラグランジュ法のFortran実装）。オンラインで入手可能。^[20]
• NLOPT（拡張ラグランジュ最適化器のC++実装、さまざまなプログラミング言語からアクセス可能^{[21] [22]}）^[23]
• PyProximal（拡張ラグランジュ法のPython実装）。^[24]

• バリア機能
• 内点法
• ラグランジュ乗数
• ペナルティ方式

• Bertsekas, Dimitri P. (1999)、非線形プログラミング(第 2 版)、マサチューセッツ州ベルモント: Athena Scientific、ISBN 978-1-886529-00-7
• バージン、EG; マルティネス、JM (2014)、制約付き最適化のための実用的な拡張ラグランジアン法、フィラデルフィア：産業応用数学協会、doi：10.1137/1.9781611973365、ISBN 978-1-611973-35-8
• Nocedal, Jorge; Wright, Stephen J. (2006)、数値最適化（第2版）、ベルリン、ニューヨーク：Springer-Verlag、ISBN 978-0-387-30303-1