4. 線形最適化問題の双対性 #

4.1. 導入 #

数理的な構造には「双対 (dual)」とよばれる多くは非自明な二元的な関係 (双対性: duality) がある．双対と呼ばれる関係では共通して，およそ次の性質を持っている．

双対な関係にある対象は互いに一対一の関係である．

(1)#\[\tilde{x} = f(x)\]

¹このような写像 \(f\) は対合 (involution) とよばれる．

双対の双対は元の対象である ¹ ¹このような写像 \(f\) は対合 (involution) とよばれる．．

(2)#\[f(f(x)) = x\]

双対性の代表的な例として次を挙げることができる．

Legendre 変換

数理最適化でも双対性があり，特に基本的なものが線形最適化問題についての双対性である．これは様々な理論的概念を互いに結びつけ，地続きの理解を構築していく上では欠かせない性質となっている．この他，先に挙げた代表的な双対性の例も，これらの話題の中で密接に関係してくる．

4.2. 主問題と双対問題 #

線形最適化問題には一般的にいえる性質として双対性がある．この性質は次に定める主問題，双対問題から直ちに導かれる．

主問題，双対問題，双対変数

線形最適化問題の標準形が与えられたとする．

(3)#\[\begin{split}& \mathrm{Minimize\colon}~ f(\vec{x}) = \vec{c}^{\top}\vec{x} \\ & \mathrm{subject~to\colon}~ \\ & A\vec{x} = \vec{b}, \\ &\vec{x} \geq \vec{0}\end{split}\]

これに対して，次の問題を考える．

(4)#\[\begin{split}& \mathrm{Maximize\colon}~ \tilde{f}(\vec{\omega}) = \vec{b}^{\top}\vec{\omega} \\ & \mathrm{subject~to\colon}~ \\ & A^{\top}\vec{\omega} \leq \vec{c}\end{split}\]

このようにして与えた問題 (4) を双対問題 (dual problem) といい，元の問題 (3) を主問題 (primal problem, master problem) という．また \(\vec{\omega}\) を双対変数という．

ここに双対問題はスラック変数を用いて定義していないことを反映して， \(\vec{\omega}\) に非負条件が不要であることと制約条件が不等式であることに注意する．スラック変数 \(\vec{s}\) を用いてこの双対問題を書き直しておくと次のとおり．

(5)#\[\begin{split}& \mathrm{Maximize\colon}~ \tilde{f}(\vec{\omega}) = \vec{b}^{\top}\vec{\omega} \\ & \mathrm{subject~to\colon}~ \\ & A^{\top}\vec{\omega} + \vec{s} = \vec{c}, \\ & \vec{s} \geq \vec{0}\end{split}\]

何かを最小化することは，何かを最大化することに同じであろう．そして制約条件が厳しすぎて解なしであることは，自由度がありすぎて非有界であることに同じであろう．これら相対する見方が同じであろうという，互いに裏返しの関係を線形最適化問題では見出すことができる．

注釈

主問題に対して双対問題の形が何故そのような形になるのか，その背景を述べる．

まず主問題として最小化問題を考えているので，目的関数の下界を知ることは大きな手掛かりである．その下限は制約条件式によって定まる実行可能領域と関係している．このことから制約条件式に直接目的関数の式を見出すことができれば，下界についての情報が得られそうである．

そこで主問題の制約条件式に対して \(\vec{\omega}^{\top}\) を左から作用させて式を整理する．

(6)#\[(A^{\top}\vec{\omega})^{\top}\vec{x} = \vec{b}^{\top}\vec{\omega}\]

ここで導入した \(\vec{\omega}\) とは \(\vec{c}\geq A^{\top}\vec{\omega}\) を満たすものと決めれば，それ故に上記に整理した制約条件式から下界が得られる．

(7)#\[\vec{c}^{\top}\vec{x} \geq \vec{b}^{\top}\vec{\omega}\]

我々は非自明な下界としてなるべく大きい下界を知りたいから，そのためには次の最大化問題を解けばよい．

(8)#\[\begin{split}& \mathrm{Maximize\colon}~ \tilde{f}(\vec{\omega}) = \vec{b}^{\top}\vec{\omega} \\ & \mathrm{subject~to\colon}~ \\ & A^{\top}\vec{\omega} \leq \vec{c}\end{split}\]

