双対問題と双対定理

主問題 $max c^{⊤} x$ , $A x \leq b$ , $x \geq 0$ から双対問題 $min b^{⊤} y$ , $A^{⊤} y \geq c$ , $y \geq 0$ を作れる。弱双対性 $c^{⊤} x \leq b^{⊤} y$ で最適値を上下から挟み、強双対定理で両者の最適値が一致することを使って、最適値や最適性を確かめられる

前提

線形計画問題の定式化と標準形（大学数学最適化・線形計画法）

この技能までの道筋（48 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

三角形の角の大きさ（算数平面図形）
対頂角と平行線の同位角・錯角（中学数学平面図形）
三角形の外角と角の組み合わせ（中学数学平面図形）
小数の四則計算（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
分数のかけ算・わり算（算数計算と数のきまり）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
1 次方程式の解き方（中学数学方程式）
二等辺三角形の角（中学数学平面図形）
平行四辺形と特別な四角形の性質（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
三平方の定理（中学数学相似と三平方の定理）
乗法公式による展開（中学数学数と式）
折り返した図形の角と長さ（中学数学平面図形）
三平方の定理と平面図形（中学数学相似と三平方の定理）
最大公約数と最小公倍数（算数整数の性質）
比の性質と簡単な比（算数割合と比）
相似な三角形と長さの比（算数平面図形）
三角形の相似条件と対応する辺の長さ（中学数学相似と三平方の定理）
平行線と線分の比（中学数学相似と三平方の定理）
2点間の距離と内分点・外分点（数学II 図形と方程式）
比例・反比例の式とグラフ（中学数学関数）
関数 $y = a x^{2}$ の式と変域（中学数学関数）
因数分解（中学数学数と式）
平方完成と 2 次関数のグラフ（数学I 2次関数）
円の方程式（数学II 図形と方程式）
連立方程式の解き方（加減法・代入法）（中学数学方程式）
1 次関数の式の求め方（中学数学関数）
直線の方程式（数学II 図形と方程式）
不等式の表す領域（数学II 図形と方程式）
点と直線の距離（数学II 図形と方程式）
2 次不等式（数学I 2次関数）
円と直線の位置関係と弦の長さ（数学II 図形と方程式）
2直線の平行・垂直（数学II 図形と方程式）
円の接線（数学II 図形と方程式）
領域における最大・最小（数学II 図形と方程式）
ベクトルの演算と成分（数学C ベクトル）
行列の和・積と 2 次の逆行列（大学数学線形代数）
線形計画問題の定式化と標準形（大学数学最適化・線形計画法）

説明

最大化の線形計画問題（主問題）から、係数を入れ替えた最小化の問題（双対問題）を作る技能です。主問題の実行可能解は最適値の下からの評価を、双対問題の実行可能解は上からの評価を与えます。両者の目的関数値が一致する組を見つければ、両方が最適だと確定できます。図が描けない多変数の問題でも、ある解が本当に最適かを数値の計算だけで確かめられます。

なぜそうしてよいのか

主問題を $max c^{⊤} x$ , $A x \leq b$ , $x \geq 0$ （ $A$ は $m \times n$ 行列）とします。目的関数の値に上限を付けたいとき、各制約式 $(A x)_{i} \leq b_{i}$ に 0 以上の数 $y_{i}$ を掛けて足し合わせると $y^{⊤} A x \leq y^{⊤} b$ が得られます。不等式の向きを保つには $y \geq 0$ でなければなりません。さらに左辺 $y^{⊤} A x = (A^{⊤} y)^{⊤} x$ の $x_{j}$ の係数が、どれも $c_{j}$ 以上（ $A^{⊤} y \geq c$ ）であるとします。すると $x \geq 0$ から $c^{⊤} x \leq (A^{⊤} y)^{⊤} x$ が成り立ちます。まとめると次のようになります。 $c^{⊤} x \leq (A^{⊤} y)^{⊤} x = y^{⊤} A x \leq y^{⊤} b = b^{⊤} y$ これが弱双対性です。主問題の実行可能解 $x$ と、 $A^{⊤} y \geq c$ , $y \geq 0$ を満たす $y$ なら、どの組でもこの不等式が成り立ちます。

こうして作れる上限 $b^{⊤} y$ のうち、いちばん小さいものを求める問題が双対問題 $min b^{⊤} y$ , $A^{⊤} y \geq c$ , $y \geq 0$ です。弱双対性から、主問題の最適値は双対問題の最適値以下です。したがって、主問題の実行可能解 $x^{*}$ と双対問題の実行可能解 $y^{*}$ で $c^{⊤} x^{*} = b^{⊤} y^{*}$ となる組が見つかれば、次のことがわかります。どんな実行可能解 $x$ も $c^{⊤} x \leq b^{⊤} y^{*} = c^{⊤} x^{*}$ を満たすので $x^{*}$ は最適解です。同様に $y^{*}$ も最適解で、その値が最適値です。

