双対性（最適化）

双対ギャップとは、任意の主解と任意の双対解の値の差のことです。$\displaystyle d^{*}}$は最適な双対値であり、${\displaystyle p^{*}}$が最適な主値である場合、双対ギャップは${\displaystyle p^{*}-d^{*}}$この値は常に 0 以上です (最小化問題の場合)。双対性ギャップは、強双対性が成り立つ場合に限りゼロになります。そうでない場合は、ギャップは厳密に正であり、弱双対性が成り立ちます。^{[ 5 ]}

計算最適化では、別の「双対ギャップ」がよく報告されます。これは、任意の双対解と、主問題の実行可能だが最適ではない反復の値との差です。この別の「双対ギャップ」は、主問題に対する現在の実行可能だが最適ではない反復の値と双対問題の値との間の不一致を定量化します。双対問題の値は、正則条件の下で、主問題の凸緩和の値に等しくなります。凸緩和とは、非凸の実行可能集合をその閉じた凸包で置き換え、非凸関数をその凸閉包で置き換えることによって生じる問題です。凸閉包とは、元の主目的関数の閉じた凸包であるエピグラフを持つ関数です。 ^{[ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ] [ 15 ] [ 16 ]}

線形問題の場合、すべての制約を満たす各準最適点から、目的関数を増加させる移動方向または移動方向の部分空間が存在する。このような方向への移動は、候補解と1つ以上の制約との間のスラックを解消すると言われる。候補解の実行不可能な値とは、1つ以上の制約を超える値のことである。

双対問題では、双対ベクトルは主問題における制約の位置を決定する制約に掛け合わされます。双対問題で双対ベクトルを変更することは、主問題の上限を修正することと同等です。求められるのは、最も低い上限です。つまり、制約の候補位置と実際の最適値との間の余裕をなくすために、双対ベクトルを最小化します。双対ベクトルの値が低すぎると、実行不可能な値となります。これは、1つ以上の制約の候補位置を、実際の最適値から除外する位置に設定します。

この直感は、線形計画法の方程式によって形式化されます: 双対性。

動機付け^{[ 17 ]}

次の非線形計画問題を解きたいとします。

${\displaystyle {\begin{aligned}{\text{最小化}}&f_{0}(x)\\{\text{制約条件}}&f_{i}(x)\leq 0,\ i\in \left\{1,\ldots ,m\right\}\\\end{aligned}}}$

この問題には制約があります。これを制約のないプログラムに変換したいのです。理論的には、関数を最小化することでそれが可能です。${\displaystyle J(x)}$定義される

${\displaystyle J(x)=f_{0}(x)+\sum _{i}I[f_{i}(x)]}$

どこ${\displaystyle I}$無限ステップ関数です。${\displaystyle I[u]=0}$もし${\displaystyle u\leq 0}$、 そして${\displaystyle I[u]=\infty }$そうでなければ。しかし${\displaystyle J(x)}$連続ではないため、解くのが難しい。近似することは可能${\displaystyle I[u]}$による${\displaystyle \lambda u}$、 どこ${\displaystyle \lambda }$は正の定数である。これにより、ラグランジアンと呼ばれる関数が得られる。

${\displaystyle L(x,\lambda )=f_{0}(x)+\sum _{i}\lambda _{i}f_{i}(x)}$

すべての${\displaystyle x}$、

${\displaystyle \max _{\lambda \geq 0}L(x,\lambda )=J(x)}$。

証拠：

• もし${\displaystyle x}$すべての制約を満たす${\displaystyle f_{i}(x)\leq 0}$、 それから${\displaystyle L(x,\lambda )}$摂取時に最大化されます${\displaystyle \lambda =0}$、そしてその値は${\displaystyle f(x)}$;
• もし${\displaystyle x}$何らかの制約に違反する、${\displaystyle f_{i}(x)>0}$一部の人にとって${\displaystyle i}$、 それから${\displaystyle L(x,\lambda )\to \infty }$いつ${\displaystyle \lambda _{i}\to \infty }$。

したがって、元の問題は以下と同等である。

${\displaystyle \min _{x}\max _{\lambda \geq 0}L(x,\lambda )}$。

最小値と最大値の順序を逆にすると、次のようになります。

${\displaystyle \max _{\lambda \geq 0}\min _{x}L(x,\lambda )}$。

双対関数は、上記の式における内在的な問題である。

${\displaystyle g(\lambda ):=\min _{x}L(x,\lambda )}$。

ラグランジュ双対計画は、gを最大化する計画である。

${\displaystyle \max _{\lambda \geq 0}g(\lambda )}$。

双対問題の最適解は、元の（主）問題の最適解の下限値となります。これが弱双対性原理です。主問題が凸かつ下限を持ち、すべての非線形制約が厳密に満たされる点（スレーター条件）が存在する場合、双対問題の最適解は主問題の最適解と等しくなります。これが強双対性原理です。この場合、最適解を見つけることで主問題を解くことができます。$\displaystyle \lambda ^{*}}$双対プログラムに渡し、次に解く：

