Microsoft PowerPoint - no1_17

(1)

数理計画法

（田地宏一）

Introduction to Mathematical

Programming

2 2017/04/14 教科書：新版数理計画入門，福島雅夫，朝倉書店２０１１参考書：最適化法，田村，村松著，共立出版２００２工学基礎最適化とその応用，矢部著，数理工学社２００６，Linear and Nonlinear

Optimization: second edition, I.Griba, S.G. Nash and A. Sofer, SIAM 2009 など多数資料 http://www.uno.nuem.nagoya-u.ac.jp/~taji/lecture/lecture.html （またはhttp://133.6.190.133/~taji/lecture/lecture.html）

(2)

3 2017/04/14

内容と今後の予定

1. イントロ（例題と種類，機械系における例） 2. 線形計画法（定式化，図形的解法，シンプレックス法，二段解法，双対性） 3. ネットワーク計画（ダイクストラ法，ネットワークシンプレックス法） 4. 非線形計画（無制約最適化のアルゴリズム，KKT条件と SQP法） 5. 組合せ最適化（分枝限定法） 6. 内点法と錐線形計画（LPの内点法，半正定値計画（ＳＤＰ）の理論，二次錐計画とSDPのアルゴリズム） 4 2017/04/14

１．数理計画モデル

(3)

数理計画の手順

5 2017/04/14 解きたい問題数理モデル線形モデル，非線形モデル，離散モデル，グラフ・ネットワーク，待ち行列，シミュレーション，統計モデル．．．．．解法・アルゴリズム修正問題の修正答え 6 2017/04/14

例題１（生産計画問題）

３種類の原料A,B,C,を加工して２種類の製品Ⅰ，Ⅱを作る． Ⅰを１単位作るには，Aが0.1単位，B 1.2単位，C 0.4単位必要である． Ⅱを１単位作るには，A 0.3単位，B 0.5単位，C 0.3 単位必要である．原料A,B,Cの在庫はそれぞれ，1.5，6，2.4である． Ⅰ，Ⅱの純益がそれぞれ 3, 6 であるとき，純益を最大とするようなⅠ，Ⅱの生産量を求めよ．

(4)

7 2017/04/14 Ⅰ Ⅱ 総量Ａ 0.1 0.3 1.5 Ｂ 1.2 0.5 6 Ｃ 0.4 0.3 2.4 純益 3 6

最大化

2 1 2 1 2 1 2 1 2 1

6

3

0 ,

0

4 .

2

3 .

0

4 .

0

6

5 .

0

2 .

1

5 .

1

3 .

0

1 .

0 x

x

製品Ⅰを製品Ⅱを生産するものとする．生産計画のデータ生産量は非負 1

x

₂

まとめると

最大化 3 + 6 制約条件 0.1 + 0.3 ≤ 1.5 1.2 + 0.5 ≤ 6 0.4 + 0.3 ≤ 2.4 ≥ 0, ≥ 0 線形計画問題（_{Linear Programming, LP）} 8 2017/04/14

(5)

9 2017/04/14 2 1 , 6 3 , 4 . 2 6 5 . 1 , 3 . 0 4 . 0 5 . 0 2 . 1 3 . 0 1 . 0 x x x c b A とおくと，以下のように書ける（行列形式）．

0 ,

s.t.

max

T

x

b

Ax

x

c

10 2017/04/14

数理計画問題

与えられた制約条件の下で，目的関数を最小化（または最大化）する数学モデル．または S x x f 制約条件最小（最大）目的関数　 ( )

S

x

f

s.t.

)

(

min

(6)

11 2017/04/14

であり，実行可能集合，feasible set (region)

実行可能解，feasible point (solution)

実行可能解の中で目的関数値が最小（または最大）となる点を最適解 n n n

_f

_R

_S

_R

R

x

,

:

,

:

S

:

S

x

されることが多いのように数式の組で表）その他（整数制約など等式制約不等式制約は 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

₍

₎

₀

_,

₍

₁

_,

₎

)

,

1 (

,

0 )

(

実行可能集合 (feasible set) solution) (feasible ：実行可能解 S x 2017/04/14 12

(7)

13 2017/04/14

数理計画問題（再掲）

X

x

l

j

x

h

m

i

x

g

x

f

j i

)

,

1 (

,

0 )

(

)

,

1 (

,

0 )

(

s.t.

)

