数理最適化特論

博士前期課程理工学研究科 - 理工学専攻

MSIS7210

コース情報

担当教員: 宮本裕一郎

単位数: 2

年度: 2024

学期: 秋学期

曜限: 月3

形式: 対面授業

レベル: 500

アクティブラーニング: あり

他学部履修: 可

評価方法

レポート

20%

小テスト等

80%

詳細情報

概要

数理最適化はマネージメント・サイエンスやオペレーションズ・リサーチにおける有用な問題解決手法であり，近年は機械学習やデータサイエンスなどにも利用されている．本講義では，さまざまな問題を数理最適化問題としてモデル化する方法，およびモデル化した問題を解く方法を紹介する．キーワードは，線形最適化，整数最適化，ネットワークフロー，動的計画，貪欲解法，近似解法，二次錐最適化，Support Vector Machine(SVM)，非線形最適化などである．

目標

自らが何らかの問題に出会った時に，それが最適化問題としてモデル化できそうなものであれば，数理最適化問題としてモデル化できるようになることを目標とする．また，闇雲にモデル化するだけでなく，それぞれの数理最適化問題の理論的・現実的な難しさを意識しながらモデル化できるようになることを目標とする．さらに，数理最適化問題の解法の設計もできるようになることを発展的な目標とする．

授業外の学習

【予習】(30分) 教材に事前に目を通すなどの指示が教員からあった場合には，その指示に従い予習をする．【復習】(160分) 講義で得た知識を自ら整理し復習する．(30分) 講義中に示された演習問題を解く．講義回によっては小テスト(Quiz)に取り組む時間がこれに含まれることもある．(130分)

所要時間: 190

スケジュール

ガイダンス，数理最適化とは/Guidance, What is Mathematical Optimization?
線形最適化問題と単体法/Linear Optimization Problem and Simplex Method
線形最適化問題とその双対/Linear Optimization Problem and its Dual
整数最適化問題/Integer Optimization Problem
NP-困難性/NP-Hardness
整数最適化問題と分枝限定法/Integer Optimization Problem and Branch-and-Bound Method
最大流と最小カット定理/Maximum Flows and Minimum Cut Theorem
最小費用流問題と完全ユニモジュラー行列/ Minimum Cost Flows and Totally Unimodular Matrix
動的計画法/Dynamic Programming
貪欲解法/Greedy Algorithm
近似アルゴリズム/Approximation Algorithm
二次錐最適化/Second-Order Cone Optimization
Support Vector Machineと非線形最適化/Support Vector Machine and Non-Linear Optimization
数理最適化の最近の話題/Recent Topics

教科書

特定のテキストはないが，講義の中で参考文献を随時紹介する．

参考書

書籍情報はありません。