机器人入行指南
原理层/优化:约束为什么不能只靠罚

原理层 T21 / 27 · 决策与优化

优化:约束为什么不能只靠罚

凸函数上局部最优就是全局最优——这不是安慰是定理。TRPO 写 KL 约束而不是大罚项,理由在对偶理论里:罚项系数要拍,约束不用拍。

凸性局部最优=全局最优分水岭梯度一阶信息 · 步长×方向下降法约束KKT 条件拉格朗日对偶换视角 · gap=0 时等价抓取 LP 用到优化的四层语言T13 的抓取力封闭就是一个 LP——凸性在那里不是理论装饰,是「枚举即精确」的理由
约 55 分钟3 定理8 步证明4 题自测

一句话结论

凸性保证局部=全局(3 行证明);拉格朗日对偶把「带约束」转成「无参数选择的鞍点问题」,强对偶时 gap=0。强化学习里所有「约束式更新」(信任域、KL 罚、安全层)的合理性都从这两个定理出发。

PPO 的 clip、TRPO 的信任域、安全 RL 的拉格朗日方法——为什么有的写成硬约束有的写成罚项、罚项系数为什么难调?答案不在 RL 文献里,在凸优化第一章。这一篇只取 RL 用得到的最小集合:凸性、拉格朗日、对偶、KKT。

为什么需要它

训练时你大概见过两种写法:TRPO 写成 max J(θ) s.t. KL(θ,θ_old) < δ(硬约束);PPO 写成 max J(θ) − β·KL(θ,θ_old)(罚项,β 需要调)。数学上罚项在 β→∞ 时逼近约束,但 β 有限时约束只是「软」的——β 太小约束失效,太大步长瘫痪。这个两难有没有严格解法?

拉格朗日对偶给出第三种形式:L(θ,λ) = J(θ) − λ(KL−δ),对 θ 取 max、对 λ≥0 取 min。λ 不再是拍的超参数,而是对偶问题的解(自动上升到约束刚好紧的值)。安全 RL 的 Lagrangian-PPO 就是这么干的。

先打地基:这一切在「凸问题」上有完整理论。非凸时对偶可能弱(gap>0)、KKT 只是必要非充分。所以要分清哪部分是定理、哪部分是启发式。

定义

定义 9.1 凸函数

f 凸:对一切 x,y 与 λ∈[0,1],f(λx+(1−λ)y) ≤ λf(x)+(1−λ)f(y)。几何读法:弦在曲线上方。严格凸:不等号在 x≠y 时严格。

为什么这样定这个定义看起来朴素,但它精确编码了「局部信息全局有效」——下面定理 9.1 三行证明。

定义 9.2 拉格朗日函数与对偶函数

原问题 min f(x) s.t. g_i(x)≤0。拉格朗日函数 L(x,λ) = f(x) + Σλ_i g_i(x)(λ_i≥0)。对偶函数 g(λ) = min_x L(x,λ)。对偶问题:maxλ≥0 g(λ)。

为什么这样定g(λ) 是逐点对 x 取 min——交换 min 和约束的次序。对偶函数总是原问题的下界(弱对偶),这一点两行可证;什么时候取等是强对偶问题。

定理与证明

定理 9.1 凸性 ⇒ 局部最优即全局最优

f 凸,x̄ 是局部极小点(存在邻域内 f(x̄) ≤ f(x)),则 x̄ 是全局极小点。

证

反证。存在 y 使 f(y) < f(x̄)。考虑连线上的点 z_λ = λy + (1−λ)x̄,λ 取足够小使 z_λ 落在 x̄ 的局部邻域内。

由凸性:f(z_λ) ≤ λf(y) + (1−λ)f(x̄) < λf(x̄) + (1−λ)f(x̄) = f(x̄)。

即邻域内存在 z_λ 严格优于 x̄,与局部最优矛盾。∎

注证明只用了凸性定义和局部性,三行。非凸时这个论证在「弦低于曲线」处断裂——T9 实测里 9 个起点落进 3 个盆地就是断裂的具象。

