凸関数

$$f(\theta x+(1-\theta )y)\le \theta f(x)+(1-\theta )f(y)$$

2 点を結ぶ線分が、関数のグラフより上にある。 下に凸。

判定法#

情報	条件
一階微分	$f(y)\ge f(x)+\nabla f{(x)}^{\top }(y-x)$（接平面が下から支える）
二階微分	ヘッセ行列が半正定値

実用上は二階の条件が最も使いやすい。 ヘッセ行列の固有値がすべて非負なら凸。

なぜ凸だと解けるのか#

局所最適解が大域最適解になる。 一階の条件から

$$f(y)\ge f(x^{\star })+\underset{=0}{\underbrace{\nabla f(x^{\star })}}{}^{\top }(y-x^{\star })=f(x^{\star })$$

停留点なら、すべての $y$ について $f(y)\ge f(x^{\star })$。 近くしか見ないアルゴリズムでも、止まった場所が最良と保証される。

凸性を保つ操作#

• 非負の重み付き和 $\sum w_i{f}_i$（$w_i\ge 0$）
• 最大値 ${\max }_i{f}_i$
• アフィン変換との合成 $f(Ax+b)$

これらを組み合わせて凸性を確かめる手続きが disciplined convex programming で、 CVXPY などのモデリング言語が採用している。

参考文献#

• Stephen Boyd, Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.（全文公開） https://web.stanford.edu/~boyd/cvxbook/
• Sébastien Bubeck. Convex Optimization: Algorithms and Complexity. 2015. https://arxiv.org/abs/1405.4980