（运筹学与控制论专业论文）不精确牛顿法求解交通平衡模型.pdf

摘要 i i i 互补性概念是最优化问题以及平衡性分析和计算研究的中心事实上，在研究 线性规划的初期，线性规划的算法：分析及其结构等基本方面与互补松弛性的相关 性就已经获得了普遍的认可，这种相关性也延续到非线性规划及其推广中，尤其是 变分不等式问题 变分不等式与非线性互补问题在数学规划、经济均衡模型、博弈论、工程设计 等众多领域都有着许多重要的应用，二者之间有着密切的联系，变分不等式是一个 比互补性问题更广泛的问题，很多互补性问题的结论都来源于变分不等式理论；然 而，二者之间的关系并不是单方面的，互补性问题也为变分不等式的发展做出了很 大的贡献 本硕士论文主要以以往求解非线性互补问题和变分不等式的方法为基础，研究 了用不精确牛顿法来求解变分不等式的方法在第一章中，我们简单介绍了非线性 互补问题和变分不等式的起源、发展历史、定义以及二者之间的联系在第二章中， 简单介绍了几种求解变分不等式的算法第三章主要介绍了不精确牛顿法求解非线 性互补问题的方法以及非线性互补问题的在经济平衡中的一个实例在第四章中， 我们在综合以上方法的基础上，将不精确牛顿法推广弱求解变分不等式问题中，证 明了算法的收敛性，并给出了其在交通平衡模型中的应用，从而证明了该算法的正 确性和可行性 关键词；变分不等式，非线性互补问题，互补松弛性，投影收缩算法，不精确牛顿 法 a b s t r a c t i v t h ec o n c e p to fc o m p l e m a n t a r i t yi sc e n t r a lt ot h es t u d yo fo p t i m i z a t i o np r o b l e m a n dt h ea n a l y s i sa n dc o m p u t a t i o no fe q u i h b r i a i n d e e d ，s i n c et h ee a r l yd a y so fl i n e a r p r o g r a m m i n g ，i th a sb e e nr e c o g n i z e dt h a tt h ee s s e n t i a la s p e c t so fal i n e a rp r o g r a m - - a l g o r i t h m i c ，a n a l y t i c a l ，a n ds t r u c t u a l - - a r ei n v a r i a b l yc o n n e c t e dt ot h ep r o p e r t yo fi t s e x t e n s i o n s ，i np a r t i c u l a r ，t h ev a r i a t i o n a li n e q u a l i t y b o t ho ft h ev a r i a t i o n a li n e q u a l i t ya n dn o n l i e a rc o m p l e m e n t a r i t yp r o b l e mh a v em a n y i m p o r t a n ta p p l i c a t i o n si nd i f f e r e n tf i e l d ss u c ha sm a t h e m a t i c a lp r o g r a m m i n g ，e c o n o m i c s e q u i l i b r i u mm o d e l ，g a m et h e o r y , e n g i n e e r i n gd e s i g n ，e c t t h e r eh a v ec l o s er e l a t i o n s h i p b e t w e e ne a c ho t h e r t h ev a r i a t i o n a li n e q u a l i t yi sam o r eg e n e r a lp r o b l e mt h a nt h ec o m p l e - m e n t a r i t yp r o b l e m m a n yr e s u l t sf o rt h ec o m p l e m e n t a r i t yp r o b l e ma c t u a l l yo r i g i n a t ef r o m v a r i a t i o n a li n e q u a l i t yt h e o r y n e v e r t h e l e s s ，t h er e l a t i o nb e t w e e nt h e s et w op r o b l e m si sn o t u n i l a t e r a l ；i n d e e d ，c o m p l e m e n t a r i t y a l s oh a sm u c ht oo f f e rf o rt h ev a r i a t i o n a li n e q u a l i t y t h em a i np u r p o s eo ft h i st h e s i si st op r o p o s ea l li n e x a c tn e w t o nm e t h o df o rt h ev a r i a t i o n a li n e q u a l i t yp r o b l e m i nf a c t ，t h ep r o p o s e dm e t h o di sm a i n l yb a s e do nt h ep r e v i o u s m e t h o d sf o rt h ev a r i a t i o n a li n e q u a l i t ya n dn 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 f i r s t ，i n c h a p t e rl ，ab r i e fi n t r o d u c t i o ni sg i v e nt ot h eo r i g i n ，h i s t o r y , d e f i n i t i o n ，a n dt h ec o n n e c - t i o no ft h et w op r o b l e m s a n dt h e n ，i nc h a p t e r2 ，w es i m p l yi n t r o d u c es e v e r a la l g o r i t h m s f o rt h ev a r i a t i o n a li n e q u a l i t y a ni n e x e c tn e w t o nm e t h o df o rt 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 ma n da ne x a m p l ef o re c o n o m i c se q u i l i b r i u ma r ea l s og i v e ni nc h a p t e r3 i n c h a p t e r4 ，w ee x t e n dt h ei n e x e c tn e w t o nm e t h o dt ot h ev a r i a t i o n a li n e q u a l i t yp r o b l e m a n de s t a b l i s ht h ec o n v e n g e n c eo ft h ea l g o r i t h m a tt h ee n do ft h ec h a p t e r4 ，w ea l s og i v e a na p p l i c a t i o nt ot h et r a f f i ce q u i l i b r i u mp r o b l e m s ，a n dt h u st h ec o r r e c t n e s sa n df e a s i b i l i t y o ft h ea l g o r i t h ma r es h o w n k e y w o r d s ：v a r i a t i o n a li n e q u a l i t y , t h en o n l i e a rc o m p l e m e n t a r i t yp r o b l e m ，t h ep r o p - e r t yo fc o m p l e m e n t a r ys l a c k n e s s ，p r o j e c t i o n a n dc o n t r a c t i o nm e t h o d ，i n e x a c tn e w t o n m e t h o d 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 本论文使用授权说明 沁6 f 。抄 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 骅嘲够 第一章。绪论 1 1 引言 自从l e m k e 和h o w s o n 共同完成的具有开创性意义的论文【3 6 】以及2 0 世纪6 0 年代中期和7 0 年代早期h e r b e r ts c a r f 的学术著作【6 2 】发表以来，各学术界和专业 人士都对经济和博弈平衡的计算产生了浓厚的兴趣关于平衡性计算的研究，其最 初的推动力来源于对一般平衡理论的经验分析以及将此理论应用于税收、失业等研 究领域的需要近些年，实验经济学的发展以及工业中战略规划模型的应用使得用 于有效分析和数值求解经济和博弈理论均衡模型的算法有了新的需求 最初用于计算经济平衡的算法都是以l e m k e 和h o w s o n 关于一个双矩阵博弈 平衡点的存在性的创造性证明为基础的，这些算法就是我们现在所熟知的不动点 算法在这一领域，有很多著名的先驱者做出了突出的贡献： s c a r f 在文【5 6 中引 入了原始基的概念，并创先描述了逼近一个连续映射的不动点的算法； k u h n 和 h a z l s e n 分别在文【3 4 】和【2 2 】中引入了单纯形法；e v e s 在【1 2 ，1 3 】中将分段线性映 射引入到了计算不动点的文章中t o d d 的经典之作 6 5 】以及g a r c i a 和z a n g w i l l 的稍近期的论文【2 1 1 中都有这些算法的详细论述，有关这些算法的应用也甚为广泛 【3 0 ，3 8 ，3 9 ，5 7 ，67 】尽管不动点算法有很强的理论性，然而，在实际中要解决大规模 的平衡模型还是有相当难度的2 0 世纪7 0 年代后期，美国能源部建立的p i e s ( 项 目独立估值系统) 能源模型，为不动点算法应用于实际问题的失效性提供了一个较 强的的实践依据 解平衡模型的另一传统算法是非线性最优化( 即文【2 1 】中的平衡规划) 正如 c a r e y 在文1 6 】中所论述的，这种算法需要在模型中做一些限制性的假设，因此，用 最优化算法求解平衡模型与不动点算法比起来，也不能使人完全满意 概括地说，用于解平衡模型的最优化和不动点算法都有各自的优点和弊端；在 需要求解大规模的平衡问题时，二者要么有失一般性，要么计算效率比较低近些 年，有限维变分不等式和非线性互补问题的出现，填补了最优化和不动点算法的空 缺 p i e s 模型和相关的p i e s 算法很大程度上推动了有限维变分不等式( v a r i a t i o n a l i n e q u a t i o n ) 和非线性互补问题( t 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 m ) 领域的发 2 0 0 6 上海大学硕士学位论文 2 展最初，变分不等式是由p h i l i ph a r t m a n 和g u i d os t a m p a c c h i a 于1 9 6 6 年在学术论 文【3 l 】中引入的，继而又由s t a m p a c c h i a 在几篇经典论文【3 7 ，“，5 8 】中将其扩展开 来变分不等式问题也有其他几个常用的名称，例如，在e v a e s 的文【1 5 1 中被称为 稳定点问题( t h es t a t i o n a r yp o i n tp r o b l e m ) ，在r o b i n s o n 的文 5 5 】中被称为广义方程 ( t h eg e n e r a l i z e de q u a t i o n ) 等对于变分不等式的早期研究，大部分都致力于与变分 法或者最优控制理论以及与偏微分方程边界值同题的解的关系的研究k i n d e r l e h r e r 和s t a m p a c c h i a 在文【3 5 】以及b a i o c c h i 和c a p c l o 在文【4 】中都详细介绍了变分不等 式在无限维度量空间的应用 而非线性互补问题则最早出现于1 9 6 4 年r i c h a r dc o t t l e 的博士学位论文【7 】中， 此论文于1 9 6 6 年发表于s i a mj o u r n a lo na p p l i e dm a t h e m a t i c s 杂志( 见文【8 ) 然而“互补问题”这一名称，在这两篇论文中都没有提及，而是后来出现在文【9 】中， 该论文是由c o t t l e ，h a b e t l e r ，和l e m k e 共同完成的，用于解决线性互补问题对于非 线性互补问题的早期研究，大多是致力于对解的存在性问题的研究，对于算法也有 一定程度的的研究，但是却很少涉及应用方面当时，对于非线性互补问题的研究大 都被对于线性互补问题的高涨热情所淹没毫无疑问，对于线性互补问题的研究， 贡献最大的应届l e m k e 和h o w s o n 给出的双矩阵博弈的独创性算法( 见文【3 6 】) ，正 如上面所提到的，这一算法引导了整个不动点算法体系的发展 非线性互补问题是变分不等式的一种特殊情形的这一说法在早期就已得到了普 遍认可( 见k a r a m a r d i a n 文 3 3 1 ) 尽管如此，这两个问题早期的发展却是沿着不同 的方向进行的，最显著的是这两个问题研究领域的不同：变分不等式是在无限维度 量空间进行研究的，而非线性互补问题却是在有限维欧几里得空间1 9 7 8 年在意 大利e r i c e 召开一次会议，首次尝试将这两个研究领域相接轨 有限维变分不等式问题( 尤其是非线性互补问题) 在目前研究领域拥有如此活 跃且颇具成果的地位，离不开以下几个开创性的贡献( 只讨论有限维的情形) 首 先，是上面提到的建立p i e s 模型的经验其次，是m i c h a e lj s m i t h 的论文 5 9 】的发 表，他在该文中用一个有限维变分不等式来表示交通分配问题( 实际上，s m i t h 建 立该模型时，并没有意识到他给出的公式是个变分不等式问题，关于这一点，却是 由s d a f e r m o s 在文【1 0 】中指出的，虽然s c f a n g 的论文【1 6 ，1 7 】也几乎在同一时间 指出了这一点，但却在几年后才发表) 正是这些论文的发表，使得很多空间和非空 间模型也随之产生并广泛应用到实际中，诸如：地域间商品流量预测 1 8 ，4 7 】，纳什 均衡的解【2 0 ，2 3 】，货物运输价格预测 24 】等第三个贡献应归属l a r sm a t h i e s e n ， 2 0 0 6 上海大学硕士学位论文 3 他尝试用最新的非线性互补问题的方法来求解w a l r a s i a n 和一般平衡模型这一事 件重新激起了经济领域里对于算法研究的兴趣尽管m a t h i e s e n 的算法获得了极具 鼓舞性的数值结果( 见文 4 0 ，4 1 i ) ，然而由于该算法在实际应用中无法证明其收敛 性，固而也引起了很多质疑其实对于这方面的研究，不只m a t h m s e n 一人，p r e e k e l ， r u t h e r f o r d ，s t o n e 都分别在文【4 8 ，5 1 ，6 0 】中获得了类似的结果，这些结果，进一步证 明变分不等式( 或非线性互补问题) 在求解大规模平衡问题时的优点所在p r e e k e l 同时在文| 4 8 1 中对不动点和非线i 生互补算法进行了有趣的比较，更进一步证明了这 一点 正是由于有限维变分不等式和非线性互补问题在实际中具有如此的重要性，从 而也引起了更广泛的关注，对于其算法的研究更是层出不穷本文将在第二，三章 详细列述有关这两个问题的一些算法 1 2 基本定义 在这一小节中，我们给出变分不等式和非线性互补问题的基本定义及其关系 ( 注：本文所讨论的问题都定义在有限维欧几里得空间酽中，故以下所说“变 分不等式”均为有限维，) 定义1 2 1 设n 是舻中的一个非空子集，f 是兄n 到其自身的一个映射则 变分不等式问题，记作v i ( a ，f ) ，就是寻找一个向量矿q ，使得 ( z 一。+ ) t f ( z + ) 0 ， vx n ( 1 2 1 ) 定义1 2 2 设f 是r ”到其自身的一个映射则非线性互补问题，记作n c p ( f ) ， 就是寻找一个向量矿，使得 x + r 华，f 扛+ ) 兄军， f ( z 4 ) r 。+ = 0 ( 1 22 ) 其中磁表示舻的非负空间 在定义1 2 2 中，若令f ( x ) 是关于z 的仿射函数，即f ( x ) = q + m x ，其中q r 4 ， 矩阵m 卯“此时，n c pc f ) 就是一个线性互补问题，记作l c p ( q ，m ) 关于这 个问题的详细论述可参阅m u r t y 的文【4 2 1 ，本文将不再列述 定义1 2 3 设q 是r “中的一个凸锥，f 是r ”到其自身的一个映射则广 义互补问题，记作g c p ( a ，f ) ，就是寻找一个向量矿，使得 x n + ，f ( x + ) n + ，f ( z ) t z + = 0 ，( 1 2 3 ) 2 0 0 6 上海大学硕士学位论文 4 其中n + 表示q 的对偶锥，即 n 4 = y r “：y t x 0 ，vz n ) k a r a r n a r d i a n 在【3 3 】中给出了以下性质，首次证明了广义( 尤其是非线性) 互 补问题与变分不等式问题的关系： 性质1 , 2 1 设n 是r “中的一个凸锥，则。+ e q 是v i ( a ，f ) 的解，当且仅当 矿是a c p ( f 2 ，f ) 的解 因此说，任一个广义( 尤其是任个非线性) 互补问题一定是一个变分不等式 问题，反之却不一定成立但是，当n = 磷时，变分不等式v i ( f l ，f ) 与非线性互 补问题n c p ( f ) 则是等价的 第二章变分不等式的几种算法 本章，我们主要介绍有关变分不等式的几种常见算法 2 1 二次临近点算法 给定一个点到集的算子t ，以及酽中的一个闭凸子集q 一个变分不等式问题 v i 可描述为：寻找一个矿n ，以及g + t ( x + ) ，使得 其中( ，_ ) 表示舻中两个向量的内积，在这里我们只讨论t 是从r “到其自身的一 个极大单调映射的情况 一y ，茁一z ) 0 ，vy 7 t ( x ) ，vy t ( z ) ，vz ，z d o m t( 2 1 2 ) 其中d o m t ：= x i t ( x ) 0 ) 则称算子t 是单调的 g ( t ) ：= “z ，y ) r “r “iy t ( z ) ) 例如，一个闭凸集q 的法锥算子，其定义如下； z c z ，= f i ( 暂，口 z ：；。1 v q ：；： c 2 3 ， 很明显，d o m n i 2 = q ，且当n ；j 矿或i n t l 2 ( 即n 的内部) 时，总有肌1 ( z ) = o 成立从文 5 2 】我们可知法锥算子胍2 是r “上的一个极大单调算子 由以上分析，我们可知( 2 1 1 ) 式中可转换为求一个极大单调算子的零点， 即寻找一个向量矿，使得 其中胍z 为( 213 ) 式所定义的这种求一个极大单调算子t 的零点的方法就是临近 点算法( p p a ) ，具体可参见文【1 9 ，5 3 】 2 0 0 6 上海大学硕士学位论文 6 给定觑2 卢 0 ，不精确的临近点算法( 见文【5 3 】) 产生迭代序列 cn ， 满足 ( p p a )e 2 臃( 刃+ 1 一x k ) + t ( z + 1 )( 2 1 5 ) 其中驴r “是误差项 当驴= 0 ( vk ) 时的情形就是精确的p p a 为了确保收敛性，很多学者对序列 e 添加了各种附加条件，具体可见文【1 4 ， 2 7 ，5 3 】- 例如，e c k s t e i a 在文 1 4 】中假设 。 i le l l + o o ， ( 2 1 6 ) k = l 以及 o o ( e ，扩) ；( 2 1 9 ) 式中的投影算子也是必要的，投影不仅加速了收 敛，而且也保证了迭代序列 扩 中的点始终包含于n 包括( 2l8 ) ，( 21 9 ) ，( 2 1 1 0 ) 以 及( 2 ，1 1 1 ) 在内的新的预测一校正临近点算法在一个相当宽松的条件 下证明是收敛的 i ie 临佻i lz 。一妒扎s u p u k 0 2 0 0 6 上海大学硕士学位论文7 值得指出的是( 2 1 1 2 ) 中的精确准则限制岛的上界为不小于l 的常数，因 而有很大的实用价值 因为临近点项( z 1 一x k ) 是二次函数到z 2 “一一1 1 2 的微分，因此如果有必 要将p p a 与其他的临近点方法相区分的话，该临近点方法也称二次临近点方法 2 2 对数一平方临近点算法 近年来，许多学者利用一些非线性函数r ( z ，一) 代替线性项扛一扩) ，致力于 临近点方法( p p a ) 的广义化，由此研究出了一些可求解变分不等式问题的“内点” 式的临近点方法详细可见 1 ，5 ，6 6 在上述的文献中，收敛性都是在对于问题的限制性条件下证明的，因而，只在 解集非空的假设下，产生一个全局收敛于( ) 的解的内点式临近点方法仍然是一 个很大的挑战 a u s l e n d e r 和他的合作者在文【2 ，3 】中提出了一个新的临近点算法 后，该问题才得以解决 设0 p l 是任意给定的参数对口霹+ ( ：= i n t r 芊) ，定义： 帅) ： 耋如t 。2 ( 灿毒扣m 瑚蚯嘞， ( 2 2 1 ) i + o 。 掣r 孙， 容易验证d ( ，”) 是个非负、严格闭凸函数，并且当且仅当u = ”时，d ( ”) = 0 函数d ( “，”) 的第一个二次项是通常用于二次临近点方法的正则项，而第二项则保证 了该算法是一个内点算法，即产生的迭代点都在冠的内部 令c 是一个多面体集合，定义如下： c ：= 扣r “| a x 耐( 2 2 2 ) 其中a 是一个纸n ) 矩阵，b 邪，p n 我们假设矩阵a 满秩，即r a n k a = n ，且 c 的内部，i n t c ：= 忙r “ia x 0 ，e 邪，一i n t c ，总存在唯一的z + 1 i n t c 满足( 2 2 6 ) 式 定理2 2 1 设 一) 是l q p 算法产生的序列，且假设偿1 纠和偿刀式成立 若工w f e c j 的解集，记作s ，为非空，则序列 收敛于一个解x + s 2 3 投影收缩算法 近年来，何炳生教授等提出了一种求解大规模单调变分不等式的投影收缩算 法，并将该算法广泛应用于经济、交通等平衡模型中具体见文【2 5 ，2 6 ，6 8 】t 本小 节主要介绍应用于交通模型的含有黑箱描述的有约束的变分不等式的投影收缩算法 【6 8 k 对应的变分不等式定义如下： 寻找一个向量矿en ，使得 v i ( q ，f )( z 。一z + ) f ( z + ) 0 ， vz 。n ( 2 3 1 ) 其中f 是r “到它自身的一个映射，n 是r “的一个非空子集，且n = 疋n s ， 其中爿，s 都是闭凸集，且 s = z 夥la 7 z b )( 2 3 2 ) 2 0 0 6 上海大学硕士学位论文9 其中a 是一个n m 阶矩阵，b r ”文【6 8 】中对应于实际问题，对变分不等式问 题作出了如下假设： 假设2 3 1f ( z 1 没有显表达式 对于给定的y r ! ，下列松弛问题 啊疋，f k ( a r v ) ) 。爿，( ：7 2 将由黑箱自动产生一个解 对于给定的5 z ，不能估计出f ( 5 ) 的值但 z ) r f ( z ) + a y ) 0 ， v z z ( 2 33 ) 假设2 3 2f ( z ) 在z 上是一致强单调的，即存在一个常数卢 0 ，使得 ( z i ) r ( f ( z ) 一f ( 孟) ) 三p l l z 一童0 2 ， vz ，孟z 假设2 3 3w m ，驯的解集，记作q + ，为非空 在适当的正则假设下，通过一个l a 母a n g i a n 乘子向量y j o ，将原问题转化 寻找u + = ( z + ，y + ) 茁r m ，使得 i ( z z ) r f ( z + ) + a y + 0 v 口z ，( 2 3 4 0 ) l ( g 一+ ) t 一( a t 。+ 一6 ) ) 0 vy 碎 ( 2 3 4 b ) 换言之，对于一个给定的对偶变量旷o ，设5 + 是自动产生的( 2 3 3 ) 式的最优 解若( 矿，y + ) 满足( 2 3 4 5 ) ，则5 + 就是w ( u ，f ) 的最优解因而可将问题转化为求 最优的l a g r a n g i a n 乘子旷以下我们记r ? 为y 定义2 3 1 闭凸集y 上的投影映射( e u c l i d e a n 范数下 记作b y ( ) ，即 ( z 一吩( z ) ) 7 ( 毋0 ) 一) 0 ，vz r ”，y y ，( 2 3 5 ) l i j ：( z ) 一f 1 2sl i z 一1 1 2 ，v 。r “，y y ，( 2 3 6 ) i i p y ( z ) 一引1 2 l i z 一1 1 2 一i i z p y ( z ) 1 1 2 ，v 。r “，y y ，( 2 3 7 ) 引理2 3 1 对v 卢 0 ，( 矿，y + ) 是俾3 4 ，的解，当且仅当 2 0 0 6 上海大学硕士学位论文 1 0 x旷*：=毋px。旷x*+-卢if。a(，x。*)+4-一ay，*”1 对于给定的y y ，设z 是( 2 3 3 ) 的解 解v i ( n ，f ) 就等价于求下面函数的零点： ( 2 3 9 a ) ( 2 39 b ) 则由假设2 3 1 和引理2 3 1 可知，求 e ，卢) ：= g j 分b + f l ( a 7 2 , 7 一b ) 1 ( 2 3 1 0 ) 引理2 3 2 对所有的y r m ，西 卢 0 ，总有 l 】e ( ，卢) | | i l e ( y ，卢) 引理2 3 3 若当分别令y = 口，y = 口时，牙和是问题 的解，则有不等式 及 成立 z 爿，扛7 一譬) t f 如) + a y 0 ， vz 疋， ( 2 3 1 1 ) ( 口一) t a t ( 5 ：一i ) 卢1 1 i 一引1 2 ，( 23 1 2 ) 归叫i 掣恬_ 引i 下面给出该算法的框架以及一些初步的分析 对一个给定的y 2 y ，投影收缩算法的每个迭代都由两步完成 步，提供一个预测值矿，第二步校正步，产生新的迭代点y 。“ 预测步；对于给定的y ，选择一个仇 0 ，满足 垆= 毋矿4 - 觑( x 一吼 和 风i i a t ( z 。一m k ) l s l l 可一雪| | ，0 0 以及一个试验值凤 0 ( 扩根据试验值y 。自 动产生) ，我们设试验值 口= 毋【2 十f l k ( a t x 一砷】， 然后计算 哪；篙产， 其中妒根据试验值矿自动产生如果r k 曼”，那么试验值矿就可作为预测值， 否则，通过令厥：= 臃+ v + o 9 来缩减凤，然后再重复该过程 校正步：选择一个讯h ，讹】，且令 f + 1 = p y y 。一n 女d ( ”2 ，凤) 】， ( 2 31 8 ) 或 9 ；+ 1 = b b + d k 卢k ( ，一b ) 】， 【2 3 1 9 ) 其中 一讥鹬铲，( 2 3 2 0 ， d ( y k , 熊) = y 一口。+ ) s k a t ( x 一) ( 2 3 2 1 ) 注2 32 ：注意到一，矿，妒都由y 和觑决定，因而( 2 3 2 1 ) 中的向量 d = y 一矿+ 凤a 7 扛一妒) 是y 和仇的函数 该方法使得距离函数 1 1 y 一矿1 1 2 取得最小值 割一9 + 1 1 2 在y 点的下降方向的 集合由向量s s d ( y ) 组成，其中 s d ( y ) = s r “l ( g 一矿) 7 s 0 ，如果铲，铲满足r 2 3 ，1 4 ) 和偿3 i 5 ) ， 则一d ( 气凤) 是距离函数剖一旷lj 2 ( vy + y + ) 在y 处的下降方向，也即 ( ”一9 + ) 7 d ( g ，仇) ( g 一口) 丁d ( g 觑) ，vy + y( 2 3 2 5 ) 及 ( 一口) 于d ( ，z 4 ) ( 1 一) l l y 。一口。1 1 2 ( 2 3 2 6 ) 引理2 3 5 对于给定的y y ，凤 0 ，如果扩，妒满足俾量j 纠和阳3 1 5 ) ， 则a 7 妒一b 是距离函数钏一旷1 1 2 ( vy + y + ) 在y 处的下降方向，也即 ( 掣一可+ ) t ( 凤( a r 童一6 ) ) s ( 一雪) t ( 凤( a t 壬一b ) ) ， vy + y ( 2 3 2 7 ) 及 ( 一) 7 ( z 4 ( a 7 i 一6 ) ) s ( p 一1 ) l l 一口1 1 2 ( 2 3 2 8 ) 对于给定的y r ? 及凤 0 ，预测步提供了两项矿，妒，满足( 2 3 1 4 ) 和 ( 2 31 5 ) 引理2 3 4 和2 3 5 说明一d ( 扩：觑) 和觑( a 7 i 。一b ) 是割一圹j 2 在y 点的 下降方向由此我们可通过下式获得新的迭代圹+ 1 ： 冀1 = p 矿o d ( 扩，厥) 】，( 232 9 ) 或 譬1 = 毋扩+ c 0 4 ( a 7 妒“) j ( 2 3 3 0 ) 令 e * ( ) ：= | | g 一9 + i f 2 一l f 破+ 1 一+ j | 2 ，( 2 33 1 ) 2 0 0 6 上海大学硕士学位论文 1 3 其中谵+ 1 由校正步( 2 3 3 0 ) 和( 2 3 3 1 ) 获得，o k ( a ) 称为利润函数，因为它度量了 第k 步迭代获得的进展情况 为了获得快速收敛，需要选择适当的步长。 0 下面的定理2 3 1 告诉我们如 何来选择步长a 首先，令 t ( ) ：= 2 a ( y 一雪) t d ( y k , 臃) 一n 2 | d ( ，z k ) 1 1 2( 2 3 3 2 ) 其中d ( 矿，凤) 如式( 2 3 2 1 ) 中定义 定理2 31 对于给定的y 0 及觑 0 ，设萨，扩以及扩满足俾3 1 4 ) 和 侣3 i 6 ) 则对于v 0 ，由碑，3 e 9 ) 或凹3 s o ) 产生的新的迭代姥+ 1 满足 e k ( o ) t k ( a ) ( 2 3 3 3 ) 推论2 3 1 对于给定的y 0 及风 0 ，设矿，一以及妒满足偿3 钉和 偿3 1 6 ) 则当n ；l ，由偿，3 2 圳或俾3 3 0 ) 产生的新的迭代砖+ 1 满足 j p + 1 9 + 0 2sf l y 一+ 1 1 2 一( 1 一，) | | g 一口0 2 ( 2 3 3 4 ) 定理2 3 1 的证明中，最关键的是不等式 | | 稚+ 1 一f + | | 2 兰 | 可。+ a 卢k ( a ? 孟一6 ) 一掣+ 2 一 轳+ a 凤( a t 牙。一砷一业+ 1 1 2 ( 2 3 3 5 ) 由此我们可得到不等式 e k ( n ) t k ( 血) = 2 a ( y 一雷) t d 0 。，卢k ) 一乜2 i l a ( 暂，凤) | 1 2 显然要选择一个步长a k 使得t k ( o ) 最大注意到t k ( a ) 是a 的二次函数，且在 a ；= 甜 处取得最大值，且 t ( d ) = o ；( 9 2 一口) t d ( 9 ，风)( 2 3 3 6 ) 下面的定理表明n ；和t k ( n ；) 都有大于零的下界 定理2 32 对于给定的y 0 及风 0 ，设矿，扩以及i 满足俾3 圳和 俾3 印，且当“= n ；时，由俾3 2 印或俾3 s o ) 产生了新的迭代砖“，则 电= 鹬铲匆1 ( 2 3 3 7 ， 2 0 0 6 上海大学硕士学位论文 1 4 且 t ( n ；) 丁1 t , 舻一挪( 2 3 3 8 ) 定理2 3 3 设 y ) 是由上面的预测一校正法产生的序列，则 y ) 收敛于某个 解y o 。y + 第三章非线性互补问题的一个经典算法 本章节主要介绍不精确牛顿法求解非线性互补问题的这一经典算法。该算法是 由j o n g - s h ip a n g 于1 9 8 6 年提出的，具体可见文【4 9 】 3 1 背景介绍 牛顿法是解非线性方程组的一个古老且常见的方法在其众多重要性质中，最 重要的应属其局部二次收敛性。嗵些年，经典的牛顿法求解非线性方程已经拓宽到 用于求解非线性互补问题( 及其相关的很多问题) r o b i n s o n 是提出此延拓的第一 人，具体可见文【5 4 ，5 5 】然而，该方法的收敛性分析是j o s e p h y 在【3 2 】中获得的 牛顿法解非线性互补问题最早应用于各种经济问题以及网络平衡模型 考虑个非线性互补问题，即； 寻找个向量x r n ，使得 z 0 ， f ( 茁) 0 ，x t f ( 卫) = 0( 3 1 1 ) 其中f 是从舻到其自身的一个可微映射 牛顿法通过以下方法产生一个序列 扩) 来解( 3 1 1 ) ： 给定，定义。+ 1 是线性互补子问题： z 0 ，w = f ( z ) + v f ( z ) ( z 一茁) 三0 ，x t w = 0( 3 1 2 ) 的一个精确解在适当的假设下，序列如 是有明确定义的，且局部二次收敛于问 题( 3 1 1 ) 的解z + 牛顿法最重要的性质是其二次收敛率，即，存在一个常数c 0 ，使得对所有 足够大的k ，有 i | z 2 + 一。40 c i i z 2 一z + | 1 2 ( 3 1 3 ) 但是，该方法也有儿处众所周知的弊端，尤其是( a ) 需要计算n n 阶的雅克 比矩阵v f ( z ) 以及( b ) 求线性互补子问题( 3 1 2 ) 的解不精确牛顿法的发展解决 了同题( a ) ，其中每步迭代都用一个修正的逼近矩阵( 通常用一个低秩矩阵) a 来 代替v f ( 扩) ，从而希望能更快地获得下一子问题的解 1 5 2 0 0 6 上海大学硕士学位论文 1 6 3 2求解非线性互补问题的不精确牛顿法 不精确牛顿法，简单来讲，即，设一表示当前迭代，a 表示v y ( z ) 的一个 逼近矩阵我们希望+ 1 是子问题 z 0 ， w = f ( x ) + a k ( z 一卫) 0 ， z t 们= 0 ( 3 2 1 ) 的一个不精确解 一个立即出现的问题就是：对于某一适当的选择( 氐 ，为了使序列 一) 收敛 于问题( 3 1 1 ) 的一个解，z + 1 应该怎样逼近( 3 2 1 ) 的一个精确解? 当然，如何获 得z + t 来满足所需要的精确度也是一个同等重要的问题 、 不精确牛顿法的本质是测定一个给定的向量怎样逼近于一个线性互补问题的 解为了引入我们所需要的这个测度，首先考虑一个一般形式的线i 生互补问题： z 0 ，w = q + m x 0 ，x t w = 0 ( 3 2 2 ) 很明显，一个向量z 是( 3 2 2 ) 的个解，当且仅当它满足 h ( x ) = m i n ( x ，q + m x ) = 0 ( 函数h 是个向量值函数，其中，“m i n ”取各分量的最小值) 这样，数量l i h ( x ) i l 可作为给定向量z 逼近( 3 2 2 ) 的解的一个测度下面的两个引理将阐明这一用途 为了阐述第一个引理，我们首先给出非线性互补问题( 3 1 1 ) 的, t n 解的概念 定义3 2 1 设矿是p 1 ， 的解若存在z