数理計画法（田地宏一） Introduction to Mathematical Programming 教科書：新版数理計画入門，福島雅夫，朝倉書店２０１１参考書：最適化法，田村，村松著，共立出版２００２工学基礎最適化とその応用，矢部著，数理工学社２００６など資料 http://www.uno.nuem.nagoya-u.ac.jp/~taji/lecture/lecture.html （または http://133.6.190.133/~taji/lecture/lecture.html） 2015/04/10 2 内容と今後の予定 1. 2. 3. 4. 5. 6. イントロ（例題と種類，機械系における例）線形計画法（定式化，図形的解法，シンプレックス法，二段解法，双対性）ネットワーク計画（ダイクストラ法，ネットワークシンプレックス法）非線形計画（無制約最適化のアルゴリズム，KKT条件と SQP法）組合せ最適化（分枝限定法）内点法と錐線形計画（LPの内点法，半正定値計画(ＳＤＰ）の理論，二次錐計画とSDPのアルゴリズム） 2015/04/10 3 １．数理計画モデル 2015/04/10 4 数理計画の手順解きたい問題数理モデル問題の修正修正線形モデル，非線形モデル，離散モデル，グラフ・ネットワーク，待ち行列，シミュレーション，統計モデル．．．．．解法・アルゴリズム 2015/04/10 答え 5 例題１（生産計画問題）３種類の原料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 であるとき，純益を最大とするようなⅠ，Ⅱの生産量を求めよ． 2015/04/10 6 製品Ⅰを x1製品Ⅱを x2生産するものとする．生産計画のデータ Ⅰ Ⅱ 総量 0.1x1 0.3x2 1.5 Ａ 0.1 0.3 1.5 Ｂ 1.2 0.5 6 1.2 x1 0.5 x2 6 Ｃ 0.4 0.3 2.4 0.4 x1 0.3 x2 2.4 純益 3 6 生産量は非負 2015/04/10 x1 0, 3 x1 6 x2 x2 0 最大化 7 まとめると最大化 3 + 6 制約条件 0.1 + 0.3 ≤ 1.5 1.2 + 0.5 ≤ 6 0.4 + 0.3 ≤ 2.4 ≥ 0, ≥0 線形計画問題（Linear Programming, LP） 2015/04/10 8 0 .1 0 .3 1 .2 0 .5 , b 0 .4 0 .3 A 1 .5 6 , c 2 .4 3 , 6 x x1 x2 とおくと，以下のように書ける（行列形式）． T max c x s.t. Ax b, x 0 2015/04/10 9 数理計画問題与えられた制約条件の下で，目的関数を最小化（または最大化）する数学モデル．目的関数　f ( x) 最小（最大）制約条件 x S または 2015/04/10 min f ( x) s.t. x S 10 n n n x R , f :R R, S R であり， S : 実行可能集合，feasible set (region) x S :実行可能解，feasible point (solution) 実行可能解の中で目的関数値が最小（または最大）となる点を最適解 2015/04/10 11 Sはg i ( x) 0, (i 1, h j ( x) 0, ( j 1, x X , m) 不等式制約 , l) 等式制約その他（整数制約など）のように数式の組で表されることが多い S x g i ( x) 0, (i 1, , m) R h j ( x) 0, ( j 1, , l) n x 実行可能集合 (feasible set) X x S：実行可能解(feasible solution) 2015/04/10 12 数理計画問題（再掲）以下のように表現される問題 min f ( x) s.t. g i ( x) 0, (i 1, , m) h j ( x) 0, ( j 1, , l) x 2015/04/10 X 13 応用１．変分問題懸垂線，最速降下線など最適制御問題 min s.t. 2015/04/10 ( x(T )) T 0 F (t , x, u )dt dx ( x(t ), u (t )), x(t ) dt 0 t T X , u (t ) U 14 ２．学習，パターン認識，画像処理ニューラル・ネットワーク，SVMなど３．統計学，統計分析最尤推定：尤度関数が最大となる統計量回帰分析：二乗誤差が最小となる直線（曲面）４．ファイナンス，金融工学最小二乗法 2015/04/10 15 ５．構造・設計トラスの構造・部材を決めるロボットアームの長さ，配置，把持位置翼の形状などなど工学・経済学・医学・生物学・・・・などのあらゆる分野にある 2015/04/10 16 数理計画問題のいろいろ（機械・制御系を中心に）連続的：変数が連続的な実数値をとる離散的：整数値や0-１などの離散値をとる（そのようなものを含む）線形計画法は，両方の性質を持つ 2015/04/10 17 線形計画 Linear Programming, LP 目的関数，制約条件がすべて一次式 T min c x s.t. Ax b, x 0 最初の生産計画の例もＬＰ非線形計画 Nonlinear Programming, NLP 目的関数や制約条件の中に一次式でないものを含む 2015/04/10 18 二次計画 Quadratic Programming, QP 目的関数が二次関数制約条件はすべて一次式 min s.t. 1 T T x Qx q x 2 Ax b Qが半正定値のとき，凸二次計画という（非線形計画の一つ） 2015/04/10 19 制御問題の例（LQR，モデル予測制御) T min x(T ) Q f x(T ) s.t. x 0 T T x(t ) Qx(t ) u (t ) Ru (t )dt Ax Bu , m u (t ) M (0 t T ) これは変分問題 min T x NT Q f x N 離散化 N 1 xkT Qxk u kT Ru k k 0 s.t. xk 1 Axk Bu k , m u k M (k 0, , N 1) Q ：半正定値， R：正定値 → 凸二次計画 2015/04/10 20 整数計画法 Integer Programming, IP 決定変数 xi の一部または全部に整数制約が付いたもの． → 連続の場合より難しい（組合せ最適化）混合整数計画 Mixed Integer Programming, MIP 組合せ最適化 Combinatorial Optimization 2015/04/10 21 区分的アフィンシステムのモデル予測制御 min pxt2 N N 1 qxt2 k rut2 k ( p, q, r 0) k 0 s.t. M xt 1 xt M 0.8 xt ut if xt 0 0.8 xt ut if xt 0 ただし M 0 : 十分大を追加０－１変数 t と補助変数 zt をもちいて制約条件を書き替える 2015/04/10 22 min 2 pxt N N 1 2 qxt k 2 rut k ( p, q, r 0) k 0 s.t. xt M 0.8 xt 1 xt t M , xt zt M t , zt zt xt t ut 1.6 zt M (1 M M t ), 0 or 1 t t t zt xt M (1 t) は０，１以外の値をとらない０－１混合整数計画問題 Mixed Integer Quadratic Programming, MIQP 2015/04/10 23 半正定値計画 Semidefinite Programming, SDP max b T s.t. S m i Ai C i 1 S 0, S n S ：半正定値対称行列制御系の解析： Linear Matrix Inequality, LMI 設計：Bilinear Matrix Inequality, BMI 2015/04/10 24 システムの安定性 x Ax リヤプノフの定理より， P P T T 0 s.t. A P PA 0 ならば安定．これはLMI．等価なSDP max s.t. I T A P PA 0, P 0, P S n λ＞０の解を持つことと，安定性が等価 2015/04/10 25 フィードバック安定化 x Ax Bu , y 出力フィードバック u P P T Cx Ly をもちいて安定化 0 T s.t. A BLC P P A BLC 0 変数 L と P のBMI→非線形（非凸）SDPとなる max s.t. 2015/04/10 I T A BLC P P A BLC 0, P 0, P S n 26 そのほかのモデルネットワーク計画最短路問題（カーナビの基礎），最大流問題，最小費用流問題，交通流割当問題などスケジューリング均衡問題などは，適宜説明します． 2015/04/10 27 今後の進め方資料は前日夜までにホームページに掲載します．当日持参することが望ましい．ほぼ毎回レポート課題がある（らしい）．数理計画に関して講義してほしいテーマ（例えば卒論関係でとか）があれば，申し出てください． 2015/04/10 28 補足：簡単な問題と難しい問題簡単な問題⇔凸計画線形計画（ＬＰ），凸二次計画，半正定値計画（ＳＤＰ）など効率のよい商用・非商用プログラムがある（後日，紹介します）難しい問題（ただし難しさのレベルはいろいろ）非凸最適化，組合せ最適化，均衡制約付き最適化問題（ＭＰＥＣ）など 2015/04/10 29