全文

(1)

数理計画法特論

田地宏一

Advanced Lectures on Mathematical Programming

目標

(非線形)最適化の理論を修得し,システムや制御 における最適化問題への応用を目指す.

(学部の)数理計画法と基礎数学15(と同等)の 知識を前提とする.

(2)

3

参考書等

今野,山下「非線形計画法」 日科技連 1978 福島「非線形最適化の基礎」 朝倉書店 2001 D.P. Bertsekas, E. Nedic and A.E. Ozdaglar,

‘Convex Analysis and Optimization’ Athena Scientific, 2003

I. Griva, S.G. Nash, A. Sofer, ‘Linear and Nonlinear Optimization, 2nd ed.’ SIAM, 2009

S. Boyd, L. Vandenberghe, ‘Convex Optimization,’

Cambridge University Press, 2004 他多数

pdf. free

おすすめ

4

1.数理計画問題

(3)

5

数理計画問題

与えられた制約条件の下で,目的関数を最小化

(または最大化)する数学モデル.

または

S x

x f 制約条件

最小(最大)

目的関数  ( )

S x

x f s.t.

) ( min

であり,

実行可能集合,feasible set (region)

実行可能解,feasible point (solution) 実行可能解の中で目的関数値が最小(または最 大)となる点を最適解 (optimal solution)

n n

n

f R R S R

R

x , : ,

: S

: S x

(4)

7

されることが多い のように数式の組で表

その他(整数制約など

等式制約 不等式制約

X x

l j

x h

m i

x g S

j i

) , , 1 (

, 0 ) (

) , , 1 (

, 0 ) (

X x

l j

x h

m i

x g R x

S j

i

n ( ) 0,( 1, , )

) , , 1 (

, 0 )

( 実行可能集合

(feasible set)

solution) (feasible

:実行可能解 S

x

8

局所的最適解と大域的最適解

) (x f

a S b c

は大域的最適解 は局所最適解,とくにb

c b a, ,

local (global) optimal solution optima (minima)

(5)

9

局所的最適解と大域的最適解

) (x f

は大域的最適解 は局所最適解,とくにb

c b a, ,

各点での近傍での(大域的)最適解

a S b c

応用

1.変分問題

懸垂線,最速降下線など 最適制御問題

T t

U t

u X t

x t

u t dt x

dx

dt u x t F T

x T

0

) ( , )

( )), ( ), ( ( s.t.

) , , ( ))

