知識科学研究科 知識システム構築論講座 林研究室 佛明 智

Presentation on theme: "知識科学研究科 知識システム構築論講座 林研究室 佛明 智"— Presentation transcript:

1 知識科学研究科 知識システム構築論講座 林研究室 佛明 智
最適化 知識科学研究科 知識システム構築論講座　林研究室 佛明　智

2 目次 数理計画法と最適値の探索 制約のない問題に対する手法 非線形計画法 最適制御 制御問題における最適化

3 “ある目的関数を最小にする解（最適解）を求める”
制約のない問題に対する手法 制約のない最小化問題とは “ある目的関数を最小にする解（最適解）を求める” と定義することができる．一般的に表現すると とかける．

4 大域的最小点と局所的最小点

5 勾配ベクトルとHesse行列 勾配ベクトル(gradient vector) Hesse行列(Hessian)

6 0次法，直線探索法 第1の方法は目的関数値のみを用いて探索方向を決める方法で，直接探索法または，0次法と呼ばれる．この方法は最小点の近傍での収束速度が遅く，全体としてあまり効率のよい方法ではない．

7 1次法 第2の方法は，目的関数の勾配ベクトルを利用して探索方向を決めるもので，最急降下法がその代表例である．この方法は，1次の導関数を利用していることから，1次法と呼ばれる．

8 2次法 第3の方法は，目的関数のHesse行列まで利用するもので，Newton法がその代表例である．この方法は，2次の導関数を利用していることから，2次法と呼ばれる．2次法では，Hesse行列を利用しているため，解の近傍での収束速度が速いという特徴がありますが，一方で計算が複雑になるため1ステップあたりの計算量が多いという欠点がある．

9 非線最適化のアルゴリズム 0次法 導関数を利用しない 直線探索，GA 1次法 1次の導関数を利用 最急降下法 2次法 2次の導関数を利用
Newton法, 準Newton法

10 ニュートン法

11 最急降下法

12 直線探索 ステップ幅を具体的に求めるために，初期点Xkより，最急降下法で求めた探索方向に沿って，最小点を通り越すまでだんだん増加させて進ませる．ここで微小な距離sを設定し，s,2s,4sのように進ませる．各々の点で関数値f(xi)を計算し，f(xi)<f(xi+1)となった時点で 　　xi-1=x1,xi+1=x2として黄金分割法に進む．

13 黄金分割法 黄金比

14 制御問題における最適化（1） 温度制御系

15 制御問題における最適化（2） 温度制御系のブロック線図

16 制御問題における最適化（3） 状態方程式 但し， 行列A(n×n) 列ベクトル 出力方程式 X(t) (n×1) b (n×1) 行ベクトル
　c (1×n)

17 最適制御 状態方程式，出力方程式 離散時間系 時間の離散的な値に対してのみ定義されるシステム 連続時間系
時間の連続的な値に対してのみ定義されるシステム 線形系 特に，状態方程式が線形の場合