通辽正规网站建设,网页制作教程,西安关键字优化哪家好,wordpress主题备案号QP 问题#xff08;Quadratic Programming, 二次规划#xff09;是什么#xff1f;
QP#xff08;Quadratic Programming#xff0c;二次规划#xff09;是一类优化问题#xff0c;其中目标函数是二次型函数#xff0c;约束条件可以是线性等式或不等式。
QP 问题是线…QP 问题Quadratic Programming, 二次规划是什么
QPQuadratic Programming二次规划是一类优化问题其中目标函数是二次型函数约束条件可以是线性等式或不等式。
QP 问题是线性规划LPLinear Programming的扩展形式广泛应用于最优控制、机器学习、金融优化、信号处理等领域。 一、QP 问题的数学定义
标准形式的 QP 问题如下 min x 1 2 x T Q x c T x \min_{x} \quad \frac{1}{2} x^T Q x c^T x xmin21xTQxcTx s.t. A x ≤ b , E x d \text{s.t.} \quad Ax \leq b, \quad Ex d s.t.Ax≤b,Exd
其中
变量 x ∈ R n x \in \mathbb{R}^n x∈Rn优化变量目标函数 Q Q Q 是 n × n n \times n n×n 对称矩阵当 Q Q Q 是正定时问题是凸的 c c c 是 n n n-维向量线性项 约束 A x ≤ b Ax \leq b Ax≤b线性不等式约束约束变量取值范围 E x d Ex d Exd线性等式约束 二、QP 问题的分类
1. 线性二次规划Convex QP
如果矩阵 Q Q Q正定 Q ≻ 0 Q \succ 0 Q≻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 条件其最优解满足 Q x c A T λ E T μ 0 , A x − b ≤ 0 , λ ≥ 0 , E x − 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} QxcATλETμAx−bEx−d0,≤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 0 T ( x t T Q x t u t T R u t ) \min_u \quad \sum_{t0}^{T} \left( x_t^T Q x_t u_t^T R u_t \right) umint0∑T(xtTQxtutTRut) s.t. x t 1 A x t B u t , x t ∈ X , u t ∈ U \text{s.t.} \quad x_{t1} A x_t B u_t, \quad x_t \in X, \quad u_t \in U s.t.xt1AxtBut,xt∈X,ut∈U
这里的 QP 优化保证
控制输入 u t u_t ut 平滑变化轨迹在约束范围内
2. 机器人运动规划Quadratic Trajectory Optimization
无人机或机械臂轨迹规划 min x ∑ t 1 T ( x t − x target ) T Q ( x t − x target ) \min_x \quad \sum_{t1}^{T} (x_t - x_{\text{target}})^T Q (x_t - x_{\text{target}}) xmint1∑T(xt−xtarget)TQ(xt−xtarget) s.t. x t 1 f ( x t , u t ) , x min ≤ x t ≤ x max \text{s.t.} \quad x_{t1} f(x_t, u_t), \quad x_{\text{min}} \leq x_t \leq x_{\text{max}} s.t.xt1f(xt,ut),xmin≤xt≤xmax
3. 机器学习支持向量机 SVM
SVM 的优化问题 min w 1 2 w T w \min_w \quad \frac{1}{2} w^T w wmin21wTw s.t. y i ( w T x i b ) ≥ 1 , ∀ i \text{s.t.} \quad y_i (w^T x_i b) \geq 1, \forall i s.t.yi(wTxib)≥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 问题计算最优控制输入 u t u_t ut确保控制输入平稳变化满足状态/输入约束 六、总结
QPQuadratic Programming二次规划 是优化问题的一种特殊形式目标函数为二次型约束为线性等式或不等式。QP 的求解方法KKT条件、内点法、主动集法、梯度投影法等。QP 在最优控制、机器学习、金融优化等领域广泛应用特别是在MPC、LQR、轨迹优化、SVM等问题中。
在强化学习和最优控制研究中掌握QP 和 DP的关系非常重要可以帮助解决 连续控制问题如无人机轨迹规划 和 最优决策问题 。 例子 以 MPC 控制无人机为例详细解析 QP 求解过程
模型预测控制Model Predictive Control, MPC 是一种基于最优控制理论的方法它在每个时间步求解一个**二次规划QP, Quadratic Programming**问题以获得最优控制输入。
在本例中我们详细解析 MPC 控制无人机的 QP 求解过程从建模到求解的每个步骤。 1. 建立无人机的动态模型
假设无人机是一个简单的线性离散系统状态变量 x t x_t xt 和控制输入 u t u_t ut 满足 x t 1 A x t B u t x_{t1} A x_t B u_t xt1AxtBut
其中 状态 (x_t)无人机的二维位置和速度简化版 x t [ p x , p y , v x , v y ] T x_t [p_x, p_y, v_x, v_y]^T xt[px,py,vx,vy]T p x , p y p_x, p_y px,py位置 v x , v y v_x, v_y vx,vy速度 控制输入 (u_t)加速度输入 u t [ a x , a y ] T u_t [a_x, a_y]^T ut[ax,ay]T ( a_x, a_y )无人机在 x 和 y 方向的加速度 系统动力学矩阵离散化 A [ 1 0 d t 0 0 1 0 d t 0 0 1 0 0 0 0 1 ] , B [ 0 0 0 0 d t 0 0 d t ] 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 10000100dt0100dt01 ,B 00dt0000dt 其中 ( dt ) 是时间步长离散化时间间隔。 2. 设定 MPC 的优化目标
MPC 通过优化 未来 ( N ) 步内的轨迹生成最优控制输入 ( u_t )。
优化目标 J ∑ t 0 N − 1 ( ( x t − x ref ) T Q ( x t − x ref ) u t T R u t ) J \sum_{t0}^{N-1} \left( (x_t - x_{\text{ref}})^T Q (x_t - x_{\text{ref}}) u_t^T R u_t \right) Jt0∑N−1((xt−xref)TQ(xt−xref)utTRut)
( x_{\text{ref}} )期望的轨迹目标点( Q )状态误差的权重鼓励轨迹跟踪( R )控制输入的权重防止过大加速度
约束条件 x t 1 A x t B u t x_{t1} A x_t B u_t xt1AxtBut u min ≤ u t ≤ u max u_{\min} \leq u_t \leq u_{\max} umin≤ut≤umax x min ≤ x t ≤ x max 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 A x 0 B U X \mathcal{A} x_0 \mathcal{B} U XAx0BU
其中 状态向量合并整个时间窗 X [ x 1 x 2 ⋮ x N ] , U [ u 0 u 1 ⋮ u N − 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 x1x2⋮xN ,U u0u1⋮uN−1 状态转移矩阵 A [ A A 2 ⋮ A N ] \mathcal{A} \begin{bmatrix} A \\ A^2 \\ \vdots \\ A^N \end{bmatrix} A AA2⋮AN 控制影响矩阵 B [ B 0 0 … 0 A B B 0 … 0 A 2 B A B B … 0 ⋮ ⋮ ⋮ ⋱ ⋮ A N − 1 B A N − 2 B A N − 3 B … 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−1B0BAB⋮AN−2B00B⋮AN−3B………⋱…000⋮B
最终预测模型 X A x 0 B U X \mathcal{A} x_0 \mathcal{B} U XAx0BU 2将目标函数转化为 QP 形式 J ( X − X ref ) T Q ( X − X ref ) U T R U 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 ( A x 0 B U − X ref ) T Q ( A x 0 B U − X ref ) U T R U 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(Ax0BU−Xref)TQ(Ax0BU−Xref)UTRU
展开并整理得 J U T ( B T Q B R ) U 2 U T B T Q ( A x 0 − X ref ) ( A x 0 − X ref ) T Q ( A x 0 − X ref ) 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}}) JUT(BTQBR)U2UTBTQ(Ax0−Xref)(Ax0−Xref)TQ(Ax0−Xref) 最终标准 QP 形式 min U 1 2 U T H U f T U \min_U \quad \frac{1}{2} U^T H U f^T U Umin21UTHUfTU
其中
Hessian 矩阵正定矩阵 H B T Q B R H \mathcal{B}^T Q \mathcal{B} R HBTQBR线性项 f B T Q ( A x 0 − X ref ) f \mathcal{B}^T Q (\mathcal{A} x_0 - X_{\text{ref}}) fBTQ(Ax0−Xref)
约束条件变为
控制输入约束 U min ≤ U ≤ U max U_{\min} \leq U \leq U_{\max} Umin≤U≤Umax状态约束 X min ≤ X ≤ X max X_{\min} \leq X \leq X_{\max} Xmin≤X≤Xmax 4. 使用 QP 求解器计算最优控制输入
1QP 求解方法
MPC 需要每个时间步求解 QP 问题求解方法包括
内点法Interior Point Method适用于大规模 QP 问题主动集法Active Set Method适用于小规模问题梯度投影法Projected Gradient Descent适用于约束优化
2求解步骤
构造 QP 矩阵 H , f H, f H,f设定约束条件调用 QP 求解器如 OSQP, quadprog, CVXPY获得最优控制输入 U ∗ U^* U∗执行第一个控制步 u 0 u_0 u0并进入下一时间步 5. 总结
MPC 通过求解 QP 问题获得最优控制输入每个时间步优化未来 (N) 步的轨迹。QP 通过二次优化目标线性约束求解最终转换为标准凸优化问题。QP 求解方法内点法、主动集法可高效求解控制问题在无人机轨迹规划、自主导航、自动驾驶等领域广泛应用。
MPC QP 是现代最优控制的核心技术之一也是强化学习、控制系统研究的重要基础。
