一种具有全局收敛性的NCP函数滤子算法.pdf

上海大学硕士学位论文一种具有全局收敛性的NCP函数滤子算法姓名：夏正洲申请学位级别：硕士专业：运筹学与控制论指导教师：田蔚文20080401上海大学硕士学位论文摘 要约束非线性规划问题是最优化领域中重要的研究课题，许多实际问题都可以归结为约束非线性规划问题自从二十世纪七十年代后期，序列二次规划(SQP)已成为解非线性最优化问题的一种最常见、最有效的方法滤子SQP最初是由Fletcher在[19]中提出的，是与信赖域相结合的一种算法在[42]中Ulbrich介绍了一种利用乘子函数来构造滤子的一个分量的方法，从而不用二次矫正步的就克服Maratos效应，而且证明了这种方法具有局部超线性收敛性基于[42]中想法我们在本论文巾我们构造了增广的拉格朗日函数易(力来代替【19】中的以习，也同样达到不用二次矫正步就避免了Maratos效应，而且结合NCP函数来构造了滤子的另一个分量以力从而我们将【19】巾滤子的两个分量给替换得到新的算法这种算法具有全局收敛性本文在前言中介绍了课题的研究背景和研究现状以及本文在论文中所做的工作；第二章介绍了约束非线性规划的一些基本的原理和结论，包括基本迭代公式，最优性条件和收敛速度，以及滤予方法的产生和发展等方面的内容：第三章给出了算法中滤予的构造，介绍了非线性互补函数(NCP)的定义和性质，鉴于在K-K-T点处的非线性互补条件，我们对于每个迭代点可以构造出一个新的违反约束度，这样就得到了一种新的滤予，于是通过把NCP函数放入滤子中我们构造出了一种新的滤子SQP算法。

该算法的特征是用到了多目标优化里控制的思想：一个迭代点被接受当且仅当该点是否被滤子接受在二次子问题不可行时，该算法需要可行性恢复阶段(首次在[19]中被提出)我们证明了在假设条件下，这种新的滤子SQP算法具有全局收敛性和超线性收敛性第四章是关于此算法的数值分析，．V．上海大学硕士学位论文我们通过编程实验算例得出了比较满意的数值结果，显示该算法是解决约束非线性规划的一种有效算法，而且比原来算法更有效第五章为本文的结论与展望关键词： NCP函数 滤子 逐步二次规划全局收敛性上海大学硕士学位论文ABSTRACTThe constrained nonlinear programming(NLP)problem is an important research topic innumerical optimization fields．Many practical problems Can be reduced to be the constrainednonlinear optimization problems．The filter SQP method which incorporated with trust regiontechnic was initially proposed by FiScher in【1 9]．In【42]，Ulbfich introduce a method with multipliers function，avoided to suffer from Maratos，andproved that this algorithm has the Superlinear Local Convergence．On the basis of【42]，we conductaugmented Lagrangian function‘(力insteading of八力and p(x)with NCP function．Thisnew algorithm also avoids to suffer from Maratos And numerical tests which ale presented confirmthe robustness ofthis approach。

Finally we prove the new algorithm has global convergence，Fistly the history of this paper and the general aspect of the study are introduced．Secondly weintroduce some basic theorices and conclusions of NLP problems in Chaperl，including theiterative formulation，the optimization condition，the rate of convergence and the filter method．NextChaper 3 proposes the construction of filter in the algorithm，the definition and properties of aNonliner Complement Problem(NCP)function．Regarding to the NCP condition at a K—K-T point，wecould construct a new constraint violation in each iterative point get a new filter．Thus a new filterSQP method is constructed．Such methods are characterrized by their nse of the dominance conceptof the multi-objective optimization，instead of a penalty parameter whose adjustment Can beproblematic．Restoration phase(firstly proposed in【1 91)is needed by the method in this paper．Amechanism for proving global convergence in filter SQP method with the NCP function is describedfor constrained nonlinear optimization problem．We prove that the algorithm has global convergenceand superlinear convergence rates under some mild conditions．Further in Chaper 4,numerical testsare presented to confirm the robudtness and efficiency of this approach．Finally,the conclusion andencouraging filter study are provided in Chapter 5．Keywords：NCP function，filter,SQP,global convergence．VIl-原创性声明本人声明：所呈交的论文是本人在导师指导下进行的研究工作，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果．参与同一工作的其他同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意．签名：夏苫埘 日期： 。

咿莎．／加本论文使用授权说明本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容．(保密的论文解密后应遵守此规定)躲复陟叶新虢Ⅵ殷吼小l口上海大学硕士学位论文第一章前言§1．1研究背景与现状约束非线性规划问题是最优化领域中重要的研究课题，许多实际问题都可以归结为约束非线性规划问题它有很多实际的应用价值：在应用数学方面，可以应用到约束拟合和优化控制领域；在物理学方面，可以应用到光学和流体力学等方面：此外还可以应用到化学、工程学、计算机科学等学科由此可见它的重要性到了二十世纪其实年代后期，序列二次规划(SOP)已成为解非线性最优化问题的一种最常见、最有效的方法我们知道SOP方法具有类似牛顿法的快速收敛性但传统的SOP方法都存在价值函数如何选取的问题，而多数罚函数含有罚因子，[5][13][15][16][17][18][24][25][26][27][28][34][40]都是研究罚函数的罚因子的选取一直是SOP方法的一个难点，选的过大或过小都会对算法产生不良的影响Fletcher在文[19]中提出了一种新的思想克服了以上困难，即把滤子和信赖域SOP相结合，不需要选取罚因子。

一个重要的概念就是如果试探点能降低目标函数或约束违反度函数的值，那么该点就被算法接受，而不象价值函数那样将两者结合在1998年，针对滤子信赖域的SOP算法，Fletcher等人给出的运算结果令人鼓舞的紧随气候，Fletcher等人又给出相关算法的全局收敛性的证明1999年，Fletcher，Gould，Leffer和Toint在[21]对[10]算法进行了改进，给出两种算法路子SOP算法并证明了他们的全局收敛性在1999年R．Fletcher，S．Gould和P．L．Toint在[23]中提出了一种序列二次规划(SLP)算法并证明了其全局收敛性，该算法也避免了使用罚函数随后由S．Ulbrich在[42]对乜D]中的滤子的做了改进后克不用二次矫正步同样避免了Maratos效应，并证明了这种算法具有超线性局部收敛性§1．2本文的主要工作本文从最优化条件出发(即KTT条件)，构造非线性互补(NCP)函数，用一个等式来表示KKT条件中的互补性质，把这种方法应用到SOP滤子中去，具体做法是在滤子对中把NCP函数范数代替约束违反度函数，这样在迭代点逼近可行域的同时能使互补条件得到满足为了避免二次矫正步，我们做的另一个工作是在上海大学硕士学位论文滤子对中用增广的拉格朗日函数代替目标函数。

