关于序列二次规划（SQP）算法求解非线性规划问题研究兰州大学硕士学位论文关于序列二次规划（SQP）算法求解非线性规划问题的研究姓名：石国春申请学位级别：硕士专业：数学、运筹学与控制论指导教师：王海明20090602兰州大学2009届硕士学位论文摘要非线性约束优化问题是最一般形式的非线性规划NLP问题，近年来，人们通过对它的研究，提出了解决此类问题的许多方法，如罚函数法，可行方向法，Quadratic及序列二次规划SequentialProgramming简写为SOP方法。

本文主要研究用序列二次规划SOP算法求解不等式约束的非线性规划问题。

SOP算法求解非线性约束优化问题主要通过求解一系列二次规划子问题来实现。

本文基于对大规模约束优化问题的讨论，研究了积极约束集上的SOP 算法。

我们在约束优化问题的s一积极约束集上构造一个二次规划子问题，通过对该二次规划子问题求解，获得一个搜索方向。

利用一般的价值罚函数进行线搜索，得到改进的迭代点。

本文证明了这个算法在一定的条件下是全局收敛的。

关键字：非线性规划，序列二次规划，积极约束集Hl兰州人学2009届硕二t学位论文AbstractNonlinearconstrainedarethemostinoptimizationproblemsgenericsubjectsmathematicalnewmethodsareachievedtosolveprogramming．Recently,Manyasdirectionit，suchfunction，feasiblemethod，sequentialquadraticpenaltyprogramming??forconstrainedInthisthemethodspaper,westudysolvinginequalityabyprogrammingalgorithm．optimizationproblemssequentialquadraticmethodaofSQPgeneratesquadraticprogrammingQPsequencemotivationforthisworkisfromtheofsubproblems．OuroriginatedapplicationsinanactivesetSQPandSQPsolvinglarge-scaleproblems．wepresentstudyforconstrainedestablishontheQPalgorithminequalityoptimization．wesubproblemsactivesetofthesearchdirectionisachievedQPoriginalproblem．AbysolvingandExactfunctionsaslinesearchfunctionsubproblems．wepresentgeneralpenaltyunderobtainabetteriterate．theofourisestablishedglobalconvergencealgorithmsuitableconditions．Keywords：nonlinearprogramming，sequentialquadraticprogrammingalgorithm，activesetlv兰州大学2009届硕士学位论文原创性声明本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立进行研究所取得的成果。

学位论文中引用他人已经发表或未发表的成果、数据、观点等，均己明确注明出处。

除文中已经注明引用的内容外，不包含任何其它个人或集体己经发表或撰写过的科研成果。

对本文的研究成果做出重要贡献的个人和集休，均已在文中以明确方式标明。

本声明的法律责任由本人承担。

oo穸．i，歹论文作者签名：丕!鱼盔日期．2授权声明本人在导师指导下所完成的论文及相关的职务作品，知识产权归属兰州大学。

本人完全了解兰州大学有关保存、使用学位论文的规定，同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版，允许论文被查阅或借阅：本人授权兰州大学可以将本学位论文的全部或部分内容输入有关数据库进行检索，可以采用任何复制手段保存和汇编本学位论文。

本人离校后发表、使用学位论文或与该论文直接相关的学术论文或成果时，第一署名单位仍然为兰州大学。

保密论文在解密后应遵守此规定。

论文作者签名：碰导师签名：硇兰i日期：三竺12：互：fⅡ兰州大学2009届硕’：学位论文第一章绪论非线性规划是计算数学和运筹学交叉的学科，由于非线性规划含有深刻的背景和丰富的内容，已经发展成为运筹学的重要分支，无论是在生产系统管理、工程技术，还是在社会科学中都得到极为广泛的应用。

非线性规划的研究始于1939年，是由w．卡鲁什首次进行的，40年代后期进入系统研究，1951年H．w．库恩和A．W．塔克尔提出最优化的判别条件，从而奠定了非线性规划的理论基础。

近几十年来，许多科学家都投身于最优化的研究，使得其在理论研究和实用算法方面都有很大的发展。

本章我们将大概地回顾一下非线性规划的研究发展过程，在此基础上重点回顾和介绍序列二次规划算法的发展与研究现状。

1．1非线性规划的发展过程求解NLP问题的算法，按照发展的时间顺序和不同的设计思路，可以大致分为以下四类。

l、直接法。

其主要思路是：用求解无约束优化问题的各种直接方法推广到求解一般的非线性约束优化问题。

这类方法对原问题不需要作任何的预处理，在按照某种方式选定了一组测试点之后，所需的仅是计算目标和约束的函数值。

因此，这类方法一般都计算简单、直观性强。

其缺点是计算量大、算法无好的理论依据，往往只能找到问题的一个较好的可行解，即使在特殊情况下能保证算法的收敛性，其收敛速度也只能是线性的。

所以，只要不是没有其它的算法可利用，一般不用这类方法。

2、线性约束问题的算法在非线性约束问题上的推广。

如可行方向法、广义简约梯度法和投影梯度法等。

其主要思路是：用线性约束问题的算法进行处理。

因此，这类方法所产生的迭代点均是问题的可行点。

