授業科目名 : 最適化

科目コード 90790
配当学年 3年
開講年度・開講期 平成30年度・後期
曜時限 水曜・2時限
講義室 総合研究8号館講義室3
単位数 2
履修者制限
授業形態 講義
使用言語 日本語
担当教員    所属・職名・氏名 情報学研究科・教授・永持 仁,情報学研究科・教授・山下信雄

授業の概要・目的

解決すべき問題をいくつかの変数と数式を含む数学モデルに定式化し、それを定められた計算手順(アルゴリズム)を用いて解くための方法論は最適化あるいは数理計画と呼ばれ、これまで様々な手法が開発され、現実の様々な意思決定の場において広く用いられている。この講義では、特に非線形最適化と組合せ最適化における基本的な方法について講述する。

成績評価の方法・観点及び達成度

期末試験の成績による.

到達目標

連続的最適化と離散的最適化の理論とアルゴリズムの基本的な事柄を理解する.

授業計画と内容

項目 回数 内容説明
非線形最適化の基礎 2 最適化問題の大域的最適解と局所的最適解,凸集合と凸関数,関数の勾配とヘッセ行列などの基礎的事項の意味と性質を説明する.
制約なし最適化の手法 2 最急降下法,ニュートン法,準ニュートン法,共役勾配法など,制約なし最適化の基本的な手法について説明する.
最適性条件と双対性 2 制約つき最適化問題の最適性条件であるカルーシュ・キューン・タッカー条件や2次の最適性条件について説明する.さらに,ラグランジュの双対理論にも言及する.
制約つき最適化の手法 1 制約つき最適化問題に対する代表的な手法であるペナルティ法や逐次2次計画法について説明する.
組合せ最適化 1 巡回セールスマン問題やナップサック問題など,代表的な組合せ最適化問題を紹介し,その困難さに言及する.
分枝限定法と動的計画法 2 組合せ最適化問題に対する厳密解法の基本戦略である分枝限定法と動的計画法の考え方を説明する.
近似アルゴリズム 3 困難な組合せ最適化問題を解くための近似アルゴリズムについて説明し, それらの理論的な性能評価に言及する.
補足とまとめ 1 講義内容のまとめ,補足と学習到達度の確認を行う.

教科書

参考書等

福島雅夫 : 新版・数理計画入門,朝倉書店
柳浦睦憲, 茨木俊秀:組合せ最適化―メタ戦略を中心として, 朝倉書店

履修要件

線形計画(90690)を履修しておくことが望ましい。

授業外学習(予習・復習)等

授業URL

その他(オフィスアワー等)

演習やテストに関する解答や到達度を確認(講評)する。