これは双対問題とよぶ問題に他ならない．以上の背景は，弱双対定理をはじめとする様々な数理的構造を自然に理解することへと繋がる．

以下に主問題と双対問題のとの関係を定理として，その数理的な構造を述べていく．

4.3. 弱双対定理 #

主問題および双対問題の定義から，弱双対定理とその系が直ちに導かれる．

弱双対定理

主問題および双対問題の任意の実行可能解 \(\vec{x},\vec{\omega}\) に対して，常に次の不等式が成立する．

(9)#\[\vec{c}^{\top}\vec{x} \geq \vec{b}^{\top}\vec{\omega}\]

証明

主問題 (3) および双対問題 (4) の制約条件を用いて，次のように所望の不等式を得ることができる．

(10)#\[\vec{c}^{\top}\vec{x} \geq (A^{\top}\vec{\omega})^{\top} \vec{x} = \vec{\omega}^{\top}\vec{b} = \vec{b}^{\top}\vec{\omega}\]

弱双対定理は次の一連の主張を系として導く．これらの主張は弱双対性定理より明らかである．

主問題の任意の実行可能解 \(\vec{x}\) に対して双対問題の最大値 \({\rm D_{\max}}\) (最適値)との間に次の関係が成立する．

(12)#\[\vec{c}^{\top} \vec{x} \geq {\rm D_{\max}}\]

またこれと同様に双対問題の任意の実行可能解 \(\vec{\omega}\) に対して主問題の最小値 \({\rm P_{\min}}\) (最適値)との間に次の関係が成立する．

(13)#\[\vec{b}^{\top} \vec{\omega} \leq {\rm P_{\min}}\]
主問題と双対問題それぞれの実行可能解 \(\vec{x},\vec{\omega}\) が弱双対定理の等号条件を満足するならば，これら \(\vec{x},\vec{\omega}\) という解は各問題の最適解である．
主問題 (双対問題) が有界でないならば，双対問題 (主問題) は実行可能解は存在しない．

4.4. 双対定理 #

弱双対定理およびその系から，双対問題の実行可能解は主問題の下界値としての情報を与えてくれる．それでは双対問題の最適解であれば，どれだけよい主問題の下界値を与えてくれるだろうか．これは次の双対定理 ² ²弱双対定理との対比を強調して強双対定理とよぶこともある．にあるように，主問題の最適解を与えてくれる！

双対定理

主問題または双対問題の一方について最適解の存在が分かれば，もう一方の問題にも最適解が存在することが保証され，且つそれらの最適値 \(z^*\) は等しい．

(14)#\[z^* = \vec{c}^{\top}\vec{x}^* = \vec{b}^{\top}\vec{\omega}^*\]

証明

証明の前提としては (後述する主問題と双対問題の置き換えより) 次の主問題の最適基底解について示せば十分である．

(15)#\[\begin{split}\vec{x} = \begin{bmatrix} \vec{x}_B \\ \vec{x}_N \end{bmatrix} = \begin{bmatrix} B^{-1}\vec{b} \\ \vec{0} \end{bmatrix}\end{split}\]

最適基底解のとき単体乗数 \(\vec{\pi}=(B^{\top})^{-1}\vec{c}_B\) は相対費用係数 \(\vec{\gamma}\) が非負であるという最適性条件を満足している．

(16)#\[\vec{\gamma} = \vec{c}_N - N^{\top}\vec{\pi} \geq \vec{0}\]

従って単体乗数は次を満足する．

(17)#\[\begin{split}\left \{ \begin{array}{l} B^{\top}\vec{\pi} = \vec{c}_B \\ N^{\top}\vec{\pi} \leq \vec{c}_N \end{array} \right. \Rightarrow \begin{bmatrix} B \\ N \end{bmatrix} \vec{\pi} \leq \begin{bmatrix} \vec{c}_B \\ \vec{c}_N \end{bmatrix}\end{split}\]

これは即ち，次に他ならない．

(18)#\[A^{\top}\vec{\pi} \leq \vec{c}\]

つまり少なくとも単体乗数は双対問題 (4) の実行可能解だとわかる．

