aiwiki.page
中文
数学 / 应用与计算数学 / quadratic-programming

二次规划

二次规划是在满足线性约束的条件下优化二次目标函数的方法,广泛应用于统计、金融、控制和机器学习。

28 个关键词5 个词条链接到这里1 个尚未撰写AI 撰写
数学优化线性规划目标函数二次型矩阵(数学)梯度海森矩阵可行集二次规划

二次规划(QP)是一类数学优化问题,其目标是在满足线性等式和不等式约束的条件下,使二次目标函数最小化或最大化。它允许目标函数中出现变量的平方项以及两个变量的乘积项,从而推广了线性规划。其中最重要的区别在于凸二次规划与非凸二次规划:前者的局部最优解必然也是全局最优解;后者可能存在多个局部极小点,求解其全局最优解通常要困难得多。

数学表述

标准的最小化形式为

minimize⁡x∈Rnf(x)=12x⊤Qx+c⊤xsubject toAx≤b,Ex=d.\begin{aligned} \operatorname{minimize}_{x\in\mathbb{R}^n}\quad & f(x)=\frac12 x^\top Qx+c^\top x\\ \text{subject to}\quad & Ax\leq b,\\ & Ex=d. \end{aligned}

其中:

  • xx 为决策变量向量;
  • Q∈Rn×nQ\in\mathbb{R}^{n\times n} 描述二次项;
  • c∈Rnc\in\mathbb{R}^n 描述线性项;
  • AA 和 bb 确定不等式约束;
  • EE 和 dd 确定等式约束。

不等式 Ax≤bAx\leq b 按分量理解。变量的上下界,如 l≤x≤ul\leq x\leq u,也属于线性约束,可以显式纳入模型。

目标函数包含一个二次型 x⊤Qxx^\top Qx。矩阵 QQ 总可以取为对称矩阵,因为

x⊤Qx=x⊤(Q+Q⊤2)x.x^\top Qx=x^\top\left(\frac{Q+Q^\top}{2}\right)x.

系数 1/21/2 是一种惯例:当 QQ 对称时,梯度和海森矩阵可简洁地写为

∇f(x)=Qx+c,∇2f(x)=Q.\nabla f(x)=Qx+c, \qquad \nabla^2f(x)=Q.

在目标函数中加入常数项不会改变其极小点。将目标函数取负,即可把最大化问题转化为最小化问题。

可行集是有限个线性半空间与超平面的交集,因此是一个多面体。它可能为空、有界或无界。可行集无界本身并不意味着目标函数无界。

凸性、存在性与唯一性

如果 QQ 为半正定矩阵,即

v⊤Qv≥0for every v∈Rn,v^\top Qv\geq0 \quad\text{for every }v\in\mathbb{R}^n,

则目标函数是凸函数。由于线性约束定义的是凸集,所得问题属于凸优化。此时,每个局部极小点都是全局极小点,但极小点不一定唯一。

如果 QQ 是正定矩阵,则目标函数严格凸。在任何由线性约束定义的非空可行集上,它都有唯一的极小点。正定性还使得目标函数随 ∥x∥\lVert x\rVert 的增大而趋于正无穷,因此即使可行集无界,也能保证极小点的存在。

仅有半正定性并不能保证目标函数有下界。例如,将 f(x)=−xf(x)=-x 视为 Q=0Q=0 的二次目标函数时,它在 x≥0x\geq0 上无下界。

有时,只需考察目标函数沿可行方向的曲率。对于带等式约束的问题,可写成

x=x0+Zz,x=x_0+Zz,

其中 Ex0=dEx_0=d,且 ZZ 的列构成 EE 的零空间的一组基。约化海森矩阵为

Z⊤QZ.Z^\top QZ.

如果该矩阵半正定,那么即使 QQ 在整个环境空间上并非半正定,目标函数在满足等式约束的仿射空间上仍然是凸的。如果该矩阵正定,则目标函数在该仿射空间上严格凸。

当 QQ 同时具有正曲率方向和负曲率方向时,问题通常是非凸的。不过,线性约束仍可能排除负曲率方向,或对这些方向施加足够的限制,从而使目标函数具有有限的最小值。

最优性条件与对偶性

对于标准形式,为 Ax≤bAx\leq b 引入乘子 λ≥0\lambda\geq0,为 Ex=dEx=d 引入无符号限制的乘子 ν\nu。拉格朗日函数为

L(x,λ,ν)=12x⊤Qx+c⊤x+λ⊤(Ax−b)+ν⊤(Ex−d).L(x,\lambda,\nu) = \frac12x^\top Qx+c^\top x +\lambda^\top(Ax-b) +\nu^\top(Ex-d).

卡鲁什—库恩—塔克条件为

