ラグランジアン緩和

数理最適化の分野において、ラグランジュ緩和法は制約条件付き最適化の難しい問題をより簡単な問題で近似する緩和法です。緩和された問題の解は元の問題の近似解となり、有用な情報を提供します。

この方法では、ラグランジュ乗数を使用して不等式制約の違反にペナルティを課し、違反にコストを課します。これらの追加コストは、最適化において厳密な不等式制約の代わりに使用されます。実際には、この緩和された問題は、元の問題よりも簡単に解決できることがよくあります。

双対変数（ラグランジュ乗数）のラグランジュ関数を最大化する問題は、ラグランジュ双対問題です。

次のような形式の 線形計画問題、 、 が与えられたとします。${\displaystyle x\in \mathbb {R} ^{n}}$${\displaystyle A\in \mathbb {R} ^{m,n}}$

の制約を、 となるように分割すると、システムは次のように記述できます。 ${\displaystyle A}$${\displaystyle A_{1}\in \mathbb {R} ^{m_{1},n}}$${\displaystyle A_{2}\in \mathbb {R} ^{m_{2},n}}$${\displaystyle m_{1}+m_{2}=m}$

制約(2)を目的関数に導入すると次のようになる。

を非負の重みとすると、制約条件(2)に違反した場合にはペナルティが課せられ、制約条件を厳密に満たした場合には報酬も与えられます。上記のシステムは、元の問題のラグランジアン緩和と呼ばれます。 ${\displaystyle \lambda =(\lambda _{1},\ldots ,\lambda _{m_{2}})}$

特に有用なのは、任意の固定された値のセットに対して、ラグランジュ緩和問題に対する最適結果は元の問題の最適結果よりも小さくならないという性質です。これを確認するには、元の問題の最適解を とし、ラグランジュ緩和の最適解を とします。すると、次のようになります。 ${\displaystyle {\チルダ {\lambda }}\succeq 0}$${\displaystyle {\hat {x}}}$${\displaystyle {\bar {x}}}$

最初の不等式は、元の問題で実行可能であるため真であり、2 番目の不等式は、ラグランジアン緩和の最適解であるため真です。 ${\displaystyle {\hat {x}}}$${\displaystyle {\bar {x}}}$

上記の不等式は、緩和された問題から得られる最大値を最小化すると、元の問題の目的値に対するより厳しい制限が得られることを示しています。したがって、代わりに部分的に双対化された問題を探索することで、元の問題に取り組むことができます。

ここで次のように 定義する。${\displaystyle P(\lambda )}$

ラグランジュ緩和アルゴリズムは、このようにして、内部問題によって返される結果を最小化しようとしながら、実行可能な値の範囲を探索します。 によって返される各値は、問題の上限候補であり、その最小値が最適な上限として保持されます。によって返される値によってシードされる可能性のあるヒューリスティックをさらに使用して、元の問題の実行可能なソリューションを見つけると、最適な上限と最適な実行可能なソリューションのコストが目的の許容値に収束するまで反復できます。 ${\displaystyle \lambda}$${\displaystyle P}$${\displaystyle P}$${\displaystyle {\bar {x}}}$${\displaystyle P}$

拡張ラグランジュ法は、ラグランジュ緩和法と本質的にはよく似ていますが、追加の項が追加され、より原理的な方法でデュアル パラメータが更新されます。これは 1970 年代に導入され、広く使用されてきました。 ${\displaystyle \lambda}$

ペナルティ法では、デュアル変数は使用されず、制約が削除され、代わりに制約からの逸脱にペナルティが課されます。この方法は概念的には単純ですが、ペナルティ法には悪条件の問題があるため、実際には拡張ラグランジュ法が好まれます 。