続けて最適基底解 \(\vec{x}^* = \begin{bmatrix} \vec{x}_B \\ \vec{x}_N \end{bmatrix} = \begin{bmatrix} B^{-1}\vec{b} \\ \vec{0} \end{bmatrix}\) について目的関数 \(f\) を評価すると次が得られる．

(19)#\[f(\vec{x}^*) = \vec{c}^{\top}\vec{x}^* = \vec{c}^{\top}_B B^{-1}\vec{b} = \vec{\pi}^{\top} \vec{b}\]

よって弱双対定理の系 2 から \(\vec{\pi}\) は双対問題の最適解である．

最後に \(\vec{c}^{\top}\vec{x}^* = \vec{\pi}^{\top} \vec{b}\) より，主問題の最小値 (最適値) は双対問題の最大値 (最適値) に等しい．

注釈

双対定理の証明からわかるように，単体乗数 \(\vec{\pi}\) は，基底行列 \(B\) が最適基底解のとき，双対問題の最適解 \(\vec{\omega}^*\) となることがわかる．

主問題と双対問題の間の関係を見てきた訳だが，詰まるところどちらの問題も，純粋な問題の構造というのはそう異なるものではない．そのためわざわざ双対問題という概念を持ち出したことに有難味を感じないかもしれない．しかしながら一連の命題はそうではないことを示唆している．

例えば最適値まで無理に要求しなかったとしても，ある程度実用的な解が欲しい場合には，弱双対定理が述べるように双対問題 (主問題) で得た目的関数の値が，主問題 (双対問題) について下限 (上限) として機能する．これはつまりある程度の解が望めることを意味している．

この他にも，後で双対変数が感度を論じる上で重要となることが明らかになる．また Lagrange の未定乗数法とも関係しており，様々な理論的な基礎を結び付けるのに重要な概念になっている．

4.5. 感度分析，潜在価格 #

双対問題は感度分析という観点で系を捉えるときに役立つ情報を与えてくれる．

感度分析

最適基底解を仮定した主問題で，次の摂動を加えたとする．

(25)#\[\vec{b} \mapsto \vec{b} + \Delta\vec{b}\]

このとき最適基底解 \(\vec{x}^* = \begin{bmatrix} \vec{x}^*_B \\ \vec{x}^*_N \end{bmatrix} = \begin{bmatrix} B^{-1}\vec{b} \\ \vec{0} \end{bmatrix}\geq\vec{0}\) や目的関数にどれほどの影響を与えるかを調べるのが 感度分析 (sensitivity analysis) である．このとき特に目的関数の変化の度合を感度 (sensitivity) という．

感度分析はまた事後分析 (post optimality analysis) ということもある．

以下に感度分析について述べ，感度を解析的に求めよう．

最適基底解 \(\vec{x}^*\) は摂動 \(\vec{b} \mapsto \vec{b} + \Delta\vec{b}\) に対して，次の変化を受ける．

(26)#\[\begin{split}\vec{x}^* \to \begin{bmatrix} B^{-1}(\vec{b}+\Delta\vec{b}) \\ \vec{0} \end{bmatrix}\end{split}\]

このとき \(B^{-1}(\vec{b}+\Delta\vec{b})\geq\vec{0}\) が成り立てば， \(B\) は再び最適基底行列である．

特に摂動を加える前で \(\vec{x}_B=B^{-1}\vec{b}>0\) で非退化であったならば，実数の連続性から \(B^{-1}(\vec{b}+\Delta\vec{b})\geq\vec{0}\) となる \(\Delta\vec{b}\) をいつでもとれて， \(B\) が最適基底行列であることを保証できる．以下，この場合を考え，この範囲で摂動を加えた (26) もまた最適解になっている．

最適性の議論を保証できたので，目的関数値の変化，感度について議論を続ける．

目的関数は \(f(\vec{x}) = \vec{c}^{\top}\vec{x}\) で，\(\vec{x}\) は制約条件 \(A\vec{x} = \vec{b}+\Delta\vec{b}\) を満たすものとなる．今，\(\vec{b}\) の摂動について目的関数の変化を見たいので， \(\vec{x}(\vec{b} + \Delta\vec{b})\) と摂動の関数として，次の関数 \(\phi\) に着目する．

