LoginSignup
16

More than 5 years have passed since last update.

双対問題を調べる

Last updated at Posted at 2016-03-27

はじめに

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

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

  • どちらかが最適解を持つならば、両方とも最適解を持ち、その最適値は一致する。
  • 双対問題の双対問題は主問題となる。
  • 双対定理が成り立つ。(参考: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だとお手軽にできます1。準備として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のテクニックを使っています。 

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
16