在数值优化领域，二次规划（Quadratic Programming，简称QP）是一类兼具理论深度与工程价值的优化问题。作为线性规划（LP）的自然延伸，它通过引入二次目标函数，能够更精准地刻画实际场景中存在的“非线性”与“凸性”特征，在机器人控制、金融投资、工程设计等诸多领域发挥着不可替代的作用。
一、二次规划的定义与数学模型
二次规划的本质，是在一组线性约束条件下，求解一个二次函数的极值问题。其核心特征在于目标函数的二次性与约束条件的线性性，这种结构既保留了线性规划的求解高效性，又能处理更复杂的优化场景——例如实际系统中普遍存在的“最小能量”“最小方差”等目标，这类目标往往天然呈现二次形式。
1.标准数学模型
QP问题的标准形式通常分为“凸二次规划”与“非凸二次规划”两类，其中凸QP因具有全局最优解且求解难度可控，应用最为广泛。其标准数学表达式如下：
目标函数（极小化）：minₓ f(x) = (1/2)xᵀHx + cᵀx
约束条件：
•线性等式约束：Ax = b
•线性不等式约束：Cx ≤ d
其中各参数的含义为：x ∈ ℝⁿ 是待优化的n维决策变量；H ∈ ℝⁿˣⁿ 是二次项系数矩阵，其正定性直接决定了QP问题的凸性——当H为正定矩阵时，目标函数是严格凸函数，结合凸集性质（线性约束下的可行域为凸集），此时QP问题存在唯一的全局最优解；当H为半正定矩阵时，目标函数是凸函数，最优解可能存在多个，但所有最优解构成凸集；当H为非正定矩阵时，问题为非凸QP，可能存在多个局部最优解，求解难度显著提升。c ∈ ℝⁿ 是线性项系数向量；A ∈ ℝᵐˣⁿ、C ∈ ℝᵖˣⁿ 分别为等式与不等式约束的系数矩阵；b ∈ ℝᵐ、d ∈ ℝᵖ 为约束的右侧常数向量。
2.核心特征：凸性与最优性条件
凸性是QP问题最关键的属性。对于凸QP，Karush-Kuhn-Tucker（KKT）条件是最优解的充要条件，这为算法设计提供了核心理论依据。KKT条件将“目标函数梯度与约束梯度平衡”“约束满足”“互补松弛”三大条件整合，具体形式如下（针对标准凸QP）：
1)原始可行性：Ax = b，Cx ≤ d；
2)对偶可行性：Hx + c + Aᵀλ + Cᵀμ = 0（λ为等式约束对偶变量，μ为不等式约束对偶变量）；
3)互补松弛：μᵀ(Cx - d) = 0（即活跃约束对应的对偶变量非零，非活跃约束对应的对偶变量为零）；
4)非负性：μ ≥ 0（仅针对极小化问题的不等式约束）。
KKT条件的本质是将带约束的优化问题转化为“原始变量+对偶变量”的方程组求解问题，绝大多数QP求解算法都是围绕KKT系统的高效求解展开的。
二、二次规划算法的分类
根据求解思路的差异，QP算法可分为“主动集法”“内点法”“梯度投影法”三大主流类别，各类算法在计算效率、收敛速度、内存占用等方面各有侧重，适用于不同规模与特性的问题。
1.主动集法：聚焦“约束活跃性”的经典方法
主动集法（Active Set Method）是最早用于求解QP问题的算法之一，其核心思想源于“将带约束优化转化为无约束优化”——通过识别可行域边界上的“活跃约束”（即等式约束与满足Cx=d的不等式约束），在每次迭代中仅考虑活跃约束构成的子问题，逐步逼近最优解。
算法的核心步骤可概括为：
1)初始化：确定初始可行点x₀，并识别其对应的活跃约束集A₀；
2)求解无约束子问题：在活跃约束集Aₖ下，将约束视为等式，求解无约束二次规划子问题，得到搜索方向pₖ；
3)线搜索：在搜索方向pₖ上，确定最大步长αₖ，使得新点xₖ₊₁ = xₖ + αₖpₖ仍满足所有约束；
4)更新活跃集：若步长αₖ为最大值（即新点触及某一非活跃约束），则将该约束加入活跃集；若子问题的解满足KKT条件，则退出，否则删除某一活跃约束；
5)迭代终止：当满足KKT条件的精度要求时，输出最优解。
主动集法的优势在于迭代次数少（尤其对于小规模问题）、收敛速度快，且解的精度较高；但缺点是对初始可行点要求严格（需先找到可行点），且当问题规模增大（n>1000）时，活跃集更新频繁，计算效率显著下降，因此更适用于中小规模的凸QP问题。
2.内点法：突破“活跃集依赖”的现代方法
内点法（Interior Point Method，IPM）是20世纪80年代兴起的QP求解技术，其核心创新在于“不依赖活跃集识别”，而是通过在不等式约束内构造“障碍函数”，将带约束问题转化为一系列无约束问题的逼近求解，始终在可行域内部迭代，最终收敛到最优解。
针对QP问题的内点法通常采用“障碍函数法+牛顿法”的组合思路，核心步骤为：
1)构造障碍问题：引入障碍参数t（t>0，逐渐趋近于0），将原QP问题转化为无约束问题minₓ f(x) - t·Σln(d - Cx)（障碍项确保x在可行域内）；
2)牛顿迭代求解：对障碍问题求梯度与Hessian矩阵，构建牛顿方程，求解搜索方向，通过线搜索确定步长，更新x；
3)调整障碍参数：当迭代满足当前t下的精度要求时，减小t（如t = t/10），重复步骤2；
4)终止条件：当t足够小且满足KKT条件精度时，输出最优解。
内点法的最大优势是“多项式时间复杂度”，对于大规模QP问题（n>10000）的求解效率远超主动集法，且对初始点要求宽松（无需严格可行），因此成为现代QP求解器（如Gurobi、CPLEX中的QP模块）的核心算法。其缺点是迭代次数相对较多，且在接近最优解时收敛速度可能放缓。
3.梯度投影法：适用于大规模稀疏问题的高效方法
梯度投影法（Gradient Projection Method）主要针对“决策变量维度极高但约束稀疏”的QP问题（如机器学习中的正则化问题、图像处理等），其核心思想是“先利用目标函数梯度确定搜索方向，再将搜索方向投影到可行域上，得到可行的迭代步长”，避免了直接求解大规模矩阵方程的高昂成本。
对于凸QP问题，梯度投影法的简化步骤为：
1)初始化：确定初始可行点x₀；
2)计算梯度：计算目标函数在xₖ处的梯度gₖ = Hxₖ + c；
3)梯度下降方向：取搜索方向dₖ = -gₖ（最速下降方向）；
4)投影操作：将dₖ投影到可行域上，得到可行搜索方向pₖ = P(xₖ + αdₖ) - xₖ（P为可行域投影算子）；
5)线搜索与更新：通过精确线搜索或不精确线搜索确定步长αₖ，更新xₖ₊₁ = xₖ + αₖpₖ；
6)终止：当投影梯度的范数足够小时，输出最优解。
梯度投影法的优势在于“投影操作可高效实现”（尤其对于简单约束如x≥0、||x||≤1等），内存占用低，适用于百万级维度的大规模问题；缺点是收敛速度为线性，相较于内点法的超线性收敛，在精度要求极高的场景下效率较低。
三、QP算法的求解关键
QP算法的实际求解效果，不仅依赖于算法框架的选择，还与“矩阵预处理”“数值稳定性”“约束处理”等工程细节密切相关，这些环节往往是区分求解器性能的核心。
1.核心瓶颈：H矩阵的特性与处理
H矩阵作为二次项系数矩阵，其“正定性”“稀疏性”“对称性”直接决定了求解难度：
•正定性处理：若H为非正定（非凸QP），牛顿法可能出现搜索方向非下降的问题，需通过“正则化”（如H = H + εI，ε为小正数）将其转化为半正定矩阵，再结合启发式策略寻找全局最优解；
•稀疏性利用：实际问题中H矩阵往往是稀疏的（如结构力学中的刚度矩阵），通过稀疏矩阵存储（如CSR、COO格式）和稀疏Cholesky分解、LU分解，可将计算复杂度从O(n³)降低到O(n)，这是大规模QP求解的关键；
•对称性利用：H矩阵通常是对称矩阵（实际问题中二次项系数对称），利用对称性可将存储量减半，且对称矩阵的分解算法（如Cholesky分解）比非对称矩阵更高效、稳定。
2.约束处理：可行性与冗余性剔除
约束条件的处理重点在于两点：一是“初始可行点的获取”（主动集法的核心难题），通常通过求解一个辅助线性规划问题（如min 0·x，s.t. Ax = b, Cx ≤ d）来得到初始可行点；二是“冗余约束的剔除”，即删除对可行域无影响的约束（如Cx ≤ d中某一约束始终满足），减少计算量。现代求解器通常集成了高效的约束预处理模块，通过线性代数工具（如QR分解）识别冗余约束。
3.数值稳定性：避免病态问题
当H矩阵或约束矩阵存在“病态性”（即条件数极大）时，数值计算过程中易出现精度丢失。为提升稳定性，通常采用“平衡预处理”（对变量和约束进行缩放，使矩阵元素量级一致）、“迭代 refinement”（对分解结果进行迭代修正）等技术，确保求解精度。
四、典型应用场景
QP算法的应用场景本质上是“需要最小化二次目标且受线性约束”的问题，这类场景在工程、金融、科学计算中极为普遍。
1.机器人与自动控制
在机器人控制中，QP是实现“平稳运动”与“约束满足”的核心工具。例如，机械臂的关节控制问题中，目标函数可设为“关节加速度的二次型”（最小化能量消耗或冲击），约束条件包括“关节角度范围”“关节速度上限”“避障约束”（线性化后），通过QP求解可得到最优的关节控制量。此外，无人机的轨迹跟踪、自动驾驶车辆的路径规划等问题，均通过QP实现动态约束下的最优决策。
2.资产组合优化
马克维茨（Markowitz）资产组合理论是QP在金融领域的经典应用。该理论中，投资组合的“收益方差”（风险）是资产权重的二次函数，目标是“在给定预期收益的约束下，最小化风险”，约束条件包括“资产权重之和为1”“单只资产权重非负（不允许卖空）”，这正是一个标准的凸QP问题。通过QP求解，可得到最优的资产配置比例，为投资决策提供量化依据。
3.工程设计
在结构工程中，梁、柱等构件的尺寸优化问题，目标函数可设为“结构重量的二次型”（或应力的二次型），约束条件包括“强度约束”“刚度约束”（线性化后），通过QP求解可在满足安全要求的前提下实现轻量化设计。在数据拟合领域，带约束的最小二乘问题（如参数范围约束）本质上也是QP问题，通过求解可得到更符合实际场景的拟合结果。
4.机器学习
在机器学习中，L2正则化（如 ridge regression）的目标函数是“损失函数+权重的L2范数（二次项）”，约束条件可包括权重的范围限制，属于QP问题；此外，支持向量机（SVM）的对偶问题也是一个凸QP问题，通过求解QP可得到最优的分类超平面，是SVM算法的核心求解环节。
五、总结
二次规划作为连接线性优化与非线性优化的桥梁，其核心价值在于“以可控的求解难度，处理复杂的二次目标问题”。主动集法、内点法、梯度投影法三大主流算法分别适用于中小规模、大规模、超大规模稀疏问题，构成了QP求解的完整技术体系。随着实际应用中问题规模的不断扩大（如百万级变量的机器学习问题、多机器人协同控制问题），QP算法的发展正朝着“稀疏化、并行化、智能化”方向推进——稀疏算法进一步提升计算效率，并行计算适应多核硬件架构，智能化策略（如结合深度学习预测初始点）则加速收敛。
对于工程实践者而言，理解QP的数学本质与算法特性，结合具体问题的规模、约束类型、精度要求选择合适的求解器（如小规模用Matlab的quadprog，大规模用Gurobi、OSQP），是实现高效优化的关键。
