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

序列二次规划

序列二次规划通过反复求解带有线性化约束的二次模型,求解光滑约束优化问题。

22 个关键词1 个词条链接到这里5 个尚未撰写AI 撰写
数学优化二次规划牛顿法目标函数拉格朗日乘数卡鲁什–库恩–塔克…雅可比矩阵海森矩阵序列二次规…

**序列二次规划(SQP)**是数学优化中用于求解光滑约束问题的一类迭代方法。在每次迭代中,SQP 方法都会构造一个二次规划子问题:在线性近似约束下,最小化一个描述局部最优性的二次模型。子问题的解给出搜索方向以及约束乘子的估计值。SQP 将牛顿法在局部的快速收敛特性与处理等式、不等式约束的机制结合起来。

问题表述

标准的非线性规划问题具有如下形式:

min⁡x∈Rnf(x),subject tohi(x)=0,i=1,…,m,gj(x)≤0,j=1,…,p.\begin{aligned} \min_{x\in\mathbb{R}^n}\quad &f(x),\\ \text{subject to}\quad &h_i(x)=0,\qquad i=1,\ldots,m,\\ &g_j(x)\leq 0,\qquad j=1,\ldots,p. \end{aligned}

这里,ff 是目标函数,hih_i 和 gjg_j 分别定义等式约束和不等式约束。经典 SQP 理论通常假设这些函数在解的邻域内二阶连续可微。变量的上下界可以纳入不等式约束,不过实际实现中往往会单独处理。

相应的拉格朗日函数为

L(x,λ,μ)=f(x)+λTh(x)+μTg(x),L(x,\lambda,\mu) = f(x)+\lambda^{\mathsf T}h(x)+\mu^{\mathsf T}g(x),

其中,λ\lambda 和 μ\mu 是拉格朗日乘子;按照上述不等式的写法,有 μ≥0\mu\geq0。

在满足适当的约束品性条件时,局部解满足卡鲁什—库恩—塔克条件:

∇xL(x,λ,μ)=0,h(x)=0,g(x)≤0,μ≥0,μjgj(x)=0,j=1,…,p.\begin{aligned} \nabla_x L(x,\lambda,\mu)&=0,\\ h(x)&=0,\\ g(x)&\leq0,\\ \mu&\geq0,\\ \mu_jg_j(x)&=0,\qquad j=1,\ldots,p. \end{aligned}

最后一个条件是互补松弛条件:严格非活跃的不等式约束所对应的乘子为零。SQP 寻找满足这些条件、同时满足局部极小值所需的适当二阶条件的点。

二次子问题

在迭代点 xkx_k 处,基本的 SQP 子问题为

min⁡d∇f(xk)Td+12dTBkd,subject toh(xk)+Jh(xk)d=0,g(xk)+Jg(xk)d≤0.\begin{aligned} \min_d\quad& \nabla f(x_k)^{\mathsf T}d +\frac12 d^{\mathsf T}B_kd,\\ \text{subject to}\quad& h(x_k)+J_h(x_k)d=0,\\ &g(x_k)+J_g(x_k)d\leq0. \end{aligned}

矩阵 JhJ_h 和 JgJ_g 是约束的雅可比矩阵,每一行对应一个约束的梯度。对称矩阵 BkB_k 是拉格朗日函数的精确海森矩阵,

Bk=∇xx2L(xk,λk,μk),B_k=\nabla^2_{xx}L(x_k,\lambda_k,\mu_k),

或其近似。由于常数项 f(xk)f(x_k) 不影响使模型最小化的步,因此将其省略。

计算出方向 dkd_k 后,原变量通常按下式更新:

xk+1=xk+αkdk,0<αk≤1.x_{k+1}=x_k+\alpha_kd_k, \qquad 0<\alpha_k\leq1.

子问题的乘子为原非线性问题的乘子提供估计值。根据具体方法,可以直接采用这些估计值,也可以将其与之前的估计值相结合。

线性化约束近似刻画了可行集的局部几何结构。满足线性化约束的步未必满足原来的非线性约束。因此,SQP 通常并不保证每次迭代都保持可行性。

为何使用拉格朗日函数的海森矩阵

如果仅使用 ∇2f(xk)\nabla^2 f(x_k),就会忽略非线性约束带来的曲率。例如,考虑

min⁡x,yxsubject tox2+y2=1.\min_{x,y} x \quad\text{subject to}\quad x^2+y^2=1.

