Part I · 第 6 章优化 · 6.8

线性规划与二次规划

目标是线性的、约束也是线性的，最优解一定躲在多面体的某个角上，这就是线性规划。把目标换成二次函数，最优解就可以离开角，停在棱上甚至内部：这就是二次规划。机器人每个控制周期里解的 MPC、全身控制和抓取力分配，几乎都是二次规划，因为它又快又可靠。

约 25 分钟前置：1.13 最小二乘 · 6.2 凸性 · 6.7 约束优化与 KKT 4 个交互

1为什么机器人需要它

机器人的世界里到处是"不等式"：关节力矩不能超过电机上限，足底接触力必须落在摩擦锥里，夹爪的手指只能推、不能拉，末端不能撞到桌面。6.3 节的梯度下降对这些硬性界限无能为力，它只会在无约束的山坡上往下走。

好消息是，当目标是二次函数、约束是线性不等式时，问题就是一个二次规划 (QP)。它是凸的（6.2 节），没有局部最小值的烦恼，而且有成熟的求解器，规模几十到几百个变量时，几毫秒就能解完。于是一台人形机器人可以在 1 kHz 的控制回路里，每个周期解一次 QP 来决定所有关节的力矩；一个机械臂可以每 20 ms 解一次 MPC，让自己在速度、加速度和障碍的限制下贴着参考轨迹走。

线性规划 (LP) 是 QP 去掉二次项后的特例。它的几何最干净，是理解"约束到底怎样决定最优解"的最好起点：先看 LP，再看 QP 多出来的那一点自由度。

2直觉：多面体与顶点

每个线性不等式 $\mathbf a^\top\x \le b$ 把空间切成两半，只保留一侧。几个不等式同时成立的点，构成一个凸的多面体（二维里是凸多边形），叫作可行域。线性目标 $\mathbf c^\top\x$ 的等值线是一族平行直线（高维里是平行超平面）。把这族直线沿"代价下降"的方向推过去，直到再推就离开可行域为止，最后接触到的位置，就是最优解。

一个凸多边形被一条直线最后碰到的，只可能是一个顶点，或者恰好平行时的一整条边，不会是边的中间某个孤立点。所以线性规划的最优解（如果存在）总能在某个顶点取到。拖动下图的箭头，亲眼看一遍。

FIG 1线性规划：把目标线推到最后一个顶点

橙色箭头是"代价下降最快的方向" $-\mathbf c$，拖动箭头尖端改变它（接近某条边的法线时会吸附，此时整条边都是最优解）。紫色虚线是通过最优点的等值线 $\mathbf c^\top\x = \text{const}$。涂成红色阴影的区域是被不等式排除的一侧。点击任意顶点可把它设为单纯形法的起点，再按"单纯形行走"：它只沿边从一个顶点走到相邻的、代价更低的顶点。

试一试

转动箭头，让最优解从一个顶点跳到另一个顶点。注意：目标方向连续变化，最优解却是跳跃的。
让箭头吸附到某条边的法线上，得到一整条边都是最优解（无穷多个最优解）。
按"单纯形行走"，看它沿边走几步到达最优顶点。
切换到"不可行"：两个约束互相矛盾，可行域为空，问题无解。

核心洞见

LP 把一个连续的优化问题变成了组合问题：只需要在有限多个顶点里挑一个。单纯形法 (simplex) 沿着边走顶点；内点法 (interior-point) 则从内部穿过去逼近最优点。两者都靠同一件事：凸，所以"局部最优 = 全局最优"。

3二次规划：最优解离开了角

把线性目标换成凸二次函数，等值线从平行直线变成椭圆，中心 $\mathbf p$ 是不考虑约束时的最优点。如果 $\mathbf p$ 恰好在可行域内部，约束全部"休眠"，答案就是 $\mathbf p$ 本身；如果 $\mathbf p$ 在域外，最优解是最先碰到可行域的那个椭圆与可行域的接触点，它可以落在边的中间，也可以落在顶点上。

6.7 节的 KKT 条件在这里有一幅很具体的"受力图"：在接触点 $\x^\star$，目标想把你拉向 $\mathbf p$（橙色，$-\nabla f$），被碰到的那几面"墙"各自把你推回来（紫色，大小 $\lambda_i$），平衡时两者之和为零。推力不能为负（墙只能推不能拉）：$\lambda_i \ge 0$。没碰到的墙不出力：$\lambda_i = 0$。这些碰到的约束叫作有效约束 (active constraints)。

FIG 2QP 的受力图：有效约束与乘子

