凸函数与凸规划

凸性的价值是把局部信息升级为全局结论。对凸问题，找到了满足条件的点，通常就不必担心远处还有更低的“坑”。

三种等价刻画

定义域 $C$ 为凸集。 $f:C\to\mathbb R$ 凸，指

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

若 $f$ 一阶可微，等价于切平面在函数图像下方：

f(y)\ge f(x)+\nabla f(x)^T(y-x).

若二阶可微，则

f\text{ 凸}\Longleftrightarrow \nabla^2f(x)\succeq0,\quad \forall x\in C

（在开凸定义域内）。严格正定 Hessian 是严格凸的充分条件。

固定 $x,y$ ，令

\phi(t)=f(x+t(y-x)),\qquad t\in[0,1].

$f$ 凸当且仅当每条线段上的 $\phi$ 都凸。很多多元证明可降为一元二阶导数 $\phi''(t)\ge0$ 。

\operatorname{epi}f=\{(x,t):f(x)\le t\}

是凸集；反之亦然。

“两个凸函数相乘仍凸”一般错误，“凸函数经过任意非线性复合仍凸”也错误，必须检查单调性和复合规则。

采用 $g_i(x)\le0$ 形式时，凸规划要求：

这样可行域是凸集。若 $x^*$ 是局部最优但不是全局最优，存在更好点 $y$ ；沿线段从 $x^*$ 向 $y$ 走一点仍可行，凸性又保证目标立即下降，矛盾。因此凸规划的局部最优都是全局最优。

若 $f$ 严格凸且可行域凸，最优解至多一个。证明只需假设两个不同最优解，取中点，严格凸性给出更小目标值，矛盾。

反之不成立： $f(x)=|x|$ 的唯一最小点是 $0$ ，但它在正半轴和负半轴上分别是仿射的，因此并不严格凸。唯一最优只能说明“这一次没有第二个最优点”，不能反推出函数在任意两点之间都满足严格凸不等式。

另一个容易混淆的事实是： $f(x)=x^4$ 确实严格凸，但

f''(0)=0.

它说明“Hessian 处处正定”只是严格凸的充分条件，不是必要条件；不能用它作为“唯一最优但非严格凸”的反例。

对 $\theta_i\ge0,\sum_i\theta_i=1$ ：

f\left(\sum_i\theta_ix_i\right) \le\sum_i\theta_if(x_i).

它可由二点凸性归纳得到，是概率、统计和机器学习中最常见的凸性工具。