5A文关于序列二次规划SQP算法求解非线性规划问题研究.docx
《5A文关于序列二次规划SQP算法求解非线性规划问题研究.docx》由会员分享，可在线阅读，更多相关《5A文关于序列二次规划SQP算法求解非线性规划问题研究.docx（36页珍藏版）》请在冰点文库上搜索。
5A文关于序列二次规划SQP算法求解非线性规划问题研究
关于序列二次规划（SQP）算法求解非线性规划问题研究
兰州大学
硕士学位论文
关于序列二次规划（SQP）算法求解非线性规划问题的研究
姓名：
石国春
申请学位级别：
硕士
专业：
数学、运筹学与控制论
指导教师：
王海明
20090602
兰州大学2009届硕士学位论文
摘要
非线性约束优化问题是最一般形式的非线性规划NLP问题，近年来，人
们通过对它的研究，提出了解决此类问题的许多方法，如罚函数法，可行方向法，
Quadratic
及序列二次规划SequentialProgramming简写为SOP方法。
本文主要研究用序列二次规划SOP算法求解不等式约束的非线性规划问
题。
SOP算法求解非线性约束优化问题主要通过求解一系列二次规划子问题来实
现。
本文基于对大规模约束优化问题的讨论，研究了积极约束集上的SOP算法。
我们在约束优化问题的s一积极约束集上构造一个二次规划子问题，通过对该二
次规划子问题求解，获得一个搜索方向。
利用一般的价值罚函数进行线搜索，得
到改进的迭代点。
本文证明了这个算法在一定的条件下是全局收敛的。
关键字：
非线性规划，序列二次规划，积极约束集
Hl
兰州人学2009届硕二t学位论文
Abstract
Nonlinearconstrainedarethemostin
optimizationproblemsgenericsubjects
mathematicalnewmethodsareachievedtosolve
programming．Recently,Many
asdirection
it，suchfunction，feasiblemethod，sequentialquadratic
penalty
programming?
?
forconstrained
Inthisthemethods
paper,westudysolvinginequality
a
byprogrammingalgorithm．
optimizationproblemssequentialquadratic
methodaof
SQPgeneratesquadraticprogrammingQP
sequence
motivationforthisworkisfromtheof
subproblems．Ouroriginatedapplications
inanactiveset
SQPandSQP
solvinglarge-scaleproblems．wepresentstudy
forconstrainedestablishonthe
QP
algorithminequalityoptimization．wesubproblems
activesetofthesearchdirectionisachievedQP
originalproblem．Abysolving
and
Exactfunctionsaslinesearchfunction
subproblems．wepresentgeneralpenalty
under
obtainabetteriterate．theofourisestablished
globalconvergencealgorithm
suitableconditions．
Keywords：
nonlinearprogramming，sequentialquadraticprogrammingalgorithm，
activeset
lv
兰州大学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．1
2
兰州大学2009届硕上学位论文
s．t．c,x--o1．2
iEE--1,2，…，他
qOzO1．3
iEIm，+卜?
?
，m
设t是当前问题NLP的迭代点，通过求解二次规划子问题
minw瓴rd+昙dr也d1．4
SI．iEE1．5
cfxk+Vq瓴rd0
iEl1．6
．q瓴+％亿，d≥0
得到一个搜索方向畋，然后经过线搜索求得步长吒，于是下一个迭代点
％+，气+吼畋。
这就是SOP算法的一般方法。
早期的SOP算法基本上都是针对带有等式约束的非线性优化问题[15][16]。
量，在文章中他利用厶精确罚函数进行线搜索，在一定的条件下建立了算法的收
敛性。
然而在1977年Powell却提出Han构造的二次规划子问题有可能造成可行
域为空集，即使原问题的可行域是非空的，而子问题的可行域未必非空。
这时
Powel
l建议在每次迭代时，求解如下修正的二次规划子问题
min1．7
Vfxkrd+三dr日。
d+丢哦1-g2
sj．iEE1．8
‖q瓴+Vci五rd--0
iEl1．9
以q瓴+Vc,瓴rd苫0
1，瓯。
是罚参数。
这个修正看起来天衣
其中肛一：
：
，三丧；三三，且。
s‖s
无缝，然而，Burke和Han1989却通过一个特殊例子说明这个方法并不完美。
Burke和Han的例子：
clO--1一矿0
c20一工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技术在总体上还
是利用厶罚函数判别点的好坏，所以它的总体收敛性仍可保证，因为他在一些迭
代点放宽了线搜索条件，所以，在一定条件下可证明它是超线性收敛的。
在1986年，Powell和Yuan提出了修改了接受试探步条件的另一方法。
用
Fletcher光滑精确罚函数作为价值函数，考虑了等式约束问题，克服了Maratos
效应。
早期SQP算法中所选取的初始点、迭代点基本都是不可行的。
但随着实际的
需要，要求迭代点具有一定的可行性，即必须满足全部或部分的约束。
于是产生
中对FSQP算法作了进一步的研究，通过求解两个二次规划子问题产生可行下降
方向，然后再解一个最dx-乘问题来校正方向，以防止Maratos效应。
在一定的
条件下，FSQP算法具有全局收敛性和局部二阶超线性收敛。
然而，FSQP算法却
有个缺点，就是不易直接处理带有等式约束的优化问题，并且迭代运算相对困难，
更重要的是需要严格互补性条件才能保证算法的超线性收敛。
4
兰州大学2009届硕t学位论文
相比，计算任务减轻了，但严格互补性条件仍然需要。
尽管还有许多工作者在没
又不属于可行算法，因为不能保证迭代点一定在可行域中，并且对应的目标函数
值也是不单调的。
算法，将原问题NLP转化为仅有不等式约束的简单问题SP，然后通过旋转
操作产生SP的占积极约束集，在s积极约束集上建立简单问题SP的二次
规划子问题
minFcx；，O一c罗cjo1．11
蔻
s1．ciO≥0，iELIUE1．12
然后求解子问题，得到主方向，通过对主方向的校正，得到SP的可行下降方
向，为了防止Maratos效应，又建立一个新的高阶校正方向。
这个算法已经被证
明在条件较弱的情况下是全局收敛和超线性收敛的。
传统的SQP算法都是利用价值罚函数进行线搜索来判断迭代点的好坏。
在
一层面上发展了SQP算法，由于滤子法免去了价值罚函数的使用，从而也克服了
选择罚函数参数难的问题。
由于滤子法的数值计算比较容易，所以，近几年，这种方法受到许多学者的
将信赖域、滤子法与SOP算法结合起来，提出了混合的信赖域滤子SOP算法，并
分析了算法的全局收敛性。
总之，随着新的算法不断地提出和旧的算法的改进，SOP算法也在不断向前
发展，逐步走向完善和成熟。
1．3本文研究内容
本文研究了用SQP算法解决不等式约束的非线性规划问题。
主要是在约束优
化问题的￡一积极约束集上构造了二次规划子问题，从而减小了二次规划子问题
的规模，在一定的条件下，证明了算法的全局收敛性。
文章结构如下：
5
兰州大学2009届硕士学位论文
第一章，回顾了非线性规划的发展及算法的研究，重点论述了SOP算法的研
究过程和现状。
第二章，介绍了非线性规划的基本知识和二次规划的几个基本算法。
第三章，基于大规模的优化问题，讨论了积极约束集上的SQP算法。
第四章，证明了算法的全局收敛性。
第五章，对本文所做的工作进行了总结，概述了算法的优点和不足与进一步
的研究。
最后是参考文献及致谢。
6
兰州人学2009届硕上学位论文
第二章预备知识
2．1非线性规划
一般的非线性约束优化问题定义如F：
NLPminfx
sJ．cioo2．1
iEE1，2，…，me
qo≥o2．2
iEl历。
+1，…，m
题的约束条件。
2．1为等式约束，2．2为不等式约束。
m为正整数。
E，，分
别为等式约束和不等式约束的指标集。
记
X扛ER“lqoO,i1,2，…，犯；qo≥O,m。
+1'…研
称X为NLP问题的可行域，X中的点称为可行点。
记
sf
，OqO0,me+1s研
称集AxIxUE为x处的积极约束指标集，qO2o’f∈彳O为NLP问题
的积极不等式约束。
问题的全局最优解，称fx’为全局最优值。
设x‘ES，如果存在￡0，使得VxES
NMO’，总有fx≥fx‘成立，其
fx’为
中札o+xER“IIIx-x"8￡，则称石+为NLP问题的局部最优解，
局部最优值。
2．1．1梯度、Hesse矩阵与Jacobi矩阵
Cecl，
定义嘲：
设厂：
S呻尺其中SR“，且厂是连续可微的函数记作f
则厂的一阶导数定义为：
7
兰州大学2009届硕：
L学位论文
州_等，等，…，掣r汜3
称为f在点x处的梯度。
定义乜1：
若厂是二阶连续可微的，记作fEC2，则厂的二阶导数用以下矩阵
定义：
a2厂a2，a2厂
嵋2帆缸：
咄吒
a2厂a2，a2厂
V2fx％咄缸：
2吨吒2．4
a2，a2厂a2厂
咄咄帆毗帆2
称为，O在点x处的Hesse矩阵。
7
设向量函数f；^，，2o厶r：
掣一R”，若每个分量函数五是连续可微
的，则称厂是连续可微的。
向量函数厂在点x处的导数用以下矩阵定义：
亟堕…亟
奶奶奶
妖唬蔹
帆Ox2ak2．5
-，，O
彰钣吮
咄Ox2ak
称为fx在点x处的Jacobi矩阵。
此时，，O在点x处的梯度v厂O．，，Or--v／,，v，2，…，既。
2．1．2凸集与凸函数
定义嘲：
设集合sc
成立，则称S为凸集。
定理乜1：
彤的一个子集合是凸的，当且仅当它包含它的元素的所有的凸组合。
定理胆1：
设F是一族凸集，那么nS也是凸集。
瓣
定理晗1：
令S，S。
，S：
是R“中的凸集，口∈R，那么
8
兰州大学2009届硕士学位论文
1集合口s；z：
工ay，yES也是凸集。
2墨+是x：
z‘+吃，五∈墨，屯∈s：
也是凸集。
定义跚：
设SCR“是非空的凸集，函数f：
5--*R，若对任意的
毛，X2ES，A∈0，1，总有
2．6
，A．■+1一Aj吃sA，．■+1一afx：
则称，是S上的凸函数。
定理犯1：
设五：
s
CR4--,R／1，2，…，七是凸函数，则
‘1善qzG也是凸的，其中呸≥0／a1,2，…，七；
2m。
．ax。
ZG是凸的。
lSlS鼻
定理嗍：
设厂：
S_尺在开的凸集S
c彤上二次可微，则厂是凸的当且仅当对
d∈尺”，有
drV2，Oy≥02．7
成立。
若对任意的x∈s，V2fx是正定的，则厂是严格凸的。
凸规划是指非空凸集sc掣上极小化一个凸函数厂@，即fx。
m魁in
2．1．3中值定理和Taylor公式
定理嘲：
设厂O在开的凸集SCR“上连续可微，则对S中任意x，y，存在
A∈0，1，使得
2．8
，@，y+vfy+AO―y”rO～Y
若函数，O是二阶连续可微的，则有
2．9
定理乜1：
设函数，：
彤_月连续可微，向量d∈尺一，那么
2．10
，z+d；厂O+drVfx+olldll
若函数，O是二阶连续可微的，则
9
兰州大学2009届硕士学位论文
2．…
，o+d一，。
‖Vfx+三押2fxd+。
删2
2．1_3Kuhn．Tucker条件
的一个下降方向。
称d为集合S在点x处的一个可行方向。
凡f∈n“，yeF．，使得
‘2?
?
12’
Vfx’X喜Vqx++uj荟Vcjo‘
五苫0ViEl2．13
^cf0’0
点称为K―T点。
2．2最优化方法的结构
最优化算法通常采用迭代方法求得最优解，因而对最优化算法的研究，主要
包括对特定非线性规划模型如何构造寻求问题最优解的迭代点列，对迭代算法的
收敛性及算法收敛速度的估计等。
迭代算法的基本思想是：
从一个选定的初始点
xoER“出发，按照某一特定的迭代规则产生一个点列‘，使得当％是有穷点
列时，其最后一个点是问题NLP的最优解，当xk是无穷点列时，它有极限点，
并且其极限点是问题NLP的最优解。
一个好的算法应具备的典型特征为：
迭代
点xk能稳定地接近局部极小点x’的邻域，然后迅速收敛于石’．当给定的某种收敛
准则满足时，迭代即终止。
一般地，我们要证明迭代点列xk的聚点即子序列
的极限点为一局部极小点。
10
兰州大学2009届硕士学位论文
最优化算法的基本结构：
给定初始解‰
Step
l：
确定搜索方向dk，即依照某种规则，构造目标函数厂在故处的下
降方向作为搜索方向；
Step
2：
确定搜索步长q，使目标函数值有某种意义上的下降。
Step3：
令
‘+lxk+吼反
若^+，满足终止性条件，则停止迭代，得到近似最优解五+，；否则重复以上步骤。
2．3二次规划的算法
本文是用序N-次规划方法求解一般的非线性规划问题。
因此下面我们简单
介绍一下二次规划问题的算法。
二次规划是最简单的非线性规划问题，一般形式为：
minzr胁2．14
gTx+i1
SI．airx-b,iEE--t2，…，胁。
2．15
口fr石苫岛iEl他+1’…，m2．16
2．3．1积极约束集法
积极集法是通过求解有限个等式约束二次规划问题来解一般约束的二次规
划问题。
直观上，不积极的不等式约束在解的附近不起任何作用，可以去掉不考
虑；而积极的不等式约束，由于它在解x‘处等于零，故我们可以用如下等式约束
来代替不等式约束。
mingTX+l，’xrHx2．17
sj．airx--b,iEEUIx+2．18
积极集法的主要理论基础是如下定理。
定理…：
设石‘是二次规划问题2．14一2．16的局部极小点，则x+也必
兰州大学2009届硕+L学位论文
行点，且是2．14一2．16的K―T点，而且相应的Lagrange乘子
凡‘≥0，f∈JO’
则石’也是原问题的K―T点。
‘
积极集法是一个可行点方法，即每个点要求是可行点。
每次迭代求解一个等
式约束的二次规划。
如果等式二次规划的解是原约束问题的可行点，则判别相应
的Lagrange乘子^‘≥0，i∈tx’是否满足，如果满足，停止计算，否则可去掉一
约束重新求解约束问题。
当等式二次规划的解不是原约束问题的可行点，则需要
增加约束，然后重新求解等式约束问题。
2．3．2对偶方法
对于凸的二次规划2．14一2．16，其中日对称正定矩阵，它的对偶问题
为：
1
min一6+彳rH。
19rA+去ArorH。
彳A
S．t．丑苫0iEl
其中，A口l，R2C'％a。
。
这样，就把一个一般的约束二次规划问题转化称为边界约束二次规划问题，
目前，已经有很多种方法解这个边界约束问题。
[3]给出了解决二次规划的对偶
方法。
文献[4]，[5]介绍了一种解大规模非线性规划问题的子空间有限存储拟牛
顿方法，文献[6]介绍了一种负梯度与截断牛顿法混合的算法。
2．3．2内点算法
自1984年提出著名的Karmarkar算法以来，内点算法理论得到了飞速发展，
并且它的应用领域也得到了不断的扩展。
特别是，在求解线性规划和凸二次规划
中，许多内点算法具有多项式复杂性，但它们要求算法的初始点是严格可行的。
在理论证明中可行初始点是存在的，然而在实际计算中要找这样的初始点很难。
为了克服这一困难，有些人从放宽初始点的要求着手，提出了不可行内点算法。
解线性规划的全局收敛的不可行内点算法。
12
兰州大学2009届硕士学位论文
第三章积极约束集上的SQP算法
3．1算法的提出与思想
随着SQP算法的不断向前发展，它的应用越来越广泛。
近几年，人们将它用
在求解不光滑的方程式、变分不等式以及带有平衡约束的数学规划上
解大规模非线性优化问题时，由于约束规模很大，导致每个二次规划子问题的规
模也很大，于是，算法的实现需要非常大的存储空间，导致运算比较困难；此外，
子问题约束的不相容性加大了。
针对这两个问题，我们研究了积极约束集SQP算法。
算法的基本思想是在原
问题的￡积极约束集上构造二次规划子问题，通过求解该二次规划子问题，获得
约束优化问题的一个改进迭代点；不断重复这个过程，直到迭代点满足一定要求。
这种做法既可减小子问题的规模，也减少了子问题可行域非空的可能性。
3．2算法的推导
本文只考虑了不等式约束的非线性规划问题
Pminfx3．1
眠qO≥o3．2
iEl--1,2，…，m
其中厂@：
彤呻R，qOⅪ∈，：
尺”呻R都是二阶连续可微函数。
设■是当前问题P的迭代点，构造二次规划子问题，
QPming瓴饥≯删3．3
st．iEl3．4
q瓴+Vqxkrd≥0，
其中g瓴zv，瓴，H。
为正定矩阵，一般是Lagrang
升级会员 