（应用数学专业论文）竞争市场均衡问题的内点算法.pdf

摘要 摘要 本文考虑应用最优化方法来求解经济学中的经典问题一竞争市场均衡问题 本文首先介绍了竞争市场均衡问题的历史背景，研究的现实意义，以及应用最 优化方法特别是内点算法解竞争市场均衡数学模型的发展情况，详细介绍了、v a l r a s 均衡理论的f i s h e r 模型和a r r o w - d e b r e u 模型以及它们的数学描述，在预备知识里 介绍了解线性规划问题的最新的内点算法理论，给出了四种不同的p a t h - f o l l o w i n g 内点算法在论文第二章我们把线性规划的原始一对偶路径跟踪算法根据均衡问题 的特点做了适当的修改，设计了f i s h e r 问题的原始一对偶路径跟踪算法，在第一节 介绍并证明了y e 首先提出的f i s h e r 问题原始一对偶路径跟踪算法，这个算法在计 算的复杂性上大大优于以前的算法，第二节，第三节在第一节算法的基础上分别给 出了对步长调整和方向分解后的逐步的改进后内点算法，并对每个算法作了详细的 理论分析和证明，三个算法在计算复杂性上完全相同，但是理论上算法2 2 ，2 3 的 计算效果优于算法2 1 ，最后我们分析初始点的确定方法，以及算法程序实现的一 些方法，并做了一些初步的数值计算 关键词a r r o w d e b r e u 竞争市场均衡问题，f i s h e r 均衡模型，凸规划，效用函数， 原始一对偶路径跟踪内点算法 a b s t r a c t a b s t r a c t i nt h i st h e 8 i sw ec o n s i d e rt h ec l a s s i cc o m p e t i t i v em a r k e te q u i l i b r i u mp r o b l e m s o ft h ee c o n o m i c su s i n go p t i m i z a t i o nm e t h o d i nt h ef i r s tc h a p t e ro ft h i st h e s i s ei n t r o d u c et h ee c o n o m i ch i s t o r y 1b a c k g r o u n d a n dt h er e a l i s t i cm e a n i n go f8 t u d yo ft h ec o m p e t i t i v em a r k e te q u i l i b r i u mp r o b l e m s a n dt h ed e v e l 。p m e n to fs o l v i n gt h e s ep r o b l e m sa p p l y i n go p t i m i z a t i o nm e t h o de 8 p e c i a l l yi n t e r i 。rp o i n t 出g o r i t h m i nt h el a t t e rw ee m p h a s i s l yi n 七r 。d u c ef i s h e rm o d e l a n da r r o w d e b r e um o d e lo fw a l r a st h e o r ya n dt h e i rm a t h e m a t i c sd e s c r i p t i o n s ，t h e n i nt h ep r e l i m i n a r yk n o r w l e d g ei n t r o d u c et h el a t e s ti n t e r i o rp o i n ta l g o r i t h m b rs 0 1 v i n g u n e a rp r o g r a m m i n g ，g i v ef o u rk i n dd i f f e r e n tp a t h f o l l o w i n gi n t e r i o rp o i n ta l g o r i t h m s i nt h e8 e c o n dc h a p t e rw ea p p r o p r i a t e l ym 。d i f yt h ei n t e r i o rp o i n ta l g o r i t h mo f1 i n e a r p r o g r a m m i n g ，a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fm a r k e te q u i l i b r i u mp r o b l e m ，a n d d e s i g nn e wp r i m a l - d u a lp a t h f 0 1 l o w i n gi n t e r i o rp o i n ta l g 。r i t h mf o rf i s h e rm o d e l ，i n t h e 丘r s ts e c t i o nw ei n t r o d u c ea n dp r o v ep r i n l a l - d u a lp a t h f 0 1 l o w i n gi i l t e r i o rp o i n t a l g o r i t h mp r o p 。s e db yy ef i r s t l y ) t h ec o m p u t a t i o n a lc o n l p l e x i t yo ft h ea l g o r i t h mi s b e t t e rt h a na l lf o r m e ra l g o r i t h m ，i nt h es e c o n da n dt h i r d8 e c t i o nw ed e s i g nn e w p r i m a l d u a lp a t h f 0 1 l 。w i n gi n t e r i o rp o i n ta l g o r i t h mb ya d j u s t i n gt h es t e ps i z ea n d s e a r c hd i r e c t i o n ) t h e ng i v ed e t a n e dt h e o r e t i c a la n a l y s i sa n dp r o o ft oe a c ha l g o r i t h m t h e o r e t i c a l l yt h ea l g o r i t h m2 2 ，2 3i sb e t t e rt h a na l g o r i t h m21 i nt h e1 a s tc h a p t e r w ea n a l y z eh 。wt 。丘n dt h es t a r tp o i n t ，a n dg i v es 。m et e c h n i q u e so ft h ei m p l e m e n t a t i o no fa l g o r i t h m s ，a l s od os o m ec o m p u t a t i o n a le x e r c i s e s a b s t r a c t k e y w o r d s ： a r r o w d e b r e uc o m p e t i t i v em a r k e te q u m b r i u mp r o b l e m ，f i s h e re q u i _ 1 i b r i u mm o d e l ，c o n v e xp r o g r a m m i n g ，u t i l i t yf u n c t i o n ，i n t e r i o rp o i n ta l g o r i t h m ， p r i m a l - d u a lp a 七h f 0 1 l o w i n gi n t e r i o rp o i n ta l g o r i t h m i i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表和撰写过的研究成果，也不包含为获得 北京工业大学或其他教育机构的学位或证书而使用过的材料，与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意。 签名 日期：趔! o ，对于每一个消费者g 至少有一 个“” 0 ，而且对于每一个生产者j p 至少有一个u ” o 假设的意思是在市场中每个消费者手中的钱数不为零，且他( 她) 至少喜欢一 种货物，每一种货物至少对有一个消费者有用( 效用函数不为零) 我们可以看到在 这个假设下每一种货物都有一个正的均衡价格如果一个消费者手中没有钱或者他 ( 她) 的效用函数对所有货物都是零，则其不买任何一种货物即是最优解，那么他 ( 她) 可以从市场中分离出去，如果一种货物对所有消费者都没有价值那么它也能 从市场中被分离出去 一3 北京工业大学理学硕士学位论文 我们将效用函数作为一个约束写入优化数学模型里 4 ，则有 m a x 叫t l o g ( 乳) t g s t = 1 ，p i g u i 一“可z 巧= o ，g j p z t j 0 ， v i ，j 我们可以考虑一个更为一般的问题 ( 1 2 ) m a x 叫。1 0 9 ( u t ) t g s t a z = b ( 1 3 ) z o 矩阵a 是一个m n 且行满秩的矩阵，6 是一个m 维的列向量叫，是第e 个变 量的非负权任意一个满足约束条件的向量称为原可行解 问题( 1 3 ) 的l a i g r a n g e 函数可写为 ，( z ，可，a ) = 叫丁l o g ( z ) + g t ( 6 一a z ) 十a t 茁 函数，( 茁，可，a ) 取得极值的必要条件是偏导数等于零，即 九甄= o ， a z = 6 z 0 。 表示矩阵a 的第i 列，整理后，令s = a 7 ，则如果问题( 13 ) 存在一个最优解 一4 一 第1 章绪论 最优性条件可写为 4 ，5 s z = 甜， a o = 6 o o f 1 4 1 一a r + s = o ，s20 变量和s 是l 柚g r a n g e 或k k t 乘子( 即对偶变量和松弛变量) ，s 是由向量s 生成的对角矩阵假设( 1 3 ) 的可行域有界，且存在有一个相对内点，即有严格内 点z o ，4 z = 6 ，则存在严格对偶解s o ，s = a 丁，对某一个我们定义可行解 集合如下： f + + = ( 。，5 ) ：a z = 6 ，s = a 7 可，z o ，s o ) 可行集的内部定义为； a = ( z ，s ) ：a z = 6 ，s = a t 可，z 0 ，s o ) 如上所述e i s e n b e r g 和g a l e 对f i s h e r 模型当其效用函数为线性时的凸最优化 描述 1 9 ，2 0 他们构造了一个凹的目标函数，该凹函数在均衡点处极大化这样， 寻找均衡点变成一个求解凸优化问题这个问题利用椭球算法在多项式时间内可求 得解这里多项式时间可解指可计算出一个e 近似解，计算所用的算术运算以n 和 1 0 9 ( 1 e ) 的多项式为上界 d e v a n u re ra l 8 j 最近给出一个求解线性效用函数的 f i s h e r 模型的组合算法这两种算法的运行时间阶都是0 ( n 8l o g ( 1 e ) ) y e 4 发展 一种内点算法来求解线性效用函数的f i s h e r 模型的内点算法的得到的计算复杂性 上界为0 ( n 41 0 9 ( 1 e ) ) ，大大降低于上述椭球算法和组合算法的计算的复杂性，等价 于相同规模的线性规划的复杂度上界 北京工业大学理学硕士学位论文 关于a r r o w d e b r e u 模型 a r r o w d e b r e u 模型( 、v a l r a s 模型) 相比f i s h e r 模型最大的区别是，所有的参 与者不分类，没有生产者与消费者区分，每个参与者预先手里只有货物没有钱通 过定价和交换货物使效用函数达到最大与f i s h e r 模型相类似我们可写凸优化模 型 4 ，5 如下： m a x 训。l o g ( 撕) 4 g s t z 。j = 1 ，”p g ( 1 5 ) t 一“可z t j = o ，b _ g j p z ”o ， v i ，j 这里妣未知，我们希望通过选择撕使得最优的对偶价格分别等于这些权可以证盟 1 】确实存在一个训o 在一定条件下有p = 训，所以最优性条件为存在( “，z ) ，( p ，”) 其中( p ，”) 为对偶变量，使得： 。j ( p ，一u q ) 仉) = o ，v 。，j 功一u a 0 ，v i ，j n z ”= l t ；1 也；一乱巧。玎= o ， v j 讹，仉，z j o ， 忱，j f 16 1 可以证明求解a r r o w d e b r e u 问题比上述的f i 8 h e r 问题更难，e a v e s 在f 1 5 】中 说明了如果效用函数是线性的该问题可描述成一个线性互补问题，因此如果这个均 衡存在， l e r n k e 的算法能在有限时间内计算均衡价格同样可以证明对一个初始 第1 章绪论 输入数据时有理数的n 2 维的线性方程系统存在一个均衡有理数解在【1 6 e v a e s 也证明c o b b - d o u g l a s 效用函数的此类问题可以在强多项式时间内求解其他的有 效算法包括p r i m a k ，d i r k s e ，f e r r i s 和r u t h e r f o r 等人的工作，更好的算法有f e r r i s 和p a n g 2 4 遗憾的是它们都没有被证明是多项式算法 e s t e b a n _ b r a v 。指出在组 合经济学有关文献有关于线性和非线性优化算法用来计算均衡问题，因此建议用替 代的基于内点算法的方法，这些方法能有效地计算均衡甚至是对于大规模的模型， 但是它们也没有理论上的复杂性分析最近j a i n 1 0 说明了w a l r a s 的模型也能描 述成一个凸优化的问题，准确地说是一个凸不等式问题，那么椭球算法可以用来求 解y e 4 ，5 提出一个内点算法( 非原对偶的) 解a r r o w d e b r e u 线性效用函数的 纯交换市场平衡问题，复杂性远低于椭球算法的结果 1 3 预备知识 关于内点算法 1 9 4 7 年，g b d a n t z 培提出了求解线性规划( l p ) 问题的单纯形算法，该算法 自提出以来经过不断的改进，在实际应用中取得了很大的成功后来，j e d m 。n d s 在1 9 6 5 年提出了优良算法( g o o da l g o r i t h m ) 即多项式时间算法的概念， v k l e e 和g l m i n t y 用具体实例说明了单纯形算法迭代的次数为0 ( 2 “) ，n 是未知数的个 数，不是一个优良算法大家开始关注和寻找求解l p 的优良算法在1 9 7 9 年， lk h a c h i y a n 提出了一个解l p 问题的多项式时间算法( 即椭球算法) ，但是在实际 中椭球算法的计算效果无法与单纯形算法的计算效果相比为了克服椭球算法在计 算方面的困难，n k a r m a r k a r 在1 9 8 4 年从一个新的视角提出了另一个解l p 问题 的多项式时间的算法( 即投影尺度算法) ，也是第一个内点算法投影尺度算法不但 7 一 北京工业大学理学硕士学位论文 在计算效果方面能够同单纯形算法相比较，而且其固有的多项式时间复杂性和在可 行域内部求解的思想掀起了l p 内点算法研究的热潮 3 7 】 k a r m a r l ( a r 提出的投影尺度算法不仅在计算复杂性方面优于单纯法，而且在解 大型线性规划问题方面显示出强大的能力在迭代过程中能保持矩阵的稀疏性对 于一个给定的l p 可行解，理论上存在一个最好的方向，沿此方向可以得到l p 的 最有解，或者判定其无解但最优可行方向的寻找不是容易的事假设l p 的可行 域是一个多胞形，k a r m a r k a r 注意到两个基本事实： ( 1 ) 如果一个内点居于多胞 形的中心，那么最速下降方向是一个好的可行方向，( 2 ) 存在一个适当的变换，能 将可行域中给定的内点置于变换后可行域的中心，且不改变问题的基本特性根据 这两个事实， k a r m a r k a r 给出了解l p 的投影尺度算法k r a m a r l c a r 投影尺度算 法基本思想是：选定一个内点作为迭代的过程的起始点，对可行域做适当的投影尺 度变换，将当前的内点解置于变换后的可行域的中心，然后，在变换后的可行域中 沿着目标函数的最速下降方向的正交投影移动，获得新的可行内点，然后通过投影 尺度逆变换将新的可行内点影射到原来的可行域，作为新的迭代点重复这个过程 直至找到满足一定精度的点 在k a r m a r k a r 以后，许多数学家提出了仿射尺度算法，包括有原始仿射尺度算 法，对偶仿射尺度算法，原始- 对偶仿射尺度算法仿射尺度算法在两个方面改进 了解线性规划的策略： ( 1 ) 放松了对单纯形结构的要求，不要求线性规划的结构必 须是k a r m a r k a r 的标准型，( 2 ) 用仿射尺度变换( 线性变换) 替代了投影尺度变换 ( 线性分式变换) 这种改进可以直接求解标准形式的l p 问题，仿射尺度算法是 一个多项式时间算法 3 7 ，3 9 一r 一 第1 章绪论 关于路径跟踪内点算法 原始一对偶仿射尺度算法的迭代过程可以看作是利用n e w t o n 法解l p 的最优 性条件的方程如果引入解析中心的概念，将线性规划的解看作是解析中心路径的 极限点，同样利用n e w t o n 法解中心路径上的点，沿着中心路径逼近最优点基于 这种思想的内点算法称为原始一对偶路径跟踪算法以l p 为例来说明几种常用的 原始一对偶路径跟踪内点算法l p 和它的对偶( l d ) 指如下问题 和 m a xc z s t 4 z = 6 ( l 尸) o o m a x 6 t s t s = c a t ， ( 工d ) s o 我们假设原可行域和对偶可行域都有非空的内部，记z 4 为最优值，在这里我 们感兴趣的是找到( l p ) 问题的一个e 近似解，即，z z + e ，z + 一铲5e 定义 2 l j ： q ( 名) = 可：c a t 2o ，一彳+ 6 t o ， b ( n ( z ) ) = 1 号野 l o g ( 勺一巧可) + l o g ( 6 7 可一z ) ，= l 这里z ，然后去寻找q ( 驴+ 1 ) 的叩一近似解析中心可以得到 b ( q ( 名2 + 1 ) ) s _ 日( q ( z ) ) 一巧， 6 o 迭代过程直到找到这样一个扩，它是q ( 妒) 的近似解析中心，其中矿芝矿一e 这个算法迭代步数的上界是0 ( 礼l o g ( ，o z o ) e + n l o g2 ) ，和k a r m a r k a r 算 法的上界相同 r e n e g a r 算法 r e n e g 雒提出了一种新的迭代算法降低了迭代步数的上界，算法描述如下 定义【2 1 q ( z ) = 可：c a 丁蓼0 ，一z + 扩暂0 1 0 - 第1 章绪论 其中一z + 酽g o 有n 项松弛变量s r 2 n 显然有s n + 1 = 算法1 1 2 l 】 c 一俨可 6 r 可一z 6 t 一z o 给定q ( 妒) 的近似解析中心( 扩，s o ) ，卵d ( s ) 叩 1 ，：= o 步1 若( ，z ( ) 一6 r 掣。) o 定理1 2 m 】至多经过0 ( 佤1 0 9 ( ，z o 矿) e + 、，伍) ) 步迭代，算法1 1 产生一个可 北京工业大学理学硕士学位论文 行内点对( 。( 矿) ，矿) 是n ( 矿) ，且 c t 。( 名) 一6 r 可s ，z ( z 2 ) 一矿e 详细证明见 2 1 改进的路径跟踪算法 在原有路径跟踪算法的基础上又发展出了好几种改进的算法，在某种意义上这 些算法仍然是沿着中心路径，只不过每一种算法都允许在中心路径上有一个特定的 松弛 2 1 】 设n 是中心路径的c 的一个邻域，有gc ca ，( z ，s ) 考虑下面的邻 域 2 1 ： a 七( 叩) = ( z ，s ) a ：l i x s 肛e | l 町“，“= z 丁s 礼) ， k ( q ) = ( 。，s ) a ：1 1 x s 一肛e l i o 。卵“，p = z t s n ) ， 二( 7 7 ) = ( z ，s ) a ：l i x s 一“e 磊叼肛，p = z t s 礼) 对某个叩( o ，1 ) 这里定义对任意z r ”， z l l 二：= i i z l j 。，i i z l i 毛：= i l z 十| | 。 其中( z 一) ，：= m i n 勺，o ) ，( 矿) ：= m a x ，o ) ，”l i 。指通常的最大范数，容易得到 a c 小，2 ( q ) c 。( q ) c 二( q ) ca ，q ( o ，1 ) 给定( z ，s ) ，搜索方向d = ( 出，匆，d s ) 有原始一对偶牛顿方法得到，设 z ( 臼) = 。+ d z ；可( 口) = 掣+ d 掣；s ( 毋) = s + d s p r e d i c t 。r c 。r r e c t o r 算法 第1 章绪论 p r e d i c t o r - c o r r e c t o r 算法是每一次迭代首先通过“p r e d i c t o r ”步减少肛，然后 进行“c o r r e c t o r ”使迭代点保持在中心路径邻域内尽管q 的取值可以是( o ，1 ) 之 闻的任意值，不过通常取值为7 7 = l 4 。 算法12 给定初始点( z o ，5 0 ) 2 ( q ) ，q = 1 4 ，设：= o 步1 若( 扩) t s o 设( ，s ) o 满足a 。= 6 ，s = a r ，如果有 s z 一曲l 茎? 7 灿 这里灿o 表示一个误差度量( 类似于线性规划经典内点算法的互补间隙) ，即是一 个小于1 的正常数，且奶= m a x 肛，q ) ，j p 则称这样的点对为原始一对偶可行 集f 上的一个近似中心路径点对 现在我们来求解关于迭代方向如，如，d s 原始一对偶系统的线性方程组【4 ，5 j ： s d 。+ x a 3 = 妇+ xs 4 如= o ，( 2 2 ) 一a t 南+ 以= 0 在这里，t l 于= m a x ( 1 一 v 伍) 弘，屿) ，注意霹如= a t 岛= o ，这个过程主要包 北京工业大学理学硕士学位论文 括求解一个系数矩阵为规范矩阵a d a t 的线性方程，d 是一个对角矩阵，其主对 角线上的元素严格大于零 具体来看 5 ，1 3 ，2 1 】，在方程组( 2 2 ) 第一个式子的两边同时左乘s _ 1 可得 如+ s - 1 x 也= s - 1 + 一x s ) 然后同时左乘a 并且注意到a 如= o 有 由于也= a r 也有 a s 一1 x 也= a s 一1 ( 仍十一x s ) a s 一1 x a t d = a s 一1 ( 曲+ 一x s ) 这里a s 。x a r 是规范矩阵，不妨假设d = s - 1 x 南= ( a d a t ) 一1 4 s 一1 ( 西+ 一x s ) 再由( 2 2 ) 的第二式，第三式可解得丸，如 d 。= a t d 口，d 。= s 一1 ( ( 而+ 一j f s ) 一x d 。) 得到了( 如，以，如) 则设 根据以上分析写出一般的算法 算法2l 茁+ = z + d z 掣+ = 可+ d g s + = s + 也 第2 章解f i s h e t 问题的原始一对偶路径跟踪算法 设： e o ，肛o ，叫，( 。o ，。，s o ) 为初始点，七= 0 步1 如果忪2 s 一国2 | l e ，停止迭代；否则 步2 令 矿+ 1 = ( 1 一叩何) 以妨+ 1 = m a x ( 肛，屿) 由方程组( 2 2 ) 解得蟊，d 。令 茁+ 1 = z + d z 步3 令= + l ，转步1 s 蚪1 = 妒+ 也 在算法中， o 为给定的计算精度，训为权重是事先给定的常向量，( z o ，g o ，s o ) 是初始迭代点 财= m a x 旷“，叻) 的迭代远快于算法的迭代，因此到算法迭代 终止有西= 叫 算法2l 的理论证明 算法的理论证明包括三部分，第一，算法每次迭代新产生的迭代点必须保证其 可行性，即仍然是原问题的一个内部可行点；第二算，算法每迭代一次都可以使目 标函数值减小，保证算法的下降性；第三算法经过0 ( v 伍1 0 9 ( m a x ( 叫) e ) ) 次迭代得 到e 近似解即算法的多项式可解性 为了证明的方便我们引入下面三个新的向量【4 ，5 ，2 扎 p ：= x 一5 s5 如， q ：= x5 s l 5 d s ， r ：= ( x s ) 一5 ( t d + 一x s ) 并且不妨设( z ，s ) 为当前迭代点，( z + ，s 十) 为通过算法得到的下一步迭代点， 一17 _ 北京工业大学理学硕士学位论文 由如，也的性质容易得到：p + q = r ，p t g = o ( 。，s ) ，( 矿，s + ) 分别为当前迭代 点和下一步的迭代点，则有。+ = 石+ 如，s 十= s + 以 引理2 1 西产= m 耵( ( 1 一卵瓶) p ，q ) ，有 8 鹃 证明：由i l s z 一而| ls ? 7 p ，曲j = m a x p ，训j ，j p 及西= m a x ( 1 一叩、历) 肛，u o ) 可得； z j 勺芝而j 一叼肛( 1 一叩) p ； i l 西+ 一x s i l = i ；西+ 一西+ 囝一x s l l i i 西+ 一西| | + i i 西一x s l l 卵p + 叩= 2 卵灿； 所以有： 盯( 聊5 矿刊篙 引理得证 引理2 2 ( 矿，s + ) 是原问题的内部可行点，即( 矿，s + ) 日_ + 证明： | | x 一1 ( z + 一z ) | | = | | x 一1 d 。| | = 1 1 x s 一5 删 i l x s 一5 i l x s 一5 p j i 型 、( 1 一叩) 肛 0 s2 ( 掣) 。 d 。酬= l m 忙竿忖 引理得证 我们设：旷= ( 1 一击) 肛，可知 p + “，西于= m x 灿+ ，奶 北京工业大学理学硕士学位论文 引理24 迭代产生的点对( 矿，s 十) 优于上一个解，| i 矿一一西十1 l 叩旷 证明：由引理21 ，引理2 3 可得： 1 l s + z + 一曲+ 1 1 2 = 1 1 ( s + d 。) ( z + d 。) 一曲+ 1 1 2 = i i s z + s d 。+ x d 。一西+ + d 。蟊| | 2 = l l 见d 。| | 2 = 1 1 珊1 1 0 为给定的计算精度，训为 权重是事先给定的常向量， ( 护，o ，s 0 ) 是初始迭代点 算法2 2 的理论证明 算法二中，当前点和迭代点的关系如下： z 十：= z 十曰d z g + ：= g + 目d ” 日 o ，1 为使其一元函数忪( 目) z ( 目) 一而+ f i 取得极小的值 引理2 6 由算法二迭代产生的点对( z ( 目) ，s ( 目) ) 是原问题的内部可行点，即( z ( 口) ，s ( 目) ) 4 + 一2 2 第2 章解f i s h e r 问题的原始一对偶路径跟踪算法 证明：因为口 o ，1 ，有 | i 义1 ( z ( 口) 一z ) | | = i | x 一1 目d 。| 1 = 钏x s 一啮| | l l x s 一5 训 s1 x s 一5 圳 型 一 ( 1 一q ) p s 爿 熹 引理得证 引理2 7 由算法二迭代产生的点对( z ( 目) ，s ( 日) ) 优于上一个解，忪( 目) 。( 日) 一西+ | | s 叼“+ 证明；由式( 22 ) 引理2 1 ，引理2 3 可得： i l s ( 目) 。归) 一面+ | l= l i ( s + 日d 。) ( z + 口d 。) 一曲十| | = l i ( 1 一目) ( 西+ 一s z ) + 目2 d 。d 。i ! s ( 1 一日) i l 西十一s 。| | + 日2 i i p q | | 2 ( 1 一日) 町“+ 目2 i p q f l 2 ( m 篙肛 这样，如果我们选择常数q ，8 使得下面的式子成立 8 2 鲁+ ( 1 叫z 南鲰叭 ； 近似地有： 3 铲碍2 4 ( 1 一q ) 8 + 2 ( 1 一昝2 ) o ，8 【o ，1 3 ； 北京工业大学理学硕士学位论文 当日= 1 时，3 目2 叩2 4 ( 1 一q ) 日+ 2 ( 1 一叩2 ) o 为给定的计算 精度，训为权重是事先给定的常向量， ( 护，扩，s o ) 是初始迭代点 算法23 的理论证明 算法三中，当前点和迭代点的关系如下； z ( ) ：= z + 。( ) = z + 口1 d 。一十。2 d 。+ ， s ( ) ：= s + s ( 0 ：) = s + d l d s 一+ 。2 d 。士 其中。= ( a ，。) o ，1 2 为使其凸函数忪( a ) z ( 乜) 一曲+ | 】取得极小的值 6 第2 章解f i s h e r 问题的原始一对偶路径跟踪算法 为证明方便对向量p ，q ，r 重新定义如下 同样容易得到 p ：= x 一5 s5 ( 口1 d z 一+ 2 d z + ) ， q ：= x5 s 一5 ( d l d s 一+ q 2 d s + ) ， r ：= ( 。y s ) 一5 ( 0 1 ( 叫+ 一x s ) 一+ n 2 ( 叫+ 一x s ) + ) p + q = r ，g = o 引理2 9 啦叫( 1 刊协蚓引川l 警 证明：类似于引理2 1 ，由财= m a x ( 1 一叩何) p ，叻) 可得： 则有 所以有 q 勺西j 一叼p ( 1 一叩) p | | 西+ 一x s | l = l l 国十一面+ 西一x s 茎叩肛+ 卵“= 2 即弘； l i ( ? ( s ) _ 、5 i 。1 ( 叫+ 一x s ) 一+ 2 ( 叫+ 一y s ) + | ( x s ) 、5 1 1 2 ( 。1 + 。2 ) 叩肛 坐! 竺边业 一f 巧 引理得证 引理2 1 0 由算法三产生的新的迭代点对( z 陋) ，5 ( ) ) ，a o ，1 2 是原问题的内部 可行点，即( z 似) ，s ( 。) ) 日+ 2 7 北京工业大学理学硕士学位论文 证明 l l 叉一1 ( z ( d ) 一z ) | | = 1 1 x 一1 ( o l d 。一+ 2 d 。+ ) l l = i l x s 、5 训 s1 | x s 一5 川硎 型 一( 1 7 7 ) p 型 一、( 1 一叩) p ! i ! ! 竺! ! 翌 1 ( 叩s ；) 引理得证 引理2 1 lp ，g 定义如上式，则有： 1 | 风吲i = l i p 洲竿盯m 证明：类似于引理3 3 的证明 引理2 1 2 由算法三迭代产生的点对( z ( o ) ，s ( ) ) 优于前一个解，忪( a ) z ( 。) 一t 。+ i | 叼肛十 证明：由引理2 9 ，引理2 1 1 可得： s ( a ) z ( a ) 一仍+ | _ = i i s z 一曲+ + 1 ( 似+ 一x s ) 一十。2 ( 训十一x s ) + s ( ) 茁( ) | i ( 1 一a 1 ) 1 1 ( 西+ 一s z ) 一| l + ( 1 一a ：) i | ( 西+ 一s z ) + l + l i s ( q ) z ( ) s2 ( 2 一( 1 + 2 ) ) 印肛十l i p q | | 0 这里肛o = m a x ( 叫) 在f i s h e r 模型中p 个生产者和p 个消费者的f i s h e r 问题里，即集 合p ，c 元素的个数为p 个，变量的个数变为p 2 + p ，毗，z 。i = 1 ，2 p ，j = l ，2 p ； 约束方程的个数为2 p ， z 订= 1 、 坳p ， u 。一u 玎。q = o ， v i c ，p 即系数矩阵a 的维数是2 p ( p 2 + 梦) 由第一个方程约束我们设 4 ： 。：= ；，忱j p ； 一3 m 那么相应的有 第3 章数值实验 硼2 暑咐巧2 ；善u “ 即“? = c ；善专著u 耵；善u d t 则 可得 设9 0 = ( 口o ，丌o ) 令 ( 1 ) s ? = ”? ，有s ? u ? = 卢 口= 2 礼_ 臼，w p ) 础：箬，v l g ，j p 讪t ， s o = a t 矿= a 忍z + p ) 。2 p ) 玑p 。l ( 2 ) s 昌昌= ( 田一”。u 订) p = 2 p 一；蔓l 卢 u 。 = l 可以看出s z 介于卢和2 卢之间在加上两个约束条件构成一个类似于最优 北京工业大学理学硕士学位论文 性条件或解析中心的问题如下； 钆? s ? = p ， v t g 可t e ，j p a z = 6 z o a t + s = o ，s o 满足上述条件的点2 0 ，s o 还不一定是我们要求的初始点，初始条件( 3 1 ) 的第 一个条件要求| | s z 一肛o e | | s ”p o ，令卢= 卢o ，同除以肛。有 i s z p o e i f 叩，根据 求解析中心的势函数下降算法，定义势函数如下 p 2 押 ( p 2 + p ) 1 0 9 ( z 7 s ) 一l o g ( z j s ) 定义7 7 ( z ，s ) ：= 1 1 x s e m 设( z ，5 ) 为可行域的内部点，迭代方向的原始一对偶 牛顿步方程如下： 改进当前点( z ，s ) s 屯+ x a 3 = e x s a 也= 0 ， 一a r d g + 也= 0 ， ( 32 ) z 十= z 十曰d 。，g + = 可+ 臼d g ，s + = s + 臼d s( 3 3 ) 算法3 1 给定初始可行域内部点( 孟o ，5 。) ：( o ，1 ) 设k ：= o 步1 若( 互2 ) r 驴 e ，停止迭代；否则 步2 设( 岔，i ) = “，驴) ，由( 3 2 ) 计算方向d = d ( i ，雷，i ) 一3 2 一 共跏 =l | 第3 章数值实验 步3 计算p = 叭压五订两川( x s ) 一1 2 ( e x s ) | | 令( 牙2 + 1 ，5 + 1 ) = ( 孟+ 口d ，i + p d i ) 步4 令：= 克+ 1 ，转步1 定理3 1 刚 设。+ ，s 十定义如( 3 3 ) ，口= a 、五面网( x s ) 一1 2 ( e x s ) | | ，则如果1 ( z ，s ) 叩，叼 为一个小于1 的正常数，那么选择适当的0 ：使得： j 为一个正常数 妒。( z + 日d 。，s + 扫d 。) 一妒。( z ，s ) 曼一j 根据定理3 1 和势函数下降算法的理论对于这个问题用内点迭代算法3 1 在至 多o ( p 2 l o g p ) 步得到满足初始条件( 3 1 ) 的点 对于原始问题( 1 1 ) 和( 12 ) ，在算法2 1 ，2 2 ，2 3 变量