定理 9.2 弱对偶与强对偶

弱对偶:g(λ) ≤ p*(对一切 λ≥0,两行证明)。强对偶:max g(λ) = p*。凸问题 + Slater 条件(存在严格可行点)⇒ 强对偶成立(陈述不证)。

证

弱对偶:对可行 x(g_i(x)≤0)与 λ≥0:L(x,λ) = f(x) + Σλ_i g_i(x) ≤ f(x)(第二项非正)。两边对 x 取 min:g(λ) ≤ f(x) 对一切可行 x 成立,再对 x 取 inf:g(λ) ≤ p*。∎

强对偶的证明(需要分离超平面/Slater)超出边界,只陈述。

注弱对偶的证明值得逐行读:全部内容就是「λ_i g_i(x) ≤ 0」。强对偶是凸优化的核心奇迹——原问题(可能很难)与对偶问题(凸、总是良定义)在温和条件下同值。KL 约束类问题满足 Slater(δ>0 时严格可行点存在),所以 gap=0。

定理 9.3 KKT 条件(凸时充分)

凸问题在 Slater 下,x* 最优 ⟺ 存在 λ*≥0 使:(平稳性) ∇_x L(x*,λ*)=0;(对偶可行) λ*≥0;(互补松弛) λ*_i g_i(x*) = 0。

证

必要性(非线性规划一般理论)超出边界,只陈述。充分性证明(凸时):对任意可行 x,

f(x) ≥ L(x,λ*) ≥ L(x*,λ*) = f(x*) + Σλ*_i g_i(x*) = f(x*)

第一式:λ*≥0 与 g_i(x)≤0。第二式:平稳性意味着 x* 是 L(·,λ*) 的全局极小(L 对 x 凸——凸函数加线性)。第三式:互补松弛消掉求和项。∎

注互补松弛的直觉:约束「顶死」时(g_i=0)λ 可以大于零,约束松着(g_i<0)时 λ 必为零——乘子只对起作用的约束收费。TRPO 里 KL 约束永远顶死(λ>0),罚项版对应「λ 固定」,安全层的自动 λ 调整对应「互补松弛在跑」。

手算一遍

min x² s.t. x ≥ 1。手算对偶函数、对偶最优解、验证强对偶 gap=0,并读出 KKT 条件。

  1. 标准形式:min f(x)=x²,约束写成 g(x) = 1−x ≤ 0。
  2. 拉格朗日:L(x,λ) = x² + λ(1−x)。对 x 求 min:∂L/∂x = 2x−λ = 0 → x = λ/2(λ≥0 时这是极小)。
  3. [object Object]
  4. 对偶问题 maxλ≥0 λ−λ²/4:d/dλ = 1−λ/2 = 0 → λ* = 2,g(λ*) = 2−1 = 1。
  5. 原问题解:x*=1(x² 在 x≥1 上最小在边界),p* = 1。gap = p* − g(λ*) = 0 ✓ 强对偶。
  6. KKT 检查:平稳性 2x−λ=0(x=1,λ=2: 2−2=0 ✓);互补松弛 λ·g = 2×(1−1) = 0 ✓;λ≥0 ✓。约束顶死(g=0),λ*=2>0——乘子在收费。
答

λ*=2, x*=λ*/2=1, gap=0。几何解读:对偶问题是一个一维凹函数的最大化,比原问题好算——对偶常常「更凸、更低维」,这是它在算法上值钱的原因。

实跑一遍

数字出处

一维实验各跑一遍(学习率 0.05,200 步梯度下降):

  • 凸函数 f=(x−1.5)²+0.3:9 个起点(−2 到 2)全部收敛到 1.5000
  • 非凸函数 f=0.3sin(3x)+0.08x²:9 个起点落进 3 个盆地:{−2.467}×1、{−0.494}×5、{1.482}×3
  • 对偶实验(min x² s.t. x≥1):网格搜索对偶函数得 λ*=2.000,x*=λ*/2=1.000,与原解一致,gap=0

映射回强化学习

