数理最適化（双対問題と双対定理①）

今回は双対定理についてまとめていきます。
最適化問題でよく登場してきます。

相対問題とは

主問題（元の解くべき問題）に対し、新たに定義した表裏の関係にある問題のことを双対問題と呼びます。

主問題が以下の場合を考えます。

目的関数

$$
最大化    c^{\top}x
$$

制約条件

$$
ax \leq b\\
x \geq 0
$$

これの、双対問題は、以下となります。

目的関数

$$
最小化    b^{\top}y
$$

制約条件

$$
a^{\top}y \geq c\\
y \geq 0
$$

これを解説していきます。
以下のように、主問題をもう少し細かく表現していみます。

目的関数

$$
最大化    c_1x_1 + c_2x_2 + ・・・ + c_nx_n
$$

制約条件

$$
a_{11}x_{1} + a_{12}x_{2} + ・・・ + a_{1n}x_{n} \leq b_1\\
a_{21}x_{1} + a_{22}x_{2} + ・・・ + a_{2n}x_{n} \leq b_2\\
・・・\\
a_{m1}x_{1} + a_{m2}x_{2} + ・・・ + a_{mn}x_{n} \leq b_m\\
x \geq 0
$$

双対問題へは、以下の手順で変換します。

1. 最大化と最小化を入れ替える

2. c と b を 入れ替える

3. x を y に 置き換える

4. 制約条件の不等式の大小を置き換える

5. 不等式の係数を転置する：Xmn → Xnm 

この手順で変換したのが以下となります。

目的関数

$$
最小化    b_1y_1 + b_2y_2 + ・・・ + b_my_m
$$

制約条件

$$
a_{11}y_{1} + a_{21}y_{2} + ・・・ + a_{m1}y_{m} \geq c_1\\
a_{12}y_{1} + a_{22}y_{2} + ・・・ + a_{m2}y_{m} \geq c_2\\
・・・\\
a_{1n}y_{1} + a_{2n}y_{2} + ・・・ + a_{mn}y_{m} \geq c_n\\
y \geq 0
$$

なぜこの変換方法なのかというと、行列で考えた時に、元の問題を裏返しにした表現だからです。
そのため、この双対問題をさらに裏返すと、元の問題に戻ります。
元の問題も、双対問題も、最適値は同じになります。

相対定理

• 主問題とその双対問題がともに許容解を持つならば、それぞれの問題に目的関数の値が有限な値を持つ最適解が存在する。また、その時それらの最適解での目的関数の値が互いに一致する。

• 主問題が非有界ならば、双対問題に許容解が存在しない。

• 双対問題が非有界ならば、主問題に許容解が存在しない。

なぜ双対問題が必要なのか

以下のような理由で、双対問題を使用します。

• 計算効率の向上や最適解を求めることが困難な問題を解くため

• 算出した実行可能解が最適解かどうかを確認するため

主問題が多数の変数を持つが制約が少ない場合、双対問題はより少ない変数を持つことが多く、解が簡単になることがあります。
数理最適化の目的は「最適解を求めること」ですが、実際の問題では、最適解を求めることが難しい場合もあります。
その場合は、最適値の上界と下界を求めることが重要になります。
　※最適解と最適値の違いは後で説明
また、最適解を求められる場合でも、求めた実行可能解が最適かどうかを確かめるときに使用します。

最適解と最適値

以下のような最小化問題を例にして説明します。

目的関数

$$
min    z=3x+4y
$$

制約条件

$$
x+2y≥8\\
4x+2y≤14\\
x,y≥0
$$

x とy は変数です。
この問題の解を求めるために調整します。
仮に、この問題の最適解が x=2、y=3 であるとします。
このとき、これらの値はすべての制約を満たし、目的関数を最小化します。

最適解

この例では、x=2、y=3 が最適解です。
これは、問題を解決するための具体的な変数の値の組み合わせを示します。

最適値

これは、最適解における目的関数の値を示します。
この例での最適値は、最適解を適用したときの z の値です。
つまり、
　　z=3(2)+4(3)=6+12=18
18が最適値となります。

次回は具体的に双対問題を解いていきたいと思います。