しっかり学ぶ数理最適化の演習解説ー2.9：ファルカスの補題から強双対定理を示す

　線形計画問題のファルカスの補題から、強双対定理を証明する。なお、これは「しっかり学ぶ最適化」の演習問題2.9である。解答は自己流なので間違っていたらご容赦ください。強双対定理およびファルカスの補題については、下記を参照のこと。
su-butsu-kikaigakusyuu.hatenablog.com

強双対定理のステートメント：

主問題

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

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

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

が成り立つ。

以下、証明

　双対問題は

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

と表せる。これに実行可能解 $\boldsymbol{y}$ が存在するとすると、弱双対定理により、 $\boldsymbol{c}^T \boldsymbol{x}^* \leq \boldsymbol{b}^T \boldsymbol{y}$ が成り立つ。
よって、強双対定理を示すには、ある $\boldsymbol{y}$ が

${\displaystyle A^T \boldsymbol{y} \geq \boldsymbol{c}, \boldsymbol{c}^T \boldsymbol{x}^* \geq \boldsymbol{b}^T \boldsymbol{y}}$

を満たすことを示せばよい。
この条件を別の表現で表すと、 $\boldsymbol{y}=\boldsymbol{y}^+ - \boldsymbol{y}^-$ 、 $\boldsymbol{z}=A^T \boldsymbol{y}-\boldsymbol{c}$ 、 $a=\boldsymbol{c}^T \boldsymbol{x}^* - \boldsymbol{b}^T \boldsymbol{y}$ を用いて、

$\begin{pmatrix} 1 & \boldsymbol{b}^T & -\boldsymbol{b}^T & \boldsymbol{0}^T \\ 0^T & -A^T & A^T & I^T \end{pmatrix} \begin{pmatrix} a \\ \boldsymbol{y}^+ \\ \boldsymbol{y}^- \\ \boldsymbol{z} \end{pmatrix} =\begin{pmatrix} \boldsymbol{c}^T \boldsymbol{x}^* \\ -\boldsymbol{c} \end{pmatrix}$

$\begin{pmatrix} a \\ \boldsymbol{y}^+ \\ \boldsymbol{y}^- \\ \boldsymbol{z} \end{pmatrix} \geq \boldsymbol{0}$

と等価になる。
ファルカスの補題により、これは

$\begin{pmatrix} 1 & \boldsymbol{0} \\ \boldsymbol{b} & -A \\ -\boldsymbol{b} & A \\ \boldsymbol{0} & I \end{pmatrix} \begin{pmatrix} \hat{a} \\ \hat{\boldsymbol{x}} \end{pmatrix} \geq \boldsymbol{0} \Rightarrow \begin{pmatrix} \boldsymbol{c}^T \boldsymbol{x}^* & -\boldsymbol{c}^T \end{pmatrix} \begin{pmatrix} \hat{a} \\ \hat{\boldsymbol{x}} \end{pmatrix} \geq 0$

と等価となる。
この条件式を整理すると、

$\heartsuit : \ \ \hat{a} \geq 0, \hat{\boldsymbol{x}} \geq \boldsymbol{0}, A \hat{\boldsymbol{x}}=\hat{a} \boldsymbol{b} \Rightarrow \hat{a} \boldsymbol{c}^T \boldsymbol{x}^* \geq \boldsymbol{c}^T \hat{\boldsymbol{x}}$

を得る。すなわち、 $\heartsuit$ の左辺を満たすような全ての $\hat{a},\hat{\boldsymbol{x}}$ に対して、右辺が成り立つことを示せば強双対定理を示すことができる。以下、 $\heartsuit$ を示す。

$\hat{a} \gt 0$ の場合

$\hat{\boldsymbol{x}} \to \hat{a} \hat{\boldsymbol{x}}$ とした上で、 $\heartsuit$ の各式を $\hat{a}$ で除算すると、下記を得る。

$\hat{\boldsymbol{x}} \geq \boldsymbol{0}, A \hat{\boldsymbol{x}}= \boldsymbol{b} \Rightarrow \boldsymbol{c}^T \boldsymbol{x}^* \geq \boldsymbol{c}^T \hat{\boldsymbol{x}}$

この左辺は元の主問題の制約条件そのものであり、 $\hat{\boldsymbol{x}}$ が実行可能解であるという仮定となる。今、題意により $\boldsymbol{x}^*$ は最適解であるから、上式の右辺は常に成り立つ。

$\hat{a} = 0$ の場合

$\heartsuit$ は以下のように書き直せる。

$\hat{\boldsymbol{x}} \geq \boldsymbol{0}, A \hat{\boldsymbol{x}}= \boldsymbol{0} \Rightarrow \boldsymbol{c}^T \boldsymbol{x}^* \geq 0$

この左辺を仮定すると、 $\boldsymbol{x}' = \boldsymbol{x}^* + \hat {\boldsymbol{x}}$ は主問題の制約を満たすことが容易に示され、実行可能解となる。。今、題意により $\boldsymbol{x}^*$ は最適解であるから、 $\boldsymbol{c}^T \boldsymbol{x}^* \geq \boldsymbol{c}^T \boldsymbol{x}' = \boldsymbol{c}^T \boldsymbol{x}^* +\boldsymbol{c}^T \hat{\boldsymbol{x}}$ であり、 $\boldsymbol{c}^T \hat{\boldsymbol{x}} \leq 0$ となるため上式の右辺が成り立つ。