（系统分析与集成专业论文）线性约束凸规划的原始对偶内点算法.pdf

要 凸规划问题是数学规划和工业应用等领域的一个重要研究课题，许多规划问 题属于凸规划问题的研究范畴，比如线性规划( l i n e a rp r o g r a m m i n g ) 、半正定规划 ( s e m i d e f i n i t eo p t i m i z a t i o n ) 、二阶锥优化( s e c o n d - o r d e rc o n i co p t i m i z a t i o n ) 等等 这些具体的规划问题出现在众多的工业应用和生产过程中，研究一类有效算法对 于解决凸规划问题具有十分重要的意义 自从k a r m a r k a r 在1 9 8 4 年提出了求解线性规划问题的多项式时间内点算法以 来，内点算法得到了较快的发展，由于对求解大规模规划问题的有效性及其广瑟 应用使得内点算法成为数学规划最活跃的研究领域之一 本文主要研究了解线性约束凸规划问题的有效内点算法，并对线性约束凸二 次规划进行了深入研究作为线性约束凸规划问题的特殊情形，线性约束凸二次 规划是一种重要的优化问题，并在实际生活中有广泛应用我们把内点算法的思 想应用于解特殊的凸规划问题针对线性约束凸规划问题的特性，设计出相应的 原始对偶路径跟踪内点算法，并得到较好的算法复杂性解线性约束凸规划阿 题的原始对偶路径跟踪内点算法基于一种新的迭代搜索方向，并通过巧妙的方 法估算当前迭代点与中心路径的距离算法中采用了纯牛顿步，我们分析了纯牛 顿步的可行性及算法的局部二次收敛性，最后在有限的多项式时间内得到原问题 的一个近似最优解，整个算法设计得比较完善；对于解凸二次规划问题的原始一 对偶路径跟踪内点算法，该算法基于一核函数，通过核函数所具有的较好性质来 进一步改善算法复杂性分析说明该算法是一多项式时间算法在完善的算法设 计、分析之后，我们给出相应的数值实验数值结果表明，设计的原始对偶路径 跟踪内点算法非常有效 全文安排如下，第一章，序言，简单地介绍了线性约束凸规划问题、凸二次 规划问题以及内点算法的研究现状，并介绍本文的主要内容；第二章，重点介绍 解线性约束凸规划问题的原始对偶内点算法设计，可行性分析及算法复杂性分 析；第三章介绍解凸二次规划问题的原始一对偶内点算法的设计以及核函数的性 质、并进行复杂性分析；第四章给出了相应的数值实验结果；最后，在第五章总结 本文的研究成果及对今后研究课题的展望 关键词：线性约束凸规划，原始一对偶内点算法，大步校正方法和小步校正方法。 凸二次规划，多项式时间复杂性 至q q 墨生土连太堂壅堂亟堂焦迨塞曼 a b s t r a c t c o n v e xo p t i m i z a t i o ni sa ni m p o r t a n ts u b j e c to fm a t h e m a t i c a lp r o g r a m m i n ga n di t h a sw i d er a n g eo fa p p l i c a t i o n si ni n d u s t r i a l ，e n g i n e e r i n ga n dm a n a g e m e n t ，e t c m a n y p r o g r a m m i n gp r o b l e m sb e l o n gt oc o n v e xo p t i m i z a t i o no n e 8 ，s u c ha sl i n e a rp r o g r a m m i n g p r o b l e m s ，s e m i d e f i n i t eo p t i m i z a t i o np r o b l e m sa n ds e c o n d - o r d e rc o n i co p t i m i z a t i o np r o b - l e m se t c t h e s es p e c i f i cp r o g r a m m i n gp r o b l e m sa r i s ei nan u m b e ro fi n d u s t r i a la p p l i c a t i o n s a n dp r o d u c t i o np r o c e s s e s i ti 8a ni m p o r t a n tt o p i ct op r e s e n te f l q c i e n ta l g o r i t h m sf o rc o n - v e xo p t i m i z a t i o np r o b l e m s s i n c e1 9 8 4 ，k a r m a r k a rp r o p o s e dap o l y n o m i a l - t i m ei n t e r i o r - p o i n ta l g o r i t h mf o rl i n e a r p r o g r a m m i n g ，i n t e r i o r - p o i n ta l g o r i t h mh a sb e e nd e v e l o p e dr a p i d l y b e c a u s eo fh i g h l y e f f i c i e n c yf o rl a r g es c a l ep r o b l e m sa n dw i d e l yu s e d ，i n t e r i o r - p o i n ta l g o r i t h mb e c o m e so n e o fm o s ta c t i v er e s e a r c ht o p i c s t h i st h e s i sc o n c e n t r a t e sm a i n l yo ne f f i c i e n ta l g o r i t h m sf o rac l a s so fc o n v e xp r o - g r a m m i n g ，t h a ti s ，l i n e a r l yc o n s t r a i n e dc o n v e xp r o g r a m m i n g m o r e o v e r ，s i n c es e v e r a l i m p o r t a n tp r a c t i c a lp r o b l e m sa r ed i r e c t l yf o r m u l a t e da sc o n v e xq u a d r a t i cp r o g r a m m i n g p r o b l e m s ，w ea l s oc o n s i d e rt h ec o n v e xq u a d r a t i cp r o g r a m m i n ga sas p e c i f i cc l a s so fl i n - e a r l yc o n s t r a i n e dc o n v e xp r o g r a m m i n g w ef i r s tp r e s e n tap r i m a l - d u a lp a t h - f o l l o w i n g i n t e r i o r - p o i n ta l g o r i t h mf o rl i n e a r l yc o n s t r a i n e dc o n v e xp r o g r a m m i n g t h i sp r i m a l - d u a l p a t h - f o l l o w i n gi n t e r i o r - p o i n ta l g o r i t h mi sb a s eo nan e wt e c h n i q u ef o rf i n d i n gac l a s so f s e a r c hd i r e c t i o n sa n das t r a t e g yo ft h ec e n t r a lp a t h t h em e a s u r e m e n to fd i s t a n c eb e t w e e n c u r r e n ti t e r a t i o np o i n tt oc e n t r a lp a t hi sa ni n g e n i o u s l ym e t h o d i nt h ea l g o r i t h m ，o n l y f u l ln e w t o ns t e p sa r eu s e d w ea n a l y z et h ef e a s i b i l i t yo ff u l l - n e w t o ns t e p sa n dq u a d r a t i c c o n v e r g e n c eo ft h ea l g o r i t h m a tt h ee n d ，w ed e r i v et h ec o m p l e x i t yo ft h ea l g o r i t h m t h e nw ea l s op r e s e n tap r i m a l - d u a lp a t h - f o l l o w i n gi n t e r i o r - p o i n ta l g o r i t h mb a s eo nak e r - n e lf u n c t i o nf o rc o n v e xq u a d r a t i co p t i m i z a t i o n t h ep r o p o s e dk e r n e lf u n c t i o nh a s8 0 m e p r o p e r t i e st h a ta l ee a s yf o rc h e c k i n g t h e s ep r o p e r t i e se n a b l eu 8t oi m p r o v et h ec o l - p l e x i t yo fl a r g e - u p d a t ei n t e r i o r - p o i n tm e t h o d f i n a l l y , w ep r o v i d en u m e r i c a lt e s t t h e n u m e r i c a lr e s u l t 8s h o wt h a tt h ep r i m a l - d u a li n t e r i o r - p o i n ta l g o r i t h mi sd e p e n d e do nt h e p a r a m e t e r so fk e r n e lf u n c t i o n t h et h e s i si so r g a n i z e da sf o l l o w s i nc h a p t e r1w ei n t r o d u c eb r i e f l yt h ed e v e l o p - m e n to fl i n e a r l yc o n s t r a i n e dc o n v e xo p t i m i z a t i o n ，c o n v e xq u a d r a t i cp r o g r a m m i n ga n dt h e i n t e r i o r - p o i n ta l g o r i t h m s w ea l s os u m m a r i z eo u rr e s e a r c hi nc h a p t e r1 i nc h a p t e r2 ，w e p r e s e n tap r i m a l - d u a li n t e r i o r - p o i n ta l g o r i t h mf o rl i n e a r l yc o n s t r a i n e dc o n v e xo p t i m i z a - t i o np r o b l e m s t h e nw ea n a l y z et h ef e a s i b i l i t ya n dq u a d r i cc o n v e r g e n c eo fn e w t o n8 r e d s a n dw ed e r i v et h ec o m p l e x i t yf o rt h ea l g o r i t h m i nc h a p t e r3 ，w ep r e s e n tap r i m a l - d u a l p a t h - f o l l o w i n gi n t e r i o r - p o i n ta l g o r i t h mb a s e do nk e r n e lf u n c t i o nf o rc o n v e xq u a d r a t i co p - t i m i z a t i o na n do b t a i nt h ec o m p l e x i t yo fa l g o r i t h m i nc h a p t e r4 ，w es h o w8 0 m en u m e r i c a l t e s tr e s u l t s f i n a l l y , s o l v ec o n c l u s i o n sa n dr e m a r k sa r ed i s c u s s e di nc h a p t e r5 k e y w o r d s ：l i n e a r l yc o n s t r a i n e dc o n v e xo p t i m i z a t i o n ，p r i m a l - d u a li n t e r i o r - p o i n tm e t h - o d s ，l a r g e - a n ds m a l l - u p d a t em e t h o d s ，c o n v e xq u a d r a t i co p t i m i z a t i o n ，p o l y n o m i a lc o i n - p l e x i t y 原创性声明 本人声明t 所呈交的论文是本人在导师指导下进行的研究工作除了文中特 别加以标注和致谢的地方外，论文不包含其他人已发表或撰写过的研究成果参 与同一工作的其他同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意 签名：掀扯 日期：沙3 御殷 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，u p , 学校有权保留 论文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容 ( 保密的论文在解密后应遵守此规定) 签名：；诙扭 导师签名：磊p 巳咨日期：蝴争r 丹3 伪 2 0 0 8 年上海大学理学硕士学位论文 1 第一章序言 1 1 研究概况 1 1 1 问题的提出 凸规划问题研究的是凸的目标函数在一系列凸函数约束下的极大( 极小) 值问 题其研究发展经历了近一个世纪，它是一类特殊的数学规划问题其规划模型在 众多的工业生产过程中使用许多规划问题像线性规划( l i n e a rp r o g r a m m i n g ) 、半 正定规划( s e m i d e f i n i t eo p t i m i z a t i o n ) 、二阶锥优化( s e c o n d o r d e rc o n i co p t i m i z a t i o n ) 等等均从属于凸规划的研究领域，相关的一些研究成果可以参考【3 3 】在凸规划问 题的发展过程中，一些其他领域相关规划问题的突破激起了凸规划问题的研究发 展 第个发展是二十世纪八十年代在线性规划领域出现的多项式时间内点算法， 给凸规划问题的研究带来激动人心的发展【冽人们发现内点算法可以有效 地用于解决凸规划问题，并且得到很好的效果 第二个发展是人们发现凸规划问题在实践中的广泛应用比以往想象的更加多 从二十世纪九十年代以来，人们在很多领域发现了凸规划的应用，像自动控制 系统、预测和信号处理、电子商务和网络，以及电路设计、数据分析和模拟、 统计、金融等等【4 5 】，人们还发现凸规划模型在组合优化和全局最优化领域有 广泛的应用 对求解线性约束凸规划问题的算法研究是非线性规划研究中的重要和基本的课题 之一对线性约束凸规划问题，g o n z a g a 和c a r l o s 给出了一种一阶仿射尺度算法。 在该算法的每一步迭代过程中，通过对目标函数的一阶泰勒展开沿最速下降方向 进行线性搜索，并且在原始非退化性的假设下，证明了这样产生的迭代点序列的 任一聚点都是问题的一个最优解【1 1 l ，后来s u n 对一类特殊的目标函数的凸规划问 题给出了一种二阶仿射尺度算法【3 7 】近来，有许多研究者用一种势函数下降内点 算法来求解带线性约束的凸规划问题，每次迭代中搜索方向由一个线性方程组解 出，再利用a r m i j o 准则进行线搜索【1 3 】，还有其它使用内椭球算法、预估一校正内 点算法、鞍梯度方法等解线性约束凸规划问题本着能够进一步降低算法复杂度 的目的，我们使用原始对偶路径跟踪内点算法解线性约束凸规划问题，力求设 计完善的算法 二次规划问题的求解是数学规划和工业应用等领域的一个重要课题，同时也 是解一般非线性规划问题的序列二次规划算法的关键求解二次规划问题的早期 技术是利用解线性规划问题的单纯形方法求解二次规划问题的k k t 最优性必要 条件【2 4 】，这类算法比较直观，但在处理不等式约束时，松弛变量的引入很容易 导致求解过程的明显减慢有效集策略是求解二次规划问题的另一类主要技术， 这类方法一般是稳定的，但随着问题中大量不等式约束的出现，其收敛速度越来 越低【1 5 】近年来，许多学者对二次规划问题的内点算法进行了研究，提出了许 多有效算法【2 1 ，2 3 1 本文使用基于核函数的原始对偶路径跟踪内点算法解凸二 次规划问题，并得到较好的大步算法复杂性为 d ( 、，佤l o g nz 0 9 ( 譬) ) 1 1 2 研究背景 线性规划作为数学规划的重要分支，历史比较悠久，理论也较为成熟线性 规划的思想最早可以追溯至1 9 3 9 年苏联数学家、经济学家在鬣生产组合与计划中 的数学方法一书中提出了类似线性规划的模型来解决下料问题和运输问题。并 给出了”解决乘数法”的求解方法 线性规划问题是在对决策变量施加一组线性等式、不等式及符号的约束下，求 决策变量的线性目标函数的最优化( 极大化或者极小化) 问题自1 9 4 9 年d a n t z i n g 提出了著名的求解线性规划问题的有效方法一单纯形方法后，线性规划理论得到不 断丰富和发展，线性规划模型应用到各个领域，其包含的数学理论和计算机技术引 起众多研究者的浓厚兴趣1 9 7 9 年，k h a n c h i a n 证明了s h o r 、j u d i n 和n e m i r o v s k i j 的”椭球法”具有多项式复杂性，椭球算法与单纯形方法是根本不同的，在理论 上它优于单纯形方法单纯形法采用指数的逐次迭代去寻找一个最优解，而椭球 法则是在一个多项式的时间界限内去寻找线性规划问题的最优解但遗憾的是椭 球法理论上的优越性并不能在实践应用中得以实现 直至1 9 8 4 年，k a r m a r k a r 的”投影尺度法”使解线性规划问题出现了真正 的突破，并促使这一领域出现激动人心的发展这种新的算法不仅在理论上优越 于单纯形方法，而且也显示出对求解大规模实际问题的巨大潜力，投影尺度法是 从可行域的内部逼近问题的一个最优解，且算法的迭代次数并不依赖于问题的规 模受k a r m a r k a r 的启发，内点算法得到飞快发展，并由此衍生出各种各样的内点 方法 在2 0 世纪九十年代，内点算法的理论已经发展的比较成熟，在此期间数学家 n e s t e r o v ，n e m i r o v s k i i 及t o d d 做出了主要贡献在【4 5 ，4 6 1 中提出了s e l f - c o n c o r d a n t f u n c t i o n s ，s e l f - s c a l e dc o n e s 的概念，把基于对数障碍函数的内点算法推广为更为 复杂的问题，比如。二次凸规划( q u a d r a t i cc o n v e xo p t i m i z a t i o n ) 、非线性凸规 划( n o n l i n e a rc o n v e xo p t i m i z a t i o n ) 、非线性互补问题( n o n l 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 s ) 等，特别地推广到半正定规划( s e m i d e f i n i t eo p t i m i z a t i o n ) 和二阶锥规划 ( s e c o n d - o r d e rc o n eo p t i m i z a t i o n ) 从k a r m a r k a r 提出的内点算法至今，内点算法已 取得丰硕成果 在各种内点算法中，原始对偶内点算法是一类最为有效和最为广泛应用的 内点方法，其中原始对偶路径跟踪方法的发展尤其引人注目该算法充分利用 原问题和对偶问题的信息，从可行域内部，沿着一条通向最优解的解析路径，经 过数次迭代，达到原问题的最优解，且该解为其对偶问题的最优解在原始对 偶内点算法中，根据迭代参数的不同设置，又可分为大步校正方法( l a r g e - u p d a t e m e t h o d ) 和小步校正方法( s m a l l - u p d a t em e t h o d ) 理论上，大步校正方法的算法复 杂性比小步校正方法要差，但在实际应用中，小步校正方法远没有大步校正方法 有效，这也是当今许多研究者致力解决的一个问题 1 1 3 最优性条件 由于凸规划是一类重要的约束最优化问题，尤其在理论上有其特殊的作用， 对一般的凸规划问题，其一般形式为 r a i n ，( z ) ，z i 护 s t 9 ( z ) 之0 ，( 1 1 ) h ( x ) = 0 ， 其中，g ( x ) = ! ( 9 l ( z ) ，目1 2 ( z ) ，1 7 n ( z ) ) t ，h ( x ) = ( 1 ( z ) ，1 2 ( z ) ，l ( z ) ) ，f ( x ) ，g i ( z ) ( i = 1 ，2 ，l n ) ， b ( z ) 0 = 1 2 ，1 ) 均为定义在z l p 上的实值函数 定义1 1 1 对于问题( 1 1 ) ，若，( z ) ，乜 ) a = 1 ，2 ，z ) 是开凸集s 上的凸函 数，职( z ) “= l ，2 ，7 , ) 是线性函数，则问题( 1 1 ) 称为凸规划特别的，若，( z ) 还是开凸集s 上的严格凸函数，则称问题( 1 1 ) 是一个严格凸规划问题 凸规划问题较一般非线性规划重要，是因为它具有下面的性质 定理1 1 2 凸规划问题的任何局部极小点都是全局极小点，且极小点的集合 为凸集 推论1 1 3 若凸规划问题为严格凸规划，则其全局极小点( 如果存在的话) 是 唯一的 从上述定理及推论，我们不难看出凸规划问题具有的优势，对于这样的规划问题， 我们均可以使用内点算法去求解 定理1 1 4 设，( z ) 是定义在凸集s 上的可徽凸函数，若存在点矿s ，使得 对于所有的点z s ，都有w ( x + ) t 扛一矿) 0 ，则矿是，( z ) 在凸集s 上的全局 极小点 定理1 1 5 若矿为定义在凸集s 上的可徽凸函数，0 ) 的一个平稳点，则矿 也是，( z ) 在凸集s 上的全局极小点 一般讲凸函数的全局极小点不一定是唯一的点，但若，( z ) 是定义在凸集s 上的严 格凸函数，则全局极小点是唯一的关于上面两个定理的证明可以参考【4 9 1 考虑线性约束凸规划问题- ( l c c p )m i n f ( x ) ：a x = b ，z o ) 其k k t 最优性条件为t 定理1 1 6 矿为问题( l c c p ) 的最优解的充要条件为 ( 1 ) 矿满足约束条件a x + = b ，矿0 ( 2 ) 存在y r m ，矿r n 使得( 矿，y ，矿) 满足v ，( 矿) 一a t y 一8 = 0 ，s 0 对于仅含等式约束的极值问题t 。j ： 其中z i p ，l 0 成立，则矿为问题( 1 2 ) 的严格局部最优解 该定理给出了判断所求解是否为最优解的具体方法凹，5 1 j 1 2 原始一对偶内点算法的思想 自1 9 8 4 年k a r m a r k a r 内点算法发现以来，内点算法得到飞速的发展内点算 法思想是从问题的可行域内选取一个初始可行点，然后根据一定的迭代规则在可 行域内部生成一系列收敛于问题最优解的点列，并要求整个迭代过程在可行域内 部进行根据搜索方向的不同设置，内点算法可以分为 射影变换法( t h ep r o j e c t i v em e t h o d s ) 射影变换法的代表性算法是k a r m a r k a r 算法每步迭代，先做射影变换， 将迭代点变换到可行域的中心，然后在中心对势函数使用最速下降步骤该迭 代次数的复杂性是o ( n l ) ，其中n 为变量数目。l 为问题的输入数据在编译成 二进制码的长度，通常称为问题的规模、 仿射变换法( t h ea f l i n es c a l i n gm e t h o d s ) t 仿设变换法是在k a r m a r k a r 的研究出现之后，作为他的算法的一个自然简 化最近，m o n t e r i o r 和a d l e r 等提出了一种原始对偶仿射变换内点算法，在 一定的条件下，迭代次数的复杂性为o ( n l 2 ) 路径跟踪法( t h ep a t hf o l l o w i n gm e t h o d s ) 路径跟踪法是在深入研究射影变换法和仿射变换法的基础上发展起来 的”中心路径”( c e n t r a lp a t h ) 的概念最早由h u a r d 和s o n n e v e n d 提出 最近，已将路径跟踪法推广应用到二次凸规划( q u a d r a t i cc o n v e xo p t i m i z a - t i o n ) 问题，且正进一步发展为从复杂性角度研究一般的非线性规划的内点算 法，它又可以分为t 中心方法( t h ec e n t r a lm e t h o d s ) 障碍函数方法( t h eb a r r i e rf u n c t i o nm e t h o d s ) 势下降方法( t h ep o t e n t i a ld e c e n tm e t h o d s ) 原始一对偶方法( t h ep r i m a l - d u a lm e t h o d s ) 在众多的内点算法中，所谓的原始对偶路径跟踪方法( p r i m a l - d u a lp a t h - f o l l o w i n g m e t h o d s ) 的发展尤其引人注目下面我们以线性规划问题为例，介绍原始一对偶 内点算法的基本思想 塑墨生土瀣太堂壅堂亟堂焦硷塞垒 1 2 1 中心路径及搜索方向 考虑线性规划问题的标准形式t ( l p )m t n c ；r z ：a z = b ，z o ) ，( 1 3 ) 及其对偶问题t ( l d )仇毗 6 t 可：，3 ，+ 3 = c ，s 0 ) ，( 1 4 ) 其中a 矽炳，b j p ，c 俨求解原问题( l 尸) 及对偶问题( l d ) 的最优解等 价于求解方程组t a z = b ，z 0 ， a t p + s = c ，8 芝0 ，( 1 5 ) z s = 0 其中z 5 表示n 维向量，0 s ) i = z i s i = 0 ，i = 1 ，2 ，n ，它是( l p ) 和( l d ) 的互补条 件事实上，方程组( 1 5 ) 正是原始问题( l p ) 及对偶问题( l d ) 的k k t - 条件为 了确保方程组( 1 5 ) 存在唯一解，我们假设 原问题( l p ) 及对偶问题( l d ) 满足内点条件，即存在( 护，y o ，s o ) 满足t a z o = b ，z o 0 ，a t y 0 + 矗o = c ， s 0 0 约束矩阵a 行满秩，即r a n k c a ) = m 原始对偶内点算法的基本思想就是用参数化的方程z s = 衅代替互补条件z 暑= 0 ， 求解方程组 其中e = ( 1 ，1 ，1 ) ，p 0 由假设内点条件成立及r a n k ( a ) - - m ，我们易知，对于任 意的参数p 0 ，参数方程组( 1 6 ) 存在唯一解，我们把此解记为t ( z ( p ) ，箩( p ) ，s ( p ) ) 称z ( 弘) 是( l p ) 的炒中心，( 秒( p ) ，s ( p ) ) 为( l d ) 的胪中心当p 的取遍所有正实 数，( z ( p ) ，掣( p ) ，s ( p ) ) 形成一条曲线，称之为( l p ) 和( l d ) 的中心路经当p _ 0 ， 中心路径的极限点存在且满足互补条件，该极限点是原始问题( l p ) 和对偶问题 ( l d ) 的最优解 对于任意的p 0 及原始一对偶问题的严格可行解( x ，y 8 ) ，我们引入向量 = 罟，v - i _ 兰， ( 1 7 ) 2 、石，滓v 磊， l 。 田 仉 仉 一 一 z 8 k 岛 肛 = = = z s 溜 a + z r a 显然，当t ，= e 时，可行点( x ，s ) 在抄中心上设障碍函数皿( 移) ，t ，衅+ 是一个凸 函数，且当u = e 时取得极小值皿( e ) = 0 ，所以成立， v 耍( ) = 0 争t ，= e 铮皿( ) = 0 所以，障碍函数皿( t ，) 可以用来度量可行点( x ，s ) 与旷中心( z ( p ) ，s ( p ) ) 的距离用 牛顿法解( 1 6 ) ，并设霉，a y 和s 为( x ，y , s ) 点处的搜索方向，则。，玑a s 满足方 程组t a a x = 0 a t a y + a s = 0 ，( 1 8 ) s a x + z a s = 一p t ，霍( 口) 因为矩阵a 行满秩且满足内点条件，因而该方程组存在唯一解 变换，首先定义尺度搜索方向如和也 如：= 警，也：= 字， 则方程组( 1 8 ) 转化为- 下面做个尺度 ( 1 9 ) a 蟊= 0 ， 铲耖+ d l = 0 ，( 1 1 0 ) 如+ 也= 一v 皿0 ) 其中，五= 丢a y x ，y = d i a g ( v ) ，x = d i a g ( x ) 通过分析容易得到， 如和也是正交的事实上，一方面如属于矩阵五的零空间，另一方面也属 于矩阵a 的行空间 如与d 。的和是障碍函数霍( u ) 的最速下降方向当且仅当( z ，y ，5 ) = ( z ( p ) ，y ( p ) ，s ( p ) ) 时，我们可以得到， 如= d o = 0 营v 霍( u ) = 0 铮u = e 铮皿( ) = 0 当( x ，y 8 ) ( z ( p ) ，爹( p ) ，s ( p ) ) 时，则( z ，秒，a s ) 是非零向量组，以( a x ，a y ，a s ) 为 搜索方向，按照一定的线搜索规则来选取合适的步长口，沿着搜索方向得到新的迭 代点( z + ，s + ) ： z + = z + a a x ，舛= y + a 秒，s + 。s + a a s 经过反复迭代直到可行点( x , y , s ) 充分接近p , - 中- c , - ( z ( p ) ，掣( p ) ，s ( p ) ) 然后进行外迭 代，使p = ( 1 0 ) u ，由方程组( 1 8 ) 求得新的胪中心如此反复进行内迭代和外迭 代，直至对偶间隙小于预先给定的值e ，即n pse ，这时得到的迭代点即为原问题 ( l p ) 和对偶问题( l d ) 的一个e - 解 至鲤墨生上渔太堂堡堂亟堂焦硷塞墨 1 2 2 原始对偶内点算法 下面给出解线性规划问题的原始一对偶内点算法流程其中t( z o ，s o ) 为满足 初始条件的点，r 1 用于控制当前迭代点与中心路径的距离，给出最优解满足 的精度为 0 解线性规划的原始对偶内点算法 i n p u t ： 临界参数7 - 1 ；精度参数e o ； 固定障碍校正参数0 ，0 0 不失一般性，可以设一= s o = e ，求解( l c c p ) 问题及( l c c d ) 问题的最优解等价 于求解下面的方程组t a z = 6 ，z 0 ， a t y + 8 一v f ( x ) = 0 ，s 0 ， ( 2 3 ) 互s = 0 其中z s 表示n 维向量，( x s ) i = 戤如= 0 ，i = l ，2 ，n ，使用原始一对偶内点算法的基 本思想，用z s = p e 替换方程组( 2 3 ) 中的第三个方程，于是考虑下面的方程组， a x = 6 ，z 0 ， a t + s v f ( z ) = 0 ，s 0 ，( 2 4 ) z s2 p e ， 我们注意到方程组( 2 4 ) 中的第二个方程在线性规划中表示为a t y + s = c ，对于 它们不同的细节部分，我们可以参考【4 ，2 s 方程组( 2 4 ) 中的后两个方程均为非 线性方程，通过使用牛顿法可以容易地解出该非线性方程组 由r a n k ( a ) = m 及内点条件成立，对任一p 0 ，系统( 2 4 ) 存在唯一解，记为 扛) ，可( p ) ，s ( p ) ) ，我们称z ( ，1 ) 为( l c c p ) 问题的弘一中心，( ! ，( p ) ，s ( p ) ) 为( l c c d ) 问 题的p 一中- l - 当p 取遍正实数时，p 一申j bz ( p ) 、( 秒( p ) ，s ( p ) ) 分别形成( l c c p ) 问题及( l c c d ) 问题的中心路径当p 趋于0 时，中心路径的极限存在且该极限 值满足互补条件，该极限值即为( l c c p ) 问题及( l c c d ) 问题的最优解 设函数妒( t ) 为定义在f 0 + o 。) 上的实值函数且在( 0 ，+ o o ) 上可微，对于任何 t 0 ，成立不等式妒( t ) 0 和( t ) 0 系统( 2 4 ) 转化为 a x = b ，石0 ， a t 秒+ 3 一v ，( z ) = 0 ，s 0 ， ( 2 5 ) 妒( 罟) = m 采用牛顿法解方程组( 2 5 ) 得到搜索方向( z ，y ，s ) 为。 a a z = 0 ， 塑垒生整太堂堡堂亟堂焦迨塞 ! 墨 a t a y + s v 2 ， ) z = 0 ， ( 2 6 ) 云( 吾) 计x po , x p sa s = 妒( e ) 一妒( 詈) ， 注意到函数f ( x ) 的凸性，因而v 2 ，( z ) 为对称正定矩阵为便于内点算法的分析， 我们引入向量，把x , 8 转化到同一t ，空间，并由此得到尺度搜索方向如和也 一居，如：= 警，扣字 从而，我们可以得到下面的关系式 s a x + x a s = p ( 如+ d o ) ，p 如d o = a x a s 经代数变换，系统( 2 6 ) 进一步转化为下面的方程组。 矾= 0 ， 3 t a y + 也一可气砜= o ， ( 2 7 ) 如+ 以= 加， 其中t7 i ：= 丢a y 一1 x ，可丽：= p v s 一1 v 2 f c x ) t ，s ， 跏：= 氆参箱产，v ：= d i a g ( v ) ， x - - d i a g ( x ) ，s - -