Part I · 第 6 章优化 · 6.8Part I · Ch. 6 Optimization · 6.8

线性规划与二次规划Linear & Quadratic Programming

目标是线性的、约束也是线性的，最优解一定躲在多面体的某个角上，这就是线性规划。把目标换成二次函数，最优解就可以离开角，停在棱上甚至内部：这就是二次规划。机器人每个控制周期里解的 MPC、全身控制和抓取力分配，几乎都是二次规划，因为它又快又可靠。 Linear objective, linear constraints: the optimum must hide in a corner of a polytope. That is linear programming. Swap the objective for a quadratic and the optimum may leave the corner and sit on an edge or in the interior: quadratic programming. The MPC, whole-body control and grasp-force allocation that robots solve every control cycle are almost all QPs, because QPs are fast and reliable.

约 25 分钟~25 min 前置：1.13 最小二乘 · 6.2 凸性 · 6.7 约束优化与 KKTPrereqs: 1.13 Least squares · 6.2 Convexity · 6.7 Constrained optimization & KKT 4 个交互4 interactives

1为什么机器人需要它Why robots need this

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

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

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

A robot's world is full of inequalities: joint torques cannot exceed the motor limit, foot contact forces must lie in a friction cone, a gripper finger can only push and never pull, the end effector must not hit the table. The gradient descent of Lesson 6.3 knows nothing about such hard limits; it just walks downhill on an unconstrained slope.

The good news: when the objective is a quadratic and the constraints are linear inequalities, the problem is a quadratic program (QP). It is convex (Lesson 6.2), so there are no local minima to fear, and mature solvers handle tens to hundreds of variables in milliseconds. A humanoid can therefore solve a QP every cycle of a 1 kHz control loop to pick all its joint torques; an arm can solve an MPC problem every 20 ms to track a reference while respecting velocity, acceleration and obstacle limits.

A linear program (LP) is the QP with the quadratic term removed. Its geometry is the cleanest there is, so it is the best place to learn how constraints decide the optimum: LP first, then the one extra degree of freedom a QP adds.

2直觉：多面体与顶点Intuition: polytopes and vertices

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

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

Each linear inequality $\mathbf a^\top\x \le b$ cuts space in half and keeps one side. The points satisfying several inequalities at once form a convex polytope (a convex polygon in 2D), the feasible set. The level sets of a linear objective $\mathbf c^\top\x$ are parallel lines (parallel hyperplanes in higher dimensions). Slide that family of lines in the direction of decreasing cost until pushing any further would leave the feasible set; where it touches last is the optimum.

The last thing a line touches on a convex polygon can only be a vertex, or a whole edge if the line happens to be parallel to it, never an isolated point in the middle of an edge. So a linear program, if it has an optimum, always has one at a vertex. Drag the arrow below and see it for yourself.

FIG 1线性规划：把目标线推到最后一个顶点Linear programming: push the objective line to the last vertex

橙色箭头是"代价下降最快的方向" $-\mathbf c$，拖动箭头尖端改变它（接近某条边的法线时会吸附，此时整条边都是最优解）。紫色虚线是通过最优点的等值线 $\mathbf c^\top\x = \text{const}$。涂成红色阴影的区域是被不等式排除的一侧。点击任意顶点可把它设为单纯形法的起点，再按"单纯形行走"：它只沿边从一个顶点走到相邻的、代价更低的顶点。 The amber arrow is the direction of steepest cost decrease, $-\mathbf c$; drag its tip to change it (it snaps near an edge normal, where the whole edge is optimal). The dashed purple line is the level line $\mathbf c^\top\x = \text{const}$ through the optimum. The red-tinted regions are the sides excluded by the inequalities. Click any vertex to make it the simplex start, then press "Simplex walk": it only moves along edges, from a vertex to an adjacent vertex of lower cost.

试一试Try this

