トップ > 数理計画用語集 > 双対定理

数理計画用語集

双対定理

読み:そうついていり
英名:Duality Theorem
関連主問題双対問題

equation凸関数とし,次の凸計画問題 (P) を考える.

(P) equation

(P) に対し,凸関数 equationequation が閉真凸で

equation

を満たすものとし,equation とおく.すると,equation凸関数であり,(P) の下限値は equationとなる.ここで,関数equationの共役関数を equation で表す.共役関数とは

equation

で定義される関数である.equation を用いて主問題 (P) の双対問題を次のように構成する.

(D) equation

双対問題 (D) の目的関数

equation

であるから,双対問題 (D) は equation をみたすアフィン関数 equation のうち,原点での値 equation を最大化するようなアフィン関数の勾配を決定する問題といえる.

故に,equation が成り立ち,これを弱双対定理と呼ぶ.不等式 equation において,等号が成り立たないとき,双対ギャップがあるという.

以下,簡単に,双対ギャップが消えるための条件を述べる.簡単な計算から equation となるので,equation は双対ギャップが消えることの必要十分条件であり,この事実を双対定理と呼ぶ.例えば,equation が閉真凸ならば equation となるので,双対ギャップは消える.また,双対問題の定義から,equation の原点において劣勾配が存在することと,双対問題 (D) に最適解が存在して equation となることが同値であることも感覚的に分かるであろう.更に,equation の原点における劣勾配双対問題 (D) の最適解を与える.即ち,equationequation の原点での劣微分に他ならない.

 双対問題 (D) の目的関数は,拡張ラグランジュ関数と呼ばれる関数

equation を用いて equation と定義することもあるが,これは equation と一致することを注意しておく.

 双対問題凸関数 equation の取り方により,その形は様々であるが,equation

equation

とした場合の双対問題は,特にラグランジュ双対問題と呼ばれる.こう呼ばれる所以は,この場合の拡張ラグランジュ関数は

equation

という形になり,よく慣れ親しまれているラグランジュ関数に他ならないからである.

 最後に主問題線形計画問題だった場合の弱双対定理,双対定理について触れておく.

以後,下記のような主問題(P)と双対問題(D)を考える.ただし,equation (m×n 行列) とし,変数 equationequation とする.

(P) equation (D) equation

問題(P),(D)の任意の実行可能解 equation に対し,equation が常に成立し,これを弱双対定理と呼ぶ.

また,問題(P),(D)に関して,いずれか一方の問題が最適解をもつならば他方の問題も最適解をもち,それらの値が等しくなるという性質がある.即ち,問題(P),(D)各々の最適解が存在するとして,(P)の最適解equation,(D)の最適解equation とおくと,問題(P)の最小値 equation と問題(D)の最大値 equation との間に equation が成り立ち,これを双対定理と呼ぶ.

[参考]
今野 浩,山下 浩,非線形計画法,日科技連,1978
福島 雅夫,非線形最適化の基礎,朝倉書店,2001