双対問題

双対問題（そうついもんだい、英: dual problem）とは、数学において、最適化問題における主問題（英: primary problem）の補問題を指す。どちらか一方の解法が両方の問題の解法となる。

双対原理と双対定理

最適化理論における双対原理（英: duality principle）とは、最適化問題を主問題と双対問題のどちらの観点からも見ることができることを指す。

双対定理（英: duality theorem）は次のように定義される。

主問題と双対問題のいずれか一方が最適解を持つなら、もう一方も最適解を持ち、主問題の最小値と双対問題の最大値は一致する。

双対定理の起源については、Saul Gass は Nering and Tucker (1993) を引用している。彼の著書の序文によると、ジョージ・ダンツィーグがジョン・フォン・ノイマンの推量が双対性定理の元になっていると書いており、厳密な証明は1948年に Albert W. Tucker らが発表したとされている。また、ダンツィーグが独自に双対性定理を証明し、同年に空軍内の報告書として書いているとも指摘している。

線型計画問題

線型計画問題は、目的関数と制約条件が全て線型性を有する最適化問題である。

主問題では、目的関数は n 個の変数を線型に組み合わせたものである。m 個の制約条件があり、それぞれが n 個の変数の線型な組合せの上限を定めている。問題は、制約条件を満たしつつ、目的関数の値を最小化する変数の値の組合せを求めることである。解は n 個の値のベクトル（リスト）であり、それらの値を目的関数に入力することで最小値が得られる。

双対問題では、目的関数は m 個の値の線型な組合せであり、これらは主問題の m 個の制約条件（上限値）それぞれに対応している。n 個の双対制約条件（dual constraints）があり、それぞれが m 個の双対変数（dual variables）の線型な組合せの下限を定めている。この場合、目的関数の値を最大化する双対変数の値の組合せを求める。

非線型計画問題

非線型計画問題では、制約条件が線型である必要はない。それ以外は線型計画問題とほぼ同じ原則が適用される。

非線型問題が一意な広域最適解を持つかどうかを確認するには、凸性（convexity）などに単純化する方法が便利である。制約条件や目的関数の曲率が適当な領域で常に凸なら、一意な広域最適解があるといえる。

ここでカルーシュ・クーン・タッカー条件 (KKT条件) が重要となる。これは、非線型計画問題が一意な大域最適解を持つかどうかを判定するのに、凸性に基づいた十分条件を提供する。最適解の方向を定義できるようにするために必要な追加の条件が存在する。最適解は局所解であって、大域最適解ではない可能性もある。

参考文献

Dantzig, G.B., 1963. Linear Programming and Extensions, Princeton University Press, Princeton, NJ.
Gass, Saul I., IFORS' Operational Research Hall of Fame: Albert William Tucker, International Transactions in Operational Research, Volume 11 Issue 2, Page 239 - March 2004, doi:10.1111/j.1475-3995.2004.00455.x. [1]
Gass, Saul I., IFORS' Operational Research Hall of Fame: George B. Dantzig, International Transactions in Operational Research, Volume 10 Issue 2 Page 191 - March 2003, doi:10.1111/1475-3995.00403. [2]
Nering, E.D and Tucker, A.W., 1993, Linear Programming and Related Problems, Academic Press, Boston, MA.