(27)#\[f(\vec{x}) = \phi(\vec{b} + \Delta\vec{b}) = \vec{c}_B^{\top}\vec{x}(\vec{b} + \Delta\vec{b}) = \vec{c}_B^{\top} B^{-1}(\vec{b} + \Delta\vec{b})\]

するとこれから簡単な式変形を施して次が得られる．

(28)#\[\phi(\vec{b} + \Delta\vec{b}) - \phi(\vec{b}) = \phi(\Delta\vec{b}) = \vec{c}_B^{\top} B^{-1} \Delta\vec{b} = \vec{\pi}^{\top}\Delta\vec{b}\]

ここで最適解の状況を考えていることと，双対定理から単体乗数 \(\vec{\pi}\) は双対問題の最適解 \(\vec{\omega}^*\) に他ならなかったことから，結局，次が得られたことになる．

(29)#\[\phi(\vec{b} + \Delta\vec{b}) - \phi(\vec{b}) = (\vec{\omega}^*)^{\top}\Delta\vec{b} = \sum_{i=1}^m \omega^*_i \Delta b_i\]

よって各成分について \(\Delta b_i=db_i\) などと微分にとると，主線形項の評価から目的関数の変化の度合 (感度) として次が得られる．

(30)#\[\frac{\partial \phi}{\partial b_i}(\vec{b}) = \omega^*_i ~~ (i\in\{1,\ldots,m\})\]

故に双対変数 \(\vec{\omega}\) やその成分の絶対値がもし大き (小さ) ければ，目的関数の変化が鋭敏 (鈍感) であることがわかる．

換言すると，例えば \(\Delta b_i\) という摂動は \(i\) 番目の制約条件への摂動を表しているので，この制約条件が目的関数の変化に対して，どれだけ感度が良いかを双対問題の最適解の成分 \(\omega^*_i\) が担っていることになる．つまり，双対問題の最適解 \(\vec{w}^*\) は目的関数値の変化量を支配している価値ある量だとみなせて，潜在価格 (shadow price) とよばれている．

4.6. 被約費用 #

線形最適化問題の最適値 \(z^*\) が次のように求められていたとしよう．

(31)#\[z^* = \vec{c}^{\top}\vec{x}^* = \vec{b}^{\top}\vec{\omega}^*\]

ここで中辺は主問題として求めた最適値であり，最右辺は双対問題として求めた最適値である．

今，線形最適化問題を変形するという立場に立つとき，最適値 \(z^*\) は問題に表れる各係数 \(\vec{b},A,\vec{c}\) の関数 \(\phi\) とみなせる．

(32)#\[z^* = \phi(\vec{b},A,\vec{c})\]

さて主問題に対して新規に \(x_0\) という変数を一つ増やして，次の線形最適化問題へと変形することを考えてみよう．

(33)#\[\begin{split}& \mathrm{Minimize\colon}~ f(\vec{x},x_0) = \vec{c}^{\top}\vec{x} + c_0x_0 \\ & \mathrm{subject~to\colon}~ \\ & A\vec{x} = \vec{b} - \vec{A}_0x_0, \\ &\vec{x} \geq \vec{0}, \, x_0\geq0\end{split}\]

特に制約条件式の部分は，行列形式で書くと次のように整理できる．

(34)#\[\begin{split}\begin{bmatrix} A_{11} & A_{12} & \cdots & A_{1n} & (A_0)_1 \\ A_{21} & A_{22} & \cdots & A_{2n} & (A_0)_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ A_{m1} & A_{m2} & \cdots & A_{mn} & (A_0)_m \end{bmatrix} \begin{bmatrix} x_1 \\ \vdots \\ x_n \\ x_0 \end{bmatrix} = \begin{bmatrix} b_1 \\ \vdots \\ b_m \end{bmatrix}\end{split}\]

この変形は見方を変えると，変形前には \(x_0=0\) という問題だったのが，\(x_0>0\) という値を持つようになって，目的関数の最適値 \(z^*\) が次のように摂動を受けたとも見れる．

(35)#\[z^* = c_0x_0 + \phi(\vec{b} - \vec{A}_0x_0, A, \vec{c})\]

