QP 问题（Quadratic Programming, 二次规划）是什么？

QP（Quadratic Programming，二次规划）是一类优化问题，其中目标函数是二次型函数，约束条件可以是线性等式或不等式。

QP 问题是线性规划（LP，Linear Programming）的扩展形式，广泛应用于最优控制、机器学习、金融优化、信号处理等领域。

🚩 一、QP 问题的数学定义

标准形式的 QP 问题如下：

min⁡x12xTQx+cTx

\min_{x} \quad \frac{1}{2} x^T Q x + c^T x

xmin​21​xTQx+cTx

s.t.Ax≤b,Ex=d

\text{s.t.} \quad Ax \leq b, \quad Ex = d

s.t.Ax≤b,Ex=d

其中：

变量：x∈Rnx \in \mathbb{R}^nx∈Rn（优化变量）目标函数：

QQQ 是 n×nn \times nn×n 对称矩阵（当 QQQ 是正定时，问题是凸的）ccc 是 nnn-维向量（线性项）

约束：

Ax≤bAx \leq bAx≤b（线性不等式约束，约束变量取值范围）Ex=dEx = dEx=d（线性等式约束）

🚩 二、QP 问题的分类

1. 线性二次规划（Convex QP）

如果矩阵 QQQ正定（Q≻0Q \succ 0Q≻0），则问题是凸优化问题，可以用梯度下降、KKT 条件、内点法（Interior Point Method）等方法求解。应用：

机器人轨迹优化（无人机规划）预测控制（Model Predictive Control, MPC）机器学习（SVM 分类）

2. 非凸二次规划（Non-convex QP）

如果 ( Q ) 非正定（可能有负特征值），则问题可能有多个局部最优解，求解更复杂，需要启发式方法或全局优化方法。应用：

经济学中的投资组合优化结构优化（力学系统）

3. 约束二次规划

约束类型：

仅等式约束（Equality Constrained QP, EQP）仅不等式约束混合等式/不等式约束

应用：

机器学习中的拉格朗日对偶（Lagrange Duality）约束最优控制（MPC）

🚩 三、QP 问题的求解方法

1. KKT 条件（Karush-Kuhn-Tucker 条件）

QP 问题满足 KKT 条件，其最优解满足：

Qx+c+ATλ+ETμ=0,Ax−b≤0,λ≥0,Ex−d=0,(等式约束)

\begin{aligned}

Qx + c + A^T \lambda + E^T \mu &= 0, \\

Ax - b &\leq 0, \quad \lambda \geq 0, \\

Ex - d &= 0, \quad \text{(等式约束)}

\end{aligned}

Qx+c+ATλ+ETμAx−bEx−d​=0,≤0,λ≥0,=0,(等式约束)​

其中：

λ\lambdaλ 是不等式约束的拉格朗日乘子μ\muμ 是等式约束的拉格朗日乘子

如果 ( Q \succ 0 )（正定），则 KKT 方程是一个线性方程组，可以直接求解最优解。

2. 内点法（Interior Point Method）

适用于大规模 QP 问题，收敛快。常用于最优控制（MPC）和机器学习（SVM）。

3. 主动集法（Active Set Method）

适用于小规模 QP 问题。适合处理约束随时间变化的情况，如实时轨迹优化。

4. 梯度投影法（Projected Gradient Descent）

适用于大规模约束 QP 问题，如约束神经网络训练。

🚩 四、QP 在强化学习、控制和无人机中的应用

1. 在最优控制（MPC, Model Predictive Control）中的应用

在 MPC（模型预测控制）中，每个时刻求解一个 QP 问题，以计算最优控制输入：

min⁡u∑t=0T(xtTQxt+utTRut)

\min_u \quad \sum_{t=0}^{T} \left( x_t^T Q x_t + u_t^T R u_t \right)

umin​t=0∑T​(xtT​Qxt​+utT​Rut​)

s.t.xt+1=Axt+But,xt∈X,ut∈U

\text{s.t.} \quad x_{t+1} = A x_t + B u_t, \quad x_t \in X, \quad u_t \in U

s.t.xt+1​=Axt​+But​,xt​∈X,ut​∈U

这里的 QP 优化保证：

控制输入 utu_tut​ 平滑变化轨迹在约束范围内

2. 机器人运动规划（Quadratic Trajectory Optimization）

无人机或机械臂轨迹规划：

min⁡x∑t=1T(xt−xtarget)TQ(xt−xtarget)

\min_x \quad \sum_{t=1}^{T} (x_t - x_{\text{target}})^T Q (x_t - x_{\text{target}})

xmin​t=1∑T​(xt​−xtarget​)TQ(xt​−xtarget​)

s.t.xt+1=f(xt,ut),xmin≤xt≤xmax

\text{s.t.} \quad x_{t+1} = f(x_t, u_t), \quad x_{\text{min}} \leq x_t \leq x_{\text{max}}

s.t.xt+1​=f(xt​,ut​),xmin​≤xt​≤xmax​

3. 机器学习（支持向量机 SVM）

SVM 的优化问题：

min⁡w12wTw

