最適化：非線形計画問題のメモ

非線形計画

以下、非線形計画問題
${ \displaystyle \vec{x} \in R^n 目的関数: f(\vec{x}) -> min 制約条件:1 \vec{x} \in S }$

局所最適と大域最適

今、この問題の制約条件Sが実数全体ならばとくに制約なし問題、そうでない場合が制約のある問題として扱う。実行可能領域全体で最も最適の解である点を帯大域最適解、適当な区間が定義されていてその区間内で実行可能かつ最適ならばそれを局所最適解と呼ぶ。

つまり、大域最適である点は必ず（定めた適当な区間に含まれていれば）局所最適だが、局所最適が大域最適であるとは必ずしも限らない。

制約なしの凸計画問題

　非線形計画問題の中ではもっとも楽な部類の問題。二次関数の頂点が最適解になっているイメージ。以下、凸計画問題の定義。
${ \displaystyle \vec{x} , \vec{y} \in R^n , 0 \leq \alpha \leq 1\\ f(\alpha \vec{x} + ( 1 - \alpha )\vec{y}) \leq \alpha f(\vec{x}) + ( 1 - \alpha )f(\vec{y}) \\ が必ず成り立ち、\\ \vec{x} , \vec{y} \in S ならば \alpha \vec{x} + ( 1 - \alpha )\vec{y} \in S }$
が成り立つ最適化問題が凸計画問題。なぜ楽な部類かといえば、この問題では局所最適解が必ず大域最適解に一致するから。
証明:もしも局所最適解 $\vec{x}$ と大域最適解 $\vec{x'}$ が一致しないとして、
${ \displaystyle f(\alpha \vec{x} + ( 1 - \alpha )\vec{x’}) \leq \alpha f(\vec{x}) + ( 1 - \alpha )f(\vec{x’}) }$
が成り立つのだから $\alpha \vec{x} + ( 1 - \alpha )\vec{x’}$ という大域最適解と一致しない最適解が見つかる、これはおかしい。■

そして、Sが
${ \displaystyle \vec{x} , \vec{y} \in S ならば \alpha \vec{x} + ( 1 - \alpha )\vec{y} \in S }$
を満たすとき、Sは凸集合と呼ぶ、このSが凸集合である条件はSを構成するためのn個の制約条件の式 $const_1(\vec{x}) , \dots ,const_n(\vec{x})$ がすべて凸関数であることが必要条件。

制約あり非•凸計画問題

${ \displaystyle\vec{x} = (x_1 , x_2 , \dots , x_n)^T }$ について、このベクトル $\vec{x}$ での(二次元での)傾きと呼ばれるものに対応する値は、

${ \displaystyle \nabla f = \frac{d f(\vec{x}}{d \vec{x}} = \left( \begin{array}{c} \frac{d f(\vec{x}}{d \vec{x_1}} \\ \frac{d f(\vec{x}}{d \vec{x_2}} \\ \vdots \\ \frac{d f(\vec{x}}{d \vec{x_n}} \\ \end{array} \right) }$
であり勾配と呼ばれる。勾配はその関数のもっとも傾きの大きい方向を示している。つまり、その方向に1の"距離"（ここの距離とは、ノルムとする）だけ動けば一番関数の値に変化するのではなく、その方向に1の"距離"その点の傾きと同じ傾きだと思って移動すればもっとも変化があるということ。
　この勾配ベクトルは、与えられた点の関数の傾き具合を示すものだから、これを用いて最適な解を探すことが考えられる。 $f(\vec{x})$ をさらに微分したものは

${ \displaystyle \Delta f = \nabla^2 f = \frac{d^2 f(\vec{x}}{d \vec{x}^2} = \left( \begin{array}{c} \frac{d^2 f(\vec{x}}{d \vec{x_1}^2} \\ \frac{d^2 f(\vec{x}}{d \vec{x_2}^2} \\ \vdots \\ \frac{d^2 f(\vec{x}}{d \vec{x_n}^2} \\ \end{array} \right) }$

と記述されるのではなく、

${ \displaystyle H = \Delta f = \nabla^2 f = \frac{d^2 f(\vec{x}}{d \vec{x}^2} = \left( \begin{array}{c} \frac{d^2 f(\vec{x}}{d \vec{x_1}\vec{x_1}} \dots \frac{d^2 f(\vec{x}}{d \vec{x_1}\vec{x_n}}\\ \frac{d^2 f(\vec{x}}{d \vec{x_2}\vec{x_1}} \dots \frac{d^2 f(\vec{x}}{d \vec{x_2}\vec{x_n}}\\ \vdots \\ \frac{d^2 f(\vec{x}}{d \vec{x_n}\vec{x_1}} \dots \frac{d^2 f(\vec{x}}{d \vec{x_n}\vec{x_n}}\\ \end{array} \right) }$

と記述されて、これをヘッセ行列と呼ぶ。つまり ${ H_{i,j} = \frac{d^2 f(\vec{x}}{d \vec{x_i}\vec{x_j}} }$ である。ここで偏微分 ${ \frac{d^2 f(\vec{x}}{d \vec{x_i}\vec{x_j}}　、\frac{d^2 f(\vec{x}}{d \vec{x_j}\vec{x_i}} }$ がともに連続だとするとこの二式は等しい。

※ちょうどいいページがありました
偏微分の順序交換

なのでヘッセ行列は対称であると仮定する。そして、このヘッセ行列の固有値を求めることでその関数のグラフがどのような形をしているか（に関係する情報のうちの一つ）を知ることができる。

いま、fを実行可能領域にある任意の点 ${ \bar{\vec{x}} }$ でテイラー展開すると、

${ \displaystyle f(\vec{x})\\ ≒ f(\bar{\vec{x}}) + f^{(1)}(\bar{\vec{x}}) ( \vec{x} - \bar{\vec{x}} ) + \sum_i \sum_j \frac{\frac{d^2 f(\bar{\vec{x}})}{dx_i dx_j}(\bar{\vec{x}})}{2!} (\vec{x_i} - \bar{\vec{x_i}} )(\vec{x_j} - \bar{\vec{x_j}} ) \\ = f(\bar{\vec{x}}) + \nabla f(\bar{\vec{x}})^T (\vec{x} - \bar{\vec{x}}) + \frac{1}{2}(\vec{x} - \bar{\vec{x}})^T \Delta f(\bar{\vec{x}}) (\vec{x} - \bar{\vec{x}}) }$

と記述できる。つまり、適当な点を近似しようと二次まで式をテイラー展開したらそこにヘッセ行列が現れる。ここでヘッセ行列が正定値行列（固有値がすべて正）ならば、もしくは半正定値（固有値がすべて0以上）ならばfは凸関数である。さらに、局所最適な点ではこの行列は半正定値行列になる。なぜならば、ヘッセ行列の固有値 ${\lambda }$ に対してヘッセ行列が半正定値行列ならば最適解 ${ \vec{x}^* }$ について、

${ H( \vec{x}^* - \bar{\vec{x}} ) = \lambda ( \vec{x}^* - \bar{\vec{x}} ) }$ 、そして ${\lambda \leq 0 }$ なのだから ${ ( \vec{x}^* - \bar{\vec{x}} )^T H(\vec{x}^*) ( \vec{x}^* - \bar{\vec{x}} ) = \lambda \geq 0 }$ である。これが成り立たないと仮定する。すると、

${ ( \vec{x}^* - \bar{\vec{x}} )^T H(\vec{x}^*) ( \vec{x}^* - \bar{\vec{x}} ) = \lambda \le 0 }$ を満たすベクトル ${ ( \vec{x}^* - \bar{\vec{x}}) }$ が存在する。このベクトルを ${ \vec{x}^* - \bar{\vec{x}} = \vec{\hat{x}} }$ と書く。そして、 ${ \vec{x}^* + \epsilon \vec{\hat{x}} }$ について関数fを ${ \vec{x}^* }$ まわりでテイラー展開すると、

${ \displaystyle f(\vec{x}^* + \epsilon \vec{\hat{x}}) \\ = f(\vec{x}^*) + \nabla f(\vec{x}^*)^T ( \vec{x}^* + \epsilon \vec{\hat{x}} - \vec{x}^*) + \frac{1}{2} ( \vec{x}^* + \epsilon \vec{\hat{x}} - \vec{x}^*)^T \Delta f(\vec{x}^*) ( \vec{x}^* + \epsilon \vec{\hat{x}} - \vec{x}^*) + o({\epsilon}^3) \\ }$

とできて、イプシロンを十分小さくして、さらに局所最適解の点では勾配が0であることを考慮すると

${ \displaystyle ≒ f(\vec{x}^*) + \frac{\epsilon^2}{2} (\vec{\hat{x}})^T \Delta f(\vec{x}^*) (\vec{\hat{x}}) \\ }$

であるが、この式の第二項はヘッセ行列が正定値でないときに負の値になるのだから局所最適解よりも小さな値になってしまいこれはおかしい■
（自分で書いといてどうかと思うけど上の説明適当かも）

以上から、局所最適解は

勾配が0
局所最適解から十分近い任意の解は局所最適ではない

ことが言える。

最急降下法

数値解析とかでやったような気がするけど、こういう問題は有限ステップをさだめて正確に解を求めることは非常に難しいのでLU分解とかして反復計算に持ち込んだのと同じように反復計算で最適解に「近づく」方法を考える。その1つが最急降下法。名前のとおり、もっとも傾きの大きい方向に進んでいけば効率よく最適解に近づくことができそう、といった考え方。
　この考え方をそのまま式にすれば、今いる点を $\vec{x_0}$ と記述すると、その点の勾配（傾き）は $\nabla f(\vec{x_0})$ となる。その方向に進むのだから、次の点は $\vec{x_1} = \vec{x_0} + \alpha_0 \nabla f(\vec{x_0})$ となる。αは進む距離で、適切なαはその方向で一番値が小さい点（最適がminを求める場合）である。そしてこれを繰り返す、つまり

1.初めに十発点 $\vec{x_0}$ を定めて、
2. $\nabla f(\vec{x_k})$ を計算

2.1 $\nabla f(\vec{x_k}) = 0$ なら $\vec{x_k}$ を解とする
2.2 $\nabla f(\vec{x_k}) \neq 0$ ならば進む距離αを求める。

3. $\vec{x_{k+1}} = \vec{x_k} + \alpha_k \nabla f(\vec{x_k})$ としてステップ2へ。

である。

最急勾配法

もしもこのようにして生成される点列 ${ \{\vec{x_k}\} }$ について、十分大きな数Nで ${ \{\nabla f(\vec{x_N}) \simeq 0\} }$ と仮定するとこの点列は収束する。今、 ${ \displaystyle \sqrt{{\vec{x}}^T G \vec{x}} = ||\vec{x}|| }$ というノルムを定義するとき、収束の早さは
${ \displaystyle (\frac{\frac{\lambda_{max}}{\lambda_{min}} - 1}{\frac{\lambda_max}{\lambda_min} + 1} + \epsilon)||\vec{x^k} - \vec{x^*}|| }$
に依存している。ここで $\lambda^2 f(\vec{x^*})$ であり、この式から収束の早さは今いる位置がどれくらい解から遠い距離にいるかと最適解のヘッセ行列の固有値の最大値と最小値の比率がどれくらいかに依存する。そして、ヘッセ行列は半正定値をのぞいて制限がないからこの固有値の比率は非常に大きくなる可能性がありその場合は収束は遅くなってしまう。

(準)ニュートン法

　最急降下は関数の一次微分の情報（勾配がどの方向に急になっているか）を用いて解に近づこうとしたが、遅くなる場合があった。ここでは、先ほどより緩いヘッセ行列は正定値（さっきは半正定値）こんどは二回微分（ヘッセ行列）の情報も用いて高速化したいと考える。つまり、今最適解をもとめたい関数は凸関数であると仮定して、 $\vec{x^k}$ でのテイラー展開を用いて任意の点の関数の値の近似値を求めると、

${ \displaystyle \tilde {f}(\vec{x}) \simeq f(\vec{x^k}) + \nabla f(\vec{x^k})(\vec{x} - \vec{x^k}) + \frac{(\vec{x} - \vec{x^k})^T \nabla^2 f(\vec{x^k}) (\vec{x} - \vec{x^k})}{2!} }$

と近似できる。kが十分大きいと $\nabla \tilde{f} (\vec{x}) \simeq \vec{0}$ なのだから

${ \displaystyle \nabla \tilde {f}(\vec{x}) \\ = \nabla f(\vec{x^k}) + 2 \frac{\nabla^2 f(\vec{x^k}) (\vec{x} - \vec{x^k})}{2!} \\ \simeq \vec{0} }$

であり、

${ \displaystyle (\vec{x} - \vec{x^k}) \\ \simeq - \{ \nabla^2 f(\vec{x^k}) \}^{-1}\nabla f(\vec{x^k}) \\ }$

よって、つぎのステップを

${ \displaystyle \vec{x_k} - \{ \nabla^2 f(\vec{x^k}) \}^{-1}\nabla f(\vec{x^k}) \\ }$

と定める、これがニュートン法。

ニュートン法の収束の早さ

爆速。あとで追記予定。

Karush-Kuhn-Tucker condition(KKT条件)

この部分は目的関数と制約条件が連続で二回微分可能だと仮定した下での記述。制約付き非線形計画問題の制約や目的関数に適当に(-1)をかけることで

目的関数 : $f(\vec{x}) の最小化$
制約条件： $c_i(\vec{x} = 0, c_j(\vec{x}) \leq 0$

と書き換えることができる。制約条件が連続で二回微分可能だと仮定したから、この問いの最適解 $\vec{x^*}$ では、 $\sum_{k = 1}^{制約条件の数} r_k \nabla c_k (\vec{x}) + \nabla f(\vec{x}) = \vec{0} , r_k \in R$ を満たす点があるということ（らしい）。この式は線形代数ででてきた式そのもので、 $c_1 (\vec{x}) , \dots , c_n (\vec{x}) , \nabla f(\vec{x})$ が線形独立である場合~~が最適解と分かる~~。つまり、これらの列ベクトルをまとめた行列を簡約してrankを調べればいい。一般化したのがKKT条件で以下のようにまとめられる。

${ \displaystyle \left\{ \begin{array}{l} \sum_{k = 1}^{制約条件の数} r_k \nabla c_k (\vec{x}) + \nabla f(\vec{x}) = \vec{0} , r_k \in R \\ r_k = \left\{ \begin{array}{ll} 任意の実数 & c_k(\vec{x^*}) = 0 が制約条件\\ 0 & c_k(\vec{x^*}) < 0 が制約条件\\ r_k \geq 0 & c_k(\vec{x^*}) \leq 0 が制約条件\\ \end{array} \right. \end{array} \right. }$

すなわち局所最適な点では

制約条件が $c_k(\vec{x^*}) \leq 0$ という形でない式に対応する係数 $r_k$ はゼロ

が必ず成り立っている、ただし成り立っているから必ずその点が局所最適とはならない。

$\sum_{k = 1}^{制約条件の数} r_k \nabla c_k (\vec{x}) + \nabla f(\vec{x}) = \vec{0} , r_k \in R$ (ラグランジュ未定常数法の式と同じ)が成り立つ。

(局所)最適性を満たすための必要十分条件

この項目ではfが目的関数、cが制約条件。 $\vec{x^*}$ が局所（大域）最適解。

制約なし問題

必要条件

最適解となる点は勾配が0となる点なのだから、 $\nabla f(\vec{x^*}) = 0$ 。
もしもヘッセ行列に負の値の固有値があると、今見つかっている $\vec{x^*}$ まわりでテイラー展開するとより良い解が見つかってしまうから、ヘッセ行列が半正定値。

必要条件

ヘッセ行列の固有値に0がないならば、最適解に十分近い値は最適解よりも大きな値になる
最適解となる点は勾配が0となる点

制約あり問題

必要条件

最適解ならばKKT条件を満たす
いまKKT条件の式のうち、ラグランジュ未定乗数法と似た形の式 $K_{KT}(\vec{r},\vec{x}) = \sum_{k = 1}^{制約条件の数} r_k \nabla c_k (\vec{x}) + \nabla f(\vec{x}) = \vec{0} , r_k \in R$ に注目する。これから制約なし問題の必要条件「もしもヘッセ行列に負の値の固有値があると、今見つかっている $\vec{x^*}$ ..(略)..より良い解が見つかってしまうから○×」に対応する式を導出すればいいと考える。すると $K_{KT}(\vec{r},\vec{x})$ をもう一回微分して $\nabla K_{KT}(\vec{r},\vec{x})$ とするとヘッセ行列になることを利用すればいいと分かる。そして必要条件となる式はすべての（有効）制約の勾配ベクトルと直行するベクトル $\vec{y}$ を用いて $\vec{y}^T{\nabla^2}_{\vec{x}}\nabla K_{KT}(\vec{r},\vec{x})\vec{y} \geq 0$ である（参考文献第四章制約付き問題の最適条件参照）。

十分条件

KKT条件
制約なしでは「半正定値→正定値」となったことを思い出すと、「 $\vec{y}$ を用いて $\vec{y}^T{\nabla^2}_{\vec{x}}\nabla K_{KT}(\vec{r},\vec{x})\vec{y} \geq 0$ → $\vec{y}$ を用いて $\vec{y}^T{\nabla^2}_{\vec{x}}\nabla K_{KT}(\vec{r},\vec{x})\vec{y} > 0$ 」とわかる。