非線形計画の最適化問題：最急降下法、ニュートン法、KKT条件まで

はじめに

大学の講義「最適化」の前半にあたる内容のメモです。書いて覚えるのが目的で書いたので細かい部分は省いています。 ${\simeq}$ が登場する証明は厳密な証明をさけています。

参考文献

システム制御情報ライブラリ数理計画入門福島雅夫著

たしか、大学の最適化の授業は今から書く範囲（つまり上記参考文献の第四章）が前半の授業範囲で後半はナップザック問題などのNP完全問題が範囲に入っていた気がする。

前回書いたメモ

<a href="http://misos.hatenablog.com/entry/2014/12/27/141241">最適化：非線形計画問題のメモ - 雑なメモ</a>
最適化：非線形計画問題のメモ - 雑なメモ

言葉と式の定義

問題の定式化

${ 目的関数: f(\vec{x}) \to min \\ 制約条件: \left\{ \begin{array}{l} c_1(\vec{x}) = 0,\dots,c_k(\vec{x}) = 0 \\ c_{k+1}(\vec{x}) \leq 0,\dots,c_{n}(\vec{x}) \leq 0 \end{array} \right. }$
のようにこれから解く問題を表現する。不等号の向きは（-1）を両辺にかけてそろえる。ただし、制約条件は一旦すべて一次関数と限定する。

最適解

以下、各問題の最適解は一貫して ${ \vec{x^*} }$ と記述。

凸関数

${ \vec{x},\vec{y} \in R^n , 0 \leq \alpha \leq 1 \\ \to f(\alpha \vec{x} + (1 - \alpha)\vec{y}) \leq \alpha f(\vec{x}) + (1 - \alpha)f(\vec{y}) }$
が成り立つ関数を凸関数と呼ぶ。

凸集合

${\vec{x},\vec{y} \in S , 0 \leq \alpha \leq 1 \to \alpha \vec{x} + (1 - \alpha)\vec{y} \in S}$ が成り立つ集合S。

凸計画問題

目的関数が凸関数で実行可能領域が凸集合の問題。また凸計画問題では局所最適解と大域最適解が一致する。

下線部の証明:
　背理法、一致しないと仮定して局所最適解 ${\vec{x} }$ と大域最適解 ${ \vec{y}}$ があるとする。もちろん ${ \vec{x} \vec{y} }$ 。ここで凸集合であることから ${\vec{x},\vec{y} \in S , 0 \leq \alpha \leq 1 \to \alpha \vec{x} + (1 - \alpha)\vec{y} \in S}$ が成り立つ。
　一方目的関数fは凸関数なのだから
${ \vec{x},\vec{y} \in R^n , 0 \leq \alpha \leq 1 \\ \to f(\alpha \vec{x} + (1 - \alpha)\vec{y}) \leq \alpha f(\vec{x}) + (1 - \alpha)f(\vec{y}) }$
が成り立つ。すなわち ${ f(\alpha \vec{x} + (1 - \alpha)\vec{y})}$ は大域最適解よりも小さい値になる、これはおかしい■

勾配とヘッセ行列

$\Delta f (\vec{x})= \nabla^2 f (\vec{x})$ がヘッセ行列で勾配は ${ \nabla f(\vec{x})}$ と記述する。

固有値の符号による行列の種類分け

正定値行列
- 固有値がすべてゼロより大きい
半正定値行列
- 固有値がすべてゼロ以上

制約無非線形計画問題の最適化

ヘッセ行列の意味付け

${ \tilde{f} (\vec{x}) \simeq f(\vec{x'}) + \nabla f(\vec{x'})^T (\vec{x} - \vec{x'}) + \frac{1}{2} (\vec{x} - \vec{x'})^T \nabla^2 f(\vec{x'}) (\vec{x} - \vec{x'}) }$
と記述できる、ここで ${\vec{x'}}$ は実行可能領域（でなくてもいいけど）の任意の点、そしてその点について多変数テイラー展開して三次以降の項を無視して近似した。ここで上の式の第三項にヘッセ行列 ${\nabla^2 f(\vec{x'})}$ が出現している。 ${(\vec{x} - \vec{x'})^T \nabla^2 f(\vec{x'}) (\vec{x} - \vec{x'}) }$ の部分が正になるかどうかはヘッセ行列の固有値の符号によって決まってくるのだからヘッセ行列が関数のグラフの形を特徴付ける一つの要因になっていることに気づく。

※上のテイラー展開の式は
${ f(\vec{x'}) + \sum_{i=1}^{n} \frac{\partial f(\vec{x'})}{\partial x_i} (x_i - {x'}_i) + \frac{1}{2!} \sum_{i=1}^{n} \sum_{j=1}^{n} \frac{\partial f(\vec{x'})}{\partial x_i} \frac{\partial f(\vec{x'})}{\partial x_j} (x_i - {x'}_i)(x_i - {x'}_j) }$
と記述できる。

最適解であるための必要条件と十分条件

　二次元のグラフで考えたとき、グラフの頂点が最も最小（最大）の値をとる。頂点での傾きは0。それに対応するように多次元（二次元も含む）では ${ \nabla f(\vec{x^*}) = 0 }$ となることが最適である必要条件。( ${\vec{x^*}}$ は以下では最適解のこと)　ただし、最適解でないときでも ${ \nabla f(\vec{x}) = 0 }$ となる点は存在して、このような点をまとめて停留点という。つまり制約なしならば最適解は停留点である。さらに目的関数が凸関数であるという制限をくわえると停留点は（大域）最適解となる。

※下線部の証明
　目的関数が凸関数ならば、任意の点でヘッセ行列は半正値になる（証明略...）。この事実から、
${ \tilde{f} (\vec{x}) \\ \simeq f(\vec{x'}) + \nabla f(\vec{x'})^T (\vec{x} - \vec{x'}) + \frac{1}{2} (\vec{x} - \vec{x'})^T \nabla^2 f(\vec{x'}) (\vec{x} - \vec{x'}) \\ \geq f(\vec{x'}) + \nabla f(\vec{x'})^T (\vec{x} - \vec{x'}) }$
ここで両辺から ${f(\vec{x'})}$ を引いたら

${ \tilde{f} (\vec{x}) - f(\vec{x'}) \geq \nabla f(\vec{x'})^T (\vec{x} - \vec{x'}) }$

が任意の点で成り立つと示せる。上の式で停留点を ${\vec{x^*}}$ と書くとき ${\vec{x'} = \vec{x^*}}$ とすれば

${ \tilde{f} (\vec{x}) - f(\vec{x^*}) \geq 0 }$

であるから、停留点よりも小さい値をとれる点がないことになる。よって停留点が最適解。■

さらに、 ${\nabla^2 f(\vec{x^*})}$ は必ず半正定値である。

※下線部の証明
　今、最適解でのヘッセ行列が半正定値でないとすると、あるベクトル ${\epsilon\vec{x'}}$ が存在して ${\epsilon^2\vec{x'}^T \nabla^2 f(\vec{x^*})\vec{x'} \leq 0 }$ である。ここで最適解の付近のベクトル ${\epsilon\vec{x'} + \vec{x^*}}$ について最適解 ${\vec{x^*}}$ でテイラー展開すると、
${ {f} (\epsilon\vec{x'} + \vec{x^*}) \\ = f(\vec{x^*}) + \nabla f(\vec{x^*})^T (\epsilon\vec{x'} + \vec{x^*} - \vec{x^*}) + \frac{1}{2!} (\epsilon\vec{x'} + \vec{x^*} - \vec{x^*})^T \nabla^2 f(\vec{x^*}) (\epsilon\vec{x'} + \vec{x^*} - \vec{x^*}) + o(\epsilon^3) \\ = f(\vec{x^*}) + \epsilon \nabla f(\vec{x^*})^T (\vec{x'} ) + \frac{1}{2} \epsilon^2\vec{x'}^T \nabla^2 f(\vec{x^*}) \vec{x’} + o(\epsilon^3) }$

と記述できる。 ${\epsilon}$ を十分小さくしたとき、 ${o(\epsilon^3)}$ を無視してよいから ${\epsilon^2\vec{x'}^T \nabla^2 f(\vec{x^*})\vec{x'} \leq 0 }$ とあわせて、

${ {f} (\epsilon\vec{x'} + \vec{x^*}) \\ \simeq f(\vec{x^*}) + \epsilon \nabla f(\vec{x^*})^T (\vec{x'} ) + \frac{1}{2} \epsilon^2\vec{x'}^T \nabla^2 f(\vec{x^*}) \vec{x’} + o(\epsilon^3) \\ \leq f(\vec{x^*}) + \epsilon \nabla f(\vec{x^*})^T (\vec{x'} ) \\ = f(\vec{x^*}) }$

となる。つまり、 ${{f} (\epsilon\vec{x'} + \vec{x^*}) \leq f(\vec{x^*})}$ が成り立つ。これは ${\vec{x^*}}$ が最適解であることに矛盾している。■

以上から制限なし問題の最適解の必要条件は

${\nabla f(\vec{x^*}) = 0}$
${\nabla^2 f(\vec{x^*})}$ は半正定値

と求められた。十分条件は上の証明の

において、不等式の向きが逆になればいいのだから

${\nabla^2 f(\vec{x^*})}$ は正定値

が十分条件とわかる。

制約なし問題の解法

最急降下

　ざっくりいうと、最も急な勾配の方向に進んでいけば手っ取り早く勾配0の点にたどり着くのではないか？というやり方。山をイメージしてもっとも傾斜のあるところを登ればすぐに頂点にたどり着く感じ。このやり方を定式化する。以下系列 ${ \{ \vec{x^(k)}\} }$ は最急降下を適用するたびに生成される点列。勾配は ${\nabla f(\vec{x^(k)}) }$ と書けるがこれだけでは勾配の方向に”進む”距離を決められないからその距離を決める変数列を ${ \{\alpha^{(k)}\}}$ と書く。方向さえ決まれば

${ \min_{\alpha \geq 0} \vec{x^(k)} - \alpha^{(k)} \nabla f(\vec{x^(k)}) }$

となるように ${\alpha^{(k)} }$ を定めればいい。結局最急降下法は

${\vec{x^{(0)}} }$ を決める。
${\min_{\alpha \geq 0} \vec{x^(k)} - \alpha^{(k)} \nabla f(\vec{x^(k)})}$ となる ${ \{\alpha^{(k)}\}}$ を決める
tex:{ \vec{x^(k+1)} = \vec{x^(k) - \alpha^{(k)} \nabla f(\vec{x^(k)})}]
ステップ2に戻る

とまとめられた。

ニュートン法

最急降下法は ${\nabla^2 f(\vec{x})}$ の情報を利用せずに解を探索した。ニュートン法は ${\nabla^2 f(\vec{x})}$ の情報を利用するから、最急降下法よりも速い収束が期待できそう。というわけで、 ${\nabla^2 f(\vec{x})}$ が出るような式変形としてテイラー展開を思い出すと、

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

と書ける。いまヘッセ行列は正定値と仮定すれば目的関数は凸関数のはずである。凸関数は勾配が0になる点で最適解を得るのが必要条件なのだから、式 ${\tilde{f} (\vec{x})}$ を ${(\vec{x} - \vec{x^(k)})}$ で微分したとき、

${ \nabla \tilde{f} (\vec{x}) \\ = \nabla \{f(\vec{x^(k)}) + \nabla f(\vec{x^(k)})^T (\vec{x} - \vec{x^(k)}) + \frac{1}{2} (\vec{x} - \vec{x^(k)})^T \nabla^2 f(\vec{x^(k)}) (\vec{x} - \vec{x^(k)}) \} \\ = 0 + \nabla f(\vec{x^(k)}) + \nabla^2 f(\vec{x^(k)}) (\vec{x} - \vec{x^(k)}) \\ = \nabla f(\vec{x^(k)}) + \nabla^2 f(\vec{x^(k)}) (\vec{x} - \vec{x^(k)}) \\ = 0 }$

となるような ${(\vec{x} - \vec{x^(k)})}$ は

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

と求まる。つまり、

${ \vec{x^(k)} = \vec{x} + (\nabla^2 f(\vec{x^(k)}))^{-1}\nabla f(\vec{x^(k)}) }$

を次の点とすればいい。結局ニュートン法をまとめると

${\vec{x^(0)} }$ を選ぶ、ここで”いまヘッセ行列は正定値と仮定すれば目的関数は凸関数のはず”とあるのはスタート地点が適切でないと収束しない場合があるから。
${ \vec{x^(k+1)} = \vec{x^{(k)}} + (\nabla^2 f(\vec{x^(k)}))^{-1}\nabla f(\vec{x^(k)}) }$
${\nabla f(\vec{x^(k)}) = 0}$ なら終了、そうでないならステップ2へ。

最急降下とニュートン法の性質

一旦略。

制約あり問題の最適化

${ 目的関数: f(\vec{x}) \to min \\ 制約条件: \left\{ \begin{array}{l} c_1(\vec{x}) = 0,\dots,c_k(\vec{x}) = 0 \\ c_{k+1}(\vec{x}) \leq 0,\dots,c_{m}(\vec{x}) \leq 0 \end{array} \right. }$
で記述された制約付きの問題についてはここから。まず、制約なし問題との明らかな違いが ${\nabla f(\vec{x^*}) = 0}$ とは限らない。ここの説明はここにはうまく記述できない（参考文献の第四章参照）けれどとにかく最適解 ${\vec{x^*}}$ では

${ \nabla f(\vec{x^*}) + r_1^* \nabla c_1(\vec{x^*}) + \dots + r_n^* \nabla c_m(\vec{x^*}) = \vec{0} }$

が成り立つ。ここでrに添字がついたものはすべて適当な実数で式をみたすような実数が存在する。自分のイメージでは「各制約条件が最適に向かうような方向（勾配ベクトル）に引っぱりあってその釣り合い位置（＝０の位置）が最も最適である」というイメージ。そして制約あり問題の必要条件であるカルーシュ・キューン・タッカー条件/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 & r_k(\vec{x^*}) \leq 0 が制約条件\\ \end{array} \right. \end{array} \right. }$