但是，由于约束函数的非线性性，这些方法的具体实现要比在线性约束上复杂的多，且有效性也没那么好。

这类方法的主要优点是它保持迭代点列的可行性并通常可找到问题的局部最优解，其缺点是有关算法的实现往往很复杂、计算量比较大，且收敛速度通常只能兰州大学2009届硕l：学位论文达到线性收敛。

3、罚函数法。

其主要思路是：把非线性约束优化问题转化为无约束优化问题。

由于早期方法均需要求解一系列无约束的罚函数极小化问题，故通常称之为UnconstrainedMinimization序列无约束极小化方法SequentialTechnique，简称SUMT。

依据方法能否保证迭代点列的可行性，可将这些方法分为三类：内点罚函数法、外点罚函数法以及两者相结合的混合罚函数法。

SUMT类方法的优点是简单易行，可直接利用无约束优化的算法来求解约束优化问题。

在很弱的条件下即可保证算法的收敛性。

缺点是这些方法要求解一系列的无约束优化问题，计算量大且收敛速度慢，后来，人们又提出另外两种类型的罚函数：精确罚函数和乘子罚函数。

精确罚函数是在原目标函数上加一些由约束函数组成的惩罚项而构成，其优点是它的无约束极小点就是原问题的最优解。

而乘子罚函数是在约束问题的拉格朗R函数中增加了一个惩罚项。

这两种方法一直是求解约束问题NLP的主要方法。

4、序列二次规划SQP法。

其主要思路是：利用原来非线性约束优化问题的有关信息来构造某一简单的近似优化问题，通过求解它来给出对当前迭代点的修正，主要用一系列的线性规划或二次规划来逐次逼近原非线性规划问题。

尽管开始时的SOP方法存在着QP子问题可能不可行及马洛托斯Maratos效应等不足，但经过人们对其不断进行改进与进一步的发展，现在，SQP类方法已成为求解非线性约束优化问题的一类非常有效的算法。

它不仅可以求解等式约束优化问题，而且很容易处理不等式约束优化问题。

这类算法不仅具有全局收敛性，而且具有超线性收敛的速度。

1．2序列二次规划SQP的发展与研究现状Newton―Lagrange方法，当时就认为该算法是处理非线性约束优化问题很有效的一种方法。

SOP算法的一般形式为：对于非线性约束优化问题NLPrainfx1．12兰州大学2009届硕上学位论文s．t．c,x--o1．2iEE--1,2，…，他qOzO1．3iEIm，+卜??，m设t是当前问题NLP的迭代点，通过求解二次规划子问题minw瓴rd+昙dr也d1．4SI．iEE1．5cfxk+Vq瓴rd0iEl1．6．q瓴+％亿，d≥0得到一个搜索方向畋，然后经过线搜索求得步长吒，于是下一个迭代点％+，气+吼畋。

这就是SOP算法的一般方法。

早期的SOP算法基本上都是针对带有等式约束的非线性优化问题[15][16]。

量，在文章中他利用厶精确罚函数进行线搜索，在一定的条件下建立了算法的收敛性。

然而在1977年Powell却提出Han构造的二次规划子问题有可能造成可行域为空集，即使原问题的可行域是非空的，而子问题的可行域未必非空。

这时Powell建议在每次迭代时，求解如下修正的二次规划子问题min1．7Vfxkrd+三dr日。

d+丢哦1-g2sj．iEE1．8‖q瓴+Vci五rd--0iEl1．9以q瓴+Vc,瓴rd苫01，瓯。

是罚参数。

这个修正看起来天衣其中肛一：：，三丧；三三，且。

s‖s无缝，然而，Burke和Han1989却通过一个特殊例子说明这个方法并不完美。

Burke和Han的例子：clO--1一矿0c20一工0任意目标函数厂O，在任一不可行点z一0处，子问题都是不可行的。

虽然这个例子很特殊，但至少说明子问题的不可行性不是都能够通过1．8一1．9解决。

3兰州大学2009届硕上学位论文在约束优化中当非光滑的罚函数作为价值函数进行线搜索时，有可能会破坏算法的超线性收敛，即当迭代点趋近最优解时，得不到单位步长。

因此，以后关于SQP算法的研究主要是围绕克服子问题不可行和Maratos 效应这两方面的困难进行的。

在[19][20]中都提出了对于只有不等式约束的非线性规划问题防止子问题不可行的方法，在[20]中，Liu和Yuan提出了通过求解两个子问题来处理不可行的问题，其中两个子问题分别是分段二次子问题和二次子问题。

后来，Zhou在[21]中又给出了改进的SQP算法，他的方法是求解一个有界约束的线性规划问题和一个二次规划问题，总之，这些方法都是通过求若干个子问题来实现。

改了接受试探步的条件。

在一些迭代中利用Lagrange函数Lx，A，0一罗桃O1．10筒作为价值函数，从而放宽选取步长为1的条件，由于Watchdog技术在总体上还是利用厶罚函数判别点的好坏，所以它的总体收敛性仍可保证，因为他在一代点放宽了线搜索条件，所以，在一定条件下可证明它是超线性收敛的。