凸最適化と非凸最適化

凸最適化は、凸関数を 凸集合の上で最小化する問題。 この形に持ち込めるかどうかが、解けるかどうかの実質的な境界になっている。

凸なら何が保証されるか#

• 局所最適解 = 大域最適解。近くしか見ないアルゴリズムでも、止まった場所が最良
• 最適性の判定条件（KKT 条件）が必要十分になる
• 多項式時間で所定の精度まで解ける定式化が揃っている

Boyd は「難しさの境界は線形と非線形の間ではなく、凸と非凸の間にある」と 述べている。これが凸最適化を独立した分野として扱う理由。

非凸で起きること#

• 局所最適解が多数でき、初期値によって結果が変わる
• 鞍点で勾配が消え、更新が止まる（高次元では局所解より鞍点の方が問題になりやすい）
• 平坦な領域では勾配情報がほとんど役に立たない

深層学習の学習も、VQE のパラメータ探索も非凸。 だから「大域解を保証する」ではなく「実用的に十分良い解に届く」を目標に置き替える。

参考文献#

• Stephen Boyd, Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. https://web.stanford.edu/~boyd/cvxbook/
• Yann N. Dauphin et al. Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. NeurIPS, 2014. https://arxiv.org/abs/1406.2572
• Sébastien Bubeck. Convex Optimization: Algorithms and Complexity. 2015. https://arxiv.org/abs/1405.4980