双対問題を調べる

はじめに

最適化では、元の問題(主問題)に対して、双対問題というものを考えることができます。

双対問題は、以下のような重要な性質があります。

• どちらかが最適解を持つならば、両方とも最適解を持ち、その最適値は一致する。
• 双対問題の双対問題は主問題となる。
• 双対定理が成り立つ。(参考:wikipedia)

主問題と双対問題の例をあげます。

主問題		双対問題
$ \min{~ c^T x} $		$ \max{~ b^T y} $
$ A x \ge b $		$ A^T y \le c $
$ x \ge 0 $		$ y \ge 0 $

いろいろな主問題の双対問題が、すぐわかるPython3のパッケージ(dual)を作ったので、ご紹介します。

インストール

bash

pip install dual

試してみる

例を見てみましょう。

bash

python -m dual << EOF
min c^T x
A x >= b
x >= 0
EOF
>>>
max b^T y
A^T y <= c
y >= 0

合っていますね。

双対問題を与えると、主問題になります。

bash

python -m dual << EOF
max b^T y
A^T y <= c
y >= 0
EOF
>>>
min c^T x
A x >= b
x >= 0

制約条件の不等号を等号に変えると、yが自由変数になります。

bash

python -m dual << EOF
min c^T x
A x = b
x >= 0
EOF
>>>
max b^T y
A^T y <= c

xを自由変数にすると、双対問題の制約条件が等号になります。

bash

python -m dual << EOF
min c^T x
A x >= b
EOF
>>>
max b^T y
A^T y = c
y >= 0

少し複雑にしてみましょう。

bash

python -m dual << EOF
min c^T x + d^T z
A x - P z >= b
Q z <= f
x >= 0
EOF
>>>
max b^T y - f^T w
A^T y <= c
- P^T y - Q^T w = d
y >= 0
w >= 0

同じように双対問題を与えると主問題に戻ります。

bash

python -m dual << EOF
max b^T y - f^T w
A^T y <= c
- P^T y - Q^T w = d
y >= 0
w >= 0
EOF
>>>
min c^T x + d^T z
-Q z >= -f
A x - P z >= b
x >= 0

Jupyterでお手軽に

Jupyterだとお手軽にできます¹。準備としてimport します。

jupyter_notebook

import dual

実行してみます。

jupyter_notebook

%%dual
min c^T x
A x >= b
x >= 0
>>>
max b^T y
A^T y <= c
y >= 0

以上

1. Jupyterの小技2のテクニックを使っています。 ↩