（运筹学与控制论专业论文）非线性互补问题的光滑化牛顿法.pdf

内蒙古大学硕士学位论文 非线性互补问题的光滑化牛顿法 摘要 本文给出非线性互补问题n c p ( f ) 的一个新的光滑逼近方程组，研究了光 滑逼近方程组的若干性质，基此给出求解n c p ( f ) 一步光滑化牛顿法，方法适用 于f 仅在殿上有定义的情形算法每次迭代只需求解一个线性方程组和执行 一次a r m i j o 线搜索当f 为连续可微昂一函数且n c p ( f ) 解集非空有界时算 法全局收敛当迭代序列的聚点满足c d 一正则假设时，算法具有超线性收敛速 率( 此时不需要严格互补条件成立) ，特别当f 的j a c o b i 矩阵满足l i p s c h i t z 连续 时，算法是局部二次收敛的数值实验表明了算法的有效性 关键词：非线性互补问题，昂一函数，光滑化牛顿法，全局收敛性，超线性- 次收敛，光滑逼近方程组 a s m o o t h i n gn e w t o nm e t h o df o r 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 s a b s t r a c t i nt h i st h e s i s ，an e ws m o o t ha p p r o x i m a t i o ne q u a t i o no ft 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 ( d e n o t e db yn c p ( f ) ) i sp r e s e n t e da n d i t sp r o p e r t i e sa r ed i s c u s s e d b a s e do n t h i s ，a no n e - s t e ps m o o t h i n gn e w t o nm e t h o df o rs o l v i n gn c p ( f ) i sp r o p o s e d ，t h em e t h o d i ss u i t a b l ef o rt h ec a s et h a tf i sd e f i n e do n l yo n 皿竺t h ea l g o r i t h mn e e d so n l yt os o l v e o n el i n e a rs y s t e mo fe q u a t i o n sa n dp e r f o r m so n ea r m i j ol i n es e a r c hp e ri t e r a t i o n w h e nf i ss m o o t hp o f u n c t i o na n dn c p ( f ) h a sn o n e m p t ya n db o u n d e ds o l u t i o ns e t ，t h ep r o p o s e d a l g o r i t h mi sp r o v e dt ob eg l o b a l l yc o n v e r g e n tu n d e rt h ec o n d i t i o no fc d r e g u l a r i t y f u r - t h e r m o r e ，t h ea l g o r i t h mi sl o c a l l yq u a d r a t i c a l l yc o n v e r g e n ti ff ，( z ) i sl i p s c h t i zc o n t i n u o u s a ts o l u t i o n n u m e r i c a lr e s u l t si n d i c a t et h a tt h ea l g o r i t h mi se f f i c i e n t 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 ，p 0 一f u n c t i o n ，s m o o t h i n gn e w t o n m e t h o d ，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 r q u a d r a t i cc o n v e r g e n c e ，s m o o t ha p p r o x i m a t i o n i i 原创性声明 本人声明：所呈交的学位论文是本人在导师的指导下进行的研究工作及取得的研究 成果。除本文已经注明引用的内容外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得内蒙古大学及其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：函彗坠邋 日 指导教师签名：燃 在学期间研究成果使用承诺书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：内蒙古大学有权 将学位论文的全部内容或部分保留并向国家有关机构、部门送交学位论文的复印件和磁 盘，允许编入有关数据库进行检索，也可以采用影印、缩印或其他复制手段保存、汇编学位 论文。为保护学院和导师的知识产权，作者在学期问取得的研究成果属于内蒙古大学作 者今后使用涉及在学期间主要研究内容或研究成果，须征得内蒙古大学就读期间导师的同 意；若用于发表论文，版权单位必须署名为内蒙古大学方可投稿或公开发表 学位论文作者签名：囟! 照邀 只 ：躞 第一章引言 1 1互补问题算法研究进展 设f ：衍_ 衍是一非线性映射，非线性互补问题( 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 ，简记为n c p ( f ) ) 是指：求一个向量z 衍，使得 z 0 ，f ( x ) 0 ，x t f ( x ) = 0 ( 1 1 ) 集合f = z 形：z 0 ，f ( x ) o 称为n c p ( f ) 的可行域，z 厂称为n c p ( f ) 的 可行点，如果z 满足z 0 ，f ( x ) 0 ，则称z 为n c p ( f ) 的严格可行点如果( 1 1 ) 中 的f ( x ) 是仿射函数，即f ( x ) = m x - 4 - q ，其中m = ( 盹f ) 研姗为常数矩阵， q = ( q 1 ，) t 研为常向量，则非线性互补问题蜕化为线性互补问题【1 , 2 s l ( 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 m ，简记为l c p ( q , m ) 互补问题是运筹学与计算数学的一个交叉研究领域，这不仅仅是由于它在非线性最优 化方面具有广泛的应用，而且在微分方程、流体力学、对策论、工程问题、经济均衡理论、 交通等许多方面都有着重要应用【7 ，2 5 1 ，这使得互补问题成为数学规划中的一个十分热门的 研究课题经过四十多年的发展，其理论体系、数值方法和应用领域日渐完善、深入和扩 大，已发展成为一门内容十分丰富并具有广阔应用前景的边缘学科，引起众多数学工作者 的广泛兴趣和高度重视参见h a x k e r 和p a n g 的综述性文章【2 5 1 ，c o t t l e ，p a n g 和s t o n e 的 专著【1 l ，f e r r i s 和p a n g 的综述性文章【7 】，f a c c h i n e i 和p a n g 的专著【2 】和韩继业，修乃华， 戚厚铎的专著【5 l 等 互补问题首先由著名运筹学家、数学规划的创始人g b d a n t z i g 和他的学生 r w c o t t l e 于1 9 6 3 年提出次年，c o t t l e 在他的博士论文中第一次提出求解互补问题的非 线性规划算法互补问题很快引起了当时运筹学界和应用数学界的广泛关注和浓厚兴趣， 许多人参与了这类问题的研究关于互补问题的研究一般分为理论和算法两个方面，前者 主要研究解的存在性、唯一性、稳定性和灵敏度分析，以及互补问题与其他数学问题的联 系等；后者则主要建立有效的求解方法及相应算法的理论分析到2 0 世纪8 0 年代中后期， 经过二十多年的努力，在理论和算法方面已取得了比较丰硕的成果关于1 9 9 0 年以前的 工作，可参见h a r k e r 和p a n g 的综述文献【2 5 】以及这一时期的专著【4 2 1 , 2 4 , 2 8 到2 0 世纪9 0 年代，对互补问题的理论和算法的研究出现了高潮，在这十多年的时间里，人们不仅改进与 丰富了互补问题的理论研究，而且还提出多种有效算法 1 方程组法 这类方法就是首先把非线性互补问题转化为等价的非线性方程组，然后利用求解方程 组的相关方法1 2 6 】间接得到n c p ( f ) 的解，这类方法通常需要借助n c p 函数来完成如果 1 内蒙古大学硕士学位论文 函数西：1 r 2 _ 皿满足条件 圣c z ，：= ( ：三：三三：) ， c 1 其中p ：皿_ 皿是一个严格单调递增函数，且e ( o ) = 0 适当选取p ( ) ( 例如o ( t ) = t i t ，i t l 3 ) ，可使圣( z ) 光滑，从而使式( 1 3 ) 成为光滑非线性方程组然而这种转化方式存 在缺点：即使一个线性互补问题，转化后的方程组非线性程度往往较高，且在退化解点的 j a c o b i 矩阵奇异为了弥补这一不足，人们转向构造非光滑方程组互补问题的非光滑方 程组等价表述形式并不是新鲜的，人们在1 9 7 1 年就知道如下形式的非光滑方程组 m i n x ，f ( z ) ) = 0 ( 1 4 ) 方程( 1 4 ) 称为n c p ( f ) ) 的自然方程【1 0 | 非光滑方程组方法的发展在于非光滑分析理论的 日渐成熟 1 9 8 7 年，r o b i n s o n 2 s 】最早利用b 导数来研究非光滑方程组的牛顿法1 9 9 0 年，基于 非光滑方程组( 1 4 ) ，p a n g 2 9 】利用b 一导数提出了一种广义牛顿法，并在一定条件下证明了 算法的全局收敛性之后，p a n g 和g a b r i e l 3 1 】提出了他们自己称作n e s q p 的方法，在某 些( 解的) 正则条件下，证明了其算法产生的点列的任意聚点是互补问题的解，同时得到了 局部超线性- 次敛性不过，该方法中每次迭代的下降方向是通过求解二次规划子问题 得到基于n c p ( f ) ) 的法方程【1 0 l 。 圣( z ) = f ( x + ) + z 一= 0 ，( 1 5 ) h a r k e r 和x i a o 3 2 】利用b 导数提出了一类广义牛顿法，并在f ( x ) 为一致p 一函数的假设 条件下，证明了其算法的全局收敛性 2 内蒙古大学硕士学位论文 1 9 9 2 年，f i s c h e r 引入了一种新的n c p 函数( 又称作f i s c h e l b u r m e i s t e r 函数【1 1 1 ) f i s c h e r - b u r m e i s t e r 函数及其它n c p 函数的出现和半光滑理论的建立，进一步促进了非光 滑方程组的发展，这类算法的全局收敛性和局部超线性收敛性在适当条件下得到证明其 中d e l u c a ，f a z c h i n e i 和k a n z o w 3 3 l 对基于极小函数和基于f i s c h e r - b u r m e i s t e r 函数的各 种广义牛顿类算法( 包括精确、不精确和l e v e n b e r g - m a r q u a r d t 型不精确广义牛顿法) 进 行了从理沦到数值结果的比较、评价，详细讨论了这些算法全局和局部收敛性所需要的条 件指出基于f i s c h e r - b u r m e i s t e r 函数的算法可在较弱条件下也能确定下降方向 ( 2 ) 光滑化牛顿法 光滑化牛顿法开始于2 0 世纪9 0 年代早期，随着人们对非光滑研究的深入，该方法的 研究得到迅速发展，并成为最优化领域中极为活跃的研究方向之一【9 】学者们通过引入光 滑逼近函数，构造了各种光滑化牛顿算法光滑化牛顿法的基本思想是首先把一个互补问 题转化一个与之等价的非光滑方程组h ( x ) = 0 ，其中h ：研_ 研克服日非光滑性的 一种途径是利用光滑函数饥( z ) ( p 0 ) 逼近非光滑函数h ( z ) ，称巩( z ) 是h ( x ) 的光滑 逼近函数，这样可以用n e w t o n 型方法，通过求解光滑方程组e ( z ) = 0 的解来逼近原方 程组h ( x ) = 0 的解，这类方法称为光滑化方法为了使求解过程的代价降到最低，一般用 近似于牛顿法的迭代格式 扩= 一或( z 詹) _ h ( x 七) ， z 七+ 1 = z 南+ a 七d k ， 方向d 七一般称为光滑牛顿方向 求解非线性互补问题的光滑化牛顿法主要有三种：j a c o b i 光滑化方法、修正j a c o b i 光滑化方法及完全光滑化方法这三种方法的局部超线性及二次收敛性依赖于方程组在解 点处的半光滑性( 强半光滑性) 及其广义j a c o b i 矩阵在解点处的非奇异性一般来说，解的 r 一正则性可保证广义j a c o b i 矩阵在解点处的非奇异性，而函数f 的一致p 一性质可保证 水平集的有界性 在j a c o b i 光滑化方法中，参数p 需要严格的迭代规则1 9 9 8 年c h e n ，q i 和s u n m 提出的j a c o b i 光滑化方法是第一个求解非光滑方程组全局收敛且具局部超线性收敛率的 算法该方法要求西p ( z ) 是西( z ) 的一致光滑逼近函数，圣p ( z ) 满足j a c o b i 相容性条件且 适用于f 为岛一函数基于这个算法，1 9 9 9 年k a n z o w 和p i e p e r 1 3 把此算法运用到求解 互补问题中，给出了另一求解一般非线性互补问题的j a c o b i 光滑化算法，由于梯度步的引 入，该方法可求解一般的非线性互补问题j a c o b i 光滑化算法的可行性及收敛性依赖于水 平集的有界性及或。( z 奄) 的非奇异性，因而通常要求f 是一致p 一函数且f 7 ( z ) 是p 一矩 阵为减弱收敛性条件，需对这一算法进行改进，从而得到修正j a c o b i 光滑化方法【圳修 正j a c o b i 光滑化方法的基本思想是在牛顿方向提供满意的下降量时，参数肛自动调节，当 使用某一效益函数的负梯度方向作为搜索方向时，参数肛需要遵守类似于j a c o b i 光滑化 3 内蒙古大学硕士学位论文 方法中的迭代规则m a ”，1 6 】将这种思想推广到非线性及混合互补问题的b r o y d e n 类算法 对n c p ( f ) 在水平集凸有界，f 光滑，v f 在水平集上l i p s c h i t z 连续及解满足c d 一正则 条件下算法超线性收敛，而对混合互补问题还需解满足严格互补条件才能得到超线性收敛 性 完全光滑化牛顿法与j a c o b i 光滑化方法的区别在于：在j a c o b i 光滑化方法中，光滑 因子p 被视为参数，需要严格的迭代规则使其下降并趋于0 ，而在完全光滑化方法中，把弘 看作与z 同等夏要的变量加以迭代q i ，s u n 和z h o u 2 9 】首次提出求解非线性及互补问题 的完全光滑化牛顿法，算法在每次迭代中只须求解一个线性方程组和进行一次线搜索对 于非线性互补问题，在f 是啦上的一致p 一函数的假设下，算法具有超线性或二次收敛 性为减弱全局收敛性条件，z h a n g ，h a n 和h u a n g 1 | 7 l 采用对称扰动f i s c h e r b u r m e i s t e r 函数，对扁一非线性互补问题提出的光滑化牛顿法不需要假设迭代序列的聚点存在而全局 收敛在解的c d 一正则条件下，算法超线性或二次收敛2 0 0 8 年，h a n g 和g u 1 8 l 为单调 l c p ( q ，m ) 构造了增广系统，并用光滑牛顿法求解该系统，算法的全局收敛性并不需要对 最优解集进行假设若线性互补问题有可行解，则算法产生问题的解或可以检验出问题解 的存在性，进而可以用现存的光滑化方法求解；否则算法可以判断此问题无解 2 内点法 内点法是求解线性规划问题的十分有效的算法，它具有多项式复杂性内点法的思想 最早可追溯到2 0 世纪5 0 年代，2 0 世纪6 0 年代也曾有人进行过研究但是，第一个具有 多项式复杂性和实用性的内点法是由k a r m a r k a r 于1 9 8 4 年首先提出的此后2 0 年，经 过众多优化专家的共同努力，对内点法的研究取得了丰硕成果：不仅建立了完善的理论体 系，而且开发出高效的数值软件如今，内点法被推广到求解单调互补问题、凸或非凸规划 问题等，详见近期综述文献 3 5 】下面介绍的主要是求解线性互补问题的内点法【5 】它的基 本思想是把互补问题转化为一个与之等价的非负约束方程组，然后用牛顿类方法求解常 见的内点法有路径追踪法、势缩减法、预测一校正法、不可行内点法等 互补问题( 1 1 ) 可以转化为求( z ，y ) 皿2 n 使得 rt t 口，1 h ( x ，y ) = i“二，、l = 0 ，s t z 0 ，y 0 l 可一，。【z ) j 当f ( x ) = m x + q 时，仅第一个方程是非线性的，且带有特殊形式的表达式，当f 是尸。一函 数时，j a c o b i 矩阵非奇异，从而在迭代中可以取牛顿方向作为搜索方向给定点 七，y k ) 忸强，内点法的一般迭代格式为 x k + l y 抖1 ) = ( z 南，y 知) + k ( 遴，砖) ， v h ( x k , y 南) 扩= 一百( z 南，y 七) ，d 南= ( 趁，砖) 4 内蒙古大学硕士学位论文 其中日( 矿，y 七) 是由h ( x 七，y 七) 经过一个微小扰动得到的，目的是调节迭代的收敛速度；a 七 为步长，它的取法使新得到的点( z 1 ，y 1 ) r ，并且价值函数有充分下降如果在迭 代过程中能保证y 七= ：( 2 7 七) ，k = 0 ，1 ，则称为可行内点法；否则称为不可行内点法 内点法具有大范围收敛性、局部超线性收敛性和多项式时间复杂性 3 非内点磨光算法 非内点磨光算法是一类特殊的光滑化方法，首先由c h e n 和h a r k e r 3 6 于1 9 9 3 年提 出与前面的j a c o b i 光滑化方法和完全光滑化方法相比较，它增加了线性调节p 的程序 及保证迭代点列在解的邻域内在文献f 3 6 1 中，c h e n 和h a r k e r 对m 是对角元素为正的 局+ 一矩阵的线性互补问题l c p ( q ，m ) ，着重考察了考察了摄动方程组的解构成的中心 路径的存在唯一性，但未提供其算法的收敛性证明1 9 9 6 年，k a n z o w 3 7 1 对线性互补问题构 造了与文献 3 8 】不同的磨光函数，并在m 为r + 一矩阵的假设下，证明了其算法的全 局收敛性鉴于此，有些学者把这类磨光函数称作c h k s ( c h e n - h a r k e r - k a n z o w - s m a l e ) 函 数近年来，用磨光方程组法解互补问题的文章有很多，h u a n g ，h a n 和c h e n 4 1 j 利用扰动 的极小化函数给出了磨光函数 砂( p ，a ，b ) = ( 1 + p ) ( o + b ) 一、( 1 一p ) 2 ( n 一6 ) 2 + 4 p 2 该光滑函数可保证迭代点列的有界性基于这一磨光函数构造了估计校正( p r e d i c t o r c o r r e c t o r ) 磨光牛顿法，对于r 一函数非线性互补问题，在最优解集非空有界的条件下全局 收敛，在解的c d - 正则条件下超线性收敛h u a n g 和s u n 19 】利用正则c h k s 光滑函数及 正则化技术将线性互补问题转化为光滑方程组，提出非内点连续化方法当m 为局一矩 阵且解点满足c d 一正则条件( 此时不需要假设严格互补条件) ，算法全局线性及局部二次 收敛 4 投影法 投影法是求解互补问题的一类基本而又重要的计算方法它源于g o l d s t e i n l e v i t i n - p o l y a k 的求解凸约束优化问题的梯度投影法，包括著名的外梯度法、逐点逼近法、矩阵分 裂法等其基本迭代格式为 z + 1 = p r x x 知一c e f ( 2 7 七) 】， 这里q 0 为给定的常数，对于非线性互补问题，上述迭代格式简化为 z 七+ 1 = i x 七一a f ( 2 7 七) 】+ 由b a n a c h 不动点定理可以证明，当f 为强单调，全局l i p s c h i t z 连续的函数当q 充分小 时具有全局收敛性虽然这类方法最多只有线性收敛速度，但它的运算量小、存储量小、 保稀疏性，因此也一直受到人们关注，特别是对计算大型互补问题投影法的文献也很多， x i u 和z h a n g 给出了最新的综述报告m 5 内蒙古大学硕士学位论文 1 2 本文的主要工作及内容安排 本文t 要完成了如下工作： 在将非线性互补问题转化为与之等价的非光滑方程组f ( 矿) + z 一= 0 ( 此方程称为 n c p ( f ) 的法方程) 的基础上，给出了新的光滑逼近方程组，它是方程组f ( x + ) + x 一= 0 的光滑逼近形式还研究了这个新的光滑逼近方程组的一些性质，并在此基础上给出了求 解非线性互补问题的一步光滑化牛顿法，在互补问题解集非空有界和函数f ( x ) 为r 一函 数的假设下，证明了该算法的全局收敛性和局部收敛性而且还证明了我们提出的算法 有以下好的性质：( a ) 算法有意义且由算法生成的迭代序列任何聚点都是( 1 1 ) 的解，而且 当( 1 1 ) 的解集是非空有界集时迭代序列是有界的；( b ) 我们的算法只需要求解一个线性方 程组和执行一次线搜索；( c ) 当迭代序列的聚点满足c d 一正则假设时，迭代序列在无严格 互补条件假设下全局收敛且局部超线性收敛特别地，如果f 的j a c o b i 矩阵是l i p s c h i t z 连续的，那么算法具有局部二次收敛性 本文共分为四章，内容安排如下：第一章是绪论部分，介绍互补问题的应用背景和有 关互补问题的求解方法；第二章是基本理论，给出本文所要用的主要概念、符号、术语和基 本结论；第三章为本文的重点，着重研究了求解非线性互补问题的光滑化算法及其收敛性， 并通过互补问题的典型数值算例，说明了本文算法的有效性；第四章是对本文的总结 1 3 符号介绍 为了便于阅读，现对本文中出现的符号加以说明： 1 v 表示对任意的，j 表示至少存在一个，表示属于 2 皿表示实数集，皿+ ，皿+ + 分别表示非负实数和正实数，记n = 1 ，2 ，n ) 3 彬表示n 维欧氏空间，啦表示衍中的非负卦限，即癣= ( z 1 ，x 2 ，x n ) t ： x i 0 ，i ) ；癣+ 表示衍中的正卦限，即啦+ = ( z 1 ，x 2 ，z n ) t ：觑 0 ，i 4 表示衍中的向量范数 5 v ，表示，( z ) 的梯度；，( z ) 表示f 在z 的j a c o b i 矩阵 6 f 7 ( z ；h ) 表示f 在点x 卿处沿方向h 脚的方向导数 7 o 表示高阶无穷小，d 表示同阶无穷小 8 v e c ? ) i ：i 1 表示元素为仇的列向量u 所有的向量都是列向量为了简单，使 用( “，v ) 表示列向量( 矿，沪) t 9 a t 表示矩阵a 的转置，矩阵，表示任意维数的单位矩阵，d i a g a 1 ，a 2 ，n n ) 表 示对角线元素为a 1 ，o 2 ，a 钆的对角矩阵 1 0 b ( z ，e ) = y 研：i l y z l i 0 为半径的邻域 6 第二章预备知识 本章第一节给出了后面将要用到的一些基本概念和性质，第_ 二节给出了互补问题的解 的存在性、唯一性和解集的有界性 2 1 基本概念和结论 定义2 1 1 a o l 设m 为礼礼矩阵，称m 为 ( i ) 正定矩阵，如果x t m x 0 ，对任意0 z 研成立； ( i i ) 半正定矩阵，如果x t m x 0 ，对任意z 砑成立； ( i i i ) p 一矩阵，如果m 的所有主子式皆为正实数； ( i v ) 局一矩阵，如果m 的所有主子式皆为非负数； ( v ) 矩阵，如果线性互补问题l c p ( o ，m ) 只有零解 容易看出，半正定矩阵必为疡一矩阵，正定矩阵必为p - 矩阵，所以岛一矩阵与p - 矩阵 分别是半正定矩阵与正定矩阵的推广p - 矩阵既是局矩阵又是风矩阵 引理2 1 1 【1 0 l 设m 衍加，则下条件是彼此等价的： ( i ) m 为昂一矩阵； ( i i ) 1 s 。m s 叩a x ；u x i ( m z ) o vz 衍，z o ； ( i i i ) m 及其所有主子矩阵的所有实特征值非负； ( i v ) 对任意e 0 ，m - t - e j 为p - 矩阵 引理2 1 21 5 , 1 0 设m 舒黼，则下条件是彼此等价的： ( i ) m 为p 一矩阵； ( i i ) 1 娜m a 忍x u x i ( m z ) i 0 vz 衍，z o ； ( i i i ) m 及其所有主子矩阵的所有实特征值为严格正； ( i v ) 线性互补问题l c p ( q ，m ) 对任意q 衍有且仅有一个解 定义2 1 21 1 0 1 设f ：毋一衍，称f 为 ( i ) p o 一函数，若 1 鳓m a 而x 鼽( 甄一玑) 阮( z ) 一只( 可) 】o ， vz ，y 砑，z 秒； ( i i ) p - 函数，若 1 m a x 。( x i 一玑) 限( z ) 一只( 秽) 】 0 ，vz ，y r n ，z 掣； 7 内蒙古大学硕士学位论文 ( i i i ) 一致p - 函数，若存在常数p 0 ，使得 凹野( x i y i ) f i ( x ) 一只( y ) 】工, l l x y l l 2 ，vz ，y 皿妒； 1 二= 7 ( i v ) 单调函数，若( z 一可) 丁f ( z ) 一f ( 秒) 】0 对任意z ，y 衍成立； ( v ) 严格单调函数，若( z y ) r 【f ( z ) 一f ( 可) 】 0 对任意z ，y 研，z y 成立； ( v i ) 强( 一致) 单调函数，若存在常数p 0 ，使得( z y ) t 旷( z ) 一f ( 可) 】工, l l x 一训2 对任意z ，y 衍成立 由定义可得出：单调函数必为r 一函数，严格单调函数必为p - 函数，强单调函数必为 一致p - 函数 引理2 1 31 1 0 1 设f 为连续可微函数，则： ( i ) f 为岛一函数当且仅当f 的j a c o b i 矩阵f 7 ( z ) ( v z 衍) 为局一矩阵； ( i i ) 若f 的j a c o b i 矩阵f 7 ( z ) ( 研) 为p 矩阵，则f 为p - 函数； ( i i i ) 若f 是一致p 函数，则jp 0 ，使得 心m a 。x 。y i ( f 仕) 可) p i i y l l 2 ，vz ，y 用n 定义2 1 3 【5 l 对于给定的l c p ( q ，m ) ，点z 衍，若瓤( m x + 口) i ，i n ，则点z 被称为非退化的若l c p ( q ，m ) 的一解z 是非退化的，则称解z 有严格互补性 引理2 1 4 ( 毗d e m a c h e r 定理) 设xc 皿n 是一个开集，h ：x _ 丑妒在x 上局部 l i p s c h i t z 连续，则日在x 内几乎处处可微记d h 为日的可微点集 定义2 1 4b o 设h ：r n _ 毋在z 衍上局部l i p s c h i t z 连续，则集合 0 h ( z ) 一出凛日k 知) ) 称为日在z 衍处的b 一微分如h ( x ) 中的元素称为日在z 处的b 一导数集合 如h ( x ) 的凸包 i ) h ( x ) = c o ( o b 日( z ) ) 称为日在z 彬的( c l a r k 意义下的) 广义j a c o b i 矩阵集 如所知【2 u ，当日在z 局部l i p s c h i t z 连续时，o h ( x ) 为非空凸紧集，如日( z ) 为非空紧 集若任意v 如日( z ) 均非奇异，则称日在z 点b d 一正则若任意v o h ( x ) 均非奇 异，则称日在z 点c d 一正则 8 内蒙古大学硕士学位论文 定义2 1 5 【5 1 设h ：研_ 衍在z 研上局部l i p s c h i t z 连续，如果极限 ，l 砷 v h 7 ：v o h ( x + t h ，) ) h 7 ，i t l o 7 对任意的0 h 衍都存在，则称h ( x ) 在点z 卯处半光滑如果h ( x ) 在劈的 每一点都半光滑，则称h ( z ) 在研上半光滑若日在z 御半光滑且满足 i i h ( x + h ) 一h ( z ) 一y h l i = o ( 1 l h l l 2 ) ，vv o h ( x + 九) ，i i h l l _ o ， 则称h ( x ) 在点z 处强半光滑 向量函数h ( x ) = ( h 1 ( z ) ，吼( z ) ，风( z ) ) r 在z 衍半光滑当且仅当所有分量 函数日1 ，凰，玩在z 半光滑半光滑函数介于光滑函数类和l i p s c h i t z 函数类之间， 所有光滑函数、凸函数、分片光滑函数均是半光滑函数，半光滑函数的和、羞、积及复合 运算也是半光滑的常见的n c p 函数m i 。a ，b ) = m i n a 6 ) 和f i s c h e r b u r m e i s t e r 函数 f b = 、了百一( a - 4 - b ) 均在皿2 上半光滑l 圳 引理2 1 5f 3 9 】设日：衍一衍在点z 研是局部l i p s c h i t z 连续的，则 ( i ) 日( ) 存在广义j a c o b i 矩阵o h ( x ) ( c l a x k e 意义下) ，如果何在点z 衍半光滑， 则对任意h 御，日在z 沿方向h 的方向导数存在此外，h o 衍_ 腑在点z 厨 半光滑，当且仅当其分量在点z 研半光滑： ( i i ) 日( ) 在z 半光滑当且仅当对任意v o h ( x + ) ，h _ 0 i i y h 一日7 ( z ；h ) l i = o ( 1 l h l l ) ， 或 i i h ( x + h ) 一h ( x ) 一日7 ( z ；h ) l l = o ( 1 l h l l ) ( i i i ) 日( ) 在z 强半光滑当且仅当对任意v o h ( x + ) ，h _ 0 i i y h h 7 ( z ；h ) l l = o ( 1 l h l l 2 ) ， 或 i i h ( x4 - h ) 一h ( x ) 一h 7 ( z ；h ) l i = o ( 1 l h l l 2 ) 命题2 1 1 【3 9 】若日在点z 衍，b d 一正则，那么 ( i ) 必存在 0 ，c 0 使对任意y b ( x ，) ，所有v 如日( 剪) ，非奇异且 i i y _ 1 i l c ( i i ) 进一步，若h ( x ) = 0 且日在z 半光滑，则存在手 0 ，c 2 c 1 0 使 c l l l y x l l i i h ( y ) i i c 2 l l y x l l ，vy b ( z ，日 9 内蒙古大学硕士学位论文 与非光滑函数密切相关的另一重要概念是光滑化函数 定义2 1 6 【2 2 l 设h ：研一研在z 砑为局部l i p s c h i t z 函数，称光滑函数 皿：研_ 衍为日的光滑化函数，若对任意 0 ， 。l 。i r a 皿( 可) = 日( z ) ，vz 卫秒 l u ，y - - - , x 定义2 1 7 ( 5 j 设函数h ：彬_ 衍，称光滑函数皿( ) ：衍一衍( 0 ) 为的 光滑逼近函数，如果对任意x 刀，存在l 0 ，使得 i i 皿( z ) 一h ( x ) i i l e ，v 0 若l 0 不依赖于z ，则称皿( ) 为的一致光滑逼近函数 定义2 1 81 5 1 设h ：衍一即是局部l i p s c h i t z 函数，则h 在z 劈处的d 次 微分定义为： o c h ( x ) r ：= o h i ( x ) o h 2 ( x ) a 月( z ) 注：d 次微分与c l a r k e 广义j a c o b i 矩阵o h 有如下关系 o h ( x ) 晚日( z ) 定义2 1 91 5 】设h ：劢_ 毋劢是局部l i p s c h i t z 函数，如果它的光滑化函数 皿( ) 满足下述条件：对任意z 衍，有 l 山i md i s t ( 匙( z ) ，o c h ( x ) ) = 0 ， 则称光滑化函数皿( ) 与日( ) 满足j a c o b i 相容性 定义2 1 1 01 5 】称x + 为n c p ( f ) 的严格互补解( 或非退化解) ，如果x 是n c p ( f ) 的 解且满足 z ：+ 只( z + ) 0 2 2 互补问题的解的存在性、唯一性和解集的有界性 定理2 2 1 【1 】对于线性互补问题l c p ( q ，m ) ，设m 是一半正定矩阵，则对任意q 衍，若l c p ( q ，m ) 有严格可行点，则l c p ( q ，m ) 的解集存在且有界 定理2 2 2 【5 】矩阵m 是一p 一矩阵，当且仅当对于任意q 开，l c p ( q ，m ) 有唯一 解 1 0 内蒙古大学硕士学位论文 定义2 2 1 【5 】l c p ( q ，m ) 的一解z + 被称为局部唯一解( 或孤立解) ，如果z 。存在一邻 域，在此邻域内l c p ( q ，m ) 只有解z 推论2 2 11 5 l 对于任意q 衍，l c p ( q ，m ) 的解均是局部唯一解当且仅当对于任意 q r ，l c p ( q ，m ) 只有有限多个解 定理2 2 3 【3 8 】设m 是r 一矩阵，如果m 又是一矩阵，则 ( i ) l c p ( q ，m ) 对任意q 研有严格可行点； ( i ) l c p ( q ，m ) 对任意q 衍有非空解集 对于非线性互补问题n c p ( f ) ，其解的存在性和唯一性的研究不能借助于二次规划 性质，而需要其它方法考虑f 是定义在一般闭凸锥中的广义互补问题 定义2 2 2 5 1 设cc 衍是一非空子集， ( 1 ) 称c 是一锥，如果x c ，则入z c ，v a 0 显然零点属于锥c ( 2 ) 称c 是一凸锥，如果z c ，y c ，则a z + p 秒c ，v a ，p 0 ( 3 ) 称c 是有尖点的，如果z c ，z 0 ，则一zgc ( 4 ) 称c 是立体的，如果c 有内点 显然殿是开中的有尖点的立体闭凸锥 定义2 2 3 【5 1 设cc 皿n 是一非空子集，称伊= 秒艉n ：y t x 0 ，v 2 c ) 为c 的对偶锥 定义2 2 4 【5 】设cc 衍是一有尖点的立体闭凸锥，伊是c 的对偶锥，f ：c _ 乃 是一非线性映射，定义在c 中的互补问题是指：求一点z ，满足 z c ，f ( x ) c ，x t f ( x ) = 0 记为c p ( f ，c ，c ) 定理2 2 4 【5 】设f ：丑珥_ 皿n 是尸一映射，则n c p ( f ) 至多有一个解( 也可能无解) 定理2 2 5 【5 】设cc 衍是有尖点的立体闭凸锥，则 ( i ) f ：c 一衍是连续单调映射，若广义互补问题有严格可行点，则c p ( f ，c ，c ：) 有 解： ( i i ) f ：c _ 乃是连续严格单调映射，若广义互补问题有可行点，则c p ( f ，c ，c + ) 有 且仅有一个解： ( i i i ) f ：c 一皿n 是连续强单调映射，则c p ( f ，c ，c + ) 有唯一解； 1 1 内蒙古大学硕士学位论文 解集的非空有界性是互补问题的许多求解算法收敛性的基础强制性条件是保证解集 非空有界的一个经典条件 定义2 2 51 1 0 1 设f ：xc 一衍_ 衍，称f 在x 强制，若存在z o x 使得 i l x l l - = + ， i l z i l 定理2 2 6 【5 1 设cc 衍是有尖点的立体闭凸锥，f ：c 一衍是连续映射，满足强 制性条件，则对于任意q 劈，互补问题c p ( f4 - g ，c ，c + ) 有解且解集有界 1 2 丛一立 弟二草 3 1 求解非线性互补问题的光滑化牛顿法 光滑逼近函数的构造及其性质 在以下的讨论中假定f 是光滑的一致p 一函数如所知【3 列，非线性互补问题n c p ( f ) 等价于如下的非光滑方程组 f ( x + ) + z 一= 0 ( 3 1 ) 其中z = m a x 0 ，z t ) ，z f = m i n 0 ，z i ) ，z + = ( z ，z 手，z ：) r ，z 一= ( z f ，x 2 一，z 二) t 即方程组( 3 1 ) 的解和n c p ( f ) 的解之间有一个一一对应，换言之，z 是方程组( 3 1 ) 的解当 且仅当z + 是n c p ( f ) 的解【3 2 鉴于直接求解非光滑方程组( 3 1 ) 的困难，考虑构造光滑逼 近函数对任意t r ，e 0 ，定义 u ( ，z ) v ( e ，t ) = - - i n ( 1 + e 其中 0 为光滑参数当= 0 时，补充定义 t 0 ， 0 z e t e ， 一) ， u ( o ，) = 矿，v ( o ，) = t 一 ，t ，= 三争 三三三 0 时这两个光滑函数的性质 引理3 1 1 对任意 0 ，有 l 让( ，t ) 一t + i 丢，vz 皿 证明山让( ，z ) 的定义，分以下三种情形讨论： ( i ) 当t 0 时， l u ( e ，t ) 一t + l = o ； ( i i