非線形最適化
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
] [
リンク元
]
開始行:
[[数理計画法]]
- 一般の最適化問題
-- 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 ...
&mimetex(f((1-t)x+ty)\leq (1-t)f(x)+tf(y));となる関数。
- 無制約最適化~
一般の滑らかな関数を最小化する。~
min. &mimetex(f(x));~
-- どう解く？~
&mimetex(f(x));の値を減少させつつ、&mimetex(\mathrm{grad}...
&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})...
正定値対称なら十分に小さいステップ幅で常に減少方向。
--- 最急降下法~
&mimetex(B^{k}=I);
--- ニュートン法
&mimetex(B^{k}=\left\{\frac{\partial^2 f(x^{k})}{\partial...
この&mimetex(B^{k});は正定とは限らないが、簡単のためにこ...
&mimetex(\mathrm{grad}f(x)=0);という方程式をニュートン法...
2次収束する。局所最適解の充分近くで反復すると、~
一回の反復について誤差の大きさが2乗くらいになる。~
ヘッセ行列の計算が大変なのと、正定になるとは限らないこと...
--- 準ニュートン法~
ヘッセ行列やその逆行列を、反復情報から推定する。~
&mimetex(\mathrm{grad}f(x^{k+1})-\mathrm{grad}f(x^{k+1}) ...
&mimetex(B^{k+1}(\mathrm{grad}f(x^{k+1})-\mathrm{grad}f(x...
となるように&mimetex(B^{k});から&mimetex(B^{k+1});を計算...
この手間はO(n^2)。~
ref)[[BFGS公式>http://zeus.mech.kyushu-u.ac.jp/~tsuji/jav...
-- ステップ幅選択(直線探索)~
探索方向を決めた後、その方向にどれくらい進むかを決める。
--- 厳密直線探索~
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(...
となる最小のlを使って、&mimetex(2^{-l});をステップ幅にす...
線形近似がそこそこ成り立つ範囲で、できるだけ長いステップ...
終了行:
[[数理計画法]]
- 一般の最適化問題
-- 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 ...
&mimetex(f((1-t)x+ty)\leq (1-t)f(x)+tf(y));となる関数。
- 無制約最適化~
一般の滑らかな関数を最小化する。~
min. &mimetex(f(x));~
-- どう解く？~
&mimetex(f(x));の値を減少させつつ、&mimetex(\mathrm{grad}...
&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})...
正定値対称なら十分に小さいステップ幅で常に減少方向。
--- 最急降下法~
&mimetex(B^{k}=I);
--- ニュートン法
&mimetex(B^{k}=\left\{\frac{\partial^2 f(x^{k})}{\partial...
この&mimetex(B^{k});は正定とは限らないが、簡単のためにこ...
&mimetex(\mathrm{grad}f(x)=0);という方程式をニュートン法...
2次収束する。局所最適解の充分近くで反復すると、~
一回の反復について誤差の大きさが2乗くらいになる。~
ヘッセ行列の計算が大変なのと、正定になるとは限らないこと...
--- 準ニュートン法~
ヘッセ行列やその逆行列を、反復情報から推定する。~
&mimetex(\mathrm{grad}f(x^{k+1})-\mathrm{grad}f(x^{k+1}) ...
&mimetex(B^{k+1}(\mathrm{grad}f(x^{k+1})-\mathrm{grad}f(x...
となるように&mimetex(B^{k});から&mimetex(B^{k+1});を計算...
この手間はO(n^2)。~
ref)[[BFGS公式>http://zeus.mech.kyushu-u.ac.jp/~tsuji/jav...
-- ステップ幅選択(直線探索)~
探索方向を決めた後、その方向にどれくらい進むかを決める。
--- 厳密直線探索~
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(...
となる最小のlを使って、&mimetex(2^{-l});をステップ幅にす...
線形近似がそこそこ成り立つ範囲で、できるだけ長いステップ...
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
