凸函数

定义在凸集 $C$ 上的函数 $f$ 若满足 $$f((1-t)x+ty)\le (1-t)f(x)+tf(y)(x,y\in C,0\le t\le 1),$$ 便称凸函数。左边是线段中点附近的函数值，右边是端点函数值连成的弦；图像位于弦的下方或其上。这一定义不要求函数处处可导。

平方函数与一阶条件

取 $f(x)=x^2$。两边相减可得 $$(1-t)x^2+t{y}^2-((1-t)x+ty{)}^2=t(1-t)(x-y{)}^2\ge 0,$$ 故 $x^2$ 凸。若 $f$ 可导，在凸定义域上还可用切线判据 $f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^{𝖳}(y-x)$：所有切平面都在函数图像下方。在一维二阶可导时，$f^{″}(x)\ge 0$ 是充分且必要的局部检查条件。

局部最小即全局最小

若 $x^{\ast }$ 是凸集上的局部最小点，却有另一点 $y$ 使 $f(y)<f(x^{\ast })$，则对足够小的 $t>0$，点 $x_t=(1-t)x^{\ast }+ty$ 落在 $x^{\ast }$ 的邻近，而凸性给 $f(x_t)\le (1-t)f(x^{\ast })+tf(y)<f(x^{\ast })$，矛盾。因而凸优化没有“局部低谷困住、别处还有更低值”的问题。若 $f$ 严格凸且最小点存在，最小点唯一。

“凸函数”不等于曲线处处向上弯得很明显：直线既凸又凹，$|x|$ 凸但在 0 不可导。

参考资料

• Boyd 与 Vandenberghe，Convex Optimization，第 3 章。
• MIT 6.079，凸优化讲义。
• 继续阅读：凸集、梯度下降、KKT条件。