(

min

以下のように表現される問題

応用

１．変分問題懸垂線，最速降下線など最適制御問題 T t U t u X t x t u t x dt dx dt u x t F T x T 0 ) ( , ) ( )), ( ), ( ( s.t. ) , , ( )) ( ( min 0 2017/04/14 14

(8)

２．学習，パターン認識，画像処理ニューラル・ネットワーク，SVMなど 2017/04/14 15 ３．統計学，統計分析最尤推定：尤度関数が最大となる統計量回帰分析：二乗誤差が最小となる直線（曲面）４．ファイナンス，金融工学

最小二乗法

2017/04/14 16

(9)

５．構造・設計トラスの構造・部材を決めるロボットアームの長さ，配置，把持位置翼の形状などなど工学・経済学・医学・生物学・・・・などのあらゆる分野にある 2017/04/14 17

数理計画問題のいろいろ（機械・

制御系を中心に）

連続的：変数が連続的な実数値をとる離散的：整数値や0-１などの離散値をとる（そのようなものを含む）線形計画法は，両方の性質を持つ 2017/04/14 18

(10)

線形計画 Linear Programming, LP 目的関数，制約条件がすべて一次式最初の生産計画の例もＬＰ非線形計画 _{Nonlinear Programming, NLP} 目的関数や制約条件の中に一次式でないものを含む

0 ,

s.t.

min

T

x

b

Ax

x

c

2017/04/14 19 二次計画 _{Quadratic Programming, QP} 目的関数が二次関数制約条件はすべて一次式 Qが半正定値のとき，凸二次計画という（非線 形計画の一つ）

b

Ax

x

q

Qx

x

s.t.

2

1 min

T T 2017/04/14 20

(11)

制御問題の例（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：正定値 → 凸二次計画 これは変分問題 2017/04/14 21 整数計画法 _{Integer Programming, IP} 決定変数の一部または全部に整数制約が付いたもの． → 連続の場合より難しい（組合せ最適化）混合整数計画

Mixed Integer Programming, MIP

組合せ最適化 _{Combinatorial Optimization}

i

x

(12)

0 if 8 . 0 0 if 8 . 0 s.t. ) 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 区分的アフィンシステムのモデル予測制御０－１変数と補助変数をもちいて制約条件を書き替える t

z

t 十分大を追加ただし _M ₀_: M x M _t 2017/04/14 23 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 ０－１混合整数計画問題

Mixed Integer Quadratic Programming, MIQP

は０，１以外の値をとらない

t

(13)

半正定値計画 Semidefinite Programming, SDP

制御系の解析： Linear Matrix Inequality, LMI

設計：Bilinear Matrix Inequality, BMI

：半正定値対称行列

n m i i i

S

C

A

S

b

,

0 s.t.

max

1 T 2017/04/14 25 システムの安定性

Ax

x

リヤプノフの定理より，

0 s.t.

0

T T

_A

_P

_PA

P

ならば安定．これはLMI． n S P P PA P A I 0, 0, s.t. max T λ＞０の解を持つことと，安定性が等価等価なSDP 2017/04/14 26

(14)

フィードバック安定化

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 n S P P BLC A P P BLC A I 0, 0, s.t. max T 2017/04/14 27

そのほかのモデル

ネットワーク計画最短路問題（カーナビの基礎），最大流問題，最小費用流問題，交通流割当問題などスケジューリング均衡問題などは，適宜説明します． 28 2017/04/14

(15)

補足：簡単な問題と難しい問題

簡単な問題⇔凸計画線形計画（ＬＰ），凸二次計画，半正定値計画（ＳＤＰ）など効率のよい商用・非商用プログラムがある（後日，紹介します）難しい問題（ただし難しさのレベルはいろいろ）非凸最適化，組合せ最適化，均衡制約付き最適化問題（ＭＰＥＣ）など 29 2017/04/14

今後の進め方

資料は前日までにホームページに掲載します．当日持参することが望ましい．ほぼ毎回レポート課題がある（らしい）．数理計画に関して講義してほしいテーマ（例えば卒論関係でとか）があれば，申し出てください． 30 2017/04/14

(16)

31 2017/04/14

演習課題

本日のスライド_{23ページの問題（区分的アフィ} ンシステム）と_{24ページの問題（その０－１混合} 整数計画版）が等価であることを説明せよ．締切：4月20日(木)16：00 Ⅳ系事務室