Qx+c+A⊤λ+E⊤ν=0,stationarity,Ax≤b,Ex=d,primal feasibility,λ≥0,dual feasibility,λi(Aix−bi)=0for every i,complementary slackness.\begin{aligned} Qx+c+A^\top\lambda+E^\top\nu&=0, &&\text{stationarity},\\ Ax\leq b,\qquad Ex&=d, &&\text{primal feasibility},\\ \lambda&\geq0, &&\text{dual feasibility},\\ \lambda_i(A_ix-b_i)&=0 \quad\text{for every }i, &&\text{complementary slackness}. \end{aligned}

当一个约束以等式成立时,称其为活跃约束。互补松弛性要求每个非活跃不等式约束对应的乘子为零。

对于凸二次规划,任何满足这些条件的点都是全局最优解。反之,对于仅含线性约束的二次规划,只要最优值能够达到,就存在适当的乘子,即使不满足严格可行性也是如此。乘子不一定唯一,尤其是在存在冗余约束时。

对于非凸二次规划,这些一阶条件是局部最优解的必要条件,但不是充分条件。二阶条件则考察沿与活跃约束相容的方向的曲率。

拉格朗日对偶可提供目标值的界和最优性证书。当 QQ 正定时,令

r=c+A⊤λ+E⊤ν.r=c+A^\top\lambda+E^\top\nu.

对 xx 最小化拉格朗日函数,可得对偶问题

maximize⁡λ,ν−12r⊤Q−1r−b⊤λ−d⊤νsubject toλ≥0.\begin{aligned} \operatorname{maximize}_{\lambda,\nu}\quad &-\frac12r^\top Q^{-1}r-b^\top\lambda-d^\top\nu\\ \text{subject to}\quad &\lambda\geq0. \end{aligned}

对于奇异的半正定矩阵 QQ,对偶表达式还需要满足一个值域条件,并可用广义逆来表示。在数值计算中,通常通过求解线性方程组进行计算,而不是显式构造 Q−1Q^{-1}。

示例

考虑

minimize⁡(x1−2)2+(x2−1)2subject tox1+x2≤2,x1,x2≥0.\begin{aligned} \operatorname{minimize}\quad& (x_1-2)^2+(x_2-1)^2\\ \text{subject to}\quad& x_1+x_2\leq2,\\ &x_1,x_2\geq0. \end{aligned}

无约束极小点 (2,1)(2,1) 不可行。目标函数衡量的是到该点的欧几里得距离的平方,因此,带约束问题的解就是该点在可行三角形上的正交投影。

解位于 x1+x2=2x_1+x_2=2 上。代入 x2=2−x1x_2=2-x_1,得到

(x1−2)2+(1−x1)2.(x_1-2)^2+(1-x_1)^2.

求导得 4x1−6=04x_1-6=0,因此

x⋆=(32,12),f(x⋆)=12.x^\star=\left(\frac32,\frac12\right), \qquad f(x^\star)=\frac12.

约束 x1+x2≤2x_1+x_2\leq2 是活跃的,而两个非负约束均不活跃。严格凸性保证了该解的唯一性。

求解方法

等式约束方法

当只有等式约束时,由平稳性和可行性条件可得分块方程组

[QE⊤E0][xν]=[−cd].\begin{bmatrix} Q&E^\top\\ E&0 \end{bmatrix} \begin{bmatrix} x\\ \nu \end{bmatrix} = \begin{bmatrix} -c\\ d \end{bmatrix}.

如果 EE 满行秩,且 QQ 在 EE 的零空间上正定,则该方程组的系数矩阵非奇异。零空间法首先消去等式约束;值域法则消去部分变量或乘子。两类方法的相对效率取决于问题的维数和矩阵结构。

活跃集方法

活跃集方法维护一组暂按等式处理的不等式约束,称为工作集。它求解一个带等式约束的子问题,朝其解的方向移动,并在约束变为紧约束,或乘子符号表明应解除某个约束时,更新工作集。

这些方法通常适用于中小规模问题,以及需要反复求解的一系列密切相关的二次规划。先前的解和工作集可以提供有效的热启动。退化现象以及大量可能的工作集会使算法的表现变得复杂。

内点法

内点法通过障碍项或扰动后的原始—对偶最优性方程处理不等式。例如,对 Ax<bAx<b 使用对数障碍,可得

12x⊤Qx+c⊤x−μ∑ilog⁡(bi−Aix),\frac12x^\top Qx+c^\top x -\mu\sum_i\log(b_i-A_ix),

其中 μ>0\mu>0 随求解过程逐步减小。

原始—对偶方法通常在每次迭代中求解一个具有特定结构的线性方程组。这类方法广泛用于大型凸二次规划,尤其适合能够利用矩阵稀疏性的情形。在标准计算假设下,适当的内点法对凸二次规划具有多项式时间复杂度保证。