変数を追加することで最適値はどのような影響を受けたかを評価するために，次を計算しよう．

(36)#\[\frac{\partial z^*}{\partial x_0} = c_0 + \frac{\partial}{\partial x_0}((\vec{b} - \vec{A}_0x_0)^{\top}\vec{\omega}^*) = c_0 - \vec{A}_0^{\top}\vec{\omega}^* = \gamma_0^*\]

この結果から次のことがわかる．

\(\gamma_0^* = \partial z^*/\partial x_0\) は \((N,\vec{c}_N)=(\vec{A}_0,c_0)\) としたときの相対費用 (20) に他ならない．
評価結果の第一項は新たな変数に対するコスト \(c_0\) が計上されたもので直接的な影響である．(コストが正であることを踏まえて) 目的関数値が変形前よりも悪化することに直接寄与している．
評価結果の第二項は双対問題の最適解 (潜在価格) を通して影響している部分で，これは新たな変数が満たすべき制約条件からの抑制的にもなりえる影響である．

以上に述べた事柄は，変数を追加することでどれだけコストが増大してしまうかを評価していることから， \(\partial z^*/\partial x_0\) を変数 \(x_0\) の 被約費用 (reduced cost) または限界費用 (marginal cost) という ³ ³経済学の文脈で機会費用 (opportunity cost) の概念を線形最適化問題で説明するために，この名称を用いることもある．．

被約費用の他の性質を明らかにするために，変数を追加して変形した問題 (33) を主問題とするときの双対問題に着目しよう．

(37)#\[\begin{split}& \mathrm{Maximize\colon}~ \tilde{f}(\vec{\omega}) = \vec{b}^{\top}\vec{\omega} \\ & \mathrm{subject~to\colon}~ \\ & A^{\top}\vec{\omega} \leq \vec{c}, \\ & \vec{A}_0^{\top}\vec{\omega} \leq c_0\end{split}\]

主問題への変数の追加は，双対問題では制約条件式 \(\vec{A}_0^{\top}\vec{\omega} \leq c_0\) の追加と対応している．追加された制約条件式は次のように整理できる．

(38)#\[\gamma_0 = c_0 - \vec{A}_0^{\top}\vec{\omega} \geq 0\]

最適解は当然ながら，実行可能解もこの制約条件式を満たさなければならないが，そのことが今，被約費用 \(\gamma_0\) が非負であることを意味していることに対応しているとわかる．そうでない場合，つまり被約費用 \(\gamma_0\) が負の場合には，実行不可能であることを意味する．主問題だけでは被約費用が非負かどうかについて，その意味が直ちに明らかとは言えないものであったが，双対問題を通して明瞭に意味を捉えられるというわけである．

以上に述べた性質は列生成法という技法の基礎を与えてくれる．

4.7. 主双対最適性条件，相補性条件 #

双対問題の理論的な理解を深めるために，一度，次に与えられた問題の双対問題を求める方法について具体例を通してみておく．

主問題として次の問題が所与だとする．

(39)#\[\begin{split}& \mathrm{Minimize\colon}~ f(\vec{x}) = \vec{c}^{\top}\vec{x} \\ & \mathrm{subject~to\colon}~ \\ & A\vec{x} \geq \vec{b}, \\ &\vec{x} \geq \vec{0}\end{split}\]

これの双対問題を求める．まず主問題を標準形に直そう．標準形の制約条件は等号条件だったから，スラック変数 \(\vec{s}=A\vec{x}-\vec{b}(\geq\vec{0})\) を導入して次のように制約条件を標準形に帰着させる．

(40)#\[A\vec{x} - \vec{s} = \vec{b}\]

このままでは帰着されたことがややわかりにくいので，次のように変形しておく．但し \(\mathbf{1}\) は単位行列である．

(41)#\[\begin{split}\begin{bmatrix} A & -\mathbf{1} \end{bmatrix} \begin{bmatrix} \vec{x} \\ \vec{s} \end{bmatrix} = \vec{b}\end{split}\]

ここで主問題の標準形 (3) を再掲しよう．