\min_w \quad \frac{1}{2} w^T w

wmin​21​wTw

s.t.yi(wTxi+b)≥1,∀i

\text{s.t.} \quad y_i (w^T x_i + b) \geq 1, \forall i

s.t.yi​(wTxi​+b)≥1,∀i

这个优化问题也是一个 QP 问题，使用拉格朗日乘子法求解。

🚩 五、QP 和 DP（动态规划）的关系

1. 经典 QP vs DP

特性QP (Quadratic Programming)DP (Dynamic Programming)目标函数二次型函数递归求解最优策略约束线性等式/不等式无约束（或通过贝尔曼方程处理）求解方法KKT, 内点法, 主动集法递归求解, 迭代法适用领域最优控制、金融优化强化学习、最优轨迹2. QP 在 DP 问题中的应用

在动态规划（DP）问题中，某些最优控制问题（如LQR, MPC）的子问题可以转化为 QP 问题：

LQR（线性二次调节）：

线性系统 + 二次成本 → QP 问题通过求解里卡提方程得到最优反馈控制律

MPC（模型预测控制）：

每个时刻求解一个 QP 问题，计算最优控制输入 utu_tut​确保控制输入平稳变化，满足状态/输入约束

🚩 六、总结

QP（Quadratic Programming，二次规划） 是优化问题的一种特殊形式，目标函数为二次型，约束为线性等式或不等式。QP 的求解方法：KKT条件、内点法、主动集法、梯度投影法等。QP 在最优控制、机器学习、金融优化等领域广泛应用，特别是在MPC、LQR、轨迹优化、SVM等问题中。

在强化学习和最优控制研究中，掌握QP 和 DP的关系非常重要，可以帮助解决 连续控制问题（如无人机轨迹规划） 和 最优决策问题 。

例子 🚀 以 MPC 控制无人机为例，详细解析 QP 求解过程

模型预测控制（Model Predictive Control, MPC） 是一种基于最优控制理论的方法，它在每个时间步求解一个**二次规划（QP, Quadratic Programming）**问题，以获得最优控制输入。

在本例中，我们详细解析 MPC 控制无人机的 QP 求解过程，从建模到求解的每个步骤。

📌 1. 建立无人机的动态模型

假设无人机是一个简单的线性离散系统，状态变量xtx_txt​ 和控制输入utu_tut​ 满足：

xt+1=Axt+But

x_{t+1} = A x_t + B u_t

xt+1​=Axt​+But​

其中：

状态 (x_t)：无人机的二维位置和速度（简化版）

xt=[px,py,vx,vy]T

x_t = [p_x, p_y, v_x, v_y]^T

xt​=[px​,py​,vx​,vy​]T

px,pyp_x, p_ypx​,py​：位置vx,vyv_x, v_yvx​,vy​：速度

控制输入 (u_t)：加速度输入

ut=[ax,ay]T

u_t = [a_x, a_y]^T

ut​=[ax​,ay​]T

( a_x, a_y )：无人机在 x 和 y 方向的加速度

系统动力学矩阵（离散化）：

A=[10dt0010dt00100001],B=[0000dt00dt]

A = \begin{bmatrix}

1 & 0 & dt & 0 \\

0 & 1 & 0 & dt \\

0 & 0 & 1 & 0 \\

0 & 0 & 0 & 1

\end{bmatrix}, \quad

B = \begin{bmatrix}

0 & 0 \\

0 & 0 \\

dt & 0 \\

0 & dt

\end{bmatrix}

A=​1000​0100​dt010​0dt01​​,B=​00dt0​000dt​​

其中 ( dt ) 是时间步长（离散化时间间隔）。

📌 2. 设定 MPC 的优化目标

MPC 通过优化 未来 ( N ) 步内的轨迹，生成最优控制输入 ( u_t )。

优化目标：

J=∑t=0N−1((xt−xref)TQ(xt−xref)+utTRut)

J = \sum_{t=0}^{N-1} \left( (x_t - x_{\text{ref}})^T Q (x_t - x_{\text{ref}}) + u_t^T R u_t \right)

J=t=0∑N−1​((xt​−xref​)TQ(xt​−xref​)+utT​Rut​)

( x_{\text{ref}} )：期望的轨迹（目标点）( Q )：状态误差的权重（鼓励轨迹跟踪）( R )：控制输入的权重（防止过大加速度）

约束条件：

xt+1=Axt+But

x_{t+1} = A x_t + B u_t

xt+1​=Axt​+But​

umin⁡≤ut≤umax⁡

u_{\min} \leq u_t \leq u_{\max}

umin​≤ut​≤umax​

xmin⁡≤xt≤xmax⁡

x_{\min} \leq x_t \leq x_{\max}

xmin​≤xt​≤xmax​

其中：

( u_{\min}, u_{\max} ) 限制无人机最大加速度( x_{\min}, x_{\max} ) 限制无人机运动范围

📌 3. 将 MPC 问题转换为标准 QP 问题

MPC 需要预测未来 ( N ) 步的状态，并优化控制输入。为此，我们展开状态方程 预测整个时间窗内的状态演化。