強双対定理は、そのような組がいつも存在することを保証します。主問題が最適解をもてば双対問題も最適解をもち、両者の最適値は一致します。なお、主問題の目的関数がいくらでも大きくなる（非有界な）場合、弱双対性から双対問題には実行可能解がありません。

手順

主問題を $max c^{⊤} x$ , $A x \leq b$ , $x \geq 0$ の形にそろえ、 $A, b, c$ を読み取る（ $\geq$ の制約は両辺に $- 1$ を掛けて $\leq$ に直す）。
双対変数 $y = (y_{1}, \dots, y_{m})$ を制約式 1 本につき 1 つ用意し、双対問題 $min b^{⊤} y$ , $A^{⊤} y \geq c$ , $y \geq 0$ を書く。 $A$ の第 $j$ 列が、双対の第 $j$ 制約の係数になる。
主問題の実行可能解 $x^{*}$ を 1 つ見つける（候補として、いくつかの制約を等号にした連立方程式の解を使う）。すべての制約と $x^{*} \geq 0$ を満たすか確かめる。
双対問題の実行可能解 $y^{*}$ を 1 つ見つける（候補として、双対の制約を等号にした連立方程式の解を使う）。 $A^{⊤} y^{*} \geq c$ と $y^{*} \geq 0$ を満たすか確かめる。
弱双対性から $c^{⊤} x^{*} \leq (最適値) \leq b^{⊤} y^{*}$ と挟む。両辺が等しければ、その値が最適値であり、 $x^{*}$ , $y^{*}$ はそれぞれの問題の最適解である。

例題

線形計画問題 $max 3 x_{1} + 5 x_{2}$ , 制約 $x_{1} + x_{2} \leq 4$ , $x_{1} + 3 x_{2} \leq 6$ , $x_{1} \geq 0$ , $x_{2} \geq 0$ の最適値を、双対問題を用いて求めよ。

例題の解答

【手順1】主問題は $A = (1113)$ , $b = (46)$ , $c = (35)$ の形になっている。

【手順2】双対問題は $min 4 y_{1} + 6 y_{2}$ , 制約 $y_{1} + y_{2} \geq 3$ , $y_{1} + 3 y_{2} \geq 5$ , $y_{1} \geq 0$ , $y_{2} \geq 0$ である。この例では $A^{⊤} = A$ となる。

【手順3】主問題の 2 つの制約を等号にして $x_{1} + x_{2} = 4$ , $x_{1} + 3 x_{2} = 6$ を解く。辺々引くと $2 x_{2} = 2$ となり、 $x_{2} = 1$ , $x_{1} = 3$ を得る。 $x^{*} = (3, 1)$ は $x^{*} \geq 0$ を満たし、2 つの制約も等号で満たすので実行可能である。目的関数の値は $3 \cdot 3 + 5 \cdot 1 = 14$ である。

【手順4】双対の 2 つの制約を等号にして $y_{1} + y_{2} = 3$ , $y_{1} + 3 y_{2} = 5$ を解く。 $2 y_{2} = 2$ より $y_{2} = 1$ , $y_{1} = 2$ を得る。 $y^{*} = (2, 1)$ は $y^{*} \geq 0$ を満たし、制約も満たすので実行可能である。目的関数の値は $4 \cdot 2 + 6 \cdot 1 = 14$ である。

【手順5】弱双対性より、主問題の最適値 $M$ について $14 = c^{⊤} x^{*} \leq M \leq b^{⊤} y^{*} = 14$ が成り立つ。よって $M = 14$ であり、 $x^{*} = (3, 1)$ が最適解である。

答え: $14$

よくある誤り

双対の制約を $A y \geq c$ と、転置せずに作ってしまう誤り。正しくは $A^{⊤} y \geq c$ で、 $A$ の列が双対の各制約になる。例えば $A = (1324)$ なら、双対の第 1 制約は $y_{1} + 3 y_{2} \geq c_{1}$ であり、 $y_{1} + 2 y_{2} \geq c_{1}$ ではない。
双対の制約の向きを $A^{⊤} y \leq c$ としたり、 $y \geq 0$ を落としたりする誤り。正しくは $A^{⊤} y \geq c$ かつ $y \geq 0$ である。 $y_{i} < 0$ を許すと、制約に掛けたときに不等式の向きが逆転し、 $y^{⊤} A x \leq y^{⊤} b$ が成り立たなくなる。
候補の $x^{*}$ や $y^{*}$ が実行可能かを確かめずに値を比べてしまう誤り。連立方程式の解が負の成分をもったり、他の制約を破ったりすることがある。弱双対性 $c^{⊤} x \leq b^{⊤} y$ は、 $x$ と $y$ が両方とも実行可能なときにしか使えない。
主問題が $\geq$ の制約（例: $x_{1} + x_{2} \geq 2$ ）を含むのに、そのまま $b_{i} = 2$ として双対を作る誤り。正しくは $- x_{1} - x_{2} \leq - 2$ に直してから $A$ と $b$ を読み取る。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること

相補性条件（大学数学最適化・線形計画法）