拖动 $\mathbf p$（空心圆）。椭圆是目标 $f(\x)=\tfrac12(\x-\mathbf p)^\top Q(\x-\mathbf p)$ 的等值线，经过解 $\x^\star$ 的那条加粗。求解器是真正的有效集枚举：对每一组可能的有效约束解一个线性方程组，取同时满足"可行"和"$\lambda\ge 0$"的那个解。橙色箭头是拉力 $-\nabla f(\x^\star)$，紫色箭头是墙的推力 $-\lambda_i\mathbf a_i$；它们首尾相接恰好抵消。

试一试

把 $\mathbf p$ 拖进可行域内部：没有任何有效约束，解就是 $\mathbf p$。
让解停在某条边的中间（一个有效约束）。观察拉力与推力共线。
让解停在一个顶点（两个有效约束，两个 $\lambda$ 都大于 0）。此时推力是两面墙的合力。
固定 $\mathbf p$ 在域外，转动椭圆的方向：解沿着边滑动，直到换到另一条边。

两种视角

几何视角：解是椭圆与可行域的"首次接触点"，也是 $\mathbf p$ 在 $Q$ 度量下到可行域的投影（$Q=I$ 时就是欧氏投影，1.9 节）。力学视角：解是各种力的平衡点，$\lambda_i$ 是墙 $i$ 出的力，也等于"把这面墙挪动一点，最优代价改变多少"（影子价格）。LP 只是其中的极端情形：椭圆被拉成无限宽，只剩下一个方向有区别。

4再看数学

提示：把鼠标悬停在公式中带底色的符号上，FIG 1、FIG 2 中对应的元素会被高亮。

标准形式

线性规划：

$$ \min_{\x\in\R^n}\ \hl{obj}{\mathbf c^\top\x} \quad\text{s.t.}\quad \hl{ineq}{A\x \le \mathbf b}, \quad C\x = \mathbf d $$

二次规划：多一个二次项，其中 $H$ 是对称半正定矩阵（$H\succeq 0$，问题才是凸的，6.2 节）：

$$ \min_{\x\in\R^n}\ \tfrac12\,\x^\top H\,\x + \mathbf g^\top\x \quad\text{s.t.}\quad A\x \le \mathbf b, \quad C\x = \mathbf d $$

FIG 2 中 $f=\tfrac12(\x-\mathbf p)^\top Q(\x-\mathbf p)$ 展开后正是 $H=Q,\ \mathbf g=-Q\mathbf p$（加一个不影响解的常数）。最常见的来源是最小二乘（1.13 节）：$\tfrac12\|M\x-\mathbf y\|^2$ 展开得 $H=M^\top M,\ \mathbf g=-M^\top\mathbf y$。所以 QP 就是"带不等式约束的最小二乘"。

KKT 条件与有效集

把 6.7 节的 KKT 条件用在 QP 上（只写不等式部分，记 $\mathbf a_i^\top$ 为 $A$ 的第 $i$ 行）：

$$ \hl{grad}{H\x + \mathbf g} + \sum_i \hl{lam}{\lambda_i}\,\mathbf a_i = \mathbf 0, \qquad A\x\le\mathbf b, \qquad \lambda_i \ge 0, \qquad \lambda_i\,(\mathbf a_i^\top\x - b_i)=0 $$

第一式就是 FIG 2 的受力平衡：$-\nabla f=\sum_i\lambda_i\mathbf a_i$（拉力恰好被墙的推力 $-\lambda_i\mathbf a_i$ 抵消）；最后一式叫互补松弛：墙要么没碰到（$\mathbf a_i^\top\x<b_i$，则 $\lambda_i=0$），要么碰到了（等号成立，$\lambda_i$ 可以大于 0）。

有效集法的想法：如果我们猜对了哪些约束有效（集合 $W$），问题就退化成只带等式约束的 QP，只需解一个线性方程组：

$$ \begin{bmatrix} H & A_W^\top \\ A_W & 0 \end{bmatrix} \begin{bmatrix} \x \\ \boldsymbol\lambda_W \end{bmatrix} = \begin{bmatrix} -\mathbf g \\ \mathbf b_W \end{bmatrix} $$

检查两件事：解是否满足所有没选入 $W$ 的约束（可行性）？$\boldsymbol\lambda_W$ 是否都 $\ge 0$？若某个 $\lambda_i<0$，说明这面墙在"拉"，应当把它从 $W$ 里放掉；若违反了某个没选入的约束，就把它加进 $W$。实用算法（primal active-set、Goldfarb–Idnani 等）就是这样一边加一边减地迭代。FIG 2 因为只有 5 个约束、$n=2$，直接枚举了全部 16 种可能的 $W$。

三类求解器

	做法	特点
