双対問題 2011 年度 OR 概論 (大学院) 担当：佐々木美裕以下では，A は m × n 行列，I は m 次単位行列，c, x は n 次元ベクトル，b, y, w は m 次元ベクトル，0 は n 次元零ベクトルとする． 1 標準形の双対問題標準形の線形計画問題 (P) minimize c⊤ x s.t. Ax = b x≥0 に対する双対問題 (D) は，等式制約に関する双対変数ベクトル w を用いて次のように書ける． (D) maximize b⊤ w A⊤ w ≤ c s.t. 標準形以外の問題でも標準形に変形することにより双対問題を求めることができる．たとえば， (P1 ) minimize c⊤ x s.t. Ax ≥ b x≥0 を標準形に変形すると minimize c⊤ x Ax − y = b s.t. x ≥ 0, y ≥ 0 となる．これは minimize c⊤ x + 0⊤ y Ax − Iy = b s.t. x ≥ 0, y ≥ 0 と等価であり，係数行列およびコストベクトルの対応付けに気をつけると，双対問題は maximize b⊤ w s.t. A⊤ w ≤ c −I ⊤ w ≤ 0 と書ける．これを整理して，(P1 ) の双対問題 (D1 ) maximize b⊤ w A⊤ w ≤ c s.t. w≥0 を得る． 1 2 ラグランジュ緩和を用いた双対問題の導出はじめに，ラグランジュ緩和を用いて (P1 ) の双対問題を導出する方法を説明する．制約条件 Ax ≥ b を緩和して得られる次のラグランジュ緩和問題 (LP1 ) を考える． (LP1 ) minimize c⊤ x + w⊤ (b − Ax) s.t. x≥0 (P1 ) の実行可能解は (LP1 ) の実行可能解であり，任意の w ≥ 0 に対して (LP1 ) の最適値 ≤ (P1 ) の最適値が成立している．すなわち，(LP1 ) の最適値は (P1 ) の最適値の下界となる．なぜなら，w ≥ 0 であり，(P1 ) の実行可能解においては b − Ax ≤ 0 が成立しているので，w⊤ (b − Ax) ≤ 0 となるからである． (P1 ) は最小化問題であるので，その最適値になるべく近い値，すなわちなるべく大きな下界に興味がある．そこで，最大の下界を与える最良の w を求めるにはどうしたらよいかを考える．(LP1 ) の目的関数を x についてまとめると， (c⊤ − w⊤ A)x + w⊤ b (1) となる．もし，x の係数ベクトル c⊤ − w⊤ A の要素の中で 1 つでも負のものがあると，対応する x の要素を大きくすることにより目的関数値をどれだけでも小さくすることができる．これは，(LP1 ) が非有界で最適値を持たないことを示している．(LP1 ) が有界で最適値を持つためには，c⊤ − w⊤ A ≥ 0⊤ , すなわち， A⊤ w ≤ c (2) という条件が必要である．以上により，最良な w を求めるラグランジュ双対問題は，w ≥ 0 と (2) の制約のもと w⊤ b を最大化する問題として定式化できる．これは，前述の (D1 ) に他ならない．同様に (P) の双対問題を導出する．制約条件 Ax = b を緩和して得られる次のラグランジュ緩和問題 (LP) を考える． (LP) minimize c⊤ x + w⊤ (b − Ax) s.t. x≥0 (P) の実行可能解は (LP) の実行可能解であり，任意の w に対して (LP) の最適値 ≤ (P) の最適値が成立している．ここで，w には符号制約がないことに注意する．上記と同様の理由により，(LP) が有界で最適値を持つためには，制約条件 (2) が必要である．したがって，最良の w を求める問題は，(2) の制約のもと w⊤ b を最大化する問題として定式化できる．これは，前述の (D) に他ならない． (D) と (D1 ) を比べると，その違いは，(ラグランジュ) 双対変数に非負制約がついているか否かである．ラグランジュ緩和を用いた双対問題の導出過程から明らかなように，等式制約に関する双対変数には非負制約が不要で，不等式制約に関する双対変数には非負制約が必要である．以下の問題 (制約) に関する双対問題はどうなるか，考えてみるとよい． • 不等号の向きが逆 (≤) である不等式制約を含む問題． • 符号制約がない変数を含む問題． • 非正制約のある変数を含む問題． 2