一种结合NCP函数的滤子SQP算法的研究

中图分类号：O224单位代号：11903密级：学号：04720952硕士学位论文SHANGHAIUNIVERSITYMASTER’STHESIS题目一种结合NCP函数的滤子SQP算法的研究作者金中学科专业运筹学与控制论导师田蔚文完成日期二零零七年四月上海大学硕士学位论文-I-上海大学本论文经答辩委员会全体委员审查，确认符合上海大学硕士学位论文质量要求.答辩委员会签名：主任：委员：导师：答辩日期：上海大学硕士学位论文-II-原创性声明本人声明：所呈交的论文是本人在导师指导下进行的研究工作,除了文中特别加以标注和致谢的地方外,论文中不包含其他人已发表或撰写过的研究成果.参与同一工作的其他同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意.签名：日期：本论文使用授权说明本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容.（保密的论文解密后应遵守此规定）签名：导师签名：日期：上海大学硕士学位论文-III-图书分类号：O224单位代号：11903学号：04720952上海大学理学硕士学位论文一种结合NCP函数的滤子SQP算法的研究硕士生：金中导师：田蔚文专业：运筹学与控制论上海大学理学院二零零七年四月上海大学硕士学位论文-IV-ADissertationSubmittedToShanghaiUniversityfortheDegreeofMasterinScienceTheResearchofAFilterSQPMethodWithNCPFunctionM.D.Candidate：JinZhongSupervisor：TianWeiwenMajor：OperationsResearchandCyberneticsCollegeofSciences，ShanghaiUniversityApril，2007上海大学硕士学位论文-V-摘要约束非线性规划问题是最优化领域中重要的研究课题，许多实际问题都可以归结为约束非线性规划问题。自从二十世纪七十年代后期，序列二次规划(SQP)已成为解非线性最优化问题的一种最常见、最有效的方法。滤子SQP最初是由Fletcher在[1]中提出的，是与信赖域相结合的一种算法。传统的SQP方法不论是LSQP还是TSQP，都需要选择某一合适的罚函数作为价值函数。使用罚函数法会在选择罚参数时通常罚因子需要有界，这个界值很难确定。为了避免罚参数带来的困难，在[1]中，这种带滤子的TSQP不需要使用罚函数作为价值函数，而是考虑滤子能否接受，这样可以避免由于罚参数选择而带来的困难。本文第一章介绍了约束非线性规划的一些基本的原理和结论，包括基本迭代公式，最优性条件和收敛速度，以及滤子方法的产生和发展等方面的内容；第二章给出了算法中滤子的构造，介绍了非线性互补函数（NCP）的定义和性质，鉴于在K-K-T点处的非线性互补条件，我们对于每个迭代点可以构造出一个新的违反约束度，这样就得到了一种新的滤子，于是通过把NCP函数放入滤子中我们构造出了一种新的滤子SQP算法。该算法的特征是用到了多目标优化里控制的思想：一个迭代点被接受当且仅当该点是否被滤子接受。在二次子问题不可行时，该算法需要可行性恢复阶段（首次在[1]中被提出）。我们证明了在假设条件下，这种新的滤子SQP算法具有全局收敛性和超线性收敛性。第三章是关于此算法的数值分析，我们通过编程实验算例得出了比较满意的数值结果，显示该算法是解决约束非线性规划的一种有效算法。第四章为本文的结论与展望。编程我们用到的是上海大学硕士学位论文-VI-MATLAB软件，主要程序具体可见本文的附录。关键词：NCP函数滤子逐步二次规划全局收敛性上海大学硕士学位论文-VII-ABSTRACTTheconstrainednonlinearprogramming(NLP)problemisanimportantresearchtopicinnumericaloptimizationfields.Manypracticalproblemscanbereducedtobetheconstrainednonlinearoptimizationproblems.ThefilterSQPmethodwhichincorporatedwithtrustregiontechnicwasinitiallyproposedbyFletcherin[1].ThispaperintroducesaNCPfunctionintothefilterandconstructanewSQP-filteralgorithm.AmechanismforprovingglobalconvergenceinfilterSQPmethodwiththeNCPfunctionisdescribedforconstrainednonlinearoptimizationproblem.Suchmethodsarecharacterizedbytheiruseofthedominanceconceptofmulti-objectiveoptimization,insteadofapenaltyparameterwhoseadjustmentcanbeproblematic.Restorationphase(firstlyproposedin[1])isneededbythemethodinthispaper.Weprovethatthealgorithmhasglobalconvergenceandsuperlinearconvergenceratesundersomemildconditions.Numericaltestswhicharepresentedconfirmtherobustnessofthisapproach.Keywords:NCPfunction,filter,SQP,globalconvergence上海大学硕士学位论文-VIII-目录摘要......................................................................................................................VABSTRACT...........................................................................................................VII第一章介绍............................................................................................................11.1最优化方法中常用的数学基础知识..................................................................11.2约束非线性规划的概念和基本迭代格式.........................................................41.3最优性条件和收敛速度.........................................................................................71.4滤子方法的产生和发展.......................................................................................11第二章结合NCP函数的滤子SQP方法......................................................172.1算法中滤子的构造................................................................................................172.2NCP函数...................................................................................................................202.3结合NCP函数的滤子SQP算法.........................................................................222.4算法的全局收敛性和超线性收敛性分析.......................................................26第三章算法的数值分析结果.........................................................................35第四章结论与展望............................................................................................38附录............................................................................................................................39参考文献...................................................................................................................45作者在攻读硕士学位期间公开发表的论文..................................................49作者在攻读硕士学位期间所参与的项目......................................................50致谢...................................................................................................................51上海大学硕士学位论文-1-第一章介绍§1.1最优化方法中常用的数学基础知识这一节我们将介绍一些在最优化方法中经常被用到的数学基础知识。定义1.1.1映射.:nRR被称为nR上的半范数当且仅当它满足下面的条件1.0x,nxR；2.axax,aR,nxR；3.xyxy,,nxyR.另外,如果该映射还满足00xx,则称.为nR上的范数。令12(,,,)TnnxxxxR，一些常用的向量范数有max,()iixxl；111,()niixxl；122221(),()niixxl；这些都是pl范数的特例。一般的，对于1p，pl向量范数定义为11()nppipixx，对于矩阵范数可以有很多选择，因为矩阵集合mnR可以被看作是实值空间mnR，所以，矩阵范数与一般的向量范数并没有本质的不同。因此，我们定义矩阵A的范数A，当映射.满足下面的条件时上海大学硕士学位论文-2-1.0A如果0A，并且0O，其中O表示所有元素都为零的矩阵；2.cAcA，对于任意cR；3.ABAB.此外，令nnAR，我们还可以这样定义矩阵范数0maxxAxAx这里x是某一向量范数。定义1.1.2设1:nfRR，_nxR.若f在点_x处对于自变量x12(,,,)Tnxxx的各分量的偏导数_()ifx