二重性（最適化）

数理最適化理論において、双対性または双対性原理とは、最適化問題を主問題と双対問題という2つの視点から見ることができるという原理である。主問題が最小化問題であれば、双対問題は最大化問題である（逆もまた同様）。主（最小化）問題に対する実行可能な解はどれも、双対（最大化）問題に対する実行可能な解と少なくとも同じ大きさである。したがって、主問題の解は双対問題の解の上限であり、双対問題の解は主問題の解の下限である。^{[1]この事実は}弱い双対性と呼ばれる。

一般に、主問題と双対問題の最適値は必ずしも等しくありません。その差は双対性ギャップと呼ばれます。凸最適化問題の場合、制約適格条件下では双対性ギャップはゼロになります。この事実は強い双対性と呼ばれます。

通常、「双対問題」という用語はラグランジュ双対問題を指しますが、ウルフ双対問題やフェンシェル双対問題など、他の双対問題も使用されます。ラグランジュ双対問題は、非負のラグランジュ乗数を使用して制約を目的関数に追加し、元の目的関数を最小化する主変数値を解くことで、最小化問題のラグランジュを形成することによって得られます。この解は、双対変数と呼ばれるラグランジュ乗数の関数として主変数を与えるため、新しい問題は、双対変数に対する導出された制約（少なくとも非負制約を含む）の下で、双対変数に関して目的関数を最大化することです。

一般に、分離された局所凸空間の2 つの双対と関数 が与えられている場合、となるような を見つけることが基本問題として定義できます。 言い換えると、 が存在する場合、は関数 の最小値であり、関数 の最小値(最大の下限) が達成されます。 ${\displaystyle \left(X,X^{*}\right)}$${\displaystyle \left(Y,Y^{*}\right)}$${\displaystyle f:X\to \mathbb {R} \cup \{+\infty \}}$${\displaystyle {\hat {x}}}$${\displaystyle f({\hat {x}})=\inf _{x\in X}f(x).\,}$${\displaystyle {\hat {x}}}$${\displaystyle f({\hat {x}})}$${\displaystyle f}$

制約条件がある場合、 をとすることで関数に組み込むことができます。ここでは、制約条件で最小値 0 を持ち、 であることを証明できる 上の適切な関数です。後者の条件は、特性関数に対して自明ですが、常に都合よく満たされるわけではありません(つまり、制約条件を満たす場合とそうでない場合)。次に、となる摂動関数に拡張します。^[2]${\displaystyle f}$${\displaystyle {\tilde {f}}=f+I_{\mathrm {制約} }}$${\displaystyle I_{\mathrm {制約} }}$${\displaystyle X}$${\displaystyle \inf _{x\in X}{\tilde {f}}(x)=\inf _{x\ \mathrm {constrained} }f(x)}$${\displaystyle I_{\mathrm {制約} }(x)=0}$${\displaystyle x}$${\displaystyle I_{\mathrm {制約} }(x)=\infty }$${\displaystyle {\tilde {f}}}$ ${\displaystyle F:X\times Y\to \mathbb {R} \cup \{+\infty \}}$${\displaystyle F(x,0)={\tilde {f}}(x)}$

双対性ギャップは不等式の右辺と左辺の差である。

${\displaystyle \sup _{y^{*}\in Y^{*}}-F^{*}(0,y^{*})\leq \inf _{x\in X}F(x,0),\,}$

ここで は両変数の凸共役であり、 は上限を表す。^{[2] [3] [4]}${\displaystyle F^{*}}$${\displaystyle \sup}$

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

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

線形計画問題は、目的関数と制約がすべて線形である最適化問題です。基本問題では、目的関数はn 個の変数の線形結合です。制約はm個あり、それぞれがn 個の変数の線形結合に上限を設定します。目標は、制約に従って目的関数の値を最大化することです。解は、目的関数の最大値を達成する n個の値のベクトル(リスト)です。

双対問題では、目的関数は、主問題のm 個の制約の限界であるm個の値の線形結合です。n個の双対制約があり、それぞれがm 個の双対変数の線形結合に下限を設定します。

線形の場合、基本問題では、すべての制約を満たす各準最適点から、目的関数を増加させる方向または方向のサブスペースが存在します。このような方向に移動すると、候補ソリューションと 1 つ以上の制約との間の余裕がなくなると言われています。候補ソリューションの実行不可能な値とは、1 つ以上の制約を超える値です。

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

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

非線形計画法では、制約は必ずしも線形ではありません。それでも、同じ原則の多くが適用されます。

非線形問題のグローバル最大値を簡単に特定できるようにするには、問題の定式化で関数が凸関数であり、コンパクトな下位レベル セットを持つことが求められることがよくあります。これが、Karush–Kuhn–Tucker 条件の重要性です。これらは、非線形計画問題のローカル最適値を特定するために必要な条件を提供します。最適解への方向を定義できるようにするために必要な追加の条件 (制約条件) があります。最適解はローカル最適値ですが、グローバル最適値ではない可能性があります。

動機. ^[17]次の非線形計画問題を解きたいとします。

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

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

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

ここで、I は無限ステップ関数です。u≤0 の場合は I[u]=0、それ以外の場合は I[u]=∞ です。しかし、J ( x ) は連続していないため解くのが困難です。I[u] をλuで「近似」することは可能です。ここで、λは正の定数です。これにより、ラグランジアンと呼ばれる関数が生成されます。

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

