読者です 読者をやめる 読者になる 読者になる

MyEnigma

とあるエンジニアのブログです。#Robotics #Programing #C++ #Python #MATLAB #Vim #Mathematics #Book #Movie #Traveling #Mac #iPhone

最適化問題における双対問題とは?

経済数学入門16:線型計画法(双対性)

経済数学入門16:線型計画法(双対性)

目次

はじめに

最適化問題を勉強していると、

双対問題[そうついもんだい] (dual problem)という言葉が出てきます。

 

実は最近の凸最適化のソルバーなどが、

高速に問題を解けるようになったのは、

この双対問題という考えを使うことにより、

実現していることが多いようです。

 

今回、この双対問題の概要と、

なぜ双対問題を考えると、

最適化を解きやすくなるのかを

紹介したいと思います。

 

双対問題とは?

双対問題はある最適化問題(主問題)に対して、

補集合になる最適化問題のことを指します。

 

例えば、下記のような線形計画問題の場合、

f:id:meison_amsl:20170130074336p:plain

その双対問題は、下記のような問題を指します。

f:id:meison_amsl:20170130074509p:plain

 

このような双対問題は、

基本的にすべての最適化問題に存在するのですが、

複雑な最適化問題の双対問題は、上記のように

あまり式の対称性が無いものもあります。

例えば、下記の最適化問題において、

f:id:meison_amsl:20170130074139p:plain

その双対問題は下記のようになります。

f:id:meison_amsl:20170130074958p:plain

 

なぜ双対問題を考えるのか?

なぜ、この双対問題を考えるかといいますと、

この双対問題を考えることで、

対象の最適化問題を簡単に解くことができることが

多いためです。

 

例えば、上記の双対問題には、

下記の双対定理という定理が成り立ちます。

 

双対定理(英: duality theorem)

主問題と双対問題のいずれか一方が最適解を持つなら、

もう一方も最適解を持ち、主問題の最小値と双対問題の最大値は一致する。

 

つまり、解きたい主問題の最適値を計算するのが難しい時、

その双対問題を解くことで、主問題を解くことができることがあります。

(ちなみに相対問題を解くと、主問題も解くことができるのは、

線形計画法のみのようです)

例えば、主問題の変数がたくさんあり、制約条件が少ない問題の場合、

双対問題の方が変数が少なくできます。

すると、主問題より楽に解ける可能性が高いのです。

 

また、もう一つのメリットとしては、

最適性の簡単な証拠を提示できるというのがあります。

ある最適化問題の結果が、本当に最適値かどうかを確認する際に、

上記の双対原理を使うことで、

主問題の最小値と双対問題の最大値は一致した場合、

その結果は最適値であると証明することができます。

 

非線形問題における双対問題

前述の通り、双対問題を解くことで、

多くの線形計画問題の解を得ることができますが、

非線形問題の場合、双対問題を解いても

直接、主問題の解を計算することはできません。

 

しかし、この主問題と双対問題を

交互に実施することで、

徐々に最適値に近づけていくことで、

最適化を実施するアルゴリズムのことを

主双対内点法(primal-dual interior point method)といいます。

 

現在、二次計画法などのソルバーとしては、

この主双対内分法を使ったソルバーが一般的のようです。

 

線形計画法の双対問題を導出してくれるPythonライブラリdual

Pythonライブラリであるdualを使うと、

線形計画法の数式を記述することで、

その双対問題の数式を表示してくれます。

 

具体的な使い方は下記を参照下さい。

 

注意点としてpython3系のみで動きます。

 

様々な最適化問題の双対問題まとめ

代表的な最適化問題とその双対問題の式をまとめておきます。

線形計画問題 1

主問題

f:id:meison_amsl:20170130074336p:plain

双対問題

f:id:meison_amsl:20170130074509p:plain

線形計画問題 2

主問題

f:id:meison_amsl:20170130074139p:plain

双対問題

f:id:meison_amsl:20170130074958p:plain

Second-order cone programming

主問題

f:id:meison_amsl:20170130083422p:plain

双対問題

f:id:meison_amsl:20170130083430p:plain

 

より詳しい双対問題の説明を知りたい人は

こちらの資料がおすすめです。

これなら分かる最適化数学―基礎原理から計算手法まで

これなら分かる最適化数学―基礎原理から計算手法まで

経済数学入門16:線型計画法(双対性)

経済数学入門16:線型計画法(双対性)

 

参考資料

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com