最適化入門
担当教員
- 佐川 浩彦?
授業の到達目標及びテーマ
本講座では、情報科学のさまざまな場面で遭遇する最適化問題を数学的に処理するための基本的な手法について解説します。
授業の概要と方法
最初に、最適化問題を扱うために必要となる数学的知識を学んだ後、制約の無い関数の最適化問題として勾配法とニュートン法を学びます。次に、制約がある場合の最適化問題としてラグランジュの未定乗数法を学び、さらに誤差のあるデータに関数を当てはめる手法である最小二乗法と最尤法を学びます。最後に変数が離散的である場合の最適化問題である動的計画法を学びます。 授業は、理解を容易にするために例題を中心に解説を行い、演習により理解を深める、という形で進めます。事前の準備は必要ありませんが、毎回出席しないと理解が難しくなります。
授業計画
| 回 | テーマ | 内容 |
|---|---|---|
| 1 | 最適化問題とは | オリエンテーション |
| 2 | 行列 | 行列と行列式、固有ベクトルの解説 |
| 3 | 偏微分 | 偏微分、曲線・曲面の方程式、接線と法線の解説 |
| 4 | 一次形式と二次形式 | 一次形式と二次形式、二次形式の微分の解説 |
| 5 | 二次形式の標準化 | 対象行列の対角化、二次形式の標準形の解説 |
| 6 | 関数の極値 | 関数の勾配、関数の極値の解説 |
| 7 | 勾配法 | 勾配法の解説 |
| 8 | ニュートン法 | ニュートン法の解説 |
| 9 | ラグランジュの未定乗数法 | ラグランジュの未定乗数法の解説 |
| 10 | 最小二乗法 | 最小二乗法の解説 |
| 11 | 最尤法 | 最尤法の解説 |
| 12 | 動的計画法1 | 最適経路問題、ナップザック法の解説 |
| 13 | 動的計画法2 | ストリングマッチの解説 |
| 14 | まとめと課題 | まとめと課題 |
| 15 | 期末テスト | 期末テスト |
授業外に行うべき学習活動
なし
テキスト
金谷健一、「これなら分かる最適化数学」、共立出版、2005年
参考書
長尾智晴、「最適化アルゴリズム」、昭晃堂、2000年
成績評価基準
期末テストと出席率(50%未満)を考慮して採点します。 採点基準: 合格: A+(100-90)、A(89-80)、B(79-70)、C(69-60) 不合格: D(59点以下)、E(未受験)
前年度の授業改善アンケートからの気づき
新規担当につき該当なし