（运筹学与控制论专业论文）非线性互补问题的近似次梯度法.pdf

北京交通大学硕士学位论文 中文摘要 中文摘要 非线性互补问题是一类非常重要的优化问题，它广泛应用在经济、交通、金 融等领域中本文中，我们利用一种新的求解无约束非光滑优化问题的算法近似 次梯度算法，来求解非线性互补问题我们证明了n c p 函数为m i n 函数时非线性 互补问题的势函数是半光滑拟可微的，并且给出近似次梯度法在非线性互补问题 中的收敛性证明我们通过数值实验验证了该算法在求解非线性互补问题中的有 效性 本论文的组织结构如下： 第l 章介绍非线性互补问题的来源，一些基本定义和常用到的定理及求解非线 性互补问题的方法 第2 章介绍非光滑优化问题中经常用到的一些基本概念，以及一些常用到的 定理此外，我们介绍了一种新的求解无约束非光滑优化问题的方法近似次梯度 法，给出该算法的基本框架及收敛性 第3 章给出本文的主要工作，本文针对非线性互补问题可以转化为求解无约束 优化问题，当n c p 一函数为m i n 函数时，该无约束优化问题变为目标函数为半光滑 拟可微的无约束优化问题我们利用一种新的求解无约束非光滑优化问题的方法 一近似次梯度法，求解该非线性互补问题等价的半光滑拟可微的无约束优化问 题，并给出收敛性证明和数值实验结果 第4 章总结了本文的主要工作并对进一步的研究进行了展望 关键词：非线性互补问题；近似次梯度算法；势函数；离散梯度；近似次梯度 分类号：0 2 2 4 北京交通大学硕士学位论文 a b s t r a ! c t a b s t r a c t n o n l i n e a rc o m p l e m e n t a r i t y p r o b l e m sa r eo n eo ft h em o s ti m p o r t a n to p t i m i z a t i o n p r o b l e m s ，t h e ya r ew i d e l yu s e di ne c o n o m i c ，t r a n s p o r t , f i n a n c ea n do t h e rf i e l d s i nt h i s p a p e r , w eu s ean e wn o n s m o o t hu n c o n s t r a i n e do p t i m i z a t i o na l g o r i t h mc a l l e da l la p p r o x i m a t es u b g r a d i e n ta l g o r i t h mt os o l v et h en o n l i n e a rc o m p l e m e n t a r i t yp r o b l e m s w ep r o v e t h a tt h em e r i tf u n c t i o nf o rn o n l i n e a rc o m p l e m e n t a r i t yp r o b l e mi ss e m i s m o o t hq u a s i d i f f e r e n t i a b l ef u n c t i o nw h e nm i n f u n c t i o ni su s e da sn c p - f u n c t i o n a n da l s ot h ec o n v e r g e n c eo ft h ea p p r o x i m a t es u b g r a d i e n tm e t h o df o rn o n l i n e a rc o m p l e m e n t a r i t y p r o b l e m s i sp r o v e d n u m e r i c a le x p e r i m e n t so nn o n l i n e a rc o m p l e m e n t a r i t y p r o b l e m ss o l v e db yt h e p r o p o s e dm e t h e ds h o wt h a ti ti sp r o m i s i n g t h es t r u c t u r eo ft h ep a p e ri sa sf o l l o w s ： i nc h a p t e r1 , w ei n t r o d u c et h es o u r c eo fn o n l i n e a rc o m p l e m e n t a r i t yp r o b l e m ，s o m e k n o w l e d g eo ft h eb a s i cd e f i n i t i o n sa n dt h e o r e m s ，a sw e l la st h em e t h e df o rs o l v i n gn o n - l i n e a rc o m p l e m e n t a r i t yp r o b l e m i nc h a p t e r2 ，w ei n t r o d u c es o m eb a s i cd e f i n i t i o n sa n dt h e o r e m so nn o n s m o o t ho p - t i m i z a t i o n w eg i v ean e wa l g o r i t h mw h i c hc a l l e da p p r o x i m a t es u b g r a d i e n ta l g o r i t h m f o rs o l v i n gn o n s m o o t hu n c o n s t r m n e do p t i m i z a t i o np r o b l e m s ，a n da l s ow ei n t r o d u c et h e b a s i cf r a m e w o r ko ft h ea l g o r i t h ma n di t sc o n v e r g e n c e i nc h a p t e r3 , i tc o n t a i n st h em a i nc o n t r i b u t i o no ft h i st h e s i s b e c a u s en o n l i n e a r c o m p l e m e n t a r i t yp r o b l e mc a nb et r a n s f o r m e di n t ou 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 ，w h e nm i n f u n c t i o ni su s e da sn c p f u n c t i o n ，t h eo b j e c t i v ef u n c t i o no ft h i su 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 mi ss e m i s m o o t ha n dq u a s i d i f f e r e n t i a b l e w eu s ea r la p p r o x i m a t es u b g r a d i e n ta l g o r i t h mt os o l v et h es e m i s m o o t ha n dq u a s i d i f f e r e n t i a b l eu n c o n s t r a l n e do p t i m i z a t i o np r o b l e mw h i c ht r a n s f o r m e db yn o n l i n e a rc o m p l e m e n t a r i t yp r o b - l e m ，a n da l s ow es h o wt h ec o n v e r g e n c er e s u l ta n dt h en u m e r i c a le x p e r i m e n t s i nc h a p t e r4 ，w eg i v et h ec o n c l u s i o no ft h i st h e s i sa sw e l la ss o m ec o n s i d e r a t i o n s f o rf u r t h e rr e s e a r c h k e y w o r d s ：n o n l i n e a rc o m p l e m e n t a r i t yp r o b l e m ；a p p r o x i m a t es u b g r a d i e n ta l g o - r i t h m ；m e r i tf u n c t i o n ；d i s c r e t eg r a d i e n t ；a p p r o x i m a t es u b g r a d i e n t c l a s s n o ：0 2 2 4 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。 特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学 校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：何趸氯 签字日期：了力尸年月i c e 1 导师签名： 签字日期2 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示了谢意。 学位论文作者签名：签字日期：年 月日 致谢 我非常荣幸能有机会在北京交通大学攻读硕士学位，学校和理学院良好的学 习环境与科研氛围使我受益匪浅，相信近两年在这里的学习生活将使我受用一 生。 本论文的工作是在我的导师修乃华教授的悉心指导下完成的，修老师渊博的 学识，严谨的治学态度，独特新颖的思维方式和科学的工作方法对我有极大的帮助 和影响，是我学习的榜样作者非常感谢修老师在学术和生活上给我的极大鼓励 和支持。在此衷心感谢近两年来修老师对我的关心和帮助 感谢孔令臣、张超、阎爱玲、周金川、罗自炎、王英楠、秦林霞、黎煜、 杨建仪、曹静杰、王高阳、胡伟、魏庆举、张彦芳等师兄师姐师弟师妹对我学 业的热情帮助。能与你们在一起学习是我人生的宝贵财富特别感谢周金川、黎 煜师兄和舍友胡伟在我论文撰写过程中给予了许多帮助和修改意见 感谢闻国光、申晓斌、雷围华、杜志阔、景柳青、庞宇磊等研究生同学，能 与你们在一起学习使我感到非常快乐，非常荣幸感谢多年来一直支持和关心我的 所有的长辈、朋友、同学、亲人，有你们我的生命才更加灿烂 感谢韩继、i k 老师、于永光老师、郝荣霞老师、王周宏老师等曾经给我授过 课和帮助过我的所有老师，是他们的包容与谆谆教诲使我对科研和人生有了更深 刻的认识，使我的人生才有了更明确的目标 感谢我的父母和姐姐对我一直默默的支持与鼓励，是他( 她) 们无私伟大的爱 让我有了不断前进的动力和克服困难的勇气 最后感谢各位专家、学者在百忙之中审阅我的论文，我愿意认真听取专家的 宝贵意见，在今后的学习及研究工作中不断改进 北京交通大学硕士学位论文 第l 章非线性互补问题概述 1 1 引言 第1 章非线性互补问题概述 互补问题是一类非常霍要的优化问题，它广泛应用在经济分析、交通平衡策 略等社会经济模型中因此，对互补问题的研究具有重要意义“互补问题”作为一 类新的数学模型，是1 9 6 4 年美国r w c o t t l e 在其博士学位论文“n o n l i n e a rp r o g r a m s w i t hp o s i t i v e l yb o u n d e dj a c o b i a n s ”中提出的c o t t l e 的导师是著名运筹学家、“线性 规划之父”g b d a n t z i g 教授这一数学问题在初期曾被称为“拼合问题”( c o m p o s i t e p r o b l e m ) 、“基本问题”( f u n d a m e n t a lp r o b l e m ) 或“互补转轴问题”( c o m p l e m e n t a r i t y p i v o tp r o b l e m ) 等c o t t l e 在1 9 6 4 年的文献1 2 9 1 中和d a n t z i g c o t t l e1 9 6 7 年的文献【l l 】中 都曾指出：线性规划与二次规划是线性互补问题的特例在c o t t l e d a n t z i g1 9 6 8 年的 文献【刈中更指出：双矩阵对策( b i m a t r i xg a m e ) 问题也是线性互补问题的一特例线 性互补问题还包括了最优停止问题和市场均衡问题等非线性互补问题、混合互 补问题和隐互补问题包括了更多的数学问题，如一般非线性规划的k k - t 条件是 混合互补问题的一特例互补问题是从线性规划与非线性规划的推广而形成的， 所以它的算法研究与可解性研究受到了研究者的重视互补问题被提出以后，很快 在工程技术中得到了重要应用，许多文献讨论了它在力学、交通、经济、金融、 控制等许多领域的广泛应用 非线性互补问题是互补问题中的基本而且非常重要的一类问题，该问题的研 究引起了国内外许多著名学者的关注对于如何提出有效的算法求解非线性互补 问题，一直以来是众多学者关注的重点我们已经知道，对于该问题已经有了许多有 效的算法，比如：投影法、内点法、非光滑牛顿法、光滑化牛顿法等本文中，则利 用一类新的不用导数的方法近似次梯度法来求解非线性互补问题，并且通过数值 实验证明了该算法在求解非线性互补问题时的有效性 1 2 非线性互补问题的基本概念与性质 非线性互补问题是这样的问题，它包含的两组决策变量之间满足一种“互补关 系”互补关系反映了广泛存在的一种基本关系对于一个给定的互补问题，它是 否有解，是否有唯一解或其他性质，往往不容易弄清楚迄今关于互补问题的解的 存在性、唯一性、解集的有界性以及其他有关问题，很多文献中已有了广泛的研 究这些定性研究阐述了不同的互补问题的特征，也成为设计求解不同互补问题 北京交通大学硕： ：学位论文第1 章非线性互补问题概述 算法的理论基础我们约定：以彤表示n 维欧式空间，殿表示彤中的非负象限水+ + 表 示彤中的正象限f 中的矢量均为列矢鼍，x r y 表示矢量工与y 的内积，丁表示矢量和 矩阵的转置文章中涉及的矢量模与矩阵模i i 0 均指欧氏模 定义1 2 1线性互补问题( m el i n e a rc o m p l e m e n t a r i t y ) 令m 彤砌是一个n n 实矩阵，q 彤是一肛维矢量，线性互补问题是：寻求解 满足 工之0 ， m x + q o ，x r ( m x + 咖= 0 线性互补问题被记为l c p ( m , q ) 如引入矢量y ，y = m x + g ，则变量而与y i 满足 条件而0 ，y i 0 ，x i y i = 0 ，汪l ，力这表明了两组变量x i 与y i 满足互补关 系线性互补问题的基本来源是线性规划与二次规划考虑二次规划( q p ) ： m i nq ( 力= c t x - i - x t q x j f a x b 。工0 其中q 彤期为对称矩阵4 彤x 一，f l l l q = 0 ，二次规划退化为一线性规划设x 是 二次规划( q p ) 的一局部最优解，根据k a r u s h k u h n t u c k e r 最优性定理，存 在l a g r a n g e 乘子矢量，满足k k t 条件： yu：=c+qx-ary，o,x，o,：xr-b a x0y0y r v0 “= 。 ( 1 - 1 ) l y =+ ， ， = 如a 是半正定矩阵q = o ，贝j j q ( x ) 是凸函数，条件( 1 1 ) 也是( q p ) 的全局最优解的充分 条件定义 肘：= 【q a rl ，留：= c a 0 】 c l 2 ， ii i 符号“：= ”表示定义条件( 1 1 ) i l p 转化为线性互补问题l c p ( m , g ) ，其中包含的矩 阵m 是一双对称( b i s y m m e t r i c ) 矩阵所以任意一个二次规划的k k t 条件等价 于一线性互补问题，而且凸二次规划与线性规划等价于一线性互补问题 定义1 2 2 非线性互补问题( t i l en o n l i n e a rc o m p l e m e n t a r i t yp r o b l e m ) 令f ：f _ 彤是由r n 至i j r 的一映射，相应的非线性互补问题是：求矢量工彤，满足 x 0 ，( 石) 之0 ，f ( 力= 0 或者等价于： x i 0 ，f i 0 ，x i 一= 0 ，f = l ，疗 非线性互补问题被记为n c p ( f ) 或简记为n c p 当映射，是线性映射时，即，( 曲= m x + q ，则非线性互补问题化为线性互补问题l c p ( m , 鼋) 本文总假定映射f ： 彤_ 彤是彤上的一个连续可微的向量值函数，其中一为，的一个分量 2 北京交通人学硕士学位论文 第1 章非线性互补问题概述 定义1 2 3 令f ：冠_ f 为由僻到彤的一映射，相应的互补问题是指：求解不等式 组 菇0 ，f ( 曲0 ，x r f ( 力= 0 表示为c p ( f ) 称满足不等式工0 ，( 曲o 的点为互补问题c 尸( ，) 的“可行点”；称 满足不等式z 之0 ，f ( x ) 0 的点为c 以，) 的“严格可行点”；称满足式工0 ，f ( x ) o ，f ( 曲= 0 的点为c 以f ) 的“解”所有可行点的集合记为f e a ( f ) ，所有解的集合 记为s d 以，) 给定一互补问题c p ( f ) ，它可能没有可行点，即不等式石0 ，f ( x ) o 无解；或虽有可行点，但没有解如可行点集f e a ( f ) 为非空的，则称# l c p ( f ) 是可行 的如解集s o l ( f ) 为非空的，则称此c p ( f ) 是可解的 例令石= ( z l 。x 9 r r 2 ，f ( 曲= ( 妨，五( 力) r ，五( 力= 2 x l x 2 2 x 2 + l ，正( 曲= 一# + 2 石l 一1 此非线性互补问题的可行点f e a ( f ) = i 工0 i f ( x ) 0 = 州z i = 1 ，娩0 为 无界集，因为任意可行点x ，有，f ( 功= 1 ，故此互补问题没有解 定义1 2 4 矩阵m 彤期被称为半正定矩阵，如工r m x 0 ，v 工彤；肘被称为正定 矩阵。如，m x 0 ，y x 彤，x 0 这里定义的半正定矩阵与正定矩阵不限制是对称矩阵 定义1 2 5 令cc 彤为一非空集，f ：c 一彤为一映射如对任意点工，y c ，有 ( x 一) ，) r ( ，( 工) 一f l y ) ) 0 则称映射f 是c 中的单调映射”( m o n o t o n e ) 如对任意点工，y c 工) ，有 ( j 【一y ) 7 ( ，( 工) 一f l y ) ) 0 则称映射f 是c 中的“严格单调映射”( s t r i c t l ym o n o t o n e ) 如存在一常数口 0 ，使得对 任意点工，) ，c 有 ( x y ) r ( ，( 曲一f ( ) ，) ) 口i 防一) ，1 1 2 则称映射f 是c 中的“一致单调映射”( u n i f o r m l ym o n o t o n e ) 或“强单调映射” 当n = l 时。即f 是单变量函数，单调映射是非降函数当f 是线性映射，即，( 曲= m x + g ，r c = 彤，则矩阵肘是半正定矩阵 定义1 2 64 - cc 彤为一非空集，f ：c 一彤为一映射，f = ，正，。五) r 如对任 意点五) ，c , x y ，存在下标七= 七力，1 k n ，使得 瓤y k ，( 瓢一弧) m ( 曲一f k f y ) ) o ( o ) 3 北京交通大学硕：j ：学位论文第l 章非线性互补问题概述 别称映射f 是c 中的p 映射”( “p o 映射”) 如存在一常数口 o ，对任意点工，y c , x y ，存在- f ；t 示k = 妖五) ，) ，l k 使得 ( x k y k ) ( a ( 砖一五( y ) ) 口i i x 一) ，l 产 则称映射f 是c 中的“一致p 映射” 命题1 2 7 令cc 科是一非空集，f ：c _ 彤是一映射 ( a ) f 是单调映射，则，是映射； ( b ) f 是严格单调映射，则f 是p 映射； ( c ) f 是一致单调映射，则，是一致尸映射 根据定义易证此命题如c = 科，f 是线性映射，( 力= m x + 留，由p 映射和p o 映射可 相应地给出肘是脯阵和p o 矩阵的定义 定义1 2 8 矩阵m 舻期被称为“p 矩阵”( “p o ”矩阵) ，如对任意xe 彤，x o ，存在一 分量x k 0 ，使得 x k ( m x ) t o ( o ) 所有的p 矩阵组成的矩阵类被称为p 类，记为p 所有的凡矩阵组成的矩阵类被称 为凡类，记为尸o 显然半正定矩阵必足p 0 矩阵，正定矩阵必是p 矩阵所以凡矩阵和p 矩阵分别是 半正定矩阵和正定矩阵的推广下面的命题说明它们的代数性质 命题1 2 9m r n n 是一尸矩阵的充要条件是：肘的全部主子式均是正值 上面命题说明：如果m 是一p 矩阵，则肘7 也是p 矩阵 推论1 2 1 0令m 彤期为任意一矩阵 ( a ) 如肘是对称的，则肘是p 矩阵的充要条件是：肘是正定矩阵 ( b ) 如肘是非对称的，m 为正定矩阵，则m 是尸矩阵 例令掰= 【三- 3 】易知m 是p 矩阵如取x = t t ，- 只则，m x = 一t ，所以m 不是正 定矩阵 命题1 2 1 1令m 舻砌是任意一矩阵。则下面的情况是等价的： ( a ) m 是一p o 矩阵 ( b ) 膨的所有主子式均为非负数 ( c ) 对于任意正数s ，m + z l 是一p 矩阵，其中，如阶单位阵 4 北京交通大学硕： ：学位论文 第1 章非线性互补问题概述 命题1 2 1 2令ccf 是一非空开凸集，f ：c 一彤是一可微映射如j 孔0 b i 矩 阵v f ( x ) 是一p 矩阵，y x c , 更i jf 是c 中的p 映射 命题1 2 1 3令cc 彤是一非空开凸集，f ：c _ 彤是一可微映射则f 是c 中 的p 0 映射的充要条件是：如j a c o b i 矩阵v f ( x ) 是一p o 矩阵，v x c 1 3 非线性互补问题的解的相关理论 给定矩阵m 彤。一和矢量q 彤，相应的线性- e f t , i u 题l c p ( m , q ) 是求解关系式 工0 m x + q 0 ( 1 3 ) ( 1 4 ) ，( m x + g ) = 0 ( 1 5 ) 为了研究l c p ( m , q ) 解的性质和求解方法，有时引入变量w = m x + g ，将上面三 式( 1 3 ) 一( 1 5 ) 等价地改写为 j 0 ，w 0( 1 6 ) w = m x + q ( 1 7 ) ，w = 0 ( 1 8 ) 其中式x r w = o f q 价于x i w i = 0 ，f = l ，1 1 变量置与w f 被称为一“互补对”如矢 $ - q 0 ，显然x = 0 是l c p ( 尬留) 的一个解一般而言，p ( m 口) 不一定有解；若有 解，其解集不一定是凸集当肘是对称矩阵时，考虑二次规划： 血n 工r 胁+ ( 1 9 ) s ， 工0 其k k 一丁最优性条件恰是式( 1 6 ) 一( 1 8 ) ，我们可求解如上二次规划( 1 9 ) 来研 究l c p ( m , q ) 的解的性质当膨是一般非对称矩阵时，考虑以下二次规划： 血n x r ( m x + q ) ( 1 1 0 ) s t m x + q 0 工0 易知：点工是l c p ( m g ) 的解，当且仅当点x 是如j ：- - 次规划的全局极小解，而且 最优值是零所以通过l c p ( m , g ) 与二次规划的这种联系，我们可以利用二次规 5 北京交通大学硕士学位论文第1 章非线性互补问题概述 划( 1 9 ) 一( 1 1 0 ) 及二次规划的有关理论，来研究线性互补问题的解的存在性、唯一 性和解的其他性质“非退化性”是线性规划与非线性规划的重要性质，对于线性互 补问题也引入类似的性质 定义1 3 1 对于给定的- - l c p ( m , q ) ，点工殿，如蕊( m x + g ) f ，i = 1 ，则 点掀称为“非退化”( n o n d e g e n e r a t e ) 如l c p ( m , g ) 的一解工是非退化的，则称解x 有“严 格互补性”( s t r i c tc o m p l e m e n t a r i t y ) 本节一开始提出的线性互补问题也可等价的表示为非光滑方程组： 日( 石) ：= m i n ( x , m x + q ) = 0 其中 r a i n ”是对各分量分别取极小在l c p ( m , g ) 的任意一解x 的邻域内，映射h 一般 是不可微的，但如解x 是非退化的，则工存在一邻域，使日在此邻域内是可微的故在此 邻域内可以使用基于日的j a c o b i 矩阵的解析方法来求l c p ( m , q ) 的一近似解 显然如上二次规划的目标函数在可行集i x 舻i 工0 ，m x + q 0 ) 中有下 界( 为零) ，根据一般二次规划的最优解存在的一个基本定理f r a n k w o l f e 定理，可 知二次规划( 1 1 0 ) 必有全局最优解下面引述这一命题 命题1 3 2 ( f r a n k w o l f e ) 如任意二次函教，在一非空多面体x ( 可以是无界 集) 中有下界，则，在x 中必有全局极小解 令x 是二次规划( 1 1 0 ) 的全局极小解，当矩阵m 具有某些特性时，r 对应的最优值可 以是零，则r 即是l c p ( m , q ) 的一解下面给出二次规划( 1 1 0 ) 最优解满足的k k 一 丁条件 命题1 3 3 i 雯l c p ( m , g ) 是可行的，则二次规划( 1 i o ) m - 有一最优解x ，r 与乘子矢 量u 满足k k 一丁条件： 而且r 与旷还满足 q + ( 肘+ 肘r ) 工一肘r “芝0 ( 石+ ) r ( 口+ ( m + m r ) 工一m 7 u ) = 0 h 之0 ，( 雎) r ( 鼋+ m x ) = 0 工0 ，m x + + q 0 ( 1 1 2 ) ( 1 1 3 ) ( 1 1 4 ) ( r 一“) f ( m r ( r h + ) ) fs0 ，i = 1 。，n( 1 1 5 ) 6 北京交通大学硕一 ：学位论文 第1 章非线性互补问题概述 命题( 1 3 3 ) 是研究l c p ( m , 彩的重要工具利用这一结果，可以给出半正定矩阵 与正定矩阵相应的l c p ( m , 留) 的解的存在性 命题1 3 4 设肘彤期是一半正定矩阵，q 彤，如配p ( 旭g ) 是可行的，则它有解 证明 因为l c p ( m , 鼋) 是可行的，由命题1 3 3 知，存在矢量x 与u 满足式( 1 1 1 ) 一 ( 1 1 5 ) ，由式( 1 1 5 ) 可得( r 一矿) r m r 防一矿) so 因朋是半正定矩阵，所以有( r 一 “+ ) r m r ( 矿一“) = 0 由此可推出 ( ，一“) f ( 肘7 ( r 一“) ) 产0 ，i = 1 ，n ，利用命题1 3 3 中的结论，由鼋+ ( m + m 7 ) r m 7 u 0 ，把式( r ) 丁( 口+ ( m + 肘7 ) r m 7 u ) = 0 表示为分量形式，可得 耳( m 7 ( 工一“) ) fs0 ，i = 1 ，n 将g + ( 朋+ m 7 ) r m 7 h o 盼第i 个分量乘以“；，由矿0 ，( h ) 7 ( g + m x ) = 0 ，可 得一“；( m 7 ( r 一矿) ) f 0 ，i = 1 ，故知 葛( m 7 1 ( 工一“) ) i = u t ( m 7 ( r 一“) ) j = 0 ，i = l ，n ， 将此式代x ( x ) r ( 留+ ( 肘+ m 7 ) r 一朋7 ”。) = 0 ，我们得到( r ) r ( 鼋+ m x ) = o ，这证明 - f x + 是l c p ( m , g ) 的一解证毕 命题1 3 5 设肘r n x “是一正定矩阵，则对于任意g 尉，l c p ( m , q ) 有唯一解 证名 因肘是正定矩阵，易知肘是一j p 矩阵故知，对于任意q 彤，l c p ( m , q ) 必 是可行的由命题1 3 4 得，l c p ( 尬g ) 有解r ，而且r 也必是二次规划( 1 1 0 ) 的全局极 小解因目标函数，( m x + q ) 是严格凸函数，二次规划( 1 。1 0 ) 只有唯一解。即证明 - j l c p ( m , g ) 也只有唯一解证毕 当f 是非线性映射时，互补j 题的解的存在性和唯一性的研究不能借助于二次 规划性质，而需要其他的方法上述非线性互补问题是定义在非负象限贮中的互补 问题殿是彤中的一个闭凸锥零点是锥的尖点在研究非线性互补问题的解的存在 性时，我们可以考虑定义在一般闭凸锥中的广义互补问题 定义1 3 6令cc 彤是一非空子集 ( 1 ) 称c 是一“锥”( c o n e ) ，如 r c ，则肌cv a 0 显然零点属于锥c ( 2 ) 称c 是一“凸锥”，如石c , y c 则肌+ 彬c , v a o ，p 0 ( 3 ) 称c 是有尖点”的( p o i n t e d ) ，如工c , x o ，则一石萑c ( 4 ) 称c 是“立体的”( s o l i d ) ，如c 有内点 7 北京交通大学硕士学位论文 第l 章非线性互补问题概述 定义1 3 7令cc 彤是一非空子集，称c ：= y 彤旷工o ，h c l 为c 的“对偶 锥”( d u a lc o n e ) 显然对偶锥c 是一非空的闭凸锥当c = 殿时，易证：c = 群利用彤中任意一 个有尖点的立体的闭凸锥c ，可以在钟中两点之间定义一偏序 定义1 3 8 令cc 舻是一个有尖点的立体闭凸锥，称点旅锥c 大于或等于 点弘如上一) ，c ，记为x 兰y ；称点非锥c 大于点) ，如工一y i n t c , 记j 【；y ( i n t c 表 示c 的全部内点) 特别是，如y ：o , x co o ；o ) 即是工c o i n t c ) 定义1 3 9令ccr n 是一有尖点的立体闭凸锥，c 是c 的对偶锥，f ：c 一彤是一 映射定义在c 中的广义互补问题是：寻求一点x ，满足 记为c p ( f , cc ) c c 一 x o ，f ( 工) 0 ，x 7 f i ：力= 0 命题1 3 1 0 令f ：冠一彤是一p 映射，则互补问题c p ( f ) 至多有一个解( 也可能 无解) 证明 设r ，y 艘是互补问题c p ( ，) 的两个不同的解，则对于任意下标i ，f = l ，l ，有 舛0 ，i o ，五( r ) 之0 ，五( ) 广) 0 工；点( 工) = 0 = ) ，；五( ) ，) 其中石是映射，的分量所以 ( 薯一y ：) ( 五( r ) 一五( ) ，) ) = 一# 五( ) ，。) 一y t f , f x ) 0 ，f = 1 ，n 这与p 映射的定义相矛盾，即证明了互补问题c p ( f ) 至多有一个解证毕 命题1 3 1 l ( b r o u w e r 不动点定理) 令ccr n 是一非空有界闭凸集，t ：c c 是 一连续映射，丁( 曲c ，则丁在c 中必有不动点，即存在点r c 使得丁) = r 命题1 3 1 2 ( h a r t m a n s t a m p a c c h i a 基本存在定理) 令ccr n 是一非空有界闭凸 集，f ：c 一即是一连续映射，则存在点r c ，满足 ( x x ) r f c ，) 0 ，v x c 证明首先证明：变分不等式( 1 1 6 ) 等价于不动点问题 x = ( x 一，( 曲) 8 ( 1 1 6 ) ( 1 1 7 ) 北京交通人学硕士学位论文第l 章非线性互补问题概述 其中p c ( z ) 表示点z 到闭凸集c 上的投影如点r 是式( 1 1 7 ) 的不动点，即r = p c ( r f ( x ) ) ，所以有r c ，且满足一r ) r ( ( ，一f ( x ) ) 一r ) s0 ，y y c , 且p ( y - x ) r f ( x ) 0 ，v y c 这表明r 是变分不等式( 1 1 6 ) 的解反之，变分不等式的解也是不动点问 题( 1 1 7 ) 的解 令映射丁( 力：= p c o 一，( 石) ) ，y x c 因，是连续映射，根据投影变换的性质，可 知丁( 石) 在c 中是连续的利用b r o u w e r 不动点定理，可证映射t ：c c 有不动点，所 以变分不等式有解证毕 命题1 3 1 3 令cc 彤是一有尖点的立体闭凸锥，f ：c 胛是一映射，则点r 是 广义互补问题c p ( 只c c ) 的解，当且仅当r 是变分不等式v i ( f , c ) 的解 证明设点x 是广义互补问题c p ( f , c c + ) 的解，即r c ，( r ) c ，( r ) r f ( r ) = 0 所以x r f ( r ) 0 ，y x c 我们得到扛一x ) 丁f ( x ) = x t f ( x ) 0 ，v j 【c 即证 点，是变分不等式的解反之，设点r 满足r c ( x r ) r ，( r ) 0 ，y x c 显 然2 r c i x c 取工= 2 x + 及 r ，代入此不等式，可得 r ，( ，) 0 ，一( r ) r ，( ，) 0 故有( r ) r f ( x ) = 0 将此式代入o r ) 7 f ( x ) 0 ，y x e 可得x 7 ，) 0 ，y x c ，这表明f ( x + ) p 即证明了点r 是广义互补问题的解证毕 特别，如凸锥c = 群，命题1 3 1 3 指出：变分不等式v i ( f , 群) 等价于互补问题c p ( f ) 我们可认为互补问题是变分不等式的一种特殊情况我们已知：非线性p 映射相应 的互补问题在可行集为非空时可以没有解 定义1 3 1 4 令ccr n 是一有尖点的立体闭凸锥，称单调映射f ：c _ 胛在 点i c 是“正常的”( p r o p e r ) ，如集合 b ( j d ：= 工ci 工一i c ，f ( d f ( j b c ，( x 一动r ( f ( x ) 一f ( j b ) = 0 l 是有界集显然点i 口( 习，所以顾习为非空 命题1 3 1 5 令cc 彤是一有尖点的立体闭凸锥，f ：c - f 是连续的单调映 射如广义互补问题c p ( f , gc ) 有可行点i ，且，在i 是正常的，则c j p ( ec c ) 有解 命题1 3 1 6 今cc f 是一有尖点的立体闲凸锥。f ：c 一彤是连续的严格单调映 射如广义互补问题c p ( e c p ) 有可行点，则c p ( 只c c ) 有解，且解是唯一的 证明令点i 是c p ( f , ec ) 的一可行点，即i cf ( 习c 显然i b ( 动因，是严格 单调映射，对任意点工c x i ，有o x - ) 丁( f ( 曲一f ( 动 o ) ，所以工薯b 回，即b 回= i 是有界集映射f 在i 是正常的，根据命题1 3 1 5 ，可知c p ( f , c c ) 有解设x 1 ，分 9 北京交通大学硕士学位论文 第1 章非线性互补问题概述 别是c p ( f , c c ) 的解，z 1 p ，则有0 i l u l i ，使得 ( x 一“) r ，( 工) 0 ，y x ci l x l i = r 则广义互补问题c p ( f , c c + ) 有解x , f f 1 l x s 厂 n 在上面的命题中，特别是，如闭凸锥c 是一“矩形锥”g ，即c r ：= 兀五，其中兀表 f = i 示笛卡尔积，集合 表示0 ，【0 ，+ ) ，( 一，o 】，( 一o o ，+ ) 等四种区间的任一种，则条 件( 1 3 1 5 ) 可以减弱，下面命题中出现的矢量无穷模是指：l l x l l 。= m a x i x i i l i = 1 ，以1 命题1 3 1 8令gc 彤是一矩形锥，f ：c r 彤是一连续映射如存在点“c r 和 常数， i l u l l 。，使得 m a x l ( x i 一蜥) 五( d l 0 ，v 工c ，i i x l l 。= r 1 ) n 其中五是映射，的第f 个分量，则互补问题c p ( 只c r g ) 有解x , - f f - i i x r 命题1 3 1 9令ccr n 是一有尖点的立体闭凸锥，f ：c _ 彤是一连续映射如c 中 存在一非空有界闭子集d ，使得对任意一点石c d ，都存在一点) ，d ，满足 o 一) ，) 7 ，( 力 0 则广义互补问题c p ( f , c c + ) 有解r ，且r d 如果闭凸锥c 推广为彤中的一般无界闭凸锥，则上面该命题可以推广到定义 在c 中的变分不等式v i ( f , c ) ，且可以利用该命题证明一致单调映射和一致p 映射 的互补问题都有唯一解 命题1 3 2 0令cc 即是一有尖点的立体闭凸锥，f ：c 一殿是连续的一致单调映 射，则c p ( f c c ) 有唯一解 证明 o i f ( o ) = 0 ，显然点0 是c p ( f , c , c + ) 的解如f ( o ) 0 ，因f 是一致单调映 射，即存在常数o t o ，使得 ( 工一y ) 7 ( ，( 曲一f l y ) ) 口i i x y 2 ，y x ，y c 1 0 北京交通大学硕士学位论文第1 章非线性互补问题概述 令j d ：= 掣 o ，集合d ：= x c ii i x l l5 d 则d 是一非空有界闭集对任意点z c d ，有 ，f ( 工) ，f ( o ) + 口1 1 工t 1 2 园l l x l l p 等价于口1 2 i i x l li i f ( 0 ) i i ，将此式代入上式，再利用sc h w a r z 不等式，可得 x r f ( x ) x r f ( o ) + ai i x l l 2 x r f ( o ) + i l x l li i f ( 0 ) i i20 上式说明：对任意点石c d ，在集合d 中有点y = 0 ，使得命题的条件成立即证 得c p ( f , c c ) 有解因一致单调映射必是严格单调映射，故可知c p ( f , g c ) 有唯 一解证毕 命题1 3 2 1 设，：哎彤是连续的一致尸映射，则c p ( f ) 有唯一解 上面三节简单介绍了非线性互补问题中的一些基本概念、基本定理以及解的相 关理论，关于该问题的更详细的内容可参考非线性互补问题的专注【1 2 1 1 4 非线性互补问题的基本求解方法 非线性互补理论的许多基本理论结果已经被证明有很长一段时间，1 9 9 0 年以 前对该理论有很好综述的文章可以参考文献【2 5 1 更多的参考和最近的研究成果 可以参考文献【