转动箭头，让最优解从一个顶点跳到另一个顶点。注意：目标方向连续变化，最优解却是跳跃的。Rotate the arrow so the optimum jumps from one vertex to another. The objective changes continuously but the optimum jumps.
让箭头吸附到某条边的法线上，得到一整条边都是最优解（无穷多个最优解）。Snap the arrow to an edge normal so that a whole edge is optimal (infinitely many optima).
按"单纯形行走"，看它沿边走几步到达最优顶点。Press "Simplex walk" and count how many edge steps it takes to reach the optimal vertex.
切换到"不可行"：两个约束互相矛盾，可行域为空，问题无解。Switch to "Infeasible": two constraints contradict each other, the feasible set is empty and there is no solution.

核心洞见Key insight

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

An LP turns a continuous optimization problem into a combinatorial one: you only need to pick among finitely many vertices. The simplex method walks from vertex to vertex along edges; interior-point methods cut through the inside to approach the optimum. Both rely on convexity: a local optimum is the global one.

3二次规划：最优解离开了角Quadratic programming: the optimum leaves the corner

把线性目标换成凸二次函数，等值线从平行直线变成椭圆，中心 $\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)。

Replace the linear objective by a convex quadratic and the level sets turn from parallel lines into ellipses centered at $\mathbf p$, the unconstrained optimum. If $\mathbf p$ happens to be inside the feasible set, every constraint is "asleep" and the answer is $\mathbf p$ itself. If $\mathbf p$ is outside, the solution is the point where the smallest ellipse first touches the feasible set; it may sit in the middle of an edge or at a vertex.

The KKT conditions of Lesson 6.7 have a very concrete "free-body diagram" here. At the touching point $\x^\star$ the objective pulls you toward $\mathbf p$ (amber, $-\nabla f$), and each wall you touch pushes back (purple, magnitude $\lambda_i$); at balance they sum to zero. A wall can only push, never pull, so $\lambda_i \ge 0$; a wall you do not touch exerts nothing, $\lambda_i = 0$. The constraints you touch are the active constraints.

FIG 2QP 的受力图：有效约束与乘子QP as a force balance: active constraints and multipliers

拖动 $\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$；它们首尾相接恰好抵消。 Drag $\mathbf p$ (hollow circle). The ellipses are level sets of $f(\x)=\tfrac12(\x-\mathbf p)^\top Q(\x-\mathbf p)$, with the one through the solution $\x^\star$ drawn bold. The solver is a genuine active-set enumeration: for each candidate set of active constraints it solves a linear system and keeps the one that is both feasible and has $\lambda\ge 0$. The amber arrow is the pull $-\nabla f(\x^\star)$, the purple arrows are the wall pushes $-\lambda_i\mathbf a_i$; together they cancel exactly.

试一试Try this

把 $\mathbf p$ 拖进可行域内部：没有任何有效约束，解就是 $\mathbf p$。Drag $\mathbf p$ inside the feasible set: no active constraint, the solution is $\mathbf p$.
让解停在某条边的中间（一个有效约束）。观察拉力与推力共线。Make the solution sit in the middle of an edge (one active constraint). Notice pull and push are collinear.
让解停在一个顶点（两个有效约束，两个 $\lambda$ 都大于 0）。此时推力是两面墙的合力。Make the solution sit at a vertex (two active constraints, both $\lambda$ positive). The push is the resultant of two walls.
固定 $\mathbf p$ 在域外，转动椭圆的方向：解沿着边滑动，直到换到另一条边。With $\mathbf p$ outside, rotate the ellipse: the solution slides along the edge until it switches to another edge.

两种视角Two views

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

Geometric view: the solution is the "first contact" of the ellipse and the feasible set; equivalently it is the projection of $\mathbf p$ onto the feasible set in the $Q$-metric (the Euclidean projection of Lesson 1.9 when $Q=I$). Mechanical view: the solution is where the forces balance, and $\lambda_i$ is the force of wall $i$, which is also how much the optimal cost changes if you move that wall slightly (a shadow price). An LP is the extreme case: the ellipse stretched infinitely wide so only one direction matters.

4再看数学The math

