首页/笔记/免费阅读与训练/Boyd《凸优化》:阅读顺序、训练与强化学习连接

Boyd《凸优化》:阅读顺序、训练与强化学习连接

围绕“怎样建模、怎样证明最优、怎样计算”组织学习。先形成可独立使用的工具,再按研究问题深入;本页为中文导读与自编训练,不是全书译文。

先认清这本书

Stephen Boyd 与 Lieven Vandenberghe 的 Convex Optimization 是凸优化教材,并非强化学习教材。它为约束建模、对偶、局部近似和数值算法提供基础;一般神经网络策略优化不能直接继承凸问题的全局保证。

PDF 可在作者站免费阅读;作者主页说明完整习题解答需教师申请,不能将其描述为公开全解。本页按章、节定位,避免电子页码与印刷页码混淆。

前置知识检查

  1. 线代:向量内积、范数、秩、正定与半正定矩阵、特征值。
  2. 分析:梯度、Hessian、链式法则、Taylor 展开。
  3. 概率:期望与条件期望,服务于统计和强化学习应用。
  4. 计算:能用数组表达目标函数,并核对解析梯度与数值结果。

缺少前两项时,回到 Axler 指南 与 分析指南。概率用于后续应用,不必等全部概率专题学完才开始凸集与凸函数。

教材地图

理论主线是第 2–5 章:凸集、凸函数、凸优化问题、对偶。第 6–8 章展示拟合、统计估计和几何应用;第 9–11 章讨论无约束、等式约束和内点算法。第 1 章用于建立问题背景。

下面是本站建议的训练顺序,并非作者指定课程安排。每个单元按完成质量推进,不给“必须几天学会”的智力评判线。

单元一:先写清变量与可行集合

阅读第 1 章与第 2 章,先抓住仿射组合、凸组合、凸集、半空间、范数球和半正定锥。

训练目标:给出一个集合,能从定义判断凸性,并明确变量所在空间。

  • 自编任务:证明两凸集的交仍为凸集;检查它们的并是否一定凸。
  • 提示:交集中的两个点分别满足两组条件;并集中的两个点可能来自不同集合。
  • 核对:实数轴上的两个单点集合都是凸集,但它们的并可以不是凸集。
  • 研究连接:先识别参数或策略受什么约束,再讨论优化算法。

单元二:判断目标的结构

阅读第 3 章,优先掌握凸函数定义、一阶条件、二阶条件与保凸运算。共轭函数等内容可在对偶与相关论文需要时回读。

对定义在开凸集上的二阶连续可微实值函数,Hessian 处处半正定与凸性等价。使用这个判据时,应先确认定义域与光滑性;非光滑目标不能直接套 Hessian 判据。

  • 自编任务:对固定矩阵 A、向量 b 与非负实数 λ,分析目标 f(x)=‖Ax−b‖²/2+λ‖x‖²/2 的凸性。
  • 推导入口:梯度为 A 的转置乘残差,再加正则梯度;Hessian 为半正定 Gram 矩阵加 λ 倍单位矩阵。
  • 自检:λ 大于零时为什么能得到严格凸性?λ 为零且 A 列不满秩时又怎样?
  • 研究连接:论文里的“损失”是对预测值凸,还是对全部模型参数凸?这两者必须分开。

单元三:把问题写成标准形式

阅读第 4 章,练习识别线性、二次和其他凸问题。首先检查目标、约束方向与定义域。

  • 自编任务:把“误差最小但参数不能超过预算”写成一个有明确变量、目标和约束的模型。
  • 自检:凸函数不大于常数通常给出凸下水平集;把不等号方向反过来是否仍然成立?构造反例。
  • 研究连接:区分原问题、等价改写、松弛和局部近似。松弛问题的解未必满足原约束。

单元四:对偶与最优性

阅读第 5 章,优先 5.1、5.2 与 5.5,理解拉格朗日函数、对偶下界、强对偶及 KKT 条件。

可微凸问题中的可行点若满足 KKT 条件,则可用于证明全局最优。反过来,从最优点推导乘子存在和 KKT 必要性时,需要检查适用的约束资格条件。Slater 条件是一类常用充分条件,不是所有问题中都必须成立的条件。

完成下面的完整自编例子后,再选教材同类习题。不要直接跳到复杂算法中的“拉格朗日惩罚”而忽略可行性与对偶间隙。

完整训练:一个约束如何改变最优点

对象、条件与目标

变量 x 为实数,目标是在 x 不超过 1 时最小化:

$$ f(x)=\frac12(x-2)^2,\qquad x\leq 1. $$

无约束最小点为 2,但它不可行。因此需要分析边界,不能仅令导数为零就结束。

先用函数性质确定答案

导数为 x−2。在可行区间内它严格为负,所以当 x 增大到 1 时函数持续下降。最小点是 1,最小值是 1/2。

再用 KKT 重建结论

把约束写为 x−1 不大于零,引入乘子 λ 不小于零。拉格朗日函数为:

$$ L(x,\lambda)=\frac12(x-2)^2+\lambda(x-1). $$

需要同时满足四个条件:

$$ x\leq1,\qquad \lambda\geq0,\qquad x-2+\lambda=0,\qquad \lambda(x-1)=0. $$

若 λ 为零,平稳条件给出 x=2,与可行性冲突。因此 λ 为正,互补条件要求 x=1;代回平稳条件得 λ=1。目标凸、约束仿射,这组 KKT 条件足以验证全局最优。

为什么对偶给出的确实是下界

对于任意可行 x 和非负 λ,约束项 λ(x−1) 不大于零,故 L(x,λ) 不超过 f(x)。因此先对所有实数 x 取下确界,得到的对偶函数也是原问题最优值的下界。

固定 λ 时,L 对 x 的二阶导数为 1,其唯一最小点为 x=2−λ。代回得到:

$$ q(\lambda)=\lambda-\frac12\lambda^2,\qquad \lambda\geq0. $$

配方可得 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 上,则该不稳定方向不会被激发。

这个结论属于给定二次函数的精确分析,不是任意非凸损失的通用步长规则。

与强化学习怎样连接

  1. 约束成本、资源预算等问题可能用到乘子与对偶;先明确约束的是期望成本、逐步成本还是概率。
  2. 固定数据和固定特征下的普通线性最小二乘拟合是凸问题;带自举目标或联合更新目标的强化学习训练不能因此被认定为同一个凸问题。
  3. 信赖域与局部二次近似可帮助理解策略更新,但局部模型的性质不等于原始策略目标的全局性质。
  4. 在某些有限 MDP 中,可换用占用测度形成线性规划;这并不意味着神经网络参数化后的目标仍然凸。

阅读论文时的核对清单

  • 决策变量是什么?论文是否中途改变了参数化?
  • 凸性、可微性、可行性和约束资格条件在哪里使用?
  • 使用的是强对偶还是仅有弱对偶?
  • 原问题与求解子问题之间是等价、松弛还是近似?
  • 数值算法的停止准则检查了什么?

返回

免费阅读与训练总览 · 凸优化资源卡 · 强化学习路线 · 站内长期路线