Part I · 第 6 章 优化 · 6.2

凸性

优化里最重要的一个"好性质"：碗状的地形里只有一个谷底，沿着坡往下走，一定走得到。数学上把这种碗叫凸函数。一个问题是凸的，意味着局部最小就是全局最小，算法有保证、有速度、结果可复现；不是凸的，就要靠运气和经验。认清哪些机器人问题凸、哪些不凸，是选对工具的第一步。

约 25 分钟 前置：6.1 什么是优化问题 · 3.5 Hessian · 1.11 特征值 5 个交互

    1为什么机器人需要它

    机器人领域有一条几乎通用的工程经验：能写成凸问题的，就写成凸问题。全身控制每毫秒要解一个二次规划 (QP)，模型预测控制 (MPC) 在线性模型下是一个凸 QP，线性最小二乘标定一步到位。它们都是凸的，所以求解器几毫秒内给出可靠、唯一、可复现的答案，不用担心卡在局部最小、不用调初值。

    反过来，机械臂的逆运动学、视觉里程计的位姿优化、神经网络训练都不是凸的，我们只能找"一个够好的谷底"。这一节要建立的是一副"眼镜"：给你一个问题，你能判断它的地形是碗还是山脉，从而知道可以对结果有多大的信心。

    2直觉：弦在曲线之上

    取函数曲线上任意两点，连一条线段（弦）。如果无论你取哪两点，弦都不会钻到曲线下面，这个函数就是凸的：它像一个碗，向上"兜住"每一条弦。只要有一对点，弦钻到了曲线下面，就说明那里有个"凸起"，凸性被破坏。

    这个看似平淡的性质威力巨大。假设碗里有两个"谷底"，它们之间的弦必须在曲线之上（或重合）；可两个谷底都是最低值 \(m\)，弦的高度恰好是 \(m\)，而曲线又不可能低于 \(m\)，于是两点之间的曲线被夹住，处处等于 \(m\)：两个谷底其实是同一片平地。如果两个谷底一高一低，弦从高的那个谷底出发就向下倾斜，紧挨着它的曲线也被压到它的高度之下，它根本不是局部最小（第 7 节给出严格证明）。凸函数不可能有彼此孤立的两个局部最小值。先亲手试试弦测试。

    3动手玩：弦测试

    选一个函数，拖动曲线上的两个点 A、B。弦在曲线之上的部分填绿色，钻到曲线之下的部分填红色。滑块 \(\theta\) 在弦上取一点，对比 \(f(\theta a+(1-\theta)b)\) 与弦的高度 \(\theta f(a)+(1-\theta)f(b)\)。"全面扫描"会测试 780 对点（区间上 40 个点两两配对），告诉你有多大比例的弦违反了凸性。

    FIG 1一维弦测试
    六个函数：\(0.4x^2\)、\(0.25e^{0.8x}\)、\(0.04x^4\)、双谷 \(0.08(x^2-2)^2\)、波浪 \(1.5+0.9\sin1.7x+0.12x^2\)、凹函数 \(3-0.3x^2\)。判定用密集采样 (200 点) 逐点比较弦与曲线，不是目测。
    试一试
    • 在"双谷"或"波浪"上找到一对点，让弦钻到曲线之下。
    • 在 \(0.04x^4\) 上做"全面扫描"：它在 \(x=0\) 处几乎是平的，却仍然是凸的，违反比例是 0。
    • 在凹函数 \(3-0.3x^2\) 上扫描：违反比例是多少？为什么凹函数的"弦"总在曲线下面？
    核心洞见

    凸性是一个"全局"性质，却能用"两点之间"来检验。你不需要知道整个地形，只要任意两点之间的弦不下沉，就知道没有多余的谷底。这也是为什么它能给出全局保证：局部信息（梯度为零）加上凸性，就等于全局信息。

    4凸集：约束的形状

    同样的"弦测试"用在集合上：一个集合是凸的，当且仅当其中任意两点之间的线段完全留在集合里。球、半空间、盒子是凸的；有凹口的"月牙"、带洞的区域、几块分离的区域都不是。

    它为什么重要？因为可行集（6.1 节）就是一个集合。如果约束是凸的，从可行点出发朝另一个可行点走，永远不会"撞墙"。反之，一个障碍物就能把可行集变成非凸的：从左边绕还是从右边绕，是两条不同的路，这正是路径规划难的原因。

    FIG 2这个集合是凸的吗？
    拖动 A、B。线段落在集合内的部分是绿色，落在外面的部分是红色。"随机扫描"在集合内随机抽 3000 对点，数一数有多少条弦会跑出集合。
    试一试
    • 在"月牙"或"星形"里，把 A、B 都放在集合内，却让弦跑出集合。
    • 选"透镜"（圆盘 ∩ 半平面）并做随机扫描：两个凸集的交仍然是凸集，违反数为 0。

    5第二个视角：切线在下，曲率向上

    弦测试需要同时看两个点，不方便。对可导函数，有两个"单点"检验：

    • 一阶条件：凸函数整条曲线都在它任何一条切线之上。选一点 \(x_0\)，画出切线，曲线不能钻到切线下面。
    • 二阶条件：曲率处处非负，即 \(f''(x)\ge0\)（多维时是 Hessian \(\nabla^2 f\succeq0\)，3.5 节）。曲线始终"向上弯"。

    下面拖动 \(x_0\)：上图画切线，红色表示曲线跑到了切线之下；下图画 \(f''\)，红色表示曲率为负。你会发现这两件事严格同步：只要某处 \(f''<0\)，就一定能找到一条切线被曲线穿透；反之，\(f''\ge0\) 处处成立则切线永远在下面。

    FIG 3切线测试与曲率
    上：曲线、\(x_0\) 处的切线（紫色）；曲线低于切线的区间标红。下：\(f''(x)\)（解析式）；负值标红。选 \(0.04x^4\)：\(x=0\) 处 \(f''=0\)，切线是水平线，曲线仍然不会钻下去：二阶条件是"\(\ge0\)"，不是"\(>0\)"。
    • 在"双谷"上拖动 \(x_0\)，找到一个位置使得切线被曲线穿透。此时 \(f''\) 在 \(x_0\) 处一定为负吗？（不一定：试试 \(x_0=1\)。）
    • 在"指数"上拖遍整条曲线：切线是否永远在曲线之下？

    6二维地形：弦、Hessian 与"负曲率区"

    到了二维，把 \(x_0\) 换成平面上的点，曲率换成 Hessian 的两个特征值 \(\lambda_1\ge\lambda_2\)（1.11 节）。\(\lambda_2\ge0\) 说明各个方向都向上弯，是碗；\(\lambda_2<0\le\lambda_1\) 说明有的方向向下弯，是鞍；两个都为负是山顶。凸函数要求处处是碗。

    下图在平面上拖动 A、B，下方的小图画出 \(f\) 沿这条线段的剖面（实线）和弦（虚线）。红色背景标出 Hessian 有负特征值的地方，那是"非凸区"。试试四种地形：只有第一个是凸的。

    FIG 4平面上的弦与 Hessian
    沿线段 A→B 的剖面
    四个地形：log-sum-exp \(\log(e^x+e^{-x}+e^y+e^{-y})\)（凸）、Rosenbrock \(\tfrac12[(1-x)^2+100(y-x^2)^2]\)（只有一个谷但不凸）、双谷（6.3 节）、鞍 \(\tfrac12x^2+\tfrac14y^4-\tfrac12y^2\)。Hessian 用梯度的中心差分数值计算，特征值取自 1.11 节的对称 2×2 公式。
    • 在 Rosenbrock 上放 A、B，使剖面鼓到弦之上（它只有一个谷底，却不是凸的）。
    • 在 log-sum-exp 上随便拖拽 A、B：剖面永远在弦下面，红色区域也不出现。

    7再看数学

    提示：悬停在带底色的符号上，FIG 1、3、4 里对应的元素（弦、切线、非凸区）会被强调。

    定义

    集合 \(C\) 是凸集，如果对任意 \(\x,\y\in C\) 与 \(\theta\in[0,1]\)，都有 \(\theta\x+(1-\theta)\y\in C\)。函数 \(f\) 是凸函数，如果定义域是凸集，且

    $$ f\big(\theta\x+(1-\theta)\y\big)\ \le\ \hl{jensen}{\cv{\theta f(\x)+(1-\theta)f(\y)}}\qquad\forall\,\x,\y,\ \theta\in[0,1] $$

    左边是弦下方曲线上的点的高度，右边是弦的高度（FIG 1 的滑块 \(\theta\)）。把 \(\le\) 换成 \(<\)（\(\x\ne\y\)，\(\theta\in(0,1)\)）就是严格凸：碗底没有平的部分，最小点唯一。\(-f\) 凸则称 \(f\) 为凹。

    一阶与二阶条件

    若 \(f\) 可微，则 \(f\) 凸 \(\iff\) 对所有 \(\x,\y\)：

    $$ f(\y)\ \ge\ f(\x)+\hl{tangent}{\cw{\nabla f(\x)^\top(\y-\x)}} $$

    右边正是 \(f\) 在 \(\x\) 处的一阶泰勒展开（切线 / 切平面，FIG 3 的紫线）。若 \(f\) 二阶可微，则 \(f\) 凸 \(\iff\)

    $$ \hl{hess}{\nabla^2 f(\x)\succeq 0}\quad\forall\,\x\qquad\Longleftrightarrow\qquad\lambda_{\min}\big(\nabla^2 f(\x)\big)\ge0\quad\forall\,\x $$

    为什么凸问题"容易"

    1. 局部最小就是全局最小。设 \(\x^\star\) 是局部最小，却有 \(\y\) 使 \(f(\y)<f(\x^\star)\)。沿线段取点 \(\x_t=(1-t)\x^\star+t\y\)，由凸性 \(f(\x_t)\le(1-t)f(\x^\star)+tf(\y)<f(\x^\star)\)，对任意小的 \(t>0\) 都成立，而 \(\x_t\) 可以任意接近 \(\x^\star\)，与"局部最小"矛盾。

    2. 梯度为零就够了。在一阶条件里令 \(\nabla f(\x^\star)=\mathbf0\)，得 \(f(\y)\ge f(\x^\star)\ \forall\y\)：驻点就是全局最小。6.1 节说"梯度为零只是必要条件"，对凸函数它也是充分条件。

    3. 算法有保证。强凸（\(m I\preceq\nabla^2f\preceq L I\)）时，梯度下降的误差按 \(\big(\tfrac{\kappa-1}{\kappa+1}\big)^k\) 衰减，\(\kappa=L/m\) 就是 6.3 节的条件数；Newton 法（6.6 节）在最优点附近二次收敛。

    怎样得到凸函数：保凸运算

    运算结论机器人里的例子
    非负加权和\(\sum_i w_if_i,\ w_i\ge0\)误差 + \(\lambda\)·能耗
    与仿射映射复合\(f(A\x+\mathbf b)\)\(\|A\x-\mathbf b\|^2\)：线性最小二乘（1.13 节）
    逐点取最大\(\max_i f_i\)最大关节误差；\(\ell_\infty\) 范数
    范数、二次型 (PSD)\(\|\x\|,\ \x^\top Q\x\)马氏距离、力矩平方
    凸集的交\(C_1\cap C_2\)限位 ∩ 速度上限 ∩ 摩擦锥

    注意非线性复合会破坏凸性：\(\|A\x-\mathbf b\|^2\) 凸，但 \(\|\mathrm{FK}(\mathbf q)-\mathbf t\|^2\) 里的 \(\mathrm{FK}\) 不是仿射的，所以逆运动学的代价对关节角 \(\mathbf q\) 不凸，见下一节。

    8机器人中的它：逆运动学为什么不凸

    对于一个目标位置 \(\mathbf t\)，最小化 \(f(\mathbf q)=\tfrac12\|\mathrm{FK}(\mathbf q)-\mathbf t\|^2\)。如果把末端位置 \(\mathbf p\) 当变量，\(\tfrac12\|\mathbf p-\mathbf t\|^2\) 是一个完美的碗；可变量是关节角 \(\mathbf q\)，\(\mathbf p=\mathrm{FK}(\mathbf q)\) 里全是 \(\sin,\cos\)，碗被"揉皱"了。最直接的证据：肘朝上和肘朝下两个解的代价都是 0，而在关节空间里把两个解连成一条线段，中点的代价却大于 0，弦在曲线下面。

    拖动下图右侧的 A、B（初始在两个解上，拖动目标会自动吸附到新解），滑块 \(t\) 让手臂沿着这条线段在关节空间里"插值"。注意中途手爪明显偏离了目标，代价鼓起一个包。红色区域是 Hessian 有负特征值的地方。

    FIG 5关节空间里的弦：IK 代价
    左：工作空间，拖动目标；淡色手臂是 A、B 两端，实心手臂是 \(\mathbf q(t)=(1-t)\mathbf q_A+t\mathbf q_B\)。右：关节空间，\(q_1,q_2\in[-\pi,\pi]\)。下：\(f(\mathbf q(t))\) 与弦。当 A、B 都是零代价解时弦是一条贴着 0 的横线，曲线却在中间鼓起来。
    • 把滑块 \(t\) 拖到中间 (0.4–0.6)，读出中点代价：它是否大于两端代价的平均值？
    真实系统里

    这解释了机器人领域的一个普遍现象："把不凸的部分藏到凸的外面"。解 IK 时通常先在关节空间做一次非凸迭代，再在每一步里解一个凸的线性化子问题（雅可比 \(J\) 把问题局部变成线性最小二乘，6.6、6.9 节）。全身控制则更进一步：在加速度层面，动力学对力矩 \(\boldsymbol\tau\) 与加速度 \(\ddot{\mathbf q}\) 是线性的，于是整个问题是一个凸 QP（6.8 节、第 IV 部分）：只要约束可行，求解器就能在 1 kHz 下可靠地给出全局最优解。凸与不凸，常常取决于你选了哪个变量。

    9常见误区

    误区 1：只有一个谷底，所以是凸的

    反例就是 Rosenbrock（FIG 4）：只有一个最小点，却不是凸的，弦能钻到曲线下面。"单峰"（unimodal）比"凸"弱得多。不凸但单谷的函数，局部算法通常也能找到最小点，只是没有凸性那样的速度保证（沿弯曲山谷爬得很慢）。

    误区 2：Hessian 在某一点为正定，函数就是凸的

    二阶条件必须在整个定义域上成立。一个点的 Hessian 正定只说明局部像碗（它是局部最小的二阶充分条件）。FIG 4 里的双谷在每个谷底都是正定的，整体却不凸。

    误区 3：等式约束 \(\|\x\|=1\) 和不等式约束 \(\|\x\|\le1\) 差不多

    单位球（\(\le\)）是凸集，单位球面（\(=\)）不是：球面上两点连线穿过球内部。这就是为什么"四元数模长为 1"、"旋转矩阵正交"这类约束让问题变得不凸，也是第 6.10 节要在流形上直接优化的原因之一。非线性等式约束一般都会破坏凸性；凸问题里的等式约束必须是仿射的。

    误区 4：凸问题就一定好解

    凸性保证"没有坏的局部最小"，但不保证"快"。条件数 \(\kappa\) 很大的凸问题，梯度下降仍然龟速（6.3 节）；规模巨大的凸问题仍然需要好的算法和实现。反过来，也有很多不凸的问题（如神经网络训练）在实践中被解得很好。

    10小练习

    1. 下列哪个函数在整个 \(\mathbb R\) 上是凸的？
    \((x^4)''=12x^2\ge0\) 处处成立（\(x=0\) 处等于 0 也没关系，条件是 \(\ge0\)）。\(\sin x\) 的二阶导数 \(-\sin x\) 会变负；\(-x^2\) 是凹的；\(x^3\) 的二阶导数 \(6x\) 在 \(x<0\) 时为负。
    2. \(f(x,y)=x^2+4xy+y^2\) 是凸函数吗？
    \(\partial_{xx}=2,\ \partial_{xy}=4,\ \partial_{yy}=2\)。特征值 \(2\pm4\)，即 6 与 \(-2\)（对应方向 \((1,1)\) 和 \((1,-1)\)）。沿 \((1,-1)\) 方向 \(f(t,-t)=-2t^2\) 向下弯，这是个鞍，既不凸也不凹。交叉项 \(4xy\) 可以压过平方项：不能只看对角线上的系数。
    3. \(f\) 是凸函数，且在某点 \(\x^\star\) 处 \(\nabla f(\x^\star)=\mathbf 0\)。可以得出什么？
    一阶条件 \(f(\y)\ge f(\x^\star)+\nabla f(\x^\star)^\top(\y-\x^\star)=f(\x^\star)\) 对所有 \(\y\) 成立，所以是全局最小。凸函数没有鞍点（鞍需要某个方向向下弯）。最小点是否唯一取决于是否严格凸，这里无法得出。
    4. 下列约束集合中，哪一个不是凸集？
    前三个是盒子、盒子、圆盘：凸。"在圆盘之外"的补集不是凸集：圆盘两侧各取一点，连线穿过圆盘。这就是避障让规划变得非凸的根本原因（FIG 2 的"月牙"与"两个圆"同理）。

    11延伸阅读

    • S. Boyd & L. Vandenberghe, Convex Optimization, Ch. 2–3 — 凸集、凸函数、保凸运算的完整讲解，含大量图示（可免费下载）
    • J. Nocedal & S. Wright, Numerical Optimization, 2nd ed., Ch. 1–2 & App. A — 凸性在局部最优性条件中的作用
    • G. Strang, Linear Algebra and Learning from Data, Ch. VI — 凸函数、正定性与深度学习中的优化