目标函数是线性的,其海森矩阵为零,但约束具有曲率。令

L(x,y,λ)=x+λ(x2+y2−1),L(x,y,\lambda)=x+\lambda(x^2+y^2-1),

则拉格朗日函数的海森矩阵为 2λI2\lambda I。在解 (−1,0)(-1,0) 处,由驻点条件可得 λ=12\lambda=\tfrac12。因此,尽管目标函数的海森矩阵为零,拉格朗日函数仍能提供非零的曲率信息。

与牛顿法的关系

对于仅含等式约束的情形,定义最优性方程

F(x,λ)=[∇xL(x,λ)h(x)]=0.F(x,\lambda)= \begin{bmatrix} \nabla_xL(x,\lambda)\\ h(x) \end{bmatrix} =0.

对该方程组应用牛顿法,得到

[∇xx2L(xk,λk)Jh(xk)TJh(xk)0][dkΔλk]=−[∇xL(xk,λk)h(xk)].\begin{bmatrix} \nabla^2_{xx}L(x_k,\lambda_k)&J_h(x_k)^{\mathsf T}\\ J_h(x_k)&0 \end{bmatrix} \begin{bmatrix} d_k\\ \Delta\lambda_k \end{bmatrix} = - \begin{bmatrix} \nabla_xL(x_k,\lambda_k)\\ h(x_k) \end{bmatrix}.

这也是等式约束二次子问题的驻点方程,其中子问题的乘子对应于 λk+Δλk\lambda_k+\Delta\lambda_k。因此,使用精确海森矩阵的 SQP 可以理解为将牛顿法应用于约束最优性条件。

对于不等式约束,这一解释还涉及识别哪些约束是活跃的。当 gj(x)=0g_j(x)=0 时,该不等式约束在相应可行点处是活跃的。一旦识别出正确的活跃集,局部问题往往就可以像等式约束问题一样处理。

上面的分块矩阵是一个鞍点矩阵,通常是不定的。可靠地求解这类方程组是数值线性代数中的一项重要任务,尤其是在约束近乎线性相关或尺度不佳时。

曲率近似与子问题求解器

精确海森矩阵 SQP

精确海森矩阵方法使用拉格朗日函数的二阶导数。这些导数可以通过解析方式给出,也可以通过自动微分获得。

海森矩阵不必在整个变量空间上正定。在满足正则性条件的约束极小点附近,相关的二阶条件关注的是沿可行方向的曲率;例如,在等式约束情形中,考察满足 Jhd=0J_h d=0 的向量 dd。不过,远离解时,不定二次模型可能难以最小化。实际实现中可以修改海森矩阵,或限制所取的步。

拟牛顿 SQP

拟牛顿法利用一阶导数的变化来近似拉格朗日函数的曲率。常见的选择是 BFGS 更新。

典型的曲率向量对使用

sk=xk+1−xks_k=x_{k+1}-x_k

以及在同一乘子估计值下计算的拉格朗日函数梯度之差,例如

yk=∇xL(xk+1,λk+1,μk+1)−∇xL(xk,λk+1,μk+1).y_k= \nabla_xL(x_{k+1},\lambda_{k+1},\mu_{k+1}) - \nabla_xL(x_k,\lambda_{k+1},\mu_{k+1}).

两项使用相同的乘子,有助于分离出关于原变量的曲率信息。当曲率条件 skTyk>0s_k^{\mathsf T}y_k>0 未能充分满足时,通常采用阻尼更新,以保持近似矩阵的正定性。

求解二次规划

二次子问题本身也是一个优化问题。活跃集方法维护一组被当作等式处理的约束,称为工作集,并在求解子问题的过程中调整它。这类方法可以利用相邻 SQP 子问题的活跃集往往相似这一特点。

其他实现则采用不同的二次规划算法。对于大型问题,利用稀疏矩阵结构并合理控制子问题的求解精度,可能比将每个子问题都求解到很高精度更加重要。

全局化策略

纯粹的类牛顿迭代主要是一种局部方法。全局化策略使算法能够从尚未接近解的初始点出发取得进展。这里的“全局化”并不意味着求得非凸问题的全局最优解。

价值函数与线搜索

线搜索可以通过检验一个综合目标函数值与约束违反程度的价值函数来选择步长。常见的例子是

Φρ(x)=f(x)+ρ(∥h(x)∥1+∥[g(x)]+∥1),\Phi_\rho(x) = f(x) + \rho\left( \|h(x)\|_1+\|[g(x)]_+\|_1 \right),

