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

as m o o t hn e w t o nm e t h o df o rs o l v i n g 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 b a ix i a o x i n s u p e r v i s e db yp r o f e s s o rc h e ng u o q i n g s c h o o lo fm a t h e m a t i c a ls c i e n c e s ， i n n e rm o n g o l i au n i v e r s i t y , h o h h o t ，010 0 21 m a y ，2 0 1 0 原创性声明 本人声明：所呈交的学位沦文足本人在导师的指导下进行的研宄t 作及取得的研究 成果。除本文已经注明0 l 用的内容外，沦艾中小包含其他人已经发表或撰写过的研究成 果，也不包含为获得内蒙古大学及其他教育机构的学位或证书而使用过的材料。与我 同工作的同志对本研究所做的仟何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：啤指导教师签名二杠 日 在学期间研究成果使用承诺书 本学位论文作者完伞了解学校有关保留、使用学位论文的规定：叩：内蒙古大学角权 将学位论文的全部内容或部分保留并向园家彳丁天机构、部门送父学位论文的复日j 件和磁 盘，允许编入有天数据库进行检索，也可以采用影e 1 j 、缩e 1 j 或其他复制手段保存、汇编学位 论文。为保护学院和导师的知识产权，作学在学期问取得的研究成果属丁内蒙也大学作 者今后使用涉及在学期闻主要研究内容或研究成果，须征得i j = i 蒙古大学就谈期间导9 i l i 的同 意；若用于发表论文，版权单位必须署名为内蒙古大学方可投稿或公开发表 学位论文作者鼢鱼衄髯指导教帅签名趣 内蒙古大学硕士学位论文 非线性互补问题的一种光滑牛顿法 摘要 通过将非线性互补问题转化为光滑方程组，本文给出求解非线性互补问 题n c p ( f ) 的一种光滑牛顿法在，为p o + r o 函数时，证明了算法的全局收敛性然 而，由于相应光滑方程组的j a c o b i 矩阵在解上为零矩阵，算法理论上不保证局部 超线性收敛率借鉴a o g f i e w a n k 3 8 并1 任玉芳 5 3 1 的工作，本文提出一个扰动策 略，在迭代点列靠近n c p ( f ) 之解时，使扰动点进入能保证快速线性收敛至u n c e ( f ) 某个近似解的星形域，继续单位步长的光滑牛顿迭代，可保证算法能够快速线 性收敛至i j n c p ( f ) 的某个近似解数值算例表明，任意初始点，算法能较快迭代到 解附近，再结合保证快速线性收敛的扰动策略，实际计算中获得很好的数值结 果相对现有非光滑牛顿法和光滑化牛顿法，本文所提出的光滑牛顿法构造简 单，便于实际应用 关键词：非线性互补问题；光滑牛顿法；奇异解；线性收敛 i nt h i sd i s s e r t a t i o n ，as m o o t hd a m p e dn e w t o nm e t h o df o rs o l v i n gt 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 mn c p ( f ) i sp r e s e n t e db yr e f o r m u l a t i n gn c p ( f ) t oas y s t e mo fs m o o t he q u a - t i o n s t h ea 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 ea s s u m p t i o nt h a tfi sp 0 + r o f u n c t i o n h o w e v e r , t h el o c a ls u p e r l i n e a rc o n v e r g e n c ei sn o tg u a r a n t e e ds i n c et h ej a c o b i a nm a - t r i xo ft h es y s t e mo fs m o o t he q u a t i o n sa tt h es o l u t i o ni saz e r om a t r i x t oo v e r c o m et h i sd e f e c t , ap e r t u r b a t i o ns t r a t e g yi sg i v e nb yw h i c ha ni t e r a t i v ep o i n txc a nb ep e r t u r b e dt o w h i c h b e l o n gt ot h es t a r - l i k er e g i o np r e s e n t e di na o g r i e w a n k 3 8 】a n dr e ny u f a n g 5 3 ，i tc a nb e p r o v e dt h a tt h es e q u e n c eg e n e r a t e db yt h es m o o t hn e w t o ni t e r a t i o nw i t hu n i ts t e ps i z es t a r t i n g f r o m i sq u i c k l yl i n e a r l yc o n v e r g e n tt oa na p p r o x i m a t es o l u t i o no fn c p ( f ) n u m e r i c a lr e s u i t ss h o wt h a t ，s t a r t i n gf r o ma n yi n i t i a lp o i n tx 0 础，t h es e q u e n c e x k g e n e r a t e db yt h e s m o o t hd a m p e dn e w t o nm e t h o di sq u i c k l yc o n v e r g e n tt on e a rt h es o l u t i o n ，a n ds t a r t i n gf r o m t h ep e r t u r b a t i o np o i n t t h es e q u e n c eg e n e r a t e db yt h es m o o t hn e w t o ni t e r a t i o nw i t hu n i ts t e p s i z ei sq u i c k l yc o n v e r g e n tt oa na p p r o x i m a t es o l u t i o n c o m p a r e dw i t ht h ee x i s t i n gn o n s m o o t h o rs m o o t h i n gn e w t o nm e t h o d s ，t h es m o o t hn e w t o nm e t h o dp r e s e n t e di nt h i sd i s s e r t a t i o ni s s i m p l ea n de a s yt ot h ep r a c t i c a la p p l i c a t i o n s 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 ；l i n e a rc o n v e r g e n c e ；s m o o t hn e w t o n m e t h o d ；s i n g u l a rp o i n t s i l 中文摘要 英文摘要 目录 第一章引言 1 1 非线性互补问题 1 2 算法研究背景 1 3 本文主要工作及内容安排 第二章预备知识 第三章非线性互补问题的光滑牛顿法 3 1 一个光滑n c p - 函数及其性质 3 2 非线性互补问题的光滑牛顿法 3 3 光滑牛顿法的收敛性分析 3 4 数值实验 第四章总结与展望 参考文献 致谢 i l 6 8 m m 懈殂 行 n 笃 第一章引言 互补问题是运筹学与计算数学的一个交叉研究领域，以其与线性规划、二次规划、变 分不等式和约束优化问题的最优性条件之间的密切联系成为数学规划的一个基本问题， 在力学、工程、经济、交通等许多实际部门有广泛的应用经过四十多年的发展，其理论 体系、数值方法和应用领域日渐完善、深入和扩大，成为数学规划中的一个十分热门的研 究课题，引起众多数学工作者的广泛兴趣和高度重视，参见h a r k e r 和p a n g 的综述性文章【l 】 1 1 非线性互补问题 非线性互补问题是指：求工r n 使其满足 工0 ，f ( 曲o x t ，( 曲= 0 记为n c p ( f ) 非线性互补问题的一个自然推广就是变分不等式问题【2 3 4 】，即求j q 使得 t y 一曲r f ) 0 ，v y q ( 1 2 ) 其中q 础为一个非空闭凸集 互补问题和变分不等式问题相伴而生 2 - 9 互补问题在工程与经济领域有着广泛的应 用，如在经济估计与对策理论研究中；互补问题在最优化中也有着广泛的应用，如在线性 规划中考虑对偶问题，或在非线性规划中求稳定点的k - t 条件都可以转化为互补问题；在 应用变分不等式的领域中可以利用二者的联系进行求解；在实际中也经常会利用互补问 题，如均衡网络设计、信号最优化问题以及交通布置问题等等 1 2 算法研究背景 c o t t l e 等人于1 9 6 3 年首次提出互补问题次年，c o t t l e 便在他的博士论文中第一次提出求 解互补问题的数学规划算法互补问题的出现引起了人们浓厚的兴趣，特别是8 0 年代中后 期，随着科技与经济的发展，互补问题越来越重要，成为了数学规研究中的热点问题，同时 也涌现出了许多求解互补问题的算法 1 方程组法 这类方法是借助n c p 一函数将互* 1 - i - - j 题( 1 1 ) 转化为等价的非线性方程组，进而通过求解 这个非线性方程组来间接求解互补问题( 1 1 ) 所i 胃n c p 函数，即函数妒：r 2 - r ，满足 驴( n ，6 ) = 0 铮a 0 ，b 0 ，a b = 0 内蒙古大学硕士学位论文 n c p - 函数的作用是将包含等式和不等式三个条件的互补问题转化为一个等式，从而把一 个复杂的等式不等式系统归结为解方程组的问题 对任意给定的n c p 函数毋，定义映射m ：r n 一础如下： ( 曲= ( j l ，f l ( 力) 妒( 而，f n ( 曲) = 0 ， ( 1 3 ) 则r 为互补问题( 1 1 ) 的解的充要条件是r 是非线性方程组( 曲= o 的解该方法可分为光 滑方程组法、非光滑方程组法和光滑化方法 ( 1 ) 光滑方程组法 m a n g a s a r i a n 6 - 于1 9 7 6 年首先提出这种方法，它利用了如下的势函数： o ( a ，易) = 0 ( 1 a 一6 i ) 一吠口) 一吠6 ) ( 1 4 ) 其中0 ：r _ r 是一个严格递增的函数，满足战o ) = 0 m a n g a s a r i a n 证明了互补问题( 1 1 ) 的 解与方程组( 1 3 ) 的解之间的等价关系适当选取f ) 可使似曲光滑满足条件的函数战f ) 有 很多，因而可以再生出很多光滑方程然后用n e w t o n 法或广义n e w t o n 法求解为了保证收 敛性，w a t s o n 7 建立了一个同伦算法( 取伏f ) = f 3 ) ；s u b r a m a n i a n 8 提出了一个带阻尼因子 的g a u s s n e w t o n 法( 取戗f ) = t i t l ) ，k a n z o w 9 考虑如下的2 力阶光滑方程组 h ( x ，y ) = y 一， 似x l ，l ) 枞杨，凡) ( 1 5 ) 并给出了j a c o b i 矩阵v h ( x ，y ) 在n c p ( f ) 的非解点处可逆的几个充分条件，并且当解点处的j a c o b i 矩阵非奇异时，该类方法在解点附近具有超线性收敛性 光滑方程法有一定的优越性，但是其缺点是，即使是一个线性的互补问题，转化后的 方程组也往往是非线性的，并且非线性程度较高，且在退化解点的j a c o b i 矩阵奇异 ( 2 ) 非光滑方程法 为了弥补光滑方程组法的刁i 足，人们转向构造非光滑方程组r o b i n s o n 1 0 弓 进了正则 解的概念，同时又提出了r 正则解，b 一正则解，c d 一正则解等概念 1 1 ，1 2 】，这些新引入的概念 在广义n e w t o n 法的超线性收敛性分析中起到了很大的作用 p a n g 【1 3 】利用n c p 函数西l ( 口，6 ) = m i n a ，6 将互补问题转化为如下的非光滑方程组 h ( x ) = m i n l x l ，f l “) m i n x n ，f n ( 工) l 2 ( 1 6 ) 内蒙古大学硕十学位论文 p a n g 在【1 2 】中证明了若f 连续可微，则以工) 是b 可微的由此建立了一个带有非精确线性 搜索的广义n e w t o n 方法，其搜索方向扩满足： h ( x k ) + b h ( x k ) 扩= 0 ( 1 7 ) 其中b h ( x k ) 为日在点处的b 导数，p a n g 在 1 3 1 中还证明了上述方法的全局收敛性和局 部超线性收敛性( 在某种正则条件下) 一般来说，( 1 7 ) 中的n e w t o n 方程是非线性的，不容易 求出铲为此，文献1 1 4 中提出了一个l 、吲s q p 方法，它仅求解一个二次子规划可得扩，并且 在解的正则性条件下，算法局部超线性或二次收敛1 9 9 2 年f i s c h e r 在【5 】中引入如下f i s c h e r - b u r m e i s t e r 函数： 晚( 口，功：丽一日一b ，( 1 8 ) 由此函数建立的n e w t o n 法所表现出来的良好的理论和数值计算结果引起了众多学者的极 大兴趣j i a n g 年h q i 1 5 基于f i s c h e r - b u r m e i s t e r 函数，提出求解n c p ( f ) 的广义牛顿法，为保证求 下降方向子问题的唯一可解性，算法要求f 为p 一函数l u c a , f a c c h i n e i 和k a n z o w p 6 禾u 用矩阵 v k o s o ( x k ) 和广义牛顿方程v k d + ( x k ) = o 提出求解n c p ( f ) 的广义牛顿法，但若广义牛 顿方程不可解或广义牛顿方向不是价值函数伏工) 的充分下降方向，则算法采用最速下降 方向, k = 一v o ( x k ) 算法全局收敛到战工) 的稳定点r ，且当西在r 点b d 正则时算法局部 超线性或二次收敛为克服使用最速下降这一缺点，y a m a s h i t a 【1 7 】提出修正广义牛顿法，构 造v keo s c p ( x ) 的扰动矩阵萨，使广义牛顿方程矿铲= 一o ( x k ) 唯一可解且其解总是价值函 数吠曲的充分下降方向在较弱的条件下，算法全局收敛且具有局部超线性或二次收敛率 k a n z o wd 8 提出互补问题的非精确半光滑牛顿法，用i l v k d + o ( x k ) l l r m l o ( ) l l 取代广义牛顿 方程v d + o ( x k ) = 0 ，其中r k 为强迫因子若班_ 0 ，算法超线性收敛；若吼= o ( 1 l o ( x k ) 1 1 ) ，则 二次收敛c h e n 和p a n 用正则化技术及广义f i s c h e r - b u r m e i s t e r 函数将互补问题转化为一系列 正则互补问题，进而提出正则半光滑牛顿法若f 是p o 一函数且在解的c d 一正则条件下，算 法超线性收敛；若，在解点处局部l i p s c h i t z 连续，则算法二次收敛 ( 3 ) 光滑化方法 克服非光滑性的另一途径是利用光滑函数吼( 工) 啦 o ) 去逼近非光滑函数( 力，称 q ( d 是( 工) 的光滑逼近函数这样可以用牛顿型方法解参数非线性方程吼( 曲= 0 ，称这 类方法为光滑化方法，其局部超线性及二次收敛性依赖于方程组在解点处的半光滑性( 强 半光滑性) 及其广义j a c o b i 矩阵在解点处的非奇异性一般说来，解的r 一正则性可以保证广 义j a c o b i 矩阵在解点处的非奇异性，而函数f 的一致p - 性质可以保证水平集的有界性这类 方法分为j a c o b i 光滑化方法、完全光滑化方法及非内点磨光算法 j a c o b i 光滑化方法 1 9 1 是第一个求解非光滑方程组全局收敛- h 具局部超线性收敛率的 算法该方法要求吼( j ) 是( 工) 的一致光滑逼近函数，吼( j ) 满足j a c o b i 相容性条件且适用于 3 内蒙古大学硕士学位论文 f 为p o 一函数基于该算法，k a n z o w 和p i e p e r ( 2 0 】给出了另一求解互补问题的j a c o b i 光滑化算法， 由于梯度步的引入，该方法可求解一般的非线性互补问题 完全光滑化方法与j a c o b i 光滑化方法的区别在于：在j a c o b i 光滑化的方法中，光滑因子 p 被视为参数，需要严格的迭代规则使其单调下降并趋于0 ，而在完全光滑化方法中，把 p 看作与j 同等变量m ，力加以迭代q i ，s u n 和z h o u 【2 1 】首次提出求解非线性及混合互补问题 的完全光滑化方法利用n c p - 函数妒将互补问题转化为 ，、 m ，曲：i l - 0 i 烈神j 其中西：瞅+ l _ + - ，其分量为庐( 置，f k x ) ) ，i = 1 ，2 ，n 算法在每次迭代中只解一个牛顿 方程，进行一次线搜索既可保证光滑参数的非负性又可使目标函数在每次迭代中有所下 降对非线性互补问题而言，在f 是r ：上的一致p 函数的假设下得到水平集的有界性，进而 证明了算法的全局收敛性在解的c d 一正则性条件下算法超线性或二次收敛 非内点磨光算法是一类特殊的光滑化方法，与前述两种光滑化方法相比较，它增加了 线性调节p 的程序保证迭代点列在解的邻域内c h e n 和h a r k e r 【3 1 】于1 9 9 3 年首先提出该方法， 对m 为对角元素为正的p o + r o 一矩阵的线性互补问题l c p ( q ，加，考察了摄动方程组之解构成 的中心路径的存在唯一性，但未提供算法的收敛性的证明b u r k e 和x u 【3 2 】通过引入中心邻 域的概念采取路径跟踪技术证明了p o + r o 一线性互补问题的非内点磨光算法的全局线性收 敛性z h a n g 等【3 3 】将非内点磨光算法推广到广义非线性互补问题，在解的b d 正则性条件 下，算法超线性或二次收敛 2 无约束优化法 无约束优化法就是将互补问题转化为一个与之等价的可微无约束优化问题，然后用 某种全局收敛的或n e w t o n 型的算法来求解 m a n g a s a r i a n 和s o l o d o v 2 2 先于他人给出了一个可微的势函数 朋苫( 曲= x t ，( j ) + | i ( 一a f ( x ) + 柚+ 1 1 2 一i i 工2 + 1 1 ( 一o r x + f ( 力) + 1 1 2 一i i f ( x ) 1 1 2 l ，a 0 ( 1 9 ) 二口 实际上，m s ( x ) 可以由可微的n c p 函数 妒m s o ，6 ) = a b + 熹( ( m a ) 【 o ，口一口6 ) 2 一2 + ( m a x o ，b 一伽 ) 2 一b 2 ) ( 1 1 0 ) 按下式生成： = y ，f i ( o m s ( x )m s ( x i工) ) ( 1 11 ) = 。 ， 工) ) ( 1 1 ) j f 1 文【2 3 】研究了( 1 11 ) 与互补问题( 1 1 ) 之问的关系，如果f ( 工) 是可微的并且v f ( x + ) 正定，那么( 1 11 ) 的稳定点与( 1 1 ) 的解是等价的近年来，对可微无约束优化法的研究兴趣转向增加非负 4 内蒙古大学硕士学位论文 约束，因为通过实际计算表明，仅用无约束优化求出的互补问题的解并不理想，为此m o r 4 1 2 4 】给出了一个可行的信赖域方法，w a n g m o n t e i r o p a n g 1 6 提出了一个降势内点法，这方面的 方法也逐渐增多。如文献 2 5 ，2 6 3 投影法 投影法是基于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 投影法，其基本迭代格式为 x k + 1 = i x k 一口f ( ) 】+( 1 1 2 ) 这里口 o 为步长然而它的收敛性需要要求f 是强单调的映射为此k o r p e l e v i c h ( 1 9 7 6 ) 提出 了外梯度法。即 = 【一a f ( x k 一口f ( ) 】+ ) 】+( 1 1 3 ) 它的收敛性仅要求f ( 工) 单调且解集r 非空s u n 2 7 ，2 8 】应用a r m i j o 搜索技术得到，在f ( 力伪 单调且x 非空的假设下，迭代点列收敛到r 虽然这类方法最多只有线性收敛速度， 但它运算量小，存储量小，保稀疏性等性质使研究者对其产生了浓厚兴趣最近，s o l o d o v 和t s e n g 2 9 给出了一个g l p 投影法的一般迭代格式 x k + 1 = 一r p - - 1 i l ( ) 一瓦( 【一口f ( ，) 】+ 1 ( 1 1 4 ) 这里r o 是步长，l = ，一g f ( 当，= m x + q 时，乃= ，+ 口肘r ) ，口 0 使得l 强单调，p 是 选取的正定矩阵 4 内点法 内点法就是将互补问题转化为一个与之等价的非负约束方程组，然后用n e w t o n 类型 方法求解内点法的研究起源于k a r m a r k a r 【蚓的求解线性与凸二次规划的内点法，是这种 方法的自然延伸 互补问题( 1 1 ) 可以转化为如下的方程组 聊= y - ，f y ( x ) 】= 0 观删脾。 嘲 显然，( 1 1 5 ) 是一个带有非负约束的2 n 阶非线性方程组，当f ( 曲= m x + q 时，仅第二个方程 是非线性的且具有特殊形式的表达式；当f ( 曲是po 一函数时，j a c o b i 矩阵是非奇异的，从而 在迭代中可以取n e w t o n 方向作为搜索方向给定点( ，矿) r 强，内点法的一般迭代格式 为 ( ，少+ 1 ) = ( ，矿) + 也( 磷，或) ， ( 1 1 6 ) v h 2 ( x k ，y k ) a = 一膨( ，矿) ，扩= ( 磷，磷) ， ( 1 1 7 ) 内蒙古大学硕士学位论文 这里晓( ，矿) 是由t h ( x ，矿) 经过一个微小的扰动得到的，其目的是调节迭代的收敛速度； 九 o 为步长，它的取法使新得到的点p + - ，少+ 1 ) r 强，并且效益函数有一定程度的下降 如果在迭代过程中能保证) ，七= f ( ) ，k = 0 ，1 ，则称为可行内点法【3 0 】；否则称为不可行 内点法1 9 9 2 年，y e 【3 l 】利用势缩减法求解p - 矩阵的线性互补问题，算法具有多项式时间复 杂性【3 2 】将内点法推广到非线性互补问题，并在，( 力为一致p - 函数及其它假设下讨论了算 法的收敛性和计算复杂性 1 3 本文主要工作及内容安排 本文主要讨论n c p ( f ) 的光滑方程组解法将n c p ( f ) 等价转化为一个处处光滑的非线 性方程组 ( 曲= 0 ，( 1 1 8 ) 进而研究其光滑牛顿类解法因西处处光滑，此方法易于工程领域所接受，便于应用 称x 酣是方程组( 1 1 8 ) 的奇异解，若j a c o b i 矩阵西7 ( r ) 奇异一般地，利用牛顿迭代 + 1 = 一( ) 一1 ( )( 1 1 9 ) 逼近( 1 1 8 ) 的数值解是合理的 当j a c o b i 矩阵( r ) 非奇异时，该类方法在解点附近具有超线性收敛性当j a c o b i 矩阵 o ，( r ) 奇异时，牛顿法的经典理论不再适用然而对于许多实际问题，m ( r ) 是奇异的，奇异 性一般会导致数值计算的困难r e d d i e n 3 6 ，d e c k e r 和k e l l y 3 7 ，以及g r i e w a n k 3 8 等都证明了 在解r 的一个特殊邻域内，牛顿法( 1 1 9 ) 产生的迭代序列线性收敛到r 但上述收敛速度 的达到必须要求西在r 二次以上l i p s c h i t z 连续可微，并且在r 处满足一定的正则性条件 后来o b e r l i n 和w r i g h t 在【4 0 】中将g r i e w a n k 3 8 的光滑性条件弱化，仅要求在r 处强半光滑， 在一定的正则性条件下证明了此时g r i e w a n k 3 8 的结论仍然成立o b e r l i n 和w r i g h t 在【4 0 】中 利用a 0 g r i e w a n k 在【3 8 】中提出的星形域的概念提出了加速牛顿法，该方法只要求m ( j ) 在r 强半光滑，并且在满足一定的正则性条件时得到快速线性收敛速度 本文取得的丰要结果可归纳如下： 1 基于任玉芳在【5 3 中构造的光滑n c p 一函数，提出求解非线性互补问题的一种光滑牛 顿法 2 证明了算法的全局收敛性 3 利用a o g r i e w a n k 在【3 8 】中提出的星形域的概念及对具有奇异解的牛顿迭代局部 收敛性的证明方法，证明了本文算法以 的速度局部线性收敛至i j n c p ( f ) 的近似解 本文内容由四章构成，第一章是引言部分，介绍了互补问题的应用背景和近年来有 关互补问题求解方法的研究成果，并简单介绍了本文的主要研究内容；第二章介绍了有 6 内蒙古大学硕士学位论文 关互补问题的一些基础知识；第三章是本文的重点，首先研究了任玉芳在【5 3 】中构造的 光滑n c p 函数的一些特殊性质，进而基于这些特殊性质给出了求解非线性互补问题的光 滑牛顿法，算法3 1 及算法3 2 从理论上证明了算法3 1 的全局收敛性进一步利用a o g f i c w a n k 在【3 8 】中提出的星形域的概念证明了算法3 2 以；的速度局部线性收敛至i j n c p ( f ) 的 近似解，本章最后给出了几个实例验证了算法的有效性9 文章最后是对本文的总结和对将 来研究工作的展望 7 第二章预备知识 弟一早耿官刘以 在本章中。将给出有关互补问题的一些基本概念和基本理论本文中主要使用如下的 数学符号： 1 础表示，z 维欧式空间，r 表示实数域 2 r n = 工r ，：x i 0 ，i = 1 ，2 ，疗l ，r 罩+ = 工珉r ：x i 0 ，i = 1 ，2 ，冗 厂i 一 3 i l x l l 表示向量工的欧式范数，即对于j 舯，删= 1 压# ；i 川表示矩阵a 的谱范数， 即i i a | l = l m a x ( a r a ) ，其中a 。啡( a ) 为a t a 的最大特征值 4 ，表示向量工的转置，并且规定工r n ，工= ( 工l ，x 2 ，而) r 5 d i a g a l ，a 2 ，锄l 表示对角线元素为a l , d 2 ，的对角矩阵 6 记n = l ，2 ，n 7 对任意的向量a r n ，记 其中m i n ，m a x 按分量计算，即 a + = m a x 0 ，口l ，a 一= r a i n 0 ，口l ， a + = ( 口j ，口；，n ：) d 一= ( 口了，n 三，a n ) ， 口产= m a x 0 ，a i ，口_ = m i n 0 ，a i ，i = 1 ，2 ，n 8 s u p 表示取上确界，i i l f 表示取下确界，l i m s u p 表示取上极限，l i m i n f 表示取下确界 m a x 表示取最大值，m i n 表示取最小值 9 p 表示分量均为1 的向量，e i 表示第f 个分量为1 ，其它分量为0 的向量 1 0 v 表示对任意的，3 表示至少存在一个，表示属于，表示不等于 11 d 表示高阶无穷小，表示证明完毕 定义2 1 【5 0 】设m r n n 为nx ，l 矩阵( 不必对称) ，称m 为 ( i ) 正定矩阵，若x t m x 0 ，y x 科，j o ； ( i i ) 半正定矩阵，若工r m x 0 ，v x r n ； ( i i i ) 尸l 矩阵，若m 的所有主子式严格正，即d e t ( g 。) o ，v 口； ( i v ) e o 一矩阵，若m 的所有主子式非负，即d e t ( m , ，。) 0 ，v a ； ( v ) r o 一矩阵，若l c p ( 0 ，加只有零解 由定义立即可知半正定矩阵必为po 一矩阵，正定矩阵必为p 矩阵，p 一矩阵既是po 一矩阵 又是r o 一矩阵，若肘为p ( p o 一) 矩阵，则m 的所有主子阵也是p 一( p o 一) 矩阵此外，若m = m 7 为 对称矩阵，则m 正定当且仅当m 为p 一矩阵，m 半正定当且仅当肘为p o 一矩阵，但若m m 7 为 8 内蒙古大学硕士学位论文 非对称矩阵，则上述关系不再成立具体而言，若m 正定( 半正定) ，则肘必为p ( po 一) 矩阵， 但反之不然 命题2 1 【4 l 】设m n ( 不必对称) ，则如下叙述等价 ( i ) m 为po 一矩阵； ( i i )m a x x i ( m x ) i 0 ，y x r n ，工0 ； t 曼l n ，工f o ( i i i ) m 及其所有主子矩阵的所有实特征值非负； ( i v ) 对任意s 0 ，m + s ，为p 矩阵； ( v ) 若d 为n 阶正对角矩阵( 每个对角元素都是非负实数) ，则m + d 为p 一矩阵； ( v i ) 对任意正对角矩阵d ，矩阵m + d 非奇异 命题2 2 4 1 1 设m 跏( 不必对称) ，则如下叙述等价 ( i ) m 为p 矩阵； ( i i )m a xx i ( n x ) i 0 ，v x 础，x 0 ； 1 o 使 m a x f i ( 曲一f i ( y ) ( x i - y i ) j u l l x y l l 2 ，y x ，y 乏“； l f 几 ( i v ) 单调函数，若 【f ( 工) 一f ( y ) 】丁( 工一) ，) o ，y x ，y i r n ； 9 内蒙古大学硕士学位论文 ( v ) 伪单调函数，若 f ( ) ，) r o y ) 0jf ( 工) 7 0 一y ) 0 ，y x ，y r n ； ( v i ) 严格单调函数，若 【，( 力一，( y ) 】r 0 一y ) 0 ，y x ，y r n ，工) ，； ( v i i ) 强单调函数，若存在p o r 【f ( 力一f ( y ) 】7 ( 工一) ，) # l l x y l 2 , y x ，y r n ； ( v i i i ) ro 一函数，若对任意满足 l l x k l l - - , 训i m 盛鲁她t i m 熙铲。 的序列i x k 必存在一个下标使当k - o o 时，有 t _ ， f j ) _ 由以上定义立即可知一致p 函数必是p 函数，p - 函数必是p o 一函数，单调函数必为p o 一函 数，严格单调函数必为p - 函数，强单调函数必为一致p - 函数 命题2 4 4 3 1 设f ：r n _ 科为连续可微函数，那么f 为po 一函数当且仅当，的j a c o b i 矩 阵在任意点处均为po 一矩阵，若f 为一致p 函数，则f 的j a c o b i 矩阵在任意点处均为p 矩阵 非线性互补问题n c p ( f ) 当，为一致p 函数时n c p ( f ) 的解存在且唯一对于线性互补 问题l c p ( q ，加，当m 为p 一矩阵时，l c p ( q ，m ) 的解存在且唯一 定理2 1 5 5 1 若f 是f 0 + r o 函数，贝j j n c p ( f ) 的解集非空有界 定义2 3 【5 5 】称二元函数：r 2 _ r 为n c p - 函数，若对任意( 口，易) r 2 ，有 驴( 口，6 ) = 0 甘a 0 ，b 0 ，a b = 0 n c p 一函数的作用是将包含等式和不等式的三个条件的互补问题转化为一个等式，从 而把一个复杂的等式不等式系统归结为解方程组的问题利用n c p 一函数可以将非线性互 补问题n c p ( f ) 转化为如下非线性方程组 ( 工) ：= 烈工l ，l ( x ) ) ( ，r ( 力) 1 0 ( 2 i ) 内蒙古大学硕士学位论文 显然r 是n c p ( f ) 的解当且仅当r 是如下非线性方程组的解： ( j ) = 0 常见的n c p - 函数有： 肘( 口，功= m i n ( a ，6 ) ，( 2 2 ) o r n ( a ，易) = 、口2 + b 2 一a 一玩 ( 2 3 ) 驴 f 册( a ，6 ) = 0 ( 1 a 一6 i ) 一伏口) 一吠6 ) ，( 2 4 ) 其中，函数( 2 2 ) 为极小函数，当且仅当a = 6 时不可微；( 2 3 ) 是著名的f i s c h e r - b u r m e i s t e r 函数 【4 7 1 ，它是一个二元凸函数，当且仅当口= b = o 时不可微，且其平方函数砟占( n ，6 ) 在r 2 上处 处连续可微；( 2 4 ) 源于m a n g a s a r i a n1 4 8 ，其中0 ：r r 为满足吠o ) = o 的严格单增函数当取 吠f ) = f 时 妒( 口，6 ) = l a b i a b = - 2 m i n l a ，易l 三- - 2 b m ( a ，功 当取伙f ) = 户时 _ f n n ( 口，6 ) = l a b 1 3 一a 3 一b 3 , v ( 口，易) r 2 ， 它是处处二次连续可微的，基此s u b r a m a n i a n 4 8 提出一个求解n c p ( f ) 的光滑l e v e n b e r g m a r q u a r d t 型算法 设函数0 ：础_ r ，若战功满足：( i ) 仪曲o 对任意x 成立；( i i ) 烈工) = o 当且仅当 j 是互补问题( 1 1 ) 的解；则称伏曲为互补问题( 1 1 ) 的价值函数利用价值函数就可以将互补 问题转化为约束或无约束优化问题若妒( 口，扫) 是非线性互补问题( 1 1 ) 的n c p 一函数，那么非 线性互补问题的一个自然的价值函数就是 1 1 西( x ) l l z 定义2 41 5 0 设向量函数f ：瞅_ r n ，称函数f 在x 上强制，若存在p x ，使 l i m 咩产= o o ro 函数【矧的概念是从线性互补问题中经常用到的强制性条件ro 矩阵的概念推广 而来的，在理论分析中所起的作用就是保证所构造的n c p ( f ) 的价值函数伙曲是强制的，即 保证l i m 烈z ) = + o o 从而保证水平集 工r 1 0 ( x ) n 对任意的实数n 都有界从而下降算 i i x l l _ + 法生成的序列有聚点 定义2 51 5 0 设x r ”为非空子集，向量函数m ：x _ 瞅在点x x 局部l i p s c h i t z 连续， 即存在s 0 ，厶 0 使得 o ( x 1 ) 一( x z ) l l l i i x l 一，v 工1 ，b ( x ，功， l l 总成立，则称为x 上的( 全局) l i p s c h i t z 函数 l i p s c h i t z 连续， 引理2 1 【5 5 】( r 矗m a c h e r 定理) 设xe 瞅是一个开集，西：x _ 瞅在x 上是局 部l i p s c h i t z i 函数的，则在x 内几乎处处可微记风为的可微点集 定义2 6 【删设向量函数：r n 舯，称m 在点工沿方向d 础方向可微，若极限 ， ( 工+ f 力一西( j ) l l m t - - * 0 +f 存在，称该极限为在点工沿方向d 的方向导数，记为0 7 ( 工；田若在点工沿任意d 础方向 可微，则称在x t y 向可微 定义2 7 【5 0 】若西在任意x r n 局部l i p s c h i t z 连续，矩阵集合 如西( 工) = l i m 移( ) i 在x k r n 可微) r + j 称为是西在工处的b 一次微分称b 次微分的凸包为在j 的c l a r k 广义j a c o b i 矩阵集，记 为 a ( 力= c o ( o ( x ) ) 定义2 81 5 0 设向量函数：_ 肿，称在点x r nb d 一正则，若对于任意的v 如( j ) 均非奇异称在点x r n c d 正则，若对于任意的v a 西( j ) 均非奇异 命题2 5 【删若向量函数：础- 在点j r nb d 正则，则存在s o ，c 0 ，使对任意 的y b ( x ，由所有v 如( y ) 非奇异，且i i y 一1 sc 定义2 9 【5 0 】若在工方向可微，且对任意d 瞅，d - 0 ，任意v a 0 + 力有 v d 一7 ( 工；力= o ( 1 l d l l ) ， 则称在上半光滑，若m 在工半光滑且 v d 一( j ；d ) = o ( 1 l d l l 2 ) ， 则称在工强半光滑 1 2 内蒙古大学硕士学位论文 实值函数的半光滑性最初由m 诵i n 【4 4 】引入，q i 年d s u n 将半光滑概念拓广到集值函数向 量函数m ( 工) = ( m l ( 曲，吼( 曲，吼( 力) r 在j 础半光滑当且仅当所有分量函数中l ，吼， 吼在工半光滑半光滑函数类介于光滑函数类和l i p s c h i t z 函数类之间，所有光滑函数、凸函 数和分片光滑函数均是半光滑函数半光滑函数的和、差、积及复合也是半光滑函数 引理2 2m 】设西：础一在x 科上局部l i p s c h i t z 连续，则 ( i ) ( ) 有广义j a c o b i 矩阵。知( x ) ( c l a r k 意义下) 如果m 在x # z 光滑，则对任意d ， 在j 沿方向d 的方向导数存在 ( i i ) 由( ) 在工半光滑当且仅当对任意v 锄o + 力，d _ o 有 i l v d 一7 ( x ；d ) l l = o ( 1 l d l l ) 或 i i m ( x + 回一西( 功一( x ；d ) l l = o ( 1 l d l l ) (