（运筹学与控制论专业论文）求解一类绝对值方程组的非内部连续化算法.pdf

中文摘要 绝对值方程组的求解问题是一类n p 难的问题，现有的方法是将绝对值方程 组转化为双线性规划问题，凹极小问题，然后再通过解决这些问题，进而求解绝 对值方程组，此外还有一些学者利用广义牛顿型算法求解绝对值方程组非内部 连续化算法是求解多种优化问题的一种有效方法，该方法首先用光滑函数把线性 互补问题转化为一系列的光滑方程，然后通过牛顿型算法来求解光滑方程组，并 逐步调整迭代点和光滑参数，从而得到光滑方程组的解，进而得到与其对应的互 补问题的解 本论文是将一类绝对值方程组转化为广义的线性互补问题后，构造光滑函 数，得到光滑函数方程，然后利用非内部连续化算法求解光滑函数方程，进而将 求解绝对值方程组的解转化为求解光滑函数方程的根，接着介绍了该算法的全局 线性收敛和局部二次收敛，最后用m a t l a b 程序执行此算法，检验此算法的性 能 关键词：绝对值方程组；非内部连续化算法；全局线性收敛；局部二次收敛 a b s t r a c t b e f o r et h i sd i s s e r t a t i o n ，t h en p h a r da b s o l u t ev a l u ee q u a t i o n sa v e sw e r e s o l v e db yu t i l i z i n ga ne q u i v a l e n tr e l a t i o n s h i pt ob i l i n c a rp r o g r a m m i n go rc o n c a v e m i n i m i z a t i o np r o b l e m s i na d d i t i o n ，ag e n e r a l i z e dn e w t o nm e t h o dw a sp r o p o s e d f o ra b s o l u t ev a l u ee q u a t i o n s an o n - i n t e r i o rc o n t i n u a t i o na l g o r i t h mi sa l le f f e c t i v e m e t h o df o ro p t i m i z a t i o np r o b l e m s w h e ns o l v i n gt h el i n e a rc o m p l e m e n t a r yp r o b - l e m s ，i tt r a n s f o r m st h el i n e a rc o m p l e m e n t a r yp r o b l e m st oas e r i e so fs m o o t h i n g e q u a t i o n sa tf i r s t ；t h e ns o l v et i l es m o o t h i n ge q u a t i o n sb yn e w t o nm e t h o d s ；t h e s o l u t i o n st ot h es m o o t h i n ge q u a t i o n sw o u l da p p r o x i m a t et h es o l u t i o n st oc o r r e - s p o n d i n gl i n e a rc o m p l e m e n t a r yp r o b l e m sb ya d j u s t i n gt h ei t e r a t i v ep o i n t sa n dt h e s m o o t h i n gp a r a m e t e r s t h em e t h o di nt h i sd i s s e r t a t i o nf o rs o l v i n ga v e si st ot r a n s f o r mt h ea v e st o g e n e r a l i z e dl i n e a rc o m p l e m e n t a r yp r o b l e m s a n dc o n s t r u c ts m o o t h i n gf u n c t i o n s t h a ta p p r o x i m a t et h es o l u t i o n st ot h eg e n e r a l i z e dl i n e a rc o m p l e m e n t a r yp r o b l e m s t h es m o o t h i n gf u n c t i o n sa r es o l v e db yt h en o n i n t e r i o rc o n t i n u a t i o na l g o r i t h m t h e nt h eg l o b a l l ya n dl o c a l l yq u a d r a t i c m l yc o n v e r g e n c eo ft h ea l g o r i t h mi si n t r o - d u c e d f i n a l l y , t h ea l g o r i t h mi si m p l e m e n t e di nm a t l a b k e yw o r d s ：a b s o l u t ev a l u ee q u a t i o n s ；n 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 d ；g l o b a l l i n e a rc 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 e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得天津大学或其他教育机构的学位或证 书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：抖意恂 签字日期：卵7 年f 月3 日 学位论文版权使用授权书 本学位论文作者完全了解天津大学有关保留、使用学位论文的规定。 特授权天津大学可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 封束垧 导师签名：c 骞蠢楚型滔卜 签字日期：呷年月弓e l 签字日期： 唧6 月弓日 第一章绪言 第一章绪言 在数学领域中，对绝对值方程的探索有着很大的研究空间，因为现实 生活中将实际问题抽象建立为绝对值方程的模型比比皆是优化领域方面 的一些专家也将部分精力放在研究这个问题上，用优化的思想转化问题， 求解方程取得了不错的成绩早在很多文章中就对绝对值方程组的求解问 题有所探索，比如【6 】，【8 中直接考虑求解一般的绝对值方程组： a x + b i z i = b ， a r ”“，b r “，b r ”， 而且发现众多问题可以转化为上述绝对值方程组的求解问题，尽管求解绝 对值方程组是一类n p 难的问题，但是 6 】，【8 】的作者利用优化的思想给出巧 妙的性质和适当的条件使得问题得以简化 7 中是先将绝对值方程组转 化为凹极小化问题，再利用连续线性算法( s l a ) 来求解凹极小化问题，最后 用m a t l a b 程序来执行此算法，检验其性能( 文章显示用此算法求解1 0 0 个随机产生的1 0 0 0 维的a v e s 时所用时间不多于1 0 s ，精确度达到了1 0 - 6 ) ， 进而得到绝对值方程组的解另外 8 中是利用广义牛顿型算法来求解这类 绝对值方程组问题的，其基本思想是用绝对值方程组来构造求解它的广义 牛顿型迭代公式，得到近似迭代解再根据迭代点的有界性，线性收敛性找 到此迭代点列的聚点，证明聚点就是绝对值方程组的收敛解这种方法求 解1 0 0 个随机产生的1 0 0 0 维的a v e s 时所用时间也不多于1 0 s ，精确度也达 到了1 0 一。而与其对应的线性互补问题在达到相同精确度的前提下用时不 超过2 9 s 然而还没有学者做过将绝对值方程组问题转化为广义的线性互补 问题后，用非内部连续化算法求解( l c p ) 的文章，于是本文基于这种思想 对绝对值方程组做了如下的分析 本文是求解如下一类绝对值方程组： a x i z i = b ，a r 竹“，b r “， 因为形如a x + b i x i = b 绝对值方程组在一定条件下可以通过矩阵之间的运 算转化为a x i x i = b 本文第一部分给出这类绝对值方程组a v e s 的一些基 础知识，并将其转化为( l c p ) 问题，第二部分给出广义的( l c p ) ，且将( l c p ) 的求解问题通过光滑函数的构造转化为光滑函数方程根的求解问题，第三 第一章绪言 部分给出求解光滑函数方程的非内部连续化算法，找到运用此算法的线性 互补问题中矩阵所需的条件，这也是本文的难点之处，最后找到了相对于 半正定矩阵来说还要弱的一个充要条件第四部分我们用m a t l a b 程序来 执行此算法，并与前人的算法做了比较与改进，得到了不错的结果最后给 出展望，希望在条件减弱的情况下得到更新，更好的结论 2 第二章基础知识 第二章基础知识 本章将给出该硕士论文要求解的绝对值方程组的基本类型，线性互补 问题的基本知识，这些内容对引入非内部连续化算法是必要的 2 1绝对值方程问题 本文要解决这样一类绝对值方程组a v e s ： a x - ixi = b ，a r 似“，b r “， 这里的表示对x 的每一个分量取绝对值下面给出这样一个事实，a v e s 等价于一个双线性规划( 这个优化问题的目标函数是两个仿射函数的乘积) 和广义的牛顿线性互补问题为了给读者清楚地介绍这部分内容，先给出 下面两个命题的简单证明，读者也可参阅 6 命题2 1( a v e 号双线性规划骨广义的线性互补问题) a v e 等价 于下面的双线性规划 02 恕 ( ( a + 啦一矿( ( a 一啦一州a + ，) x - - b 0 ，( a 一啦一6 ) o ) ( 2 1 ) 也等价于下面的线性互不问题 o ( a + i ) x b 上( a 一，) z b 0 ，( 2 2 ) 证明：显然( 2 1 ) 和( 2 2 ) 是等价的，下面我们将通过( 2 1 ) 与a v e 等价给出 命题的证明过程，注意这个等价关系 x l a x b 营- a x + b x a x b ，( 2 3 ) 等价式的右边就是( 2 1 ) 约束的变形式子，因此 x i = a x b 管( ( a + ，) z 一6 ) 7 ( ( a i ) x b ) = 0 ，i x i a x b ， 所以( 2 1 ) 成立当且仅当a v e 有解 3 第二章基础知识 命题2 2( a v e 兮l c p ) 如果1 不是a 的奇异值，那么a v e 能够等 价转化为下面的l c p 0 z 上( a + j ) ( a 一，) - 1 z + q 0 ，( 2 4 ) q2 ( a + j ) ( a j ) 一1 6 ， f 2 5 ) z = f a i ) z b 。 证明：首先从等价于a v e 的广义l c p ( 2 2 ) 开始，为了得到( 2 4 ) 式子，先用 ( 2 5 ) 式的z = ( a i ) x b 来代替l c p ( 2 2 ) 的右边不等式，得到( 2 4 ) 的右 边不等式z 0 ，将( 2 5 ) 变形得到x = ( a 一，) q ( z + b ) 代入( 2 1 ) 的右半边 不等式，得到 0 ( a + j ) ( a j ) 一1 ( z + 6 ) 一6 ( 2 6 ) = ( a + ，) ( a j ) 一1 z + ( ( a + ，) ( a 一，) 一1 一z ) b 这就给出了如( 2 5 ) 所定义的( 2 4 ) 的右半边不等式，( 2 5 ) 的正定性有( 2 1 ) 可得这就给出了我们要求解的绝对值方程组的一些基本知识及与其等价 的线性互补问题，下面简单介绍线性互补问题 2 2 线性互补问题 线性互补问题l c p ( m ，q ) ，矩阵m 舻黼，q 形，向量( x ，8 ) r 2 竹满 足 ( x ，8 ) 0 ，8 = m x + gx t 8 = 0 用厂，5 来分别定义l c p ( m ，q ) 的可行域和解集合，即 厂：= ( z ，s ) r 2 “：s = m x + g ) ， 这里：= 是定义的意思( 下面用法相同) ，本文假设m 是一个r 矩阵 众所周知，l c p ( m ，q ) 可以简化为一系列的非光滑方程通过引进一个 参数，非光滑方程能够简化为一系列的含参数的光滑方程，因此我们可以在 4 、， 0 i i s r z0 一 、l ， sz ，f 厂 、l ， sz ，r l = s 和 第二章基础知识 每次迭代中使用一系列的牛顿型算法近似求解含参量的光滑方程并使得光 滑参数趋向于0 ，这样原始问题的解就能找到这种算法的起始点和中间 的迭代点不需要保证分量是正的，这是与内点算法相比最大的不同之处， 所以说非内部连续化算法在未来十年有广阔的发展空间而本文中要求解 的l c p ( m ，q ) ( m 是一个p 0 矩阵) 所用到的这种新的非内部连续化算法具有 下面的特点： 这种算法在概念上比现有的非内部连续化算法简单，在每次迭代中 最多需要求解一个线性方程 在适定的条件下，这种算法是全局线性收敛和局部二次收敛的 下面将给出本文在互补问题中所用的一些参量对于任意的a 形，e i g ( a ) 表示a 的所有奇异值的集合，九表示为a t a 的特征值，吼( a ) 表示a 的奇异值，吼( a ) = 九( a 丁a ) z ：- - - 1 ，2 ，凡) ，彤表示为1 2 维实数列向 量空间，r 华，r 华+ 分别表示为舻中的非负向量空间和正向量空间符号t 表示转置，对于任意的两个向量乱r z ，v f ，这里的1 , r 是任意的两个正整 数，用( u ，v ) 表示为( u 丁，v t ) 丁的简化形式，用l l 札| | 表示u 的二范数a r 似”， 用i i a i | 表示矩阵a 的f 范数对于任意的q ，卢 0 ，o z = d ( p ) 表示n 卢是 一致有界的当p 一0 时，迭代次数的集合用瓦来表示，瓦：= o ，1 ，2 ) 对 于任意的x ，8 r ”，本文使用下面的符号，除非另有定义： w ：= ( x ，s ) ，w 2 ：= ( x 七，8 k ) ，v k 瓦，霹：= - - - ( 霹，霹) ，v k 瓦，v i z 为了求解绝对值方程组a v e s ，将( 2 5 ) 中的z ，( a + 州a 一，) ，( ( a + 州a j ) 一z ) b 分别给出如下记法， z = z ；( a + ，) ( a j ) 一1 = m ；( ( a + j ) ( a j ) 一1 一i ) b = 口， 因此8 = m x + q ，这样就得到了与绝对值方程组a v e s 等价的( 2 4 ) 式又与 ( x ，8 ) 0 ，8 = m x + g ，x 1s = 0 ，( 2 7 ) 等价这样就将a v e s 方程转化为了线性互补问题( 2 7 ) 因为( 2 7 ) 中要求 m 是一个p o 矩阵，为了使m = ( a + 州a j ) - 1 是一个蜀矩阵，本文需要 找到a 满足什么样的条件才能保证m 是一个局矩阵后面要给出具体证 明，这里不详细说明了 5 第三章非内部连续化算法 第三章非内部连续化算法 首先给出几个光滑函数，再通过变形将线性互补( 2 7 ) 的求解问题转化 为光滑函数方程的求解问题，下面详细描述此算法 3 1光滑函数的构造 令西：r 3 一r 记为c h e n h a r e r k a n z o w - s m a l e 光滑函数 西( p ，o 6 ) = o + b 一、气i 二百乒可；v ( p ，o ，6 ) r 3 ( 3 1 ) 对于任意的p r ，令圣“：r 2 几一舻如下定义 西p c 叫，= ( 三：二 三：) ；讹：= c z ，s ，r c 3 2 ， 对于任意的i i ，知厩：= ( x i ，8 i ) 对于任意p r ，通过下式来定义函数 f u ：r 2 “一r 2 “ 只c 叫，= ( s - - 垂m 肛。叫x ，- g ) ；v 叫：= c z ，s ，r 2 n c 3 3 ， 刃b 么 兄( 伽) = 0 ，肛= 0 骨w s 容易看出，对于任意的肛 0 ，函数兄是连续可微的， r ( ) 在w r 2 “处的雅可比矩阵，那么 触= ( 晚以品) i 是n 礼的单位矩阵并且 以西“( 叫) ：= d i a g 1 一 统垂“( 叫) ：= d i a g 1 + z t 一8 i 识i i 铲干孕。 z i 一鼠 识i i 铲干孕 6 现用兄( ) 来表示 i ，】， i ，) ( 3 4 ) 第三章非内部连续化算法 d i a g u i ：i ， 表示一个对角矩阵，第i 个对角元素是u t ，对于任意的让r n 故本文要求解l c p ( m ，q ) ，就是近似求解在每一次迭代中所产生的光滑函数 方程兄( 叫) 当光滑参数p 减小到0 时的根下面先从理论上介绍一下这种 算法： ( 1 ) 非光滑化算法是直接求解不可微的互补函数，因为该函数是非光滑的， 雅可比矩阵不存在，这时就不能直接使用经典的牛顿法了，需要用非光 滑的理论和算法但是非光滑的理论比较复杂，不太容易掌握，而且非 光滑法存在一个弱点：一般情况下，次梯度难于计算 ( 2 ) 光滑化方法的主要思想是：首先利用带参数( 称为光滑参数p 0 ) 的光 滑函数近似这个非光滑方程组，之后可用牛顿型方法求解，并使得光滑 参数趋于零，这种方法被称作光滑化法在一定的假设下，并通过逐步 调整光滑参数趋于零来得到光滑函数的解收敛于互补问题的解类似于 内点法，随着光滑参数逐渐趋向于零，光滑函数的解构成了一条趋于最 优解集的光滑路径与求解互补问题的其它方法相比，这种方法不仅思 想简单，而且易于程序实现，只需嵌入一个求解线性方程组的子程序即 可和内点算法比较起来，光滑化算法的优点是：初始点和中间迭代点 均不必是可行内点 依据这种想法，使用新的非内部连续化算法来解l c p ( m ，q ) 下面给出具体 的算法描述 3 2 算法描述 算法3 1非内部连续化算法 第零步：选取任意的6 盯，7 ( 0 ，1 ) ，x o r “，p o ( 0 ，+ 。) ，令8 0 ：= m x + 口，w o = ( x o ，8 0 ) 选取p 使得卢2 何和| | ( 叫o ) j i 卢弘o 令k = o 第一步：若v o ( w 知) = 0 ，停止，w 为光滑方程兄( 伽) = 0 的根，否则转 到第二步 第二步2 ：如果兄。( w 缸) = 0 ，令w 1 ：= w 2 ；以：= 1 ，转到第四步否则令 7 第三章非内部连续化算法 z x w 七：- - - - ( a x ，a y 血) r 2 n ，解方程： 咒。( 叫南) a w 2 = 一兄。( 叫2 ) ， 第三步：令以是1 ，6 铲的最大值，满足 l | 冗。( 伽+ 民叫七) i | ( 1 一a 6 k ) 3 p k ， 令w k + 1 ：= 叫k + 以a w 。，如果民( 叫“+ 1 ) = 0 停止，否则转到第四步 第四步：令 1 玩= ( 卜南a o k ) v k ， 仇是1 ，y ，y 2 的最大值，满足 i i f 。觎( 伽1 ) | i 卢讯m ， 令胍+ l ：= 犰反k ：一- - - k + l ，转到第二步 ( 3 5 ) ( 3 6 ) ( 3 7 ) ( 3 8 ) 注释3 1算法特点及比较 非内部连续化算法在其它文章中也出现过，只是本文用到的非内部 连续化算法的框架简单一些 算法3 1 很容易启动，只要任意选取( p o ，x o ，8 0 ) r + + xr 2 ”做为算 法的起始点即可，然后令：= m a x 2 v - 元，i i ( z o ，8 0 ) l l m o 构造两个集合 瓦l ：= 后瓦：兄。( 叫七) = o )瓦2 ：= k j i c ：目。( 叫七) o ， ( 3 9 ) 则j | l c lu 瓦2 = 尼瓦ln 瓦2 = d 因此对于任意的迭代指标k 瓦，得到k j j | c l 或k 瓦2 容易看到对于任意的南j c l ，算法( 3 1 ) 在第k 步不需要求解n e w t o n 方程( 3 5 ) ，也不需要执行线性搜索( 3 6 ) ，此次迭代只需求解一个线性方程 引理3 1假如m ( m = ( a + 州a j ) 。) 是一个r 矩阵，那么 ( i ) 算法3 1 是有定义的 ( i i ) 算法( 3 1 ) 产生的序列 胀是单调减小的，并且对于所有的k 瓦，肌0 ( 饿) i | 兄。( w 七) 峪p 舰，对于所有的k 瓦 ( i v ) w 2 厂，对于所有的k 瓦2 ，赶2 是通过( 3 9 ) 定义的 证明：引理的结论很容易证明，这里省去 r 第三章非内部连续化算法 下面给出矩阵m 是一个p 0 阵时a 满足的条件 些基本知识 定义3 1矩阵m r 似”称为p 阵( 局阵) ， 毋，z 0 ，存在一个分量x k 0 ，使得 x k ( m x ) k 0 ( 0 ) ， 首先给出p o 矩阵的一 如果对于任意的x 所有的p 矩阵组成的矩阵被称为p 类，记为p 矩阵，所有的r 矩阵组成的 矩阵类称为p 0 类，记为岛显然正定矩阵必是p 矩阵，半正定矩阵必是蜀 矩阵，这是正定矩阵和半正定矩阵的推广 引理3 2令m r 似n 为任意的矩阵，d 舻黼是一对角矩阵，则 行列式 d e t ( m + d ) = d e td q qd e t m 。a ， ( 3 1 0 ) q 其中o t l ，2 ，札 是一子集，d 。是矩阵d 中所有元素屯组成的子 矩阵，i q ，j q ，阮n 是矩阵m 中所有元素m i j 组成的子矩阵， i g a j e o z ：口表示对所有可能的q 求和本文约定：当q 或石为空集0 时， d e td 口。= d e tm 品= 1 定理3 1令m r n 跏为任意的矩阵，则下面的情况是等价的： ( 1 ) m 是r 矩阵 ( 2 ) m 的所有主子式均为非负数 ( 3 ) 对于任意的正数，m + e i 是一个p 矩阵，其中i 是1 1 阶单位阵 证明过程参看 1 2 中引理2 1 7 和定理2 1 8 由m = ( a + ，) ( a 一，) 一1 = ( 2 1 + a 一，) ( a 一，) 一1 = 2 ( a j ) 一1 + ，要证 m = ( a + 州a 一，) _ 1 为r 矩阵，只需证明2 ( a j ) _ 1 + j 为p 0 矩阵，不妨 令2 ( a 一，) _ = b ，下面给出b 满足什么条件，b + i 是局矩阵时 定理3 2b + i 是p o 矩阵仁专d e t 磷石0 ，k 1 ，2 ，佗】1 a 萝( 1 ) 其中m = i 知+ b “表示与m 的任意的k 阶主子式对应的子矩阵，七，b 七 的取法和m 的取法相同，分别表示i ，b 的k 阶主子阵，o t k 1 ，2 ，佗 表示m 七中元素m 翕的指标集 a q 如垦 1 ，2 ，n ) 的子集 砧。表示 9 第三章非内部连续化算法 矩阵，2 中所有元素i 嚣组成的子矩阵，i q ，j o l 婊表示矩阵b 中所 有元素屹组成的子矩阵， i - f f ，j h ；huq = o t k 由此可知i 。k 口的行列 式要么为1 ，要么为0 令莎( a 七) 表示o t k 的所有子集构成的集合，把使得 贮。的行列式为1 的所有口莎( q j c ) 构成的集合记为莎( 1 ) ，为0 的记为 莎( o ) ，莎( 1 ) u 莎( 0 ) = 步( q k ) 证明：由定理3 1 可知：m = i + b 是岛矩阵 m 的所有主子式0 ， 对于m 任意的k 阶主子式m 2 ，k 1 ，2 ，礼】- 有 d e t ( m 2 ) = d e t ( i 七+ b 知) = d e t i f f q 妣b 是 a e 0 2 ( a k ) = d e t 礁 q 。尹( 1 ) 所以定理3 2 成立 由上述定理得到： 如果b 是一个晶矩阵，则i + b 是一个p 矩阵，进而i + b 是一个岛 矩阵 如果b 的特征值一1 ，那么i + b 是半正定矩阵，进而是r 矩阵 如果b 是一个半正定矩阵，i + b 一定是正定矩阵，进而是晶矩阵 3 3 算法收敛性的探索 首先通过下式给出光滑路径领域的定义 a r ( z ，肛) ：= w r 2 “：i i f ( 叫) i l p 肛) ， 这里的肛 0 ，p 0 是上面算法给出的领域的宽度，下面由p ( 0 p o 】通过 下面的式子给出此领域片来 ( 口( 0 ，p o ) ) = ( 伽( p ，肛) ：p ( 0 ，p o ) ( 3 1 1 ) 这篇文章中还会用到如下假设： l o 第三章非内部连续化算法 假设3 1通过( 3 1 1 ) 定义的领域片是有界的 这个假设是非内部连续化算法中所用到的假设中一个比较基本的充分条 件，这个假设能够确保算法的全局收敛性 通过引理3 1 的第( i i i ) 个结论，可知假设3 1 能够确保算法3 1 产生的 迭代序列是有界的，这一点本文在后面的分析中要经常使用 引理3 3假如m 是一个p 0 矩阵，假设3 1 也能够满足，那么算法3 1 产生的有限迭代序列 ( 肌，w 2 ) 南艽有极限1 i m 纵= 0 尼- ( ) o 证明：引理的结果很容易被证明，省去证明过程 定理3 3 假如m 是一个r 矩阵，序列 ( 肌，w 。) 】i 七( 是有算法3 1 产 生的，如果假设3 1 满足了，那么迭代序列 ( 肌，w 七) 】咒是有界的，并且迭 代序列 ( 肌，w 七) 】- 的每一聚点( 纵，w ) 都满足以= 0 和w + 5 证明：由引理3 3 得到纵= 0 ，由一个简单的连续性讨论得知w + 是l c p ( m ，q ) 的一个解 3 4 算法的全局收敛性和局部二次收敛性 这部分首先给出下面的重要假设，然后研究这个假设和以前一些假设 的关系通过引用此假设和已知假设，下面讨论算法3 1 的全局线性和局部 二次收敛 3 4 1 重要假设 在后面的分析当中要经常使用到这个假设 假设3 2 令 纵) 七k 和 a w 】七。是有算法3 1 产生的，这里的瓦2 是 通过( 3 9 ) 定义的，那么一定存在一个标量c 0 满足i l a w k l | c p ，对于所 有的k j i c 2 ( 类似假设在其它文章中也出现过) 在这一部分要分析假设3 2 与两个已知假设之间的关系，第一个假设是 有下面的假设3 3 给出的，这个假设在非内部连续化算法中证明算法的全局 线性收敛时被广泛的使用 第三章非内部连续化算法 证明：此引理的结论类似与h u a n ge ta 1 ( 2 0 0 1 ) 中的引理7 ，这里省去证 明过程 命题3 1假如m 是一个半正定矩阵，假设3 4 是满足的，那么假设3 4 能够推出假设3 2 证明：不妨令假设3 4 成立，那么通过引理3 2 可知存在一个正整数 k o 厄2 和一个标量c l 0 使得 j l a w 七| | 臼肌，( 3 1 3 ) 对于所有k o 瓦2 和k k o 都成立因为对于任意的肌 o ，咒。忡七) 是一个 非奇的函数，那么 m a x l f ：。w 2 ) 。1 i i ：k 1 ，2 ，k o 一1 】n 瓦2 ) ， 是一个正的有限数通过和引理3 3 相似的证明，可知一定存在一个标量 岛 0 使得 i la w 2i i c 1 z k ，。( 3 1 4 ) 对于所有的k 1 ，2 ，尼。一1 ) n 瓦2 都成立 结合3 1 3 和3 1 4 ，假设3 2 成立 若m 是一个半正定矩阵，假设3 2 满足，那么根据引理3 2 和命题3 1 可知只要假设3 3 和假设3 4 中的任意一个成立，假设3 2 就是满足的因此 假设3 2 比起假设3 3 和假设3 4 中的任何一个都是严格弱的 3 4 2 算法3 1 的全局线性收敛性 对于任意的p r 和c ：= ( a ，b ) 酞2 ，令v 。西( p c ) ：= v ( a ，6 ) 咖( p ，a b ) 这里 定义的的梯度是和变量a , b 有关的令 a w 七 七咒。是由算法3 1 产生的， 瓦2 是通过( 3 9 ) 定义注意 a w ? ：= ( ( 扩) ，( a s 2 ) i ) r ，v i 2 - ，v k 瓦2 引理3 5 假设是通过( 3 1 ) 定义的令 ( 纵，w 如) 瓦和 a w 七) 七( ：是 有算法3 1 产生的，瓦2 是通过( 3 9 ) 定义的那么v i z ，v k 瓦2 ，o l 0 ，1 ) 下式成立 i 咖奄，磷+ a 赢：) 一灿知，磁) 一a v 西? ( - t k , 磁) 丁赢准菱i i 硫斯 1 3 第三章非内部连续化算法 证明：令西( 肌，麟) 是关于变量磷的雅可比矩阵，对于任意的k 瓦。那 么通过直接计算得到 嗡( 胍霹) = 丽寿鲁丽 _ 11 1 舢b 11 ， 因此，| | 每( 纵，磁) 忙1 i u k ，v i z ，vk | i c 2 对于任意的i z 和k 瓦2 ， 证明完毕 = i q 0 1 ( v 钟( 磁+ q 赢? ) 一v 面? ( 磅) ) r 瓦血 = q 2 , 0 1t 0 1 ( 赢：) 丁讲i t ( 霹+ n 打赢：) 葡知出i s q 2 0 1 t 0 1 i i i i 面! 灿，面? + q t r 赢：) i i f d r d t1 1 瓦斯 q 2 0 1t 0 1 1 砒i | 硪1 1 2 1 2 蕊斯 定理3 4 假设m 是一个r 矩阵，令 ( 肌，w 知) ) 七瓦：和 a w k k 咒：是有 算法3 1 产生的，咒2 是通过( 3 9 ) 定义的如果假设3 1 和假设3 2 成立，那 么一定存在一个c ( 0 ，1 ) ，使得对于所有的k 瓦有七+ 1 c p k 证明：令瓦l 和尼2 是通过( 3 9 ) 定义的，对于任意的k j i c ，k | i c l 或 k j i | c 2 第一种情况：假设k 瓦1 在这种情况下，得到民= l ，因此算法的 第四步，由肌+ 1 = 仇砒砒= c # k ，得到 = 1 1 + 以 ( 3 1 5 ) 第二种情况：假设k 瓦2 ，在这种情况下，a w 2 是由( 3 5 ) 产生的，对 于任意的n ( 0 ，1 ，令 r 七( a ) ：= 丘。( 叫缸+ a a w 2 ) 一o 。( 伽膏) 一q 咒。a w 七 1 4 ( 3 1 6 ) 第三章非内部连续化算法 那么 i i f 。( 叫七十m a w 2 ) 一f i i 剑蹦训七) + q ( 一( 叫+ l i t k ( q ) | i ( 3 1 7 1 ( 1 一q ) i i r 。( 叫七) i | + i i r 知( q ) l | 、 ( 1 一q ) p p 知+ l i r 七( q ) 第一个不等式由( 3 1 5 ) 和( 3 1 6 ) 得到，第三个等式由l i f 。( 训南) l | 臼伽得到 因此 1 1 r “( 口) l i = i l 兄。( 加2 + a a w “) 兄。( 伽) 一q 。( 叫) ( 叫“) l = l i 面p 。( 叫七+ a a w 七) 一面p 。( 叫惫) 一。圣：。( 训七) ( 叫南) 型ii赢七ii。2 一 # k ”。一 孚q z m ( 3 1 8 ) 这里的第一个等式根据3 1 6 式，第二个等式根据( 3 3 ) 和引理3 1 的( i i i ) ，第 一个不等式根据引理3 4 ，最后一个不等式根据假设3 2 令 珏错v ( 3 1 9 ) ，6 l ，二 由( 3 1 8 ) 式得到对于所有的q ( 0 ，) ， 胪( q ) i | ( 1 一a ) z a u k ( 3 2 0 ) 因此通过( 3 1 7 ) 和( 3 2 0 ) 得到对于所有的n ( 0 ，a ) ， l i f k ( 伽七十a a w 七) i i 一( 1 一a a ) 3 u k 茎 ( 1 一口) p p 女+ | l r “( q ) f l 一( 1 一盯q ) p p 七 = ( 盯一1 ) q p j c + f i7 七( q ) i i 0 的标量对于所有充分大的k 瓦2 和所有的i 2 ，有 i i ( 垂p 。( 伽+ 1 ) ) i 一( 西 风( 彬。+ 1 ) ) t | | 1 的 稠密矩阵，随机产生的矩阵a 中元素是服从f 1 0 ，1 0 上的均匀分布，随机向 量z 中的分量是服从卜l ，1 上的均匀分布 用广义牛顿算法求解1 0 0 个连续随机产生的a v e s 和与其对应的 l c p s ( n = 1 0 0 0 ) 的数值计算结果： 表4 1 ：广义牛顿算法的计算结果 问题 a v el c p 性质 s v d ( a ) lm 非对称正定矩阵 n1 0 0 01 0 0 0 求解问题的个数 1 0 01 0 0 i | a x - lzi - 6i i 精确度 1 0 61 0 6 牛顿迭代次数 5 0 08 0 6 所用时间( 秒) 9 4 0 3 02 8 6 0 6 所有a 的奇异值的最小值 2 8 8 3 71 0 从上表可知 ( i ) 所有随机产生的1 0 0 个a v e s 和l c p s 在满足j | a x - izi 一圳= 0 的 条件下精确度达到了1 0 - 6 ( i i ) 1 0 0 个a v e 和l c p s 所需的平均牛顿迭代次数分别为5 和8 6 ( i i i ) 解决这1 0 0 个随机产生的a v e s ，l c p s 中的每一个所需的平均时间 分别是9 4 0 s ，2 8 6 1 s ( i v ) 1 0 0 个a v e s 和l c p s 中的矩阵a 的奇异值的最小值分别为2 8 8 3 7 和1 0 用凹极小化算法求解1 0 0 个连续随机产生的a v e s ( 分为十组，每组 十个) 和与其对应的( l p ) 的数值计算结果： 注释：n n z t o t 表示十个问题中每一组方程中无效方程的总个数；n n z x 第四章数值比较 表4 2 ：凹极小化算法的计算结果 例子 n z t o tn n z xk t o c ( s )l p ( s ) 1 1 0118 04 2 3 65 3 1 1 2 0002 61 3 6 15 2 2 1 3 0 l1- 7 43 8 0 45 1 3 1 4 0002 61 3 5 15 2 4 1 5 00o2 61 3 5 45 2 5 1 6 0 002 61 3 6 45 2 6 1 7 0118 04 2 0 75 3 7 1 8 02 1 9 14 3 7 94 8 8 1 9 0002 61 3 5 85 2 9 1 1 0 0002 61 3 5 95 2 表示一个问题中无效方程的总个数；k 表示每一个问题中( l p s ) 的迭代次 数；t o c ( s ) 表示解决十个问题中的每一组所用时间；l p ( s ) 表示由方程的按 列排后得到的每一个( l p ) 所用时间 非内部连续化算法求解a v e 的计算结果： 为了准确得描述非内部连续化算法的计算结果，要求a v e s 中矩阵a 的 奇异值1 且和变量x 都是随机产生的在n 的不同取值下，取1 0 组计算 结果求其平均值现给出下面三种情况下的计算结果： ( i ) 随机产生的矩阵a 中的元素服从 一1 0 ，1 0 上的均匀分布，变量x 中 的分量是服从 - 1 ，1 上均匀分布 ( i i ) 随机产生的矩阵a 中的元素服从 - 5 0 ，5 0 】上的均匀分布，变量x 中 的分量是服从【- l ，l 】上均匀分布 ( i i i ) 随机产生的矩阵a 中的元素服从 - 1 0 0 ，1 0 0 上的均匀分布，变量x 中的分量是服从 - 1 ，1 】上均匀分布 注释；三表中的精确度，迭代次数，时间表示的是在每一个确定的n 值 下，随机求解1 0 次后得到的数值结果的平均值 从下面三表中可以看出用非内部连续化算法求解绝对值方程组时迭代 2 1 第四章数值比较 表4 3 ：非内部连续化算法的计算结果( i ) n 精确度迭代次数 时间( s ) 1 0 04 8 5 x1 0 1 4 1 4 0 0 3 3 2 0 02 1 0 1 0 1 41 60 1 2 6 3 0 01 3 7 x 1 0 1 61 30 3 4 0 4 0 02 3 5 1 0 1 31 50 7 7 5 5 0 05 1 8 x 1 0 1 51 61 6 3 4 6 0 03 7 2 1 0 1 51 82 6 0 7 7 0 01 3 0 x 1 0 1 41 74 0 0 9 8 0 03 3 6 x 1 0 1 61 65 8 1 4 9 0 07 7 2 1 0 1 5 1 7 8 3 5 7 1 0 0 01 7 0 1 0 1 521 2 2 1 9 表4 4 ：非内部连续化算法的计算结果( i i ) n 精确度迭代次数 时间( s ) 1 0 04 4 3 1 0 1 31 70 0 2 7 2 0 02 8 8 1 0 1 3 1 50 1 1