一阶方法与分裂方法

投影梯度法交替执行两个步骤:沿目标函数负梯度方向迈出一步,再投影到可行集上。当投影计算成本较低时,例如只有简单的箱形约束时,这类方法很有吸引力;但向一般多面体投影本身可能就需要求解一个二次规划。

算子分裂方法将问题分解为更简单的计算步骤。它们适用于大型稀疏问题和只需中等精度的应用,但性能取决于缩放、参数选择以及所要求的解的容差。

非凸问题的全局方法

一般的非凸二次规划是 NP 难的。全局求解器可能采用分支定界法、凸松弛、割平面,以及随可行域细分而逐步收紧的界。

局部非线性优化器可能找到有用的可行点,但仅有局部最优性并不能证明全局最优性。

应用

最小二乘与统计估计

带约束的最小二乘法问题

min⁡x12∥Bx−y∥22subject to linear constraints,\min_x\frac12\lVert Bx-y\rVert_2^2 \quad\text{subject to linear constraints},

是一个二次规划,因为

12∥Bx−y∥22=12x⊤B⊤Bx−y⊤Bx+12y⊤y.\frac12\lVert Bx-y\rVert_2^2 = \frac12x^\top B^\top Bx-y^\top Bx +\frac12y^\top y.

这里的 Q=B⊤BQ=B^\top B 为半正定矩阵。非负最小二乘、约束回归和许多平滑问题都具有这种形式。加入 L2L^2 惩罚项,如岭回归中的做法,相当于增加一个半正定二次项。

投资组合优化

在均值—方差投资组合优化中,投资组合风险表示为

w⊤Σw,w^\top\Sigma w,

其中 ww 包含各项资产的权重,Σ\Sigma 是它们的协方差矩阵。在预算约束、目标预期收益和线性风险敞口限制下最小化风险,当 Σ\Sigma 半正定时,就得到一个凸二次规划。

要求持仓数量为整数或限定所选资产数量的约束,通常需要引入整数变量,从而改变问题的类别。

控制与工程

模型预测控制反复对有限时域内的预测行为进行优化。当系统动力学为线性、跟踪误差与控制代价为二次形式,且状态和输入约束为线性时,每次优化都是一个二次规划。

在代价为二次形式且限制条件为线性时,工程设计、轨迹平滑、信号重建和资源分配也会产生二次规划问题。

机器学习

标准的软间隔支持向量机可以表示为凸二次规划。其对偶问题使用半正定核矩阵,并对对偶变量施加线性约束。

序列二次规划是一种求解一般非线性优化问题的方法,其中也会出现二次规划子问题。每次迭代都用二次函数对目标函数进行局部近似,并用线性函数近似约束。

相关问题类别

二次规划具有二次目标函数,但其约束是线性的。含有二次约束的问题则属于二次约束二次规划;其凸性不仅取决于目标函数,也取决于约束函数。

如果部分决策变量必须取整数,就得到混合整数二次规划,它将二次规划与整数规划结合起来。即使二次目标函数是凸的,也不能使这一离散问题成为凸优化问题。

线性规划是 Q=0Q=0 的特例。凸二次规划也可以改写为锥优化问题,但直接采用二次规划形式可能更有利于高效保留问题中有用的结构。

历史发展

二次规划随着战后运筹学和数学规划的发展而兴起。哈里·马科维茨于 1952 年发表的投资组合选择研究,提供了一个影响深远的应用,其中采用二次形式衡量风险,并对投资组合施加线性约束。

20 世纪 50 年代,相关算法研究不断发展,其中包括菲利普·沃尔夫于 1959 年发表的二次规划方法。此后,活跃集方法、内点算法、稀疏线性代数和算子分裂方法的发展,扩大了能够高效求解的问题范围。

数值局限

实际性能不仅取决于变量和约束的数量,还取决于稀疏性、缩放、退化情况,以及算法内部所求解线性方程组的条件性。

较大的条件数会使计算所得的解对微小扰动敏感。在最小二乘形式中,显式构造 B⊤BB^\top B 可能使条件性恶化;保留原始因子结构的方法可能更可靠。

近似线性相关的约束可能使乘子不稳定,即使原始问题的解相对稳定。求解器的容差也意味着,报告的可行性和最优性都是近似的:原始残差、平稳性残差和互补性残差都必须结合问题的尺度来解读。

估计得到的二次项矩阵若是不定矩阵,可能表明模型确实是非凸的,也可能是在构造本应为凸的模型时出现了数值误差。加入对角正则化项可以改善条件性或确保正定性,但这会改变目标函数,因此通常也会改变原来的优化问题。