（应用数学专业论文）互补问题与半定规划算法研究.pdf

互补问题与半定规划算法研究 摘要 本文主要研究互补问题与半定规划问题的数值解法。所取得的主要结果有： 1 提出无约束最优化共轭梯度法参数反修正的两种新形式与经典共轭梯度法的 区别是新方法中体现了函数值下降量信息提出这两种方法的改进形式证明了 这四种方法的全局收敛性数值实验表明了算法的有效性 2 提出求解大规模非线性互补问题( n c p ( f ) ) 的共轭梯度法( i ) 利用f i s c h e r - b u r m e i s t e rn c p 一函数，将n c p ( f ) 转化为非线性方程组，基此提出p r p 一型共 轭梯度法算法的突出特点是在不需要额外假设及线搜索的辅助下满足充分下降 条件，在f 是连续可微蜀+ 凰函数且f 7 ( z ) 在水平集上全局l i p s c h i t z 连续条件 下，算法全局收敛( i i ) 利用光滑f i s c h e r - b u r m e i s t e r 函数，将n c p ( f ) 转化为光滑 非线性方程组，基此对大规模非线性互补问题提出光滑p r p 一型共轭梯度法算 法执行一步需进行两个a r m i j o 线性搜索既确保光滑参数弘的非负性又极小化由 光滑f i s c h e r b u r m e i s t e r 函数所形成的光滑价值函数在f 为蜀+ 凰连续可微函 数时，算法全局收敛数值实验表明了这两种算法的数值有效性 3 提出半定规划的半定互补解法首先考虑一类特殊的半定规划问题( 即在对偶问 题中加入约束条件y 0 ) ，将其最优性条件等价转化为半定互补问题( s d c p ) ，藉此 提出预估一校正光滑牛顿法，证明了牛顿方向的存在性、迭代点列的有界性及算法 的全局收敛性在解点处广义导数可逆的假设下得到算法的超线性收敛率然后 推广这一思想，将标准半定规划的最优性条件转化为广义半定互补问题( g s d c p ) ， 提出预估一校正光滑牛顿法该方法是非线性互补问题( n c p ( f ) ) 算法的推广同 样证明了牛顿方向的存在性、迭代点列的有界性及算法的全局收敛性在解点处 广义导数可逆的假设下得到算法的二次收敛率不需要任何对称化技巧，此二方 法自动产生对称搜索方向 4 提出半定规划的非内点连续化方法该方法是求解半定互补问题( s d c p ) 算法的 推广证明了牛顿方向的存在性在中心路径邻域有界的假设下得到迭代点列的 有界性，进而证明了算法的全局收敛性在解点处广义导数可逆的假设下算法局 部二次收敛给出了数值实验结果 i i 5 提出半定规划的p r p + 共轭梯度法基于f i s c h e r b u r m e i s t e rs d c p 一函数，对s d p 的最优性条件提出一梯度具有全局l i p s c h i t z 连续性的价值函数，从而将半定规划 转化为无约束优化问题，进而用p r p + 共轭梯度法求解为得到p r p + 共轭梯度 法的收敛性同时使函数值在每次迭代中有所下降，提出一a r m i j o - 型线搜索无 需水平集有界及迭代点列聚点的存在，算法全局收敛 关键词：共轭梯度法，互补问题，半定规划，牛顿法，全局收敛性，超线性收敛， 二次收敛 i i i s t u d yo nt h ea l g o r i t h m sf o r c o m p l e m e n t a r i t ya n ds e m i d e f i n i t e p r o g r a m m i n gp r o b l e m s a b s t r a c t t h i st h e s i si sd e v o t e dt os t u d yt h ea l g o r i t h m sf o rc o m p l e m e n t a r i t ya n ds e m i d e f i n i t e p r o g r a m m i n gp r o b l e m s t h em a i nr e s u l t s ，o b t a i n e di nt h i sd i s s e r t a t i o n ，a l es u m m a r i z e da s f o l l o w s ： 1 t w on e wf o r m u l a so ft h em a i np a r a m e t e r 玩o fc o n j u g a t eg r a d i e n tm e t h o d sf o ru 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 sa r ep r e s e n t e d i nc o m p a r i s o nw i t hc l a s s i cc o n j u g a t e g r a d i e n tm e t h o d s ，t h en e wm e t h o d st a k eb o t ha v a i l a b l eg r a d i e n ta n df u n c t i o nv a l u ei n f o r m a t i o n f u r t h e r m o r e ，t h e i rm o d i f i c a t i o n sa r ep r o p o s e d t h eg l o b a lc o n v e r g e n c eo f t h e s em e t h o d sa r ep r o v e dr e s p e c t i v e l y 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 e s ea l g o r i t h m s a l ee f f i c i e n t 2 t l l ec o n j u g a t eg r a d i e n ta l g o r i t h m sf o rl a r g es c a 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 s ( n c p ( f ) ) a l ep r o p o s e d ( i ) w r ep r e s e n tan e wp r p t y p ec o n j u g a t eg r a d i e n tm e t h o d f o rs o l v i n gl a r g es c a 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 sb a s e do nan o n l i n e a rs y s - t e r no fe q u a t i o n sr e f o r m u l a t e db yf i s e h e r - b u r m e i s t e rn c p f u n c t i o n ，w h i c hs a t i s f i e st h e s u f f i c i e n td e s c e n tc o n d i t i o nw i t h o u tr e q u i r i n ga n ya s s u m p t i o n u n d e rt h ec o n d i t i o n s t h a tf ：形_ 研i sac o n t i n u o u s l yd i f f e r e n t i a b l ep 0 + r of u n c t i o na n dt h ej a c o b i a n m a t r i xf 7 ( z ) s a t i s f i e sg l o b a ll i p s c h i t z i a nc o n t i n u i t yo nl e v e l s e t ，g l o b a lc o n v e r g e n c e r e s u l ti se s t a b l i s h e d n u m e r i c a le x p e r i e n c ei sr e p o r t e dw h i c hd e m o n s t r a t e sg o o dc o i n - p u t a t i o n a lp e r f o r m a n c eo nl a r g es c a l en c p ( f ) ( i i ) ap r p t y p es m o o t h i n gc o n j u g a t e g r a d i e n tm e t h o df o rs o l v i n gl a r g es c a 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 si sp r o p o s e d b a s e do nas m o o t h i n gn o n l i n e a rs y s t e mo fe q u a t i o n sr e f o r m u l a t e db ys m o o t h i n gf i s c h e r - b u r m e i s t e rf u n c t i o n a te a c hi t e r a t i o n ，t w oa r m i j ol i n es e a r c h e sa l ep e r f o r m e d ，w h i c h g u a r a n t e et h ep o s i t i v ep r o p e r t yo ft h es m o o t h i n gp a r a m e t e rpa n dm i n i m i z et h em e r i t f u n c t i o nf o r m e db ys m o o t h i n gf i s c h e r - b u r m e i s t e rf u n c t i o n ，r e s p e c t i v e l y g l o b a lc o n v e r - g e n c ei so b t a i n e dw h e nf ：衍- 衍i sac o n t i n u o u s l yd i f f e r e n t i a b l ep 0 + r 0f u n c t i o n f i n a l l y , n u m e r i c a le x a m p l e sa r eg i v e nt os h o wt h ee f f e c t i v e n e s so ft h em e t h o d i v 3 t h es e m i d e f i n i t ec o m p l e m e n t a r i t ym e t h o d sa r ep r e s e n t e dt os o l v es e m i d e f i n i t ep r o g r a m - m i n g ( s d p ) f i r s t l y , as p e c i a lt y p eo fs e m i d e f i n i t ep r o g r a m m i n g ( n a m e l y , t h ed u a lp r o b - l e mc o n t a i n st h ec o n s t r a i n ty 0 ) i sc o n s i d e r e d t h eo p t i m a l i t yc o n d i t i o n so fs e m i d e f i n i t ep r o g r a m m i n gi sr e f o r m u l a t e de q u i v a l e n t l ya sas e m i d e f i n i t ec o m p l e m e n t a r i t yp r o b - l e m ( s d c p ) ，a n dt h e nap r e d i c t o r c o r r e c t o rs m o o t h i n gn e w t o na l g o r i t h mf o rs d c p i sp r e s e n t e d t h ee x i s t e n c eo fn e w t o nd i r e c t i o n s ，b o u n d e d n e s so fi t e r a t e sa n dg l o b a l c o n v e r g e n c ea r ep r o v e d l o c a ls u p e r l i n e a rc o n v e r g e n c ei sp r o v e du n d e rt h ea s s u m p t i o n t h a tt h eg e n e r a l i z e dd e r i v a t i v ea ts o l u t i o np o i n ta r ei n v e r t i b l e s e c o n d l y , t h eo p t i m a l i t y c o n d i t i o n so ft h es t a n d a r ds e m i d e f i n i t ep r o g r a m m i n gi sr e f o r m u l a t e da sag e n e r a l i z e d s e m i d e f i n i t ec o m p l e m e n t a r i t yp r o b l e m ( g s d c p ) t h e n ，e n l i g h t e n e db ys o m et e c h n i q u e s i na l g o r i t h m sf o rn c p ( f ) ，w ep r e s e n tap r e d i c t o r - c o r r e c t o rs m o o t h i n gn e w t o na l g o - r i t h ma n dp r o v et h ee x i s t e n c eo fn e w t o nd i r e c t i o n s ，b o u n d e d n e s so fi t e r a t e sa n dg l o b a l c o n v e r g e n c e l o c a lq u a d r a t i cc o n v e r g e n c ec a nb eo b t a i n e du n d e rt h ec o n d i t i o nt h a tt h e g e n e r a l i z e dd e r i v a t i v ea ts o l u t i o np o i n ta r ei n v e r t i b l e t h ep r e s e n t e dm e t h o d sg e n e r a t e s y m m e t r i cd i r e c t i o n sw i t h o u ta n yf u r t h e rt r a n s f o r m a t i o n s 4 t h en o n i n t e r i o rc o n t i n u a t i o nm e t h o df o rs e m i d e f i n i t ec o m p l e m e n t a r i t yp r o b l e m ( s d c p ) i se x t e n d e dt os e m i d e f i n i t ep r o g r a m m i n g ( s d p ) t h ee x i s t e n c eo fn e w t o nd i r e c t i o n s i sp r o v e d t h eb o u n d e d n e s so fi t e r a t e sg e n e r a t e db yt h em e t h o di so b t a i n e du n d e r t h ec o n d i t i o nt h a tt h en e i g h b o r h o o di sb o u n d e d ，a n dt h eg l o b a lc o n v e r g e n c ei sp r o v e d l o c a lq u a d r a t i cc o n v e r g e n c ef o l l o w sf r o mt h ea s s u m p t i o nt h a tt h eg e n e r a l i z e dd e r i v a t i v e a ts o l u t i o np o i n ta r ei n v e r t i b l e s o m en u m e r i c a lr e s u l t sa r ea l s or e p o r t e d 5 t h ep r p + c o n j u g a t eg r a d i e n ta l g o r i t h mf o rs o l v i n gs e m i d e f i n i t ep r o g r a m m i n g ( s d p ) i s d i s c u s s e d b a s e do i lt h ef i s c h e r - b u r m e i s t e rs d c p - f u n c t i o n am e r i tf u n c t i o nw i t hg l o b - a l l yl i p s c h i t z i a nc o n t i n u o u s l yg r a d i e n tf o rt h eo p t i m a l i t yc o n d i t i o n so fs d p i sp r o p o s e d ， w h i c hr e f o r m u l a t e st h eo p t i m a l i t yc o n d i t i o n sa sa nu 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 ep r p + c o n j u g a t eg r a d i e n ta l g o r i t h mi sa p p l i e dt os o l v et h i sp r o b l e m i no r d e rt o o b t a i nt h ec o n v e r g e u c eo ft h ep r p + m e t h o da n dd e c r e a s et h ef u n c t i o ne v a l u a t i o na t e a c hi t e r a t i o n ，w ep r o v i d ean e wa r m i j o t y p el i n es e a r c hr u l e g l o b a lc o n v e r g e n c eo f t h ea l g o r i t h mi sp r o v e dw i t h o u tr e q u i r i n gt h eb o u n d e d n e s so fl e v e ls e ta n de x i s t e n c eo f a c c u m u l a t i o np o i n to fp r o d u c e ds e q u e n c eb yt h em e t h o d k e y w o r d s g r a m m i n g ，n e w t o n g e n c e c o n j u g a t eg r a d i e n tm e t h o d ，c o m p l e m e n t a r i t yp r o b l e m ，s e m i d e f i n i t ep r o - 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 rc o n v e r g e n c e ，q u a d r a t i cc o n v e r - v 符号说明 本文所用符号，除文中特别说明外，均按如下规定： 1 疵表示实数集，皿+ ，匠十+ 分别表示非负及正实数集，表示自然数集 2 卿表示n 维欧氏空间， 婢，厨华+ 分别表示研的非负卦限和正卦限，即 丑珥= ( 茁1 ，x 2 ，z 住) t i i 0 ，i ) ，卫珲+ = ( z 1 ，x 2 ，z n ) t i z i o ，i ) 3 毋肌表示nxn 实矩阵空间 4 i | j j 表示衍中的向量范数 5 v ( x ) 表示，( z ) 在x 点处的梯度向量 6 s u p 表示取上确界，i n f 表示取下确界，l i m s u p 表示取上极限，l i m i n f 表示取下 极限，m a x 表示取最大值，m i n 表示取最小值 7 对向量z ，投影算子z + = m a x ( 0 ，z ) ，z 一= m i n ( 0 ，z ) ，其中m a x ，m i n 按分量计算 8 x t 表示向量x 的转置，( x ，y ) 和x t y 都表示毋中向量x = x l ，x 2 ，z 竹) t 与 y = y l ，y 2 ， t 的内积，即 9 a t 表示矩阵a 的转置，表示单位矩阵。 1 0 v 表示对任意的，j 表示至少存在一个，表示属于，表示不等于 1 1 e 表示分量均为1 的向量，巳表示第i 个分量为1 其他分量均为0 的向量 1 2 o 表示同阶无穷小，o 表示高阶无穷小，i 表示证完 v i 玑 z n：l 1 1 秒 t z | i y z 原创性声明 本人声明：所呈交的学位论文足本人在导师的指导下进行的研究- 【二作及取得的研究成果 除本文已经注明引用的内容外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得内蒙古大学及其他教育机构的学位或证书而使用过的材料。勺我一同j 二作的同志对本研究 所做的任何贡献均已在论文中作了明确的说明并表示澍意。 学位论文作者签名：鸟鹈箕。 指导教师签名： e t 期： 日期： 在学期间研究成果使用承诺书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：内蒙古大学有权将学位 论文的全部内容或部分保留并向国家有关机构、部门送交学位论文的复印件和磁盘，允许编入有 关数据库进行检索，也可以采用影印、缩印或其他复制手段保存、汇编学位论文。为保护学院和 导师的知识产权，作者在学期间取得的研究成果属于内蒙古大学。作者今后使用涉及在学期间主 要研究内容或研究成果，须征得内蒙古大学就读期间导师的同意；若用于发表论文，版权单位必 须署名为内蒙古大学方可投稿或公开发表。 学位论文作者签名： 日期： 钮 哔 指导教师签名： 日期： 趣 蝌 l粒半 第一章引言 1 1互补问题及算法研究进展 互补问题是运筹学与计算数学的一个交叉研究领域，以其与线性规划、二次规 划、变分不等式和约束优化问题的最优性条件之间的密切联系成为数学规划的一个 基本问题【l ，2 1 ，在力学、工程、经济、交通等许多实际部门有广泛的应用【5 6 1 经过四 十多年的发展，其理论体系、数值方法和应用领域日渐完善、深入和扩大，成为数学 规划中的一个十分热门的研究课题，引起众多数学工作者的广泛兴趣和高度重视，参 见h a r k e r 和p a n g 的综述性文章【2 2 】，c o t t l e ，p a n g 和s t o n e 的专著 4 】，f e r r i s 和p a n g 的 综述性文章 6 】，f a c c h i n e i ，p a n g 的专著【5 】和韩继业，修乃华，戚厚铎的专著 7 】等 1 1 1 定义与基本事实 1 9 6 4 年，c o t t l ef 1 】首先研究了非线性互补问题，其主要目的是计算非线性规划 的驻点而“互补问题”称谓的启用是在c o t t l e ，h a b e t l e r ，l e m k e 的文章 2 】中1 9 6 6 年，h a r t m a n 和s t a m p a c c h i a 【8 】提出变分不等式的概念在对互补问题和变分不等式 的研究初期，人们并未注意到它们之间的关系，到1 9 7 1 年，k a r a m a r d i a n 3 1 证实了非 线性互补问题是变分不等式的特例，从此，互补问题总是被看作变分不等式的特例 1 1 1 1变分不等式和互补问题的概念 定义1 1 1 设x 是衍的非空子集，f 是从形到它自身的映射变分不等式， 记为v i ( x ，f ) ，是指：求矿x ，使对任意y x 有 一矿) t f ( x + ) 0 ( 1 1 1 ) 在上述定义中，x 一般是非空闭凸集，在许多情况下，x 为多面体当 x = 【a ，6 】= x i r n l a t 婉玩，i 时，称v i ( x ，f ) 为箱约束变分不等式或混合互补问题，记为b v i ( a ，b ，f ) 或m c p ( a ，b ，f ) 特别地，若a i = 0 ，b i = + o o ，i n ，则混合互补问题蜕化为非线性互补问题，记为 n c p ( f ) 通常将n c p ( f ) 等价表述为：求矿衍使得 z + 0 ，f ( x + ) 0 ，f ( x + ) t z + = 0 ( 1 1 2 ) 1 第一章引言 集合尸= z 衍i z 0 ，f ( x ) 0 ) 称为n c p ( f ) 的可行域，x 厂称为n c p ( f ) 的可 行点，如果满足z 0 ，f ( z ) 0 ，则称z 为n c p ( f ) 的严格可行点若f 是仿射函数，即 f ( x ) = m x + q ，m 研姗，g 帮，则n c p ( f ) 蜕化为线性互补问题，记为l c p ( q ，m ) 在不需要考虑线性与非线性互补问题的差别时，我们一般用互补问题统称之 从几何直观上看，式( 1 1 1 ) 意味着f ( x + ) 必与始自矿的所有可行方向成锐角 以坛 ) 表示x 在z 处的法锥，即 k c 茁，= 三i i z t 可一z 。v 秒x 喜孟。亍x c 1 1 3 ， 则x + x 是v i ( x ，f ) 的解当且仅当- f ( x + ) 坛( 矿) 如果f ( x ) 是某个可微函数 ，( z ) 的梯度，即f ( x ) = v ，( z ) ，x 衍为凸子集，则v i ( x ，f ) 恰好是约束优化问题 m z i x n ，( z ) 的一阶必要条件由定义易见，约束最优化问题的k k t 条件就是一个混合 互补问题式( 1 1 2 ) 意味着对非负卦限的每个x + 其在映射f 下的象f ( x ) 也在非负 卦限中且与z + 正交 1 1 1 2解的存在性、唯一性和解集的有界性 变分不等式v i ( x ，f ) 不一定有解，但当x 为非空凸紧集而f 在x 上连续时， v i ( x ，f ) 有解因此，如果x 为非空闭凸集，f 在研上连续，且存在x 的非空有 界集d ，使得对任意x x d ，有y d 满足( x 一可) t f ( x ) 0 ，则v i ( x ，f ) 有解如 果存在x o x ，使得 l i m 一护) t f ( z ) l l x l i = ， x e x ，忙i i o o 、 则称f 相应于x 是强制的设x 为非空闭凸集，f 在x 上连续，如果f 相应于x 强制，则v i ( x ，f ) 有非空紧解集设x 为非空闭凸集，f 在x 上连续，如果存在 z o x ，使得 z x l 一x 0 ) t f ( x ) 有界，则v i ( x ，f ) 的解集为紧集 定义1 1 2 设m 为1 0 , 佗矩阵称m 为 ( i ) 正定矩阵，如果z t m x 0 对任意0 z 衍成立； ( i i ) 半正定矩阵，如果z t m x 0 对任意z 础成立； ( i i i ) p 一矩阵，如果m 的所有主子式皆为正实数； ( i v ) 岛一矩阵，如果m 的所有主子式皆为非负数； ( v ) 凰一矩阵，如果线性互补问题l c p ( 0 ，m ) 只有零解 内蒙古大学博士学位论文 半正定矩阵必为晶一矩阵，正定矩阵必为p 一矩阵，p 一矩阵既是岛一矩阵又是风一 矩阵 定义1 1 3 设f ：衍一册称j 为 ( i ) p 0 一函数，若对任意z ，y 研，z y ，存在i n 使得( 甄一犰) 暇( z ) 一只( ! ，) 】0 且婉y i ； ( i i ) p 一函数，若对任意z ，y 帮，z y ，存在i n 使得一纨) 限x ) 一只( 秒) 】 o ； ( i i i ) 一致p 一函数，若存在常数o 0 ，使得m 。a x ( x t 一玑) 【鼠( z ) 一只( 可) 】o 忙一训2 对任意z ，y 殿成立； ( i v ) 单调函数，若 一) t f ( z ) 一f ( 秒) 】0 对任意z ，y 衍成立； ( v ) 严格单调函数，若 一可) t 旧( z ) 一f ( 可) 】 0 对任意茁，可翮成立； ( 访) 强单调函数，若存在常数a 0 ，使得 一可) t f ( z ) 一f ( w 】a l l x 一洲2 对任 意z ，y 衍成立； ( v i i ) 风一函数，若对任意满足 忙七i i c o 也i m 。i n f 酱 0 ，l i m i n f1 m i n i 矿f i ( x k ) 。 的序列 扩) ，必存在一个下标j 使当k o o 时，有 苟 _ o o ， f j ( x 南) 】- _ o o ( v i i i ) 珊一函数( 即为弱风一函数) ，若对任意满足 l 渖七i l _ o o ，l i m s u pl i 七) 一l i o 。，l i m s u pl i ( f ( x 知) ) 一l l o o 的序列 扩】- ，必存在一个下标j 使当k _ o o 时，有 z ；) _ 0 0 ， 乃 南) ) _ o 。 单调函数必为r 一函数，严格单调函数必为p 一函数，强单调函数必为一致尸一 函数一致p 一函数既是蜀一函数又是r 0 一函数l i 6 定理1 1 1 1 7 1 设f 是c 1 一函数，那么，f 为局一函数当且仅当f 的j a c i b i 矩 阵在任意点处均为岛一矩阵；若f 为一致p 一函数，则f 的j a c i b i 矩阵在任意点处 均为p 矩阵 3u 第一章引言 风一函数【1 6 】和础一函数【1 8 】的概念是从线性互补问题中经常用到的强制性条件 风一矩阵的概念推广而来的，在理论分析中所起的作用就是保证所构造的价值函数 是强制的，即保证。 1 珥伊( z ) = + ，换, a - - j 话说，即保证水平集 z 皿佗l e ( x ) o ) 对 任意正数a 都有界，这里e ( x ) 是n c p ( f ) 的价值函数这样的条件还有下面的假设 1 1 1 ，显然，假设1 1 1 是其中最弱的条件 假设1 1 1 【1 9 】若序列 z 七) 满足 f i 扩f f _ ，l i r a s u p | | ( ) 一| f 0 时，用n e w t o n 法解下 面的摄动方程组 h ( x , y ) ：i 可一f i ：0 ， ( 1 1 4 ) l x 耖p l 其中p 0 为摄动参数随着p _ 0 ，方程组( 1 1 4 ) 的解( z ) ，可( p ) ) 描绘出一条通向 互补问题解集的曲线，即所谓的“中心路径”，因而这种方法又称为路径跟踪法该方 法首先由k o j i m a ，m i z u n o 和y o s h i s e 矧提出在【2 4 】中他们应用2 一范数定义了一点到 中心路径的距离，实际上可以采用其他形式度量距离1 9 8 9 年，k o j i m a ，m i z u n o 和 y o s h i s e 【9 】首先提出求解线性互补问题的内点算法，在矩阵m 半正定且l c p ( q ，m ) 有 严格可行点的假设下，算法具有多项式时间复杂性k o j i m a ，k u r i t a 和m i z u n o 1 0 1 推 广线性规划内点法求解m 半正定的l c p ( q ，m ) ，提出两种步长规则g ，和p 7 证明了使 用g 7 的内点法全局收敛，而使用p 7 的内点法具有多项式时间复杂性j i 等f 3 2 】通过 预估校正法证明了单调线性互补问题的内点算法不仅是多项式时间的，且具有局部 二次收敛性m i a o 嘲将这一方法推广到只一矩阵线性互补问题，证明了算法的多项 式时间复杂性和局部二次收敛性与以往光滑因子的选取不同，a c h a c h e 【2 5 】用非负 向量作为光滑因子将线性互补问题转化为加权问题，进而提出加权路径跟踪法算法 第一章引言 具有多项式时间复杂性在l c p ( q ，m ) 的严格可行解集非空，m 半正定且度量函数 盯 0 为 参数，r 0 为加权向量，则( p ) 妒的解 ( z ( p r ) ，叫( p r ) ：p 0 ) t 构成光滑加权中一l - 路 径在严格可行集非空及m 半正定的假设下，其加权路径跟踪法全局线性收敛且具 有多项式时间复杂性z h a o 和l i 2 7 利用中心路径和正则路径的组合给出正则中心 路径的概念，并为只一非线性互补问题提出新的路径跟踪法，全局收敛性依赖于算 法参数的选取，而超线性收敛性需要迭代点的梯度的逆有界的假设 线性互补问题的势函数为 n ( z ，y ) = ( 佗+ ) l o g x t y 一l o g x t 犰一nl o gn ， i - - - - 1 其中 0 为一参数，而势缩减法就是要产生一个点列 ( 矿，y k ) ) ，使其满足( 扩，y 七) 丑珥+ 卫珥+ ， ( z 知+ 1 ，y 七十1 ) ( z 南，y 七) 一5 ，vk ， 这里6 是不依赖于k 的正数第一个势缩减的内点法首先由k a r m 盯k a r 于1 9 8 4 年为 求解线性规划问题而提出1 9 9 1 年，k o j i m a 等【2 8 】提出了第一个求解线性互补问题 的势缩减法进一步的讨论见文献 2 9 】，在 2 9 】中作者给出路径跟踪法和势缩减法的 统一框架1 9 9 2 年，y e 删利用势缩减法求解p 一矩阵的线性互补问题，算法具有多 项式时间复杂性p a r d a l o s ，y e 等【3 1 】将势缩减法推广到r 一矩阵线性互补问题，证 明了算法的全局收敛性，但没有算法的复杂性结论【3 5 】将内点法推广到非线性互补 问题，并在f ( x ) 为一致p 一函数及其它假设下讨论了算法的收敛性和计算复杂性 2 方程组法 这类方法需借助n c p 一函数将互补问题( 1 1 2 ) 转化为等价的非线性方程组所 谓的n c p 一函数，即函数：疵2 _ 尻，满足( o ，b ) = 0 营a 0 ，b 0 ，a b = 0 常见的 n c p 一函数有： c m ( a ，b ) = m i n ( a ，6 ) ， c r a ，b ) = 石巧万一a b ， ( 口，b ) = ( a 一6 ) 2 一a l a i 一6 1 6 i ， ( 1 1 5 ) ( 1 1 6 ) ( 1 1 7 ) 其中，函数( 1 1 5 ) 为极小函数，当且仅当a = b 时不可微；( 1 1 6 ) 为f i s c h e r - b u r m e i s t e r 函数删，当且仅当a = b = 0 时不可微；( 1 1 7 ) 源于m a n g a s a r i a n 【3 7 1 ，在匝2 上处处可 6 内蒙古大学博士学位论文 微关于n c p 一函数的更多讨论，参见【1 9 ，3 8 ，3 9 ，4 0 n c p 一函数的作用是将包含等 式和不等式的三个条件的互补问题转化为一个等式，从而把一个复杂的等式不等式 系统归结为解方程组的问题 对任意给定的n c p 一函数咖，定义映射h ：研_ 衍如下： h ( x ) = ( z t ，r ( z ) ) ： ( z n ，r ( z ) ) = 0 ， 则矿为非线性互补问题n c p ( f ) 之解的充要条件是矿是非线性方程组h ( x ) = 0 的 解该类方法的基本思想是把互补问题转化为与之等价的方程组，然后用n e w t o n 法 或广义n e w t o n 法求解可分为非光滑方法和光滑化方法 ( 1 ) 非光滑方法 该方法开始于2 0 世纪9 0 年代早期，随着人们对非光滑研究的不断深入，该方法 的研究得到迅速发展，并成为当时最优化领域中极为活跃的研究方向之一这类方法 把互补问题转化为一个与之等价的非光滑方程组，由于此时方程组非光滑，因而经典 的n e w t o n 法不再适用，需要用非光滑方程组理论和算法，求方向时利用广义牛顿方 程俨驴= 一h ( x k ) ，v 膏o h ( x 七) 半光滑理论的建立，极大促进了求解互补问题非光 滑方法的发展p a n g 和g a b r i e l 【1 1 】提出了n e s q p 方法，在解的正则性条件下，算 法局部超线性或二次收敛h a r k e r 和x i a o 【4 1 】利用j e 7 一导数提出了一类广义牛顿法， 算法的全局收敛性需f ( x ) 为一致p 一函数的假设f i s c h e r 【1 2 】提出求解线性互补问 题的广义牛顿法，为克服v 七o h ( x 七) 的奇异性，采用y 七的非奇异扰动矩阵y 知，使 广义牛顿方程 扩= 一g ( x 七) 唯一可解在解的非退化条件下，算法二次收敛对非 线性互补问题，j i a n g 和q i 【1 3 】基于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 【1 4 】利用矩阵v 知o s h ( x 七) 和广义牛顿方程v 膏d + h ( x 知) = 0 提出 求解n c p ( f ) 的广义牛顿法，但若广义牛顿方程不可解或广义牛顿方向不是价值函数 0 ( x ) 的充分下降方向，则算法采用最速下降方向铲= 一v o ( x 知) 算法全局收敛到o ( x ) 的稳定点矿，且当日在矿点b d 一正则时算法局部超线性或二次收敛为克服使用 最速下降方向这一缺点，y a m a s h i t a 1 5 】提出修正广义牛顿法，构造v 知o s h ( x 知) 的 扰动矩阵渺，使广义牛顿方程胪扩= 一h ( x 七) 唯一可解且其解总是价值函数o ( x ) 的 充分下降方向在较弱的条件下，算法全局收敛且具有局部超线性或二次收敛率 7 第一章引言 l u c a ，f a c c h i n e i 和k a n z o wi 倒对基于极小函数和基于f i s c h e r - b u r m e i s t e r 函数的各种广 义n e w t o n 算法进行了从理论到数值结果的比较、评价，详细讨论了这些算法的全局 和局部收敛所需要的条件s u n ，w o m e r s l e y 和q i 鹞】为混合互补问题提出的可行半光 滑牛顿法克服了投影类半光滑牛顿法可能出现的不收敛性，在解的b d 一正则性条件 下得到算法的超线性或二次收敛性k a n z o wf 删提出互补问题的非精确半光滑牛顿 法，用l i v 七d + h ( x 七) l l r l k h h ( x 后) | i 取代广义牛顿方程v 膏d + h ( x 知) = 0 ，其中讯为强 迫因子若饥_ 0 ，算法超线性收敛；若讯= o ( 1 l h ( x ) 忱则二次收敛c h e n 和p a n 【4 5 j 用正则化技术及广义f i s c h e r - b u r m e i s t e r 函数将互补问题转化为一系列正则互补问 题，进而提出正则半光滑牛顿法若f 是r 一函数且在解的c d 一正则性条件