提示：把鼠标悬停在公式中带底色的符号上，FIG 1、FIG 2 中对应的元素会被高亮。Tip: hover the highlighted symbols in the formulas; the matching elements in FIG 1 and FIG 2 light up.

标准形式Standard forms

线性规划：

Linear program:

$$ \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 节）：

Quadratic program: one extra quadratic term, where $H$ is symmetric positive semidefinite ($H\succeq 0$ makes the problem convex, Lesson 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 就是"带不等式约束的最小二乘"。

The $f=\tfrac12(\x-\mathbf p)^\top Q(\x-\mathbf p)$ of FIG 2 expands to exactly $H=Q,\ \mathbf g=-Q\mathbf p$ (plus a constant that does not change the minimizer). The most common source is least squares (Lesson 1.13): $\tfrac12\|M\x-\mathbf y\|^2$ expands to $H=M^\top M,\ \mathbf g=-M^\top\mathbf y$. A QP is least squares with inequality constraints.

KKT 条件与有效集KKT conditions and the active set

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

Apply the KKT conditions of Lesson 6.7 to a QP (inequality part only; $\mathbf a_i^\top$ is row $i$ of $A$):

$$ \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）。

The first equation is the force balance of FIG 2: $-\nabla f=\sum_i\lambda_i\mathbf a_i$ (the pull is exactly cancelled by the wall pushes $-\lambda_i\mathbf a_i$). The last one is complementary slackness: a wall is either untouched ($\mathbf a_i^\top\x<b_i$, so $\lambda_i=0$) or touched (equality holds and $\lambda_i$ may be positive).

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

The idea of the active-set method: if we guess right which constraints are active (the set $W$), the problem collapses to an equality-constrained QP, and that needs just one linear solve:

$$ \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$。

Then check two things: does the solution satisfy every constraint left out of $W$ (feasibility)? Are all $\boldsymbol\lambda_W\ge 0$? If some $\lambda_i<0$, that wall is "pulling" and must be released from $W$; if some unlisted constraint is violated, add it to $W$. Practical algorithms (primal active-set, Goldfarb–Idnani, ...) iterate by adding and dropping in exactly this way. FIG 2 has only 5 constraints and $n=2$, so it simply enumerates all 16 possible sets $W$.

三类求解器Three families of solvers

	做法Idea	特点Character
Active set / simplex	沿着有效约束的"面"走，每步解线性方程组Walk along faces of active constraints, one linear solve per step	热启动极好（MPC 里下个周期的解和这个周期很像），精确到顶点；最坏情况步数可能很多Excellent warm starts (next MPC cycle looks like this one) and exact at vertices; worst-case step count can be large
Interior point	用对数障碍把约束"软化"，从内部走牛顿步逼近边界Soften constraints with a log barrier and take Newton steps from the interior toward the boundary	迭代次数稳定（十几次），热启动差；大规模问题的首选A steady dozen or so iterations, poor warm starts; the choice for big problems
ADMM (OSQP)	交替做一次线性方程组求解和一次"投影到约束区间"Alternate a linear solve with a "clip to the constraint interval" step	实现简单、矩阵只分解一次，精度中等；机器人里很常用。FIG 3、FIG 4 用的就是它Simple, factorizes the matrix once, medium accuracy; popular in robotics. FIG 3 and FIG 4 use it

5机器人中的它：抓取力分配与 MPCIn robotics: grasp-force allocation and MPC

抓取：用最小的力握住物体Grasping: hold the object with the least force

圆盘形物体受重力（或任意外力）$\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}$。在所有能平衡的力分配里，我们挑总力平方最小的那组，以免捏坏物体：

A disc-shaped object under gravity (or any external force) $\mathbf w$ is held by $k$ fingers. Finger $i$ can produce a normal force $f_{n,i}\ge 0$ (push only) and a tangential friction force $f_{t,i}$, which must lie in the friction cone: $|f_{t,i}|\le\mu f_{n,i}$. These are two linear inequalities. For the object not to move we need force and torque balance (linear equalities). The gripper also has a maximum squeeze $f_{n,i}\le f_{\max}$. Among all balanced force allocations, pick the one with the smallest squared total force, so we do not crush the object:

$$ \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 实时求解。

Here $\mathbf F_i = f_{n,i}\mathbf n_i + f_{t,i}\mathbf t_i$ is the force finger $i$ applies to the object. The objective is a quadratic with $H=I$ and all constraints are linear: a QP, solved live below with ADMM.

FIG 3抓取力分配 QPGrasp-force allocation QP

拖动圆周上的空心圆移动手指。橙色是外力（默认重力，向下），蓝色箭头是 QP 求出的接触力，青色扇形是摩擦锥。每次拖动都在重新解一个 QP（OSQP 风格的 ADMM，400 次迭代）。若约束无法同时满足，约束违反量不会降为零，页面显示"无可行抓取"。 Drag the hollow circles around the rim to move the fingers. Amber is the external load (gravity by default, pointing down), blue arrows are the contact forces found by the QP, and the cyan wedges are friction cones. Every drag re-solves a QP (OSQP-style ADMM, 400 iterations). If the constraints cannot all hold, the violation does not go to zero and the page reports "no feasible grasp".

用两个手指（默认对置），把摩擦系数 $\mu$ 调小，直到抓不住。临界值大约是多少？（提示：外力大小为 1，默认 $f_{\max}=6$；每个手指的摩擦力要承担一半的重量，而法向力最多 $f_{\max}$。）With two fingers (opposed by default), lower the friction coefficient $\mu$ until the grasp fails. What is the critical value? (Hint: the load has magnitude 1 and $f_{\max}=6$ by default; each finger's friction carries half the weight, while its normal force is at most $f_{\max}$.)
切换成三指，把 $\mu$ 调到 0.1：现在抓得住了。哪个手指几乎没有出力？Switch to three fingers with $\mu=0.1$: the grasp holds now. Which finger is almost idle?
用两指，把外力方向转成水平：外力所推向的那个手指只用法向力就能直接抵抗它，不再需要摩擦（另一个手指几乎不出力）。With two fingers, turn the load horizontal: the finger the load pushes against resists it with a pure normal force, and friction is no longer needed (the other finger is almost idle).

MPC：每个周期解一个 QPMPC: one QP per control cycle

模型预测控制 (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}$。

Model predictive control (MPC, Part IV) works like this: at each control cycle, predict $N$ steps ahead, choose the best control sequence that respects the constraints, apply only the first, and re-plan next cycle. When the dynamics are linear, $\mathbf x_{k+1}=A\mathbf x_k+B u_k$, the cost is quadratic and the constraints are linear, the whole prediction problem is a QP in $u_0,\dots,u_{N-1}$. Below is a 1D cart: position $p$, velocity $v$, control input acceleration $u$. The goal is to follow a reference $p_{\rm ref}$; the constraints are bounded acceleration and a "wall" $p_{\max}$ ahead that must not be crossed.

FIG 4MPC 的 QP：约束一碰到就饱和The MPC QP: constraints saturate the moment they bind

上图：位置预测（$N=25$ 步，$\Delta t=0.2$ s）、参考线（橙色，拖动右端的手柄）和墙（红色，也可拖动）。下图：预测控制量，触到 $\pm u_{\max}$ 的柱子涂成紫色（"饱和"）。每次改动都重新解一个 $25$ 变量的 QP。"运行 MPC"会真的闭环仿真：每步只执行 $u_0$，再用新状态重新解，墙靠近时车会提前减速。 Top: the position prediction ($N=25$ steps, $\Delta t=0.2$ s), the reference (amber, drag the handle at the right) and the wall (red, also draggable). Bottom: the planned control inputs; bars touching $\pm u_{\max}$ are purple ("saturated"). Every change re-solves a 25-variable QP. "Run MPC" simulates the closed loop for real: apply only $u_0$ each step, then re-solve from the new state; the cart brakes early as the wall approaches.

把加速度上限 $u_{\max}$ 调小，让预测里饱和的柱子越来越多，直到整段起步加速都顶在上限上。Lower the acceleration limit $u_{\max}$ and watch more bars saturate until the whole start-up acceleration sits on the limit.
把参考拖到墙的后面：小车为什么最终停在墙前，而不是穿过去？Drag the reference behind the wall: why does the cart end up in front of the wall rather than going through?
按"运行 MPC"，观察闭环轨迹。Press "Run MPC" and watch the closed-loop trajectory.

真实系统里In real systems

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

Whole-body control writes "make the center-of-mass acceleration, end-effector acceleration and posture match the desired values" as a least-squares problem in joint accelerations and contact forces, adds torque limits, friction cones and joint limits as inequalities, and solves one QP per 1 kHz cycle (Part IV). Legged-robot MPC (e.g. the convex MPC of MIT Cheetah) treats foot forces as decision variables and linearizes friction cones into pyramids: again a QP. Common solvers are OSQP, qpOASES, ProxQP and HPIPM; all exploit warm starts, since the problem structure is the same every cycle and only the numbers change slightly.

6常见误区Common pitfalls

误区 1：忘了问题可能"不可行"或"无界"Pitfall 1: forgetting a problem can be infeasible or unbounded

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

When constraints contradict each other (the "Infeasible" mode of FIG 1) a solver simply reports failure; when the cost can fall forever and no constraint stops it, the problem is "unbounded". The most common cause of infeasibility in MPC is a hard constraint conflicting with the initial state: the cart is already past the position limit, or moving so fast it cannot brake within the acceleration bound. The cure is to make such constraints soft: add a slack variable $s\ge 0$ with a large penalty $\rho s^2$, so the problem is always feasible but violations cost something. A real system must also decide what control to use when the solver fails.

误区 2：$H$ 不是半正定，却当 QP 用Pitfall 2: using a QP solver when $H$ is not positive semidefinite

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

If $H$ has a negative eigenvalue (from numerical error or a wrongly approximated Hessian) the problem is nonconvex: possibly unbounded, possibly with several local minima. A convex QP solver may error out, diverge, or quietly return a saddle point. Check the smallest eigenvalue of $H$ (Lesson 1.11); an $M^\top M$ from a least-squares form is positive semidefinite automatically.

误区 3：把有效约束当成"边界附近"Pitfall 3: treating "active" as "near the boundary"

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

"Active" strictly means "equality holds", and usually $\lambda>0$. A solution that sits 0.001 from a wall with $\lambda=0$ is not influenced by that wall at all. Conversely, degenerate cases (several constraints meeting at one vertex, e.g. three walls through a point) make the multipliers non-unique and can make active-set methods cycle. Test with a tolerance (say $10^{-9}$), never with ==.

误区 4：变量尺度悬殊，ADMM 收敛慢Pitfall 4: wildly different scales make ADMM crawl

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

ADMM is a first-order method and, like the gradient descent of Lesson 6.3, dislikes bad conditioning. If positions are in meters and forces in kilonewtons, scale variables and constraint rows first (OSQP does Ruiz equilibration internally). Also, ADMM returns a medium-accuracy answer whose constraint violation may be around $10^{-3}$; for safety-critical constraints, leave a margin or polish the result.

7小练习Check yourself

1. 一个有界、非空可行域上的 LP，目标向量 $\mathbf c$ 不与任何一条边垂直。最优解在哪里？1. An LP over a bounded, nonempty feasible set, with a cost vector $\mathbf c$ not perpendicular to any edge. Where is the optimum?

线性目标的梯度处处等于 $\mathbf c\ne\mathbf 0$，内部不可能是最小点。等值线最后碰到凸多边形的位置只能是顶点，或者与某条边平行时的整条边；题目排除了后者，所以是唯一的一个顶点。The gradient of a linear objective equals $\mathbf c\ne\mathbf 0$ everywhere, so no interior point can be a minimizer. The last contact of a level line with a convex polygon is a vertex, or a whole edge if the line is parallel to it; the second case is excluded, so it is a single vertex.

2. 一维 QP：$\min\ \tfrac12(x-3)^2$，约束 $x\le 1$。解是 $x^\star=1$，对应的乘子 $\lambda$ 是多少？（Lagrangian 为 $\tfrac12(x-3)^2+\lambda(x-1)$。）2. A 1D QP: $\min\ \tfrac12(x-3)^2$ subject to $x\le 1$. The solution is $x^\star=1$. What is the multiplier $\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$。Stationarity: $(x-3)+\lambda=0$; at $x=1$ this gives $\lambda=2\ge 0$, the right sign (the wall pushes). Meaning: the pull $-\nabla f=3-x=2$ is cancelled by a wall push of 2; moving the wall from 1 to $1+\delta$ lowers the optimal cost by about $2\delta$.

3. 有效集法解完一组猜测的有效约束后，发现其中一个乘子 $\lambda_j<0$。应该怎么做？3. After solving for a guessed active set, the active-set method finds one multiplier $\lambda_j<0$. What should it do?

负乘子意味着这面墙在"拉"，而墙只能推。也就是说离开这面墙、往可行域内部走，目标还能继续下降，所以把它放出有效集。这正是 FIG 2 里枚举时会被淘汰的候选。A negative multiplier means the wall is "pulling", and walls can only push. So moving off that wall into the interior still decreases the objective, and the constraint is released from the active set. These are exactly the candidates FIG 2's enumeration rejects.

4. 两个对置的手指夹住一个重 10 N 的物体，摩擦系数 $\mu=0.4$，不计其他力。每个手指的法向力至少要多大？4. Two opposed fingers hold an object weighing 10 N, with friction coefficient $\mu=0.4$ and no other forces. What is the minimum normal force per finger?

两指对称，各自的摩擦力承担一半重量：$f_t=5$ N。摩擦锥要求 $f_t\le\mu f_n$，所以 $f_n\ge 5/0.4=12.5$ N。若夹爪最大握力低于这个数，抓取不可行，这正是 FIG 3 里把 $\mu$ 调小会失败的原因。By symmetry each finger's friction carries half the weight: $f_t=5$ N. The friction cone requires $f_t\le\mu f_n$, so $f_n\ge 5/0.4=12.5$ N. If the gripper's maximum squeeze is below that, the grasp is infeasible, which is why lowering $\mu$ in FIG 3 makes it fail.

5. 线性动力学 + 二次代价 + 线性约束的 MPC，为什么能在毫秒内可靠求解？5. Why can MPC with linear dynamics, a quadratic cost and linear constraints be solved reliably in milliseconds?

变量是 $N$ 个控制量（FIG 4 里是 25 个），约束很多但线性，$H\succeq 0$。凸性保证全局最优，求解器的运行时间可预测，这对必须在固定周期内给出答案的实时控制至关重要。The variables are the $N$ control inputs (25 in FIG 4); constraints are numerous but linear, and $H\succeq 0$. Convexity guarantees a global optimum and a predictable solve time, which is essential for real-time control that must answer within a fixed cycle.

8延伸阅读Further reading

S. Boyd & L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004, Ch. 4.3–4.4 — LP、QP 的标准形式、对偶与例子，免费在线standard forms, duality and examples of LP and QP; free online
J. Nocedal & S. J. Wright, Numerical Optimization, 2nd ed., Springer, 2006, Ch. 13–16 — 单纯形法、有效集法与内点法 QP 的权威讲解the standard treatment of the simplex, active-set and interior-point methods for LP and 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 迭代的出处the source of the ADMM iteration used in FIG 3 and FIG 4
J. B. Rawlings, D. Q. Mayne & M. M. Diehl, Model Predictive Control: Theory, Computation, and Design, 2nd ed., 2017 — 线性 MPC 如何化为 QPhow linear MPC becomes a QP