任意のxに対して、

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

証拠：

• xがすべての制約f _i ( x )≤0を満たす場合、L( x , λ )はλ =0のときに最大化され、その値はf(x)になります。
• x が何らかの制約、すなわち、あるiに対してf _i ( x )>0に違反する場合、λ _i →∞のときに L(x, λ )→∞ となる。

したがって、元の問題は次の問題と同等になります。

${\displaystyle \min_{x}\max_{\lambda \geq 0}L(x,\lambda )}$。

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

${\displaystyle \max_{\lambda\geq0}\min_{x}L(x,\lambda)}$。

双対関数は上記の式の内部問題です。

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

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

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

双対プログラムの最適解は、元の（主）プログラムの最適解の下限です。これが弱い双対性原理です。主問題が凸で下から有界であり、すべての非線形制約が厳密に満たされる点（スレーターの条件）が存在する場合、双対プログラムの最適解は主プログラムの最適解に等しくなります。これが強い双対性原理です。この場合、双対プログラムの最適解λ *を見つけて、次のように解くことで主プログラムを解くことができます。

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

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

最小-最大と最大-最小が等しいもう一つの条件は、ラグランジュ関数が鞍点を持つときである： (x∗, λ∗)がラグランジュ関数Lの鞍点であるのは、x∗が主関数の最適解であり、λ∗が双対関数の最適解であり、示された問題における最適値が互いに等しい場合のみである。^{[18] ：Prop.3.2.2}

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

${\displaystyle {\begin{aligned}{\text{最小化}&f_{0}(x)\\{\text{ただし}&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\}}.}$

双対関数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}}}$

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

ジョージ・ダンツィグによると、線形最適化の双対定理は、ダンツィグが線形計画問題を提示した直後に ジョン・フォン・ノイマンによって推測された。フォン・ノイマンは、ゲーム理論の情報を使用していることに気づき、2人ゼロ和行列ゲームは線形計画と同等であると推測した。厳密な証明は、1948年にアルバート・W・タッカーとそのグループによって初めて発表された。（ダンツィグによるネリングとタッカーへの序文、1993年）

サポートベクターマシン(SVM)では、SVM の主問題を双対問題として定式化することでカーネルトリックを実装できますが、従来のケースでは後者の方が時間計算量が高くなります。

• 凸双対性
• 二重性
• 緩和（近似）

• Ahuja, Ravindra K. ; Magnanti, Thomas L. ; Orlin, James B. (1993)。ネットワークフロー: 理論、アルゴリズム、アプリケーション。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). 数値最適化: 理論と実践の側面。Universitext (1997 年フランス語版の翻訳の第 2 版)。ベルリン: Springer -Verlag。pp. xiv+490。doi :10.1007 / 978-3-540-35447-5。ISBN 3-540-35445-X. MR  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 年マクミランの再版]。大規模システムの最適化理論。ミネオラ、ニューヨーク：ドーバー出版、pp. xiii+ 523。ISBN 978-0-486-41999-2. MR  1888251.
• Lawler, Eugene (2001)。「4.5. 最大フロー最小カット定理の組み合わせ的意味、4.6. 最大フロー最小カット定理の線形計画法による解釈」。組み合わせ最適化: ネットワークとマトロイド。ドーバー。pp. 117–120。ISBN 0-486-41453-1。
• ルマレシャル、クロード(2001)。 「ラグランジュ緩和」。ユンガーでは、マイケル。ナデフ、デニス (編)。計算による組み合わせ最適化: 2000 年 5 月 15 ～ 19 日にダグシュトゥール城で開催されたスプリング スクールの論文。コンピューター サイエンス (LNCS) の講義ノート。 Vol. 2241. ベルリン: Springer-Verlag。 112–156ページ。土井：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アルゴリズム、Éditions Tec & Doc、パリ、2008. xxx+711 pp. ))。
• Nering, Evar D.; Tucker, Albert W. (1993).線形計画法と関連問題. ボストン、マサチューセッツ州: Academic Press. ISBN 978-0-12-515440-6。
• Papadimitriou, Christos H.; Steiglitz, Kenneth (1998 年 7 月)。組み合わせ最適化: アルゴリズムと複雑性(完全版)。ドーバー。ISBN 0-486-40258-4。
• Ruszczyński, Andrzej (2006).非線形最適化. プリンストン、ニュージャージー:プリンストン大学出版局. pp. xii+454. ISBN 978-0-691-11915-1MR  2199043 。

• Everett, Hugh III (1963). 「リソースの最適割り当ての問題を解決するための一般化ラグランジュ乗数法」.オペレーションズ・リサーチ. 11 (3): 399–417. doi :10.1287/opre.11.3.399. JSTOR  168028. MR  0152360. 2011-07-24 にオリジナルからアーカイブされました。
• Kiwiel, Krzysztof C.; Larsson, Torbjörn; Lindberg, P. O. (2007 年 8 月). 「ボールステップ サブグラディエント法によるラグランジアン緩和」.オペレーションズ リサーチの数学. 32 (3): 669–686. doi :10.1287/moor.1070.0261. MR  2348241. 2011 年 7 月 26 日にオリジナルからアーカイブ。2011年 5 月 12 日に取得。
• 線形計画法における双対性 ゲイリー・D・ノット