数理最適化特論／mathematical optimization（2018年度）

• 2018年度 秋学期 水曜 4時限（15:15〜16:45）
• 市ヶ谷キャンパス 本館 102号講義室
• 登録コードMSIS7210

1st lecture (Oct. 3)

• Guidance
• What is mathematical optimization?
  • Excel solver example
  • Python (PuLP) example
  • NEOS Solvers

10月10日は休講です．

代わりのレポート課題をいつか出します．

2nd lecture (Oct. 17)

• Linear optimization and simplex method (filled in version)

3rd lecture (Oct. 24)

• Linear optimization and dual (filled in version)

• Symbols
• Terms

4th lecture (Oct. 31)

• Integer optimization

5th lecture (Nov. 7)

• quiz01（出題範囲は2nd lectureと3rd lectureのexercise）
  • ちなみに昨年のquiz01
• 今回は，「Integer optimization」の「Directed graph and shortest s-t-path problem」から話します．
• NP-completeness

6th lecture (Nov. 14)

• Branch and bound

• Assignment 1

7th lecture (Nov. 21)

• Totally unimodular matrix and minimum cost flow

8th lecture (Nov. 28)

• Maximum flow and minimum cut
  • 今回は「Totally unimodular matrix and minimum cost flow」の「Integer flow and airline scheduling」を振り返るところから話します．

9th lecture (Dec. 5)

• quiz02（出題は7th lectureの12ページのExercise，定義と定理は予め問題用紙に書いておきます）
• Dynamic Programming
  • 今回は「Maximum flow and minimum cut」の「最大流と最小カット」から話します．

10th lecture (Dec. 12)

• Greedy algorithm
  • 今回はナップサック問題の最適解の最適性原理から再び話します．

11th lecture (Dec. 19)

• Quiz03（出題は8th lectureのExerciseと同等の問題とします．）
• Approximation algorithm
  • 今回は「Greedy algorithm」の7ページから話します．

12th lecture

• Assignment 2

13th lecture (Jan. 9)

• Second-Order Cone Optimization and Robust Optimization
  • 今回は「Approximation algorithm」の15ページから話します．

14th lecture (Jan. 16)

• Quiz04（出題は11th lectureのExercise（そのもの）です．）
• Support Vector Machine
  • 参考となる動画

Appendix

• Blackbox optimization

15th lecture

• Final assignment