（计算数学专业论文）变分不等式问题的仿射内点信赖域方法和应用.pdf

中文摘要 摘要 变分不等式问题起源于数学物理问题和非线性规划。长期以来，变分不等式问题已 被广泛应用于构建和研究金融学、运筹学、交通规划及区域科学等领域产生的各种均衡 模型。因其在数学规划研究中的重要作用，变分不等式问题的有效求解正成为当今变分 不等式问题研究的重要方面。由于对变分不等式问题直接进行求解难度很大，许多研究 工作者设想了很多间接求解变分不等式问题的方法，其中最重要的分支之一是将其转化 为等价的( 无) 约束优化问题，以便于运用成熟的最优化方法得以解决。 非线性( 无) 约束的最优化理论与方法的研究，由整体收敛性和局部收敛速率两部分构 成，其中线搜索技术与信赖域策略是保证算法的整体收敛性的两个重要手段。同时，伴 随着计算机的发展和软件的完善，最优化问题的数值求解正变得越来越实际可行。 本文主要针对有界约束、线性约束、非线性约束及一般凸约束的单调变分不等式问 题，引入f u k u s h i m a 及p e n g 介绍的各种势函数，将变分不等式问题转化为等价的( 无) 约 束优化问题，提出了各类结合非单调线搜索技术的仿射变换内点信赖域方法。 在构造约束优化问题的信赖域子问题过程中，本文通过引入一些仿射矩阵技巧性克 服了有界约束、线性等式和不等式约束带来的困难，构建了近似二次函数和具有常用的 椭球约束信赖域子问题。解此子问题即得可行的迭代方向，通过非单调线搜索获得下一 迭代点并可保证目标函数有足够下降量。在合理的假设条件下，所给出的这类算法具有 整体收敛性和局部二次收敛速率。 最优路径法及修正梯度路径法是解无约束优化问题时的常用方法，由于具有构造简 便，易于编程计算等优点，这些弧线路径法已经成为求解大规模问题的一种重要方法。 在本文中，通过引入仿射变化矩阵，构造了约束优化问题的仿射变换最优路径。沿着最 优路径搜索得到迭代方向，当该迭代方向步不严格可行时，利用线搜索技术得到可接受 的步长因子，并且此步长因子保证了新的迭代点有足够的下降量并且位于可行域的内 部。由于最优路径是通过信赖域问题得到的，因此具有非常良好的性质。文章证明了最 优路径仿射内点算法具有整体收敛性和局部二次收敛速率。 另外，基于变分不等式问题的无约束优化问题( 1 e n g ) 的势函数，将线性约束变分不 等式问题转化为等价的约束优化问题，提供了结合非单调线搜索技术的仿射变换内点修 正梯度路径方法。考虑将信赖域子问题中的信赖域约束去掉，沿着修正梯度路径搜索并 结合回代线搜索技术，可以近似的求解信赖域子问题。文中证明了在合理的假设条件之 下，算法具有整体收敛性。若在算法中引入线性化变分不等式问题，同样可得局部超线 性收敛速率。 投影梯度法是解决凸约束最优化问题的一类有意义的方法，本文中对于凸约束的单 第1 页 上海师范大学博士学位论文 调变分不等式问题产生的信赖域子问题，采用近似投影梯度算法对其进行求解，既避免 了反复求解信赖域子问题，又保证了算法具有整体收敛性和局部二次收敛速率。算法的 数值结果表明了有效性和可行性。 变分不等式问题和最优化问题与k k t 系统之间具有紧密的联系，特别是一般的非线 性约束变分不等式问题可以转化为k k t 系统。本文一方面考虑对非线性约束变分不等 式问题的k k t 条件进行重构，转化为等价的约束优化问题，提供了仿射内点信赖域方 法进行求解。另一方面对一般的k k t 系统进行研究，给出了求解k k t 系统的仿射内点 l e v e n b e r g m a r q u a r d t ( l 广m ) 方法。将k k t 系统转化为等价的非负约束优化问题，然后使 用l - m 方法求解该约束优化问题。在合理的假设条件下，证明了这两类算法的整体收敛 性及超线性收敛速率。 最后本文对所做的研究工作进行总结，特别是创新点小结，并提出了进一步的研究 方向。 关键词：变分不等式问题；仿射变换：内点法：信赖域策略：非单调技术；曲线路径； 投影梯度；整体收敛性；局部收敛速率。 第页 英文摘要 ab s t r a c t 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 ma r i s e sf r o mm a t h e m a t i c a l p h y s i c sp r o b l e m sa n d n o u l i n e a rp r o - g r a m m i n g i th a sb e e nw i d e l yu s e dt of o r m u l a t ea n ds t u d yv a r i o u se q u i l i b r i u mm o d e l sa r i s i n gi n e c o n o m i c s ，o p e r a t i o n sr e s e a r c h ，t r a n s p o r t a t i o np r o b l e m sa n dr e g i o n a ls c i e n c e sf o ral o n gt i m e t h ee f f e c t i v es o l u t i o nf o rv a r i a t i o n a li n e q u a l i t yp r o b l e mi sb e c o m i n gam a i nf i e l do fa p p r o a c h e s f o rv a r i a t i o n a li n e q u a l i t yp r o b l e mb e c a u s ei tp 量a y sa ni m p o r t a n tr o l ei nm a t h e m a t i c a lp r o g r a m - m i n g s i n c ei ti sr a t h e rd i f f i c u l tt os o l v ev a r i a t i o n a li n e q u a l i t yp r o b l e md i r e c t l y , m a n yi n d i r e c t m e t h o d sh a v e b e e nd e v e l o p e d , i nw h i c ho n ei m p o r t a n tb r a n c hi st r a n s f o r m i n gv a r i a t i o n a li n e q u a l i t yp r o b l e mi n t oe q u i v a l e n t ( u n ) e 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 t h es t u d yo ft h e o r ya n dm e t h o d so fn o n l i n e a r ( t i n ) c o n s t r a i n e do p t i m i z a t i o ni sc o m p o s e do f t w op a r t s ，i e ，g l o b a lc o n v e r g e n c ea n dl o c a lc o n v e r g e n tr a t e b o t hl i n es e a r c ht e c h n i q u ea n d t r u s tr e g i o ns t r a t e g ya r ew e l l a c c e p t e dm e t h o d si nt h eo p t i m i z a t i o ni no r d e rt oa s s u r eg l o b a lc o n = v e r g e n c e a tt h es a m et i m e ，a c c o m p a n yw i t ht h ed e v e l o p m e n to fc o m p u t e ra n dt h ep e r f e c to f s o f t w a r e ，n u m e r i c a le x p e r i m e n t so fo p t i m i z a t i o np r o b l e m sa r eb e c o m i n gm o r ea n dm o r ef e a s i b l e a n de f f e c t i v e t h i st h e s i si sd e v o t e dt os t u d y i n gs y s t e m a t i c a l l yt h ea l g o r i t h m so fm o n o t o n ev 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 , i n c l u d i n g 埘t l lb o xc o n s t r a i n t s ，l i n e a rc o n s t r a i n t s ，n o n l i n e a rc o n s t r a i n t sa n d g e n e r a lc o n v e xc o n s t r a i n t s b ye m p l o y i n gv a r i o u sm e r i tf u n c t i o n si n t r o d u c e db yf u k u s h i m aa n d p e n ge ta 1 ，w et r a n s f o r mv a r i a t i o n a li n e q u a l i t yp r o b l e mi n t oe q u i v a l e n t ( u n ) 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 sa n dt h e np r o p o s es e v e r a le f f i c i e n ta f f i n es c a l i n gi n t e r i o rt r u s tr e g i o na l g o r i t h m sw i t h n o n m o n o t o n i cl i n es e a r c ht e c h n i q u ef o rs o l v i n go p t i m i z a t i o np r o b l e m s b yi n t r o d u c i n ga f f i n es c a l i n gm a t r i c e si nt h ep r o c e s so ff o r m u l a t i n gt r u s tr e g i o ns u b p r o b l e m ， w ew i l lt e c h n i c a l l yo v e r c o m ed i 师c u l t i e si m p o s e d b yb o xc o n s t r a i n t s ，l i n e a re q u a l i t ya n di n e q u a l i t yc o n s t r a i n t s t h e nw ef o r m u l a t ea l la p p r o p r i a t eq u a d r a t i cf u n c t i o na n dt r u s tr e g i o ns u b p r o b l e m o n l yw i t hg e n e r a le l l i p t i cc o n s t r a i n t s af e a s i b l ed i r e c t i o ni so b t a i n e db ys o l v i n gt r u s tr e g i o ns u b - p r o b l e ma n df u r t h e ran e wa c c e p t e di t e r a t i v es t e pc a l lb eo b t a i n e db yn o n m o n o t o n i cl i n es e a r c h t e c h n i q u eb e c a u s es u f f i c i e n td e c r e a s eo ft h eo b j e c t i v ef u n c t i o nv a l u e sc a nb eg u a r a n t e e d f u r t h e r - m o r e ，t h eg l o b a lc o n v e r g e n c ea n dl o c a lq u a d r a t i cc o n v e r g e n tr a t eo ft h ep r o p o s e da l g o r i t h ma l e e s t a b l i s h e du 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 b o t ho p t i m a lp a t hm e t h o da n dm o d i f i e dg r a d i e n tc u r v i l i n e a rt e c h n i q u ea r et h em o s tp o p u l a r m e t h o d si nu n c o n s t r a i n e do p t i m i z a t i o n b e c a u s ei ti sc o n v e n i e n tt oc o n s t r u c tt h e s ep a t h sa n di tc a n b ee a s i l yp r o g r a m m e da n dc o m p u t e d ，t h e s ec u r v i l i n e a rp a t ht e c h n i q u e sh a v eb e c o m ei m p o r t a n t 第1 页 上海师范大学博士学位论文 m e t h o d sf o rs o l v i n gl a r g e - s c a l eo p t i m i z a t i o np r o b l e m s i nt h i st h e s i s ，w ei n t r o d u c et h ea f f i n e s c a l i n gm a t r i xt og e n e r a t ea na f f i n es c a l i n go p t i m a lp a t ho fo p t i m i z a t i o np r o b l e mw i t hl i n e a r e q u a l i t ya n di n e q u a l i t yc o n s t r a i n t s e m p l o y i n gb o t ht h ea f f i n es c a l i n go p t i m a lp a t hs e a r c hs t r a t e g y a n dl i n es e a r c ht e c h n i q u e ，w ew i l lf i n da l la c c e p t a b l et r i a ls t e pl e n g t ha l o n gt h ei t c r a t i v ed i r e c t i o n w h i c hi ss t r i c t l yf e a s i b l ea n dm a k e st h eo b j e c t i v ef u n c t i o nn o n m o n o t o n i c a l l yd e c r e a s i n g s i n c e o p t i m a lp a t hi sc o n s t r u c t e df r o mt r u s tr e g i o ns u b p r o b l e m , i th a sg o o dc o n v e r g e n tp r o p e r t i e s h e m ， w es h o wt h a tt h ep r o p o s e da l g o r i t h mn o to n l yh a st h eg l o b a lc o n v e r g e n c e ，b u ta l s oh a sl o c a l q u a d r a t i cc o n v e r g e n tr a t e b a s i n go nt h em e r i tf u n c t i o na b o u tu n 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 mo fv a r i a t i o n a li n - e q u a l i t yp r o b l e mp r o p o s e db yp e n g 。w er e f o r m u l a t ev a r i a t i o n a li n e q u a l i t yp r o b l e mw i t hl i n e a r i n e q u a l i t yc o n s t r a i n t sa se q u i v a l e n tc 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 w e a l s op r e s e n tm o d i f i e d g r a d i e n tp a t ha n da f f i n es c a l i n gi n t e r i o rm e t h o df o rs o l v i n gm i s tr e g i o ns u b p r o b l e m b ys e a r c h i n g t h es t e pa l o n gt h ep a t hi n s t e a do ft h et r u s tr e g i o ns t r a t e g ya n du s i n gi n t e r i o rb a c k t r a c k i n gl i n e s e a r c ht e c h n i q u e , t h et r u s tr e g i o ns u b p r o b l e mc a l lb ea p p r o x i m a t e l ys o l v e d u n d e rs e i n en ：a s o n a b l ec o n d i t i o n s ，t h eg l o b a lc o n v e r g e n c ei se s t a b l i s h e d f u r t h e r t h ea l g o r i t h ma l s oh a sl o c a l s u p e r t i n e a rc o n v e r g e n c ep r o p e r t yi fl i n e a r i z e dv a r i a t i o n a li n e q u a l i t ys u b p r o b l e mi nt h ea l g o r i t h m i sf l l r t h e rc o n s i d e r e d p r o j e c t e dg r a d i e n ta l g o r i t h mi sak i n do fs i g n i f i c a n tm e t h o df o rs o l v i n gc o n v e xc o n s t r a i n e d o p t i m i z a t i o np r o b l e m w ee m p l o ya p p r o x i m a t ep r o j e c t e dg r a d i e n ta l g o r i t h mf o rt r u s tr e g i o ns u b - p r o b l e mp r o d u c e db ym o n o t o n ev a r i a t i o n a li n e q u a l i t yp r o b l e ms u b j e c tt oc o n v e xc o n s t r a i n t s o n e i m p o r t a n ta d v a n t a g eo ft h i sa l g o r i t h mi st h a tw ec a na v o i ds o l v i n gi p a s tr e g i o ns u b p r o b l e mr e p e a t - e d l y t h e o r e t i c a la n a l y s i sa 他g i v e nw h i c hp r o v et h a tt 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 dh a sal o c a lq u a d r a t i cc o n v e r g e n c er a t eu 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 t h er e s u l t so f n u n 伦r i c a le x p e r i m e n t sa 他r 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 ep r o p o s e da l g o r i t h m i ti sw e l lk n o w nt h a tv 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 , o p t i m i z a t i o np r o b l e ma n dk a r u s h - k u h u - t u c k e r ( k k t ) s y s t e mh a v ec l o s e l yr e l a t i o n s h i p ，s p e c i a l l yg e n e r a ln o n l i n e a rc o n s t r a i n t sv 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 mc a na l s ob et r a n s f o r m e di n t ok k ts y s t e m o nt h eo n eh a n d ，w ec o n s i d e rt o r e f o r m u l a t ek k tc o n d i t i o n so fv a r i a t i o n a li n e q u a l i l ) ，p r o b l e mw i t hn o n l i n e a rc o n s t r a i n t s 器a l l e q u i v a l e n tc 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 ，a n dp r e s e n ta na f f i n es c a l i n gi n t e r i o rt r u s tr e g i o n a l g o r i t h m o nt h eo t h e rh a n d ，w ep r o p o s ea l la f f i n es c a l i n gi n t e r i o rl e v e n b e r g m a r q u a r d t ( l - m ) m e t h o df o rk k t s y s t e m f i r s t l y , w et r a n s f o r mk k ts y s t e mi n t oa ne q u i v a l e n tc 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 mw i t hi t sv a r i a b l et ob en o n n e g a t i v e t h e nw ep r o p o s ea nn o n m o n o t o n i ca f f i n e s c a l i n gl - ma l g o r i t h mw i t hb a c k t r a c k i n gi n t e r i o rp o i n tt e c h n i q u ef o rs o l v i n gt h i so p t i m i z a t i o n p r o b l e m b o t ho ft h et w op r o p o s e da l g o r i t h m sg u a r a n t e eg l o b a lc o n v e r g e n c ea n dp o s s e s sl o c a l 第页 s u p e r l i n e a rc o n v e r g e n tr a t eu n d e r s u i t a b l ec o n d i t i o n s f i n a l l y , w ec o n c l u d et h em a i nn f f o yr e s e a r c hr e s u l t so ft h i st h e s i sa n dp r o p o s es o m ef u r t h e r r e s e a r c hd i r e c t i o na b o u to u rw o r k k e yw o r d 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 ；a f f i n es c a l i n g ；i n t e r i o rp o i n tm e t h o d ；t r u s tr e g i o n s t r a t e g y ；n o n m o n o t o n i ct e c h n i q u e ；c u r v i l i n e a rp a t h ；p r o j e c t e dg r a d i e n t ；g l o b a lc o n v e r g e n c e ； l _ x ) c a lc o n v e r g e n tr a t e 主要符号对照表 主要符号对照表 舻 n 维实向量空间 舻mnx 饥维实矩阵 l | 0 ，i i 1 1 2e u c l i d 范数 | 1 | j g 表示g 范数一 z 住维决策变量 巧向量z 的第歹个分量 文 交分不等式问题的解 v ， 函数，的梯度向量 v f 映射f 的雅可比矩阵 v 2 ，函数，的h e s s i a n 矩阵 s 可行集。 m r ( s )严格可行集 i n f 表示取下确界 表示属于 v 表示任意 ( z ，y )表示向量z 与剪的内积运算 g - 1 表示矩阵g 的逆运算 c o n v ( s ) 表示集合s 的凸包 七信赖域半径 c ( z o ) = z 9 p i ，( z ) ，( z o ) ) 水平集 r ( 下)约束优化问题的仿射最优路径或修正梯度路径 第页 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除了特别 加以标注和致谢的地方外，不包含其他人或机构已经发表或撰写过的研究成果。其他同 志对本研究的启发和所做的贡献均已在论文中做了明确的声明并表示了谢意。 作者签名： 论文使用授权声明 本人完全了解上海师范大学有关保留、使用学位论文的规定，即：学校有权保留送 交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以 采用影印、缩印或其它手段保存论文。保密的论文在解密后遵守此规定。 作者签名：埤导师签名： l 一， 磁 日期：芈 第一章变分不等式问题及最优化理论与方法的基础 第一章变分不等式问题及最优化理论与 方法的基础 1 1变分不等式问题简介 变分不等式起源于数学物理问题和非线性规划，目前已在物理、力学、工程、 经济等领域中得到广泛应用。数学物理中最早的变分不等式出现于2 0 世纪6 0 年代初。 至1 9 6 俾，s t a m p a e c h i a 把l a x m i l g r a m 定理由希尔伯特空间推广到其非空闭凸子集的情 形，得到了变分不等式的第一个解的存在唯一性定理。其后，l i o n s 、l e w y 、b m z i s 等人 发表了一系列文章，为变分不等式理论奠定了初步的基础。2 0 世纪7 0 年代，变分不等式 在最优控制问题、弹性问题及渗流问题等领域中得到了成功的应用。2 0 世纪8 0 年代以 来，作为现代偏微分方程理论重要部分的变分不等式理论得到深入发展，至今已较为成 熟。另一方面，2 0 世纪6 0 年代中期，在非线性规划的研究中出现了线性和非线性互补问 题。它们进一步发展成了有限维空间中的变分不等式。2 0 世纪9 0 年代，数学规划杂志出 版了非线性互补问题与变分不等式的专辑，标志着变分不等式已成为非线性规划的一个 重要领域。 本文考虑有限维变分不等式问题：寻找向量“s ，使得对任意的向量z 5 恒有 ( f ( 巩) ，z z ) 0 ( 1 1 1 ) 成立，其中5 为舻中的一非空闭凸集，f 为从舻到舻的映射，( ，) 表示舻中的内积 运算。该问题也简称为变分不等式问题。特殊的当s = 舰时，变分不等式问题变为下 列非线性互补问题：寻找向量飘5 使得下式成立 z 。0 ，f ( z ) 0 ，f ( z ) 1 z = 0 ( 1 1 2 ) 变分不等式问题的研究大致可分为理论与算法两大方向，理论方面的研究焦点集中 于变分不等式问题的解的存在性、唯一性等；而算法方面主要是研究如何引进和借助有 关技术、概念和思想以设计各种类型的变分不等式问题的具体求解方法。 为了得到变分不等式问题的数值解，许多研究工作者相继提出了很多的迭代算法， 如经典的牛顿类方法、投影方法、雅可比方法等。但是由于对变分不等式问题直接进行 求解难度较大，研究者进一步设想了很多间接求解变分不等式问题的方法，其中最重要 的分支之一便是利用各种势函数将其转化为等价的( 无) 约束优化问题，以便于运用成熟的 最优化理论与方法得以解决。 第1 页 上海师范大学博士学位论文 最优化理论与方法在工程、经济和金融等许多重要领域有着广泛的应用，通常，为 应用最优化技术确定最优的方案，需要针对具体的实际问题建立相应的模型，再根据模 型的具体形式和特性选择适当的优化方法求解。伴随着计算机与软件的高速发展，数值 计算方法的进步和完善，为最优化理论和方法的研究提供了更新的、更有效的手段和发 展前景。非线性( 无) 约束的最优化理论与方法的研究，由整体收敛性和局部收敛速率两部 分构成。从任何初始点进行迭代获得最优解的过程称为整体收敛性；而当接近最优解时 寻求尽快地收敛速度称为局部收敛速率。两部分相互研讨共同发展，形成了数值优化方 法的重要理论基础和算法的有效数值计算。 1 2 变分不等式问题基本概念简介 现简要回顾映射f 单调性的概念及性质等相关内容。 如果对所有的点z ，5 映射f 满足 ( f ( x ) 一f ( ) ，z 一，) 0 ，( 1 2 1 ) 则称映射f ：舻一舻在集合s 上为单调映射。进一步，若当z 一时( 1 2 1 ) 中不等号 严格成立，则称映射f 在集合s 上严格单调。当f 连续可微，且对任意的z s ，雅可 比矩阵v f ( z ) 正定，即对任意的z s 和d 舻( d 0 ) 有( d ，v f ( x ) d ) 0 成立，则映 射f 在集合s 上严格单调。注意到v f ( x ) 不一定对称。如果存在系数p 0 使得对所有 的z ，s ，有 ( f ( x ) 一f ( x 7 ) ，z 一一) p o z z ，f | 2 ( 1 2 2 ) 成立，则称映射f 为集合s 上的强单调映射( 或一致单调映射) 。 当映射f 连续可微时，( 1 2 2 ) 的一个等价形式为对任意。5 及d 舻有 ( d ，v f ( z ) d ) # l d l l 2 成立。显然强单调包含了严格单调。 给定佗n 对称正定矩阵g 作为范数权数，点ze 舻到集合s 的g 一范数投影记为 p r o j s , c ( z ) ，它表示的是下面约束优化问题的唯一解： m i nl i 一z 0 g s t y s ， 其中i i 。l l a = 。，g z ) 表示向量z 在舻上g 一范数。投影乘子p r o j s ，g ( ) 具有非扩张 性( 见【5 】) ，即对所有的点z ，舻，有 i p r o j 5 g ( z ) 一p r o j s ，g ( 一) l i esi i z 一一0 g ( 1 2 3 ) 第2 页 第一章变分不等式问题及最优化理论与方法的基础 假设g 为一给定的钆竹对称正定矩阵，z 咿为一给定的点。因为最小化问题 1 r a i n ( f ( z ) ，y z ) + 去( y z ，g ( y z ) ) s t 耖s ( 1 2 4 ) 等价于下列问题 r a i nj i 可一0 一g 1 f p ) ) 0 各s t ! ，s ， ( 1 2 5 ) 这里，h ( x ) d = d p r o j s , c ( x g 一1 f ( z ) ) 表示( 1 2 5 ) 的最优解，则它也是问题( 1 2 4 ) 的唯一最 优解。从( 1 2 3 ) 可知当映射f 连续时，日：舻_ s 也连续，并且映射日的不动点是变分 不等式问题( 1 1 1 ) 的解。 命题1 2 1 ( 见【6 9 】) 假设g 为一给定的nxn 对称正定矩阵，对每个z 渺设日( z ) 为问 题( 1 2 5 ) 的最优解，则z 为变分不等式问题( 1 1 1 ) 的解当且仅当z 是映射j 5 r 的不动点，即 z = 日( z ) 对任意给定的点z s ，变分不等式问题( 1 1 1 ) 的线性化变分不等式问题为： 寻找z 8 使得对任意5 恒有但( z ) + v f ( z ) t 0 一z ) ，y z ) 20 成立。( 1 2 6 ) 当映射f 连续可微且v f ( x ) 正定时，上述问题的唯一解存在，记为z ( z ) 映射z ：s _ s 具有下面的性质。 命题1 2 2 ( 见【6 9 】) 当映射f 连续可微且在集合s 上强单调时，映射z ：s _ s 也在集合s 上连续。进一步，z 是变分不等式问题( 1 1 1 ) 的解当且仅当z 满足z = z ( z ) 事实上，从这个命题的证明( 见【6 9 】) 可以得出结论当映射f 连续可微且雅可比矩阵 v f ( x ) 在集合s 上正定时，该命题的第二部分也成立。 本论文主要研究变分不等式问题转化为等价的( 无) 约束优化问题。 1 3 最优化问题简介 最优化问题的一般形式数学模型为 m i n ，( z ) ， s t 臼0 ) = 0 ， = l ，2 ，! - ，m ，( 1 3 1 ) g p ) 之0 ，i = m + 1 ，p ， 其中z 舻为决策变量，( z ) ：舻一跪为目标函数，q ( z ) ：妒一瓣i = l ，p 为约 束函数。称集合 s = f z 酽iq ( z ) = 0 ，i = 1 ，2 ，m ；e i ( x ) 0 ，i = m + l ，p ) ( 1 3 2 ) 第3 页 上海师范大学博士学位论文 为问题( 1 3 1 ) 的可行集。如果s = 咿，则称问题( l 3 ，1 ) 为无约束优化问题。对于最优化问 题，主要任务就是求最优解或者稳定点。 下面引入最优化理论与方法的基本概念。 定义1 3 1 设文s ，若对vz 5 有 f c x ) ，( z ) ， ( 1 3 3 ) 则称z 是问题( 1 3 1 ) 的整体极小值点。进一步，若对v z s 且z 文，有 f c x 。) o ) ，对vz sn m ( 文) ，有 f ( x ) ， ) ， ( 1 3 5 ) 则称矾是问题( 1 3 1 ) 的局部极小值点。进一步，若对v z sn m ( 矗) 且z 文，有 ， ) 0 ， 则文是问题( 1 3 1 ) 的一个严格局部最优解。 1 5 最优化问题的算法迭代格式 非线性( 无) 约束最优化理论与方法的研究，由整体收敛性和局部收敛速率两部分构 成。通常采用迭代法求解问题( 1 3 1 ) 的k k t 点得到最优解。其基本思想为：给定初始点 第5 页 上海师范大学博士学位论文 x 0 ，按照某一规则产生一个迭代序列f 妊) ，使得当 z 膏 是有限点列时，它的最后一个点 是k k t 点；当 孤) 是无限点列时，收敛于的任意一个聚点就是k k t 点。迭代法的基本 格式如下： 算法1 5 1 ( 最优化方法的基本迭代格式) 1 给定最优解的一个初始估计z o ，令k = 0 。 2 ：如果钆满足对最优解估计的终止条件，则停止迭代。 3 确定一个改善“的修正量靠。 4 得到最优解的一个更好的估计z 七+ 1 = + 吼，令k 卜后+ i ，转步2 。 在上述迭代法的基本格式中涉及到初始点的选取；迭代点好坏的判断；迭代的终止 条件；以及最重要也是最关键的修正量8 七的确定。 初始点的选取依赖算法的收敛性能。一个算法称为是收敛的是指算法产生的序列 z 知 满足 。l i m 慨一孔0 = 0 ， ( 1 5 1 ) 其中文是问题的k k t 点。线搜索技术与信赖域策略是保证算法具有整体收敛性的重要 手段。 收敛速度是迭代方法的又一重要性质。设序列 以) 在某种范数意义下收敛于孔，若 存在实数口 0 及一个与迭代次数k 无关的常数q 0 ，使得 l i r a k - - - * o o 矧钆 ( 1 5 2 )驿掣：口，( 1 5 2 ) l i 一“i i q 则称算法产生的迭代序列 巩) 具有q o t 阶收敛速率。特别地， ( 1 ) 当q = 1 ，口 1 时，迭代序列 孤) 具有q 一线性收敛速率： ( 2 ) 当1 0 ，使得 ，( z 七+ q 奄也) ；r a a i n of ( x k + q d 七) o t 七= m i l l 【a 0lv f ( x i g + q d 七) t 呶= o ) ， 第6 页 第一章变分不等式问题及最优化理论与方法的基础 这样的线搜索通常称为精确线搜索，得到的a 七称为精确步长因子。一般有直接搜索法和 插值法。但是，一般地，精确线搜索需要的计算量很大，而且在实际上也不必要，因此 人们提出了既花费较少的计算量，又能达到足够下降的不精确线搜索方法，如w o l f e 准 则，所求鲰只需满足充分下降条件 和曲率条件 i ( x k4 - q 七畋) 厂( z 七) + 胆七v 孵d k( 1 6 1 ) v f ( z k + & 奄磊) t d k 矿v 蠢? 靠，( 1 6 2 ) 其中，0 p 盯 1 在求解问题的过程中，要求每步迭代都有充分下降的线搜 索技术，我们称为单调的线搜索。如果不要求每次迭代都下降，只须每隔几步就有 所下降，这样的线搜索技术称为非单调线搜索。通常采用的是将( 1 6 1 ) 中的，( z 知) 用 ，( z l ( 功) 磐o g 搽 ) ，( z 七叫) ) 来代替，其中m ( k4 - 1 ) = n 曲( 仇( 后) + 1 ，m ) ，m 是取定的非 负整数。 信赖域方法的思想是在当前迭代点矾的某个邻域( 称为信赖域) 内，构造目标函数的 一个合适的二次模型近似，并在信赖域内极小化二次模型，通过反复迭代和校正信赖域 半径，得到新的迭代点z 七+ 1 无约束优化问题的信赖子问题通常是如下形式： 皿n ? 竖d 等，( 孤) + v 髭t d + 矿风d ( 1 6 3 ) s t i i d l i a k ， 、 其中鼠是h e s s i a n 矩阵v 2 f ( x k ) 或其近似，七为信赖域半径。对任意试探步如，我们称 p r e d ( d k ) = 妒七( o ) 一妒k ( d k ) 为二次模型(