• Ravindra K. Ahuja、Thomas L. Magnanti、James B. Orlin (1993)。ネットワークフロー：理論、アルゴリズム、アプリケーション。Prentice Hall。ISBN 0-13-617549-X。{{cite book}}: CS1 maint: 複数の名前: 著者リスト (リンク)
• Bertsekas, Dimitri P. (1999)。非線形計画法: 第 2 版。Athena Scientific。ISBN 1-886529-00-0。 
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). 数値最適化: 理論と実践の側面。Universitext (1997 年フランス語版の翻訳の第 2 版)。ベルリン: Springer -Verlag。pp. xiv+490。doi :10.1007 / 978-3-540-35447-5。ISBN 3-540-35445-X. MR  2265882。
• ヒリアルト・ウルティ、ジャン・バティスト。ルマレシャル、クロード(1993)。凸解析および最小化アルゴリズム、第 1 巻: 基礎。 Grundlehren der Mathematischen Wissenschaften [数学科学の基本原理]。 Vol. 305. ベルリン: Springer-Verlag。ページ xviii+417。ISBN 3-540-56850-6MR  1261420 。
• ヒリアルト・ウルティ、ジャン・バティスト。ルマレシャル、クロード(1993)。 「実践者のための14の二元性」。凸解析および最小化アルゴリズム、第 II 巻: 高度な理論とバンドル法。 Grundlehren der Mathematischen Wissenschaften [数学科学の基本原理]。 Vol. 306. ベルリン: Springer-Verlag。ページ xviii+346。ISBN 3-540-56852-2。
• Lasdon, Leon S. (2002).大規模システムの最適化理論(1970 年 Macmillan 版の再版). ミネオラ、ニューヨーク: Dover Publications, Inc. pp. xiii+523. MR  1888251.
• ルマレシャル、クロード(2001)。 「ラグランジュ緩和」。 Michael Jünger と Denis Naddef (編)。計算による組み合わせ最適化: 2000 年 5 月 15 ～ 19 日にダグシュトゥール城で開催されたスプリング スクールの論文。コンピューターサイエンスの講義ノート。 Vol. 2241. ベルリン: Springer-Verlag。 112–156ページ。土井：10.1007/3-540-45586-8_4。ISBN 3-540-42877-1. MR  1900016. S2CID  9048698.
• Minoux, M. (1986).数理計画法: 理論とアルゴリズム. Egon Balas (序文) (Steven Vajda によるフランス語版 (1983 パリ: Dunod) からの翻訳). Chichester: A Wiley-Interscience Publication. John Wiley & Sons, Ltd. pp. xxviii+489. ISBN 0-471-90170-9。MR  0868279. (2008 第 2 版、フランス語: Programmation mathématique: Théorie et programminges . Editions Tec & Doc、パリ、2008. xxx+711 pp.)。

• エヴェレット、ヒュー III (1963)。「資源の最適配分の問題を解決するための一般化ラグランジュ乗数法」。オペレーションズ・リサーチ。11 (3): 399–417。doi : 10.1287 /opre.11.3.399。JSTOR  168028。MR 0152360  。
• Kiwiel, Krzysztof C .; Larsson, Torbjörn; Lindberg, P. O. (2007 年 8 月)。「ボールステップサブグラディエント法によるラグランジアン緩和」。オペレーションズ リサーチの数学。32 (3): 669–686。doi :10.1287/moor.1070.0261。MR  2348241。
• Bragin, Mikhail A.; Luh, Peter B.; Yan, Joseph H.; Yu, Nanpeng および Stern, Gary A. (2015)。「代理ラグランジュ緩和法の収束」『最適化理論と応用ジャーナル』 164 (1): 173-201, doi :10.1007/s10957-014-0561-3
• Bragin, Mikhail A.; Tucker, Emily, L. (2022)「混合整数線形計画法の代理「レベルベース」ラグランジアン緩和法」、Scientific Reports . 12 : 22417、doi:10.1038/s41598-022-26264-1
• Neal Young、「ラグランジアン緩和の例」、AlgNotes ブログより。
• Neal Young、2012、CSTheory Stack Exchange の Plotkin-Shmoys-Tardos および Arora-Kale ソルバーのおもちゃの例。