围绕“怎样建模、怎样证明最优、怎样计算”组织学习。先形成可独立使用的工具,再按研究问题深入;本页为中文导读与自编训练,不是全书译文。
Stephen Boyd 与 Lieven Vandenberghe 的 Convex Optimization 是凸优化教材,并非强化学习教材。它为约束建模、对偶、局部近似和数值算法提供基础;一般神经网络策略优化不能直接继承凸问题的全局保证。
PDF 可在作者站免费阅读;作者主页说明完整习题解答需教师申请,不能将其描述为公开全解。本页按章、节定位,避免电子页码与印刷页码混淆。
缺少前两项时,回到 Axler 指南 与 分析指南。概率用于后续应用,不必等全部概率专题学完才开始凸集与凸函数。
理论主线是第 2–5 章:凸集、凸函数、凸优化问题、对偶。第 6–8 章展示拟合、统计估计和几何应用;第 9–11 章讨论无约束、等式约束和内点算法。第 1 章用于建立问题背景。
下面是本站建议的训练顺序,并非作者指定课程安排。每个单元按完成质量推进,不给“必须几天学会”的智力评判线。
阅读第 1 章与第 2 章,先抓住仿射组合、凸组合、凸集、半空间、范数球和半正定锥。
训练目标:给出一个集合,能从定义判断凸性,并明确变量所在空间。
阅读第 3 章,优先掌握凸函数定义、一阶条件、二阶条件与保凸运算。共轭函数等内容可在对偶与相关论文需要时回读。
对定义在开凸集上的二阶连续可微实值函数,Hessian 处处半正定与凸性等价。使用这个判据时,应先确认定义域与光滑性;非光滑目标不能直接套 Hessian 判据。
阅读第 4 章,练习识别线性、二次和其他凸问题。首先检查目标、约束方向与定义域。
阅读第 5 章,优先 5.1、5.2 与 5.5,理解拉格朗日函数、对偶下界、强对偶及 KKT 条件。
可微凸问题中的可行点若满足 KKT 条件,则可用于证明全局最优。反过来,从最优点推导乘子存在和 KKT 必要性时,需要检查适用的约束资格条件。Slater 条件是一类常用充分条件,不是所有问题中都必须成立的条件。
完成下面的完整自编例子后,再选教材同类习题。不要直接跳到复杂算法中的“拉格朗日惩罚”而忽略可行性与对偶间隙。
变量 x 为实数,目标是在 x 不超过 1 时最小化:
无约束最小点为 2,但它不可行。因此需要分析边界,不能仅令导数为零就结束。
导数为 x−2。在可行区间内它严格为负,所以当 x 增大到 1 时函数持续下降。最小点是 1,最小值是 1/2。
把约束写为 x−1 不大于零,引入乘子 λ 不小于零。拉格朗日函数为:
需要同时满足四个条件:
若 λ 为零,平稳条件给出 x=2,与可行性冲突。因此 λ 为正,互补条件要求 x=1;代回平稳条件得 λ=1。目标凸、约束仿射,这组 KKT 条件足以验证全局最优。
对于任意可行 x 和非负 λ,约束项 λ(x−1) 不大于零,故 L(x,λ) 不超过 f(x)。因此先对所有实数 x 取下确界,得到的对偶函数也是原问题最优值的下界。
固定 λ 时,L 对 x 的二阶导数为 1,其唯一最小点为 x=2−λ。代回得到:
配方可得 q(λ)=1/2−(λ−1)²/2,所以对偶最大值为 1/2,在 λ=1 处达到。它与原问题最小值相同;本例通过直接计算验证了零对偶间隙。
自编任务:把目标中心 2 改为任意实数 a,把约束上界 1 改为任意实数 b。分别讨论 a 不超过 b 与 a 大于 b。
核对结果:最小点为 min(a,b),乘子为 max(a−b,0)。解释为什么约束松弛时乘子为零,以及边界点也可能对应零乘子。若把约束换成非凸集合,不能继续沿用上述凸性保证。
按兴趣选择第 6 章或第 7 章;第 8 章在投影与几何问题出现时查阅。
先读第 9 章的下降法、梯度法与 Newton 法,再根据需要读第 10、11 章。
自编任务:对二维二次函数 f(x,y)=(x²+10y²)/2,分析固定步长 α 的梯度下降。两坐标分别乘上 1−α 与 1−10α,因此对任意初始点都收敛到原点需要两因子的绝对值均小于 1,即 0<α<0.2。分别试 α=0.1、0.19 和 0.21,并解释最后一种情况下 y 方向的失败;若初值恰在 y=0 上,则该不稳定方向不会被激发。
这个结论属于给定二次函数的精确分析,不是任意非凸损失的通用步长规则。