${\displaystyle \min _{x}L(x,\lambda ^{*})}$。

弱双対性原理または強双対性原理のいずれかを使用するには、計算する方法が必要であることに注意してください。${\displaystyle g(\lambda )}$一般的にこれは難しいかもしれません。なぜなら、それぞれに対して異なる最小化問題を解く必要があるからです。${\displaystyle \lambda }$しかし、一部の関数クラスについては、明示的な式を得ることが可能です。${\displaystyle g(\lambda )}$主問題と双対問題を一緒に解く方が、どちらか一方だけを解くよりも簡単な場合が多い。線形計画法や二次計画法などがその例である。双対性に対するより優れた、より一般的なアプローチは、フェンシェルの双対性定理によって提供される。^{[ 18 ]： Sub.3.3.1}

最小値と最大値と最小値が等しくなるもう一つの条件は、ラグランジアンに鞍点が存在する場合である。${\displaystyle (x^{*},\lambda ^{*})}$ラグランジュ関数の鞍点である${\displaystyle L}$かつその場合に限り${\displaystyle x^{*}}$これは原始問題の最適解です。$\displaystyle \lambda ^{*}}$これは双対問題の最適解であり、示された問題における最適値は互いに等しい。^{[ 18 ]：命題3.2.2}

標準形式の非線形計画問題が与えられた場合

${\displaystyle {\begin{aligned}{\text{minimize }}&f_{0}(x)\\{\text{subject to }}&f_{i}(x)\leq 0,\ i\in \left\{1,\ldots ,m\right\}\\&h_{i}(x)=0,\ i\in \left\{1,\ldots ,p\right\}\end{aligned}}}$

ドメイン付き${\displaystyle {\mathcal {D}}\subset \mathbb {R} ^{n}}$内部が空でないラグランジュ関数${\displaystyle {\mathcal {L}}:\mathbb {R} ^{n}\times \mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R} }$は次のように定義される。

${\displaystyle {\mathcal {L}}(x,\lambda ,\nu )=f_{0}(x)+\sum _{i=1}^{m}\lambda _{i}f_{i}(x)+\sum _{i=1}^{p}\nu _{i}h_{i}(x).}$

ベクトル${\displaystyle \lambda }$そして${\displaystyle \nu }$これらは、問題に関連付けられた双対変数またはラグランジュ乗数ベクトルと呼ばれます。ラグランジュ双対関数${\displaystyle g:\mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R} }$は次のように定義される。

${\displaystyle g(\lambda ,\nu )=\inf _{x\in {\mathcal {D}}}{\mathcal {L}}(x,\lambda ,\nu )=\inf _{x\in {\mathcal {D}}}\left\{f_{0}(x)+\sum _{i=1}^{m}\lambda _{i}f_{i}(x)+\sum _{i=1}^{p}\nu _{i}h_{i}(x)\right\}.}$

二重機能${\displaystyle g}$初期問題が凸関数でない場合でも、これはアフィン関数の点ごとの下限であるため、凹関数となる。双対関数は最適値の下限を与える。${\displaystyle p^{*}}$初期問題の場合、${\displaystyle \lambda \geq 0}$そしてどんな${\displaystyle \nu }$我々は持っています${\displaystyle g(\lambda ,\nu )\leq p^{*}}$。

スレーター条件などの制約条件が満たされ、元の問題が凸である場合、強い双対性、すなわち${\displaystyle d^{*}=\max _{\lambda \geq 0,\nu }g(\lambda ,\nu )=\inf f_{0}=p^{*}}$。

不等式制約付き凸最小化問題の場合、

${\displaystyle {\begin{aligned}&{\underset {x}{\operatorname {minimize} }}&&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\ldots ,m\end{aligned}}}$

ラグランジュ双対問題は

${\displaystyle {\begin{aligned}&{\underset {u}{\operatorname {maximize} }}&&\inf _{x}\left(f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)\right)\\&\operatorname {subject\;to} &&u_{i}\geq 0,\quad i=1,\ldots ,m\end{aligned}}}$

ここで、目的関数はラグランジュ双対関数である。ただし、関数は${\displaystyle f}$そして${\displaystyle g_{1},\ldots ,g_{m}}$連続的に微分可能であり、勾配がゼロになる点で下限値が発生する。

${\displaystyle {\begin{aligned}&{\underset {x,u}{\operatorname {maximize} }}&&f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)\\&\operatorname {subject\;to} &&\nabla f(x)+\sum _{j=1}^{m}u_{j}\,\nabla g_{j}(x)=0\\&&&u_{i}\geq 0,\quad i=1,\ldots ,m\end{aligned}}}$

これはウルフ双対問題と呼ばれています。この問題は、目的関数が結合変数に関して凹関数ではないため、計算的に扱うのが難しい場合があります。${\displaystyle (u,x)}$また、等式制約${\displaystyle \nabla f(x)+\sum _{j=1}^{m}u_{j}\,\nabla g_{j}(x)}$は一般に非線形であるため、Wolfe 双対問題は典型的には非凸最適化問題である。いずれにせよ、弱双対性は成り立つ。^{[ 19 ]}

