Pythonで学ぶ最適化問題

まず典型的な問題を通してこの講座のテーマである最適化問題とはどのような問題であるか、それをどのような手法で解決するのか紹介します。また、最適化はその数学的な性質によって線形最適化、非線形最適化、凸最適化など様々な種類に分類されています。これらの分類についても概要を説明します。

目的関数、制約条件が1次式で与えられる最適化問題を線形最適化といいます。様々な最適化問題の中でも基本的なもので、厳密に最適値を求めることができます。不等式条件を扱うためのスラック変数の考え方も説明します。

解法として単体法や内点法などが知られており、この講義では特に単体法のアルゴリズムについて詳しく解説します。線形最適化は基本ではありますが適用できる状況は多くとても有用です。線形最適化の適用例としてスケジューリング問題を扱います。

一般に目的関数や制約条件が1次式とは限らない最適化問題についての最適化手法について解説します。このような場合にはしばしば厳密に最適値を求めるのが困難です。そのため、近似的な手法を用います。具体的な方法として勾配法とNewton法Levenberg-Marquardt法を紹介します。いずれも微分を用いた近似解法で、目的関数によってはうまく近似できない場合があります。このような例についても具体的な問題を通して解説します。

ここまでで触れられなかった話題について紹介します。
最短経路問題(Dijkstra法)、双対問題、時間が許せば凸最適化について簡単な紹介をします。