（应用数学专业论文）二阶锥互补问题的光滑算法研究.pdf

摘要 摘要 在这篇文章里，我们研究二阶锥瓦补问题( 简记为s o c c p ) ，这个问题是寻找 一个向量，这个向量同时满足一个方程组和一个定义在二阶锥笛卡尔积上的互补 性条件。它是一类内容新、涵盖面宽、理论丰富、且有广泛应用背景的均衡优化 问题。本文首先简述了二阶锥互补问题的基本知识，包括二阶锥互补问题的理论、 算法和研究现状，然后利用欧几里得若当代数技术，给出s o c c p 的3 种光滑算法。 具体如下： 1 、在s o c c p 光滑算法哺1 的基础上进行改进，给出二阶锥瓦补问题的一个基于 非单调线搜索的光滑牛顿法。该算法对初始点的选取没有要求，在异性质的假设 下给出算法的全局收敛性和局部超线性收敛性分析，最后给出算法的数值实验， 数据结果说明本文的算法要比原光滑算法瞳旬的效果好。 2 、将线性规划的预估校正光滑化方法h 1 1 扩展到二阶锥互补问题中来，基于 c h e na n dm a n g a s a r i a n 族光滑函数给出了一个求解二阶锥互补问题的非内点预估 校正路径跟踪法。该算法对初始点的选取没有任何限制，我们给出了算法的全局 收敛性及局部二次收敛性分析，并且给出数值实验，数据结果说明该算法比求解 二阶锥规划的预估校正光滑算法m 1 的效果好。 3 、将线性规划的预估校正光滑牛顿法h 6 1 扩展到二阶锥瓦补问题中来，基于 c h e na n dm a n g a s a r i a n 族光滑函数给出了一个求解二阶锥互补问题的预估校正光 滑牛顿法。中心路径的邻域没有在算法中出现，因此不需要另外的计算去保证迭 代序列位于给定的邻域内，该算法比求解二阶锥规划的预估校正光滑算法口u 简单。 该算法对初始点的选取也没有任何限制，我们给出了算法的全局收敛及局部超线 性收敛性分析，并且给出数值实验说明算法的有效性。 关键词：二阶锥互补问题非单调线搜索光滑化方法预估校正 a b s t r a c t i nt h i sp a p e r , w es t u d yt h es e c o n d o r d e rc o n ec o m p l e m e n t a r i t yp r o b l e m ( s o c c p f o rs h o r t ) t h i sp r o b l e mi st of i n dav e t o rs a t i s f y i n gas y s t e mo fe q u m i o n sa n da c o m p l e m e n t a r i t yc o n d i t i o nd e f i n e do nt h ec a r t e s i a np r o d u c to fs e c o n d o r d e rc o n e s ， s i m u l t a n e o u s l y ，i th a sw i d ea p p l i c a t i o n si ne n g i n e e r i n g ，e c o n o m i c s ，m a n a g e m e n t s c i e n c e ，a n do t h e rf i e l d s i nt h ep a p e r , f i r s t l yt h et h e o r y , a l g o r i t h m ，a n dr e c e n t r e s e a r c ho ft h es e c o n d - c o n ec o m p l e m e n t a r i t yp r o b l e mi s s u m m a r i z e d ，w ep r o p o s e t h r e ek i n d so f s m o o t h i n ga l g o r i t h mu s i n gj o r d a na l g e b r a i ct e c h n i q u e t h e no u rs o m e w o r ki na l g o r i t h mi si n t r o d u c e d f o rd e t a i l ，w ec o n c l u d et h e ma sf o l l o w s ： 1 i nt h i s p a p e r , b a s e do nt h es m o o t h i n gm e t h o df o rs o c c p z r , w ep r o p o s ea s m o o t h i n ga l g o r i t h mf o rs o l v i n gt h es o c c pw i t han o n m o n o t o n el i n es e a r c h t h i s a l g o r i t h md o e sn o th a v er e s t r i c t i o n sr e g a r d i n gi t ss t a r t i n gp o i n t w es h o wt h a tt h e a l g o r i t h mi sg l o b a l l yc o n v e r g e n ta n dl o c a l l ys u p e r l i n e a r l yc o n v e r g e n tw i t hap 0 f u n c t i o n f i n a l l y ，t h ee x p e r i m e n ti sg i v e na n dt h ed a t ar e s u l tp r o v et h a tt h i sa l g o r i t h m i ss u p e r i o rt ot h es m o o t h i n gm e t h o d 2 w ee x t e n dt h e p r e d i c t o r - c o r r e c t o rs m o o t h i n gm e t h o df 0 rl p t ot h e s e c o n d - o r d e rc o n ec o m p l e m e n t a r i t yp r o b l e m ，b a s e do nc h e na n dm a n g a s a r i a n s m o o t h i n gf u n c t i o n ，an o n - i n t e r i o r - p o i n tp r e d i c t o r - c o r r e c t o rp a t hf o l l o w i n gm e t h o di s p r e s e n t e di nt h i sp a p e r t h i sa l g o r i t h md o e sn o th a v er e s t r i c t i o n sr e g a r d i n gi t ss t a r t i n g p o i n t w es h o wt h a tt h ea l g o r i t h mi s g l o b a l l yc o n v e r g e n ta n dq q u a d r a t i c a l l y c o n v e r g e n t f i n a l l y ，t h ee x p e r i m e n ti sg i v e na n dt h ed a t ar e s u l tp r o v et h a tt h i s a l g o r i t h mi ss u p e r i o rt ot h ep r e d i c t o r - c o r r e c t o rs m o o t h i n g a l g o r i t h mf o rs o c p 3 1 1 3 w ee x t e n dt h e p r e d i c t o r - c o r r e c t o rs m o o t h i n gm e t h o df o rl p 拍1t ot h e s e c o n d - o r d e rc o n ec o m p l e m e n t a r i t yp r o b l e m ，b a s e do l lc h e na n dm a n g a s a r i a n s m o o t h i n gf u n c t i o n ，ap r e d i c t o r - c o r r e c t o rs m o o t h i n gm e t h o df o rs o l v i n gs o c c pi s p r e s e n t e d ，t h en e i g h b o r h o o do fp a t hd o e sn o ta p p e a ri nt h ea l g o r i t h m ，t h u s ，i td o e sn o t n e e daf e wa d d i t i o n a lc o m p u t a t i o n sw h i c hk e e pt h ei t e r a t i o ns e q u e n c es t a y i n gi nt h e g i v e nn e i g h b o u r h o o d ，m ea l g o r i t h mi ss i m p l e rt h a nt h ep r e d i c t o r - c o r r e c t o rs m o o t h i n g a l g o r i t h mf o rs o c pl 3 l 】，i td o e sn o th a v er e s t r i c t i o n sr e g a r d i n gi t ss t a r t i n gp o i n t w e s h o wt h a tt h ea l g o r i t h mi sg l o b a l l yc o n v e r g e n ta n dl o c a l l ys u p e r l i n e a r l yc o n v e r g e n t f i n a l l y ，s o m ep r e l i m i n a r yc o m p u t a t i o n a lr e s u l t sa r er e p o r t e d k e y w o r d s ：s e c o n do r d e rc o n ec o m p l e m e n t a r i t y n o n m o n o t o n el i n es e a r c h s m o o t h i n gm e t h o d p r e d i c t o r - c o r r e c t o r 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名： 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在年解密后适用本授权书。 本人签名：受益翻 导师签名：立恤旦 日期：兰 ! ：互：z 日期：迎争 第一章绪论 第一章绪论 本章首先介绍y - - 阶锥互补问题的模型和研究现状：然后讲述了二阶锥的基 础知识，即二阶锥的若当代数性质，最后列出了本文的预备性知识及主要工作。 1 1 二阶锥互补问题的模型和研究现状 二阶锥互补问题( s o c c p ) 是指在二阶锥( s o c ) 约束条件下，两组决策变量 之间满足一种互补关系，它是一类均衡优化问题，其核心是运用严谨的数学方法并 以电子计算机与网络为工具，研究存在这种互补关系的各种复杂系统及相应的解 决方案，为决策者提供科学决策的依据，最终达到复杂系统运行的均衡和谐目标。 二阶锥具有优美的几何结构( 例如三维的二阶锥形如冰激凌，因此又称二阶锥为冰 激凌锥) ，鲜明的代数特征( 若当代数) ，以及能在该锥上进行整体函数值分析， 二阶锥上的瓦补问题是一类内容新、涵盖面宽、理论丰富、且有广泛应用背景的 均衡优化问题。s o c c p 是二阶锥规划的一个推广，包括线性和非线性二阶锥互补问 题。 在本文中，令r 一表示刀维列向量，记号( z ，x 。) r 川xr h 表示 ( 0 ，x ：) r r 一r “，即( x i ，) r 川r 一一表示r 伪r 一”上的列向 量。二阶锥互补问题( s o c c p ) 定义为：找( x ，s ，4 - ) r ”r ”r ”使得 x k ，s k ，xo s = 0 ，f ( x ，s ，f ) = 0 ， 这里f ：r ”r ”x r ”一r ”r ”是连续可微映射，kcr ”二阶锥上的笛卡尔积， 即k = k 4 1 k “2 k “，这里n ，n l ，n n l ，n i + n n = n ， x = ( x ”，x 。) k ， s = ( s l ，s 。) k ， x o j = ( x lo j l ，x 。o s n ) ，v x ，s r ” 且玎，维二阶锥k 嘶c r 一定义为： k n ；= ( x i l ，x ；：) r r n i - i ：峪x i l ) ， i n t ( k 砷) = ( x i l ，x i 2 ) r xr n , - 1 忆20 r ”，非线性互补问题( n c p ) 就是找x r ”，使得 x 0 ，( 石) 0 ，x r f ( x ) = 0 。显而易见，当1 3 l = n n = 1 ，r ( x ，j ，f ) = 厂( z ) y 时， _ 阶锥互补阎题的光滑算法研究 s o c c p 就等价于n c p 。另外，s o c p 被写为： m i n i m i z e 口( z ) s t ，( z ) k 这里曰：r ”一r ，y ：r ”一尺”是连续可微函数。s o c p 的k k t 条件为： z k ，7 ( z ) k ，名y ( z ) = 0 ，v o ( z ) + v r ( z ) a = 0 这里彳r ”为l a g r a n g e 乘子。令 捌舻时一砌川= ( v 口篇z ，兄) ， 则s o c p 的k k t 条件就等价于s o c c p 。 令s ”是玎刀的矩阵集，f ：r ”xr ”r ”jr ”r ”为一给定函数。则半定互 补问题( s d c p ) 表述为： 找( x ，y ，f ) s 一s 一s r 使得 x 三o ，眨o ，x y = o ，f ( x ，y ，f ) = 0 ， 这里x 三o 的意思是x 为半正定矩阵，算子表示矩阵内积，即：x y = t r ( x r 】，) 。 半定规划的k k t 条件可以被写为s d c p 的形式。尤其是对x = ( 而，屯) r x r n - i 与矩 阵x ：f 五，1 有下面关系： l 恐五 x 兰o x k ”。 这样，问题的维数从原来的刀维增加到n ( n + 1 ) 2 维，所以它的计算量要比原s o c 约束问题的计算量大的多。 近几年来，人们对s o c c p 的研究呈上升趋势，主要研究内容包括：解的存在性与 特征，价值函数和误差界乜删各种优化方法：其中包括矩阵分裂法n 1 1 对，内点算法 1 3 - 2 0 ，价值函数法胁剖，光滑和半光滑牛顿法“q ，各种实际应用2 删。这些算法中大 部分算法都是建立在s o c - f t 补函数( 价值函数) 的基础上，将s o c c p 问题重新表述为 一个与其等价的方程组来实现求解的目的。尽管已经有许多关于s o c c p 有效的算 法，但还有许多问题需要研究。研究s o c c p 的另外一个动机是它的应用性：对于线 性s o c p i 商q 题，已经有许多有效的算法n 3 诩肚3 副，然而对非线性s 0 c p 问题的算法就相 对比较少。由于s o c p 的k k t 条件可以化为s o c c p ，我们就可以应用s o c c p 的算法来解 s o c p ；另外，许多均衡问题以及纳什均衡问题就也可以重新表述为s o c c p 口2 删。 1 2 二阶锥上的若当代数 对任意的z = ( x ix ：) ，y = ( y ，y ：) r x r 一_ l ，定义k ”上的一个若当积： 第章绪论 j g oy = ( 扛，j ，) ，咒屯+ x l y 2 ) 在这个定义下：x 2 = x 。x ，x + y 表示各个分量的和，令p = ( 1 ，0 ，0 ) r n 则有下 面的基本性质： 性质1 1 1 ) p o x = x ，v x 尺“ 2 ) x o y = y o x ，坛，y r “ 3 ) x 。( x 2 。y ) = x 2 。( x 。y ) ，v x ，y r “ 4 ) ( x + j ，) o z = x o z + yo z ，v x ，y r ” 注意到o 。y ) 。z x 。 。z ) ，v x ，y ，z r ”，例如： 刀= 3 ，x = ( 1 ，- 1 ，1 ) ，y = z = ( 1 ，0 ，1 ) 有( xoy ) oz = ( 4 ，- 1 ，4 ) x 。( y 。z ) = ( 4 ，- 2 ，4 ) 。 性质1 2 1 ) 对x = ( x 。，x ：) r xr 川，有d e t ( x ) = x ? - i i x ：1 1 2 ，护( 曲= 2 x l ，尤其是 d e t ( x 。y ) d e t ( x ) d e t ( y ) ，只有当x 2 = y 2 时等号成立。 2 ) 若d e t ( x ) 0 ，则x = ( 而，x 2 ) r xr 川称为可逆的。如果x 是可逆的，则存在 唯一的y = j ，y 2 ) r r 柚满足石。y = p ，我们称y 为石的逆，记为x 。通过直 接计算有： 2 南吣硇2 等 所以有x i n t ( k ”) 亡，x - 1 i n t ( k ”) 争) 对任意x = ( x l ，x 2 ) r r 川，定义一个对称矩阵 小旺辩 所以有石。y = l ，y ，石i n t ( k ”) 今三。 - 0 。 下面我们给出k ”上的向量的谱分解：令z = 。，石：) r x r 川，- t p a 表示为： x = “1 + 2 2 u 2 ，其中 ，2 2 ，z 4 1s “2 分别表示x 的特征值和相应的特征向量， 小肛，静。， l 扣( _ 1 ) f w ) ，石：= o 其中i = 1 ，2 w r n - i 满足0 卅= l 。 以= x ，+ ( 1 ) i i x ：l l ， 4 二阶锥互补问题的光滑算法研究 ，屯，掰1 ，u 2 的性质如下 性质1 3 1 ) “1 “2 = 0 ， = 0 2 0 = 1 压。 2 ) “1 “= u 。，i = 1 , 2 。 3 ) z k ” 五0 ，x i n t ( k ”) c ，丑 o ，i = 1 , 2 。 4 ) d e t ( x ) = t ，t r ( x ) = a + 九，2 恻1 2 = g + 麓。 命题1 1 对任意x ，y r ”有 x k “s k nx f s = 0 亡x k n ，s k “，x os = 0 o 命题1 2 对仟意函数雪：r 。r ，定义二阶锥上的函数g ：r ”j r ”为： g ( x ) = 季( 五) “1 + 雪( 五) z ，2 ， v x = ( x 1x 2 ) r xr 川，这里五，免2 ，“1 ，u 2 为x 的谱值和谱向量。 推论1 3v x = ( _ ，恐) r r 一，这里a ，如，“1 ，甜2 为x 的谱值和谱向量，则下面 的结果成立： 1 ) x 2 ：五2 u 1 + 乃2 “2 。 2 ) x 1 心= 见1 圯矿+ 分舱z ，2 。 3 ) l x l = ( x 2 ) 1 坨- n u l + i 五j 甜2 。 4 ) x 】+ = 】+ u 1 + 五】+ “2 ，这里 口】+ - - - m ：a x 0 ，口) ，v a r 。 1 3 本文所需的预备性知识及主要工作 一、预备性知识 在本文中我们丰要考虑这样的二阶锥互补问题： 寻找x r 一，使得 j = f ( x ) ，xo j = 0 ，且x k ，s k 。 ( 1 1 ) 式中f ：r ”j r ”是连续可微映射。 二阶锥互补问题的等价或者近似转化是该研究领域的基本理论之一，它的意 义在于借助这些再牛形式( 例如方程或者优化问题等) ，既可对解的存在性进行深 入研究，又可以在设计有效算法方面发挥显著的作用。如果存在一个向量值函数 西：r “r “jr ”，使得 xk，jk，xrs=0c 西( x ，s ) = 0 称它为互补函数。对此。主要有以下结果： 第章绪论 1 ) ( 惩罚) n r 一函数：( x ，s ) = x - p k ( x - - s ) ( = x p , ( x - s ) + 只( x ) 。最( s ) ) 由推论1 3 中的4 ) 知( 惩罚) n r 一函数也可以写成下面的式子： ( x ，j ) = x - i x - s + ( = x - x s 】+ + x 】+ o s 】+ ) 2 ) ( 惩罚) f b 一互补函数：( x ，s ) = x + s x 2 + s 2 ( = x + s 一x 2 + s 2 + 【x 】+ 。p + ) 3 ) c 卅光滑近似互补函数：。( 工，s ) = x - , u g ( o - s ) u ) ，其中z o , g c m 。 4 ) f b 一光滑近似互补函数：( x ，j ) = x + s 一x 2 + s 2 + 2 , u 2 e 。 在本文中，我们考虑光滑逼近来求解二阶锥瓦补问题。我们选择连续可微函 数丸：r ”r ”- - - r 4 ( 参数 0 ) ，使得死( x ，j ) = l i m 丸( x ，s ) ，并且满足 1 1 u x k ，s k ，x 7j = 0 死( x ，s ) = 0 。 我们注意到死是非光滑的，因此不能采用光滑算法来求解。唬的选择最常用 的是投影互补函数和f b 一互补函数，在本文中，我们唬的选择为：自然剩余函数 ：r ”r ”斗r “ 破怅( x ，s ) = x 一只( x j ) 因此有，全n r 一函数日脓：r ”r ”寸r ”r ”为 啪- ( 嬲) 我们可以进一步定义v n r ：r ”r ”一r 为： 、( 石，s ) ：丢。日脉( x ，s ) 1 1 2 = 丢o ( x ，j ) 1 1 2 + 丢i i ( x ) 一s l l 2 为s o c c p 的互补函数。因此s o c c p 等价于方程h 脚( s ) = 0 。并且易知对于任 意的( x ，j ) r “xr ”，( 工，s ) o 且( x ，j ) = 0 当且仅当( 五j ) 是s o c c p 的解。 由于函数唬是非光滑的，我们运用函数九对其光滑化，这样s o c c p 问题可 以转化成求解下面光滑方程 九o ，s ) = 0 。 九的选择最常用的一个是自然剩余函数的c m 一光滑近似互补函数，另一个是 f b 函数的f b 一光滑近似互补函数。在本文中我们选择自然剩余函数的c m 一光滑 近似互补函数来求解s o c c p 。 二、本文的主要工作 第二章给出二阶锥瓦补问题的一个基于非单调线搜索的光滑牛顿法，在r 性 质的假设下给出算法的全局收敛性和局部超线性收敛分析，最后给出算法的数值 实验，实验证明本文的算法要比 2 6 的效果要好。 _ 阶锥互补问题的光滑算法研究 第三章将线性规划的预估校正光滑化方法h 妇扩展n - 阶锥互补问题中来，给 出一个求解二阶锥瓦补问题的非内点预估校正路径跟踪法，我们给出了算法的全 局收敛性，及在严格瓦补的假设下给出算法的局部二次收敛性，最后给出数值实 验，实验证明本文的算法要比 3 1 的效果要好。 第四章我们给出一个求解二阶锥互补问题的预估校正光滑牛顿法，这个算法 由线性规划的预估校正光滑化方法m 1 扩展n - 阶锥互补问题中的，并且比算法 3 1 要简单，我们给出了算法的全局收敛性及局部超线性收敛性证明。最后给出数值 实验来说明算法的有效性。 第二章基于非单调线搜索的光滑牛顿法 7 第二章基于非单调线搜索的光滑牛顿法 在本章中我们给l i l - 阶锥互补问题的一个基于非单调线搜索的光滑牛顿法， 在昂性质的假设下给出算法的全局收敛性和局部超线性收敛证明，最后给出算法 的数值实验。数据结果表明本章的算法要比 2 6 中的光滑算法效果要好。 2 1 引言 为了简单起见，我们研究k = k ”的情形：即在本章中我们研究这样的二阶锥 互补问题：找x r ”，使得 s = 厂( x ) ，x os = 0 ，且z k “，s k ”。 ( 2 1 ) 最近光滑化方法成为求解优化问题的一种新方法二阶锥互补问题的光滑方 法的理论研究乜，纷2 7 骨3 玎取得了一些成果，但还有许多问题需要研究。本章出于对 称锥互补问题的基于非单调线搜索的光滑算法6 3 的动机，在光滑算法啪1 的基础上 提出了二阶锥互补问题的基于非单调线搜索的光滑算法本算法对初始点的选取 没有任何限制，我们先基于c h e na n dm a n g a s a r i a n 族光滑函数构造了一个方程组， 在异性质的假设下给出算法的全局收敛性和局部超线性收敛性分析，并且给出数 值实验，数据结果说明本章的算法比光滑算法乜6 1 的效果好。 2 2 基于非单调线搜索的光滑牛顿法 二阶锥互补问题的等价或者近似转化是该研究领域的基本理论之一，它的意 义在于借助这些再生形式( 例如方程或者优化问题等) ，既可对解的存在性进行深 入研究，又可以在设计有效算法方面发挥显著的作用。如果存在一个向量值函数 ：r ”r “专r ”，使得 x k ，s k ，x7 j = 0 ，( 石，s ) = 0 称它为互补函数。有关互补函数的研究已有好多文献口侧，其中m f u k u s h i m a ，z q l u o ，a n det s e n gs 和h a y a s h i ，n y a m a s h i t a , a n dm f u k u s h i m a 研究了n r 一函数 二阶锥互补闯题的光滑算法研究 ( x ，s ) = x - l 。( x - s ) 的相关性质，并且给出了相关的算法。显然，下列有下面 x k ”，s k ”，z7 j = 0 亡，x k ”，s k ”，x 。j = 0 x 一 z j 】+ = 0 ( 2 2 ) 耻 舻= 。 汜3 ， 因为( x ，s ) 是不可微的，方程组( 2 3 ) 是非光滑方程组，所以不能用牛顿 型方法求解，但是我们可以对其进行光滑化。因此，可以用c h e na n dm a n g a s a r i a n 族光滑函数对( z ，s ) 光滑化瞳1 ，即 其中t 0 ，g ：r ”专r ”并且满足命题1 2 ，即对任意函数雪：r 。r ，二阶锥上 g ( x ) = 雪( ) “1 + 雪( 五) 甜2 口( x ，s ) = x - , u ( 雪( 五) 甜1 + 喜( 如) z ，2 ) ( 2 5 ) 这里五，五，u 1 ，u 2 分别为 一s ) , u 的谱值和谱向量，雪：r 寸r + 是连续可微凸函数， l i m 季( 口) = 0 ，l i m ( 宫( 口) 一口) = 0 ，且0 0 ，并且序列讧) 是单调下降的。 由步2 可知：对所有k ，有 ”= 4 - r 舡t 等+ 学， 第：章基于非誓调线搜索的光滑牛顿法 1 1 ( 1 一，) + p 矿( 1 ) c t 0 而且 x 川2 x + ，以 叫嗲1 - e 一 + 学) + ，( 一e + o p ) c , ) z + ，( 一e + z ) ( 1 + ，| ) 一，e z 5 ) 步3 的定义：令 n ( c o k ) = ，( 国+ t ：r ，c o ) 一f ( c o ) 一c w f ( c a ) a c o 则有： 0 f ( + t r a c o 。) 0 = 0 ( ) + f ( 彩) + a v f ( c o ) 国。0 m ) l l + t - a ( 1 - 1 z ) a l l ， o ，使得p 叫 0 ，f ( x k , s ，) 在( ，s ) 是 强制的，所以有 l i r n ( ，t ，。t ) i _ 。0 j f 7 ( x ，j ，) 0 = a 。， 又由注2 2 的1 ) ，2 ) ，知 l i f ( x k , s k , t l l - p 。 所以，当k 充分大时有： 慨x ，s ，) 忙肛 这与强制性矛盾。所以 ks ) ) 是有界的。所以序列 ) 有界。 定理2 1 假定厂是连续蜀映射，如果所有v a f ( c a + ) 是非奇异的，则由算法产生 的序列 0 3 ) 是有界的且 ( ，s ) ) 的任意聚点是s o c c p 的解。 证明：由引理2 2 有：由算法产生的序列 是有界的，下面我们证明 ( x k ，s ) ) 的任意聚点是s o c c p 的解。 由注2 2 的1 ) ，5 ) 有： 0 o ( c o k + 1 ) c k + i c ：局“局“o o 我们推导出一个矛盾。下面两部分来推导。 首先，假定气c 0 ，这里c 是常数，由注2 2 的1 ) 有，对任意尼孵( 相 应的下标为吼) 邓q 一孚1q 卟等1 g c 七+ - = c f i + c j 一q 一产q = g 一产g 由于 g ) 是有界的，所以有 薹等1 即 由q 的定义有： q + 旬+ 善县仇一， o 矛盾。 其次假定存在一个吼的一个子集( 我们仍然用贸来表示) 使得l 。i 。m 吼r 。- = 0 ，则 步长声= ，艿对任意k 9 l 不满足线搜索准则，即 o ( o j + 矿缈) ( 1 一仃( 1 1 f 1 ) f 。) c 七 ( 2 1 4 ) 对任意足够大的k 锨都成立，则我们可得下面的结果： ( a ) 。 0 ( b ) a m 女e 孵是收敛的。 事实上，由于+ 0 ，由步2 知，如果v f ( c o ) q 存在任意k 吼连续。若不 存在，v f ( r o ) 对任意k 9 t 也是连续的，因此有l i m a m = a m 。 膏e w ( c ) c = o ( w ) 。 - 4 三坠丝兰i ! 塑璺塑堂塑簦鎏堕窒 。_ - _ 一 c 口( ) ， 又由( 2 9 ) 有 c 秒( 缈+ ) 由( 2 1 3 ) 有 p ( 国2 + 声“缈2 ) ( 1 一仃( 1 1 夕) 鲈) c t 。 由于耿) g ，( 2 1 4 ) 变为 ( o ( c o + 声。国。) 一秒( 国) ) 声 - c r ( 1 1 p ) c k ， 由( a ) ，( b ) 并且令k - - - o o ，我们有 丽1 ( + ) ，卯( 咖国+ ) 押( 1 一护 另外由( 2 8 ) 及( b ) ( c ) 有： 丽i ( ，( 缈) ，即( 国+ 埘) 卅( ) + 南( 鼬) ，p ) 列( 硼) + 器 卅( v 吾 ( _ t + 分c 所以有 小砉c 卜分 这与盯( 0 ，1 ) 和p 1 矛盾。 综合上述，原定理得证。 定理2 2 ( 局部超线性收敛) 假定厂是连续昂映射，如果所有矿护( 功+ ) 是非奇 异的，则助 超线性收敛到。即 lc o 一j 0 = 。( 桫一j i i ) ， 川= d ( ) 。 证明：类似于f 3 7 的定理8 。 第二章基于非单调线搜索的光滑牛顿法 2 4 数值实验 我们解下面线性二阶锥互补问题： 找x r ”，使得j = m x + q ，x os = 0 ，r x k ，s k 。 其中m 的秩， x - - 【x j 】+ = 0 因此，二阶锥瓦补问题( 3 1 ) 中的瓦补性条件x o s = 0 可以写成： 胀( 1 x ，s ) = x 一只( x s ) = 0 ， 于是求解二阶锥互补问题( 3 1 ) 等价于求解下述方程组 h 施加( 嬲) ：0 组2 ) 因为( x