(42)#\[\begin{split}& \mathrm{Minimize\colon}~ f(\vec{x}) = \vec{c}^{\top}\vec{x} \\ & \mathrm{subject~to\colon}~ \\ & A\vec{x} = \vec{b}, \\ &\vec{x} \geq \vec{0}\end{split}\]

すると，今の書き換えとは次の対応 (\(\cong\)) があることを述べている．

(43)#\[\begin{split}A &\cong \begin{bmatrix} A & -\mathbf{1} \end{bmatrix}, \\ \vec{x} &\cong \begin{bmatrix} \vec{x} \\ \vec{s} \end{bmatrix}, \\ \vec{b} &\cong \vec{b}, \\ \vec{c} &\cong \begin{bmatrix} \vec{c} \\ \vec{0} \end{bmatrix}\end{split}\]

よってこの対応を元に双対問題を求めれば，次の問題だとわかる．

(44)#\[\begin{split}& \mathrm{Maximize\colon}~ \tilde{f}(\vec{\omega}) = \vec{b}^{\top}\vec{\omega} \\ & \mathrm{subject~to\colon}~ \\ & \begin{bmatrix} A^{\top} \\ -\mathbf{1} \end{bmatrix} \vec{\omega} \leq \begin{bmatrix} \vec{c} \\ \vec{0} \end{bmatrix} \Leftrightarrow A^{\top}\vec{\omega} \leq \vec{c},~ \vec{\omega} \geq \vec{0}\end{split}\]

以上に述べてきた線形最適化問題の双対性に着目して，線形最適化問題を主双対最適性条件という形で書き直そう．

始めに双対定理を次の主問題と双対問題について適用しよう．

主問題

(45)#\[\begin{split}& \mathrm{Minimize\colon}~ f(\vec{x}) = \vec{c}^{\top}\vec{x} \\ & \mathrm{subject~to\colon}~ \\ & A\vec{x} = \vec{b}, \\ &\vec{x} \geq \vec{0}\end{split}\]

双対問題

(46)#\[\begin{split}& \mathrm{Maximize\colon}~ \tilde{f}(\vec{\omega}) = \vec{b}^{\top}\vec{\omega} \\ & \mathrm{subject~to\colon}~ \\ & A^{\top}\vec{\omega} + \vec{s} = \vec{c}, \\ & \vec{s} \geq \vec{0}\end{split}\]

このときそれぞれの最適解が \(\vec{x},\vec{\omega}\) であるならば，双対定理によって次の一連の関係式が，\(\vec{x},\vec{\omega},\vec{s}\) の間に成り立つ．

(47)#\[\begin{split}\left \{ \begin{array}{l} \vec{c}^{\top}\vec{x} = \vec{b}^{\top}\vec{\omega}, \\ A\vec{x} = \vec{b}, \\ A^{\top}\vec{\omega} + \vec{s} = \vec{c}, \\ \vec{x} \geq \vec{0}, \\ \vec{s} \geq \vec{0} \end{array} \right.\end{split}\]

ここで第一関係式 \(\vec{c}^{\top}\vec{x} = \vec{b}^{\top}\vec{\omega}\) は第二および第三関係式を用いて次の式に書き直すことができる．

(48)#\[\vec{s}^{\top}\vec{x} = 0\]

この関係式の右辺は別にこのままでもよいが，この業界ではしばしば， \(\vec{x} \geq \vec{0}\) 且つ \(\vec{s} \geq \vec{0}\) のときに，

(49)#\[\vec{s}^{\top}\vec{x} = 0 \Leftrightarrow s_ix_i = 0 ~~ (\forall i \in \{1,\ldots,n\})\]

であることを用いて，等価な関係式をベクトル形式で次のように書き直す．但し \(K_1,\ldots,K_n\) を対角成分にもつ対角行列を \(\operatorname{Diag}(K_1,\ldots,K_n)\) で表し，すべての成分が \(1\) のベクトル (all-ones vector) を \(\vec{1}\) で表した．

(50)#\[\operatorname{Diag}(x_1,\ldots,x_n)\operatorname{Diag}(s_1,\ldots,s_n)\vec{1} = \vec{0}\]

