凸最適化・組合せ最適化の問題

ステップ 1: 双対問題を書き下す

「$\max c^{\top }x$, $Ax\le b$, $x\ge 0$」の双対問題は「$\min b^{\top }y$, $A^{\top }y\ge c$, $y\ge 0$」である。ここでは $c=(2,3{)}^{\top }$, $b=(4,6{)}^{\top }$, $A=\left(\begin{array}{cc}1& 1\\ 1& 3\end{array}\right)$ なので、(D) は
$$\begin{array}{rl}\text{minimize}& 4y_1+6y_2\\ \text{subject to}& y_1+y_2\ge 2,\\ & y_1+3y_2\ge 3,\\ & y_1\ge 0,y_2\ge 0\end{array}$$
となる。

ステップ 2: 相補性条件を使う

主・双対の実行可能解 $x$, $y$ がともに最適であるための条件（相補性条件）は
- $x_j>0$ ならば (D) の $j$ 番目の制約は等号で成り立つ
- $y_i>0$ ならば (P) の $i$ 番目の制約は等号で成り立つ

である。(P) の最適解 $x=(3,1)$ では $x_1=3>0$, $x_2=1>0$ なので、(D) の 2 つの制約はどちらも等号で成り立つ:
$$y_1+y_2=2,y_1+3y_2=3.$$
2 式目から 1 式目を引くと $2y_2=1$、よって $y_2=\frac{1}{2}$, $y_1=\frac{3}{2}$。

ステップ 3: 確認

$y=\left(\frac{3}{2},\frac{1}{2}\right)$ は $y\ge 0$ を満たすので (D) の実行可能解である。(P) の制約も $3+1=4$, $3+3=6$ とどちらも等号なので、$y_i>0$ に対する相補性条件も満たされる。目的関数の値は
$$4\cdot \frac{3}{2}+6\cdot \frac{1}{2}=6+3=9,2\cdot 3+3\cdot 1=9$$
で一致する。弱双対性より (D) のどの実行可能解の値も (P) の最適値 $9$ 以上なので、値 $9$ をとる $y$ は (D) の最適解である。また、等式 $y_1+y_2=2$, $y_1+3y_2=3$ の解はただ 1 つなので、最適解は一意である。

よって (D) の最適解は $(y_1,y_2)=\left(\frac{3}{2},\frac{1}{2}\right)$ である。

双対問題 (D) は
$$\text{minimize}4y_1+6y_2\text{subject to}{y}_1+y_2\ge 2,y_1+3y_2\ge 3,y_1\ge 0,y_2\ge 0.$$
主問題の最適解 $(x_1,x_2)=(3,1)$ では $x_1>0,x_2>0$ なので、相補性条件より双対の第 1, 第 2 制約は等号で成り立つ:
$y_1+y_2=2$, $y_1+3y_2=3$。
辺々引いて $2y_2=1$、$y_2=\frac{1}{2}$、$y_1=\frac{3}{2}$。

検算: $y_1,y_2\ge 0$ を満たす。主問題の制約は $3+1=4$, $3+3\cdot 1=6$ でともに等号なので、$y_1,y_2$ に関する相補性条件も成り立つ。主問題の目的関数値は $2\cdot 3+3\cdot 1=9$、双対の目的関数値は $4\cdot \frac{3}{2}+6\cdot \frac{1}{2}=6+3=9$ で一致する。よって $(y_1,y_2)=\left(\frac{3}{2},\frac{1}{2}\right)$ が (D) の最適解。