数理最適化
目的関数と制約を数式で書き下せる問題を扱う分野。構造が分かっているぶん、専用の解法で大規模かつ高精度に解ける。
目的関数と制約を数式で明示的に書き下せる問題を扱う分野。 Mathematical Programming とも呼ばれる。
関数の形が分かっているので、その構造を使った専用の解法が作れる。 ブラックボックス最適化が 「中身が見えない」前提なのと対照的で、解ける規模も精度も桁違いになる。
分類#
| 種類 | 目的関数 | 制約 | 難しさ |
|---|---|---|---|
| 線形計画 | 線形 | 線形 | 多項式時間 |
| 二次計画 | 二次 | 線形 | 凸なら多項式時間 |
| 非線形計画 | 任意 | 任意 | 一般に困難 |
| 整数計画 | 線形 | 線形 + 整数条件 | NP 困難 |
難しさの境界は線形か非線形かではなく、 凸か非凸か、 そして変数が連続か整数かにある。
参考文献#
- Stephen Boyd, Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. https://web.stanford.edu/~boyd/cvxbook/
- Jorge Nocedal, Stephen J. Wright. Numerical Optimization, 2nd ed. Springer, 2006. https://doi.org/10.1007/978-0-387-40065-5