（1）构造状态预测矩阵

对 整个预测时间窗 (N)，我们将状态方程展开为矩阵形式：

X=Ax0+BU

X = \mathcal{A} x_0 + \mathcal{B} U

X=Ax0​+BU

其中：

状态向量（合并整个时间窗）：

X=[x1x2⋮xN],U=[u0u1⋮uN−1]

X = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_N \end{bmatrix}, \quad

U = \begin{bmatrix} u_0 \\ u_1 \\ \vdots \\ u_{N-1} \end{bmatrix}

X=​x1​x2​⋮xN​​​,U=​u0​u1​⋮uN−1​​​

状态转移矩阵：

A=[AA2⋮AN]

\mathcal{A} =

\begin{bmatrix}

A \\ A^2 \\ \vdots \\ A^N

\end{bmatrix}

A=​AA2⋮AN​​

控制影响矩阵：

B=[B00…0ABB0…0A2BABB…0⋮⋮⋮⋱⋮AN−1BAN−2BAN−3B…B]

\mathcal{B} =

\begin{bmatrix}

B & 0 & 0 & \dots & 0 \\

A B & B & 0 & \dots & 0 \\

A^2 B & A B & B & \dots & 0 \\

\vdots & \vdots & \vdots & \ddots & \vdots \\

A^{N-1} B & A^{N-2} B & A^{N-3} B & \dots & B

\end{bmatrix}

B=​BABA2B⋮AN−1B​0BAB⋮AN−2B​00B⋮AN−3B​………⋱…​000⋮B​​

最终预测模型：

X=Ax0+BU

X = \mathcal{A} x_0 + \mathcal{B} U

X=Ax0​+BU

（2）将目标函数转化为 QP 形式

J=(X−Xref)TQ(X−Xref)+UTRU

J = (X - X_{\text{ref}})^T Q (X - X_{\text{ref}}) + U^T R U

J=(X−Xref​)TQ(X−Xref​)+UTRU

代入状态预测矩阵 ( X = \mathcal{A} x_0 + \mathcal{B} U )：

J=(Ax0+BU−Xref)TQ(Ax0+BU−Xref)+UTRU

J = (\mathcal{A} x_0 + \mathcal{B} U - X_{\text{ref}})^T Q (\mathcal{A} x_0 + \mathcal{B} U - X_{\text{ref}}) + U^T R U

J=(Ax0​+BU−Xref​)TQ(Ax0​+BU−Xref​)+UTRU

展开并整理得：

J=UT(BTQB+R)U+2UTBTQ(Ax0−Xref)+(Ax0−Xref)TQ(Ax0−Xref)

J = U^T (\mathcal{B}^T Q \mathcal{B} + R) U + 2 U^T \mathcal{B}^T Q (\mathcal{A} x_0 - X_{\text{ref}}) + (\mathcal{A} x_0 - X_{\text{ref}})^T Q (\mathcal{A} x_0 - X_{\text{ref}})

J=UT(BTQB+R)U+2UTBTQ(Ax0​−Xref​)+(Ax0​−Xref​)TQ(Ax0​−Xref​)

最终标准 QP 形式：

min⁡U12UTHU+fTU

\min_U \quad \frac{1}{2} U^T H U + f^T U

Umin​21​UTHU+fTU

其中：

Hessian 矩阵（正定矩阵）：

H=BTQB+R

H = \mathcal{B}^T Q \mathcal{B} + R

H=BTQB+R线性项：

f=BTQ(Ax0−Xref)

f = \mathcal{B}^T Q (\mathcal{A} x_0 - X_{\text{ref}})

f=BTQ(Ax0​−Xref​)

约束条件变为：

控制输入约束：

Umin⁡≤U≤Umax⁡

U_{\min} \leq U \leq U_{\max}

Umin​≤U≤Umax​状态约束：

Xmin⁡≤X≤Xmax⁡

X_{\min} \leq X \leq X_{\max}

Xmin​≤X≤Xmax​

📌 4. 使用 QP 求解器计算最优控制输入

（1）QP 求解方法

MPC 需要每个时间步求解 QP 问题，求解方法包括：

内点法（Interior Point Method）：适用于大规模 QP 问题主动集法（Active Set Method）：适用于小规模问题梯度投影法（Projected Gradient Descent）：适用于约束优化

（2）求解步骤

构造 QP 矩阵 H,fH, fH,f设定约束条件调用 QP 求解器（如 OSQP, quadprog, CVXPY）获得最优控制输入 U∗U^*U∗执行第一个控制步 u0u_0u0​，并进入下一时间步

🚀 5. 总结

MPC 通过求解 QP 问题获得最优控制输入，每个时间步优化未来 (N) 步的轨迹。QP 通过二次优化目标+线性约束求解，最终转换为标准凸优化问题。QP 求解方法（内点法、主动集法）可高效求解控制问题，在无人机轨迹规划、自主导航、自动驾驶等领域广泛应用。

MPC + QP 是现代最优控制的核心技术之一，也是强化学习、控制系统研究的重要基础。🚀🚀🚀