（应用数学专业论文）非线性约束优化问题的信赖域内点算法.pdf

非线性约束优化问题的信赖域内点算法 摘要 最优化问题是决策科学和物理系统分析中的一个重要工具，它广泛应用于科学、工 程、经济和工业等领域非线性规划是优化问题的重要分支，本文我们对三个不同的非 线性约束规划问题分别提出三种信赖域内点算法。 线搜索技术和信赖域策略是解非线性优化问题的两种基本逼近方法，这两种技术都 能用来保证算法的整体收敛性本文将提出一种仿射变换的信赖内点算法解决变量有界 的线性等式约束优化问题构造合理的仿射变换矩阵，在投影空间构造信赖域子问题， 产生迭代方向，使迭代点既保持在信赖域内，又是严格可行域的内点信赖域方法并不 要求目标函数的二次模型凸性，在信赖域内求得迭代步使得二次模型最小如果目标函 数，相对于预计下降量有一个较好的实际下降量，则迭代步被接受，并且信赖域半径可 扩大，否则信赖域半径应缩小并重新计算信赖域子问题来得到新的迭代点在合理的假 设条件下，我们证明了这一算法不仅具备整体收敛性，而且具有超线性收敛速率并给 出了数值结果，表明了算法的有效性 本文又提供了一种基于双折线路径的非单调信赖域内点回代法，求解变量有界的约 束优化问题，对于传统的信赖域方法，要获得可按受的迭代步可能要通过重复计算多次 信赖域子问题才能获得，因此每完成一次迭代的整个计算会比较大n o c e d a l 和y u a n 提出了信赖域与线搜索两种技术相结合的方法，称为回代法( b a c k t r a c k i n g ) 当由信赖域 子问题求得的搜索方向不被接受时，利用线搜技术得到接受步长，定义新的有足够下降 量的送代点我们利用非单调技术得到使目标函数非单调下降的迭代点，因为非单调克 服高度非线性化函数的求解问题，从而避免了只使用单调搜索在“峡谷”现象局部最优 解被卡的情况，我们用信赖域策略和非单调线搜索技术相结合的方法，使算法产生的迭 代步落在可行域内点，同时又在信赖域内满足接受准则d e n n i s 和m e i 提出了双折线 路径方法，它利用柯西步和牛顿步信息构造双折线，一般地，基于双折线路径方法可以 在双折线路径和信赖域边界相交点得到迭代步通过给出双折线路径的一些性质，在合 理的条件下，我们证明了所提供算法具有整体收敛性并得到局部收敛速率，给出数值结 果，表明了算法有效性 既约h e s s e 算法是目前较流行的解决非线性等式约束优化问题的有效方法之一最 近c h a y ag u r w i t z 在n o c e d a l 和o v e r t o n 等人工作的基础上，提出了两块校正的投影 h e s s e 矩阵方法，讨论了其算法的局部收敛速率，但未涉及整体收敛性本文我们又提供 一种两块校正的投影信赖域方法解非线性等到式约束问题为了处理大规模问题，我们 i i i 使用双边的两块校正代替整个h e s s e 矩阵的校正采用f 1 罚函数作为势函数，用非单调 的信赖域回代策略，不用每一步迭代均下降我们引进二阶校正步，克服了由f 。罚函数 的不可微性引起的m a r a t o s 效应在合理的条件下我们证明了所提供的非单调信赖域回 代方法具有整体收敛性，并有如果每一步至少校正两个校正矩阵中的一个，则算法保持 一步q 超线性收敛速率 关键词：非线性约束优化；整体收敛性；局部收敛速率；信赖域方法；非单调技术；内 点法 分类号：0 2 4 17 i v t r u s tr e g i o ni n t e r i o rp o i n ta l g o r i t h m sf o rn o n l i n e a r c o n s t r a i n e do p t i m i z a t i o np r o b l e m s a b s t r a c t o p t i m i z a t i o ni sa ni m p o r t a n tt o o li nd e c i s i o ns c i e n c ea n di nt h ea n a l y s i so fp h y s i c a l s y s t e m s i th a st h ew i d e ( a n dg r o w i n g ) a p p l i c a t i o n si ns c i e n c e ，e n g i n e e r i n g je c o n o m i c sa n d i n d u s t r y ，e t c n o n l i n e a rp r o g r a m m i n g i sa ni m p o r t a n ta n da c t i v eb r a n c ho fo p t i m i z a t i o n s i nt h i st h e s i s ，w ep r o p o s et h r e et r u s tr e g i o ni n t e r i o ra l g o r i t h m sf o rt h r e ed i f f e r e n tn o n l i n e a r o p t i m i z a t i o n s ，r e s p e c t i v e l y b o t hl i n es e a r c ha n dt r u s tr e g i o na r ew e l l a c c e p t e dm e t h o d si nt h en o n l i n e a rp r o g r a m m i n g t oa s s u r eg l o b a lc o n v e r g e n c e i nt h i st h e s i sw ep r o p o s ea s c a l i n gt r u s tr e g i o n i n t e r i o rp o i n ta l g o r i t h mf o rl i n e a rc o n s t r a i n e d o p t i m i z a t i o ns u b j e c tt ob o u n d so nv a r i a b l e w eu s eas c a l i n gm a t r i xw h i c hm a k et h ea l g o r i t h mg e n e r a t es e q u e n c e so fp o i n ti nt r u s t r e g i o na n dt h ei n t e r i o ro f t h ef e a s i b l es e t b e c a u s eo ft h eb o u n d e d n e s so ft h et r u s tr e g i o n ， t r u s tr e g i o na l g o r i t h mc & nu s en o n c o n v e x a p p r o x i m a t em o d e l s as o l u t i o nt h a tm i n i m i z e s t h em o d e lf u n c t i o nw i t h i nt h et r u s tr e g i o ni ss o l v e da sat r i a ls t e p i ft h ea c t u a lr e d u c t i o n a c h i e v e do ut h eo b j e c t i v ef u n c t i o n | a tt h i sp o i n ti ss a t i s f a c t o r yc o m p a r i n gw i t ht h er e d u c t i o n p r e d i c t e db yt h eq u a d r a t i cm o d e l ，t h e nt h ep o i n ti sa c c e p t e da san e wi t e r a t e ，a n d h e n c et h et r u s tr e g i o nr a d i u si sa d j u s t e da n dt h ep r o c e d u r e i sr e p e a t e d o t h e r w i s e ，t h e t r u s tr e g i o nr a d i u ss h o u l db er e d u c e da n dad e wt r i a lp o i n tn e e d st ob ed e t e r m i n e d w e s h o wt h ep r o p o s e da l g o r i t h mi sg l o b a l l yc o n v e r g e n ta n dl o c a l l yf a s tc o n v e r g e n tr a t ee v e n i fc o n d i t i o n sa r er e a s o n a l b e t h er e s u l t so fn u m e r i c a le x p e r i m e n ta r er e p o r t e dt os h o w t h ee f f e c t i v e n e s so ft h ep r o p o s e da l g o r i t h mf o rl i n e a rc o n s t r a i n e do p t i m i z a t i o ns u b j e c tt o b o u n d so nv a r j a h 】e w ea l s op r o p o s ea na f f i n es c a l i n gt r u s tr e g i o ni n t e r i o rp o i n ta l g o r i t h mv i ad o u b l e d o g l e gp a t hf o r n o n l i n e a ro p t i m i z a t i o ns u b j e c tt ob o u n d so nv a r i a b l e si ti s p o s s s i b l e t h a tt h et r u s tr e g i o ns u b p r o b l e mn e e d st ob er e s o l v e dm a n yt i m e sb e f o r eo b t a i n i n ga n a c c e p t a b l es t e pf o r t h et r a d i t i o n a lt r u s tr e g i o nm e t h o d ，a n dh e n c et h et o t a lc o m p u t a - t i o nf o rc o m p l e t i n go n ei t e r a t i o n m i g h tb ee x p e n s i v e n o c e d a la n dy u a ns u g g e s t e d a c o m b i n a t i o no ft h et r n s tr e g i o na n dl i n es e a r c hm e t h o df o ru n c o n s t r a i n e do p t i m i z a t i o n t h i sm i x e dt e c h n i q u ei sc a l l e db a c k t r a k i n g t i l ep l a u s i b l er e m e d ym o t i v a t e d st os w i t c h v t ot h el i n es e a r c hm e t h o db ye m p l o y i n gt h eb a c k t r a c k i n gs t e p sa ta nu n s u c c e s s f u lt r i a l s t e p o fc o u r s e ，t h ep r e r e q u i s i t ef o rb e i n ga b l et om a k i n gt h i ss h i f ti st h a ta l t h o u g ht h e t r i a ls t e pi s u n a c c e p t a b l ea sn e x ti t e r a t i v ep o i n t ，i ts h o u l dp r o v i d ead i r e c t i o no fs u f f i c i e n td e s c e n t f o rp r o b l e m sw h o s eo b j e c t i v ef u n c t i o no rc o n s t r a i n tf u n c t i o n sh a v es h a r p c u r v e so nt h e i rc o n t o u rm a p s ( s u c ha st h er o s e n b r o c k sf u n c t i o nw h i c hh a sb a n a n a s h a p e c o n t o u r s ) ，m o n o t o n i c i t ym a y c a u s eas e r i e so fv e r ys m a l ls t e p s ，c a u s i n gah u g en u m b e r o fi t e r a t i o nt or e a c ht h e i rs o l u t i o n s b yu s i n gt h en o n m o n o t o n et e c h n i q u e ，w eg e tt h e s e q u e n c eo fs u c c e s s f u li n t e r a t i v ep o i n tw h i c hs h o u l dm a k et h eo b j e c t i v ef u n c t i o nm o n o t o n i c a l l yd e c r e a s i n g h e n c e ，w eu s eb o t ht r u s tr e g i o ns t r a t e g ya n dl i n es e a r c ht e c h n i q u e a n dm a k ee a c hi t e r a t eg e n e r a t ea na c c e p t a b l et r i a ls t e pi ni n t e r i o rf e a s i b l es e ta sn e x t i n t e r a t i v ep o i n t t h ed o u b l ed o g l e gp a t hm e t h o d ，w h i c hm a k e su s eo ft h ei n f o r m a t i o no f c a u c hs t e pa n dn e w t o ns t e p ，w a sp r o p o s e db yd e n n i sa n dm e i b a s e do i ld o u b l ed o g l e g p a t h ，t h ei t e r a t i v ed i r e c t i o ni sa l w a y so b t a i n e di nt h ei n t e r s e c t i o no fd o u b l ed o g l e gp a t h a n db o u n do ft r u s tr e g i o nb ys o l v i n gt h ea f f i n es c a l i n gt r u s tr e g i o ns u b p r o b l e r n b y g i v i n g s o m e p r o p e r t i e so f t h ed o u b l ed o g l e gp a t h ，w ep r o v et h eg l o b a lc o n v e r g e n c ea n df a s tl o c a l c o n v e r g e n c er a t eo ft h ep r o p o s e da l g o r i t h mu n d e rs o m er e a s o n a b l ec o n d i t i o n s an o n m o n o t o n i cc r i t e r i o ni su s e dt os p e e du pt h ec o n v e r g e n c ep r o g r e s si ns o m ei l l c o n d i t i o n e d c a s e s t h er e s u l t so fn u m e r i c a le x p e r i m e n ta r er e p o r t e dt os h o wt h ee f f e c t i v e n e s so ft h e p r o p o s e da l g o r i t h m s r e d u c e dh e s s i a na l g o r i t h mh a sb e c a m eo n eo ft h ev e r yp o p u l a ra n dm o s te f f e c i v e m e t h o d sf o rs o l v i n gn o n l i n e a re q u a l i t yc o n s t r a i n e dp r o g r a m m i n g r e c e n t l y ，c h a y ao u r w i t zp r o p o s e dt h et w o p i e c eu p d a t eo fap r o j e c t e dh e s s i a nm a t r i xa l g o r i t h mw h i c hb a s e d o nt h ew o r ko fn o c e d a la n do v e r t o n h ed i s c u s s e do n l yt h el o c a lq s u p e r l i n e a ro ft h i s o r i g i n a la l g o r i t h mb u td i dn o td e a lw i t ht h eg l o b a lc o n v e r g e n c e i nt h i st h e s i sw ea l s o p r o p o s eat w o - p i e c eu p d a t eo fp r o j e c t e dh e s s i a na l g o r i t h mw i t ht r u s tr e g i o nm e t h o df o r s o l v i n gn o n l i n e a re q u a l i t yc o n s t r a i n e do p t i m i z a t i o np r o b l e m s i no r d e r t od e a lw i t hl a r g e p r o b l e m s ，at w o p i e c eu p d a t eo ft w o s i d er e d u c e dh e s s i a ni su s e dt or e p l a c ef u l lh e s s i a n m a t r i x b ya d o p t i n gt h el lp e n a l t yf u n c t i o n a st h em e r i tf u n c t i o n ，an o n m o n o t o n i cb a c k t r a c k i n gt r u s tr e g i o ns t r a t e g yi ss u g g e s t e d w h i c hd o e sn o tr e q u i r et h em e r i tf u n c t i o nt oi t s v a l u ei ne v e r yi t e r a t i o n b yu s i n gs e c o n do r d e rc o r r e c t i o ns t e p ，w eo v e r c o m et h em a r a t o s e f f e c tw h i c hc a u s e db yt h ei n d i f f e r i t yo ft h e1 1p e n a l t yf u n c t i o nt h ep r o p o s e da l g o r i t h m w h i c hs w i t c h st on o n m o n o t o n i ct r u s tr e g i o ns t r a t e g yp o s s e s sg l o b a lc o n v e r g e n c ew h i l e m a i n t a i n i n go n es t e pq s u p e r l i n e a rl o c a lc o n v e r g e n c er a t e si fa tl e a s t o n eo ft h eu p d a t e v i f o r m u l ai su p d a t e da te a c hi t e r a t i o n k e y w o r d s ：n o n l i n e a r c o n s t r a i n e dp r o g r a m m i n g ；g l o b a lc o n v e r g e n c e ；l o c a lc o n v e r g e n c e r a t e ；t r u s tr e g i o nm e t h o d ；n o n m o n o t o n i ct e c h n i q u e ；i n t e r i o rp o i n tm e t h o d a m s1 9 9 1s u j b e c tc l a s s i f i c a t i o n ：9 0 c 3 0 ，6 5 k 0 5 v i i 致谢 首先本文在导师朱德通教授的精心指导顺利地完成朱德通教授有渊博的数学知识， 严谨的学术作风，指引我在基础学习和学术研究上找到正确的方向他经常耐心地对我 进行指导，毫无保留将他的研究心得和新的想法与我分享在本人研究生学习期间，从 学习、工作、生活等方面给予我莫大的帮助谨向我的导师表示衷心的感谢 还要感谢在数理信息学院学习期间给我上课的很多老师，像王国荣教授、张寄洲教 授、曾六j ij 教授、施永兵教授、王立联老师和王蓉华老师，从他们的课上学到了很多知 识同时感谢其他帮助支持过我的老师特别还要感谢钱纯青老师，他是我的老师，也 是我的同事、兄弟，他的进取心，他的学术追求是我很好的榜样，他在我研究生学习的 最初时间给予我很细致的关心和指导，但他不幸被病魔所累，最后永远地离开了我们， 我永远怀念他 衷心感谢同办公室的两位同事，姚战平老师和李琦蔚老师，他们在我研究生学习期 间给予我极大的帮助与支持感谢同门师兄姐妹，傅军、赖海英、张乐瑛、郭佩华、王云 娟等，在学习期问给了我许多的支持与互勉 最后衷心感谢我的家人，是他们的支持给了我动力和灵感，是他们的无限关怀和鼓 励让我能不断进步，是他们的无私付出使我安心地完成学业 序言 最优化问题( 数学规划) 是个古老的课题，在数学上是一种求极值的问题随着生产 和科学研究的突飞猛进的发展，最优化理论和算法在近五六十年中也有了迅速的发展， 在实际应用中也发挥着越来越大的作用 最优化是决策科学和工程系统分析的重要工具，使用最优化方法解实际问题，首先 必须根据实际情况列出目标函数，目标函数是由变量( 未知数) 组成的函数式，这个过 程我们称为建模，然后通过合适的方法寻求变量的值使得目标函数值最优最优化问题 据其目标函数和约束条件是否线性可分为线性最优化问题和非线性最优化问题，这里我 们讨论和研究的问题都是非线性最优化问题非线性规划就是解决和计算许多变量的非 线性函数( 目标函数) 的最优解特别当变量受到一些条件的限制时，寻求目标函数最优 解称为约束优化反之，变量不受任何约束的限制，寻求最优解称为无约束最优化 本文基于变量有界约束优化和非线性等式约束优化的特性及特点提出新的算法和理 论因为信赖域方法能有效应用于大规模的具有稀疏h e s s e 矩阵的( 无) 约束优化中，它避 免了目标函数h e s s e 矩阵正定性的条件限制，是一种新的保证整体收敛性的数值方法 所以本文在求解约束优化问题时，均使用了信赖域策略约束问题使用信赖域方法，在 求解搜索方向时每次迭代都需要求解一个带约束的子问题，对于变量有界的线性等式约 束优化问题，我们利用仿射内点变换，在取合理的信赖域半径时迭代所得方向均落在严 格内点，使解信赖域子问题时不用考虑有界约束又利用不同于前者的仿射投影方法， 同时采用信赖域策略与线搜索技术相结合的方法，解信赖域子问题得到搜索方向后，通 过线搜索使迭代步于可行域内点求得，并且满足接受准则两种技术结合方法避免了重 复求解信赖域子问题，有效减少了的计算工作量，发挥了信赖域和线搜索的各自优势， 克服各自局限性，并更有效、完善地改进了收敛性信赖域方法中如何解信赖域子问题是 关键的部分，我们针对变量有界等式约束问题构造双折线路径方法来解信赖域子问题， 有效利用牛顿步和c a u e h y 步的信息，在信赖域内从双折线路径上找到搜索方向应用 线搜索技术可以确定沿信赖域迭代方向的步长因子，使目标函数得到可接受的下降量 精确一维搜索方法往往需花费很大的工作量，特别当迭代点远离问题的解时，通常不十 分有效因此我们采用不精确一维搜索方法，利用a r m i j o g o l d s t e i n 准则，保证目标函 数有满意下降量对于非线性等式约束我们基于信赖域和线搜索结合的技术，利用q r 分解的既约h e s s e 思想将原问题分解成两个通常的信赖域子问题，更易于数值求解和实 现算法中我们还使用p ，罚函数作为价值函数进行线搜索，在较弱的条件下，可以证明 了算法具有局部超线r _ 线性收敛，我们又使用二阶校正步技术，引入非对称的b r o y d e n 校正，克服了由，罚函数的不可微性引起的m a r a t o s 效应，从而获得了更好的具有局部 步q 一超线性收敛速率在信赖域和线搜索结合方法中，我们还采使用非单调的搜索技 术，一方面非单调的搜索技术可以克服m a r a t o s 效应，另一方面克服高度非线性化函数 ( 称为病态) 的求解问题，从而避免了只使用单调搜索在“峡谷”现象局部最优解被卡的 情况，比单调搜索有更快的收敛进程，特别是函数的斜率非常陡的情况下，显得更为突 出本文中所提出的算法使用的思想和技巧有创新也有一定的难度，但算法对优化问题 的数值计算，特别是对于大规模的数值运算，运算量和运算速度有很大的改善我们对 所提供算给出了完善的理论证明，同时也利用计算机编程对算法进行数值实验，通过数 值实验进一步说明算法的有效性 论文概述 第一章将回顾了在其它章节中将用到的( 无) 约束优化的基本理论，熟悉这方面概 念的读者可以跳过这一章第二章我们提供一种仿射内点信赖域算法解决变量有界的线 性等式约束优化问题，加上合理的假设可以证明这种算法的整体收敛性和超线性局部收 敛速率，并给出了数值计算结果，表明了所提供算法的有效性第三章提供另外一种信 赖域回代投影内点算法解变量有界约束的非线性优化问题，该算法的信赖域子问题用双 折线路径技术来解决也证明了该算法在合理的条件下具有整体收敛性，并保证局部超 线性收敛速率利用较多的数值算例，对此算法的有效性进行了检验第四章解决非线 性等式约束优化问题，提供了两块校正的非单调回代算法，此算法利用两块校正的双边 既然约h e s s e 技术，使用非单调的信赖域回代法，较好的解决了非线性等式约束优化， 具有良好的整体收敛性和整体收敛速率。第五章对本文工作进行总结，同时提出进一步 研究的方向 符号和缩写 舻表示n 维向量空间； 虢“表示nxm 维实矩阵； 口( z ) = v ，( 。) 表示目标函数f ( x ) 的梯度； n 表示可行集； i n t ( q ) 表示严格可行集； 表示等式约束指标集； z 表示不等式约束指标集； a ( z ) 表示约束优化问题在可行点z 处的起作用集； v 2 ，( z ) ，v 2 c ；( z ) 和v ：。l ( x ， ) 分别表示，( z ) ，c i ( x ) 和l ( z ，a ) 关于向量变量z 的 2 h e s s i a n 矩阵； 向量和矩阵范数”l l 是如范数 以表示迭代方向； v ( x ) 舻。“表示构成a ( x ) 值空间的一组标准正交基； z ( x ) 舻。( 一“】表示构成4 ( z ) 7 零空间的一组标准正交基； r ( x ) 表示m 阶上三角满秩矩阵； 冗( a ( z ) ) 表示a ( x ) 的值空间； 厂( a 扛) 7 ) 表示a 0 ) 丁的值空间； a 表示等式约束的拉格朗日乘子； l ( x ，a ) = ，( 。) 一a t c ( z ) 表示等式约束优化问题的拉格朗日函数； w ( z ，a ) = v 2 f ( z ) 一2 1 九v 2 q ( 。) 表示拉格朗日函数关于x 的h e s s e 阵； 碟表示零空间步； 醒表示值空间步； 表示信赖域半径 p ( r ) 表示有界变量优化问题的双折线路径； p r e d ( s ) 表示信赖域子问题二次模型的预计下降量； a r e d ( s ) 表示目标函数的实际下降量； 机( o k ) 表示l l 罚函数； d 妣( 茁 ；5 k ) 表示l 沿方向以的方向导数罚函数 r 7 ? 表示注释 a 7 ? 表示假设 3 第一章非线性优化的基本概念、方法及收敛性质 1 1 非线性最优化问题 非线性最优化问题是解决和计算许多变量的非线性函数的最优解当目标函数中决 策变量受到一定条件限制时寻求最优解我们称约束最优化，反之，决策变量不受任何限 制时我们称为无约束最优化 我们记x 舻为决策变量，( z ) 称为目标函数，c ( z ) 为约束向量函数则约束最 优化问题一般形式为： m i n f ( z ) s t q ( 。) = 0 ，i = 1 ，2 ，一，m 。( 11 1 ) c i ( x ) 0 ，i = m 。+ 1 ，一，m 为了方便数值计算，这里我们定义的目标函数f ( x ) 与约束函数c ( z ) 均为实值可微函数， 且其中f ( x ) 一定是非线性的m m 。是两非负整数，当m = m 。= 0 时，问题( 1 1 1 ) 是无约束最优化问题集合 q d e j zlc i ( z ) = 0 ，i = 1 ，2 ，一，m 。；c ；( 石) 0 ，i = m 。+ 1 ，- 一，m )( 1 1 2 ) 称为问题( 1 1 1 ) 的可行域不要求不等式约束等号满足时，可行域成为严格可行域，即 i n t ( f 2 ) d = e f ziq ( z ) = 0 ，i = 1 ，2 ，m 。；c i 扛) 0 ，i = m 。+ 1 ，m ) ( 1 1 3 ) 称为问题( 1 1 1 ) 的严格可行域 定义1 1 1设x + n ，若对任意z n 有 f ( x + ) ，( z )( 1 1 4 ) 则称矿是问题“j 圳的整体极小值点进一步，若对一切x n 且z z + 有 ，( z + ) 0 为半径 使得对任意z q n ( z + ，e ) 有 f ( x 4 ) 5f ( x ) 4 以z + 为中心点的邻域( 矿，) ( 1 1 6 ) 则称z + 是问题门j j 的局部极小点，进一步，如果 f ( x + ) 0 成立，则我们可将第矿个约束条件去掉，且z + 仍然是去掉第一个约束条件所 得到问题的局部最优解由此，我们称上述第一个约束在矿处不起作用若记 = ( 1 ，2 ，一，m 。) ， z = ( m 。+ 1 ，一t ，m ) ， 五( z ) = 。lq ( z ) = 0 ，i z ( 1 2 ，1 ) ( 1 2 2 ) ( 1 2 3 ) 定义1 2 i 对任意z 舻，我们称集合 一4 ( z ) = u 五( z ) ( 1 2 4 ) 是问题“1 叫在茁点处的起作用集他有效集合，c 。扛) ( i a ( 嚣) ) 是在z 点处的起作 用约束傀有效约束j 定义1 2 2设z + q ，4 ( 。+ ) 是由( 1 2 4 ) 定义的起作用集，如果 v c i ( z + ) ，i 4 ( 矿) ) 线性无关，则称问题仁j j ，具有线性无关约束品性 定义m + n 维关于( x ，a ) 的函数 c ( x ，a ) = ，( z ) 一a 矗( 茁) ， ( 1 25 ) t = l 称为问题( 111 ) 的拉格朗日函数，其中a 称为拉格朗日乘子 5 定理1 2 3设z 4 是问题f j j j j 的局部最优解，又设在。+ 点线性无关约束品性成立 则存在向量a + = ( a j ，a 麓) r ，使得 v 。l ( x + ，a + ) = 0 ， a ：兰0 ，a ；c ：( 茁+ ) = 0 ，i 工 ( 12 6 ) ( 1 27 ) 定理1 2 3 通常被称为k a r u s h k u h n t u c k e r ( 简称k k t ) 定理，( 1 2 6 ) 一( 1 ，2 7 ) 称为问题( t 1 1 ) 的一阶必要性条件或k k t 条件，满足( 12 6 ) 一( 1 2 7 ) 的点z + 称为问 题( 1 1 1 ) 的k k t 点可见，在线性无关约束品性成立的假定下，最优解必定是k k t 点 条件n c 。( z + ) = 0 称为互补松驰条件，它表明，碍与c i ( x + ) 不能同时不等于0 ，或 者说，非有效约束的拉格朗日乘子为0 k 与岛( 矿) 有可能同时等于0 ，即有效约束的 乘子可能为0 如果所有有效约束的乘子均不为0 ，即对i 4 ( z + ) 有n = c i ( x 4 ) = 0 ， 则我们说严格互补松驰条件成立， 问题( 1 1 1 ) 当u 工= 0 时为无约束最优化问题 锄m i n 。m ) 它的一阶最优性条件可描述为 定理1 2 4设z + 是，( z ) 的局部极小点，且，在。+ 的一个开邻域内可微，则 v ( z + ) = 0 1 3线搜索技术及信赖域方法 ( 1 2 8 ) ( 1 2 9 ) 解最优化问题方法最常见的是迭代迭代法的基本思想是：在给出( x ) 的极小点位 置的一个初始估计x o 舻( 称为初始点) 后按照某一迭代规则计算出一系列的x k ( = 1 ，2 ，) ，希望点列 z k ) 收敛或就是最优化问题的解当迭代点满足所要求的收敛准则 时，迭代终止 设x k 为第k 次迭代点，以为第k 次搜索方向，。 为第k 次步长因子，则第k 次 迭代格式为 x k + l = x k + 乜女“ 6 ( 13 1 ) 线搜索方法是非线性优化的整体收敛性方法，很多线搜索方法要求以为，在z 点 处的下降方向，即要求满足 或者 v f ( x ) t & o( 1 3 2 ) f ( x k + a ：s k ) ，( z )( 1 3 3 ) 因为这样能确保函数，值延着下降方向逐次减小每一类下降迭代算法包含两个关键步 骤：一是如何搜索方向5 k ，二是在确定方向后如何进行一维搜索确定搜索方向的方法有 很多，如最速下降法、牛顿法、拟牛顿法、共轭梯度法等等， 基于目标函数的一次泰勒展开，在迭代点x k 附近， f ( x + 6 ) f ( x ) 十5 t v f ( x k )( 1 3 4 ) 所以，根据c a u c h y s c h w a r t z 不等式 1 6 t v f ( x ) i 茎恻 v f ( x ) | |( 1 3 5 ) 可知当且仅当如= 一v f ( x k ) 时，5 t v f ( x k ) 达到最小最速下降法就取f ( x ) 在z t 点 方向导数最小的方向作为搜索方向，即令 “= 一v ，( ) ( 1 3 6 ) 基于目标函数的二次泰勒展开，在迭代点z t 附近， ，( z 女+ 6 ) z ，o k ) + 6 t v ，( z k ) + ：6 t v 2 ，( 王k ) d ( 1 ，3 。7 ) 故考察 m i nt v ，( z k ) + ；铲v 2 f ( x k ) d ( 1 3 8 ) 则知道( 1 3 8 ) 的解是以= 一【v 2 ，( z k ) 】v f ( x k ) 牛顿法就取 5 k = 一 v 2 f ( x 女) - 1 v f ( x k )( 1 39 ) 作为搜索方向，其中假定v 2 f ( x k ) 是正定的 线搜索下降方向确定后，接着沿此方向进行线性搜索，线性搜索方法可分为精确线 性搜索和不精确线性搜索精确的线性搜索求o l k 使得 ，( z k + a k 6 k ) 2 恕口，( z t + 以) ( 1 3 1 0 ) 7 精确的搜索方法往往需要花费大量工作，特别当迭代点远离问题的解时，精确地求解一 个子问题通常不十分有效实际上，我们只要保证每一步迭代都有满意的下降量就可以 了，这样能大大节省工作量a r m i j o 和g o l d s t e i n 分别提出了不精确一维搜索过程，要 求步长因子满足 f ( x k + o r k s k ) 曼，( z 女) 十p c e k ( v f ( x k ) ，民) ( v f ( x k + a 女以) ，以) ( 1 p ) ( v f ( x k ) ，以) ( 13 1 1 ) ( 1 3 1 2 ) 其中p j 1 ( 1 3 1 1 ) 和( 1 3 ，1 2 ) 称为a r m i j o g o l d s t e i n 准则 a r m i j o g o l d s t e i n 准则可 能把步长因子a 的极小值排除掉了，所以w o l f - p o w e l l 准则给出了一个更简单的条件代 替，就是 0 是信赖域半径 定理1 3 2 伽r e 礼s e 吖j 明s 舻是子问题p o j 圳的解当且仅当存在唯一的“0 使 得 f b + v i ) s = - g 弘( 1 l s l l 2 一：) = 0 且b + 是半正定矩阵 对任一试探步乱，我们称 p r e d ( s k ) = 妒k ( o ) 一c i o k ( s k ) 为二次模型函数( 3 1 7 ) 的预计下降量，称 a r e d ( s k ) = ，( z ) 一，( z k + 8 k ) ( 1 3 1 6 ) ( l 3 1 7 ) ( 1 , 3 1 8 ) ( 1 3 1 9 ) 为目标函数的实际下降量定义比值 p 女= 必p r e d ( s k ) ( 1 3 2 0 )m 2 l l 。”， 它衡量了二次模型近似目标函数的程度，因此通过这一比值可以决定是否接受试探步并 且调节信赖域半径当p t 越接近l ，表示近似程度越好，则由该试探步得到新的迭代点， 并调整信赖域；否则，缩小信赖域半径并重新求解搜索方向 9 信赖域子问题的求解方法有很多一般情况下，当仇正定且i l b i l v f ( x k ) i l 。 时，子问题( 1 3 1 5 ) 的解可以简单地通过求二次模型仇( 6 ) 在无信赖域约束下的最优解 s g = 一b i l v f ( x ) 得到，s 被称为牛顿步信赖域方法也可以通过构造适当的路径， 在路径上搜索满足信赖域约束的二次模型最小值弧线路径方法有很多，如折线路径、 最优路径、共轭梯度路径、修正梯度路径等 n o c e d a 和y u a n 1 3 提出了一种结合信赖域和线搜索的方法，这种方法被称为回代 ( b a c k t r a c k i n g ) 法在信赖域方法中我们知道第次迭代后二次模型在信赖域半径k 内 计算出了一个试探步以，以是否被接受取决于比值p k ，如果不接受，需要缩小信赖域半 径后对同一问题重新计算步以而回代法自然地利用了内计算出的试探