（管理科学与工程专业论文）互补问题的非内点光滑型算法研究.pdf

互补问题的非内点光滑型算法研究 i n v e s t i g a t i o ni n t on o n i n t e r i o r - p o i n t s m o o t h i n ga 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 y p r o b l e m s 一级学科：筐堡型堂皇王猩 学科专业：笪堡型堂皇工程 研究生：型! 歪蕴 指导教师：塑至逻塾援 天津大学管理学院 二零零八年五月 中文摘要 互补问题是一类非常重要的优化问题，它在工程，经济与交通平衡等领域有 着广泛的应用。因此，对互补问题算法的研究具有重要意义。本文主要研究了几 类互补问题的非内点光滑型算法，并在较弱的假设条件下，具体分析了所提算法 的全局收敛性。本文主要内容如下： 1 对于线性规划问题，文中给出其原问题与对偶问题的最优性条件，并通过 引入一个正则化的对称扰动的光滑函数，将其扩展成一个混合线性互补问题，然 后利用非内点光滑型牛顿算法解该混合线性互补问题。文中提出的算法具有全局 收敛的特性。对于有最优解的线性规划问题，算法能得到一个严格互补解；对于 无可行解的线性规划问题，算法可正确地判断原问题的不可行性。 2 基于线性互补问题的一个增广系统，提出一个正则化的光滑型算法来求解 该增广系统，在较弱的假设条件下得到好的收敛性结论：如果线性互补问题有一 个解，给出的算法或者可判断原问题的可解性，或者直接给出一个极大互补解； 如果线性互补问题不可行，给出的算法能够正确地判断原问题的不可行性。 3 提出一个非内点光滑型牛顿算法求解单调的非线性互补问题和带有p 。函 数的非线性互补问题。算法的全局收敛性假设比已有文献中算法要求的假设条件 弱，只需问题有非空解集即可。在全局收敛性假设相对较弱的条件下，所提出的 算法能够得到问题的极大互补解。 特别是，本文提出的非内点光滑型牛顿算法在求解上述问题的过程中，在每 一个迭代点处只需要解一个线性方程组和做一次线性搜索，比已有文献中的算法 具有更大的优越性。 关键词：线性规划，互补问题，非内点光滑型算法，全局收敛性 2 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 m sa r eo fa l li m p o r t a n tb r a n c hi nt h em a t h e m a t i c a l p r o g r a m m i n gf i e l d ，w h i c ha r ew i d e l yf o u n di nm a n yf i e l d s s u c ha s e n g i n e e r i n g ， e c o n o m i c sa n dt r a f f i cc o n t r 0 1 t h e r e f o r e ，i ti ss i g n i f i c a n tt oi n v e s t i g a t ea l g o r i t h m sf o r s o l v i n g t h e s e p r o b l e m s n o n i n t e r i o r - p o i n ts m o o t h i n ga l g o r i t h m s f o rs o m e c o m p l e m e n t a r i t yp r o b l e m sa r ep r o p o s e da n dt h e i rg l o b a lc o n v e r g e n c ei sa n a l y s e d u n d e rs o m ew e a k e rc o n d i t i o n s m a i nc o n t r i b u t i o n so ft h i sd i s s e r t a t i o na r ea sf o l l o w s 1 a na l g o r i t h mi sd e v e l o p e dt os o l v el i n e a rp r o g r a m m i n gp r o b l e m s ( l p s ) b y i n t r o d u c i n gas m o o t h i n gf u n c t i o nw i t han o r m a l i z e ds y m m e t r i c a lp e r t u r b a t i o n t h e o p t i m a l i t yc o n d i t i o nf o rl p sa r er e f o r m u l a t e da sam i x t e dl 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 w i t c hi ss o l v e db yu s i n gt h ed e v e l o p e ds m o o t h i n ga l g o r i t h m 1 1 1 ep r o p o s e d a l g o r i t h mi ss h o w nt ob eg l o b a l l yc o n v e r g e n tw i t h o u ta n yn o r m a l i t ya s s u m p t i o n i n a d d i t i o n ，t h ep r o p o s e ds m o o t h i n ga l g o r i t h mi sa b l et of i n das t r i c t l yc o m p l e m e n t a r y s o l u t i o ni fl p sa r ef e a s i b l e ，o rt oi n d i c a t ei n f e a s i b i l i t yo fl p si n s t e a d 2 as m o o t h i n g t y p ea l g o r i t h mi sp r o p o s e dt os o l v eas t a n d a r dm o n o t o n el 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 ( l c p ) ，a n de s t a b l i s ht h er e l a t i o n sb e t w e e nt h ea u g m e n t e d s y s t e ma n dl c et h ea l g o r i t h mi st h e nu s e dt os o l v et h ea u g m e n t e ds y s t e mw i t h g l o b a lc o n v e r g e n c ea n dw i t h o u ta n ya s s u m p t i o no fap r i o rk n o w l e d g e o f f e a s i b i l i t y i n f e a s i b i l i t yo fl c ei np a r t i c u l a r , i fl c pi ss o l v a b l e ，t h e nt h ea l g o r i t h mi s a b l et og e n e r a t ee i t h e ram a x i m a lc o m p l e m e n t a r ys o l u t i o nt ot h el c po rd e t e c t c o r r e c t l ys o l v a b i l i t yo fl c p , a n di nt h el a t t e rc a s e ，a ne x i s t i n gs m o o t h i n g - t y p e a l g o r i t h mc a nb ed i r e c t l ya p p l i e dt os o l v i n gl c pw i t h o u ta n ya d d i t i o n a la s s u m p t i o n , d e l i v e r i n gam a x i m a lc o m p l e m e n t a r ys o l u t i o nt ol c ei f , h o w e v e r ，l c pi si n f e a s i b l e ， t h ea l g o r i t h md e t e c t sc o r r e c t l yi n f e a s i b i l i t yo fl c et ot h eb e s to fm yk n o w l e d g e ， s u c hp r o p e r t i e sh a v en o tb e e nd i s c o v e r e da n dc o n t r i b u t e di nt h ee x i s t i n gl i t e r a t u r e so n s m o o t h i n g - t y p ea l g o r i t h m s 3 an o n - i n t e r i o r - p o i n ts m o o t h i n ga l g o r i t h mi sf u r t h e rp r o p o s e di nt h i sd i s s e r t a t i o nt o s o l v em o n o t o n 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 ( n c p ) a n dap 。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 1 1 1 ea l g o r i t h mi ss i m p l e rt h a nm a n ye x i s t i n gs i m i l a r a l g o r i t h m si nt h es e n s et h a ti tn e e d so n l yt os o l v eo n es y s t e mo fl i n e a re q u a t i o n sa n d t op e r f o r mo n el i n e a rs e a r c ha ta ni t e r a t i o ns t e p t h ep r o p o s e da l g o r i t h mi sp r o v e dt o b eg l o b a l l yc o n v e r g e n tu n d e ra na s s u m p t i o nt h a tt h en c ph a san o n e m p t ys o l u t i o ns e t 1 s u c ha s s u m p t i o ni sw e a k e rt h a nt h o s er e q u i r e db ym o s to t h e rn o n 。i n t e r i o r - p o i n t s m o o t h i n ga l g o r i t h m s i np a r t i c u l a r , t h es o l u t i o no b t a i n e db yt h ep r o p o s e da l g o r i t h m i ss h o w nt ob eam a x i m a l l yc o m p l e m e n t a r ys o l u t i o nt ot h en c p c o n c e r n e d t o s h i l l u p ，an o n i n t e r i o r - p o i n ts m o o t h i n ga l g o r i t h m f o r s o l v i n g t h e c o m p l e m e n t a r i t yp r o b l e mi sp r o p o s e di nt h i sd i s s e r t a t i o n , w h i c ho u t p e r f o r m sm a n y e x i s t i n gn o n i n t e r i o r - p o i n ts m o o t h i n ga l g o r i t h m si nt h es e n s et h a to n l yo n es y s t e mo f l i n e a re q u a t i o n si ss o l v e da n do n el i n e a rs e a r c hn e e d st ob em a d ef o rt h es o l u t i o na ta n i t e r a t i o ns t 印 k e yw o r d s ：l i n e a rp r o g r a m m i n g ，c o m p l e n t a r i t yp r o b l e m ，n o n - i n t e r i o r - p o i n t s m o o t h i n ga l g o r i t h m ，g l o b a lc o n v e r g e n c e 4 独创性声明 本人声明所星交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得鑫蓥盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：嘲、本奄 签字口期：劲口g年 月汐日 学位论文版权使用授权书 本学位论文作者完全了解丞鲞盘堂有关保留、使用学位论文的规定。 特授权叁室叁兰可以将学位论文的全都或部分内容编入有关数据库进行检 索，并采用影印，缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：、奄僖 导师签名： 签字日期：加g 年箩月日 签字日期：钟 月、卢 第一章绪论 第一章绪论 最优化问题是个古老的课题。长期以来，人们对最优化问题进行着探讨和研究。 早在1 7 世纪，英国科学家n e w t o n 发明微积分的时代，就已经提出极值问题，后来 又出现l a g r a n g e 乘数法。1 8 4 7 年法国数学家c a u c h y 研究了函数值沿什么方向下降 最快的问题，提出最速下降法。1 9 3 9 年前苏联数学家l v k a n t o r o v i c h 提出了解决下 料问题和运输问题这两种线性规划问题的求解方法。关于最优化问题的研究，随着 历史的发展不断深入。 2 0 世纪4 0 年代以来，由于生产和科学研究突飞猛进的发展，特别是电子计算 机日益广泛应用，使最优化问题的研究不仅成为一种迫切需要，而且有了求解的有 力工具。因此最优化理论和算法迅速发展起来，形成一个新的学科。线性规划问题 最早是由g e o r g eb d a n t z i g 在1 9 4 7 年以前设想出来的。他当时作为联邦空军审计员 的一名数学顾问，开发一个数学规划工具，用于制订、部署、训练后勤保障的方案。 由于该项工作，他于1 9 4 8 年出版了线性结构的规划一书。稍后，在1 9 4 8 年夏 天，t c k o o p m a n s 和g b d a n t z i g 1 j 提出“线性规划”的名称。1 9 4 9 年g b d a n t z i g 提出了用于求解线性规划问题的一个有效的方法一单纯形法。与其它科学领域一 样，线性规划问题的诞生也不是轻而易举的事情。早在1 9 4 7 年以前，数学工作者就 研究了线性不等式系统，它是线性规划的数学理论的核心。对这些系统的研究，可 以追溯到1 8 2 6 年f o u r i e r 的工作。从那以后，许多数学工作者考虑了相关的课题。 尤其是，1 9 3 9 年在w k a r u s h 的硕士论文中出现了有限维空间不等式约束函数的最 优性条件，以及由其他作者提出的线性规划的基础对偶理论的各种特殊实例。早在 1 9 3 9 年以前，l v k a n t o r o v i c h 曾指出了一类有限界的线性规划模型对于生产计划的 实际重要意义，并提出了一个求解线性规划的基础算法。可惜，k a n t o r o v i c h 的工作 在前苏联被忽视了。求解线性规划算法的重要性尚未得到广泛的重视，甚至在线性 规划为d a n t z i g 等人确定以后很久，在别处还不为人所知。( 引自文献【2 】) 在1 9 5 0 年到1 9 6 0 年之间，线性规划理论得到进一步发展和丰富，直到1 9 7 5 年，它真正受到公众的关注，因为在这一年，瑞典皇家科学院把经济科学的诺贝尔 奖授予l vk a n t o r o v i c h 【j j 和t c k o o p m a n s ，以奖励他们对资源最优分配理论的 贡献。另一受到公众关注的线性规划的重大事件发生在1 9 7 9 年，l g - k h a n c h i a n 4 】 证明了s h o r 【5 j 、 j u d i n 和n e m i r o v s k i i 的“椭球法”。这种方法与单纯形法是完全不 同的。在理论上，它应当是优于单纯形法的。单纯形法采用指数的逐次迭代去寻找 第一章绪论 一个最优解。与单纯形法不同，椭球法则在一个多项式的时间界限内找到线性规划 的一个最优解，理论上这新的解法能快速地求解大规模的线性规划问题，但是椭球 法在理论上的优越性并不能在实践应用中得以实现。下面简单地介绍单纯形法和椭 球法的基本思想，借以明确二者之间的区别。 1 1线性规划问题的单纯形法 1 1 1单纯形法的基本思想 试考虑一个标准的线性规划问题 m i n c r x s j a x = b 工o 其中，c 和x 是n 维列向量，彳是m n 维矩阵，b 是m 维列向量。定义 p = 扛r ”j 出= 6 ，x o 是线性规划的可行域。当p 非空时，称线性规划是相容的。 对于一个相容的线性规划，它有一个可行解x p ，如果c t x 在可行域p 上使目标 函数c r x 达到最小值，则称x 是该线性规划的最优解。称p = x + p f 是一个最 优解) 为最优解集合。如果存在一个正的常量m ，对每个在p 中的可行解x ，它的 欧氏范数i i x l l - ( x 。2 + 工：2 + + x 3 2 ) z 小于或等于m ，则称此线性规划有一个有界的 可行域。如果存在一个常量c ，对每个工p ，有c t x c ，则称此线性规划是有界 的。 定理i 1 ( 线性规划的基本定理) 假设对于一个相容的标准型线性规划有可行域 p ，则该问题在p 上极小化目标值z = c t x ，或是无下界的，或是至少在p 的一个顶 点上达到。( 证明见文献【2 】) 需要说明的是，该定理不排除在一个非顶点上有一个最优解的可能性。换言之， 在一个给定的线性规划问题的最优解集中，至少有一个是顶点。线性规划的基本定 理指出，可行域p 的顶点之一是该相容的线性规划问题的一个最优解，除非该问题 是无界的。这一特性指导着线性规划的算法设计。针对寻找一个最优的顶点，单纯 形法由一个顶点开始，希望沿着边界达到一个较好的相邻的顶点，最终停在一个最 优的顶点上。该方法在最坏的情况下，可能要访问所有非最优的顶点。由于在项点 与可行解之间存在着对应性，在迭代算法中，单纯形法可以依据基础可行解来描述： 步骤1 寻找一个基础可行解； 2 第一章绪论 步骤2 检查现行基础可行解是否为最优，如果它为最优，停止迭代。否则，转至 下一步骤； 步骤3 移动至目标值有所改善的一个基础可行解，然后返回至步骤2 。 对步骤1 ，通常应用两阶段法和大m 法来寻找一个初始的基础可行解。在步骤 2 检查现行解是否达到最优，给出停止规则。停止规则未被满足，转至步骤3 ，去寻 找一个改善了的基础可行解。单纯形法由现行解出发，以适当的步长，沿着使目标 函数值有所改善的边方向移动去寻找最优解。 1 1 2 单纯形法的计算复杂性 单纯形法的计算复杂性取决于总的迭代次数和每步迭代所需的基本运算的次 数。d a n t z i g 6 1 的每步迭代需要m ( n m ) + 刀+ 1 次乘法和m ( n m + 1 ) 次加法，是o ( m n ) 阶的，其他改进的单纯形法每步迭代需要的乘法和加法也是o ( m n ) 阶的。下面说明 单纯形法需要的迭代次数。单纯形法及其变型的每步迭代是从一个顶点到另一个顶 点。一个标准形式的线性规划问题，其可行域具有c ( n ，m ) 个可能访问的顶点。只要 n 2 m ，就有c ( n ，m ) = n ! ，z ! ( 以一m ) ! ( n m ) ”2 ”，这说明需要指数阶的迭代次数 是完全有可能的。1 9 7 1 年，v e e 和g l m i n 7 1 给出一个例子，证明d a n t z i g 的单 纯形法需要经过所有2 ”一1 个顶点才能达到最优解。 例( k l e e m i n t 、y 的例子) 对于0 万 1 2 ： m a x x n s f 0 x l 1 蠡i l x i 1 一反i 一1 ； i = 2 ，3 ，n x i 0 ； i = 1 , 2 ，n 可以看出，原点是基础可行解。如果从原点出发，按最大下降规则旋入非基变量， 单纯形法需要作2 ”一1 次迭代，经过可行域的所有顶点，才能达到最优解。然而， 这种指数次的迭代情况，在现实问题中很少发生。一般情况下，对于中等规模的实 际问题单纯形法需要4 m 至6 m 次迭代来完成两阶段的计算。据估计，当刀相对于m 来说较大时，迭代次数预计为铡，其中e x p ( a ) l o g ：( 2 + n m ) 。因此单纯形法可以 期望的计算量是o ( m 2 刀) 。这说明单纯形法虽然在理论上是指数复杂性的，但在实际 中很有效。 1 2 线性规划问题的椭球法 单纯形法的指数复杂性为人们认识后，线性规划的一个主要理论问题就是“线 一3 一 第一章绪论 性规划有没有多项式时间算法?1 9 7 9 年l g k h a c h i a n 4 】改进了n z s h o r ， d b y u d i n 和a s n e m i r o v s k i i 为凸规划设计的椭球法，获得了多项式时间复杂性的 线性规划算法。 1 2 1 椭球法的基本思想 试考虑下面n 个变量m 个线性不等式 a x b 其中，么是m 露的矩阵，x r “和b r ”。 椭球算法首先从球开始，若上述线性不等式系统有解，则该球的半径大到足以包 括不等式系统的一个解在内。令初始球中的解集为p ，算法不断构造一系列椭球， 第k 次迭代的椭球为b ，使得p 冬b 。这些椭球是按照体积几何收缩的方式构造的。 能够证明p 矽时p 的体积是正的，从而证明经过多项式次迭代后算法可以找到椭 球的中心即为解，或者证明上述线性不等式系统没有解。下面给出方法的几何描述： 给定一个非负数，和一个点z r ”，n 维欧氏空间中以r 为半径的球定义为 1 月 s ( z ，) = z 月”l ( x ，一z ，) 2 ，j 2 ) = x 尺4j ( x z ) r ( x - z ) r 2 ) i = 1 s ( z ，i ) 的体积定义为v o l s ( z ，) 。给定一个r l 聆的非奇异矩阵a 和一个点c r “， 仿射变换t ( a ，c ) 将每个点x r “映射为一个新的点a ( x c ) r “。每个椭球都是单 位球s ( o ，1 ) 经某个仿射变换的像。因此，一个椭球可表示为 e = x 尺“i ( x c ) 1a r a ( x c ) 1 ) ， 点c 定义为e 的中心，e 的体积由下式给出 v o l ( e ) = l d e t ( a 一) i v o t s ( o ，1 ) ， 其中，d e t ( a 一1 ) 为4 的逆矩阵的行列式的值，用半椭球去e = 缸e a r x a r c 表示e 和半空间的交，这个半空间是由经过e 的中心的超平面h = x r ”a 7 x = 历界定 的，其中a r “是一向量，是标量。于是有如下几个重要的结果： ( 1 ) 每个半椭球去e 包含在体积小于p - 1 心”1 v o l ( e ) 的椭球苴内； ( 2 ) 最小的椭球e 包含了其中心在p 内的凸多面集p ； ( 3 ) 如果不等式a x b 有解，则必有石r ”是它的一个解，且一2 工，2 ( j = 1 , 2 ，n ) ； 4 第一章绪论 ( 4 ) 如果不等式a x b 有个解，它的解所在的立方体 z r ”峙i 2 ，i = 1 , 2 ，z ) 中的体积至少是2 叫”。 利用上述结果，求解线性不等式系统的椭球法可描述如下： 步骤1 初始化。令k ：= 0 ，e 。= s ( o ，2 2 ) ，b k = 2 2 l i ，且x 。= 0 步骤2 解的检查。若x 满足a ，7x b ，i = 1 ，2 ，m ，则停止，x 即为解；否 则，确定使不等式口，t z b i 成立的下标i ，按式 石t + j = z t f ( b 。口，而) 和 b m = 6 8 一o b 女口f ( 反以f ) r ( a i r b 口f ) ) 计算x 和b m ， k ：= k + 1 步骤3 若v o l ( e ) 2 小+ ”，则停止，口，t x c r x ，当满足终止准 则时，则停止迭代。这种方法的关键是选择使目标函数值上升的可行方向。下面给 出简要分析。 首先，引进松弛变量，将上述线性规划写成 m a xc r x s t a x + 1 ，= b( 1 2 ) ，0 在第k 次迭代，定义，似为非负松弛变量构成的m 维向量，使得 1 ，( 。，= b 一厶( 。) 再定义对觚阵耻讲a g ( 专，古) 作仿射变换，令w = d 。1 ， 把线性规划式( 1 2 ) 改写成 m a xc7 x s t a x + d k - 1 w = b w 0 在变换空间中，选择搜索方向d = 匮 ，j 作为可行方向是下面齐次方程的一个解。 d 彳d ，+ d 。= 0 ( 1 3 ) 对于式( 1 2 ) 的任一解，有么r 4 ( q 么以+ d 。) = 0 ， 由此得到 d ，= 一( 4 r d k 2 彳) 一1 彳7 d 女d 。 ( 1 - 4 ) 在每次迭代中，目标函数在d ，方向的方向导数是c r d ，将( 1 - 4 ) 式代入c7 d ，中， 有 c r d ，= c7 1 卜( 4 r d t 2 彳) 一1a r d k d 。 = - 0 女爿( 4 r d k 2 彳) 一1c r d 。 选择d 。，使c r d ，最大，则 d 。= 一d k a ( a r d k 2 彳) 一1c ( 1 - 5 ) 由式( 1 5 ) 确定d 。后，可得出( 1 3 ) 式的一个解，其中 d ，= ( 彳7 d k2 彳) 一1c 同时，对d 。作逆仿射变换，可得到 d ，= d k d 。= 一彳( 彳r d 女2 彳) 一1c = 一, 4 d ， 搜索方向确定后，还需确定沿此方向的步长。设后继点x ( “1 ) = x + 2 d ， - 8 第一章绪论 步长五的取值应保证x ”制为司行域的内点，即满足 a ( x + 2 d ，) b 2 , 4 d ， b a x ( ) 一2 , 3 。 1 ，( 。) 令口= m i l l - 盖了) i ( d v ) i 0 ，置k ：= 0 ； 步骤2 计算) - 卜，令对角矩阵么= 纰( 古，古) ，计算 d ，= ( 彳r d k 2 爿) 一1 c ； 步骤3 令以= 一彳以，五2 厂m i n 若l ( 以) ， j m i n _ 。li = 1 ，聊 i ，则有出( o ) _ x a t o ) e 0 ( 1 7 ) ( 1 8 ) 其中，c 和x 是r l 维列向量，b 和y 是m 维列向量，a 是m n 矩阵，秩为m ，可行 域分另u 记作s p = t x l 4 x = 6 ，x 。，s 。= l y l a t y + w c 。) ， 可行域内部删记作蹄咄i 血乩删，踣= l y l a t y + w 鸹w 。) ， 根据线性规划互补松驰性质，x ，y ，w 为最优解的充分必要条件是 fa x = b ，x o 彳7 y + w = c ，w 0 【x w e = 0 其中，x = d i a g ( x l ，x 2 ，工。) ，工，是x 的第j 个分量，w = a g ( w 1 ，w 2 ，w 。) ，是w 的第i 个分量。这组条件称为k a r u s h k u h n t u c k e r 条件。现将条件x w e = 0 换作 x - w e = e ，e 是分量全为1 的n 维列向量，实参数 0 。得到松驰 k a r u s h k u h n t u c k e r ( k k t ) 条件： fa x = b ，z o a 7 y + w = c ，w 0 ( 1 - 9 ) i x w e = e 定理1 2 设线性规划( 1 7 ) 式的可行域有界且内部s p + 非空，则对每个正数，松 驰k k t 条件( 1 9 ) 存在唯一内点解。( 证明见文献【2 】。) 定义原始对偶可行集 和可行集内部 s = ( x ，y ，w ) f 彳x = 6 ，a r y + w - - c ，( x ，w ) o ) 1 0 一 第一章绪论 s + = ( x ，y ，w ) a x = 6 ，a 。y + w = c ，( 石，w ) 0 ) ， 由定理i 2 知，若s + 非空，则对每个 0 ，下面系统 i a x = b ，工 0 a 7 y + w = c ，w 0 im 殆= p 存在唯一解 ( ) ，y ( i t ) ，w ( i t ) ) 。一般把点集 ( x ( ) ，y ( i t ) ，w ( i t ) ) j 0 ) 称为原始一对偶 中心路径。 定理1 3 在中心路径上，当i t 减少时，原问题的目标值单调减少且趋于最优值，对 于每个中心路径参数，对偶间隙c r x ( i t ) - b r y ( i t ) = n i t 。( 证明见文献 【2 】。) 定理1 3 说明，在中心路径上，随着参数的减小，对偶间隙趋近于零，相应的点x ( i t ) 和y ( ) ，w ( i t ) 分别趋近原问题和对偶问题的最优解。 1 4 2 参数的估计和移动方向的计算 如果点( 石，j ，w ) 在中心路径上，即满足式( 1 - 9 ) ，显然有i t ：兰型，如果任取 n 点( x ，y ，w ) 不在中心路径上，后面给出的算法仍按式：! 兰来估计的值。 n 如果线性规划存在最优解，根据定理1 3 ，在原始对偶中心路径上，当参数趋 于零时，原问题与对偶问题均趋于最优值，如果能够求出中心路径 ( x ( i t ) ，y ( i t ) ，“i t ) ) ，再令趋于零，取极限即可求出原问题和对偶问题的最优解。 然而，要求出x ( i t ) ，y ( i t ) ，w ( i t ) 的解析表达式一般并非易事，因此路径跟踪法并 不去计算中心路径，而是通过迭代，大致沿着中心路径逼近最优解。 设任取一点( 工，y ，们，其中x 0 ，w 0 。此时，目标是求一个方向 ( h 石，ay ，aw ) ，使迭代产生的点 + a x ，y + a y ，w + a w ) 位于原始- 对偶中心路 径上，即满足 a ( x + x 、= b ， a 1 ( y + 少) + ( w + 川= c ( x + 必) ( 形+ a w ) e = e 经整理，上式可写作 a a x = b a x ， 彳7 缈+ a w = c a r y w w a x + x a w + 灭r w e = i te x - 1 4 , r e ， 第一章绪论 记6 一a x = p ，c a r y w = 盯，忽略二次项觚a 耽，用矩阵形式表示，则有 褂0 a 。i w 0x 料a w r | | yl = i 仃 i il lii e x 阮i 解之，可求出移动方向 朗。 1 4 3 选择步长参数 求出移动方向( 缸缈，a w ) 后，需确定沿此方向移动的步长参数五，以便求出后 继点( x + 缸，y + 缈，w + a w ) ，a 的取值应满足 x + 2 5 x 0 ，w + a s w 0 即 石+ 心， o ，= l ，2 ，疗； + 五w f 0 ，i = 1 , 2 ，刀 由于 x o ，w f 0 ，旯 0 ， 上式即 一生，：1 ，2 ，以了17 一一a w i ，f - 1 ，2 ，刀， 九x| w 因此， _ 1 m a x 一一a x j ，一坐) ，为保证x + 心 o ，w + 肋m o 成立，引进小于 工j w i 且接近1 的正数p ，令五：m i n 印 m a x ( 一a x j ，一业) 】- l ，1 ) 。 1 4 4 计算步骤 步骤1 给定初始点( x ( ，y ，w 1 ) ，其中x 1 0 ，w 1 0 ，取小于且接近l 的 数p ，精度要求s 0 ，正数m 0 0 ，置k ：= l ； 步骤2 计算p ：6 一a x ( ，仃= c a r y 一w ，7 = x 。1w ，= 万三，其中万 是小于l 的正数，通常取万2 而1 ； 步骤3 若恻i 。 s ，i 。 m ，则停止计算，原问题或对偶问 题无界。否则进行下一步。 步骤4 解方程 1 2 第一章绪论 瞄0a 蝈i ay0 a w = k ey w e 、 7 l = l 仃 i l 形x | |il “一 其中， x = d i a g ( x i ( k ) , x 2 ，x n ( k ) ) ，w = d i a g ( w i ( k ) , w 2 w n ) 得解( 缸，分”，w ( t ) ，置名：i n i n 仞【m a x ( 一垒，一坐) _ l ，1 ) 步骤5 令x 。+ 1 = x 。+ 尬“，y + 1 2y + 旯分，w 。+ 1 = w + 2 a w 。 1 5 论文结构与内容 自1 9 8 4 年k a r r n a r k a r 求解线性规划的投影算法发表以来，已有大量内点法的文 献 1 4 - 2 3 用于求解线性规划、线性互补和凸规划问题，近几年研究热点已转向非凸规 划、半定规划【2 4 。6 】等问题的求解。然而内点法也并非尽善尽美，其中最突出的问题 是，由复杂性分析所提供的多项式时间界限并不能作为一个算法好坏的依据。例如， 小步算法的多项式复杂界限d ( ，zl o g ( n 6 ) ) 远低于大步算法的o ( n l o g ( n 6 ) ) ，但在 实际计算上比后者要差得多。虽然提出一些方法来缩小这两类算法存在的上述矛盾， 但算法实现方面的问题并没有得到很好解决。其次，内点法中的内点限制在算法实 现方面有一定的障碍。为克服内点算法的上述缺陷，非内点路径跟踪算法【37 j ( 光滑 型算法) 被提出用以解决各类问题。 利用非内点路径跟踪算法解决各种优化问题已有很多成功的研究成果 3 8 - 5 6 】。该方 法通过引入一个单调下降且趋于零的光滑参数，将非光滑问题重构成光滑问题，再 通过求解光滑问题，从而获得非光滑问题的解。该算法与内点算法相比，其最大的 优点就是初始点的选取是任意的，且不要求中间的迭代点恒为正的，比内点算法具 有更大的灵活性。 本文利用一个对称扰动的光滑函数，分别将线性规划问题，线性互补问题，非 线性互补问题重构成光滑问题，利用光滑型算法求解所讨论的问题。在较弱的条件 下证明所给出的算法的全局收敛性质。 全文的组织结构如下：第二章互补问题概述，介绍互补问题及其推广，运筹学、 工程管理中的互补问题以及互补问题的研究现状；在第三章，介绍求解线性规划问 题的光滑型算法，它与已有方法的主要区别是将线性规划问题的最优性条件扩展为 一个混合线性互补问题，得以利用光滑型算法求解，算法的全局收敛性不需要添加 任何假设条件；在第四章考虑了单调线性互补问题的光滑型解法；在第五章给出了 非线性互补问题的光滑型算法；在第六章利用光滑型算法研究特定的非线性互补问 1 3 第一章绪论 题，即带有p 函数的非线性互补问题。 本文使用如下符号：“：2 意思是“定义为”，如i ：= 1 , 2 ，1 + 1 ) 。孵”定义为 维实列向量空间，在吼”中，吼：，吼：+ 分别定义为非负和正的子空间。上标丁定义 为“转置”。任取正数z ，厂，对任意的两个向量x 吸7 ，y 吸，记( 工，y ) 铮0 r ，y r ) r 。 若x 0 ，则x ，0 ，( 对任意的i = 1 , 2 ，) ，0 协定义为每个元素均为0 的，xr 的 矩阵。 1 4 第二章互补问题 2 1 互补问题及其推广 第二章互补问题 互补问题是一类重要的优化问题，在实际应用中，它出现在工程物理，经济 与交通平衡等领域 5 7 - 6 1 ，同时它也出现在约束优化的最优性条件中。因此，对它 的研究具有重要意义。 互补问题的标准形式是：给定向量函数f ( x ) ：吼”一吼”，求一向量x 吼一， 使得 了r f ( x ) = 0 ，工0 ，f ( x ) 0 ( 2 1 ) 当f ( x ) 为线性函数，即f ( x ) = m x + q ，m 吼“”，q 9 t ”时，称式( 2 1 ) 为线 性互补问题，记为l c p ( m ，g ) ；当f ( x ) 为非线性函数时，称式( 2 1 ) 为非线性 互补问题，记为n c p ( f ) 。互补问题的一个自然推广就是变分不等式问题，即求 解一向量x q ，使得 ( y x ) 。，( x ) 0 ，v y q ( 2 2 ) 这里q 吼”为一个非空闭凸集。互补问题也有不同形式的推广，例如混合线性 互补问题，水平线性互补问题，l o r e n t s 锥上的线性互补问题等。 ( 1 ) 混合线性互补问题 混合线性互补问题，简称m l c p ，一般形式是：给定a 吼“4 ，b 吼 c 婀”，d 贸，f 吼”和b 9 t “，求工孵”，y 吼4 ，j 吼”且满足 f a y + b x + 归o 砂+ e x + f = 0 ( 2 3 ) l x o ，s o ，x ，s ：0 在式( 2 3 ) 中，若a 为非奇异矩阵， l c p ( e - d a b ，f d a 一1 c ) 。 ( 2 ) 水平线性互补问题 水平线性互补问题，简称h l c p ， m 孵“”，求x 孵“，s 吼”且满足 则式( 2 3 ) 可进一步表述为线性互补问题 一般形式是：给定n 孵t