求解约束问题的自适应sqp过滤器算法-刘隽.pdf

《求解约束问题的自适应sqp过滤器算法-刘隽.pdf》由会员分享，可在线阅读，更多相关《求解约束问题的自适应sqp过滤器算法-刘隽.pdf（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、硕士学位论文求解约束问题的自适应SQP过滤器算法作 者： 刘隽指导教师： 肖伟教授南京理工大学2013年12月声 明本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均已在论文中作了明确的说明。研究生签名： 沙c炸乡月了日学位论文使用授权声明南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。

2、对于保密论文，按保密的有关规定和程序处理。研究生签名： 到堡 力年岁月日硕士论文 求解约束问题的自适应SQP过滤器算法摘 要SQP算法是求解非线性规划最有效的方法之一，在现实中也得到广泛应用。该方法总体上涉及四方面的处理：海森矩阵的正定性，QP子问题的相容性，初始点的可行性，以及马拉托斯效应。SQP算法与过滤器结合是一种常用的技术，有效的避免了选择罚因子的困难。本文对传统的SQP算法做了一些修改，利用带函数值信息的风来近似海森矩阵，给子问题增加容忍度已达到对QP子问题的修改，采用自适应技术，对过滤器接受准则进行修改。另外，本文还对QP子问题不可行的情况进行了处理，给出了修复阶段的详细过程。通过

3、这几个方面的处理获得的算法，不仅具有良好的收敛性，而且数据实验表明本文算法有效。关键词： SQP；非线性规划；过滤器； 自适应Abstract 硕士论文AbstractSQP algorithm is one of the most effective methods for nonlinear programmingand used widelyThe method generally involves four aspects in processingThey arethe positivity definiteness of the Hessian matrix，the compati

4、bility of QP sub-problem，the feasibility of the initial points，and Maratos effectsThe SQP algorithm is usuallycombined with filter to overcome the difficulty of selecting a suitable penalty factorInthis paper，we make some modifications on the traditional SQP algorithmFirst，weuse the information of t

5、he function value to approximate the Hessian matrixSecondin order to to modify QP sub-problems，we increase the tolerance of sub-problemThird，we revise the acceptance criteria of the filter by adapting techniqueIn addition，we process QP sub-problems，which is not feasible，and present the restoration p

6、rocessin detailThe result of the experiment data suggests that the new algorithm not onlyhas an efficient convergence，but also feasibleKeywords： SQP；Nonlinear Programming；Filter； AdaptiveII硕士论文 求解约束问题的自适应SQP过滤器算法目 录摘 要 IAbstractII1绪论111 SQP算法的研究背景111 SQP算法的产生112 SQP算法的研究现状12过滤器算法的研究现状121过滤器算法的基本思想12

7、。2信赖域过滤器技术123线性过滤器技术13本文的研究思想 2算法阐述21 SQP过滤器算法的基本思想22 QP子问题的修改221约束条件的近似-222海森矩阵的构造23过滤器的构造 231接受准则的修改232可行修复阶段24新算法l12778935566799241，27789埒坫M埔“均均盟丝m目录 硕士论文3收敛性证明264数据试验36IV铊她的结谢献丈考总致参1绪 论11 SQP算法的研究背景SQP算法h 2，3，43是求解中小规模约束优化问题的有效方法。该类算法都是求解一个二次规划得到搜索方向，作为目标函数的下降方向，当不满足可行性要求时，对该方向进行修正。该部分主要介绍SQP算法的

8、由来，SQP算法在执行过程中遇到的问题。以及SQP算法的分类和研究现状。下面分两部分来介绍：111 SQP算法的产生首先假设我们要解决的问题是：min他)(11)st ci(z)=0 i=1，2，m假设f：舻-跪与c：乎p_舻，并且均为二阶连续可微的。牛顿法是解决无约束非线性优化的最有效的方法，所以，如果将牛顿法应用在约束问题上，将有事半功倍的效果。于是在1963年，wilson嘲首次提出SQP方法，他用牛顿方法来求解KKT条件，得出可以通过一系列子问题来近似求解原问题，从而产生SQP算法。该算法产生之后，成为求解非线性规划的主要算法。当然各种算法都有自己的缺陷，SQP算法也不例外，为了克服这

9、些缺陷，产生了各种各样的SQP算法。通过对目标函数的二阶近似和对约束函数的一阶近似，得到下面子问题：mlnVm2)T，d+drBkd (12)stVq(z)Td+q(z)=0， i=1，2，一，m，其中鼠是拉格朗日函数海森矩阵的某种近似，Vf(z)表示，0)在处的梯度。Vci)表示q。)在z处的梯度。Bk的具体形式后文会详细讲述。每迭代一1绪论 硕士论文步就会产生一个这样的子问题。通过求解形如(12)的一系列子问题，来近似求出原问题的解，这就是一般SQP方法。随着SQP方法的发展，它逐渐成为求解约束非线性规划和大规模问题的最主要的方法。11。2 SQP算法的研究现状早期的SQP算法在等式约束，

