Document

システム最適化特論
担当：平田健太郎
第10回（6/15）
１．グラフとネットワークにおける数理
・組合せ最適化（3）
２．システム制御と最適化
・最適制御とDP
1
講義日程（予定）
4/13 １．グラフとネットワークにおける数理
・輸送問題とLP
4/20
・シンプレックス法（１）
4/27
・シンプレックス法（２）, 双対問題
5/7
・多項式時間アルゴリズム, 内点法（１）
5/11
・内点法（２）
5/18
・最短経路問題とダイクストラ法（１）
5/25
6/1
6/8
・最短経路問題とダイクストラ法（２）
・組合せ最適化（１）
・組合せ最適化（２）
2
6/15
・組合せ最適化（3）
２．システム制御と最適化
・最適制御とDP
6/22
・凸解析と線形行列不等式
6/29
・最適制御再訪
7/6
・ LMIによる制御系解析・設計
7/13
・非線形最適化（１）
7/27
・非線形最適化（２）
（8/3）
（期末レポート提出）
＊期末試験はレポートとする
3
例4: 巡回セールスマン問題
8
1
7
4
2
4
4
5
8
3
動的計画法（ダイナミックプログラミング）による解法：
最適制御問題の導入も兼ねて
4
動的計画法（Dynamic Programming）
離散過程に対する多段階決定問題
状態 𝑥 に決定 𝑢 を与えたときの状態遷移： 𝑓(𝑥, 𝑢)
𝑥2 = 𝑓(𝑥1 , 𝑢1 )
𝑥3 = 𝑓(𝑥2 , 𝑢2 )