Active set / simplex	沿着有效约束的"面"走，每步解线性方程组	热启动极好（MPC 里下个周期的解和这个周期很像），精确到顶点；最坏情况步数可能很多
Interior point	用对数障碍把约束"软化"，从内部走牛顿步逼近边界	迭代次数稳定（十几次），热启动差；大规模问题的首选
ADMM (OSQP)	交替做一次线性方程组求解和一次"投影到约束区间"	实现简单、矩阵只分解一次，精度中等；机器人里很常用。FIG 3、FIG 4 用的就是它

5机器人中的它：抓取力分配与 MPC

抓取：用最小的力握住物体

圆盘形物体受重力（或任意外力）$\mathbf w$，由 $k$ 个手指接触。每个手指 $i$ 能产生法向力 $f_{n,i}\ge 0$（只能推）和切向力 $f_{t,i}$（摩擦），而且必须在摩擦锥内：$|f_{t,i}|\le\mu f_{n,i}$。这是两个线性不等式。物体不动要求受力平衡与力矩平衡（线性等式）。夹爪还有最大握力 $f_{n,i}\le f_{\max}$。在所有能平衡的力分配里，我们挑总力平方最小的那组，以免捏坏物体：

$$ \min_{\mathbf f}\ \tfrac12\|\mathbf f\|^2 \quad\text{s.t.}\quad \sum_i \mathbf F_i = -\mathbf w,\ \ \sum_i \mathbf p_i\times\mathbf F_i = 0,\ \ 0\le f_{n,i}\le f_{\max},\ \ |f_{t,i}|\le\mu f_{n,i} $$

其中 $\mathbf F_i = f_{n,i}\mathbf n_i + f_{t,i}\mathbf t_i$ 是第 $i$ 个接触点施加给物体的力。目标是 $H=I$ 的二次函数，所有约束都是线性的：这是个 QP，下面用 ADMM 实时求解。

FIG 3抓取力分配 QP

拖动圆周上的空心圆移动手指。橙色是外力（默认重力，向下），蓝色箭头是 QP 求出的接触力，青色扇形是摩擦锥。每次拖动都在重新解一个 QP（OSQP 风格的 ADMM，400 次迭代）。若约束无法同时满足，约束违反量不会降为零，页面显示"无可行抓取"。

用两个手指（默认对置），把摩擦系数 $\mu$ 调小，直到抓不住。临界值大约是多少？（提示：外力大小为 1，默认 $f_{\max}=6$；每个手指的摩擦力要承担一半的重量，而法向力最多 $f_{\max}$。）
切换成三指，把 $\mu$ 调到 0.1：现在抓得住了。哪个手指几乎没有出力？
用两指，把外力方向转成水平：外力所推向的那个手指只用法向力就能直接抵抗它，不再需要摩擦（另一个手指几乎不出力）。

MPC：每个周期解一个 QP

模型预测控制 (MPC，见第 IV 部分) 的想法是：在每个控制周期，预测未来 $N$ 步，在满足约束的前提下选一串最好的控制量，只执行第一个，下个周期再重新规划。当动力学是线性的 $\mathbf x_{k+1}=A\mathbf x_k+B u_k$、代价是二次的、约束是线性的，整个预测问题就是一个 QP，决策变量是 $u_0,\dots,u_{N-1}$。下图是一个一维小车：质点位置 $p$、速度 $v$，控制量是加速度 $u$。目标是让位置跟上参考 $p_{\rm ref}$，约束是加速度有界、位置不能越过前方的"墙" $p_{\max}$。

FIG 4MPC 的 QP：约束一碰到就饱和

上图：位置预测（$N=25$ 步，$\Delta t=0.2$ s）、参考线（橙色，拖动右端的手柄）和墙（红色，也可拖动）。下图：预测控制量，触到 $\pm u_{\max}$ 的柱子涂成紫色（"饱和"）。每次改动都重新解一个 $25$ 变量的 QP。"运行 MPC"会真的闭环仿真：每步只执行 $u_0$，再用新状态重新解，墙靠近时车会提前减速。

把加速度上限 $u_{\max}$ 调小，让预测里饱和的柱子越来越多，直到整段起步加速都顶在上限上。
把参考拖到墙的后面：小车为什么最终停在墙前，而不是穿过去？
按"运行 MPC"，观察闭环轨迹。

真实系统里

全身控制 (whole-body control) 把"让质心加速度、末端加速度、姿态都符合期望"写成关于关节加速度和接触力的最小二乘，再加上力矩上限、摩擦锥、关节限位等不等式，每个 1 kHz 周期解一个 QP（第 IV 部分）。足式机器人 MPC（如 MIT Cheetah 的凸 MPC）把足底力当作决策变量，摩擦锥线性化为金字塔，也是一个 QP。常用求解器有 OSQP、qpOASES、ProxQP、HPIPM；它们都针对"每个周期问题结构不变、只有数字略变"做了热启动优化。

6常见误区

误区 1：忘了问题可能"不可行"或"无界"

