2024年度学院等開講科目情報理工学院数理・計算科学系

数理最適化

開講元: 数理・計算科学系
担当教員: 山下真 / 藤澤克樹 / 澄田範奈 / 横井優 / LIU TIANXIANG
授業形態: 講義/演習 (対面型)
メディア利用科目: -
曜日・時限 (講義室): 月3-6 (W8E-308(W834)) / 木3-4 (W8E-308(W834))
クラス: -
科目コード: MCS.T302
単位数: 210
開講時期: 2024年度
開講クォーター: 1Q
シラバス更新日: 2025年3月14日
使用言語: 日本語

シラバス

授業の目的（ねらい）、概要

この科目は講義と演習からなる。講義の部分では、数理最適化モデルの基礎となっている線形計画問題について、代表的な解法であるシンプレックス法および双対定理などの理論面を扱う。非線形最適化では、最適解の満たす最適性条件の理論的性質についてふれた後、最急降下法や内点法などの計算手法を扱う。演習の部分では、シンプレックス法を実際に線形計画問題に適用し、その手順を確認する。また、講義内容の証明の一部などを行うことで、理論面の理解を深める。

数理最適化は、「特定の条件を満たす中から、最適な解を選び出す」という最適化に数学的なアプローチを行う学問であり、理学・工学の諸問題と密接に関係しているだけでなく、実社会に幅広く用いられている。例えば、必要なエネルギーを確保する食事メニューの中から、最小カロリーとなっているメニューを選び出す、などのようなダイエット問題を数学でどのように解くか、というようなことが考えられる。実社会の最適化問題をどのような数学的性質を使って性質をどのような手順で解いていくのか、理論面と計算面の２つを楽しめる科目である。

到達目標

この科目によって，以下の内容を修得する。
(1) シンプレックス法による線形計画問題の求解
(2) 双対理論など線形計画問題の理論的性質を理解して，求解に用いることができる
(3) 非線形最適化における最適性条件と最適解の関係性を理解できる
(4) 最急降下法や内点法など，非線形最適化の計算手法の枠組みと特徴を説明できる

キーワード

線形計画問題，シンプレックス法，双対理論，感度分析，最短路問題，最大流問題，凸関数，非線形最適化問題の最適性条件，Karush-Kuhn-Tucker 条件，最急降下法，Newton 法，逐次２次計画法，内点法

学生が身につける力

専門力
教養力
コミュニケーション力
展開力 (探究力又は設定力)
展開力 (実践力又は解決力)

授業の進め方

講義では，計算手法や理論的性質などの解説を主に行います。演習では，計算手法を実際に適用して数理最適化問題の求解や非線形最適化理論の証明に関する演習問題に取り組んでもらいます。なお，演習は基本的に毎回レポートを提出してもらいます。

授業計画・課題

	授業計画	課題
第1回	数理最適化の導入，線形計画問題	線形計画問題の基準形による表記
第2回	演習：線形計画問題	線形計画問題に関する演習問題
第3回	シンプレックス法	シンプレックス法などに関する演習問題
第4回	シンプレックス法における巡回と２段階シンプレックス法	Bland のルールを用いたシンプレックス法および２段階シンプレックス法の計算
第5回	演習：シンプレックス法と２段階シンプレックス法	シンプレックス法と２段階シンプレックス法などに関する演習問題
第6回	双対理論	双対問題への変形，弱双対定理を利用した線形計画問題の理論的性質の導出
第7回	相補性定理と行列形式のシンプレックス法	相補性定理による最適解の導出，行列形式でのシンプレックス法の計算
第8回	演習：双対理論と相補性定理	双対理論と相補性定理などに関する演習問題
第9回	感度分析と最短路問題	感度分析の計算、ダイクストラ法の計算
第10回	最大流問題と質問タイム	フォード・ファルカーソン法よる最大流問題の計算
第11回	演習：最短路問題と最大流問題に関する演習問題	最大流問題などに関する演習問題
第12回	制約なし最適化問題と凸関数	非線形最適化問題への定式化，凸性の定義確認
第13回	制約なし最適化問題の最適性条件	制約なし最適化問題の最適性条件の導出
第14回	演習：凸関数と最適性条件に関する演習問題	凸関数と最適性条件に関する演習問題
第15回	最急降下法	最急降下法の収束の証明を導出
第16回	Newton法と制約付き最適化問題	Newton 法の計算手順の説明，KKT 条件と最適解の関係性の導出
第17回	演習：最急降下法とNewton 法, Karush-Kuhn-Tucker condition に関する演習問題	最急降下法、Newton法、Karush-Kuhn-Tucker conditionに関する演習問題
第18回	双対問題	Lagrange 関数と KKT 条件の関連性の導出
第19回	逐次２次計画法	逐次２次計画法の計算手順の説明
第20回	演習：双対問題と逐次２次計画法に関する演習問題	双対問題と逐次２次計画法に関する演習問題
第21回	内点法	内点法の計算手順の説明，逐次２次計画法との違いの説明
第22回	演習：内点法	内点法などに関する演習問題

準備学修(事前学修・復習)等についての指示

学修効果を上げるため，教科書や配布資料等の該当箇所を参照し，「毎授業」授業内容に関する予習と復習（課題含む）をそれぞれ本学の学修規程で定められた時間を目安に行う。

教科書

教科書は必須ではないが、次の項目にある参考書などを参考として講義内容としている。

参考書、講義資料等

・「数理最適化」, 久野誉人, 繁野麻衣子, 後藤順哉, オーム社, 2012
・「最適化法」，田村明久, 村松正和, 共立出版, 2002
・ Linear and Nonlinear Optimization, Igor Griva, Stephen G. Nash, Ariela Sofer, SIAM,
2009
・ Linear Programming, Vasek Chvatal, Freeman, 1983
・ Linear Optimization, Glenn H. Hurlbert, Springer, 2010
・ Introductory Lectures on Convex Optimization, Yurii Nesterov, Kluwer Academic Publishers, 2004

成績評価の方法及び基準

線形計画問題については，シンプレックス法を適用した求解や，双対理論，ネットワーク最適化などの理解度を評価します。
非線形最適化理論については，最急降下法などの計算手法および最適性条件などの理論面についての理解度を評価します。

配点は，期末試験（約５０％），演習でのレポート状況（約５０％）
（ただし、期末試験が行えない場合はレポート課題を課す可能性もある）

履修の条件・注意事項

応用線形代数 (MCS.T203) を履修していること，または同等の知識があること。

その他

期末試験については試験期間中の対面試験の予定。