（计算数学专业论文）求解互补问题的一种修正的光滑newton法.pdf

摘要 互补问题自1 9 6 3 年首次提出以后便得到了广大研究者的重视，直是数 学规划研究中较为活跃的分支，在求解互补问题的算法的研究领域也取得了丰 硕的成果 本文一方面基于现有的各种光滑n e w t o n 法的思想和半光滑理论，利用著 名的f - b 互补函数的光滑形式，首先将互补问题的求解转化为求解一系列光滑 的非线性方程组，然后给出了种修正的光滑n e w t o n 法，该方法不仅放宽对函 数，的要求，在n e w t o n 方程不可解时引入初始效益函数的最速下降方向，而且 光滑因子的选择也比较简单可行，同时在适当的条件下，证明了其算法具有全 局收敛性；另一方面，借助另一种f b 光滑函数，将多面体锥上的广义互补问 题转化为一种光滑形式，讨论了优化问题的稳定点与广义非线性互补问题的解 之间的理论关系，并将这种修正的光滑n e w t o n 法用于求解广义非线性互补闯题 中，在适当的条件下，该算法同样具有全局收敛性 全文共分为四章，各部分内容安排如下：第一章是绪论部分，介绍了互补 问题的应用背景和近年来有关互补问题求解方法的研究成果；第二章是预备知 识，介绍了与求解互补问题有关的一些定义以及相关的定理和推论；第三章是 本文的重点，提出了求解互补问题的一种修正的光滑n e w t o n 算法，从理论上对 算法的全局收敛性了证明；第四章是这种修正的光滑n e w t o n 法用于求解广义非 线性互补问题中，同样证明了算法的全局收敛性最后，总结了全文研究的内容， 指出了还没有研究清楚的一些领域，提出了进一步研究的方向 关键词：非线性互补问题，广义互补问题，修正的光滑n e w t o n 法，收敛性 a b s t r a c t c o m p l e m e n t a r i t yp r o b l e mw a s f i r s tp r o p o s e di n1 9 6 3 s i n c et h e ni th a sb e e nt h e h o ts p o ti nt h er e s e a r c ho fm a t h e m a t i c a lp r o g r a m m i n g a l s om a n ya l g o r i t h m sh a v e b e e np r o p o s e d w i t ht h ei d e ao fs m o o t h i n gn e w t o nm e t h o d ，w ep r o p o s ean e wc l a s so f s m o o t h i n gn e w t o nm e t h o d sf o rt 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 mb a s e d0 1 3a c l a s so fs p e c i a lf u n c t i o n s i nt h i sp a p e r , c o m p l e m e n t a r i t yp r o b l e mi sc o n v e r t e di n t oa s e r i e so fs m o o t h i n gn o n l i n e a re q u a t i o n sa n dam o d i f i e ds m o o t h i n gn e w t o na l g o r i t h mi s u s e dt os o l v et h ee x l u s t i o n s w eu s en e w t o nd i r e c t i o na n dg r a d i e n td i r e c t i o nt o g e t h e r i nt h ea l g o r i t h mw h i c h g u a r a n t e e st h a to u rm e t h o di sg l o b a l l yc o n v e r g e n t a l s ou s i n g a n o t h e r s m o o t h i n gf u n c t i o n , w e r e f o r m u l a t et h e g e n e r a l i z e d n 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 m sd e f i n e d0 1 1ap o l y h e d r a lg o n ea sas y s t e mo fs m o o t h i n g e q u a t i o n sa n das 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 np r o b l e m t h o o r e t i c a lr e s u l t st h a t r e l a t et h es t a t i o n a r yp o i n t so ft h em e r i tf u n c t i o nt ot h es o l u t i o no ft h eg e n e r a l i z e d 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 sa r cp r e s e n t e d , w eu s et h em o d i f i e ds m o o t h i n g n e w t o na l g o r i t h mi ng e n e r a l i z e dn 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 , u n d e rm i l d h y p o t h e s i s ，ag l o b a lc o n v e r g e n c ei sp r o v e d t h ep a p e rc o n t a i n sf o u rp a r t s i nt h ef i r s tc h a p t e r , t h ea p p l i c a t i o nb a c kg r o u n d a n dt h em a i na l g o r i t h m so f t h ec o m p l e m e n t a r i t yp r o b l e m si si n t r o d u c e d i nc h a p t e r2 ， s o m cb a s i cd e f i n i t i o n sa n dt h e o r i e so fe n m p l e m e n t a r i t y p r o b l e m sa r ei n t r o d u c e d t h e 3 r dc h a p t e ri st h em o s ti m p o r t a n tp a r to ft h i sp a p e r , i nw h i c ham o d i f i e ds m o o t h i n g n e w t o nm e t h o di sd e t a i l e d ；a l s ot 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 df o rt h em e t h o d i nt h e4 t hc h a p t e r , w eu s et h em o d i f i e ds m o o t h i n gn e w t o na l g o r i t h mi ng e n e r a l i z e d 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 。i nt h el a s tc h a p t e r , w cc o n c l u d et h ep a p e r 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 y p r o b l e m ,g e n e r a l i z e dc o m p l e m e n t a r i t y p r o b l e m ，m o d i f i e ds m o o t h i n gn e w t o na l g o r i t h m ，c o n v e r g e n c e i i 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包括其他人已经发表或撰写过的研究成果，也不包 括为获得武汉理工大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 签名：骂二塾垒日期：迎互碰：筘 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定， 即学校有权保留、送交论文的复印件，允许论文被查阅和借阅；学校 可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手 段保存论文。 签名： 定) 型型乙f i 窍 武汉理工大学硕士学位论文 第1 章绪论 本章简要介绍了互补问题的类型和求解互补问题的算法的最新研究成果， 以及本文的主要工作 1 1 互补问题 互补问题( c o m p l e m e n t a i r i t yp r o b l e m ，简记为c p ) 是由c o t t l e 于1 9 6 3 年首次提 出耐，而i , o m k e 在1 9 6 5 年正式提出了互补理论近四十年在数学和工程科学 中互补问题得到了充分的发展 1 1 1 互补问题的引入 互补问题是指这样的问题，它包含的两组决策变量之间满足一种“互补关 系”互补关系反映了广泛存在的一种基本关系根据问题中变量所满足的条件 的不同，以及互补关系的不同形式，互补问题被区分为若干类型下面列举几种 常见的数学形式 线性互补问题 令m r 是- - 7 x 挖实矩阵，q 霆。是一撑维矢量，线性互补问题是：寻求 解工r 1 ，满足 j o ，m x + q 2 0 ，j 1 ( 缸+ g ) = 0 线性互补问题被记为l c p ( m ，g ) 如引入矢量y r 4 ，y = m x + q ，则变量而与几 满足条件t 0 ，y i 0 ，x i y ；= o ( i = 1 ，2 ，1 ) 这表明了两组变量k ) 与秒。) 满 足互补关系线性互补问题的基本来源是线性规划与二次规划考虑二次规划 ( q p ) ： m i n q ( x ) = c - x + 1 - x 7 劣 二 s t a x b ，x 2 0 其中q r ”4 为对称矩阵，a e r ，如果q = 0 ，二次规划即退化为一线性规 武汉理工大学硕士学位论文 划设工是二次规划( 9 p ) 的一局部最优解，根据勋r u s h - k u h n - t u c k c r 最优性定 理，存在l a g r a n g e 乘子矢量，满足k _ k t 条件： j “= c + q x a 7 ) ，o - x o ，j 7 = 00 1 1 ) 【v = 而+ i x o ，y o ，y 7 y = 0 如q 是半正定矩阵( 如q = 0 ) ，则q o ) 是凸函数，条件( i i 1 ) 也是( q p ) 的全局 最优解的充分条件 令 m = q - a t a 0h 匀b ii 1 卜i 符号“：= ”表示定义条件( 1 1 1 ) 即转化为一线性互补问题三c p ( m ，d ，其中包 含的矩阵肘是一双对称( b i s y m m e t r i c ) 矩阵所以任意一个二次规划的k - k - t 条件等价于一线性互补问题，而且凸二次规划与线性规划等价于一线性互补问 题 广义线性互补问题 令m 。m ：r 为两矩阵，pcr “为一多面体广义线性互补问题是；求 工，y r “，满足 工o ，y 0 ，m l x - m y p ，工7 y = 0 广义线性互补问题被记为e l c p ( m 。，m ：，p ) 当所= 力，且p = g 时，即多面体 退化为一点q ，贝j e l c p ( m ，m ：，p ) 化为一水平线性互补问题 一般的广义线性互补闯题 令m 。r “4 和m ：r ”为两矩阵，b e r 和b 2 r 。为两矢量， a i ( i = l ，r ) 是 l ，s ) 的一子集一般的广义线性互补问题是：求矢量 工尺”，满足 m l x b 1 o ，m 2 j = b 2 丌( 吖，工一b 1 ) ，= o 一般的广义线性互补问题被记为g e l c p ( m 。，m ：，b t , b 2 , 娩 ) 这种互补问题是 由b d es c h u t t e r 和b d em o o r 提出条件兀( m 1 工一b 1 ) = o 反映了一种互 净jj 许 2 武汉理工大学硕士学位论文 补关系因m 。x - b 1 0 ，此互补关系说明：对于解x 存在一工够( f = 1 ，2 ，) ， 使得( m l x - b 1 ) = 0 非线性互补问题 令，：掣_ r 4 是由r ”到r ”的一映射，相应的非线性互补问题是：求矢量 x r 4 满足 工0 ，f ( x ) 0 ，( 曲= 0 ( 1 1 2 ) 非线性互补问题被记为n c p ( f ) 当映射f 是线性映射时，即f ( x ) = m x + q ，则 非线性互补问题化为线性互补问题l c p ( m ，q ) 广义非线性互补问题 令g ，强掣寸震”是两个映射，广义菲线性互补问题是：求石r 5 ，满足 g ( 力o ，h o ) 2 0 ，g ( 工) 7 i - 1 ( x ) = 0 广义非线性互补问题被记为c p ( g ，日) 1 1 2 互补问题的算法 c o t t l e 等人于1 9 6 3 年首次提出互补问题次年，c o t t l e 便在他的博士论文中 第一次提出求解互补问题的数学规划算法互补问题的出现引起了人们浓厚的 兴趣，特别是8 0 年代中后期，随着科技与经济的发展，互补问题越来越重要， 成为了数学规划研究中的热点问题，同时也涌现出了许多求解互补问题的算法。 目前，线性互补问题的求解方法已经较为成熟，本文主要研究非线性互 补问题，常见的算法有： i 光滑方程法 这类方法就是把互补问题( 1 1 2 ) 转化为一个与之等价的光滑方程组，然后 用n e w t o n 类型法求解m a n g a s a r i a n 于1 9 7 6 年首先提出这种方法，它利用了如 下的势函数： 妒( 口，6 ) = 口( p 一6 i ) 一口( 口) 一护( 6 ) 其中0 ( 0 ：r r 是一个严格递增的函数，满足烈o ) = 0 m a n g a s a r i a n 构造了如 下的光滑方程组： 武汉理工大学硕士学位论文 g ( x ) ：= 伊( x 正( x ) ) 妒( x ：，f 2 叫；o ， ：l 绯。 ( x ) ) ( i 2 1 ) m a n g a s a r i a n 证明了互补问题( 1 1 2 ) 的解与方程组( 1 2 1 ) 的解之问的等价关系， 即，r “是互补问题( 1 1 2 ) 的解g ( x 。) = o 函数0 ( t ) 有很多，因而可以再生 出很多光滑方程为保证大范围收敛性，w a t s o n 建立了一个同伦算法 2 1 ( 取 烈f ) = t 3 ) s u b r a m a n i a n 则提出一个带阻尼因子的g a u s s - n e w t o n 法【3 1 ( 取 o ( 0 = t h ) ，k a n z o w 4 1 贝u 考虑了下面的2 n 阶光滑方程组 h 缸，协= ) 一，( 工) 妒( 王，曩( 谚 庐( ，c ( j ” 他给出了j a e o b i a n 矩阵v h o ，y ) 在n c p ( f ) 的非解点处可逆的几个充分条件 光滑方程法有一定的优越性，但是其缺点是，即使一个线性的互补问题， 转化后的方程组也往往是非线性的，并且非线性程度较高，这势必将导致理论 推导和实际计算的复杂化 2 非光滑方程法 众所周知，光滑方程的n e w t o n 方法在解点附近的超线性收敛性是建立在 该点的j a e o b i a n 矩阵非奇异基础之上的r o b i n s o n 把这一结果推广到变分与互 补问题中1 5 ，即引进了正则解的概念，又提出了r - 正则解，b 正则解，c d - 正 则解等概念 6 - 7 1 ，这些新的概念的引入在广义n e w t o n 法的超线性收敛性分析中 起到了很大的作用 p a n g 利用n c p 函数6 p l ( a ，b ) = m i n a ，( 取o ( t ) = 一o 5 t ) 将互补问题转化为 如下非光滑方程组【g l ： h 。( 功= r a i n “，巧o ) ) 酬而卜 r a i n 矗，c ( 力 p a n g 证明若f 连续可微，则h 。( 工) 是b 一可微的，由此他建立了一个带有非精 确线性搜索的广义n e w t o n 方法，其搜索方向以满足； 4 武汉理工大学硕士学位论文 蜀( x d + b h l ( 屯) d k = 0 ( 1 2 2 ) 其中b h 。( 以) 为h 。在点以处的b - 导数，p a n g 【8 】还证明了上述方法的大范围收敛 性和局部超线性收敛性( 在某种正则条件下) 一般来说，( 1 2 2 ) 中的n e w t o n 方 程是非线性的，不易求出d 为此，文【9 】提出了一个n e s q p 法，它仅求解一 个二次子规划可得d 。而后，文【1 0 】将该方法改造成仅求解一个线性方程组便可 得到以，但要保证迭代点在r ：+ = b r “k o j 内文 1 1 】用降势内点法求解一类 非负约束方程组( 事实上，变分不等式和互补问题均可归为此类问题) 1 9 9 2 年 f i s c h e r 引入了一个结构简单而又奇特的n c p 函数( 又称f i s c h e r - b u r m e i s t e r 函 数1 鲠( 口，6 ) = 4 a 2 + 6 2 - - a 一务 由此函数建立的n e w t o n 法所表现出来的良好的理论和数值计算结果引起了众 多学者的极大兴趣，出现了较多的文献【1 2 1 6 1 本文中光滑n e w t o n 法所用的函数 即为该函数的光滑化形式 3 无约束优化法 这种方法就是把互补问题转化为一个与之等价的可微无约束优化问题，然 后用某种大范围或n e w t o n 类型的算法来求解由于无约束优化的求解方法比较 成熟，因此，对这类方法的研究重心在于如何转化上 m a n g a s a r i a n 和s o l o d o v l l 7 1 先于他人给出了一个可微的势函数 中m ( x ) = x t f 如) + 去 o ( 川f ( x ) + 破1 1 ：- i i x l l ：+ o ( 吨石+ f ( 枷+ 卜i l f ( x ) 1 1 2 ) ( 口 o ) 实际上，o m 可以由可微的n c p 数 ，( a ，6 ) = d 6 + ：l ( m a x 2 0 ，a - a b - a 2 + m a x 2 o ，6 一c r 口) 一6 2 ) 按下式生成： o ( x ) = ( 墨，f a x ) ) ( 1 2 3 ) 文研究了( 1 2 3 ) 与互补问题( 1 1 2 ) 之间的关系，如果f ( 力是可微的且v f ( 矿) 正定，那么( 1 2 3 ) 的稳定点与( 1 1 2 ) 的解是等价的 近年来，对可微无约束优化法的研究兴趣转向增加非负约束，因为实际计 算表明，仅用无约束优化求出的互补问题的解并不理想为此m o r 6 给出了一个 武汉理工大学硕士学位论文 可行的信赖域方法【，w a n g - m o n t e i r o - p a n g 提出了一个降势内点法【1 5 】，这方面 的方法也逐渐增多，如文献【2 们1 i 4 投影法 投影法就是基于g o l d s t e i n l e v i t i n - p o l y a k 求解凸规划的梯度投影法的思想求 解互补问题，所以又称为g l p 投影法其基本迭代格式为 j t + i = 【屯一c e f ( x ) 】+ 这里口 0 为步长然而它的收敛性需要，是强单调的映射为此， k o r p e l e v i c h ( 1 9 7 6 ) 提出了外梯度法，即 以+ l = 【一o f f ( i x t a f ( x i ) 】+ ) 】+ 它的收敛住仅要求，( 石) 单调且解集x 非空s u n 应用a n n i j o 搜索技术得到，在 ，( x ) 伪单调且x 非空的假设下，迭代点列收敛到虽然这类方法最多只有线 性收敛速度，但它运算量小，存储量小，保稀疏性，受到了研究者的浓厚兴趣 2 2 - 2 3 i 最近，s o l o d o v 和t s e n g 给出了一个g l p 投影法的一般迭代格式幽1 t + = 以一，p 。 疋( 以) - r a x - u f ( x i ) 】+ ) 这里r 0 是步长，疋= ，一栌( 当f ( x ) = m x + q 时，l = i + t r m 7 ) ，口 o 使得疋 为强单调，p 是选取的正定矩阵 5 内点法 这是把互补问题转化为一个与之等价的非负约束方程组，然后用n e w t o n 类 型法求解它的研究起源于k a r m a r k a r 的求解线性与凸二次规划的内点法，也是 这种方法的自然延伸 互补问题( 1 1 2 ) 可以转化为如下的方程组 力= 眵 = o ， s t 砣岍。2 脚 显然，( 1 2 4 ) 是一个带有非负约束的2 n 阶非线性方程组，当f ( x ) = m x + q 时， 仅第二个方程是非线性的，且带有特殊形式的表达式；当f ( 曲是只函数时， j a e o b i a n 矩阵是非奇异的，从而在迭代中可以取n e w t o n 方向作为搜索方向给 定点o 。，y 。) r 冀，内点法的一般迭代格式为 ( 工“ ) ，i + 1 ) = ( x i ，y i ) + 以( d ：，d ：) 6 武汉理工大学硕士学位论文 v h ：( j 。，y t ) d = 一曰：( 石t ，y i ) ，d = ( d ：，d ：) 这里日：( x j ，y k ) 是由日：( ，y 。) 经过一个微小的扰动得到的，其目的是调节迭代 的收敛速度：五 0 为步长，它的取法使新得到的点o 。，y k + 。) r 三：并且效益函 数有一定程度的下降如果在迭代过程中能保证y 。= f ( 孔) ( 1 【= o ，1 , 2 ，) ，则称 为可行内点法【2 5 】；否则称为不可行内点法内点法具有大范围收敛性，局部超线 性收敛性和多项式时间复杂性 6 磨光方程与非内点法 前面的菲光滑方程法存在一个弱点，即方程胃( 工) = 0 的j a c o b i a n 矩阵 v h ( x ) 难于计算自然的，可以考虑用一个光滑函数h ( x ，口) 近似代替日( 曲( 这里 h ( x ，口) 称为磨光函数，口称为磨光参数，日o ) = 日( z ) ) ，这样可以转而求解 h ( x , o t ) = 0 如果在迭代过程中能自动调整a 到0 ，则称之为连续磨光方程进一 步，如果连续不断地压缩口到0 ，则称为非内点法后者具有路径跟踪法的主要 特征，但它能取任何初始点及充分选取步长，这恰好能克服内点法的弱点，所 以自它由c h e r t h a r k e r 于1 9 9 3 年提出以来，吸引了众多学者的注意，并取得 了迅速发展，如文献”删 1 2 广义互补问题 一般意义下的互补问题在工程力学，经济运筹学，不动点理论和最优控制理 论等理论中有广泛的应用，近十几年来成为运筹学研究的一个热门课题，并产生 了各式各样的有效算法随着对互补问题的研究，人们又提出了如下广义互补问 题 广义互补问题，记为g n c p ，是求，e r 4 满足 f ( x ) 茁，g ( x ) ，f ( x ) 7 g ( x ) = 0 其中，和g 是彤到r ”的连续映射，r 是彤中的非空闭凸锥，矿表示r 的极 锥 对于该闯题，若m = 行，1 c = 霹，g ( 力= x - - 蜀，其中：专掣为某一 函数，则g n c p 转化为隐式互补问题，也称为拟互补问题。”蚓特别地，若 g 0 ) = 石，则g n c p 转化为一般意义下的非线性互补问题同时，g n c p 与变分不 7 武汉理工大学硕士学位论文 等式问题有着密切的关系：若，可逆，则工+ g n c p ( f ，g ，r ) 的解等价于f ( x ) 是 v i ( g o f - , d 的解 为求鳃g n c p ，人们习惯于把它等价地转化为具有饲单约束的光滑优化问题 对于r 为一般闭凸锥的情形，t s e n g 等证明了若在，稳定点x 处的j a c o b i a n 矩 阵f ( p ) 非奇异，且g ( 矿) 【f 。( 矿) r 1 正定，则工为g n c p 的解恤1 基于这种转化形 式，可以利用下降算法来求解g n c p 对于r = 磁的情形，k a n z o w 与f u k u s h i m a 借助f i s c h e r 函数( ：r 2 专r 1 妒( 口，b ) = 口2 + 6 2 一a - b ，对任意a , b r ) 将g n c p 转化为无约束优化问题，并给 出了无约束最优化问题的稳定点茗为g n c p 的解的充分条件为，( 确可逆，而 且g ( 矿) 【，( 矿) 】- 为b 矩阵 利用与m 1 中相同的转化形式，j i a n g 等。”给出了无约束优化问题的稳定点 工为g n c p 的解的充分条件为f 1 ( 矿) 可逆，j l d ( g ( 一) ，( 矿) r ) 。d 为s o 矩阵， 并在此基础上给出了一个信赖域算法 我们主要考虑广义互补问题的如下特殊情形：f 和g 均为彤上的连续可 微函数，j r 为r ”中的多面体锥，即存在a r “，b r ”使得茁与矿分别有 如下表示形式： r = p e r ”1 4 v o , b v = 0 r 。= 缸r ”卜= 彳7 a + 艿7 如， e r s , 如e r 。j 对于上述情形，a n d r e a n i 等将g n c p 转化为如下带有简单约束的优化问题 【圳： m i n ，( 五乃= l l 足f ( 工) 一z l l 2 + 8 g ) - r 7 五l f 2 + 户怯， ) 2 s t z i o 五0 其中胄= ( ： ，z = ( i r x r 7 ，z = ( 主) r r 。 上述最优化问题的目标函数有非常简单的结构a n d r e a n i 。f r i e d l a n d e r 和s a n t o s 给出了一些使得上述优化问题的稳定点为g n c p 的解的充分条件汨“1 同时，由于上述目标函数可以使用g n c p 的函数f 和g 的导数信息，使得任意 8 武汉理工大学硕士学位论文 求解光滑简单约束优化问题的有效算法都可以用来求解上述约束优化问题 虽然上述最优化问题的目标函数有非常好的连续可微性质，但鉴于目标函数 的结构也使得它的h e s s i a n 矩阵比较复杂，从而难以建立其求解算法的超线 性收敛性为建立求解g n c p 问题算法的超线性收敛性，m a 等人借助f i s c h e r 函 数将g n c p 问题转化为一个非线性方程组，给出了求解g n c p 问题的 l e v e n b e r g m a r q u a r d t 超线性收敛性算法 1 ，3 本文主要工作 比较好的光滑n e w t o n 法有两类：其一是由戚，孙及周提出i 加】，另一个是由江 提出【4 “，这两种方法都将光滑参数看作与变量x 同等重要，p 的迭代与方向的 搜索过程有关；在文【4 2 】提出的方法中，作为参数进行直接的迭代，因而对 的迭代规则有所放宽，使得算法更易于实现，且算法是全局收敛的但是文暇】 中的n e w t o n 法需要函数f 是晶函数，当，是咒函数时，v h 。( 以) 有可逆性， 所以可由下列n e w t o n 方程：h 。( 屯) + 阳。( 以) h = o 确定迭代方向但是在 函数，条件较弱时，n e w t o n 方程未必可解，或者即使可解，得到的搜索方向也 不一定是很好的搜索方向本文针对n e w t o n 方程不可解时采取新的办法，主要 完成了如下两项工作： ( 1 ) 基于现有的各种光滑牛顿法的思想和半光滑理 论，利用著名的f i s c h e r - b u r m e i s t e r 互补函数的光滑形式，首先将非线性 互补问题的求解转化为求解一系列光滑的非线性方程组，然后给出了一种修正 的光滑n e w t o n 法，该方法不仅放宽对函数f 的要求，在n e w t o n 方程不可解时 引入初始效益函数的最速下降方向，而且光滑因子的选择也比较简单可行，同 时在适当的条件下，证明了其算法具有全局收敛性 ( 2 ) 借助另一种f - b 光滑函数，将多面体锥上的广义互补问题转化为一种光 滑形式，讨论了优化问题的稳定点与广义非线性互补问题的解之间的理论关系， 并将这种修正的光滑n e w t o n 法用于求解广义非线性互补问题中，在适当的条件 下，该算法同样具有全局收敛性 全文共分为四章，各部分内容安排如下：第一章是绪论部分，介绍了互补 问题的应用背景和近年来有关互补问题求解方法的研究成果；第二章是预备知 9 武汉理工大学硕士学位论文 识，介绍了与求解互补问题有关的一些定义以及相关的定理和推论；第三章是 本文的重点，提出了求解互补问题的一种修正的光滑n e w t o n 算法，从理论上对 算法的全局收敛性了证明；第四章是这种修正的光滑n e w t o n 法用于求解广义非 线性互补问题中，同样证明了算法的全局收敛性 1 0 武汉理工大学硕士学位论文 第2 章预备知识 本章主要介绍与互补问题相关的概念和一些常用结论 给定向量值函数胁置”一r ”，我们说日在点x 是局部l i p s c h i t z 连续的， 是指它在x 的某个邻域内l i p s c h i t z 连续如果日在集合s 量r 4 的每一点均是局 部l i p s e h i t z 连续的，则称日是s 上的一个局部l i p s c h i t z 函数 今假设日：r ”_ r “是局部l i p s e h i t z 连续的，财日几乎处处f 可微且在其 存在的任何有界集上，j a e o b i a n 矩阵有界因此对任何工r “，可引入c l a r k e h 3 i 意义下的广义j a e o b i a n 矩阵 令集合 p 。= 了r “1 日在点z 是f 一可微 若工d n ，则定义在点x 的广义j a c o b i a n 矩阵a h ( x ) 就是通常意义的j a e o b i a n 阵日( 工) ；若x r 。、d ，则定义日在点x 的广义j a c o b i a n 矩阵( 确切地说，应 该是矩阵集) a l l ( x ) = c o ( a 口日( 石) ) 其中g ( 印表示集合a r ”的凸包，以及 a 口h ( 曲= l i mh o 。) j j j t p h 由于日为局部l i p s e h i t z 连续函数，故九日( 力有界于是，a l l ( x ) 为非空有界闭 凸集 定义2 1 1 设日：r 4 一r “是局部l i p s e h i t z 连续的，称h 在点石r 。半光 滑，是指对任何h r “和h 0 总使 l i m 舫 f e a h ( x + t h ) 斗 t 0 存在极限如果日在集s r “的每一点都半光滑，则称日在集s 上半光滑 定义2 1 2 设日：r ”专r “是局部l i p s e h i t z 连续函数称它在点工r 4 是 b d 一正则的，如果对任意的矩阵v 钆- ( x ) 都是非奇异的 定义2 1 3 给定函数h ：r 4 一r “，我们称光滑函数日。( ) ：r 。一r ” ( o ) 为h 的光滑逼近函数，如果对任意x r ”，存在r 0 ，使得 武汉理工大学硕士学位论文 l p ，( 工) 一日( x ) 卜掣，跏 o 如果不依赖于x ，则称日。( ) 为h 的一致光滑逼近函数 定义2 , 1 4 矩阵me r 被称为“p 矩阵”( “只矩阵”) ，如对任意 工r “，工0 存在一分量以0 ，使得 以( 膨r ) i o ( o ) 引理2 , 1 5 ( a ) 设m r 一为只矩阵，见和见为且中负定对角矩阵，则 矩阵绣+ 玩m 非奇异 ( b ) 设m r 为p 矩阵，d 4 和见为r “。中使见+ 见负定的半负定对角 矩阵，则矩阵见+ 见m 非奇异 定义2 1 6 设f ：r ”专r 4 ，对v x ，y r ”且x y ，有下式成立：存在一个 指标i ，使得而y ；且： ( 一一y ，) ( e ( 工) 一只( _ ) ，) ) 20 ( o ) ， 那么称f 为“最函数”( “p 函数”) 性质2 1 7 “”对v x r ”，我们有 a l l ( x ) 7 ( 彳( x ) 一，) + v f ( x ) ( 占( x ) 一，) ( 2 1 1 ) 其中j 是拄x 玎阶单位矩阵，彳( 力和曰( d 皆为对角阵，即 彳( 砷= d i a g ( a “( 石) ) ，b ( 力= d i a g ( b ( j ) ) 以： 南趟胁) ) o以( 曲= 钏( 一，e ( z ) ) 0 】一”。”。 旧，否则 岛( 力：i f ，删a x ) 矿当( ，e ( 砌咐岛( 力= i 胁，只( j ) ) 一。”“”7 【p i ，否则 这里( 鼻，n ) 满足条件l i ( 茧，n ) 捧1 证明：由c l a r k e 广义j a c o b i a n 矩阵定义知 a h ( x ) 1 ( o h l ( z ) 捆。( x ) ) 若f 使( x ie ( 瑚0 ，则巩( 力在点x 可微，且 v h j ( z ) = v 0 ( x ，e ( x ) ) 2 ( 南哦1 + 哪) ( 尚_ 1 ) 1 2 武汉理工大学硕士学位论文 若i 使瓴，e ( 瑚= 0 ，由广义梯度复合定理及 a | 口，6 ) l i ( o ，o ) = 参，只) 胀磊，只) 8 l ， a 日；( 工) = a 庐0 l ，只( 工) ) = ( 岳一1 ) 岛+ 1 9 e ( 】f ) ( 成一1 ) 硼曲= 臣籍刁i _ 2 性质2 1 8 “4 函数日( 砷半光滑：函数妒( x ) 是连续可微的，且它的梯度为 o h ( x ) 7 h ( 力 证明：对每个f 1 ，2 ，筇 ，z ( 力是可微函数瓴，霉o ) ) ：r 。一r 与 凸函数：r 2 啼r 的复合因为凸函数和可微函数是半光滑的，半光滑函数的 复合仍为半光滑，所以日( 刁半光滑因而第一结论得证 对每一个f 1 ，2 ，九，考虑函数【e ( x ) 】2 ，显然它在集 q _ 扛l ( x ie ( 工) ) 0 上连续可微，且v 【e ( x ) 】2 = 2 啊( 工) h o ) 而在集 五= & i ( _ ，e ( 枷= o 上，【- u x ) 2 半光滑且针e ( x ) 】2 = 2 0 , ( x ) e ( x ) = o ，即 a 只( 力q ( 力此时为单值因而【e ( x ) 】2 在五上可微 i i v z - , ( = ) l l - o e ( 工) o ， ：= 考四 容易证明它们与d 。日，d 6 日之间的关系为： ( 见) j 0 营( 见月) ， 0 i 万 4 h 1 = 0 b h ) i = 0 i z ( 见日) i 0 定义2 1 1 0 我们说j + 为r - 正则，是指v f 乙( 工) 非奇异且它在矩阵 兀滚昌瓷跚 中的s c h u r 补 v ( 工+ ) 一v ( 工) v ( x ) 。v ( 工) 是一个p 矩阵 1 4 武汉理工大学硕士学位论文 第3 章求解互补问题的一类修正的光滑n e w t o n 法 本章把非线性互补问题的求解转化为求解一系列光滑的非线性方程组，并 将牛顿方向和最速下降方向相结合来求解该系列方程组，从而得到了求解互补 问题的一类光滑n e w t o n 法，并从理论上证明了该算法的全局收敛性 3 1n c p 函数和等价形式 互补问题在某些情况下可以等价于其他的数学问题，例如方程组或最优化 问题等等这些等价的问题在研究互补问题的解的存在性以及求解方法时可以 发挥显著的作用反之，也可以利用互补问题来研究其等价的数学问题令 ，r 4 是互补问题n c p ( f ) 的解，即有 x 0 ，f ( x ) 0 ，# 只( ，) = 0 ( f = 1 ，2 ，n ) ， 显然这等价于，满足 n l i n ，e ( x ) = o ( f = 1 ，2 ，打) 这一组等式可记为 l l l i n p ，f ( x ) - o ， 这里m i i l x ，f ( x ) ) 是一矢量，其分量是m i i l # ，f ( ，) ( 扛1 ，2 ，”) 所以互补 问题n c p ( f ) 等价于求解方程组 m 血 以力 = 0 函数l n i n 口，b 被称为“m m 函数”广义互补问题c p ( f ，g ) 也可等价地化成为： 求解方程组m m ( f ( x ) ，g ( 工) ) = 0 这导致n c p 函数的概念 定义3 1 1 函数咖r 2 寸r 1 被称为一“n c p 函数”，如对任意g ，6 ) ，r 2 ， d ( a ，6 ) = 0 当且仅当a o , b 2 0 ，a b = 0 显然r a i n 函数是一c p 函数，它被记为对于任意一c | p 函数矿，互 补问题n c p ( f ) 可等价地转化为方程组 武汉理工大学硕士学位论文 i ( ，( 工”l ( 工) ：= i i i _ 0 ( 3 1 1 ) l 妒( ，只o ) ) j m i n 函数的不足是在直线a 一6 = 0 上的点均不可微，这使得映射m i n x ，f ( x ) l 为 不可微r a i n 函数有另一种表达式，它在互补问题的算法的设计中非常有用： ( 口，6 ) = 去( 口+ 6 一o - b ) 2 ) 二 另一个重要的n c p 函数是f i s c h e r - b u r r a e i s t e r 函数： 口( 口，：= d 2 + 6 2 一( 口+ 6 ) ，v ( a ，6 ) 7 r 2 定理3 1 2 “4 1函数妒。是一凸的n c p 函数，且在任意点( 口，6 ) 7 0 为可微， 镌在平面上任意点为连续可微 证明：如口o ，b o ，a b = 0 ，显然有兢0 ，b ) = 0 反之，如( 口，b ) = 0 ， 即有口2 + 6 2 = 口+ 6 ，则有口6 ：o 如口= 0 ，则b = 6 2 0 ，同理如b = 0 ，即口0 a p e 如是一c p 函数根据凸函数的定义，可验证。是一凸函数函数在 ( 4 ，b ) o 显然是可微的编在( ，o 的梯度是 v 编( 口，b ) = 2 咖而一等 2 ( a + 2 b - 厮一等) 令v 镌( o ，o ) ：= o ，易证v 锯在( o ，o ) 是连续的，所以坛在r 2 中是连续可微的 b c h e r t x c h e n 和c k a n z o w 提出了一种带惩罚的f i s c h e r - b u r m c i s t e r 函 数： 妒c “( 口，：= 妒”( 口，6 ) 一r m a x ( o ，a ) m a x ( o , 功，v (