（计算数学专业论文）原始对偶内点fs算法及其全局收敛性.pdf

l l i l llllli i i i i1 111i iii ii y 17 3 2 3 18 苏州大学学位论文使用授权声明 本人完全了解苏州大学关于收集、保存和使用学位论文的规定， 即：学位论文著作权归属苏州大学。本学位论文电子文档的内容和纸 质论文的内容相一致。苏州大学有权向国家图书馆、中国社科院文献 信息情报中心、中国科学技术信息研究所( 含万方数据电子出版社) 、 中国学术期刊( 光盘版) 电子杂志社送交本学位论文的复印件和电子 文档，允许论文被查阅和借阅，可以采用影印、缩印或其他复制手段 保存和汇编学位论文，可以将学位论文的全部或部分内容编入有关数 据库进行检索。 涉密论文口 本学位论文属 在年一月解密后适用本规定。 非涉密论文日 论文作者签名：肇扭日 导师签名：i 袈等l l 一日 原始对偶内点f s 算法及其全局收敛性 中文摘要 中文摘要中又捅要 以过滤方法为代表的无惩罚型方法是近年来非线性规划的研究热点，大量的理论 研究及数值试验表明这类方法不论在理论上还是数值表现上都是非常成功的 内点法是数学规划中的重要算法之一，近几年来正在被逐步推广到非线性规划问 题并被广泛应用到金融、电力等领域在诸多内点算法中原始对偶内点法是最成功的 算法之一，多数成功的内点算法都属于原始对偶内点法的范畴 f s 算法是一种新的无惩罚型方法这种算法设置了一个递减的可行性违反度阈 值f s 序列在迭代过程中，将迭代点的可行性违反度控制在f s 值以内，同时减少目 标函数值数值试验表明这种算法也是比较有效的 本文将f s 算法思想应用于原始对偶内点法，提出原始对偶内点f s ( i p f s ) 算法 新算法具有以下特征： 一、不使用任何形式的罚函数或效益函数； 二、不使用过滤方法中必需的滤子集合： 三、采用原始对偶内点法框架 在合理的假设条件下，文章证明了算法的全局收敛性，并给出了初步的数值试验， 结果表明了算法的有效性 关键词：非线性规划原始对偶内点法无惩罚型方法f s 算法全局收敛性 作 者：邱松强 指导老师：陈中文 a b s t r a c tap r i m a l - - d u a li n t e r i o r - p o i n tf sa l g o r i t h ma n di t sg l o b a lc o n v e r g e n c e a b s tr a c t p e n a l t y - f r e e - t y p em e t h o d s ，s u c ha sf i b e rm e t h o d s ，h a v eb e c o m eo n eo fh o ts p o t s i nt h ef i e l do fn o n l i n e a rp r o g r a m m i n g ag r e a tn u m b e ro fn u m e r i c a le x p e r i m e n t sh a v e s h o w nt h e i ri m p r e s s i n ge f f i c i e n c yo ff i l t e rm e t h o d s i n t e r i o rp o i n tm e t h o d s ( i p m s ) a r eo n eo ft h em o s ti m p o r t a n tc l a s s e so fa l g o r i t h m s i nn o n l i n e a rp r o g r a m m i n g t h e ya r en o w b e i n gg e n e r a l i z e dt on o n l i n e a rp r o g r a m m i n g a n dh a v eb e e na p p l i e di n t om a n yf i e l d ss u c ha sf i a n c ea n dp o w e rs y s t e m o fa l lt h e i t e r i o rp o i n tm e t h o d s ，p r i m a ld u a li n t e r i o rp o i n tm e t h o d s ( p d i p m s ) a r ec o n s i d e r e da s t h em o s ts u c c e s s f u lo n e s f sm e t h o di san e wp e n a l t y - f r e e - t y p em e t h o d t h i sc l a s so fa l g o r i t h m ss e t sa f sv a l u et oc o n t r o lt h ed e g r e eo ff e a s i b i l i t yv i o l a t i o no ft r i a lp o i n t sa n du s e ss o m e t e c h n i q u e st or e d u c et h ev a l u eo fo b j e c t i v ef u n c t i o n i nt h i sp a p e r ，w ep r e s e n ta na l g o r i t h mt h a tc o m b i n e st h ei d e a so ff st e c h n i q u ea n d i n t e r i o rp o i n tf r a m e w o r k t h en e wa l g o r i t h mh a sn oa n yc h o i c eo fp e n a l t yp a r a m e t e r a n dp e n a l t yf u n c t i o n ，a n di td o e sn o tu s et h ef i l t e rt e c h n i q u ee i t h e r w ea n a l y z e t h eg l o b a lc o n v e r g e n c eo ft h em a i na l g o r i t h mu n d e ra p p r o p r i a t ea s s u m p t i o n s t h e p r e l i m i n a r yn u m e r i c a lr e s u l t sa r er e p o r t e d k e y w o r d s ：n o n l i n e a rp r o g r a m m i n g ，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 ，p e n a l t y f r e e - t y p ca l g o r i t h m ，f sa l g o r i t h m ，g l o b a lc o n v e r g e n c e i i w r i t t e nb yq i us o n g q i a n g s u p e r v i s e db yp r o f ic h e nz h o n g w e n 目录 第一章引言1 第二章f s 技术4 第三章原始对偶内点法6 第四章算法描述1 2 第五章中心性和下降性1 6 第六章全局收敛性2 7 第七章数值试验3 6 第八章结论4 0 参考文献4 1 致谢4 4 原始对偶内点f s 算法及其伞局收敛性 第一章引言 第一章引言 考虑如下问题 r a i n ，( z ) ， s t h ( z ) = 0 ， ( 1 1 ) z 0 ， 其中f ( x ) ：胛一r ，h ( z ) ：舻_ ( m n ) 都是二次连续可微函数 原始对偶内点f s ( i p f s ) 算法属于原始对偶内点法范畴内点法产生于线性规划， 是数学规划中一类重要的算法其历史可以追溯到上个世纪4 0 年代，几乎和d a n t z i g 提出著名的单纯形方法产生于同一时代当时包括冯v o ns e 眦a n n x ，h o f f m a n 等 2 】，f r i s c h 3 在内的很多作者提出了从可行域内部进行计算的内点算法但这些算法 需要巨大的计算量，数值上也缺乏稳定性因而都不足以跟单纯形方法相比 直到1 9 8 4 年，k a r m a r k a r 4 】提出了一个著名的内点法算法，文中卢称这种算法计 算具有多项式复杂度，因而计算效率远高于单纯形方法尽管在实际计算中，k a r m a r k a r 的算法一直没达到他所说的高效率，但是这篇文章引发了一个研究内点法的热潮从 那以后，出现了各种各样的内点算法，像仿射尺度内点法、对数障碍函数法、路径跟踪 法、原始对偶内点法等等在所有的内点法算法中，一般都认为原始对偶内点法是其 中最重要也是最有效的算法 原始对偶内点法主要分为路径跟踪算法、势下降算法、不可行路径跟踪法等其 中路径跟踪算法将迭代点严格地限制在中心路径的一个领域内，沿着中心路径达到问 题的解有些路径跟踪算法为保证迭代点不远离中心路径，每次得到的步长都比较短， 因而被称为短步法另一些路径可以得到较长的搜索步长，被称为长步法还有一类算 法采用两个中心邻域，其中一个包含于另一个在计算时，每个偶数步都是从内邻域出 发，到达外邻域，这样的尝试步叫做预测步；在两个预测步之间的尝试步将迭代点从外 邻域拉回内邻域，这样的尝试步叫做校f 步这种算法也因此被叫做预测校正方法，最 1 第一章引言 原始对偶内点f s 算法及其全局收敛性 著名的是m e h r o t r a 的预测校正方法 5 】 势下降法使用和中心路径法相同的方法求尝试步，但它不沿中心路径求迭代点它 用对数势函数来衡量严格可行域内每个点的优劣在每次迭代中都要求势函数值有充 分的下降性这方面的详细论述可参见r c n e g a r 6 ，t o d d 和y o 7 和k o j i m a 等 8 以 及其它相关文献 不可行原始对偶内点法可以认为是长步跟踪算法的变形，它也采用路径跟踪算法， 只是在求尝试步时，允许一定的不可行性比较成功的不可行路径跟踪法有k o j i m a 等 9 ，z h a n g 1 0 等方法 其他重要的原始对偶内点算法还有自对偶方法 1 1 ，自正则方法【1 2 ，1 3 等关于 原始对偶内点法比较全面的论述可见文献 1 4 ，1 5 】 内点法在线性规划和凸规划中已经取得了巨大的成功但在非凸非线性规划中仍 是一个难点困难之一是很难找到理想的效益函数以确保算法的全局收敛性尽管如 此，这方面还是有一些卓有成效的工作，如文献 1 6 ，1 7 ，1 8 ，1 9 】等使用各种效益函数讨 论了非线性规划内点法的全局收敛性 我国的学者也很重视对内点法研究，c h e n 和z h a n g 在文献【2 0 中讨论了一类仿 射尺度信赖域内点算法刘中意在文献【2 1 】中讨论了凸规划的自正则度量原始对偶内 点法余谦等在【2 2 中研究了多项式复杂度的预测校正内点法李洪伟在 2 3 】中较为 系统地介绍了求解非凸规划的同伦内点法的研究进展在应用方面，内点法在电力电 网上的应用受到格外关注，如文献【2 4 ，2 5 等 非线性规划的另一个研究热点是无惩罚型方法这类方法的特点是不使用任何形 式的罚函数或效益函数，其中过滤方法 2 6 】被认为是最为成功的无惩罚型方法过 滤方法的基本思想是使用“滤子”代替罚函数，要求迭代点必须能被滤子所接受( 也 即至少改善可行性和最优性两者之一) 文献【2 7 ，2 8 ，2 9 ，3 0 ，3 1 】等分别将过滤方法与 s l p 方法、s q p 方法、信赖域方法相结合并证明了它们的全局收敛性除了过滤方 法，u l b r i c h 和u l b r i c h 在 3 2 】和c h e n 3 3 也提出了一种基于信赖域方法的无惩罚型方 2 原始对偶内点f s 算法及其全局收敛性第一章引言 法g o u l d 和t o i n t 在 3 4 中提出了t r u s t f u n n e l 算法这些方法也是比较成功的无 惩罚型方法 受过滤方法的思想启发，q i u 和c h e n 在 3 5 中提出了求解等式约束非线性规划 问题 m i nm ) ， ( 1 2 ) s t h ( x ) = 0 的f s 算法f s 算法设置了一个递减的可行性违反度阈值f s 序列在迭代过程中将 迭代点的可行性违反度i i h ( x ) l i 控制在f s 值以内，同时运用某种方法( 如信赖域方法) 寻求。个“足够好”的新迭代点，然后减小f s 值如此循环，直至得到稳定点同过滤 方法类似，在可行性违反度大于f s 值或相比最优性而言过大时，也调用可行性恢复算 法来改善可行性文 3 5 证明了算法的全局收敛性并给出了数值试验结果 自从无惩罚型方法出现后，非线性规划内点法缺乏合适的效益函数这。问题得以 被规避最近已经有一些研究人员将过滤思想应用于内点法，得到一些内点过滤算法， 如文献【3 0 ，3 1 ，3 6 ，3 7 ，3 8 ，4 1 】，这些算法的特点是结合内点法和过滤方法，因而f i 需要 使用罚函数，并取得了很好的理沦和数值结果但内点法与其它无惩罚型方法结合的 成果尚未见到本文以【3 5 ，3 7 ，3 8 为主要参考文献，结合f s 技术和原始对偶内点法， 提出原始对偶内点f s 算法，算法不需要使用罚函数也不需要使用过滤方法中必需的 “滤子” 本文的结构如下，第二，三章简单介绍f s 技术和原始对偶内点法的框架第四章 给出原始对偶内点f s 算法的详细表述第五章给出了有关尝试步的中心性和下降性 的几个结果第六章证明算法的定义和全局收敛性第七章给出数值试验结果 本文使用的符号说明：文中以下标k 代表在第k 个迭代点z 奄处的相关量的取值， 如用 代表f ( x 七) ，用饥代表h ( x k ) 等，用v 厂( z ) ，v h ( x ) 分别表示，( z ) ，h ( x ) 的梯 度，其中，v h ( x ) = ( v h l ( x ) ，v h m ) ) ，”l l 表示e u c l i d 范数 3 第二章f s 技术原始对偶内点f s 算法及其全局收敛性 第二章f s 技术 首先，我们通过求解( 1 2 ) 的信赖域f s 算法来说明f s 技术的基本思想 信赖域f s 技术是迭代算法设当前迭代点为，当前可行性违反度阈值为f 瓯 我们把寻求新迭代点的循环分为f - 型循环和h 型循环两大类前者的主要目标是减 小目标函数值，后者则着力改善可行性在f - 型循环中，我们要求迭代点的可行性违 反度不大于f s 值同时为了兼顾可行性，我们只在最优性相比可行性而言“不太好”， 即迭代点的最优性尺度与可行性违反度比值大于某一个正常数时才进行f - 型循环也 就是当 i i h , , i i f & 且j i z 。t 鲰i i 竹l i 饥l i ，( 竹( 0 ，1 ) )( 2 1 ) 时，算法进入f - 型循环，其中磊的列向量是v h ( x k ) t 的零空间的一个标准正交基， 矶= w ( x k ) ，ii 饥ii ，ii 刃鲰i | 是常用的衡量迭代点的可行性违反度和最优性的尺度这 时我们先求解如下法向子问题 m i n 批堋矽咿+ 掣s 川2 ， ( 2 2 ) s t ， l 妒l l 知， 其中厶知型k 七m i n l ，即2 - ，七为信赖域半径，即 o ，c ，p ( o ，1 ) ，( 1 ，2 ) 为 常数设s 嚣是( 2 2 ) 的解接下来求解切向子问题 m i n 吼( s 嚣+ s 。) = 9 舌( s 譬+ s 。) + 互1 ( s 嚣+ s 。) t 鼠( s 嚣+ s ) ， s t v 礤s k0 ， ( 2 3 ) s | | ， 其中b 七是问题( 1 1 ) 的l a g r a n g e 函数的h e s s e 矩阵的近似对称矩阵设s t 是切向 子问题( 2 3 ) 的解，令8 k = s 嚣+ s i ：如果目标函数的实际下降量 a r e d = ，( z 南) 一f ( x 七+ s ) 4 原始对偶内点f s 算法及其全局收敛性 第二章f s 技术 和预测下降量 以及法向预测下降量 之间满足以下关系 p r e d = 吼( o ) 一q k ( s k ) p r e d 2 = i i h 七1 1 2 一i 十v h s k i l 2 a r e d f j d 矿e d f ，a r e d f , h p r e d h ，p ，讹( o ，1 ) 且i i h ( x k + s k ) l i f 乳( 2 4 ) 则称s k 为成功尝试步，令z 七+ 1 = 矾+ 8 七需要说明的是( 2 4 ) 中第二个不等式是不可 缺少的，它保证了a r e d f 非负这个条件也可换成一个略强些的条件 p r e d 矿e d 2 当在某个迭代点处有l i 召乃i l 0 ，呱，p ( 0 ，1 ) 为此，我们令 a 啪，= 皿n 1 ，赢卜c ，= 血n ，龠) 9 ， 这样我们就有 、 i i s ( ) l l = i i q ”( ) s n + ( ) s 。l i li s ”( ) s ”i i + ii s 。( ) s 。i 厶4 - a 2 a h - 型循环中步长的确定方法在下章中介绍 为了简便起见，我们记 伽=(三)，伽c，=(兰 =伽+乜”c，扩+c， s i a ) = a “( ) 矿+ q 。( ) s ， p ( ) = 兰( 型t 三t 坐2 ， 我们再介绍三个在算法中起着非常重要作用的量，它们分别是 o g ( w ) = f ( x ) + c p ，o h ( 叫) = l i h ( = ) 1 1 2 和p l ( 叫) = i i v z l ( w ) l l ， 其中c 是某个正常数，其取值将在下文确定这三个量中，前两个量包含了算法需要减 小的i 大目标：函数值、互补度和可行性违反度第i 个量表示l a g r a n g e 函数的梯度 和0 的距离，是衡量一个点是否是稳定点( k k t 点) 的一个重要指标 为了使迭代点远离可行域边界并保证全局收敛性，很多原始对偶内点算法都采用 路径跟踪方法一般地，称 咒= 叫：v z l ( w ) = 0 ，h ( x ) = 0 ，x u = p e ，( z ，) o 】 为中心路径路径跟踪算法将迭代点限制在中心路径的一个邻域( 称为中心邻域) 内， 沿中心邻域计算新迭代点，直至终止条件满足常见的中心邻域有 人尼( 口) = w ：v z l ( w ) = 0 ， ( z ) = 0 ，l x u p e i l 2 p 肛，( z ，) 0 ，0 ( 0 ，1 ) ) ， 8 原始对偶内点f s 算法及其全局收敛性第三章原始对偶内点法 和 人乞( p ) = 硼：v z l ( w ) = 0 ，h ( x ) = 0 ，1 1 x 一p e i l o 。护p ，( z ，) 0 ，矽( 0 ，1 ) ) 人l ( 7 ) = w ：v 霉l ( w ) = 0 ，h ( z ) = o ，x 7 p e ，( z ，) 0 ，7e ( o ；1 ) ) 注意到上述的中心邻域要求迭代点可行，这在非线性规划中是很难做到的所以在非 线性规划中常采用不可行内点法将迭代点限制在如下中心邻域内 1 4 ，1 7 人厂( 7 ，m ) = w ：矿( 叫) + 萨( 埘) m 肛，x 一y 妒，( z ，) o ，7e ( o ，1 ) ，m 0 ) 在内点过滤方法f 3 7 ，3 8 】中，这种中心邻域策略已被证明是十分有效的这罩的条件 口h ( 硼) + 口l ( 伽) m p 是为了控制可行性和稳定性当弘_ 0 时，叫趋向k k t 点由于f s 算法已经对可行 性违反度作了限制，所以我们将该条件放宽为 萨( 叫) m p 即定义中心邻域为 ( 7 ，m ) = 叫：口l ( 伽) m p ，x 二， t p e ，( z ，) o ，7e ( o ，1 ) ，m o 下文我们将证明，在本文的尝试步取法下，通过缩小，可以将迭代点都限制在这 个放宽的中心邻域( 为简便，下文仍称之为中心邻域) 内即若w ( ，y ，m ) ，则充 分小时，叫( ) 也在( 7 ，m ) 内同时它可以保证算法的全局收敛性 与信赖域方法类似，我们定义可行性违反度铲的预测下降量和实际下降量 p r e d h ( a ) = ( z ) i1 2 一ii h ( x ) + v ( z ) t 8 。( a ) i1 2 ， a r e d ( ) = 驴( 训) 一钞( 伽( ) ) 以及函数伊的预测下降量和实际下降量 p r e d g ( a ) = 一v f ( z ) t 8 x ( ) c 兰尘丛垒羔掣， a r e d g ( a ) = 伊( ) 一伊( 加( ) ) 我们通过实际下降量和预测下降量来确定尝试步是否可接受，为此有如下引理 9 第三章原始对偶内点法 原始对偶内点f s 算法及其全局收敛性 引理3 1 设，h 均二阶连续可导且x 属于有界闭凸集q ，则存在常数d ， 坞d 0 使得 i a r e d ( ) 1 w e d ( ) i 螈d 2 ， ( 3 1 0 ) i a r e d g ( a ) 一p r e d g ( a ) i m g d 2 ( 3 1 1 ) 证明：根据t a y l o r 展开式，注意到o h ( 叫) 只与z 有关，有 驴( 叫( ) ) = o h ( w ) + v 。萨( 叫) t 8 x ( ) + 丢8 z ( ) t v ：。0 h ( 西) s 。( ) ， 其中，西= w + t s ( a ) ，丁( 0 ，1 ) 又驴( 伽) 关于z 的梯度和h e s s e 矩阵分别是 v z p w ) = v z ( ( z ) t ( z ) ) = 2 v 。九( z ) ( 茁) ， v ：。0 ( 叫) = 2 ( v z h i ( x ) v 。h i ( z ) r + ( z ) v ：。h t ( z ) ) i = l 故 铲( 叫( ) ) = 轳( 伽) + v 。0 ( 叫) t ( ) + s 。( ) t v 。2 铲( 西) ( ) = ll h ( x ) + v 九( z ) t 8 z ( a ) i1 2 慨( 酽( 姜1 ( 珊舡刚矿地v ： ( 驴v 册t 卜) i = = ( z ) + v h ( x ) t 8 z ( n ) l1 2 + ( ) t ( v 玩( 孟) v 吃( 舅) t + 玩( 孟) v ：z 吃( 孟) 一v h t ( z ) v ) t ) s z ( ) 那么 1 a r e d ( ) 一p r e d ( ) i = 1 0 h ( 叫) 一o h ( 伽( ) ) 一( i i h ( z ) 1 1 2 一l i h ( x ) + v h ( x ) t 8 z ( ) 1 1 2 ) = ii i h ( z + 8 x ( ) ) ij 2 一i l ( z ) + v 允( z ) 丁s 。( 9 1 1 2 i = l s 。( ) te ( w ( 童) v 鬼 ) t + ( 孟) v ：。h t ( 童) 一v h t ( x ) v h t ( z ) t ) ( ) i = 1 | | 乏二( v ( 奎) v ( 孟) ? + 吃( 矛) v ：z h t ( 童) 一v h t ( z ) v 见( z ) t ) 1 1 1 1 s 。( a ) 1 1 2 l ：= 1 m h d a 2 ， 1 0 原始对偶内点f s 算法及其全局收敛性 第三章原始对偶内点法 其中螈d 是i l 伍m ，( v h ( 圣) v 玩( 量) t + 吃( 岔) v z z 玩( 孟) 一v h i ( x ) v h t ( z ) t ) l | 在q 上的上 界 再考虑( 3 1 1 ) ，由于 。 伊( 叫( ) ) = ，( z + s 。( ) ) + c 鱼2 上当墨全2 2 三删 = ，( z ) + v f ( z ) t s z ( ) + 互1 s z ( ) r v ：z ，( 岔) 如( ) + c x t b , + x t 8 ( ) + l , t 8 。( ) + 8 x ( ) r s p ( ) = 伊+ v f ( z ) t s 。( ) + c 兰! 丛垒掣 + 丢s z ( ) 丁v 。2 。，( 岔) s 。( ) 十c 垒学， 其中，岔= z + 丁s 。( ) ，7 i ( 0 ，1 ) 故而， = l 伊一p g ( 叫( ) ) 一( 一v ，( z ) t ( ) 一c 三二兰垒垒掣) = l 丢s z ( ) 丁v 。2 z ， ) s 。( ) + c 鱼学i l l l v ：z f ( 5 ：) 1 1 l s 。( a ) 1 1 2 + 丢i i s 。( a ) i i i i s p ( a ) i i 婢啊乙施) + 等) 2 ( 2 m y + 等) 2 ：m n i 厶2 其中，坞d = ( 2 吩+ 4 c n ) ，岣为i l v ：z f ( x ) l i 在q 上的上界证牛 第四章算法描述 原始对偶内点f s 算法及其全局收敛性 第四章算法描述 综合f s 方法和原始对偶内点法的基本思想，我们给出原始对偶内点f s ( i p f s ) 算 法的基本框架在i p f s 算法中，我们设置f s 值为铲( 叫) 的阈值，在f s 值允许范围 内减小伊( 叫) 设当前迭代点为w k ，则当 萨( 训) + 肌竹礁且礁f 鼠，竹( 0 ，1 ) ( 4 1 ) 时，算法进入，一型循环，j 习y a - 章中的原始对偶内点法计算尝试点叫七( ) 若 o r e ( ) j d 矿e 耀( ) ，口r e ( ) 7 印r e 以( ) ，0 h ( 叫k ( ) ) f 鼠， ( 4 2 ) 其中p ，伽( 0 ，1 ) ，则认为w 知( ) 为成功迭代点令叫七+ 1 = 叫凫( ) 否则减小a 若 ( 4 1 ) 不成立，算法进入h 一型循环，调用可行性恢复程序详细的i p f s 算法如下 步0 。选择0 o ，a 。舣 。i 。 0 选 定初始点( 黝，峋) 0 和l a g r a n g e 乘子估计a o 选择7 ( 0 ，1 ) 使得赫峋 p o e 选 择m 0 使得萨( 叫o ) m 肋计算c = 4 n 2 口2 ( ( 1 一盯) ，y 2 ) 令k ：= 0 且 盛嚣 步1 若礁+ 礁+ 鲰= 0 ，则算法终止，输出结果 步2 若( 4 1 ) 不成立，转步9 步3 令：= 笙计算s ： ，s 2 步4 由( 3 9 ) 计算q 嚣( ) ，口2 ( ) 步5 计算路使得对v ( 0 ，a k 】都有伽( ) ( 7 ，m ) 步6 若( 4 2 ) 成立，则w k + l = 伽七( ) ，舭+ l = m ( ) ，选择合适的釜+ 1 ( 见注3 ) 原始对偶内点f s 算法及其全局收敛性 第四章算法描述 步7 若萨w 七+ 1 ) + p 七+ 1 p 2 ， 其中，纯( p l ，1 ) ，埋= a r e 4 ( a ) p r c 4 ( a ) 算法框架可参见下页i p f s 算法流程图 下面讨论可行性恢复算法跟文【3 8 类似，我们用原始对偶内点法进行可行性恢 复可行性恢复算法的目的是减小o h ( ) = ( z ) 悒直至满足f - 型循环的条件的迭代 事实上，法方向s ：就是纱( 伽) 的下降方向这是由于根据法向方程组( 3 7 ) ，我们 v z 0 6 ( 叫) t 8 “x = 2 ( v ( z ) ( z ) ) t s 。n = 2 h ( x ) 丁v ( z ) r s 。n = 一2 p h ( 硼) 0 使得i i 髟p ( 叫) _ 1 i | a f 假设a 中，( a 1 ) ，( a 2 ) ，( a 4 ) 在 3 7 ，3 8 】中用到，( a 3 ) 在 3 8 】用到由假设a 可知， 存在常数，坳，m h 0 使得i i e “| i ，l i v f ( x ) l i 地，i i h ( x ) l i 慨 我们简要说明一下这些假设条件的合理性假设条件( a 1 ) ，( a 2 ) 是通常的假设 假设条件( a 3 ) 较s q p 等方法中常用的v ：z l ( w ) 在v h ( x ) t 的零空间上半正定的假 设条件要弱，耷内点法中x 0 ，v 0 ，从而x 1 是有意义的另外，关于( 叫) 的 非奇异性讨论如下在任意点伽处，若存在西t = ( 畲t ，又丁，矿) 使得( 叫) t z = 0 ，则 v ：三篡：j p)v0(z)一0，(兰)=0v 0x v ( z ) t| l 又l2 jidj 篡y 唧肛州蛳_ 0 ， 2 t ( v ：。l ( x ，入，) + x 一1 y ) 岔= 0 根据( a 3 ) 知，圣= 0 ，从而v 危( z ) 又= 0 只要v h ( x ) 列满秩( 比如，l i c q 规格成立) ， 1 6 原始对偶内点f s 算法及其全局收敛性 第五章中心性和下降性 就有又= 0 再根据x d + y 圣= 0 得痧= 0 从而面= 0 ，这说明x 0 ，v 0 时， ( a 3 ) 隐含e 。可逆 如果在k k t 点w 处某些分量z ：等于0 ，那么内点法不会在有限步内产生稳定 点，我们希望它至少有一个聚点是k k t 点，一般我们用反证法来证明其全局收敛性， 所以在给定误差的条件下，我们是在m i n i x l ，耽) 大于某一正常数e 的情况下研究的， 再结合条件( a 1 ) ，假设( a 4 ) 中要求群肛( 埘) 可逆而且i | e “( 叫) 一1 i l g f 是合理的 下面证明，算法通过缩减，可以将新迭代点控制在拟中心邻域内为此需要证明 如下几个引理 则 引理5 1存在常数地 0 ，对任意a 0 ，有 9 l ( 叫( ) ) ( 1 一口。( ) ) 萨( 伽) + 地2 ( 5 1 ) 证明：设q 是v ：。l ( w ) 的l i p s c h i t z 常数，m l 2 c l 由( 3 8 ) 知 v ：枷三( 叫) t s ( ) = 一q 。( ) v 。( 叫) 口l ( 叫( ) ) = ii v z l ( 训( ) ) 啦蛾筠筌扎：捌训q 舭刮 1 7 第五章中心性和下降性原始对偶内点f s 算法及其全局收敛性 引理5 2 对任意a 0 及i = 1 ，2 ，佗，都有 翰( ) 耽( ) ( 1 一( ) ) 耽阮+ q ( ) 盯p + 4 a 2 ， 如( ) 珑( ) ( 1 一o t t ( ) ) 鼢耽+ 0 ( ) 盯p 一4 a 2 ， x ( a m a ) x v a 。( ) ( x 一a # e ) + 4 a 2 e ， x ( a m a ) x v a 。( ) ( x 一a p e ) 一4 a 2 e ， 其中向量不等式是指对应分量的不等式成立 证明：由法向方程( 3 7 ) 和切向方程( 3 8 ) 得 翰( ) 耽( ) = ( 翰+ o t n ( ) s + ( ) s ：；) ( 耽+ o t n ( ) s 琵+ a ( ) s 复) ( 5 2 ) ( 5 3 ) ( 5 4 ) ( 5 5 ) 原始对偶内点f s 算法及其全局收敛性第五章中心性和下降性 又 则 由( 5 6 ) ，( 5 7 ) 知， 又 x v a u e l l 2 = ( 础) 2 2 a # 啪+ n o 2 p 2 ( 喜z ；玩) 2 2 n 盯p 。+ n 盯。p z = n 2 1 t 2 一n ( 2 a 一0 2 ) 肛2 x v 一口肛e i | p 、石万= 弋互了二了而竹p ( 5 7 ) 咿| | c i f ( m + 佗) p 另一方面，由切向方程组( 3 8 ) 知 从而， x v a t t e l l l l 髟“i i i i s l | c f l l s 。| | x v o p e l i m a x ( x i u i ) 一盯p ( 1 一仃) p 1 t 1 学 ( 5 8 ) ( 5 9 ) 综合( 5 8 ) ，( 5 9 ) ，引理得证 再考虑法方向8 n ，根据法向方程组( 3 7 ) 和假设条件a ，我们不难得到如下结论 簇州i i i i 砸 s”=一cf：p，一1(詈，) 第五章中心性和下降性原始对偶内点f s 算法及其全局收敛性 两边取范数得， s 竹忙i i ( ) 一1 i i i i h ( z ) l l o f 佰= m h v 何 另一方面，据法向方程组( 3 7 ) ，我们有 和“* ， 令 一曲 v 匝4 + 4 7 ，一) i 则根据( ) 的定义及引理5 3 知，当0 a ( p ) 时， ( 1 一c x t ( ) ) ，y p e + d x t ( ) 盯p e 一4 a 2 e ( 1 一q 。( ) ) 7 p e + ，y 口( x ) a # e + 4 - y a 2 e ( 5 1 2 ) 由( 5 2 ) 得 7 舭) e = ，y 半幽e ( 1 一a 2 ( ) ) 一y p e + 7 a ( ) 仃p e + 4 7 a 2 e ( 5 1 3 ) 2 0 原始对偶内点f s 算法及其全局收敛性 第五章中心性和下降性 由( 5 5 ) ，( 5 1 0 ) 可知 x ( ) ( ) ( 1 一& ( ) ) x + c t t ( a ) c r i t e 一4 a 2 e ( 5 1 4 ) 之( 1 一a 。( a ) ) 3 , i t e + q 。( a ) 盯i t e 一4 2 e 于是，由( 5 1 2 ) 一( 5 1 4 ) 知， x ( ) 王，( ) ，y p ( ) e ( 5 1 5 ) 进一步可以证明只要 0 m i n l l s 。i i ，) 繇( i t )( 5 1 6 ) 成立，( 5 1 5 ) 就成立事实上，当0 a i | s f | | 时，( 5 1 6 ) 等价于0 a ( p ) ，故此 时( 5 1 5 ) 成立当i | s l i 时，口。( ) = 1 ，w ( a ) = w ( i s 。i i ) 则依据前面的证明可知 0 i i s 。i i 时，( 5 1 5 ) 成立 令 ( 1 一，y ) 盯 i t l2 虿再巍瓦茅獗了萨 若i t 厨1 ，则取 6 ( i t ) = m i n 厮一) 当0 a ( i t ) 时，有0 m i n a ，l l s i i ( p ) 若p 口l ，则 厮 d 器 由引理5 3 ， ( 1 一，y ) 口 = - _ _ i _ _ _ - - _ _ _ _ - _ _ _ - _ _ _ _ _ _ _ _ _ _ _ - _ _ _ 一 ( 4 + 4 ，y ) o f ( m + n ) + n 1 同样有0 m i n a ，i i i 繇( p ) 这说明，只要 。 两最蔫丽d 陀= f 。- 。p 2 1 = 繇( 弘) 第五章中心性和下降性 原始对偶内点f s 算法及其全局收敛性 成立，( 5 1 6 ) 就成立，从而( 5 1 5 ) 成立 再取 繇c 萨+ m i n 则0 a ( p ) 时， ，而蒜4 m ) c , f ( m ) ( 死+ n ) f 。 m ( 1 一q 。( ) ) p + m l a 2 m ( 1 一( ) ) p + m a 。( ) 盯p 一4 m a 2 由引理5 1 ，引理5 2 及( 5 1 1 ) 知，当0 a 鼹( p ) 时， 0 l ( 伽( ) ) m p ( ) ( 5 1 7 ) 类似地，可以进一步证明 。 面而箍丽而竺砼 时，( 5 1 7 ) 成立从而当0 一i i q i 1 2 证明：由矩阵2 - 范数定义知，i i a i i = a 1 任取q r n ， q i l 2 i i a l l a i l a l l a - l ， 其中，i i q i i a = ( a t a a ) m 将上式两边平方，得 。 i i , 1 1 1 4 ( a t a _ 1 a ) ( q t a q ) ( a t a _ 1 q ) ( n 1 q t 口) = i i a i i l i q l i 2 ( q t a - 1 n ) 由此得证 引理5 8 若w ( ，y ，m ) ，则存在常数心，蜥 0 使得 证明：由定义， p r e d g ( a ) o l 2 ( ) p m 够l l a n ( ) s ：1 1 ( 5 1 9 ) 删( ) ：一v f ( 矿以) _ c 鱼学 = 一v f ( z ) r s 。( ) 一c 兰! 型兰攀+ 丢a 2 ( ) s 罗x 一1 y s ： 一扣) s 磐唧s ： ( 5 2 0 ) 第五章中心性和下降性 原始对偶内点f s 算法及其全局收敛性 利用( 3 7 ) ，( 3 8 ) 有 一z t 8 p ( ) 一v t 8 。( ) = 一x t ( 口”( ) s 吕+ ( ) s ：) 一z ，t ( q n ( ) s ：+ ( ) s ：) = 一q “( ) e t ( x s 苗+ y s ：) 一( ) e t ( x s ：+ y s ：) = n q ( ) ( 1 一盯) p 故 一兰二垒垒羔! 型：q t ( ) ( 1 一口) 卢 (521)7 - - ，。、， 又 一v ，( z ) t 8 。( i x ) = 一v f ( x ) t ( a ”( ) s ：+ o t t ( ) s ：) 一q 。( ) v ，( z ) t s 霉t l i v 厂( z ) l q ”( ) s 引i 一( ) v 厂( z ) t s z t 一朋孑i i q ”( ) s ：i i ，( 5 2 2 ) 其中m a 为i v f ( x ) l i 在q 上的上界由v 。l ( w ) = w ( x ) + v h ( x ) a 一知v f ( x ) = v 。l ( w ) 一v h ( x ) a + y 再根据切向方程组( 3 8 ) 得 一v ，( z ) t s 。t = 一( v 。l ( w ) 一v h ( x ) a +