最適化
「一番良いものを選ぶ」を数学の問題として扱う分野。勾配が使えるか、評価に何回かけられるか、ノイズが乗るかで手法が分かれる。
たくさんの候補の中から、ある基準で一番良いものを選び出す。それを数式の問題として 扱うのが最適化。基準を表す関数を目的関数と呼び、その値を最小（または最大）に する入力を探す。
何で分かれるのか#
手法がこれほど多いのは、問題の性質が大きく違うから。実際に手法を選ぶときは、 次の 3 つを順に確かめることになる。
- 勾配が使えるか — 目的関数を微分できるなら 勾配に基づく手法が 圧倒的に速い。微分できない、あるいは式そのものが分からないなら 導関数を使わない手法に移る。
- 評価に何回かけられるか — 1 回の評価が数秒で済むのか、実機の実験が要るのか。 評価が高価ならブラックボックス最適化の考え方が要る。
- 凸か非凸か — 凸なら局所解が大域解で、 到達したら終わり。非凸なら「どこまで探すか」が本質的な問題になる。
変数が連続か離散か#
もう一つの大きな分かれ目が、変数の種類。実数を動かすなら連続最適化、 順番や組合せを選ぶなら組合せ最適化で、 後者は候補数が組合せ的に爆発するため厳密解を諦めることが多い。
参考文献#
- 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
- Sébastien Bubeck. Convex Optimization: Algorithms and Complexity. Foundations and Trends in Machine Learning, 2015. https://arxiv.org/abs/1405.4980
この階層のノート
最適化の基礎 7 / 7 目的関数・制約・局所解といった、どの手法の説明にも出てくる共通の語彙をここで揃える。 数理最適化 6 / 6 目的関数と制約を数式で書き下せる問題を扱う分野。構造が分かっているぶん、専用の解法で大規模かつ高精度に解ける。 勾配に基づく最適化 7 / 7 勾配を使って下る方向へ進む手法群。微分できるならこれが最も効率的で、深層学習の学習もここに含まれる。 導関数を使わない最適化 7 / 7 目的関数の値しか使えないときの最適化。微分できない、式が分からない、値にノイズが乗る、といった場面で選ぶことになる。 ブラックボックス最適化 5 / 5 目的関数の中身が見えず、入力と出力しか分からない状況での最適化。評価回数が予算のすべてになる。 進化計算 13 / 13 集団を持ち、良かった個体に寄せながら次の候補を作る枠組み。勾配が無くても回るので、微分できない目的関数やノイズのある評価で使われる。 群知能 13 / 13 単純な規則で動く個体の相互作用から、集団として賢い探索が現れる枠組み。中央の指令が無いのに全体が良い解へ寄っていく。 焼きなまし・局所探索 7 / 7 現在の解を少しずつ変えながら良くしていく手法群。局所最適解から抜け出す仕掛けをどう持つかで分かれる。 組合せ最適化 7 / 7 有限個の候補から最良を選ぶ問題。原理的には全探索できるが、候補数が爆発するため多くが NP 困難になる。 QUBO最適化 7 / 7 0-1 変数の二次式を最小化する単一の形式。多くの NP 困難問題がこの形に書き直せるため、量子・専用ハードウェアの入口になっている。 量子最適化 6 / 6 量子力学的な現象を使う最適化。断熱型とゲート型があり、どちらも QUBO / イジング形式を入口にする。 最適化アルゴリズムの評価 8 / 8 どの手法が良いかをどう測って主張するか。ノーフリーランチ定理がある以上、主張は必ず条件付きになる。