最適化手法

9/28 最適化問題の分類と基礎 モデリング・定式化・具体例 無制約最適化の最適性条件 10/5 直線探索法 最急降下法 大域的収束性 10/12 Newton法 Newton法 収束の速さ 10/19 その他の解法 準Newton法 信頼領域法 凸関数 10/26 制約付き最適化 最適性条件 Lagrange未定乗数法 11/2 不等号制約付き最適化(理論) KKT条件 凸計画問題 11/9 Lagrange双対問題 11/30 不等号制約付き最適化(解法) ペナルティ法 拡張Lagrange未定乗数法 内点法 12/7 整数計画問題 定式化 分枝限定法 12/14 組合せ最適化入門 アルゴリズムの効率性 最小全域木問題 12/21 最短路問題 深さ優先探索 Dijkstra法 Bellman-Ford法 1/4 ネットワーク最適化 最大流問題 1/7 難しい問題に対する解法 近似アルゴリズム メタヒューリスティックス 9/28 Introduction 10/5 Line search method 10/12 Newton method 10/19 Quasi-Newton method and trust-region method 10/26 Optimization with equality constraints 11/2 Constrained optimization (theory) 11/9 Lagrange dual problems 11/30 Constrained optimization (algorithms) 12/7 Integer programming 12/14 Introduction to combinatorial optimization 12/21 Network optimization (shortest path problem) 1/4 Network optimization (maximum flow problem) 1/7 Algorithms for hard problems

講義はオンライン形式105分で行う。

試験およびレポートで評価を行う。

寒野善博, 土谷隆: 最適化と変分法 （東京大学工学教）

寒野 善博 : 最適化手法入門, 講談社. 繁野麻衣子: ネットワーク最適化とアルゴリズム, 朝倉書店. Jon Kleiberg and Eva Trados: Algorithm Design (共立出版より訳本あり). Jorge Nocedal and Stephen Wright: Numerical Optimization, Springer, 2nd ed., 2006

基礎を固める（工学部共通）