1. No category

知能ロボット設計論
担当：平田 健太郎
第5回 （5/12）
１．グラフとネットワークにおける数理
・ 主双対内点法
Design of Intelligent Robot
1
Schedule
4/14 １．グラフとネットワークにおける数理
・ 輸送問題とLP
4/21
・ シンプレックス法（１）
4/28
・ シンプレックス法（２）, 最大流/最小費用流問題
5/8
・ 双対問題
5/12
・ 多項式時間アルゴリズム, 内点法
5/19
5/26
6/2
・ 最短経路問題とダイクストラ法
・ 組合せ最適化（１）
・ 組合せ最適化（２）
Design of Intelligent Robot
2
逆向きの証明は…
標準形へ
変換
同値
1. (D) が最適解をもつとき
同値
x
min c~ T ~
~
~
subject to A ~
x = b,~
x ≥0
とおけば
2. これが最適解をもつ
双対問題
3. 先と同じ議論から
これが最適解をもつ
min cT x
同値
Design of Intelligent Robot
subject to A x = b, x ≥ 0
4. よって, これが最適解をもつ
5
主問題に依存して双対問題の形も変わる
Design of Intelligent Robot
6
双対問題の解釈
価格設定に矛盾がない
Design of Intelligent Robot
7

多項式時間アルゴリズム
• その計算量が変数の数，制約条件の数などの問題の規模を表す
パラメータの多項式関数で表されるもの
• 一般的に“効率的な”アルゴリズムとみなされる
• シンプレックス法 (1947)
反復回数は（経験的に）制約条件数の1.5倍から3倍
⇒ 実用上は問題なし. 人工的なある種の問題に対しては問題の
サイズにつれて計算量が爆発的に増加. 多項式時間アルゴリズム
であるとはいえない.
•
楕円体法 (1979 Khachiyan)
線形計画問題に対する初めての多項式時間アルゴリズム. 実際の計算
効率ではシンプレックス法に劣る.
Design of Intelligent Robot
8
• 楕円体法
(a) 変数の空間において，最適解を確実に含むと考えられる楕円体を
見つける
(b) その楕円体を二つの半楕円体に分け, 最適解を確実に含んでいる
と考えられる半楕円体を選ぶ
(c) 得られた半楕円体を含む最小の楕円体を構成, (b)に戻る
• 内点法 (1984 Karmarkar)
新しい多項式時間アルゴリズム. 大規模な問題に対してはシンプレッ
クス法をしのぐ方法として評価が定着している.
⇒ システム制御工学における近年の動向 （LMI approach
の普及）にも関与
Design of Intelligent Robot
9
内点法 (Interior Point Method)
Design of Intelligent Robot
10

パス追跡・主双対内点法
主問題 primal problem (P)
双対問題 dual problem (D)
双対問題
Design of Intelligent Robot
(D’)
11
双対定理より
スカラ量
少なくとも一方は0： 相補性条件
Design of Intelligent Robot
12
線形相補性問題
非線形
パス追跡法
Design of Intelligent Robot
13
(Newton法)
高速化のための線型方程式を解く工夫等はあるが，ここでは触れない
Design of Intelligent Robot
14
Karmarkar法: 対数障壁関数を用いたポテンシャル関数の値で最適解からの
誤差を測り, 射影変換 を用いて探索方向を決定.
非線形計画
Design of Intelligent Robot
15
Design of Intelligent Robot
16
既に前章でも触れたスタンフォー
ド大学グループの研究は、 α と D
を適当に決めてやると、フィアッコ
＝マコーミックの障壁関数法が得
られることを示したものである。
Design of Intelligent Robot
17
バリア関数（ペナルティ）法
制約条件：
バリア関数：
− log(− f i ( x))
制約領域
の境界
− f i (x)
制約領域の内側
Design of Intelligent Robot
18
バリア関数と（線形）評価関数を合成
バリア関数の値
合成した値
バリア関数の
等高線
Design of Intelligent Robot
19
バリア関数（ペナルティ）法
原問題 (制約つき）
制約なし問題 （等価）
バリア関数
対数バリア関数（微分可能）
制約なし問題 （近似）
制約なし非線形最適化
Design of Intelligent Robot
20
Karmarkar法: 対数障壁関数を用いたポテンシャル関数の値で最適解からの
誤差を測り, 射影変換 を用いて探索方向を決定.
非線形計画
射影変換法
アフィン変換法
60年代に先行研究(ディキン(ロシア))
AT&Tの特許戦略: 制約領域の内部を通るものなら
どんなものであれ特許侵害とみなす
主双対内点法
対抗ソフト OB1 (5万ドル) 登場
Design of Intelligent Robot
21
Newton法
非線形方程式の求解 f ( x) = 0
f (x)
非線形関数値の最小化 g ′( x) = 0
g (x)
f ′( x1 )
x2
x1
x2
f ( x1 )
∆x = −
f ′( x1 )
g ( x) ≅ g ( x1 ) + g ′( x1 )∆x +
∆x = −
1
g ′′( x1 )(∆x) 2 と近似
2
2

g ′( x1 ) 
1
 + c
= g ′′( x1 ) ∆x +
′
′
g ( x1 ) 
2

Design of Intelligent Robot
x1
最小化
g ′( x1 )
g ′′( x1 )
∆x の計算
⇒線形方程式の求解
g ′′( x1 )∆x = − g ′( x1 )
22