10、不等约束都有应用，形成了等式SQP和不等式SQP两类算法，最初应用在等式约束上。但这类算法在实际执行过程中，会出现一些缺陷。主要体现在下面几个方面：首先，虽然收敛速度可以达到二次，但是都只是局部收敛。其次，拉格朗日函数的海森矩阵计算量大，并且可能出现不正定的情况。针对上述问题，1976年Han旧提出了用正定矩阵来近似拉格朗日函数的海森矩阵，同时他还提出了采用罚函数来评价步长的好坏，有效的克服了上面的两个问题。这给SQP算法带来了一次革新。罚函数的概念由此诞生。在hart的文章中采用了如下罚函数啡(z)：R”_R。啡(z)=，(z)+r氆(z)十，i=l其中吼(z)+=max0，吼(z)，原问题

11、的约束条件是吼(z)0，r是一个大于。的数。然而，通常情况下的罚函数是非光滑的。因此，寻找精确和可微的罚函数是研究罚函数法的主要目标。Fletcher提出了用增广拉格朗日函数做罚函数的方法。Powell在1977论证了Han的算法在求解某些问题时，会出现可行域为空的情况。所以，这种算法在某种意义下是不可行的。引发TSQP算法一个新话题的讨论，一类新SQP算法也随之诞生。即，可行SQP算法(FsQP)ISl o这类算法处理的主要问题是：虽然鼠已经是正定的，看似这个问题一定有解，但会出现子问题本身就不相容的情况，也就是约束条件总是有一部分不满足，导致问题无解。针对这个问题，Powell侧提出了一种

12、新的对子问题的修正方法，使得子问题必定可行，他的修2硕士论文 求解约束问题的自适应SQP过滤器算法改如下：min qk(d)=jdrBkd+Vf(x2)rd+；6(1一)2st Vq(z2)rd+如(z)=0 i=1川2，m7Vq(z)Td+ici(z2)s 0 i=m+1,2，一，mIIdlIAk，(13)其&中满足下面条件：毛=i兰篆：；三：。通过这种修改使得子问题在求解的过程中总是可行的。这种修改看上去是很严密的修改。t旦Burke和Han【101说明了这种修改并不是对所有问题都适合的，在某些特殊情况下是不适合的。还给出了具体的例子。他们提出了一种新的修改方法，在他们的算法之中，首先构造

13、了一个非空集合：D(x，盯，卢)：=(d9PI IIdllp，g(x)+g(z)drl(x)，h(x)+(z)d=r。(z)】l，再用这个集合里面的条件来构造下面子问题：q(x，H，盯，卢)：rainqk(d)=矿瞰d+vf(x)Tdsubject to Ai(z)rd+Ci(z。)=r2(矿)i=1川2，m7Ai0)Td+q(Xk)T1(z2)i=m+1，2，一，mlIdlI卢通过求这个问题可以确保所得的解是在D(x，盯，卢)中，即可行域不可能为空。保证子问题的可行性。这类SQP算法就是可行SQP算法。另外，Zhou【11。对这种方法进行了更新，他修改7D(x，or，卢)的给法。在他的算法中

14、：D(x，or，卢)=dR“：劬(z)+V鲫(。)Td皿o(z，盯)，JM，JIdlloo卢】，皿。和相关参数的具体形式在此不给出详细阐述。Yuan，Fletcher等也提出过修改子问题的方法。还有其他学者m，13，“，1瓦161对此类问题都有贡献。31绪论 硕士论文采用信赖域算法时，会遇到一些问题。当信赖域半径很小时，子问题有可能不可行，并且当问题非凸时，会出现鞍点，针对这些问题，有人提出通过多子问题来求解。该方法是通过求解两个或者两个以上的子问题，比如1998年，LALEE等人提出了如下两个子问题(1)minckTAkTvju丁AATu1 T?懈u其中磊和A是互补空间，从第一个子问题中求出

15、班，从第二个子问题中求出磊札。这种方法的问题(1)将约束条件作为目标来处理，求极小值，这样可以保证问题(2)的可行性。很好的解决了子问题不可行的缺陷。当然还有很多其他的多子问题方法，这里就不详述了。1978年马拉托斯【1刀发现，用上面提到的方法求解非线性问题时，当zk非常接近z+时，求出的步长会被拒绝。即，有可能出现目标函数不下降反而会上升的情况。人们称这种现象为马拉托斯效应。随着SQP算法不同问题的出现，该算法朝着解决两个问题的方向发展，这两个问题就是：子问题的可行性和马拉托斯效应。解决不同问题就产生了不同的算法演变。当然还会出现迭代点不可行的情况，针对这种情况，Panier和Tits【181提出了可行SQP方法。称之为FSQP算法，该算法的基本思想是从可行点出发，然后求解子问题，得到使11标函数下降的方向，再用线性搜索确定步长，进行迭代。基本思路如下：首先求解子问题：4