2050-01-01

数学、物理、機械学習

全体

数学、物理、機械学習を中心に、

理論、応用例を紹介していきたいと思います

また、参考図書や論文なども適宜載っけていきます。

趣味、大学入試、院試や資格などの勉強にお使いください。

あと、時々無関係な話題が入ってきますが、無視してください。

2022-03-06

しっかり学ぶ数理最適化の演習解説ー2.7：相補性定理と、その応用

数学最適化線形計画法

　線形計画法において、主問題とその双対問題が実質的に等しい値を持つことが強双対定理により要請される。では、値ではなく最適解同士にはどういう関係があるのだろうか？以下の相補性定理がそれに対するアンサーとなる。

・相補性定理

以下、 $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}$ とし、 $n \gt m$ かつ $A$ の全ての行ベクトルが一次独立であるとする。

主問題を

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

とし、その双対問題を

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

とする。このとき、それぞれの実行可能解 $\boldsymbol{x},\boldsymbol{y}$ がともに最適解であるための必要十分条件は、

$x_j (\sum^m_{i=1} a_{ij} y_i -c_j)=0, \ \ j=1,...,n$

が成り立つことである。この条件を相補性条件と呼ぶ。

・応用事例として　

　これを用いて問題を解いてみよう(自己流の解き方のため間違っていたらご容赦ください)。例えば、「しっかり学ぶ数理最適化」の演習2.7は下記のような問題である。

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

ただし、 $\boldsymbol{a}, \boldsymbol{c} \geq \boldsymbol{0}, b \gt 0$ とする。

　まず $n=1$ の場合は、明らかに $x_1=b/a_1$ が最適解で、値 $b_1 c_1/a_1$ をとる。

　次に、 $n \gt 1$ の場合を考える。まず相補性定理が使えるかを吟味する。行列 $A$ はベクトル $\boldsymbol{a}=(a_1,a_2,..,a_n)$ となり一行のみの行列となるので、明らかに一次独立となる。また、制約の数も $m=1$ なので $n \gt m$ を満たしているため、相補性定理が適用できる。

　演習2.7の主問題は制約が1つのみであるため双対問題の方が解きやすいはずである。双対問題は

$min_{\boldsymbol{y}} \ \ by \ \ s.t.\ y \boldsymbol{a} \geq \boldsymbol{c}$

であり、制約条件を整理すると $y \geq max_j c_j/a_j$ となるため、この問題の最適解は $y=max_j\ c_j/a_j$ で、値 $b \cdot max_j \ c_j/a_j$ をとる。

相補性定理により、主問題の実行可能解 $\boldsymbol{x}$ が最適解であることは、すべての $j$ に対して $x_j (y -c_j/a_j)=0$ が成り立つことと同値である。今、 $y=max_j \ c_j/a_j$ であるため、 $c_j / a_j$ を最大化する $j$ の集合を $J$ で定義すると、相補性条件は

$x_j=0 \ (j \notin J)$

と等価になる。従って、これを満たし、かつ実行可能となるため制約 $\boldsymbol{a}^T\boldsymbol{x} =b$ を満たすような解が最適解となる。

以上より、主問題の最適解は $x_j=0 \ (j \notin J)$ かつ ${\displaystyle　 \sum_{j \in J} a_j x_j =b}$ なる任意の解 $\boldsymbol{x}$ であって、このとき値 $b \cdot max_j \ c_j/a_j$ をとる( $n=1$ の結果もこれに含めることができる)。

なお上記の最適解は、 $J$ の要素が1つのみの場合は1つに限られる。すなわち、その要素を $j^*$ として最適解は $x_{j^*}=b/a_{j^*}, x_{j\neq j^*}=0$ に一意に決まる。 $J$ の要素が2つ以上の場合は最適解は無数に存在する。

　相補性定理の証明は下記の参考書を参照されたい。また、上記では等式制約の主問題を考えたが、不等式制約の場合の相補性条件についても参考書では述べられている。

しっかり学ぶ数理最適化モデルからアルゴリズムまで (KS情報科学専門書)

作者:梅谷俊治
講談社

Amazon

2022-03-05

しっかり学ぶ数理最適化の演習解説ー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$ となるため上式の右辺が成り立つ。

以上により $\heartsuit$ が示された。

2022-03-05

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

数学最適化線形計画法

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

su-butsu-kikaigakusyuu.hatenablog.com

以下、証明

ファルカスの補題の(1)が成り立つとき、(2)が成り立たないことを示す

　(1)の仮定の下では、主問題

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

は実行可能解を持つ。ここで、特に $\boldsymbol{c} =\boldsymbol{0}$ とすると、これの双対問題は

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

となる。

よって、 $A^T \boldsymbol{y} \geq \boldsymbol{0}$ を仮定すると、この $\boldsymbol{y}$ は双対問題の実行可能解となる。よって、弱双対定理より、

${\displaystyle \boldsymbol{b}^{T} \boldsymbol{y} \geq \boldsymbol{c}^T \boldsymbol{x} = 0}$

が成り立つ。従って、 $A^T \boldsymbol{y} \geq \boldsymbol{0}$ と $\boldsymbol{b}^T \boldsymbol{y} \lt 0$ を満たすような $\boldsymbol{y}$ は存在せず、ファルカスの補題の(2)が成り立たないことが示された。

ファルカスの補題の(2)が成り立つとき、(1)が成り立たないことを示す

　(2)の仮定の下では、双対問題

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

は実行可能解を持つ。この解を $\boldsymbol{y}$ とすると、これを正定数倍した $\boldsymbol{y}'=\lambda \boldsymbol{y}$ もまた上記の制約を満たすため実行可能解となる。

　今、(2)の仮定により $\boldsymbol{b}^T \boldsymbol{y} \lt 0$ であるため、 ${\displaystyle \boldsymbol{b}^T \boldsymbol{y}'=\lambda \boldsymbol{b}^T \boldsymbol{y}}$ は $\lambda \to \infty$ とすれば $-\infty$ に発散し、上記の双対問題は非有界となる。

弱双対定理の系により、「主問題と双対問題のいずれか一方が非有界なら、他方は実行不能となる」ため、

主問題

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

は実行不能となる。よって、ファルカスの補題の(1)が成り立たないことが示された。

以上により、ファルカスの補題が示された。

しっかり学ぶ数理最適化モデルからアルゴリズムまで (KS情報科学専門書)

作者:梅谷俊治
講談社

Amazon

2022-03-04

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

数学最適化線形計画法

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

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

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

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

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

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

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

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

と、

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

は等価である。

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

・主問題と双対問題

弱双対定理をステートする前に、線形計画問題における主問題と双対問題をまとめておく。以下、 $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}$ とし、 $n \gt m$ かつ $A$ の全ての行ベクトルが一次独立であるとする。

主問題は、

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

双対問題は、

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

とする。

・弱双対定理

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