このように書き直したとき，この関係式を 相補性条件 (complementarity condition) ⁴ ⁴相補性条件は非線形方程式であることに注意せよ．主双対問題では主問題の変数 \(\vec{x}\) と双対問題の変数 \(\vec{\omega},\vec{s}\) の両方が系の変数となるからである．とよぶ．名前の由来は \(s_ix_i=0\) より，少なくとも \(s_i,x_i\) の何れかが \(0\) であることが確定するが，そのもう一方は不定となる相補性を有していることからきている．

以上により双対定理から次の条件がまとめられた．

(51)#\[\begin{split}\left \{ \begin{array}{l} \operatorname{Diag}(\vec{x})\operatorname{Diag}(\vec{s})\vec{1} = \vec{0}, \\ A\vec{x} = \vec{b}, \\ A^{\top}\vec{\omega} + \vec{s} = \vec{c}, \\ \vec{x} \geq \vec{0}, \, \vec{s} \geq \vec{0} \end{array} \right.\end{split}\]

これらを満たす \(\vec{x},\vec{\omega},\vec{s}\) を求めれば，主問題および双対問題の最適解が得られることになる．このことから (51) を線形最適化問題に対する 主双対最適性条件 (primal-dual optimization conditions) という．

しかしながら (51) そのものを解くことは困難である．相補性条件からそのような領域しか解を探索できないからである．この問題はパス追跡法という内点法によって打開される．

4.8. Lagrange の未定乗数法 #

Lagrange の未定乗数法は双対問題を通して，次のように理解することもできる．

線形最適化問題についての双対変数と Lagrange の未定乗数

制約条件付き極値問題に対する Lagrange の未定乗数は，制約条件付き極値問題を主問題と見たときの双対問題に対する双対変数に他ならない．

証明

主問題の標準形について \(\vec{x}\) を適当な実行可能解だとするとき，次の量 (目的関数) に着目する．

(52)#\[\begin{split}\min_{\substack{A\vec{x}=\vec{b},\\ \vec{x}\geq\vec{0}}} \vec{c}^{\top}\vec{x}\end{split}\]

この量の最良の下限，つまり主問題についての最適値を Lagrange の未定乗数法に従って求めたいとする．

制約条件は \(A\vec{x}=\vec{b}\) と \(\vec{x}\geq\vec{0}\) の二種だから，それぞれで Lagrange の未定乗数を \(\vec{\omega}(\geq\vec{0})\) および \(\vec{s}(\geq\vec{0})\) とすると，次が成立する．

(53)#\[\begin{split}\min_{\substack{A\vec{x}=\vec{b},\\ \vec{x}\geq\vec{0}}} \vec{c}^{\top}\vec{x} \geq \min_{\vec{x} \in \mathbb{R}^n} [ \vec{c}^{\top}\vec{x} - \vec{\omega}^{\top} (A\vec{x}-\vec{b}) - \vec{s}^{\top} \vec{x}] = \min_{\vec{x} \in \mathbb{R}^n} [ (\vec{c} - A^{\top}\vec{\omega} - \vec{s})\vec{x} + \vec{\omega}^{\top} \vec{b}]\end{split}\]

よって，

(54)#\[\begin{split}\min_{\substack{A\vec{x}=\vec{b},\\ \vec{x}\geq\vec{0}}} \vec{c}^{\top}\vec{x} \geq \max_{\vec{s}\geq\vec{0}}\min_{\vec{x} \in \mathbb{R}^n} [ (\vec{c} - A^{\top}\vec{\omega} - \vec{s})\vec{x} + \vec{\omega}^{\top} \vec{b}]\end{split}\]

を考えるとき，

(55)#\[\vec{c} - A^{\top}\vec{\omega} - \vec{s} = \vec{0} \Leftrightarrow A^{\top}\vec{\omega} + \vec{s} = \vec{c}\]

だとわかる．これは双対問題の制約条件に他ならない．そしてこのとき，

(56)#\[\begin{split}\min_{\substack{A\vec{x}=\vec{b},\\ \vec{x}\geq\vec{0}}} \vec{c}^{\top}\vec{x} \geq \max_{\vec{s}\geq\vec{0}} \vec{\omega}^{\top} \vec{b}\end{split}\]

である．

それ故，Lagrangeの未定乗数が双対変数に他ならないことがわかる．

線形最適化問題の双対性

目次