约束互相矛盾（FIG 1 的"不可行"）时求解器会直接返回失败；目标可以无限下降而约束拦不住时问题是"无界"的。MPC 里最常见的不可行原因是硬约束与初始状态冲突：小车已经越过了位置约束，或者速度太大、在加速度上限内根本刹不住。解决办法是把这类约束变成软约束：加一个松弛变量 $s\ge 0$ 和大惩罚 $\rho s^2$，让问题永远可行，但违反时有代价。真实系统必须处理求解失败时用什么备用控制量。

误区 2：$H$ 不是半正定，却当 QP 用

如果 $H$ 有负特征值（比如由数值误差、或把 Hessian 近似写错造成），问题是非凸的：可能无界，也可能有多个局部最小。凸 QP 求解器遇到它可能报错、发散，或悄悄给出一个鞍点。排查办法是看 $H$ 的最小特征值（1.11 节）；对最小二乘形式 $M^\top M$ 则天然半正定，可以放心。

误区 3：把有效约束当成"边界附近"

有效约束的严格含义是"等号成立"，并且通常$\lambda>0$。解离某面墙 0.001 但 $\lambda=0$，这面墙对解毫无影响。反过来，退化情形（多个约束在同一个顶点相交，比如三面墙交于一点）会让乘子不唯一，也会让有效集法"绕圈"。数值上用容差（如 $10^{-9}$）判断，而不是 ==。

误区 4：变量尺度悬殊，ADMM 收敛慢

ADMM 是一阶方法，和 6.3 节的梯度下降一样怕条件数。位置以米计、力以千牛计时，要先对变量和约束行做缩放（OSQP 内置了 Ruiz 平衡）。另外，ADMM 给的是中等精度解，约束违反量可能有 $10^{-3}$，对安全相关约束要留余量或做后处理。

7小练习

1. 一个有界、非空可行域上的 LP，目标向量 $\mathbf c$ 不与任何一条边垂直。最优解在哪里？

线性目标的梯度处处等于 $\mathbf c\ne\mathbf 0$，内部不可能是最小点。等值线最后碰到凸多边形的位置只能是顶点，或者与某条边平行时的整条边；题目排除了后者，所以是唯一的一个顶点。

2. 一维 QP：$\min\ \tfrac12(x-3)^2$，约束 $x\le 1$。解是 $x^\star=1$，对应的乘子 $\lambda$ 是多少？（Lagrangian 为 $\tfrac12(x-3)^2+\lambda(x-1)$。）

平稳性：$(x-3)+\lambda=0$，代入 $x=1$ 得 $\lambda=2\ge 0$，符号正确（墙在推）。含义：拉力 $-\nabla f=3-x=2$ 被墙的推力 2 抵消；若把墙从 1 放到 $1+\delta$，最优代价大约下降 $2\delta$。

3. 有效集法解完一组猜测的有效约束后，发现其中一个乘子 $\lambda_j<0$。应该怎么做？

负乘子意味着这面墙在"拉"，而墙只能推。也就是说离开这面墙、往可行域内部走，目标还能继续下降，所以把它放出有效集。这正是 FIG 2 里枚举时会被淘汰的候选。

4. 两个对置的手指夹住一个重 10 N 的物体，摩擦系数 $\mu=0.4$，不计其他力。每个手指的法向力至少要多大？

两指对称，各自的摩擦力承担一半重量：$f_t=5$ N。摩擦锥要求 $f_t\le\mu f_n$，所以 $f_n\ge 5/0.4=12.5$ N。若夹爪最大握力低于这个数，抓取不可行，这正是 FIG 3 里把 $\mu$ 调小会失败的原因。

5. 线性动力学 + 二次代价 + 线性约束的 MPC，为什么能在毫秒内可靠求解？

变量是 $N$ 个控制量（FIG 4 里是 25 个），约束很多但线性，$H\succeq 0$。凸性保证全局最优，求解器的运行时间可预测，这对必须在固定周期内给出答案的实时控制至关重要。

8延伸阅读

S. Boyd & L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004, Ch. 4.3–4.4 — LP、QP 的标准形式、对偶与例子，免费在线
J. Nocedal & S. J. Wright, Numerical Optimization, 2nd ed., Springer, 2006, Ch. 13–16 — 单纯形法、有效集法与内点法 QP 的权威讲解
B. Stellato, G. Banjac, P. Goulart, A. Bemporad & S. Boyd, OSQP: An Operator Splitting Solver for Quadratic Programs, Mathematical Programming Computation, 2020 — FIG 3、FIG 4 所用 ADMM 迭代的出处
J. B. Rawlings, D. Q. Mayne & M. M. Diehl, Model Predictive Control: Theory, Computation, and Design, 2nd ed., 2017 — 线性 MPC 如何化为 QP