( (

min 0

(6)

11

2.学習,パターン認識,画像処理 ニューラル・ネットワーク,SVMなど 3.統計学,統計分析

最尤推定:尤度関数が最大となる統計量

回帰分析:二乗誤差が最小となる直線(曲面)

4.ファイナンス,金融工学

最小二乗法

12

5.構造・設計

トラスの構造・部材を決める

ロボットアームの長さ,配置,把持位置 6.運動制御・運動予測

トルク変化最小軌道,ジャーク最小軌道...

工学・経済学・医学・生物学・・・・などのあらゆる分 野にある

(7)

13

数理計画問題の分類

連続的:変数が連続的な実数値をとる

離散的:整数値や0-1などの離散値をとる(その ようなものを含む)

線形計画法は,両方の性質を持つ

線形計画 Linear Programming, LP 目的関数,制約条件がすべて一次式

非線形計画 Nonlinear Programming, NLP 目的関数や制約条件の中に一次式でないもの を含む

0 ,

s.t.

min T

x b Ax

x c

(8)

15

二次計画 Quadratic Programming, QP 目的関数が二次関数

制約条件はすべて一次式

Qが半正定値のとき,凸二次計画という

b Ax

x q Qx

x s.t.

2

min 1 T T

16

制御問題の例(LQR,モデル予測制御)

) 0

( )

( ,

s.t.

) ( )

( )

( )

( )

( )

(

min T

0

T T

T t M

t u m Bu

Ax x

dt t Ru t

u t

x Q t

x T

x Q T

x f T

離散化

) 1 ,

, 0 (

, s.t.

min

1

1 0

T T

T

N k

M u

m Bu Ax

x

Ru u

Qx x

x Q x

k k

k k

N k

k k

k k

N f N

Q :半正定値, R:正定値 凸二次計画 これは変分問題

(9)

17

整数計画法 Integer Programming, IP

決定変数 の一部または全部に整数制約が 付いたもの.

連続の場合より難しい

混合整数計画

Mixed Integer Programming, MIP

組合せ最適化 Combinatorial Optimization

xi

0 if

8 . 0

0 if

8 . s.t. 0

) 0 ,

, ( min

1

1 0

2 2

2

t t

t

t t

t t

N k

k t k

t N

t

x u

x

x u

x x

r q p ru

qx px

区分的アフィンシステムのモデル予測制御

0-1変数 と補助変数 をもちいて制約 条件を書き替える t

t z

十分大を追加 ただし M 0:

M x

M t

(10)

19

1 or 0

) 1

( ),

1 ( ,

,

6 . 1 8

. 0 s.t.

) 0 ,

, ( min

1

1 0

2 2

2

t

t t

t t t

t

t t

t t

t t

t t

t t

t t

N k

k t k

t N

t

M x

z M

x z

M z

M z

M x

M x

M

z u

x x

r q p ru

qx px

0-1混合整数計画問題

Mixed Integer Quadratic Programming, MIQP

は0,1以外の値をとらない

t

20

半正定値計画 Semidefinite Programming, SDP

制御系の解析: Linear Matrix Inequality, LMI 設計:Bilinear Matrix Inequality, BMI

:半正定値対称行列

n m

i

i i

S S

S

C A

S b

, 0 s.t.

max

1 T

(11)

21

システムの安定性

Ax x

リヤプノフの定理より,

0 s.t.

0 T

T A P PA

P P

ならば安定.これはLMI.

Sn

P P

PA P

A

I 0, 0,

s.t.

max

T

λ>0の解を持つことと,安定性が等価 等価なSDP

有界実補題(Bounded Real Lemma)

0 )

0 ( , , y Cx x Bu

Ax x

2 0

T

T T

I P

B

PB C

C PA

P A

H2ノルムがγ以下の必要十分条件

これもLMI

前述と同様の方法でSDPにできる

(12)

23

フィードバック安定化

Cx y

Bu Ax

x ,

出力フィードバック をもちいて安定化

変数 L P BMI→非線形(非凸)SDPとなる

Ly u

0 s.t.

0

T T

BLC A

P P

BLC A

P P

Sn

P P

BLC A

P P BLC A

I 0, 0,

s.t.

max

T

24

二次錐計画 Second Order Cone Programming, SOCP

0 , 1

2 2

2 2

1 x x x

x R

x n n

x2

x1

0

2のとき n

x3

x2 0

3のとき n

x1

二次錐 Lorentz 錐

(13)

25

二次錐計画=目的関数は線形,二次錐およびそれらの直 積を制約に含む

摩擦円錐の拘束=クーロン摩擦を考慮した力学系 凸二次不等式

凸二次計画問題

SDPやSOCPは非線形計画

T 0

TQx q x c x

0 ,

0 x xy

凸計画

Convex Programming

目的関数,制約式がすべて凸関数 LPSDPLMI),SOCPなどを含む

効率よい解法がある(商用・非商用多数)

technology’(技術)である 凸:理論的にも重要かつ美しい

(14)

27

今後の予定

多変数関数の微積分および線形代数のまとめ 凸集合と凸関数の基本的な性質

最適性条件と双対問題 以下はオプション

解法について,微分不可能な最適化,

S-procedure (S-lemma) KYP補題,学習制御 その他(要望に応えます)

28

本日のスライドおよび,

多変数関数の微積分と線形代数のまとめは http://www.uno.nuem.nagoya-

u.ac.jp/~taji/lecture/lecture.html にあります.

レポート問題なども随時追加します.

Updating...

参照

Updating...

関連した話題 :