𝑥𝑁 = 𝑓(𝑥𝑁−1 , 𝑢𝑁−1 )
各段階におけるコスト： 𝐿 𝑥𝑘 , 𝑢𝑘 , 𝑘 = 1, ⋯ , 𝑁
𝑁
𝐿 𝑥𝑘 , 𝑢𝑘
和
を最小にするよう 𝑢𝑘 を選ぶ.
𝑘=1
5
N段決定過程の最小和
𝐽𝑁 𝑥1 = min 𝐿 𝑥1 , 𝑢1 + ⋯ + 𝐿 𝑥𝑁 , 𝑢𝑁
𝑢𝑘
= min min ⋯min 𝐿 𝑥1 , 𝑢1 + ⋯ + 𝐿 𝑥𝑁 , 𝑢𝑁
𝑢1
𝑢2
𝑢𝑁
= min 𝐿 𝑥1 , 𝑢1 + min ⋯ min 𝐿 𝑥2 , 𝑢2 ⋯ + 𝐿 𝑥𝑁 , 𝑢𝑁
𝑢1
𝑢2
𝑢𝑁
= min 𝐿 𝑥1 , 𝑢1 + 𝐽𝑁−1 𝑥2
𝑢1
= min 𝐿 𝑥1 , 𝑢1 + 𝐽𝑁−1 𝑓(𝑥1 , 𝑢1 )
𝑢1
N-1段決定過程
の最小和
6
動的計画法による解法
巡回セールスマン問題に対する最適性の原理
8
1
7
4
2
4
4
5
8
3
8
8
1
7
4
2 5
4 8
3
4
S 1
S 2
9
S 3
8
1
7
4
5
4 8
3
4
2
10
ヒューリスティック解法（発見的解法）
NP困難な問題に対しては厳密解をあきらめて，比較的短時間で
よい近似解が得られればよしとする．
最近近傍法
ある節点から出発点して，まだ訪問していない隣接節点の
なかで現在の節点に最も近い節点へ次々と移動していく．
（欲張り法）
8
1
7
4
2 5
4 8
3
4
1から出発すると1⇒3⇒2⇒4⇒1（最適解！）
3から出発すると, 1と２は同距離
3⇒1⇒2⇒4⇒3（最適でない）
3⇒2⇒4⇒1⇒3（最適）
11
ヒューリスティック解法によって得た近似解を部分的に修正して，よ
りよい近似解を求める
⇒メタヒューリスティックス（主として局所探索法）
近似解
2-opt 法: 得られている巡回路から隣接し
ない2本の枝を選んで別の2本と変える
3-opt 法:
etc …
12
局所解に囚われないための工夫
シミュレーテッド・アニーリング法
温度のパラメータを定め，高温時には目的関数値を悪化させ
るような遷移もある確率で許す．
タブー探索法
一度探索した領域をタブーリストに加えて，再度探索しない
ようにする
その他にもいろいろな探索アルゴリズムがある.
遺伝アルゴリズム(GA, Genetic Algorithm),
PSO(Particle Swarm Optimization), NN (Neural Network)
etc…
13
２．システム制御と最適化
・最適制御とDP
14
制御系設計においては, 各種性能の最大化が求めら
れる. これは最適化問題に他ならない.
また, ある仕様を満足するような設計問題は, 目的関
数を持たない実行可能解の探索問題（feasibility
problem）と見ることができる.
まずは典型例として, いわゆる最適制御問題を考える.
15
 最適制御問題 (一般形, 非線形）
制御入力 𝑢(𝑡)
システム
（内部状態 𝑥 𝑡 )
出力
システムの動特性は（非線形な）常微分方程式で与えられるとする.
状態方程式
終端条件の重み関数
状態，制御入力の重み関数
16
線形系
一般形
状態方程式
評価関数
𝑥 𝑡 = 𝐴𝑥 𝑡 + 𝐵𝑢(𝑡)
𝐽 = 𝑥 𝑇 𝑇 𝑄𝑓 𝑥 𝑇
𝑇
+
𝑥 𝑇 𝑡 𝑄𝑥 𝑡 + 𝑢𝑇 𝑡 𝑅𝑢 𝑡 𝑑𝑡
0
(2次評価関数)
17
最適性の原理
min 𝐽
𝑢(⋅)
s. t. 𝑥 𝑡 = 𝑓(𝑥 𝑡 , 𝑢 𝑡 )
18
動的計画法に基づく最適条件の導出
最適コスト関数
積分区間を分割
最適性の原理から
19
最適コスト関数
（離散時間の場合の次式に相当）
𝐽𝑁 𝑥1 = min 𝐽𝑁−1 𝑥2 + 𝐿 𝑥1 , 𝑢1
𝑢1
𝑥(𝜏)
𝑥(𝜏1 )
𝑥1
𝑥2
20
とし, 右辺第1項をテーラー展開する. （2変数関数）
第2項については
中の
を
と近似し,
𝜕𝐽∗
𝜕𝐽∗
= − min
𝑢 𝜏 ∈𝑈 𝜕𝑥
𝜕𝜏
の極限をとる.
𝑇
𝑓 𝑥 𝜏 ,𝑢 𝜏
+ 𝐿(𝑥 𝜏 , 𝑢 𝜏 )
21
𝜕𝐽∗
𝜕𝜏
= − min
𝑢 𝜏 ∈𝑈
𝑇
∗
𝜕𝐽
𝜕𝑥
𝑓 𝑥 𝜏 ,𝑢 𝜏
右辺を最小化する 𝑢 は 𝑥(𝜏) と
𝑢 𝑥 𝜏
𝜕𝐽∗
,
𝜕𝑥
𝜕𝐽∗
𝜕𝑥
+ 𝐿(𝑥 𝜏 , 𝑢 𝜏 )
に依存するので, これを
とおくと
最適であるための必要条件 (十分性もいえる)
22
一般に, 非線形偏微分方程式であるHJ方程式を
解析的に解くことは困難 ⇒ 線形システムに限定
23
平方完成
右辺を最小化する
24
-1 ×
𝑇 → ∞ （定常解）⇒ 代数リカッチ方程式
25

Download Report