在此基础上给出一个新的NCP函数滤子算法，给出和证明了算法的收敛性和收敛速度并用数值例子说明算法的有效性第二章介绍§2．1最优化方法中常用的数学基础知识这一节我们将介绍一些在最优化方法中经常被用到的数学基础知识定义2．1．1 映射lI．|I：∥一月被称为∥上的半范数当且仅当它满足下面的条件1．1141->0，Vxe∥：2．8纠1．I叫0爿l，V#e刀，z∈∥；3．忙+川≤1141+INI，Vx,j,'e∥．另外，如果该映射还满足㈣=o§X--0，则称II．|l为∥上的范数令X----(玉，毛，…，而)，∈∥，一些常用的向量范数有1141maXH，(乞)；41∑M(‘)；卅I：：(兰#)％，(‘)；／=l这些都是名范数的特例一般的，对于1≤尸o如果彳≠0，并且0叫I=o，其中秒表示所有元素都为零的矩阵20刮I=l圳卅I，对于任意f∈月：0彳+纠l≤0硎+0卅I．此外，令彳∈∥”，我们还可以这样定义矩阵范数悱赠蝌这里恫I是某一向量范数定义2．1．2 设／：∥一詹， i∈∥．若／在点i处对于自变量X-----(而，吒，…，而)厂的各分量的偏导数掣(川，2，…，功ox，都存在，则称函数／在点i处一阶可导，并且称向量耽为：、Of3(x)．，掣，…，掣)厂 嘶 ％ ％是／在点i处一阶导数或梯度。

定义2．1．3 设／：∥一爿，i∈∥和血∈∥．记吠l|纠I)为If纠I的高阶无穷小如果存在口∈∥，使得／(A∽一／(为=∥血+训纠I)，则称函数／在点i处可微，并称搿国=0缸是在／在点i处的微分下面的定理给出了微分和梯度之间的关系定理2．】．1 设／：∥专詹，j∈∥．若／在点j处可微，则／在点i处的梯度vf(h存。