はじめに
大学の講義「最適化」の前半にあたる内容のメモです。書いて覚えるのが目的で書いたので細かい部分は省いています。が登場する証明は厳密な証明をさけています。
参考文献
- システム制御情報ライブラリ 数理計画入門 福島雅夫 著
たしか、大学の最適化の授業は今から書く範囲(つまり上記参考文献の第四章)が前半の授業範囲で後半はナップザック問題などのNP完全問題が範囲に入っていた気がする。
前回書いたメモ
言葉と式の定義
問題の定式化
のようにこれから解く問題を表現する。不等号の向きは(-1)を両辺にかけてそろえる。ただし、制約条件は一旦すべて一次関数と限定する。
最適解
以下、各問題の最適解は一貫してと記述。
凸関数
が成り立つ関数を凸関数と呼ぶ。
凸集合
が成り立つ集合S。
凸計画問題
目的関数が凸関数で実行可能領域が凸集合の問題。また凸計画問題では局所最適解と大域最適解が一致する。
下線部の証明:
背理法、一致しないと仮定して局所最適解と大域最適解があるとする。もちろん。ここで凸集合であることから が成り立つ。
一方目的関数fは凸関数なのだから
が成り立つ。すなわちは大域最適解よりも小さい値になる、これはおかしい■
勾配とヘッセ行列
がヘッセ行列で勾配はと記述する。
制約無非線形計画問題の最適化
ヘッセ行列の意味付け
と記述できる、ここでは実行可能領域(でなくてもいいけど)の任意の点、そしてその点について多変数テイラー展開して三次以降の項を無視して近似した。ここで上の式の第三項にヘッセ行列が出現している。の部分が正になるかどうかはヘッセ行列の固有値の符号によって決まってくるのだからヘッセ行列が関数のグラフの形を特徴付ける一つの要因になっていることに気づく。
※上のテイラー展開の式は
と記述できる。
最適解であるための必要条件と十分条件
二次元のグラフで考えたとき、グラフの頂点が最も最小(最大)の値をとる。頂点での傾きは0。それに対応するように多次元(二次元も含む)ではとなることが最適である必要条件。(は以下では最適解のこと) ただし、最適解でないときでもとなる点は存在して、このような点をまとめて停留点という。つまり制約なしならば最適解は停留点である。さらに目的関数が凸関数であるという制限をくわえると停留点は(大域)最適解となる。
※下線部の証明
目的関数が凸関数ならば、任意の点でヘッセ行列は半正値になる(証明略...)。この事実から、
ここで両辺からを引いたら
が任意の点で成り立つと示せる。上の式で停留点をと書くときとすれば
であるから、停留点よりも小さい値をとれる点がないことになる。よって停留点が最適解。■
さらに、は必ず半正定値である。
※下線部の証明
今、最適解でのヘッセ行列が半正定値でないとすると、あるベクトルが存在してである。ここで最適解の付近のベクトルについて最適解でテイラー展開すると、
と記述できる。を十分小さくしたとき、を無視してよいからとあわせて、
となる。つまり、が成り立つ。これはが最適解であることに矛盾している。■
以上から制限なし問題の最適解の必要条件は
- は半正定値
と求められた。十分条件は上の証明の
において、不等式の向きが逆になればいいのだから
- は正定値
が十分条件とわかる。
制約なし問題の解法
最急降下
ざっくりいうと、最も急な勾配の方向に進んでいけば手っ取り早く勾配0の点にたどり着くのではないか?というやり方。山をイメージしてもっとも傾斜のあるところを登ればすぐに頂点にたどり着く感じ。このやり方を定式化する。以下系列は最急降下を適用するたびに生成される点列。勾配はと書けるがこれだけでは勾配の方向に”進む”距離を決められないからその距離を決める変数列をと書く。方向さえ決まれば
となるようにを定めればいい。結局最急降下法は
- を決める。
- となるを決める
- tex:{ \vec{x^(k+1)} = \vec{x^(k) - \alpha^{(k)} \nabla f(\vec{x^(k)})}]
- ステップ2に戻る
とまとめられた。
ニュートン法
最急降下法はの情報を利用せずに解を探索した。ニュートン法はの情報を利用するから、最急降下法よりも速い収束が期待できそう。というわけで、が出るような式変形としてテイラー展開を思い出すと、
と書ける。いまヘッセ行列は正定値と仮定すれば目的関数は凸関数のはずである。凸関数は勾配が0になる点で最適解を得るのが必要条件なのだから、式をで微分したとき、
となるようなは
と求まる。つまり、
を次の点とすればいい。結局ニュートン法をまとめると
- を選ぶ、ここで”いまヘッセ行列は正定値と仮定すれば目的関数は凸関数のはず”とあるのはスタート地点が適切でないと収束しない場合があるから。
- なら終了、そうでないならステップ2へ。
最急降下とニュートン法の性質
一旦略。