凸集与凸函数

集合中任意两点连线仍在集合内即凸集；函数图像“碗形”即凸函数：
$f(\lambda\mathbf x+(1-\lambda)\mathbf y)\le\lambda f(\mathbf x)+(1-\lambda)f(\mathbf y)$
凸函数的局部最优即全局最优，这是“可高效求解”的分水岭。二阶判据：$\nabla^2 f\succeq0$。

最优性条件

  • 无约束：一阶 $\nabla f=\mathbf0$，二阶 $\nabla^2 f\succ0$ 为极小；
  • 带约束：用 KKT 条件（梯度的拉格朗日组合为零、原始/对偶可行、互补松弛）。

拉格朗日对偶

约束问题 $\min f$ s.t. $g_i\le0$ 的拉格朗日函数 $L=f+\sum\lambda_i g_i$，对偶函数取下确界。弱对偶总成立，凸问题在 Slater 条件下强对偶（对偶间隙为零）——这是 SVM 求解的理论基础。

例题

例　$\min x^2+y^2$ s.t. $x+y=1$：$L=x^2+y^2+\lambda(1-x-y)$，$\nabla=0$ 得 $x=y=\lambda/2$，代入约束得 $x=y=\tfrac12$，最小值 $\tfrac12$。

应用

凸优化是经典机器学习的“可解内核”：SVM、Lasso、逻辑回归都是凸问题，保证全局最优；KKT 与对偶揭示了支持向量的含义；即便深度学习非凸，凸分析仍是理解与设计优化器的语言。