利用拟牛顿法的约束变尺度二次规划算法

简称SQP（Sequential Quadratic Programming），也称有约束问题的变尺度法或拉格朗日拟牛顿法。经过不断完善，序列二次规划法在保证整体收敛性的同时，保持局部超一次收敛性，比乘子法更为优越，已经成为公认的当今求解光滑非线性规划问题的优秀算法之一。其基本原理是将原问题转化为一系列二次规划子问题，求解子问题，得到本次迭代的搜索方向，沿搜索方向寻优，最终逼近问题的最优点。另外，算法利用拟牛顿法（变尺度法）近似构造海赛矩阵，以建立二次规划子问题，故又称约束变尺度法。

原问题的数学模型为：

对应的拉格朗日函数为：

L（x，λ）=f（x）+λ^Th（x） （9-2-2）

在x^k点作泰勒展开，取二次近似表达式：

式中 H^k——海赛矩阵，H^k=∇²L（x^k，λ^k）。

该矩阵一般使用拟牛顿法中的变尺度矩阵B^k来代替。令：

d^k=x^k+1-x^k （9-2-4）

拉格朗日函数的一阶导数为：

将式（9-2-5）、式（9-2-4）代入式（9-2-3），得：

将等式约束函数h（x）=0在x^k作泰勒展开，取线性近似式：

代入式（9-2-6），并略去常数项，则构成二次规划子问题：

求解上述二次规划子问题，得到的d^k就是搜索方向。沿搜索方向进行一维搜索，确定步长a_k，然后按：x^k+1=x^k+a_kd^k的格式进行迭代，最终得到原问题的最优解。(www.xing528.com)

对于具有不等式约束的非线性规划问题：

仍可用同样的推导方法，得到相应的二次规划子问题：

求解过程中，每次迭代时应对不等式约束进行判断，去掉无效的约束，保留有效的约束并纳入等式约束中。这样，基于不等式约束的子问题和只具有等式约束的子问题保持了一致。相应地，变尺度矩阵也应包含有效的不等式约束的信息。

序列二次规划法的迭代步骤如下：

1）给定初始值x⁰、λ⁰，B⁰=I（单位矩阵）。

2）计算原问题的函数值、梯度值，构造二次规划子问题。

3）求解二次规划子问题，确定新的乘子向量λ^k和搜索方向d^k。

4）沿d^k进行一维搜索，确定步长a_k，得到新的近似极小点：x^k+1=x^k+a_kd^k。

5）满足收敛精度：

则停止计算。否则转下步。

6）采用拟牛顿公式（如BFGS公式）对B^k进行修正，得到B^k+1，返回2）。