（运筹学与控制论专业论文）锥约束变分不等式问题的数值方法的研究.pdf

大连理工大学博士学位论文 摘要 变分不等式问题在运筹学、计算机科学、系统科学、工程技术、交通、经济与管 理等许多方面有广泛应用在二十世纪最后2 0 年里，它受到许多学者的特别关注另外， 锥约束优化，尤其半定规划和二阶锥规划也是目前最优化领域的研究热点之一，而锥 约束变分不等式的研究还很初步本论文主要研究了锥约束变分不等式问题的数值方 法的收敛性，包括求解二阶锥约束变分不等式的半光滑n e w t o n 方法与光滑函数方法，以 及h i l b e r t 空间中的变分不等式的迫近点算法的收敛性 本论文所阐述的主要研究结果可概括如下： 1 第二章主要研究二阶锥约束变分不等式的半光滑n e w t o n 方法运用f i s c h e r - b u r m e i s t e r 函数将二阶锥约束变分不等式的k a r u s h k u h n t u c k e r 条件转化为非光 滑方程组问题圣f 召= 0 ，并给出了映射圣f b 的c l a r k 广义微分a 雪册的表达式在一 定条件下证明了该广义微分的非奇异性提出采l 罚a r m i j o 线搜索的求解该非光滑方 程组的修正牛顿法，证明了该算法的全局收敛性和局部超线性收敛性最后给出数 值例子验证了算法的有效性 2 第三章主要用光滑化方法求解二阶锥约束变分不等式运用光滑化的f i s c h e r - b u r m e i s t e r 函数将二阶锥约束变分不等式的k a m s h k u h n - t u c k e r 条件转化为光滑方 程组问题e = 0 在一定条件下，证明了映射e 的j a c o b i n 矩阵j e 的非奇异性运用 光滑的牛顿算法求解该光滑方程组问题，证明了算法的全局收敛性最后给出数值 例子验证了算法的有效性 3 第四章主要研究了基于预解算子理论的一般变分不等式的求解方法我们引入 了h i l b e r t 空间中一类新的单调算子，即m 单调算子，建立了一般变分不等式和一个 不动点问题的等价性为了求解该不动点问题，本文提出了一个迫近点算法在一 定条件下证明了该迫近点算法的全局收敛性而后，将上述理论应用到半定矩阵空 间中的变分不等式的求解为了保证算法的可行性，还另外给出了求解不动点问题 的近似解方法 关键词：二阶锥；变分不等式；f i s c h e r - b u r m e i s t e r i 函数；牛顿算法；h i l b e r t 空间；m 单调算子；预解算子 n u m e r i c a lm e t h o d sf o rs o l v i n gc o n ec o n s t r a i n tv a r i a t i o n a l i n e q u a l i t y p r o b l e m s a b s t r a c t 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 s h a v em a n yi m p o r t a n ta p p l i c a t i o n si n 叩e r a t i o nr e s e a r c h , c o m p u t e rs c i e n c e ，s y s t e ms c i e n c e ，e n g i n e e r i n gt e c h n o l o g y , t r a n s p o r t a t i o n e c o n o n l l c sa n dm a n a g e m e n te c t i nt h ei a s t2 0 y e a r so ft h et w e n t i e t hc e n t u r y , g r e a ta t t e n t i o n s n a v eb e e np a i db ym a n ys c h o l a r si n t h i sd i r e c t i o n m e a n w h i l e ，c o m c o p t i m i z a t i o n ，e s p e c i a l l v s e m l d e n n i t ep r o g r a m m i n ga n ds e c o n do r d e rc o n ep r o g r a m m i n g ，i sa na c t i v ef i e l di no p t i 嘶z a t l o nc o m m u n i t y h o w e v e r , t h es t u d yo fv 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 sw i t hc o n ec o n s 曲i i l t s l sn o te n o u g h b a s e do nt h i so b s e r v a t i o n ，t h i sd i s s e r t a t i o nf o c u s e s o nt h es t u d yo fc o n v e r j 聊1 c e a n a l y s i so fn u m e r i c a lm e t h o d sf 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 m sw i t hc o n ec o n s t r a i n t s i n c l u d m gs e 皿s m o o t hn e w t o nm e t h o d sa n ds m o o t h i n gf u n c t i o nm e t h o d sf o rs e 0 d n d o r d e r c o n ec o n s t r a i n e 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 sa n dp r o x i m a lp o i n tm e t h o d s f o rv a r i a t i o n a li n e q u a l i 西 p r o b l e m s i nh i l b e r ts p a c e t h em a i nr e s u l t so ft h i sd i s s e r t a t i o nc a n b es u i m n a d z e da sf b n o w s ： 1 i nt h es e c o n dc h a p t e r , t h ek a r u s h k u h n t u c k e rs y s t e mo f as e c o n do r d e rc o n ec o n s t r a i n e d 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 mi st r a n s f o r m e di n t oa s e m i s m o o t hs y s t e mo f e q u a t i o n sw i t h t h eh e l po ff i s c h e r - b u r m e i s t e ro p e r a t o r so v e rs e c o n do r d e rc o n e s t h ec l a r k e2 e n e r a l i z e dd i f f e r e n t i a lo ft h es e m i s m o o t hm a p p i n gi sp r e s e n t e d am o d i f i e dn e w t o nm e t h o d w i t ha r m i j ol i n es e a r c hi sp r o v e dt oh a v e g l o b a lc o n v e r g e n c ew i t hl o c a ls u p e r l i n e a rr a t e o ic o n v e r g e n c eu n d e rc e r t a i na s s u m p t i o n so nt h ev 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 a mi 1 1 u s t r a t i v ee x a m p l ei sg i v e nt os h o wh o wt h e g l o b a l l yc o n v e r g e n tm e t h o dw o r k s 2 t h et h i r dc h a p t e r m a i n l yd e a l sw i t ht h es m o o t hm e t h o df o rs c c o n d o r d e rc o n ec o n s 仃a i n e d 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 t h ek a r u s h k u h n t u c k e rs y s t e mo f as e c o n do r i b rc o n e c o n s t r a i n e 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 mi st r a n s f o r m e di n t oas m o o t hs y s t e mo f e q h a - t i o n se=0 w i t ht h eh e l po f s m o o t h i n gf i s c h e r - b u r m e i s t e ro p e r a t o r so v e rs c c o n do r d e r c o n e s u n d e rs o m ec o n d i t i o n s ，w ep r o v et h ej a c o b i nj e o fe i sn o n s i n g u l a r ag l o b a l c o n v e 略e n ts m o o t hn e w t o nm e t h o di sg i v e nf o rs o l v i n gt h es m o o t hs y s t e mo f e q u a t i o n s 3 c h a p t e r4d i s c u s st h em e t h o db a s e d o nt h er e s o l v e n to p e r a t o rf o rg e n e r a l v a r i a t i o n a li n e q u a l 。 i “an e wm o n o t o n i c i t y , m m o n o t o n i c i t y , i si n t r o d u c e d w i t ht h eh e l po f r e s o l v e n to p - e r a t o r a l le e l u i v a l e n c eb e t w e e nt h ev a r i a t i o n a li n e q u a l i t yv i ( c ，f + g ) a n d t h ef i x e dp o i n t p r o b l e mo fan o n e x p a n s i v em a p p i n gi se s t a b l i s h e d ap r o x i m a lp o i n ta l g o r i t h m i sc o n 。 s t r u c t e dt os o l v et h ef i x e dp o i n tp r o b l e m ，w h i c hi sp r o v e dt oh a v eag l o b a lc o n v e r g e n c e u n d e rt h ec o n d i t i o nt h a tfi nt h ev ip r o b l e mi ss t r o n g l ym o n o t o n ea n dl i p s c h i t z c o n t m 。 u o u s f u r t h e r m o r e ，ac o n v e r g e n tp a t hn e w t o nm e t h o d ，w h i c h i sb a s e do nt h ea s s u m p t i o n t h a tt h ep r o j e c t i o nm 印p m g1 i c ( ) i ss e m i s m o o t h ，i sg i v e nf o rc a l c u l a t i n ge s o l u t l o n s t ot h es e q u e n c eo ff i x e dp o i n tp r o b l e m s ，e n a b l i n gt h ep r o x i m a lp o i n ta l g o r i t h mi m p l e m e n t a b l e k e y w o r d s ：s e c o n d o r d e rc o n e ；v a r i a t i o n a li n e q u a l i t y ；f i s c h e r - b u r m e i s t e rf u n c t i o n ；n e w t o nm e t h o d ；h i l b e r ts p a c e ；m m o n o t o n i c i t y ；r e s o l v e n to p e r a t o r 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方 外，本论文不包含其他个人或集体已经发表的研究成果，也不包含其他己 申请学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的 贡献均己在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：纽渔塞童鲤鱼立羽箜堕垒邋堡堡翌杰 作者签名：塑盟篮 日期：巡年l 月2 韭日 大连理工大学博士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：塑丝缝翅! 趁醯塑堑辇鳋壅堑殓豆 作者签名：型! ! 堑堕日期：二堡王年j l 月竺l 日 导师签名：硷杰亚日期： 盟互年l 与三扛日 大连理工大学博士学位论文 1绪论 本章简要地介绍了变分不等式问题的背景和研究现状，并对相关文献做了综述在 本章的最后，扼要地列出本文的研究内容以及取得的主要结果。 1 1 变分不等式问题的背景和研究现状 “变分不等式”是“v a r i a t i o n a li n e q u a l i t y ”的中文译名，也有人译为“变分不等方程”变 分不等式作为变分原理的主要推广，是一类非常重要的非线性问题，产生于许多不同的 领域，如物理学，工程学和金融管理科学等等人们对变分不等式的兴趣始于一些力学问 题的研究1 9 3 3 年，s i g n o r i n i t l j 在研究一个线性弹性体与刚性体的无摩擦接触时导出了 一个变分不等式，称为s i g n o r i n i f q 题然而，变分不等式作为一个重要的数学分支则始于 上世纪六十年代关于s i g n o 矗t r i 问题的变分不等式的第一个严格的分析是在f i c h e r a 川中 给出的几乎同时，s t a m p a c c h i a 做出了变分不等式这一数学学科的奠基性贡献1 9 6 4 年， s t a m p a c c h i a l 3 j 把l a ) 【m i l g r a m 定理由h i l b e r t 空间推广到其非空闭凸子集的情形，得到了 变分不等式的第一个解的存在唯一性定理在“o n s 和s 伽n p a c c h i a l 引这篇著名的论文中 给出了变分不等式的一些数学理论d u v a u c 和l i o n s 5 在变分不等式的框架下研究了许 多力学和物理学问题l i o n s ，l e w y , b r e z i s 等人发表了一系列文章，为变分不等式理论奠 定了初步的基础2 0 世纪7 0 年代，变分不等式在最优控制问题，弹性问题，弹塑性问题及 渗流问题领域中得到了成功的应用2 0 世纪8 0 年代以来，作为现代偏微分方程理论重要 部分的变分不等式理论得到了深入发展，至今已较为成熟 另一方面，2 0 世纪6 0 年代中期，在非线性规划的研究中出现了线性和非线性互 补问题，它们进一步发展成为有限维空间中的变分不等式2 0 世纪9 0 年代，m a t h p r o g r a m m i n g 杂志出版了非线性互补问题与变分不等式的专辑，标志着变分不等式己成 为非线性规划的一个重要研究领域目前，经典的变分不等式理论己被大量地用于研究 产生于应用数学，优化控制理论，力学，物理学，非线性规划，经济学，金融，交通，弹性学， 应用科学等各个领域中的有效问题的一般处理框架如文献c 1 1 i p o t l o j ( 障碍问题，水坝问 题的正则理论) ，f r i e d m a n j ( 几类变分不等式和自由边界问题的数学分析) ，g l o w i n s k i 8 j 幂l l g l o w i n s k i ，l i o n s 和t r 6 m o l i e r 色s 剀( 变分不等式的数值分析和算法) ，h a n s f l l r e d d y l lo j ( 塑性力学中的硬化等问题的变分不等式的数学理论和离散逼近) ，h a n 和s o f o n e a l 儿j ( 粘弹性，粘塑性材料的接触力学的变分不等式的数学理论和数值分析) ，k i n d e r l e h r e r 锥约束变分不等式问题的数值方法的研究 n s t a m p a e e h i a 1 2 j ( 变分不等式的数学理论引论) ，p a n a g i o t o p o u l o s 1 3 ( 力学中的变分不 等式的理论和数值逼近) ，r o d r i g u e s 1 4 j ( 障碍问题中的变分不等式的完整理论介绍) 等 变分不等式理论是当前数学技术的一个强大工具 设k 是b a n a c h 空间y 中的一个非空闭凸集，f ：k _ y 为一个连续映象则称下面的 问题为经典变分不等式( e ) 问题：找z ，使得 ( f ( x + ) ，z z + ) 0 ，v z k ， 其中，y + 表示y 的对偶空间，( ，) 表示y 与y + 之间的偶对 我们通常所说的变分不等式理论的基本内容就是研究各种类型的变分不等式的 解的存在性和唯一性条件，解( 或解集) 的性状，解的各种迭代逼近算法，以及对各种问 题的应用等等因此，变分不等式的基本问题之一就是解的存在性问题关于变分不等 式解的存在性，己经有许多理论性的结果关于黔空间中变分不等式( 1 1 ) 解的存在性， 1 9 6 6 年h a r t m a n s t a m p a c c h i a 给出了一个最基础的结果 定理1 1 ：【j j 设k 是黔空间中的一个非空有界闭凸集，f ：k _ 琏铃连续，则存在z + k 满足变分不等式( 1 1 ) 当k 是无界的，或者空间为无限维空间时，变分不等式( 1 1 ) 解的存在性要求f 具有某 种单调性纵观研究变分不等式解的存在性历程，我们发现研究变分不等式的解的存在 性的方法主要有以下几种： ( 1 ) 将变分不等式( 广义方程) 转化为等价的不动点问题，构造迭代算法，然后利用空 间的完备性证明迭代序列收敛到变分不等式( 广义方程) 的解常用的方法有预估校正 的多步迭代算法、隐式方法以及对预解方程和辅助变分不等式变形后的迭代法，参阅文 献 1 5 18 1 ( 2 ) 利用几个经典的大定理，如b r o w d e r 不动点定理、k k m 定理、k y f a n 极大极小原 理等这种方法是经典不动点理论的一个重要应用l 1 9 1 ( 3 ) 例外簇方法这是近年来出现的一种新的用于研究变分不等式和互补问题解的 存在性的分析方法这种方法是基于连续函数的例外簇概念，与拓扑度紧密相关，可以认 为是一种广义强制性条件利用例外簇的定义，证明变分不等式或者有解，或者对于定义 域中的任意一点有关于这一点的一个例外簇从而可通过证明变分不等式没有关于这一 点的一个例外簇，来说明变分不等式有解，见文献l 2 u 屯引 一2 大连理工大学博士学位论文 由于变分不等式和其特例互补问题广泛用于阐述和研究物理学、力学、经济学、 运筹学、最优控制等数学模型以及交通运输中出现的各种平衡模型，近几十年来，其数值 解的研究发展也非常迅速，学者们已经提出了许多的有效的算法这些方法主要分为两 大类，二类为直接算法，一类为迭代算法直接法中经典算法为l e m k e 矛n h o w s o n 在1 9 6 4 年 提出的求解有限维线性互补问题的l e m k e 算法此后，c o m e 和d a j l t z i g 等进行了推广，得 到了许多的有效的算法c o t t l e 、p a n g 和s t o n e 在其专著【口j 中对这些算法进行了详细的 阐述迭代法的早期结果可参见g l o w i n s k i 的专著 9 1 ，p i v o t 方法 2 4 ，2 5 和不动点同伦方 法【曲j 等p i v o t 方法具有指数计算复杂性，不适合于大规模问题的计算近年来发展的方 法主要包括以下几类： ( 1 ) 内点法，可参见文献l 2 7 - 3 ij 等内点法是求解线性互补问题的一类很重要的算法， 其思想来源于1 9 8 4 年k a r m a r k a r 提出的解线性规划的算法这类算法的优点在于它具有多 项式计算复杂性，适合于大规模问题的计算l 3 2 j ( 2 ) 投影迭代法，可参见文献l j j 等 ( 3 ) 多重分裂法，这类方法最早由o l e 哪和洲t e l 鲻j 提出用来求解线性方程组， f r o m m e r 3 9 - 4 3 等做了进一步的研究，b e n a s s i 和w h i t e 4 4 】提出了一个求解变分不等式 的多重分裂算法，b a i 【4 5 _ 4 州对互补间题做了一系列的研究 ( 4 ) 非线性方程组方法，这类方法是将非线性互补问题转化为非线性方程组问 题h ( x ) = 0 ，再进行迭代求解早期的工作见m a n g a s 撕a 1 1 【川j ，到现在为止已出现许 多有效的方法根据s ( x ) 是否光滑又分为两类，即光滑方法【m 句4 j 等和非光滑方 法d 5 - 5 9 等光滑方法的主要优点是可以直接用n e w t o n t y p e 方法求解问题，其缺点是只 有当问题是非退化时才有快速的局部收敛性而非光滑方法在退化情形下也具有快速的 局部收敛性 ( 5 ) 优化界公认的在有限维空间研究互补问题与变分不等式的理论与算法的集大成 者为f a c c l l i n i e i 和p a n g ( 2 0 0 3 ) 专著【o 该专著收集了关于r 礼空间中r 的互补问题与变分不 等式的几乎所有重要的成果 然而除了r n 空间中的互补与变分不等式问题的理论和计算方法得到很好的研究，其 它的锥约束变分不等式的研究进展比较缓慢，比如半定变分不等式与二阶锥变分不等式 中p 性质的研究，这两类问题有效的数值算法的设计等等，都期待更多的工作的出现 3 锥约束变分不等式问题的数值方法的研究 1 2 二阶锥约束变分不等式问题 二阶锥约束变分不等式问题( s e c o n d - o r d e rc o n ec o n s t r a i n e dv a r i a t i o n a li n e q u a l i t yp r o b 1 e m ) 是：求解z c 满足 ( f ( z ) ，y z ) 0 ，v y c ，( 1 2 ) 其中c 表示为 c = x r n ：h ( x ) = 0 ，- g ( x ) 瓦) ，( 1 3 ) ( ，) 表示欧式内积，h ：酞礼_ 则和夕：r 竹一r m 都是连续可微的，并且 咒= 厄? 1 瓦m 2 瓦唧 ( 1 4 ) 其中2 0 ，m l ，m 2 ，1 和m 1 + m 2 + + m p = m 厄册，i = 1 ，p 是m i 维的 二阶锥 糟 下面给出二阶锥的定义 定义1 1 ：若j | | c 忆r n ( 礼1 ) 满足 瓦n = ( x l ；x 2 ) ix l r ，x 2 r n _ 1 并且x l i i x 2 1 1 ， 则称j i c 几为n 维的二阶锥，又叫做冰激凌锥 当佗= 1 时，足礼退化为非负实数集r + ”i | 表示f 2 范数 易见凸二阶锥规划可以看成二阶锥约束变分不等式的一个特殊情况： m i n 厂( z ) s t a x = b ， g ( x ) - e ， ( 1 5 ) 其中a r l n 行满秩，b 科，g ：r n r m ，：r n r 当，是凸的二次连续泛函时，问 题( 1 5 ) 等价于下面的二阶锥变分不等式问题：求解z c 满足 ( v 厂( z ) ，y z ) 0 ，v y c ， 一4 大连理工大学博士学位论文 集合c 表示为 c = z r n ：a x b = 0 ，- g ( z ) 咒) 二阶锥约束优化问题是目前研究的热点之一众所周知，咒n 如r ! 和仡死维实对称 正半定矩阵空间。兜一样，属于对称锥，这样我们就可以定义关于它的若当积基于此，学 者们提出了若干算法来求解二阶锥规划问题如内点法被应用到求解二阶锥约束线性规 划，见 6 1 - - 6 6 1 在文献 6 7 】中，给出非内部光滑化方法求解非线性补问题对于二阶锥补 问题( s o c c p ) ，学者们提出了大量光滑和非光滑算法，见文【o 毯，6 9 j 等但是，有关二阶锥 约束变分不等式的文献却不多见因此，本文要在此基础上对二阶锥约束变分不等式问 题展开研究 1 3h i l b e r t 空间中一般变分不等式问题 设日是h i l b e r t 空间，( ，) 和”f f 分别为其内积和范数。设c 是h i l b e r t 空间日中的一 个闭凸锥考虑下面的一般变分不等式( v k c ，f + g ) ) ：求解让c 满足 ( f ( u ) + g ( 乱) ，v u ) 0 ，v v c ， ( 1 6 ) 其中，f 和g 是日到其自身的映射显然，变分不等式( 1 6 ) 等价于下面的广义方程问题： 求解u c 满足 0 a ( u ) - t - t ( 珏) ， ( 1 7 ) 其中 t 三f + ( ；c ) ， ( ；c ) 是c 的法映射 变分不等式理论的最有趣的问题之一是构造有效的迭代算法以求得变分不等式的 近似解在h i l b e r t 空间中这个问题已经有大量的学者进行过研究，产生了大量的迭代算 法，如投影算法，基于预解算子技术的算法，基于辅助技术的算法，w i e n n e r - h o p f 方程技巧 等，见文献【7 0 - 7 4 和 7 4 ，7 6 - 8 0 ，8 2 投影算法及其变形，包括w i e 加e 广h o p f 方程技巧都 是求解变分不等式的重要方法，其来源可追溯至l j l i o n 年f l s t a m p a c c h i a l 4 j 许多关于h i l b e r t 空间中变分不等式的文献把注意力集中在引入一类新的变分不等式形式上，并针对这类 变分不等式问题提出相应的若干隐式迭代算法然而，却很少关心这些算法是否有效可 5 锥约束变分不等式问题的数值方法的研究 行例如：求解变分不等式( 1 6 ) 曾提出下面的基于辅助原理技术的迭代算法： 算法1 1 给定u n c ，新的迭代点u 什1 由下面不等式导出 ( 让n ，v 一乱n ) ( 1 一q 扎) 矿+ 1 ，v 一心他) + q nu n + 1 + 弘( f ( u n ) + g ( u 他) ) ，移一让n ) ，v v c ， 其中o l n 0 按照一定规则选择，p 0 是常数 下面是求解广义方程( 1 7 ) 的基于预解算子基础上的迭代算法： 算法1 2 给定u 佗c ，计算u 舛1 由 u 卅1 = 以，t ( u n c ( u n ) ) ， 其中以，r 三( 1 + c t ) 1 是丁的预解算子，c 0 是常数 可见，算法1 2 是不可行的，而算法1 1 中即使我们知道让n 也很难算出u n + 1 因此，本文中我们的目的是要提出一个可行有效的算法来求解h i l b e r t 空间中的变分 不等式问题v i ( c ，f + g ) 1 4 本文内容介绍 本论文主要研究了二阶锥约束变分不等式和h i l b e r t 空间中的变分不等式问题的数 值方法 本论文所阐述的主要研究结果可概括如下： 1 第二章主要研究了基于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 函数将二阶锥约束变分不等式的k a r u s h k u h n - t u c k e r 系统转化为非光滑方程组问题西f 日= 0 ，并给出了映射圣f b 的c l a r k 广义微 分a 圣f b 定理2 1 在假设严格互补成立的前提下证明了该广义微分的非奇异性进 一步，为了减弱定理2 1 的条件，我们又给出三个指标集将最优解附近的点进行分类 ，讨论，从而给出了二阶锥约束变分不等式的k a r u s h 。k u h n t u c k e r 系统的另外一个等 价方程函f b = 0 然后，在没有严格互补假设的情况下证明了a 垂邝的非奇异性最 后，提出修正的牛顿迭代算法求解该非光滑方程组，证明了该算法的全局收敛性和 局部超线性收敛性最后，给出数值例子用m a t l a b 进行计算 6 一 大连理工大学博士学位论文 2 第三章主要用光滑化方法求解二阶锥约束变分不等式运用光滑化的f i s c h e r - b u r m e i s t e r 函数将二阶锥约束变分不等式的k a r u s h k u h n t u c k e r 系统转化为光 滑方程组问题圣( z ) = 0 为求解该光滑方程组，我们又构建了一个辅助方程 组e ( ，z ) = 0 说明了z + 是西( z ) = 0 的解当且仅当( o ，z + ) 是e ( e ，z ) = 0 的解之 后，我们在一定条件下，证明了映射e 的j a c o b i n 矩阵j e 的非奇异性最后，运用q i ， s u n 和z h o u l 副j 所提出的光滑的牛顿算法求解该辅助光滑方程组问题，并证明了算 法的全局收敛性给出数值例子用m a t l a b 进行计算 3 第四章主要研究了基于预解算子基础上的一般变分不等式的求解方法我们引入 了h i l b e r t 空间中一类新的单调算子，即m 单调算子，详细地讨论了m 。单调算子和 极大单调算子的关系，并举例说明了m 一单调算子是极大单调算子的真推广证明 了m 单调算子的预解算子是单值的并_ 且是l i p s c h i t z 连续的然后，基于预解算子理 论，建立了广义变分不等式和一个不动点问题的等价性为了求解该不动点问题， 本文提出了一个迫近点算法在一定条件下证明了该迫近点算法的全局收敛性进 一步又将上述理论应用到半定矩阵空间中的变分不等式问题的求解为了保证算 法的可行性，还另外给出了求解不动点问题的近似解方法最后，给出具体算例说 明所提出算法的可行性 7 大连理工大学博士学位论文 2二阶锥约束变分不等式问题的半光滑n e w t o n 法 本章主要研究通过f i s c h e r - b u r m e i s t e r 函数将二阶锥约束变分不等式的k a r u s h k u h n t u c k e r 条件转化的半光滑方程组给出了该方程组中映射的c l a r k e 广义微分的计算公式， 提出修正的牛顿迭代算法求解二阶锥约束变分不等式的k k t 点，证明了算法的全局收敛 性和局部超线性收敛速度 2 1 引言 f i s c h e r - b u r m e i s t e r 函数作为补函数的一个，受到学者们的广泛关注f a c c h i n i e i 和p a n g 的著作【o u j 运用f i s c h e r - b u r m e i s t e r 函数构造了非线性补问题和多面体锥约束变 分不等式问题的数值解法目前，对于求解互补问题，变分不等式问题和非光滑方程问题， 学者们提出了大量算法，见 6 0 l 一【8 圳，并且将f i s c h e r - b u r m e i s t e r 函数推广到二阶锥中，目 的是使二阶锥补问题( s o c c p ) 和二阶锥约束优化问题能像多面体锥约束问题那样得以解 决，见 6 0 ，8 3 ，8 6 ，9 0 和 9 1 1 然而，由于严格互补条件不成立的情况下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 函数的c l 址广义微分的计算就变得尤为重要；另一 个重要的问题是保证f i s c h e r - b u r m e i s t e r 函数的c l a r k 广义微分非奇异的条件的研究我们 运用建立在二阶锥上的f i s c h e r - b u r m e i s t e r 算子将二阶锥约束变分不等式问题的k a r u s h k u h n t u c k e r 系统转化为半光滑方程组问题( 西f 日( z ，p ，a ) = 0 ) ，给出严格互补成立条件 下映射西f b 的微分形式同时，在严格互补不成立的情况下，刻画了西f b 的c l a r k e 广义微 分中元素，同时定义了西f 日的一个修正的映射圣f b ，说明该修正映射具有可微性根据上 述理论，给出一个修正的带h r m i j o 线收索的牛顿迭代算法并证明了算法的全局收敛性最 后通过计算实例检验算法的收敛性 2 2 基本概念和预备知识 对于任意的z = 1 ；z 2 ) ，y = ( 夕1 ；y 2 ) r r n ，我们定义它们的若当积为： z y = ( x t 秒；y l x 2 + x l y 2 ) 规定z 2 = z z ，h = 佰另外，任意的可瓦凡，施是瓦n 中唯一满足y = 扫施的向量 9 锥约束变分不等式问题的数值方法的研究 如果映射西：r n 瓞n _ 酞n 满足： ( z ，y ) = 0 甘瓦n 弓z 上y 瓦n ， 其中z 上y 兮z 可= 0 ，那么我们把映射咖：r 忆x 黔_ r n 叫做二阶锥上的补函数所谓 的f i s c h e r - b u r m e i s t e r ( f b ) 函数是指： 咖四( z ，y ) = z + y 一x 2 _ t _ y 2 。， 是一个二阶锥上的补函数3 礅 9 0 1 告诉我们砂船是强半光滑的 对于每一个z = ( z l ；x 2 ) 瓜xr 卜1 ，我们定义它的行列式和迹分别为： d e t ( x ) = z ；一l i z 2 i f 2 和t r ( x ) = 2 x 1 ， 与矩阵不同，一般情况下我们有d e 亡 y ) d e t ( x ) d e t ( y ) 只有当z = a y ，q r 时上述等 式才成立对于向量z = ( x l ；x 2 ) r 酞冗一，如果如亡( z ) 0 ，则我们说它是可逆的，并且 它的逆z - 1 满足z z _ 1 = e ，其中e = ( 1 ，0 ，o ) ? r 仡直接计算可以得到 z - 1 = 絮茅 显然，z i n t ( k ：n ) 当且仅当z 4 i n t ( k ：n ) 对于任意的z = ( x l ；z 2 ) rx 豫“，定义下面 二z = ( 三主：) c 2 - ， ，i o 大连理工大学博士学位论文 _ 一d e i ( x ) 仁筝d e t ( x ) i 簪) 亿2 ， 由 9 2 】可知，我们可以对每一个z ：( z 1 ；z 2 ) r r n 一1 做谱分解，与赶矗相对应有下面的 p i 三z 1 + ( - 1 ) i i i x 2 1 1 ， ，雹：曩i f 嘞x 2 。，# 0 , 命题2 1 ：任意的z = ( x l ；x 2 ) rxr n ，令其谱分解值为p 1 和p 2 ，谱分解向量为u ( 1 ) s l i u ( ：) 我们有下面的性质成立： ( a ) u 1 和让2 在若当积意义下具有正交性，并且其模长为击，既是 u ( 1 州= 。，桫) f f = 栌1 1 = 砺1 ( b ) u 0 ) 和让( 2 ) 在若当积意义下具有幂等性质，既是珏( ) 让( ) = 珏( 们，i = 1 ，2 。 ( c ) z 尼n 当且仅当p 1 0 ，并且z i n t ( c n ) 当且仅当p 1 0 ( d ) x 2 = p u ( 1 ) + p 2 u ( 2 ) 舻 ( e ) 如果z 瓦n ，贝0 2 1 2 = 、万u ( 1 ) + 、历u ( 2 ) c n ( f ) d e t ( x ) = p 1 户2 ，t r ( x ) = p l + p 2 ，i i x l l = p ；+ p ； 2 ( g ) p 1 ，化是n 佗维矩阵厶的特征值，u ( ，让( 2 ) 是其相应的特征向量余下的礼一2 个特 锥约束变分不等式问题的数值方法的研究 征值都是z 1 ，相应的特征向量形式为( 0 ，钉) ，其中u 属于酞铲1 且依赖于z 2 的零空间 2 3 二阶锥约束变分不等式k k t 条件的转化形式 所谓的二阶锥约束变分不等式问题是指：求解z c 满足 其中c 嚷示为 ( f ( z ) ，y z ) 0 ，v y c ， ( 2 3 ) c = ( z r n ：h ( x ) = 0 ，- g ( x ) 厄) ， ( 2 4 ) ( ，) 表示欧式内积，h ：r n _ 耐和夕：r 竹一r m 都是连续可微的，并且 | i c = 瓦m 1 c m 2 瓦m p ( 2 5 ) 其中z 0 ，仇1 ，m 2 ，m p 1 和m 1 + m 2 + + m p = m 瓦佩，i = 1 ，p 是m t 维的 二阶锥 需要指出，本文中j 表示单位矩阵，酞n 表示n 维实列向量空间对于闭凸锥疋n ，我们 用i n t ( 庀n ) j b d ( 厄竹) 和b d + ( 瓦n ) 分别表示它的内部，边界，和不包括零点的边界对于任意 的z ，y 庀，我们用z 三y 或z 墨y ( 相应的，z _ y 或。_ - b ( 相应 的，a 三b ) 来表示a b 的对称部分( a b + 4 t b t ) 2 是正定的( 相应的，正半定的) 对于任意的f r 6 c h e t - 可微映射f ：黔_ r m ，我们用j f ( z ) 酞m 黼来表示它在点z r n 处的j a c o b i a n 矩阵，即当u 一0 时 f ( x + u ) - f f ( 下z ) - j f ( x 一) u 一0 恻j 设f 在点互r n 是局部l i p s c l l i t z 连续的，如果f 在岔时点是不可微的，那么f 在牙点 处的c l a r k e 广义j a c o b i a n 为： c 9 f ( , 2 ) 兰c o n v j a c f ( ：z ) = c o n v o s f ( 孟