[[数理計画法]]
- 一般の最適化問題
-- min. &mimetex(f(x));~
s.t. &mimetex(g_{i}(x)\leq 0);~
&mimetex(h_{j}(x) = 0);
- 特別な場合として、
-- &mimetex(g_{i},h_{j});がない⇒無制約最適化
-- &mimetex(f,g_{i});が凸関数、&mimetex(h_{i});が線形関数~
⇒許容領域が凸集合⇒凸計画,凸最適化~
凸最適化では局所最適解が大域的最適解。
--- 線形計画
--- 凸2次計画
--- 半正定値計画
-- 凸集合は任意の内部の2点を結んだ直線を含む集合。
-- 凸関数は定義域が凸集合で、~
定義域上の任意の2点&mimetex(x,y);と&mimetex(0\geq t \geq 1);について~
&mimetex(f((1-t)x+ty)\leq (1-t)f(x)+tf(y));となる関数。
- 無制約最適化~
一般の滑らかな関数を最小化する。~
min. &mimetex(f(x));~
-- どう解く？~
&mimetex(f(x));の値を減少させつつ、&mimetex(\mathrm{grad}f(x^{k})\to 0);となる点列&mimetex(\{x^{k}\});を探す。~
&mimetex(x^{k+1} = x^{k}-t^{k}B^{k}\mathrm{grad}f(x^{k}));~
&mimetex(B^{k});探索方向を定める正定値対称行列。~
&mimetex(t^{k});ステップ幅。
-- &mimetex(B^{k});の作り方。~
&mimetex(B^{k});は正定値対称行列を選ぶ。~
&mimetex(f(x^{k+1})-f(x^{k})=-t^{k}(\mathrm{grad}f(x^{k}))^{T}B^{k}\mathrm{grad}f(x^{k}) \leq 0);~
正定値対称なら十分に小さいステップ幅で常に減少方向。
--- 最急降下法~
&mimetex(B^{k}=I);
--- ニュートン法
&mimetex(B^{k}=\left\{\frac{\partial^2 f(x^{k})}{\partial x_{i} \partial x_{j}}\right\}^{-1});(ヘッセ行列の逆行列)~
この&mimetex(B^{k});は正定とは限らないが、簡単のためにここでは正定とする。~
&mimetex(\mathrm{grad}f(x)=0);という方程式をニュートン法で解くことに相当。~
2次収束する。局所最適解の充分近くで反復すると、~
一回の反復について誤差の大きさが2乗くらいになる。~
ヘッセ行列の計算が大変なのと、正定になるとは限らないことから、実用的にはあまり使われない。
--- 準ニュートン法~
ヘッセ行列やその逆行列を、反復情報から推定する。~
&mimetex(\mathrm{grad}f(x^{k+1})-\mathrm{grad}f(x^{k+1}) = \mathrm{grad grad}f(x^{k+1})(x^{k+1}-x^{k}) = (B^{k+1})^{-1}(x^{k+1}-x^{k}));~
&mimetex(B^{k+1}(\mathrm{grad}f(x^{k+1})-\mathrm{grad}f(x^{k+1})) = x^{k+1}-x^{k});~
となるように&mimetex(B^{k});から&mimetex(B^{k+1});を計算する。~
この手間はO(n^2)。~
ref)[[BFGS公式>http://zeus.mech.kyushu-u.ac.jp/~tsuji/java_edu/QNewton.html]],DFP公式
-- ステップ幅選択(直線探索)~
探索方向を決めた後、その方向にどれくらい進むかを決める。
--- 厳密直線探索~
min. &mimetex(x^{k}-tB^{k}\mathrm{grad}f(x^{k}));を解いて、その最適解を使う。
--- Armijo法~
&mimetex(f(x^{k}-2^{-l}B^{k}\mathrm{grad}f(x^{k}))\leq f(x^{k})-0.1\times 2^{-l}(\mathrm{grad}f(x^{k}))^{T}B^{k}\mathrm{grad}f(x^{k}));~
となる最小のlを使って、&mimetex(2^{-l});をステップ幅にする。~
線形近似がそこそこ成り立つ範囲で、できるだけ長いステップ幅をとっている。
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
