（基础数学专业论文）无二次子规划算法及应用.pdf

摘要 摘要 非线性不等式约束优化问题是最优化领域中重要的研究课题，许多实际问 题都可以归结为非线性不等式约束优化问题。它有很多实际的应用价值。在应 用数学方面，可以应用到约束拟合和优化控制等领域；在物理学方面，可以应 用到光学和流体学等学科；还可以应用到化学、工程学、计算机科学等学科， 由此，可见它的重要性。f l - 十世纪七十年代后期，序n - 次规划( s q p ) 方法已 成为解非线性最优化问题的一种最常见、最有效的方法。s q p 方法具有类似牛 顿方法的快速收敛性，但是当迭代点远离问题的解时有可能会出现不稳定的行 为，而且s q p 方法在求解二次子规划时，计算量相当大，有可能出现二次子规 划无解的情况。因此，有必要研究一种新的方法来克服这些问题。 近年来，有不少学者【3 3 ，6 4 ，8 0 ，1 0 5 ，1 3 3 1 研究用线性方程组来代替二次规 划子问题来解非线性不等式约束优化问题和变分不等式的数值解问题，这就是 无二次子规划( q p f r e e ) 算法，是把求非线性不等式约束优化问题转换为线性方 程组的求解问题。在每次迭代中，只需解若干个具有相同系数矩阵的线性方程 组，因此避免了序列二次规划( s q p ) 方法中遇到的问题，而且减少了计算量。 本学位论文通过构造新的无二次子规划( q p f r e e ) 算法求解非线性不等式约 束优化问题、变分不等式问题，以及对这类方法进一步的研究，包括对非线性 互补( n c p ) 函数的及其与算法的收敛性和收敛率的关系研究；构造以牛顿法 和拟牛顿法为核心的新算法，以及对这些算法在”弱”的假设条件下的可行性、 稳定性、全局收敛性和收敛率的分析，不但对解非线性不等式约束优化问题、 变分不等式的数值解问题提供了有效方法，并且可以把这些思想和技巧扩展应 用到其他一些非线性规划的方法，取到更好的成果。研究的内容和方法主要包 括如下几个方面： ( 1 ) 在 1 0 5 】h q i 和l q i 提出了个可行的q p f r e e 算法解非线性不等式 约束优化问题。在【1 3 3 中，y y a n g ，d l i 和l q i 提出另一类q p f r e e 算法， 也可称为序列线性方程组( s s l e ) 算法解非线性不等式约束优化问题。但在算 法的全局收敛性的证明中，仍需要一些较强的假设条件。一是假设在解处的积 极约束函数的梯度是线性独立的；另一个是假设由拟牛顿方法修正得到的矩 阵日七的一致正定性，但是，对于一般的函数厂( z ) ，不能确保矩阵h 的一致正定 性。为了克服这些缺点，提出新的可行的无二次子规j 甜( q p f r e e ) 算法和新的可 摘要 行的序列线性方秘f l ( s s l e ) 算法解非线性不等式约束优化问题，能够在较弱的 条件下得到新算法的收敛性。新的算法是可执行的，并且不需假定聚点的孤立 性、严格互补条件和积极约束函数的梯度的线性独立性得到全局收敛性。其中 由拟牛顿方法得到的子矩阵不需要假设是一致正定的。并且在一些弱条件下得 到新算法的超线性收敛率。 ( 2 ) 在 6 4 ，1 0 5 的q p f r e e 方法都利用f i s c h e r - b u r m e i s t e r 非线性互补 ( n c p ) 函数求解非线性不等式约束优化问题、变分不等式问题。然 而，f i s c h e r - b u r m e i s t e r 函数是无理的。这使得原来的线性的项通过f i s c h e r - b u r m e i s t e r 函数转化后为非线性的。为了克月艮f i s c h e r - b u r m e i s t e r 函数的缺点，提 出两个新的非线性互补( n c p ) 函数：分片、线性有理的非线性互补( n c p ) 函数和光滑化的f i s h e r - b u r m e i s t e r 函数。通过这两个函数构造新的可行的q p f r e e 算法求解非线性不等式约束优化问题、变分不等式问题。结合论文的第一部 分研究方法，新的算法能够在较弱的条件下得到收敛性。这些新的算法都是可 执行的，并且不需假定聚点的孤立性、严格互补条件和积极约束函数的梯度的 线性独立性得到算法的全局收敛性。其中由拟牛顿法修正得到的子矩阵不需假 设是一致正定的。 ( 3 ) 已有的无二次子规戈t j ( q p f r e e ) 算法都要求所有的迭代在可行域内部。 然而当接近可行域的边界时，步长会很小，而且要花很多的计算来避免m a r a t o r s 效应。为了克服这些缺点，提出新的不可行的q p f r e e 算法解非线性不等式约束 优化问题，新的算法分别采用论文的第二部分提出的新的分片、线性有理的 非线性互补函数和光滑化的f i s h e r - b u r m e i s t e r 函数。新算法中，定义一个价值函 数，这个函数与目标函数、乘自函数和新的非线性互补函数有关。在每步迭 代，使这个价值函数下降。这些新的算法都是可执行的，并且不需假定聚点的 孤立性、严格互补条件和积极约束函数的梯度的线性独立性得到算法的全局收 敛性。并且在一些弱条件下得到算法的超线性收敛率。 ( 4 ) 在 3 3 中，ef a c c h i n e i 和c l a z z a r i 对不等式约束s c l 函数最小化问题 提出了一个q p f r e e 算法。但是这个算法是局部可行的。结合 1 3 3 】中的算法 思想，提出了一个新的可行的序列线性方程组( s s l e ) 的算法解不等式约 束s c l 函数最小化问题。不需假定聚点的孤立性和严格互补条件，就能证明算 法产生的迭代点序列全局收敛到s c l 函数最小化问题的k k t 点。在一些弱的条 件下证明算法的超线性收敛性。 一i i 摘要 关键词：非线性不等式约束优化问题，变分不等式问题，q p f r e e 算法，全局收 敛性，超线性收敛性 i i i ，。 a b s 仃a c t a b s t r a c t t h en o n l i n e a r l 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 ( n l p ) i sa ni m p o r t a n tr e s e a r c h t o p i ci nm a t h e m a t i c a lp r o g r a m m i n gf i e l d s m a n yp r a c t i c a lp r o b l e m sc a nb em o d e l l e d a st h ec o n s t r a i n e dn o n l i n e a ro p t i m i z a t i o np r o b l e m s s i n c et h el a t e19 7 0 s ，t h es e q u e n t i a l q u a d r a t i cp r o g r a m m i n g ( s q p ) m e t h o dh a sb e c o m eo n eo ft h em o s te f f e c t i v em e t h o d s f o rs o l v i n gn o n l i n e a r l 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 th a sr e c e i v e dm u c ha t t e n t i o ni nt h er e c e n ty e a r s b yc h o o s i n ga p p r o p r i a t e l yaq u a d r a t i cs u b p r o b l e m ，t h es q p m e t h o dc a l lb ev i e w e da st h en a t u r a le x t e n s i o no fn e w t o na n dq u a s i - n e w t o nm e t h o d s f r o mt h eu n c o n s t r a i n e dt ot h ec o n s t r a i n e do p t i m i z a t i o n t h u st h es q pm e t h o de n j o y s t h ec h a r a c t e r i s t i c so fn e w t o n l i k em e t h o d s ：s o m er a p i dc o n v e r g e n c ew i l lb eo b t a i n e d w h e nt h ei t e r a t e sa r ec l o s et ot h es o l u t i o n ，b u tt h e r ew i l lb ep o s s i b l ee r r a t i cb e h a v i o r w h e nt h ei t e r a t i o np o i n t sa r ef a rf r o mt h es o l u t i o n h o w e v e r , s q pa l g o r i t h m sf o rt h e s o l u t i o no fp r o b l e m ( n l p ) s h a r eac o m m o nf e a t u r e ：o n em u s ts o l v ea ni n e q u a l i t yc o n s t r a i n e dq u a d r a t i cp r o g r a m m i n gp r o b l e ma te a c hi t e r a t i o n t h ec o m p u t a t i o na m o u n to f a l g o r i t h m si sv e r yl a r g e s oi ti sd e s i r a b l et od e s i g na l g o r i t h m sw h i c ho n l yr e q u i r et h e s o l u t i o no fl i n e a rs y s t e m s w ea r ei n t e r e s t e di nm e t h o d st h a td on o ti n v o l v et h es o l u t i o n o fq u a d r a t i cp r o g r a m s t h e s em e t h o d sa r eu s u a l l yc a l l e dq p - f r e ea l g o r i t h m s t h i st h e s i sf o c u s e so ns o m eu n s o l v e dp r o b l e m si nq p - f r e ea l g o r i t h m s ，a n di m p r o v e st h ec o m p u t a t i o ne f f i c i e n c yo ft h e s em e t h o d s i ti n c l u d e st h ef o l l o w i n ga s p e c t s ： ( 1 ) t h ee x i s t i n gq p - f r e ea l g o r i t h m s ，f o rt h eg l o b a lc o n v e r g e n c e ，s t i l lu s e ds o m e s t r o n g e rc o n d i t i o n s o n ei st h el i n e a ri n d e p e n d e n c eo ft h eg r a d i e n t so fa c t i v ec o n s t r a i n e df u n c t i o n sa tt h es o l u t i o n ；a n o t h e ri st h eu n i f o r m l yp o s i t i v ed e f i n i t eo fm a t r i x h 七w h i c hi so b t a i n e db yt h eq u a s i n e w t o nu p d a t e ，b u tw ec a nn o te n s u r et h a tm a t r i x h 七i su n i f o r m l yp o s i t i v ed e f i n i t ef o rg e n e r a lf u n c t i o n ，( z ) w ep r o p o s ean e wf e a s i b l e q p f r e ea l g o r i t h ma n da n e wf e a s i b l es e q u e n t i a ls y s t e mo fl i n e a re q u a t i o n s ( s s l e ) a l g o r i t h mt oo b t a i nt h el o c a lc o n v e r g e n c eu n d e rs o m ew e a k e rc o n d i t i o n s i np a r t i c u l a r , t h ea l g o r i t h m sa r ei m p l e m e n t a b l ea n dg l o b a l l yc o n v e r g e n tw i t h o u ta s s u m i n gt h a tt h e i s o l a t e d n e s so ft h ea c c u m u l a t i o np o i n t ，t h es t r i c tc o m p l e m e n t a r i t yc o n d i t i o na n dt h e l i n e a ri n d e p e n d e n c eo ft h eg r a d i e n t so fa c t i v ec o n s t r a i n e df u n c t i o n s t h es u b m a t r i x ， w h i c hm a yb eo b t a i n e db yt h en e w t o no rq u a s i - n e w t o nm e t h o d s ，d on o tb er e q u e s t e d 一一 a b s t r a c t u n i f o r m l yp o s i t i v ed e f i n i t e w ea l s op r o v et h a tt h ea l g o r i t h m sh a v et h es u p e r l i n e a r c o n v e r g e n c er a t eu n d e rs o m em i l dc o n d i t i o n s ( 2 ) i l l 【6 4 ，1 0 5 ，f e a s i b l eq p - f r e ea l g o r i t h m sw e r ep r o p o s e df o rs o l v i n gi n e 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 sa n dv a r i a t i o n a li n e q u a l i t yp r o b l e m sb yu s i n gt h e f i s c h e r - b u r m e i s t e rf u n c t i o n s h o w e v e r , t h ef i s c h e r - b u r m e i s t e rf u n c t i o ni si r r a t i o n a l t h i sm a k e ss o m eo r i g i n a l l yl i n e a rt e r m sb e c o m en o n l i n e a ra f t e rt h er e f o r m u l a t i o nb y u s i n gt h ef i s c h e r - b u r m e i s t e rf u n c t i o n s b yt h en e wp i e c e w i s el i n e a r - r a t i o n a ln c p f u n c t i o n so rs m o o t h e df i s h e r - b u r m e i s t e rf u n c t i o n s ，w ep r o p o s en e wf e a s i b l eq p f r e e a l g o r i t h m sf o rs o l v i n gi n e 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 sa n dv a r i a t i o n a l i n e q u a l i t yp r o b l e m s b yu s i n gt h ef i r s tp a r tm e t h o d so f t h i st h e s i s ，t h em e t h o d sa r ei m p l e m e n t a b l ea n dg l o b a l l yc o n v e r g e n tw i t h o u ta s s u m i n gt h a tt h es t r i c tc o m p l e m e n t a r i t y c o n d i t i o n ，t h ei s o l a t e d n e s so f t h ea c c u m u l a t i o np o i n ta n dt h el i n e a ri n d e p e n d e n c eo f t h e g r a d i e n t so f a c t i v ec o n s t r a i n e df u n c t i o n s t h es u b m a t r i x ，w h i c hm a yb eo b t a i n e db yt h e n e w t o no rq u a s i - n e w t o nm e t h o d s ，i sn o tr e q u e s t e dt ob eu n i f o r m l yp o s i t i v ed e f i n i t e ( 3 ) t h ee x i s t i n gq p f r e ea l g o r i t h m sa r ef e a s i b l em e t h o d s s o m e t i m e s h o w - e v e lt h es e a r c hs t e p sm a yb et o os h o r tn e a rt h eb o u n d a r yo f t h ef e a s i b l es e t ，a n dt h e r e i sm u c hm o r ec o m p u t i n gf o ra v o i d i n gt h em a r a t o r se f f e c ti nt h ef e a s i b l em e t h o d t o o v e r c o m et h i ss h o r t c o m i n g ，w ep r o p o s ei l e wq p - f r e ei n f e a s i b l ea l g o r i t h m sf o rs o l v i n gi n e 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 ，b yt h en e wp i e c e w i s el i n e a r - r a t i o n a l n c pf u n c t i o n sa n ds m o o t h e df i s h e r - b u r m e i s t e rf u n c t i o n s i np a r t i c u l a r , w ed e f i n ea m e r i tf u n c t i o nw h i c hi sr e l a t e dt ot h eo b j e c t i v ef u n c t i o n ，t h em u l t i p l i e rf u n c t i o na n dt h e n e wf u n c t i o n s t h e nw em a k et h em e r i tf u n c t i o nd e c r e a s i n ga te a c hi t e r a t i o n t h e s e a l g o r i t h m sa r ei m p l e m e n t a b l ea n dg l o b a l l yc o n v e r g e n tw i t h o u ta s s u m i n gt h es t r i c tc o m o p l e m e n t a r i t yc o n d i t i o n ，i s o l a t e d n e s so ft h ea c c u m u l a t i o np o i n ta n dl i n e a ri n d e p e n d e n c e o ft h eg r a d i e n t so fa c t i v ec o n s t r a i n e df u n c t i o n sa tt h es o l u t i o n w ea l s op r o v et h a tt h e a l g o r i t h m sh a v es u p e r l i n e a rc o n v e r g e n c er a t eu n d e rs o m em i l dc o n d i t i o n s ( 4 ) i n 3 3 ，aq p f r e ea l g o r i t h mw a sp r o p o s e df o rm i n i m i z i n ga ns c lf u n c t i o n s u b j e c tt oi n e q u a l i t yc o n s t r a i n t s b u tt h i sm e t h o di sl o c a lf e a s i b l e w ep r o p o s eaf e a - s i b l es e q u e n t i a ls y s t e mo fl i n e a re q u a t i o n sa l g o r i t h mf o rt h ep r o b l e mo f m i n i m i z i n ga l l s c lf u n c t i o ns u b j e c tt oi n e q u a l i t yc o n s t r a i n t s w i t h o u ta s s u m i n gi s o l a t e d n e s so ft h e s t a t i o n a r yp o i n t s ，w ep r o v et h a tt h es e q u e n c eg e n e r a t e db yt h ep r o p o s e da l g o r i t h mc o n v e r g e n c et oak k tp o i n to ft h ep r o b l e mg l o b a l l y u n d e rs o m ea d d i t i o n a lc o n d i t i o n s ， 一v 一 a b s t r a c t w es h o wt h a tt h ec o n v e r g e n c er a t ei ss u p e r l i n e a r k e yw o r d s ：n o n l i n e a ri n e 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 ，v a r i a t i o n a li n - e q u a l i t yp r o b l e m s ，q p f r e ea l g o r i t h m ，g l o b a lc o n v e r g e n c e ，s u p e r l i n e a rc o n v e r g e n c e 一一 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：倒爹 j 口 2 0 口乡年夕月“日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：澎三、虱 学位论文作者签名：) 虱痞 z 。u 年尸月“日 2 口。芗年夕月2 日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均己在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 签名： _ o s 肆 同杰 夕月2 名日 第一章引言 第一章引言 1 1q p f r e e 算法的产生和发展 非线性不等式约束优化问题( n l p ) r a i n 厂( z ) ， s t c ( x ) 0 ， ( 1 1 ) 其中目标函数厂( z ) ：形_ r ，约束函数g = ( g l ，9 2 ，) t ：形一胛都是 连续可微函数，而且目标函数和约束函数中至少有一个是变量z 的非线性函数。 用 d = z r 1 i g ( x ) o ) 和 d = c l ( d ) = z r “i c ( x ) o 】- 分别表示问题( n l p ) 的严格可行集和可行集。 问题( n l p ) 的l a n g r a n g e 函数定义为 l ( x ，入) = ，( z ) + 入t g ( z ) ( 1 2 ) 其中a = ( 入1 ，a 2 ，a 。) t 舻是l a n g r a n g e 乘子向量。为了简便，用( z ，a ) 表 示列向量( 护，妒) t 。1 9 5 1 年，k u h n s n t u c k e ：给t k u h n - t u c k e r 定理，它是解决 约束优化的最优性条件。 点对( z ，a + ) r 似m 称作问题( n l p ) 一个k k t 点或者k k t 对，如果它满足 下面的条件： v 。( z + ，a + ) = 0 ，9 ( z + ) 0 ，a + 0 ，9 t ( z ) a ：= 0 ，vi i ， ( 1 3 ) 其中，i ：= 1 ，m ) 和 v 。l ( z ，a ) ：= v f ( x ) + 銎1 九v 仇( z ) 第一章引言 有时，也称满足条件( 1 3 ) 的点z + 为问题( n l p ) 一个k k t 点。如果( 矿，a ) 满 足( 1 3 ) 中的所有条件，除了不等式 0 ，称点矿为问题( n l p ) 一个稳定点。 自二十世纪七十年代后期，序列二次规划方法( s q p ) 已经成为解非线性最优 化问题的一种最常见、最有效的方法。最近几十年，在这类方法上已作了很多 的研究，关于s q p 方法的综述见 1 。 s q p 方法的迭代过程如下。设z 七为当前的迭代点。通过解下面的二次规划 子问题( q p ) 计算搜索方向扩： 僻min艄l(d,h+kd()+(vf(xktv g i ( xd ) 曼0 ：vi i ( 1 4 ) ls 吼( z 七) + ( 七) ，) ，v 、 其中h k 形肌是对称正定的。通过一维最小化问题决定步长t k ，则下一步迭 代为z 七+ 1 = z 七+ t k d 七。 通过选择合适的二次规划子问题，s q p 方法可以看作是牛顿方法和拟牛顿 方法从无约束优化到约束优化的扩展。因此，s q p 方法有牛顿类方法的很多特 点：当接近解时有很好的收敛性，但是当迭代点远离问题的解时有可能会出现 不稳定的现象。 然而，多数的s q p 方法有两个严重的缺点：( 1 ) 为了得到搜索方向，每步迭 代必须解一个或者多个二次规划子问题，一般来讲，计算量很大。另外，在解 二次规划子问题时，很难应用矩阵的稀疏性和对称性，这限制t s q p 方法的应 用，特别是对于大规模问题的应用；( 2 ) s q p 方法要求相应的二次规划子问题 必须在每步迭代有解，然而，一般来说这是很难满足的。即使有解也不一定是 可行的。因此，需要提出一些新的算法，在解非线性优化问题时能避免这些缺 点。 为了克服这些缺点，已提出了一些好的方法，见【6 ，6 8 ，7 9 ，9 2 ，1 2 2 1 。在 7 9 ，p a n i e r 和t i t s 提出可行的s q p ( f s q p ) 算法，产生的迭代都在可行域西中， 这类f s q p 方法是全局收敛的且局部二步超线性收敛。关于f s q p 算法的进一步 研究见 8 1 。f s q p 方法对于解一些经济问题特别有用，这些经济问题的目标函 数在可行域d 外没有定义。 然而，f s q p 算法仍要求在每步迭代解二次规划子问题，其计算量很大。 在 8 0 】，p a n i e r ，t i t s 和h e r s k o v i t s 提出一个可行的无二次规划子规划( q p f r e e ) 算法解非线性不等式约束优化问题。通过解线性方程组的问题代替了解二 次规划子问题，来计算搜索方向扩，因此克服t s q p 方法的缺点。在 8 0 中， 算法在每步迭代只需解两个线性方程组和一个最小二乘问题，这样大大的节省 一2 一 第一章引言 了计算量，而且能够求得非线性不等式约束优化问题的解。 q p f r e e 算法的迭代步骤如下。让( ，舻) 为当前迭代。为了确保下步迭代 的可行性，通过选择两个不同的向量c 舻，先解有下面形式的两个线性方程 组： ，、，、 7 a ) v k 夕( z 南) t v9z七：)(ad)=(一vfdiag(#diag(g(xc z 岛) ( 1 5 ) ) v 夕( z 南) t ) ) a c 、。7 其中h o 舻n 是正定的，矿胪是乘子向量的当前估计。d i a g ( # 血) 表示m m 对角矩阵，其第i 个对角元素是p ? 。为了避免m a r a t o s 效应，然后通过解一 个最d x - - 乘问题进一步“弯曲”搜索方向。在 8 0 ，已经证明，在一些条件 下，这个q p f l e e 算法全局收敛且局部二步超线性收敛。但是，这个q p f r e e 算 法存在些问题。当一些积极约束函数仇对应的乘子u l 变得很小时，线性方程 组( 1 5 ) 可能变得“病“条件。另外，在全局收敛定理中，需要一个较强的条 件：稳定点是有限的。 通过f i s c h e r - b u r m e i s t e r 非线性互补( n c p ) 函数，在【1 0 5 h q i 和l q i 提 出了一个可行的q p f r e e 算法解非线性不等式约束优化问题。在每步迭代，通过 选择三个不同的向量c 胛，解三个下面形式的线性方程组： ( d i 口9 。叼七n ，v kg。z七，tv夕(z七)知，)(妥)(一vfvf2diag(oc ( z 七) c - 6 ， d i 口9 ( 7 7 七) v g ( z 七) t 一知) a c 、1 。7 其中对每个i i ， 前= 丽筹丽“ 畿= ( 1 一 为了避免m a r a t o s 效应，该算法也需解一个最小二乘子问题。这个算法保留 了 8 0 】中的算法的优点。而且即使严格互补条件不成立，( 1 6 ) 中的系数矩阵仍 然是非奇异的。这个算法不需要假定稳定点是有限的和严格互补条件，就得到 了算法全局收敛性，并且在一定条件下得到一步超线性收敛性。 由于非线性互补问题的发展，在 6 4 ，c k a n z o w 和h q i 通过f i s c h e r 。 b u r m e i s t e r 非线性互补( n c p ) 函数得至i j q p f r e e 算法解变分不等式问题。其数 值结果说日f j q p f l e e 算法解变分不等式问题也是有效的方法。 在【1 3 3 中，y y a n g ，d l i 和l q i 提出另一类q p - f r e e 算法，也可称为序列 线性方程组( s s l e ) 算法解非线性不等式约束优化问题。在每步迭代，只需解 一3 一 第一章引言 四个简化的且具有相同系数矩阵的线性方程组来求搜索方向。算法中，只考 虑在工作集小j 内的约束函数，而不在工作集中的约束不考虑。因此， 子问题不是满秩的。这个工作集，它是积极集z o ( x 知) 的估计。如果充分地接 近k k t 点z + ，那么小就是积极集z o ( x 七) 。这个对积极集的估计的方法已经做了 很多研究，见 2 7 ，2 9 ，1 2 2 】。 在 3 3 ，f f a c c h i n e i 和c l a z z a r i 提出一个局部可行的q p f r e e 算法解不等 式约束的s c l 函数最小化问题。这个算法不同于已有的同类算法，因为不要求 目标函数是二次连续可微的，且在收敛性的证明不需严格互补条件。 虽然有很多的作者对q p f r e e 算法进行研究，但是仍然存在很多的问题。 本学位论文主要构造新的无二次子规划( q p f r e e ) 算法求解非线性不等式约 束优化问题、变分不等式问题，以及对这类方法进一步的研究，包括对非线性 互补( n c p ) 函数的及其与算法的收敛性和收敛率的关系研究；构造以牛顿法 和拟牛顿法为核心的新算法，以及对这些算法在”弱”的假设条件下的可行性、 稳定性、全局收敛性和收敛率的分析，不但对解非线性不等式约束优化问题、 变分不等式的数值解问题提供了有效方法，并且可以把这些思想和技巧扩展应 用到其他一些非线性规划的方法，取到更好的成果。研究的内容和方法主要包 括如下几个方面： ( 1 ) 在【1 0 5 】h q i 和l q i 提出了一个可行的q p f r e e 算法解非线性不等式 约束优化问题。在 1 3 3 】中，y y a n g ，d l i 和l q i 提出另一类q p f r e e 方法，也 可称为序列线性方程组( s s l e ) 算法解非线性不等式约束优化问题。但在算法的 全局收敛性的证明中，仍需要一些较强的假设条件。一是假设在解处的积极约 束函数的梯度是线性独立的；另一个是假设由拟牛顿方法修正得到的矩阵日的 一致正定性，但是，对于一般的函数f ( x ) ，不能确保矩阵日七的一致正定性。为 了克服这些缺点，提出新的可行的无二次子规划( q p f r e e ) 算法和新的可行的序 列线性方程组( s s l e ) 算法解非线性不等式约束优化问题，能够在较弱的条件下 得到新算法的收敛性。新的算法是可执行的，并且不需假定聚点的孤立性、严 格互补条件和积极约束函数的梯度的线性独立性得到全局收敛性。其中由拟牛 顿方法得到的子矩阵不需要假设是一致正定的。并且在一些弱条件下证明得到 新算法的超线性收敛率。 ( 2 ) 在 6 4 ，1 0 5 中的q p f r e e 方法都利用f i s c h e r - b u r m e i s t e r 非线性互补 ( n c p ) 函数求解非线性不等式约束优化问题、变分不等式问题。然 而，f i s c h e r - b u r m e i s t e r 函数是无理的。这使得原来的线性的项通过f i s c h e r - b u r m e i s t e r 函数转化后为非线性的。为了克, q 艮f i s c h e r - b u r m e i s t e r 函数的缺点，提 出两个新的非线性互补( n c p ) 函数：分片、线性有理的非线性互补( n c p ) 一4 一 第一章引言 函数和光滑化的f i s h e r - b u r m e i s t e r 函数。通过这两个函数构造新的可行的q p f r e e 算法求解非线性不等式约束优化问题、变分不等式问题。结合论文的第一部 分研究方法，新的算法能够在较弱的条件下得到收敛性。这些新的算法都是可 执行的，并且不需假定聚点的孤立性、严格互补条件和积极约束函数的梯度的 线性独立性得到算法的全局收敛性。其中由拟牛顿法修正得到的子矩阵不需假 设是致正定的。并且在一些弱条件下得到算法的超线性收敛率。 ( 3 ) 已有的无二次子规划( q p f r e e ) 算法都要求所有的迭代在可行域内部。 然而当接近可行域的边晃时，步长会很小，而且要花很多的计算来避免m a r a t o r s 效应。为了克服这些缺点，提出新的不可行的q p f r e e 算法解非线性不等式约束 优化问题，算法中采用论文的第二部分提出的新的分片、线性有理的非线性互 补函数和光滑化的f i s h e r - b u r m e i s t e r 函数。新算法中，定义一个价值函数，这个 函数与目标函数、乘自函数和新的非线性互补函数有关。在每步迭代，使这个 价值函数下降。这些新的算法都是可执行的，并且不需假定聚点的孤立性、严 格互补条件和积极约束函数的梯度的线性独立性得到算法的全局收敛性。并且 在一些弱条件下得到算法的超线性收敛率。 ( 4 ) 在 3 3 q h ，ef a c c h i n e i 和c l a z z a r i 对不等式约束s c l 函数最小化问 题提出了一个q p f r e e 算法。但是这个算法是局部可行的。结合【1 3 3 中的算 法思想，提出了一个新的可行的序列线性方程组( s s l e ) 的算法解不等式约 束s c l 函数最小化问题。不需假定聚点的孤立性和严格互补条件，就能证明算 法产生的迭代点序列全局收敛到s c l 函数最小化问题的k k t 点。在一些弱的条 件下证明算法的超线性收敛性。 本论文结构安排如下： 在第一章给出- j q p f r e e 算法的产生和发展，以及相关的知识；在第二章 提出新的可行的无二次子规戈l j ( q p f r e e ) 算法求解非线性不等式约束优化问题， 能够在弱的假设条件下，得到算法的收敛性；在第三章提出新的分片、线性有 理的非线性互补函数和光滑化的f i s h e r - b u r m e i s t e r 函数，来构造新的可行的q p f r e e 方法求解非线性不等式约束优化问题、变分不等式问题；在第四章提出新的 不可行的无二次子规划( q p - f r e e ) 算法求解非线性不等式约束优化问题，算法中 采用新的分片、线性有理的非线性互补函数和光滑化的f i s h e r - b u r m e i s t e r 函数： 在第五章提出一个新的可行的序列线性方程组( s s l e ) 算法解不等式约束s c l 函 数最小化问题。在第六章对论文进行总结。 论文中出现的符号：n 维e u c l i d e a n 空间，用钟表示。忙l i 为向量z 冗”的e u c l i d e a n 范数。两个向量z ，可形的数乘记做z 丁秒。不等式z 0 说明 向量z 舻的所有的分量都是非负的。函数f ：衍一形称作c 知函数，如果 一5 一 第一章引言 它是k 次连续可微。函数f ：舻一形称作l c 缸函数，如果它是伊函数使得 其第k 次导数是几乎处处局部l i p s c