这里的对象RL 里的对应物站内用法
凸性局部=全局线性策略+凸目标的情形(如 LQR)可放心用局部方法用法 →
拉格朗日对偶安全层约束的自动乘子调节(Lagrangian-PPO)用法 →
KKT 互补松弛信任域里 KL 约束顶死 → 乘子=学习率的自适应上界用法 →
非凸多盆地策略优化的随机重启、大 batch 降方差的实际理由用法 →

边界:这一篇停在哪里

本篇停在哪里:非凸优化的一般理论、内点法、鞍点问题的算法(如对偶上升的收敛率),都不讲。诚实声明:策略优化几乎总是非凸的,本篇定理给出的是「理想情形」的骨架,实践中它们以「方向性直觉」的方式起作用。

自测 4 题

全是手算和「找证明错在哪」类题目,不出背诵题。答不上来回到对应小节。

01定理 9.1 的证明在非凸函数上哪一步断裂?

「f(z_λ) ≤ λf(y)+(1−λ)f(x̄)」——弦低于曲线这一步需要凸性。非凸时弦可以在曲线之上,局部邻域内找不到更优点不等于全局没有。实测的 3 个盆地就是弦断裂的具象。

02弱对偶的证明只有两行,强对偶为什么难?

弱对偶是逐点不等式(λg≤0),无条件成立。强对偶要证明下界「取得到」——需要分离超平面这类几何工具和 Slater 条件。『下界存在』和『下界紧』是两回事,跟「价值 gap」的直觉一致。

03罚项法(PPO 的 β·KL)和对偶法(自动 λ)的本质区别是什么?

罚项的 β 是外生超参数(拍定后不管约束松紧);对偶的 λ 是对偶变量,沿对偶梯度自动上升直到约束恰好顶死(互补松弛)。后者把「调 β」变成了「解一个低维凸问题」,这就是安全 RL 用对偶法的理由。

04写出 min x² s.t. x≥1 的 KKT 三条件并逐条验证 x*=1, λ*=2。

平稳性:2x−λ=0 → 2−2=0 ✓。对偶可行:λ=2≥0 ✓。互补松弛:λ(1−x)=2×0=0 ✓。三条全过,且问题是凸的+Slater 满足,所以 KKT 充分——x*=1 确是全局最优。

接着看

全系列 27 篇

T1矩阵就是旋转的记账本约 25 分钟T2从斜率到梯度:机器人学习算法的第一行约 25 分钟T3向量与受力:点积的物理读法约 20 分钟T4两把尺子和一把更好的尺子约 25 分钟T5电机转一圈的账:弧度、转速与功率约 20 分钟T6复数乘法就是旋转:四元数的一维版约 20 分钟T7基与坐标:为什么机器人什么都用矩阵约 45 分钟T8矩阵乘法:变换的串联,不是表格运算约 40 分钟T9雅可比:关节转一度,末端动多少约 45 分钟T10特征向量:矩阵不敢动的方向约 45 分钟T11SVD 与伪逆:没有精确解时,找最近的解约 50 分钟T12泰勒展开:用直线替曲线打工约 40 分钟T13概率空间:为什么「随机」需要公理约 50 分钟T14期望:「平均」的严格构造约 55 分钟T15条件期望:竖线的真正含义约 60 分钟T16四个不等式:「多少样本才够」的定量答案约 45 分钟T17范数与不动点:「一定收敛」的出处约 55 分钟T18马尔可夫链:时间平均何时等于集合平均约 55 分钟T19MDP 的数学构造:一条公理值多少钱约 50 分钟T20动态规划:两种迭代的账约 50 分钟T21优化:约束为什么不能只靠罚约 55 分钟T22随机逼近:学习率公式里的每一条约 55 分钟T23接触的数学:Hertz 理论约 45 分钟T24摩擦与摩擦锥:约束的几何形状约 40 分钟T25力封闭与抓取度量:ε 是一个线性规划约 50 分钟T26接触运动学:滚动为什么不是「贴着滑」约 45 分钟T27滑移检测:从「感觉到了」到「算出来了」约 50 分钟