• Ahuja, Ravindra K. ; Magnanti, Thomas L. ; Orlin, James B. (1993). Network Flows: Theory, Algorithms and Applications . Prentice Hall. ISBN 0-13-617549-X。
• Bertsekas, Dimitri; Nedic, Angelia; Ozdaglar, Asuman (2003).凸解析と最適化. Athena Scientific. ISBN 1-886529-45-0。
• Bertsekas, Dimitri P. (1999).非線形計画法（第2 版）. Athena Scientific. ISBN 1-886529-00-0。
• Bertsekas, Dimitri P. (2009).凸最適化理論. Athena Scientific. ISBN 978-1-886529-31-1。
• Bonnans, J.  Frédéric; Gilbert, J.  Charles; Lemaréchal, Claude ; Sagastizábal, Claudia  A. (2006). Numerical optimization: Theoretical and practical aspects . Universitext (1997年フランス語版の翻訳版、第2版改訂版 ). Berlin: Springer-Verlag. pp.  xiv+490. doi : 10.1007/978-3-540-35447-5 . ISBN 3-540-35445-XMR 2265882 .​ 
• Cook, William J. ; Cunningham, William H.; Pulleyblank, William R. ; Schrijver, Alexander (1997年11月12日).組合せ最適化(第1 版). John Wiley & Sons. ISBN 0-471-55894-X。
• Dantzig, George B. (1963).線形計画法とその拡張. プリンストン、ニュージャージー州: プリンストン大学出版局.
• ヒリアルト・ウルティ、ジャン・バティスト。ルマレシャル、クロード (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. MR 1295240 . 
• ラスドン、レオン・ S. (2002) [1970年マクミラン版の復刻版]。大規模システムの最適化理論。ニューヨーク州ミネオラ：ドーバー出版。xiii  +523頁。ISBN 978-0-486-41999-2. MR 1888251 . 
• Lawler, Eugene (2001). "4.5. 最大フロー最小カット定理の組み合わせ論的意味、4.6. 最大フロー最小カット定理の線形計画法による解釈".組み合わせ最適化：ネットワークとマトロイド. Dover. pp. 117–120 . ISBN  0-486-41453-1。
• ルマレシャル、クロード(2001)。 「ラグランジュ緩和」。ユンガーでは、マイケル。ナデフ、デニス (編)。計算による組み合わせ最適化: 2000 年5 月15 ～ 19 日にダグシュトゥール城で開催されたスプリング スクールの論文  。コンピューター サイエンス (LNCS) の講義ノート。 Vol.  2241. ベルリン: Springer-Verlag。 pp. 112–156 . doi : 10.1007/3-540-45586-8_4。ISBN  3-540-42877-1. MR 1900016 . S2CID 9048698 .  
• ミヌー、ミシェル（1986）。数理計画法：理論とアルゴリズム。エゴン・バラス（序文）、スティーブン・ヴァイダ（翻訳）（1983年パリ：デュノ社刊）。チチェスター：ワイリー・インターサイエンス出版。ジョン・ワイリー・アンド・サンズ社。pp.  xxviii+489。ISBN 0-471-90170-9。MR 0868279。 (2008 第 2 版、フランス語: Programmation mathématique : Théorie et programminges、Éditions Tec & Doc、パリ、2008 年。xxx+711 pp. ))。  
• ネリング、エヴァー・D.、タッカー、アルバート・W. (1993).線形計画法と関連問題. ボストン、マサチューセッツ州: アカデミック・プレス. ISBN 978-0-12-515440-6。
• パパディミトリウ、クリストス・H.、スティーグリッツ、ケネス（1998年7月）。組み合わせ最適化：アルゴリズムと複雑性（完全 版）。ドーバー出版。ISBN 0-486-40258-4。
• Ruszczyński, Andrzej (2006).非線形最適化. プリンストン、ニュージャージー州:プリンストン大学出版局 . xii+454頁. ISBN 978-0-691-11915-1. MR 2199043 . 

• Everett, Hugh III (1963). 「資源の最適配分問題の解決のための一般化ラグランジュ乗数法」 . Operations Research . 11 (3): 399–417 . doi : 10.1287/opre.11.3.399 . JSTOR 168028. MR 0152360. 2011年7月24日にオリジナルからアーカイブ済み。  
• Kiwiel, Krzysztof  C.; Larsson, Torbjörn; Lindberg, P.  O. (2007年8月) 「ボールステップ劣勾配法によるラグランジュ緩和」 . Mathematics of Operations Research . 32 (3): 669–686 . doi : 10.1287/moor.1070.0261 . MR 2348241. 2011年7月26日のオリジナルからアーカイブ済み。 2011年5月12日取得。 
• 線形計画法における双対性 ゲイリー・D・ノット