其中,[g(x)]+[g(x)]_+ 将负分量替换为零,ρ>0\rho>0 为罚参数。

在适当的假设下,若罚参数足够大,这就是一个局部精确罚函数:满足相应条件的约束局部解也是该罚函数的局部极小点。实际方法必须更新罚参数,同时避免对可行性改善的追求压倒目标函数的一切有效改进。

信赖域与过滤器

信赖域方法将步限制在局部模型被认为可靠的邻域内,例如

∥d∥≤Δk.\|d\|\leq\Delta_k.

信赖域半径根据预测改进与实际改进之间的一致程度进行调整。

过滤器方法则将目标函数值与约束违反程度作为两个独立的量来比较。它通过与先前接受的数值对进行比较来评判试探点,而不是仅依赖单一的加权价值函数值。为保证收敛,还需要额外的保障机制。

线性化不相容与可行性恢复

一个可行的非线性问题,在某个迭代点处可能产生不可行的线性化子问题。例如,在 x=0x=0 处对 x2−1=0x^2-1=0 进行线性化,会得到不可能成立的方程 −1=0-1=0。

可能的应对方式包括:

  • 在弹性子问题中引入带罚项的松弛变量;
  • 先计算一个法向步以减小约束违反程度,再计算一个切向步以改善目标函数值;
  • 进入专注于恢复可行性的恢复阶段。

一个相关的困难是 Maratos 效应:由于非线性约束违反量仍具有二阶量级,一个局部表现优良的步可能被价值函数检验拒绝。二阶校正步可以减小这种违反量,并有助于在解附近重新接受全步长。

收敛性

局部收敛性取决于正则性、曲率、导数精度以及步的接受机制。

一组典型的充分假设包括:

  • 目标函数和约束函数光滑;
  • 活跃约束的梯度线性无关;
  • 满足严格局部极小值的二阶充分条件;
  • 在标准局部分析中,活跃不等式约束满足严格互补性;
  • 二次子问题的求解足够精确;
  • 最终能够接受全步长。

使用精确的拉格朗日函数海森矩阵,并满足适当的额外光滑性条件时,SQP 可以二次收敛。使用合适的拟牛顿近似时,它可以超线性收敛。这些收敛速度是局部性质,并不是从任意初始点出发都能获得的保证;严格互补性也并非每一种变体或收敛定理都必需的条件。

对于带有保障机制的方法,全局收敛性结果通常是在给定假设下证明其收敛到驻点。对于非凸问题,仅有驻点条件并不能证明全局最优性。退化、约束不相容或迭代点无界等情况可能需要另行分析。

实际的终止判据通常会考察多种残差:驻点条件残差、等式约束违反量、不等式约束的正向违反量以及互补性残差。仅仅步长很小,并不足以说明优化问题已经求解完成。

发展与应用

SQP 于 20 世纪 60 至 70 年代从约束优化的牛顿型方法发展而来。R. B. Wilson 的早期工作确立了二次规划形式,随后 S.-P. Han、M. J. D. Powell 等人的研究发展了收敛理论、拟牛顿更新以及实用的全局化策略。

其应用包括工程设计、参数估计、轨迹优化和带约束的最优控制。在非线性模型预测控制中,前后相继的优化问题密切相关,因此先前的解和乘子估计值可以作为有用的初始值。

当光滑约束对解有显著影响,并且能够获得精确导数时,SQP 尤其有效。其性能取决于问题规模、约束结构、导数计算成本以及二次规划求解器的效率,而不是某个统一的规模阈值。

局限性及与相关方法的比较

SQP 经常面临以下困难:

  • **非凸性:**不同的初始点可能得到不同的局部解。
  • **约束退化:**活跃约束梯度线性相关,可能导致乘子估计不唯一,以及最优性方程组的矩阵奇异。
  • **导数误差:**含噪声或不准确的导数会降低曲率估计的质量,并妨碍快速局部收敛。
  • **尺度问题:**变量或约束的尺度差异过大,可能使步的选择和残差检验失真。
  • **子问题成本:**在大型模型中,反复求解二次规划可能占据主要计算开销。

与序列线性方法不同,SQP 显式纳入了二阶曲率信息。与无约束罚函数方法不同,它在子问题中直接表示线性化约束。因此,其主要的计算权衡在于:更丰富的局部模型能够带来快速的局部改进,但反复求解约束二次问题也会带来计算成本和数值困难。