二次规划(QP)是一类数学优化问题,其目标是在满足线性等式和不等式约束的条件下,使二次目标函数最小化或最大化。它允许目标函数中出现变量的平方项以及两个变量的乘积项,从而推广了线性规划。其中最重要的区别在于凸二次规划与非凸二次规划:前者的局部最优解必然也是全局最优解;后者可能存在多个局部极小点,求解其全局最优解通常要困难得多。
数学表述
标准的最小化形式为
其中:
- 为决策变量向量;
- 描述二次项;
- 描述线性项;
- 和 确定不等式约束;
- 和 确定等式约束。
不等式 按分量理解。变量的上下界,如 ,也属于线性约束,可以显式纳入模型。
在目标函数中加入常数项不会改变其极小点。将目标函数取负,即可把最大化问题转化为最小化问题。
可行集是有限个线性半空间与超平面的交集,因此是一个多面体。它可能为空、有界或无界。可行集无界本身并不意味着目标函数无界。
凸性、存在性与唯一性
如果 为半正定矩阵,即
则目标函数是凸函数。由于线性约束定义的是凸集,所得问题属于凸优化。此时,每个局部极小点都是全局极小点,但极小点不一定唯一。
如果 是正定矩阵,则目标函数严格凸。在任何由线性约束定义的非空可行集上,它都有唯一的极小点。正定性还使得目标函数随 的增大而趋于正无穷,因此即使可行集无界,也能保证极小点的存在。
仅有半正定性并不能保证目标函数有下界。例如,将 视为 的二次目标函数时,它在 上无下界。
有时,只需考察目标函数沿可行方向的曲率。对于带等式约束的问题,可写成
其中 ,且 的列构成 的零空间的一组基。约化海森矩阵为
如果该矩阵半正定,那么即使 在整个环境空间上并非半正定,目标函数在满足等式约束的仿射空间上仍然是凸的。如果该矩阵正定,则目标函数在该仿射空间上严格凸。
当 同时具有正曲率方向和负曲率方向时,问题通常是非凸的。不过,线性约束仍可能排除负曲率方向,或对这些方向施加足够的限制,从而使目标函数具有有限的最小值。
最优性条件与对偶性
对于标准形式,为 引入乘子 ,为 引入无符号限制的乘子 。拉格朗日函数为
当一个约束以等式成立时,称其为活跃约束。互补松弛性要求每个非活跃不等式约束对应的乘子为零。
对于凸二次规划,任何满足这些条件的点都是全局最优解。反之,对于仅含线性约束的二次规划,只要最优值能够达到,就存在适当的乘子,即使不满足严格可行性也是如此。乘子不一定唯一,尤其是在存在冗余约束时。
对于非凸二次规划,这些一阶条件是局部最优解的必要条件,但不是充分条件。二阶条件则考察沿与活跃约束相容的方向的曲率。
拉格朗日对偶可提供目标值的界和最优性证书。当 正定时,令
对 最小化拉格朗日函数,可得对偶问题
对于奇异的半正定矩阵 ,对偶表达式还需要满足一个值域条件,并可用广义逆来表示。在数值计算中,通常通过求解线性方程组进行计算,而不是显式构造 。
示例
考虑
无约束极小点 不可行。目标函数衡量的是到该点的欧几里得距离的平方,因此,带约束问题的解就是该点在可行三角形上的正交投影。
解位于 上。代入 ,得到
求导得 ,因此
约束 是活跃的,而两个非负约束均不活跃。严格凸性保证了该解的唯一性。
求解方法
等式约束方法
当只有等式约束时,由平稳性和可行性条件可得分块方程组
如果 满行秩,且 在 的零空间上正定,则该方程组的系数矩阵非奇异。零空间法首先消去等式约束;值域法则消去部分变量或乘子。两类方法的相对效率取决于问题的维数和矩阵结构。
活跃集方法
活跃集方法维护一组暂按等式处理的不等式约束,称为工作集。它求解一个带等式约束的子问题,朝其解的方向移动,并在约束变为紧约束,或乘子符号表明应解除某个约束时,更新工作集。
这些方法通常适用于中小规模问题,以及需要反复求解的一系列密切相关的二次规划。先前的解和工作集可以提供有效的热启动。退化现象以及大量可能的工作集会使算法的表现变得复杂。
内点法
内点法通过障碍项或扰动后的原始—对偶最优性方程处理不等式。例如,对 使用对数障碍,可得
其中 随求解过程逐步减小。
原始—对偶方法通常在每次迭代中求解一个具有特定结构的线性方程组。这类方法广泛用于大型凸二次规划,尤其适合能够利用矩阵稀疏性的情形。在标准计算假设下,适当的内点法对凸二次规划具有多项式时间复杂度保证。
一阶方法与分裂方法
投影梯度法交替执行两个步骤:沿目标函数负梯度方向迈出一步,再投影到可行集上。当投影计算成本较低时,例如只有简单的箱形约束时,这类方法很有吸引力;但向一般多面体投影本身可能就需要求解一个二次规划。
算子分裂方法将问题分解为更简单的计算步骤。它们适用于大型稀疏问题和只需中等精度的应用,但性能取决于缩放、参数选择以及所要求的解的容差。
非凸问题的全局方法
一般的非凸二次规划是 NP 难的。全局求解器可能采用分支定界法、凸松弛、割平面,以及随可行域细分而逐步收紧的界。
局部非线性优化器可能找到有用的可行点,但仅有局部最优性并不能证明全局最优性。
应用
最小二乘与统计估计
带约束的最小二乘法问题
是一个二次规划,因为
这里的 为半正定矩阵。非负最小二乘、约束回归和许多平滑问题都具有这种形式。加入 惩罚项,如岭回归中的做法,相当于增加一个半正定二次项。
投资组合优化
在均值—方差投资组合优化中,投资组合风险表示为
其中 包含各项资产的权重, 是它们的协方差矩阵。在预算约束、目标预期收益和线性风险敞口限制下最小化风险,当 半正定时,就得到一个凸二次规划。
要求持仓数量为整数或限定所选资产数量的约束,通常需要引入整数变量,从而改变问题的类别。
控制与工程
模型预测控制反复对有限时域内的预测行为进行优化。当系统动力学为线性、跟踪误差与控制代价为二次形式,且状态和输入约束为线性时,每次优化都是一个二次规划。
在代价为二次形式且限制条件为线性时,工程设计、轨迹平滑、信号重建和资源分配也会产生二次规划问题。
机器学习
标准的软间隔支持向量机可以表示为凸二次规划。其对偶问题使用半正定核矩阵,并对对偶变量施加线性约束。
序列二次规划是一种求解一般非线性优化问题的方法,其中也会出现二次规划子问题。每次迭代都用二次函数对目标函数进行局部近似,并用线性函数近似约束。
相关问题类别
二次规划具有二次目标函数,但其约束是线性的。含有二次约束的问题则属于二次约束二次规划;其凸性不仅取决于目标函数,也取决于约束函数。
如果部分决策变量必须取整数,就得到混合整数二次规划,它将二次规划与整数规划结合起来。即使二次目标函数是凸的,也不能使这一离散问题成为凸优化问题。
线性规划是 的特例。凸二次规划也可以改写为锥优化问题,但直接采用二次规划形式可能更有利于高效保留问题中有用的结构。
历史发展
二次规划随着战后运筹学和数学规划的发展而兴起。哈里·马科维茨于 1952 年发表的投资组合选择研究,提供了一个影响深远的应用,其中采用二次形式衡量风险,并对投资组合施加线性约束。
20 世纪 50 年代,相关算法研究不断发展,其中包括菲利普·沃尔夫于 1959 年发表的二次规划方法。此后,活跃集方法、内点算法、稀疏线性代数和算子分裂方法的发展,扩大了能够高效求解的问题范围。
数值局限
实际性能不仅取决于变量和约束的数量,还取决于稀疏性、缩放、退化情况,以及算法内部所求解线性方程组的条件性。
较大的条件数会使计算所得的解对微小扰动敏感。在最小二乘形式中,显式构造 可能使条件性恶化;保留原始因子结构的方法可能更可靠。
近似线性相关的约束可能使乘子不稳定,即使原始问题的解相对稳定。求解器的容差也意味着,报告的可行性和最优性都是近似的:原始残差、平稳性残差和互补性残差都必须结合问题的尺度来解读。
估计得到的二次项矩阵若是不定矩阵,可能表明模型确实是非凸的,也可能是在构造本应为凸的模型时出现了数值误差。加入对角正则化项可以改善条件性或确保正定性,但这会改变目标函数,因此通常也会改变原来的优化问题。