| 英文名 | Optimization | |
|---|---|---|
| 科目概要 | 未来工学研究科（修士課程）生命データサイエンス専攻修士１年～２年後期、専門科目、選択、講義、2単位 |
|
| 科目責任者 | 榊原 康文 | |
| 担当者 | (※は実務経験のある教員) 榊原 康文、 |
|
| 講義室 | ||
世の中の多くの問題は最適化問題として定式化できる。機械学習や回帰、最尤法などのモデルのデータへのフィッティングも実は最適化の問題である。最適化は、与えられた制約条件の下で、ある目的関数を最大（小）にする解を見出すことであり、そのためのアルゴリズムを設計する分野である。本講義では、最適化の先端知識と考え方を学ぶ。
線形計画問題から始めて、凸計画，非線形最適化，ネットワーク計画，近似解法・発見的解法，整数計画といった代表的な最適化問題を体系的に扱い、そのために設計されたアルゴリズムについて理解する。
教科書を指定し、その内容について理解を深めるためにパワーポイントや板書及び輪講形式による講義を行う。また数回程度のレポート課題を行い、最適化の知識と考え方の定着を図る。
レポート課題等のフィードバックは、次回講義や講義のwebページ等で共有する。
DP2
| 回 | 項目 | 内容 | 担当者 |
|---|---|---|---|
| 1 | イントロダクション | 最適化問題の定式化 | 榊原 康文 秋山 真那斗 |
| 2 | 線形計画法（１） | 線形計画問題、基底解と最適解、シンプレックス法 | 榊原 康文 秋山 真那斗 |
| 3 | 線形計画法（２） | シンプレックス法の収束性、双対定理 | 榊原 康文 秋山 真那斗 |
| 4 | 線形計画法（３） | シンプレックス法の効率化の演習 | 榊原 康文 秋山 真那斗 |
| 5 | 凸2次計画 | 凸2次計画問題，KKT条件 | 榊原 康文 秋山 真那斗 |
| 6 | 非線形最適化（１） | 無制約最適化，勾配法，ニュートン法 | 榊原 康文 秋山 真那斗 |
| 7 | 非線形最適化（２） | 制約付き最適化，ラグランジュ法，逐次2次計画法 | 榊原 康文 秋山 真那斗 |
| 8 | 非線形最適化（３） | 無制約／制約付き最適化の計算演習，逐次2次計画法の例題 | 榊原 康文 秋山 真那斗 |
| 9 | 凸最適化 | 凸集合と凸関数，凸計画問題 | 榊原 康文 秋山 真那斗 |
| 10 | ネットワーク計画（１） | グラフの基礎，最短路問題 | 榊原 康文 秋山 真那斗 |
| 11 | ネットワーク計画（２） | 最小木問題，階層的クラスタリング | 榊原 康文 秋山 真那斗 |
| 12 | ネットワーク計画（３） | 最短路・最小木・最小費用流の計算演習 | 榊原 康文 秋山 真那斗 |
| 13 | 近似解法 | 厳密解法と近似解法，ナップサック問題，近似保証 | 榊原 康文 秋山 真那斗 |
| 14 | 発見的解法 | 非階層的クラスタリング，劣モジュラ最大化問題，メタ戦略など代表的ヒューリスティクス | 榊原 康文 秋山 真那斗 |
| 15 | 整数計画 | 整数計画問題，分枝限定法の基礎と計算演習 | 榊原 康文 秋山 真那斗 |
最適化問題の定式化とそれを解放するアルゴリズムを理解し、応用ができるようになる。
期末試験（70％）とレポート課題（30％）の結果から総合的に判断する。
【講義時間外に必要な学修時間：60時間】
予習：講義中に事前に指定する次回講義内容について教科書を読み、疑問点を明らかにしておくこと。また輪講形式の回については、事前に内容をパワーポイントにまとめておく。
復習：講義中に出題する演習課題について解答を作成し、次回の講義中に示す模範解答と比較・検討する。
講義内容に不安がある場合は、学部科目の「人工知能・機械学習入門」を聴講することを推奨する。
【関連科目：生命科学と機械学習、最適化プログラミング、データモデリング特論】
| 種別 | 書名 | 著者・編者 | 発行所 |
|---|---|---|---|
| 教科書 | 最適化手法入門 | 寒野善博（著）、駒木文保（編） | 講談社 |
| 参考書 | 必要に応じて講義内で指示する。 |