ChunPom’s diary

数学、物理、機械学習に関する話題。あと院試、資格、大学入試まで。

ファルカスの補題、弱双対定理、強双対定理

 線形計画法による最適化で特に重要な概念が、ファルカスの補題、弱双対定理、強双対定理である。これらにより、主問題とその双対問題を解くことの関係性が示される。

 以下、これらの定理をまとめる。

・ファルカスの補題(Farkas' lemma)

行列{\displaystyle A \in R^{m \times n}}とベクトル{\displaystyle \boldsymbol{b} \in R^{m}}が与えられる。この時、次のいずれか一方の条件のみが成り立つ。

(1) {\displaystyle A \boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x} \geq \boldsymbol{0}}を満たす解{\displaystyle \boldsymbol{x} \in R^n}が存在する。

(2) {\displaystyle  A^{T} \boldsymbol{y} \geq \boldsymbol{0}, \boldsymbol{b}^{T} \boldsymbol{y} \lt 0}を満たす解{\displaystyle \boldsymbol{y} \in R^m}が存在する。

このように二律背反な関係にある形の定理を、一般に二者択一定理と呼ぶ。なお、上記を必要十分条件の形式の主張に言い換えると、下記のようになる。

(1') {\displaystyle A \boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x} \geq \boldsymbol{0}}を満たす解{\displaystyle \boldsymbol{x} \in R^n}が存在する。

と、

(2') {\displaystyle  A^{T} \boldsymbol{y} \geq \boldsymbol{0}}ならば、{\displaystyle \boldsymbol{b}^{T} \boldsymbol{y} \geq 0}が成り立つ。

は等価である。

ファルカスの補題には色々証明方法があり、後述する弱双対定理を用いて示すこともできる(おいおい記載する)。

 

・主問題と双対問題

弱双対定理をステートする前に、線形計画問題における主問題と双対問題をまとめておく。以下、{\displaystyle A \in R^{m \times n}, \boldsymbol{b} \in R^{m}, \boldsymbol{c} \in R^{n}, \boldsymbol{x} \in R^{n}, \boldsymbol{y} \in R^{m}}とし、{\displaystyle n \gt m}かつ{\displaystyle A}の全ての行ベクトルが一次独立であるとする。

主問題は、

{\displaystyle max_{\boldsymbol{x}} \ \  \boldsymbol{c}^{T} \boldsymbol{x}  \ \  s.t.\ A \boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x} \geq \boldsymbol{0}}

双対問題は、

{\displaystyle min_{\boldsymbol{y}} \ \  \boldsymbol{b}^{T} \boldsymbol{y}  \ \  s.t.\ A^{T} \boldsymbol{y} \geq \boldsymbol{c}}

とする。

 

・弱双対定理

{\displaystyle  \boldsymbol{x},\boldsymbol{y}}がそれぞれ主問題と双対問題の実行可能解ならば、下記が成り立つ。

{\displaystyle  \boldsymbol{c}^{T} \boldsymbol{x} \leq \boldsymbol{b}^{T} \boldsymbol{y}}

これより、以下の系も成り立つ。

主問題と双対問題のいずれか一方が非有界ならば、他方は実行不能である。

弱双対定理の証明は、各制約条件を組み合わせれば容易に示すことができる。

 

・強双対定理

主問題に最適解{\displaystyle \boldsymbol{x}^*}が存在すれば、双対問題にも最適解{\displaystyle \boldsymbol{y}^*}が存在し、

{\displaystyle \boldsymbol{c}^{T} \boldsymbol{x}^*  =  \boldsymbol{b}^{T} \boldsymbol{y}^*}

とが成り立つ。

つまり、主問題に最適解が存在すれば、主問題と双対問題が実質的に等価になることを示している。強双対定理には複数のステートメントが存在し、例えば「主問題と双対問題に実行可能解が存在する」場合にもこの同値な関係が成り立つ。

強双対定理により、主問題の次元{\displaystyle n}が制約条件数{\displaystyle m}よりも十分小さい場合には、双対問題の方が次元が小さく解きやすくなるためこちらを解く方が楽になる。

この定理はファルカスの補題を用いて証明することができる(おいおい記載)。

 

以上の記述は下記の参考書を参考にした。