序列二次规划法.pdf

《序列二次规划法.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、序列二次规划算法1序列二次规划法简介非线性规划问题是目标函数或约束条件中包含非线性函数的规划问题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不像线性规划有单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。当目标函数和约束条件具有良好的分析性质时，人们喜欢用间接法分析与求解约束最优化问题。利用间接法求解最优化问题的途径一般有两种，另一种途径是在可行域内使目标函数下降的迭代点法，如可行点法。另一种是利用目标函数和约束条件构造增广目标函数，借此将约束最优化问题转化为无约束最优化问题，然后利用求解无约束最优

2、化问题的方法间接求解新目标函数的局部最优解或稳定点，如人们所熟悉的惩罚函数法，乘子法和序列二次规划等。序列二次规划算法是目前公认的求解约束非线性优化问题的最有效方法之一，与其它优化算法相比，其最突出的优点是收敛性好、计算效率高、边界搜索能力强，受到了广泛重视及应用。但其迭代过程中的每一步都需要求解一个或多个二次规划子问题。一般地，由于二次规划子问题的求解难以利用原问题的稀疏性、对称性等良好特性，随着问题规模的扩大，其计算工作量和所需存贮量是非常大的。因此，目前的序列二次规划方法一般只适用于中小型问题。另外，由于大型二次规划问题的求解通常使用迭代法，所需解的精度越

3、高，花费的时间就越多，稳定性也就越差，相对线性方程组的求解理论来说，二次规划的求解是不完善的。2序列二次规划的研究最优化理论及方法是一个具有广泛应用背景的研究领域。它研究诸如从众多的方案中选出最优方案等问题，常见的各种模型如线性规划，二次规划，非线性规划，多目标规划等。最优化理论及方法已经在经济计划，工程设计，生产管理，交通运输等领域得到了广泛的应用，吸引了很多学者的研究。一般非线性约束的数学规划问题是：min()fXstgX..()0(u1,2,...,)pu()hX0(v1,2,...,)mvn其中XR是决策变量，fX()是目标函数，gX()，hX

4、()分别是不等uv式约束函数和等式约束函数。在求解上述问题的诸多算法中序列二次规划(SQP)是最有效的一类方法之一"由于它具有超线性收敛速度,对它的研究一直是非线性规划的一个热点,许多学者对它进行了研究和改进"序列二次规划（SQP）算法最早由Wilson（1963）提出。Wilson提出了Newton-SQP方法。60年代末和70年代初，随着解无约束优化问题的拟Newton法的发展，拟Newton-SQP算法的研究引起了学者们的高度重视。Polomares-Mangasarian（1976）提出了一类拟Newton-SQP方法。在该类方法中，他采用对Lagran

5、ge函数的整体Hesse矩阵（即既对x又对Lagrange乘子的Hesse矩阵）的近似进行修正的方法来修正。Han（1976，1977）证明了PSB-SQP和BFGS-SQP方法的局部收敛性。而且，若采用精确罚函数进行搜索，则算法具有全局收敛性。自此，SQP算法的研究受到了广泛的重视。迄今为止，SQP算法的研究工作已取得了丰硕的成果。SQP算法的主要优点之一是它的全局收敛性和局部超线性收敛性。为使算法具有全局收敛性，通常要求子问题（QP）中的矩阵H对称正定。使得（QP）产生的方向S是某个效益函数的下降方向。另一方面，若矩阵H对称正定，则子问题（QP）是一个严格凸

6、二次规划。此时，该问题有唯一解。而且，其求解也相对容易。因此，研究矩阵H的对称正定性是一项非常重要的工作。并己引起了学者们的重视。Powell（1976）提出了一个修正的BFGS公式。该公式可保证产生的矩阵是对称正定的。数值计算的结果表明利用该修正公式的SQP算法的数值效果较好。然而该算法的局部收敛性质尚不清楚。Coleman和Conn（1984）提出了一种既约Hessian-SQP方法。即用一系列的正定矩阵去逼近解[*,*]S处的既约Hessian矩阵。Noeedal和Overton（1985）提出了单边及双边的投影Hessian方法。在单边投影Hessia

7、n方法中证明了局部1-步超线性收敛性而在双边投影Hessian方法中证明了在某种假设条件下的2-步超线性收敛性质。但他的BFGS修正公式是在满足一定的修正准则才进行修正。Xie和Byrd（1999）在RHSQP方法的基础上加上线性搜索得到全局收敛性算法。他并且把Nocedal和Overton的修正法则改为了一种新的修正法则一正曲率法则。这样能得到更好的数值结果。并且证明了当利用两个常用的效益函数，Flether效益函数和l精确罚函数进行线性搜索时，算法具有全局收敛性和R-线性收敛性。1R.Fontecilla（1988）提出了一种2-步超线性收敛算法。与Cole

8、man和Conn不同之处