凸优化

找到一个比附近点更好的解，通常还不能断定它在所有可行解中最好。凸优化研究的是一类局部最优也能保证全局最优的问题。可以按以下顺序学习：

1. 凸集与凸函数；
2. 标准问题形式及其变换；
3. 最优性条件；
4. 拉格朗日对偶；
5. 一阶与二阶求解方法；
6. 在统计学与机器学习中的应用。

完整课程与证明可参考 Stanford EE364A 和 Boyd、Vandenberghe 的教材 《Convex Optimization》。

够用的基本概念

这张地图说明全局保证依赖哪些假设；对偶与算法的完整推导见 Boyd 与 Vandenberghe 教材第 2–5、9 章。

若任意 $x,y\in C$、$0\le t\le1$ 都满足 $(1-t)x+ty\in C$，即连接两点的线段不离开集合，就称 $C$ 为凸集。定义在凸域上的函数若满足

$$f((1-t)x+ty)\le(1-t)f(x)+tf(y),$$

就称为凸函数。图像位于弦的下方。若两点不同时，对 $0<t<1$ 都是严格不等式，则函数严格凸；这保证最小点至多一个，不保证存在。例如 $e^x$ 在 $\mathbb R$ 上严格凸，却只有下确界零，没有最小点。

可微凸函数满足支撑平面不等式：

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

因此无约束驻点就是全局最小点。更一般地，对凸集 $C$ 中的可行点 $x_*\in C$，一阶条件 $\nabla f(x_*)^T(y-x_*)\ge0$ 对所有 $y\in C$ 成立，是最优性的充要条件。$f(x)=x$ 在 $[0,1]$ 上的最优解 $x_*=0$ 满足它，尽管 $f'(0)=1$。凸问题的每个局部极小点都是全局最小点：若存在更好的可行点，沿连接它的线段，任意靠近当前点的位置都能改善目标，与局部极小矛盾。

标准凸问题最小化凸目标，约束由凸不等式 $g_i(x)\le0$ 和仿射等式 $Ax=b$ 组成。仅目标凸、可行集非凸还不够。例如在 $\{-1,2\}$ 上最小化 $x^2$，孤立点 $2$ 是局部极小点，却不是全局最小点。

对开凸域上的二阶连续可微函数，凸性等价于 Hessian 半正定。梯度与曲率说明从二阶偏导和二次型出发，定义了 Hessian 与正定性。最小二乘的 $H=2X^TX/n\succeq0$；设计矩阵列满秩时正定，解唯一。凸性不能让任意梯度步长都收敛，仍需考虑光滑性和步长。

对偶用在哪里

拉格朗日函数为 $\mathcal L(x,\lambda,\nu)=f(x)+\sum_i\lambda_i g_i(x)+\nu^T(Ax-b)$，其中 $\lambda_i\ge0$。取 $\inf_x\mathcal L$ 得到原问题最小值的下界，再最大化这个下界就是对偶问题。原问题的可行目标值与对偶下界之差可以衡量最优性差距，迭代变化很小则不能。

Karush–Kuhn–Tucker 条件包括原问题可行、对偶可行、拉格朗日函数的驻点条件，以及互补松弛 $\lambda_i g_i(x)=0$。在可微凸问题中，满足这些条件足以保证全局最优。它们成为必要条件、对偶间隙为零，还需要适当的正则性条件，例如 Slater 条件：在定义域相对内部存在满足等式约束、且严格满足不等式约束的点。不能把这些保证无条件套到任意约束问题或神经网络上。

我的阅读 · 打开过的笔记会记在当前浏览器里。