（系统分析与集成专业论文）解半正定规划问题的基于参数化对数障碍函数的内点算法.pdf

摘要 解线性规划问题的具有多项式时间内点算法已显示出强大的功效和广泛的应 用，研究者们试图将它推广到凸非线性规划问题上去从上世纪九十年代中期到 现在，研究的热点集中于两种凸非线性规划模型，即半正定规划和二阶锥规划问 题具有多项式时间内点算法主要应用于解大规模优化问题，并可分析算法的计 算复杂性 在众多的内点算法中，基于对数( 1 0 9 a r i t h m ) 障碍函数的内点算法是一类最为 有效和最为广泛应用的内点算法在已有的基于障碍函数的原始对偶内点算法 的研究工作中，对障碍函数的研究基本局限于对障碍函数的障碍性的分析，很少 考虑障碍函数中所含参数对障碍性的影响，也没有对参数作具体的分析然而， 有些数值结果显示，障碍函数中所含参数对障碍性起很大的作用，比如有限障碍 函数就是一个典型的例子【5 】 在本文，我们所做的工作集中在以下三个方面首先。我们考虑对一般障碍 函数的参数化问题，其目的是为了扩大障碍函数的种类我们研究了参数化障碍 函数和它的的核函数的性质，以及参数化核函数的导数性质，比较了参数化核函 数的各阶导数并分析了参数和算法复杂性的关系进一步我们给出了参数化对 数障碍函数，并根据参数化对数障碍函数设计了解半正定规划问题的原始对偶 内点算法，应用参数化对数障碍函数的性质分析了算法的复杂性，得到了一个理 论迭代界，这个迭代界与解线性规划问题的算法的迭代界一致最后，我们通过 数值算例阐明参数化对数障碍函数和算法复杂性的关系数值结果表明和基于经 典对数障碍的原始对偶内点算法相比，我们的算法的迭代界与参数的不同取值 有关当参数取某个值时，算法的迭代界比经典的算法好 全文共分五章，在第一章里，我们简单介绍半正定规划问题、原始对偶内点 算法与障碍函数，以及本文的主要工作在第二章里，我们主要讨论了参数化障 碍函数和的参数化核函数的性质，以及参数和算法的关系在第三章，我们给出 了一个基于参数化对数障碍函数的解半正定规划问题的原始一对偶内点算法，分 析了算法的计算复杂性在第四章给出了基于参数化障碍函数原始一内点算法的 线性规划算例和基于参数化对数障碍函数的原始对偶内点算法的半正定规划算 例第五章是结论与展望 关键词；半正定规划，原始一对偶内点算法，对数障碍函数，大步校正方法和小 步校正方法 a b s t r a c t i n t e r i o r - p o i n tm e t h o dh a sb e e no n eo fm o s tp o w e r f u lt o o l sf o rs o l v i n gl i n e a ro p t i - m i z a t i o np r o b l e m i th a sa t t r a c t e dm a n yr e s e a r c h e r st oe x t e n dt or e s e a r c ht ot h ea r e ao f n o n l i n e a rp r o g r a m m i n g ，i n c l u d i n gs e m i d e f i n i t eo p t i m i z a t i o na 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 n ，t w ok i n do fc 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 el a t eo f1 9 9 0 s ，t h et r e m e n d o u s r e s e a r c ha c t i v i t yh a sb e e ns p u r r e db yt h ew i d ea p p l i c a t i o n so fs e m i d e f i n i t eo p t i m i z a t i o n ， t h ed e v e l o p m e n to fe f f i c i e n ti n t e r i o r - p o i n ta l g o r i t h m sf o rs e m e 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 sw e l la st h ed e p t ha n de l e g a n c eo fo p t i m i z a t i o nt h e o r y a m o n g a l le x i t e di n t e r i o r - p o i n ta l g o r i t l n n s ，t h ep r i m a l - d u a ll o g a r i t h m i cb a r r i e ra l g o - r i t h mh a st h ea d v a n t a g et h a ti ti sc o n c e p t u a l l ys i m p l ea n da l s oq u i t ee l e m e n t a r ya n a l y s i s ， i t i sa l s ot h eb a s i so fa 讯d ec i s s so fp o l y n o m i a lt i m ea l g o r i t h m h o w e v e r 。t h em o s to fr e - s e a r c hf o c u s e do nt h eb a r r i e rf u n c t i o ni t s e l f , t h e r ei sn o tm u c hf o rt h ep a r a m e t e ri n v o l v e d ， a l s of o rt h er e l a t i o nb e t w e e nt h ep a r a m e t e ra n dt h ec o m p l e x i t yb o u n do ft h ea l g o r i t h m w en o t e dt h a ts o m en u m e r i c a lr e s u l t ss h o wt h a tt h ep a r a m e t e r sc o u l di n f i n e n tt h eb a r r i e r p r o p e r t yf o rb a r r i e rf u n c t i o n f o re x a m p l e ，t h e 缸b a r r i e ri sat y p i c a le x a m p l e 【5 】 i nt h i st h e s i s ，o u rm a j o rc o n t r i b u t i o n sa r ei nt h r e ea s p e c t s f i r s to fa l l ，w ec o n s i d e r ap a r a m e t e r i z a t i o no fc l a s s i c a lb a r r i e rf u n c t i o n w ea i mt oe n l a r g et h et y p eo fb a r r i e r f u n c t i o n w es t u d yt h ep r o p e r t i e so fp a r a m e t r i ck e r n e lf u n c t i o nw h i c hd e t e r m i n e st h e b a r r i e rf u n c t i o na sw e l la si t sd e r i v a t i v e s ，w ea l s oa n a l y s i st h ei m p a c to ft h ep a r a m e t e r f o rt h ec o m p l e x i t yb o u n do fa l g o r i t h m s e c o n d w ep r e s e n t 觚p r i m a l - d u a li n t e r i o r - p o i n t a l g o r i t h mf o rs o l v i n gs e m e 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 s t h i sa l g o r i t h mi sb a s e do nt h e p a r a m e t r i ck e r n e lf u n c t i o n w ed e r i v et h ec o m p l e x i t yb o u n do fa l g o r i t h ma n dc o n c l u d e t h a tt h eb o u n di st h es a m ea st h a tb a s e do nt h ec l a s s i c a ll o g a r i t h m i cb a r r i e rf u n c t i o ni n l i n e a rc a s e f i n a l l y , t h en u m e r i c a lt e s ti sg i v e nt oe x p l o i tt h er e l a t i o nb e t w e e np a r a m e t e r a n dt h ec o m p l e x i t yb o u n d t h et h e s i si n c l u d e sf i v ec h a p t e r s i nc h a p t e r1 w em a k eab r i e fo v e r v i e wo fs e m i - d e f i n i t ep r o g r a m m i n gp r o b l e m ，p i r 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 ，b a r r i e rf u n c t i o n s i n c h a p t e r2 ，w ef o c u so ns t u d y i n gp a r a m e t r i ck e r n e lf u n c t i o na n dt h er e l a t i o nb e t w e e nt h e p a r a m e t e ra n dt h ec o m p l e x i t yb o u n do fa 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 i n t e r i o rp o i n ta l g o r i t h mb a s e do nt h ep a r a m e t r i cl o g a r i t h m i cb a r r i e rf u n c t i o nf o rs e m i d e f - i n i t eo p t i m i z a t i o n ，i nc h a p t e r4 ，w es h o wt w on u m e r i c a le x a m p l e s o n ei sp r i m a l - d u a l i n t e r i o ra l g o r i t h mb a s e do nt h ek e r n e lf u n c t i o nw i t hp a r a m e t e rf o rl i n e a ro p t i m i z a t i o na n d t h eo t h e ro n ei sf o rs e m i d e f i n i t eo p t i m i z a t i o n t h el a s tc h a p t e rw ec o n c l u d eo u rt h e s i s a n dd i s c u s sr e m a r k s k e y w o r d s ：s e m i d e f i n i t eo 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 o g a r i t h m i c b a r r i e rf u n c t i o n ，l a r g e - a n ds m a l l - u p d a t em e t h o d s 原创性声明 本人声明。所呈交的论文是本人在导师指导下进行的研究工作除了文中特 别加以标注和致谢的地方外，论文不包含其他人已发表或撰写过的研究成果参 与同一工作的其他同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意 签名：黼逝日期：啤6 j f 本论文使用授权说明 本人完全了解上海大学有关保留，使用学位论文的规定，即t 学校有权保留 论文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容 ( 保密的论文在解密后应遵守此规定) 签名偶敞导师签名：匆延勇日期：吵c ，多2 2 0 0 7 年上海大学理学硕士学位论文 1 第一章前言 1 1 半正定规划问题概述 半正定规划是一类求解受约束于仿射集和半正定矩阵锥交集的凸规划问题，早 在二十世纪六十年代，半正定规划问题已经提出 9 】 其原因在于以下几方面，首先， 半正定规划包括许多重要的数学规划问题，如，线性规划( l i n e a rp r o g r a m m i n g ) ， 二次规划( q u a d r a t i cp r o g r a m m i n g ) 、二阶锥优化( 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 ) 及线性互补问题( 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 ) 其次，半正定规划在组合最优 化【1 4 】，【删、机械工程及电子工程【1 0 】， 2 9 】等领域得到广泛的应用最重要原因在 于内点算法在线性规划、二次规划及线性互补问题的巨大成就，激发了内点算法 向半正定规划的推广，并最终成为求解半正定规划问题的有效算法经过近二十 年的发展，半正定规划已经成为数学规划一个重要的领域 在内点算法从线性规划到半正定规划及二次锥规划的推广方面，n e s t e r o v 和 n e m i r o v s k i i 【2 z 做出了奠基性的工作a l i z a d e h 【1 】将半正定规划应用到了组合最 优化中从此半正定规划在理论上和实际应用中都得到了广泛的发展求解半正 定规划问题的内点算法主要有- 对数障碍函数法( l o g a r i t h m i cb a r r i e rm t h o d s ) 对数障碍函数法是根据f r i s h 1 2 1 求解线性规划对数障碍函数法推广而来 其基本思想是，将不等式约束通过障碍参数放进目标函数，从而将有约束问题 转化为无约束问题，或仅有等式约束问题算法中对数障碍函数的作用在于阻 止迭代点离开可行域 f a y b u s o v i c h 首先将此方法用于半正定规划【1 1 】 仿射尺度法( a f f i n e 。s c a l i n gm e t h o d s ) 原始仿射尺度法于k a m a r k a r 的投影算法非常相似，v a n d e r b e i 3 0 】等对投 影算法的改进是原始仿射尺度算法一项重大突破然而对于半正定规划的原 始仿射尺度法却被证明它可能收敛于非最优解1 2 5 】d ek l e r k 等将原始一对偶 仿射尺度法从线性规划推广到半正定规划此方法将半正定规划的原始一对 偶空间仿射到一个椭球上，然后在此椭球上最小化对偶间隙，采用尺度矩阵 p = d 然而，m u r a m a s t s u 和v a n d e r b e i 【2 6 】证明了若尺度矩阵是p = s 或 是p = e 时，原始一对偶仿射尺度法不能用来求解半正定规划 原始对偶势函数方法( p r i m a l - d u a lp o t e n t i a lr e d u c t i o nm e t h o d s ) 该方法主要是基于势函数 田( x ，s ) = ( n + 矿、元) l o g ( j t r ( x s ) ) 一l o g ( d e t ( x s ) ) 一n l o g n ) ， 来设计算法，其中，p 1 通过寻找合适的搜索方向及步长来降低势函数的 值以求得最优解【删 非可行一初始点算法( i n f e a s i b l e - s t a r tm e t h o d s ) 第一个非可行初始点法由p o t r a 和s h e n g 3 3 提出，此外y e 等将s k e w - s y s t e m m e t r i cm o d e l 思想应用到了非可行一初始点方法【删 1 2 原始一对偶内点算法 1 9 8 4 年，k a r m a r k a r 用对数函数作为障碍函数，把线性规划问题化为无约束最 优化问题，然后使用带投影变换的最速下降法求解，创造了一个新的线性规划多项 式时间算法1 ，从而掀起了深入研究内点算法的热潮k a r m a r k a r 的投影算法经过 改进之后，产生了许多种内点法算，其中原始对偶内点算法( p r i m a l - d u a li n t e r i o r m e t h o d ) ，又称为原始对偶一路径跟踪法( p r i m a l - d u a lt a r g e tf o l l o w i n gm e t h o d s ) 是 学术界评价最高的有效算法之一，它是将对数障碍函数算法和牛顿迭代法结合起 来应用到线性规划的结果本节介绍求解线性规划问题的原始对偶内点算法 线性规划的标准形式： 原始问题 ( l p ) m i n c t x ：a x = 6 蛋0 ，( 1 1 ) 对偶问题 ( l d )m a x b t y ：a t y + 5 = c 8 2o ，( 1 2 ) 其中a r m 一，b r m ，c r n 假定矩阵a 是行满秩，即r ( a ) = m 只要给定 一个向量s 0 ，向量y 就能够唯一确定，因此可以根据s 确定( l d ) 的可行解下 面给出线性规划( l o ) 的一些基本概念 定义1 2 1 如果点。满足ta x = b ，且z20 向 叫，那么z 是口纠的可行 俨- 格可行j 点如果点m 砂满足：a t y + 8 = c 且8 0 扫 o ，那么向，砂是陋功 的可行( 严辐可行) 彘、如果最、( z w 8 ) 满足lz 是( l p ) 均可行( 严诲可行) 最，钿t s ) 是( l d ) 的可辑严诲可行) 氐。琊么( z v 。3 ) 乏豫强砖偶可行( 严格可行1 熹、 分别用c p 和c d 表示( l p ) 和( l d ) 的可行域 c p ：= z ：a x = 6 ，z o ) ，c d ：= 0 ，s ) ：a r 弘+ s = c ，s o ) 如果c p 是空集，那么就称( l p ) 不可行，否则( l p ) 可行如果( l p ) 可行而目标 函数值c t x 在( l p ) 上无界，那么就称( l p ) 无界，否则( l p ) 有界同样可以根据 c d 得到( l d ) 的相关概念 1 问题的大小记为厶是此线性规划的所有效据的二进制代码的长度比如对于线性规划( 1 1 ) ，l = e t _ - 。o 1 0 9 2 ( 1 0 玎i + 1 ) 1 其中d t 0 = m ，a o j = 勺，d = 0 一个算法求解出p 最优解所需的迭代教的 上界为o ( n l ) ，那么此算法就称为多项式时间算法，其中七是一常数是预先给定的精度- ! 螋z 生土连太堂墨芏塑堂焦迨塞 定理1 2 2 ( 弱对偶定理) 若z 和8 分别是仁p j 和陋d j 的可行点，那么c t x b r y 0 如果对偶间隙z t s = 0 ，那么z 和似叫分别是仁驯和仁d ，的最优解 证明， 0 x t 8 = z t ( c 一剪) = ，一( 血) r 暑，= c t z 一6 ，” 定理1 2 3 ( 强对偶定理【3 5 】) 对于仁一和仁驯必有下述命题之一成立 何仁彤和仁纠都可行且存在一个原始- 对偶可行点( 矿，矿，矿) 满足t c t x = b t y + ( 诋) ( l p ) 不可行。( l d ) 无界 ( 谳) ( l d ) 不可行。( l p ) j 乙界 洳) ( l p ) 和( l d ) 都不可行 定理1 2 4 ( g o l d - t u c k e r 定理【1 5 ) 如果仁纠和仁驯可行，那么存在最优 互补解p ，y ，s 它是最优解且满足矿+ 8 0 根据定理1 2 2 和定理1 2 3 容易知道，求解( 工p ) 和( l d ) 的最优解等价与求 解方程组： 其中s 表示n 维向量，扛s ) i = x i s i = 0 ，i = 1 ，m 它是( l p ) 和( l d ) 的互补条 件原始对偶内点算法的基本思想就是甩参数化的方程8 x = 肛代替互补条件 。s ；0 ，求解方程组 a x = b ，z 20 ， a t y + s = c 8 之0 ， ( 1 4 ) z s = “e 其中e = ( 1 ，1 ，1 ) ，p 0 定理1 2 5 如果内点条件成立，即t 存在( z o ，护，s o ) 满足： a x o = b ，x , 0 0 ，a 丁矿+ 8 0 = c 8 0 0 任给参数弘 0 ，参数化方程组口卅有唯一解c 3 5 】 假定( l p ) 和( 工d ) 的内点条件成立，( 1 4 ) 的解记为( z ( p ) ，( p ) ，s ( p ) ) ，称z ( p ) 是( l p ) 的p 中心，( 可( _ i i ) ，s ( p ) ) 为( l d ) 的p 中心随着p 的变化，( z ( p ) ，”( p ) ，s ( p ) ) 3 o m m 一 一 蕾 s 阮 6 仉 = = = 血 船 矿 形成一条曲线，称之为( 工p ) 和( l d ) 的中心路经p 一0 ，中心路径的极限点满足 互补条件，是原始一对偶问题( l p ) 和( l d ) 的最优解 原始一对偶内点算法计算过程就是沿着中心路径逼近最优点的过程下面给 出中心路径邻域的概念： ( 下，p ) = ( z ，8 ) 0 ：a a ：；b ，a r y + s = c ，町( z ，8 ，p ) r )( 1 5 ) 其中q ( 毛8 ，p ) 是点( z ，s ) 到妒中心( z ( p ) ，s ( p ) ) 的一种度量2 ，r 是邻域的半径 原始对偶内点算法可以概述为，先给定p 0 ，假定初始点( x , y , s ) 在邻域 厂 内3 ，每次外迭代是通过更新p 来完成p + ：= ( 1 一口) “0 0 o ； 固定障碍校正参数口，0 0 ) 是线性规划原 始问题的严格可行域对问题( 1 7 ) 用牛顿法求解，对于取定的参数m 此问题的 k k t 条件 2 3 】与原始对偶内点算法关于p 的最优性条件( 1 4 ) 完全一致【3 5 】当 p 趋于0 时，由k k t 条件所产生的序列扛( p ) ) 就趋于线性规划问题的最优解 1 3 1中心路径的度量 根据原始对偶内点算法1 1 ，要实施一个外迭代，首先要判断迭代点是否进 入中心路径的邻域内因此迭代点到中心路径的度量町( 蜀s ，p ) 的选取直接影响算 2 q q z 生上连盘堂垄堂亟堂焦盈塞 法的有效性为此我们引入向量 “= 居，”以- 、兰， ( 1 9 ) “。、i ，”_ 5 、盖， 【1 9 ) 它们的第i 元素分别是厣和、焉，z 和s 分别是线性规划原始问题和对偶问 题严格可行解 对于原始对偶内点算法，迭代点到中心路径的度量函数为。 皿( 为毛p ) ：= 雪 ) ：= 币( 啦) ， ( l 1 0 ) i = 1 其中，妒( t ) = ! 一l o g t ，雪( z ，s ，p ) 是经典对数障碍函数 1 3 2 搜索方向 为了阐明度量函数( 1 1 0 ) 与搜索方向( 。，弘a x ) 之间的关系，我们引入尺度 搜索方向； 如：= 半，也：= 字， ( 1 1 1 ) 如：2 ，也：2 f ， ( 1 1 1 ) 其中，”由( 1 9 ) 给出尺度搜索方向在原始对偶内点算法理论迭代界的分析中 有很重要的作用 用以求解搜索方向的牛顿方程组( 1 6 ) 转化为如下形式： a 如= 0 ， a t g + d o = 0 ， ( 1 1 2 ) d 工+ 以：口一t ， 其中，a = j a y x ，v = d i a g ( v ) ，x = d i a g ( = ) 上述方程组的第三个方程右边的 表达式正是度量函数( 1 1 0 ) 的负梯度有如下结论t 如和比正交事实上，一方面如属于矩阵a 的零空间，另一方面也属于矩 阵a 的行空间 如与也的和是度量函数m ( ”) 的最速下降方向 当且仅当( x , y , s ) 在中心路径( z ( p ) ，( p ) ，s ( p ) ) 上时， z = a y = 8 = 0 争m ( u ) = 0 甜- 皿( 口) = 0 1 4 本文所作的工作 本文的主要内容分为三个部分 第一部分的主要工作是：在已有的基于障碍函数的原始对偶内点算法的研 究工作中，对障碍函数的研究基本局限于对障碍函数的障碍性的分析，很少考虑 障碍函数中所含参数对障碍性的影响，也没有对参数作具体的分析然而，有些 数值结果显示，障碍函数中所含参数对障碍性起很大的作用，比如有限障碍函数 就是一个典型的例子，看 5 】因此，我们首先列举已有含有参数的障碍函数和它 们的核函数，给出它们各自的性质以及对应的小步和大步算法的复杂性然后对 含参数核函数的参数进行了分析研究 第二部分工作是；在对参数化核函数分析的基础上，本文对经典对数障碍函 数做了推广，提出一个参数化核函数 t p + 1 1 妒( t ) = 二_ _ 一l o g t ，t 0 ，0 p s l ( 1 1 3 ) y 十1 参数p = 1 时，此函数正是经典对数障碍函数的核函数，因此由( 1 1 3 ) 构造的障碍 函数称为参数化对数障碍函数基于这个函数设计了求解半正定规划问题的原始 对偶内点算法，分析了算法的复杂性，得到的大步和小步方法的理论迭代界与基 于经典对数障碍函数的算法的理论迭代界一致，分别为o ( v 伍l o g 詈) 和o ( n l o g ) 论文的最后一部分的工作是，对第一部分的工作给出数值结果，即针对一个 具体线性规划问题，给出基于含参数核函数的原始对偶内点算法的数值结果， 分析了参数对算法复杂性的影响同时对第二部分中得到的算法应用到求解具体 的半正定规划问题中，数值结果表明和基于经典对数障碍的原始一对偶内点算法 相比，我们的算法的迭代界与参数的不同取值有关当参数取某个值时，算法的 迭代界比经典的算法好 1 5 注记 文章中用到下面符号，r 罩和r 孙分别代表n 维空间，非负n 维空间， 正n 维空间| | 表示矩阵的f r o b e n i u s 范数，即二范数对于向量z 和s ，x 8 表 示元素为甄s i 的向量s n ，s 罩和s 轧表示t l n 对称矩阵，半正定矩阵，正定 矩阵锥对于任意对称矩阵a ，b ，a 三b ( 或a 卜b ) 表示a b 是半正定( 正定) 矩 阵以b = t r ( a t b ) 任意v s h ，假定y 的特征值按递增顺序排列，即满足： a 1 ( y ) a 2 ( y ) k ( y ) 任意矩阵m ，记a l ( m ) a 2 ( m ) 2 ( m ) 为m 的 奇异值当m 为对称矩阵时有，m ( m ) = i 知( m ) l ，t = 1 ，2 ，t 1 ! ! ! ! 鱼占童查童矍堂堑圭兰堡垒塞垒 第二章参数化障碍函数在内点算法中的应用 2 1 障碍函数与核函数 、 障碍函数最早用于障碍函数算法( b a r r i e rp a n c t i o n s ) 求解非线性规划问题原 问题( p r i m a lp r o b l e m ) 形如； m i n f ( x ) ：g ( x ) s0 ，z x ) 其中，g 是由g l ，9 m 组成的方程向量， ，g t ，9 m 在i p 上连续，x 是r ，的 非空集合 障碍问题( b a r r i e rp r o b l e m ) 形如t m i n o ( # ) ：p o ) 其中，p 称作障碍参数，口( p ) = i n f f ( x ) + p b ：g ( x ) 0 ，z x b 是障碍函数在 区域 x ：g ( x ) x ) 上非负而且连续，当x 趋于x ：g ( x ) 0 ) 的边界时，b 趋于 正无穷障碍函数一般形式为t m b ( z ) = 妒h ( z ) 】 ( 2 1 ) t = 1 其中是在b ：口 o ； 甑m ) 。规巾) = o 。 则称函数，( z ) 为核函数 由核函数妒( t ) 构造的障碍函数为t n 田( ) ：= 妒( q ) ( 2 5 ) i = l 其中，”的定义由( 1 9 ) 给出皿( e ) = o ； 基于障碍函数的原始一对偶内点算法中，障碍函数的作用主要表现在 障碍函数完全由核函数妒( t ) 确定，并各个分量具有分离性 用障碍函数皿( ”) 代替( 1 5 ) 中的”( z ，s ，_ ) ，作为迭代点( z ，s ) 到少中心( 。( p ) ，s ( p ) ) 的度量； 通过求解方程组 a z = 0 a t a y + 8 = 0 ，( 2 6 ) s z + z s = - # u v 雪0 ) 来求得内迭代的搜索方向； 内迭代中步长a 选取也与障碍函数有密切的联系 算法理论迭代界的具体分析中还用到障碍函数的很多性质【6 】 3 t 1 1 3 2 1 2 2 已有的核函数 原始一对偶内点算法分为小步校正方法和大步校正方法在理论上，基于经 典对数障碍函数的原始对偶内点算法的小步校正方法的理论迭代界0 ( 、，佤) 1 0 9 ；， 相比大步校正方法的理论迭代界0 ( n ) l o g 孚要好，然而在实际应用中小步校正方 法却远不如大步校正方法有效这个理论与实践之间的间隙一直被许多学者和专 家关注和研究，他们通过寻找新的核函数来减小这个间隙j p e n g 等人提出了 s e l f - r e g u l a r 函数1 3 1 1 标准形式： 妒( t ) = 石t p 丽+ i - 1 + 而t 1 - q 可- 1 + 学( t 一1 ) ，t 0 7 p 1 口 1 ( 2 7 ) 2 q q z 生土盘盘堂垄堂亟堂焦硷塞! q 此函数满足下述两个条件； 1 妒( t ) 是( 0 ，o o ) 内是严格凸函数，在t = 1 处达到全局最小值，即妒( 1 ) = ( 1 ) = 0 另外，存在常数屹魄 0 及p 1 ，q 1 满足t v l ( t p 一1 + t - i q ) ( ) sv 1 ( t - - i - - 9 ) ，y t ( 0 ，o 。) ； 2 任意t l ，t 2 0 ， 妒( 巧t ；一7 ) sr 妒( t 1 ) + ( 1 一r ) 妒( t 2 ) ，r 【0 ，l 】 基于此函数他们设计了线性规划和半正定规划的原始对偶内点算法分析得出 了大步校正方法的理论迭代界d ( 、，丽l o g n ) l o g ；，这是目前大步校正方法最好的理 论迭代界，从而在一定程度上改善了其在理论与实践之间的间隙 随后j p e n g 等【3 2 】提出核函数 仲) = 等+ 当，。 1 ( 2 s ) 此函数为强凸函数，具有二次增长性1 3 2 】采用了新的数学工具，简化了复杂性 的分析过程，得出在参数q = l o g n 时，基于此函数的原始对偶内点算法的大步 校正方法的理论迭代界也达到了目前最好0 ( 瓶崦n ) l o g ； y q b a i 等人【6 】提出形如 州：之2 + 如( t ) ( 2 9 ) 的函数，如果满足下面五个性质， 1 t 矿( t ) + ( t ) 0 ，t 0 ，t l ； 3 妒“( t ) 0 ，t 0 ，t 0 ，t 1 ，卢 1 就可以作为核函数来设计原始对偶内点算法容易验证( 2 8 ) 满足这五个性质 赧炳惭嗽瞰她，牟一p k 眨埘 和 她) = 等+ 宰( 2 1 1 ) 得出大步校正方法的复杂性都为o ( 、，丽i 0 9 2n ) l o g 詈 2 q q z 生盘盔望墨堂亟堂焦监塞! ! y q b a i 等人【4 提出了具有线性增长性的核函数 仲) = t - l + 并，口 1 ( 2 1 2 ) 相对于( 2 9 ) 此函数没有二次增长项，也不具备强凸性 y q b a i 5 】等人还提出了一个特殊的核函数 。 仲) = 争+ 口1 - ( e q ( 1 - t ) - 1 ) ，q 1 ( 2 1 3 ) 相对于其他核函数它的特点在于 溉2 等m ( 2 1 4 ) 因此它被命名为有限障碍核函数( 2 1 4 ) 有悖于定义2 1 1 ，表面上看起来( 2 1 3 ) 无 法起到障碍作用，在算法分析中此核函数的障碍作用是通过参数q 来体现的，具 体分析见【5 】参数q = d ( 1 0 97 1 ) 时，对于大步校正方法也得出了目前最好的理论迭 代界0 ( 、，丽l o g n ) l o g ； y q b a i 【7 】等人对( 2 1 0 ) 引入参数之后提出 妒( t ) ：单一f 一( 心口1 ( 2 1 5 ) 当参数q = d ( 1 0 9n ) 时，基于此函数的原始对偶内点算法的大步校正方法理论迭 代界达到目前最好 v q ，b a i 等还对经典对数障碍函数引入参数提出 p + l1 妒( t ) 2 哥一l o g t ，t 0 ，0 s p 1 设计了基于此函数的解线性规划问题的原始对偶内点算法，得到的大步校正方 法的理论迭代界与基于经典对数函数的原始对偶内点算法相同 k a m i n i 3 对( 2 1 3 ) 形式上进行了改进提出 仲) = 争+ 三a ( e t - - l _ 1 ) ，口 1 ，( 2 1 6 ) 此函数与定义2 1 1 相一致，但相对于( 2 1 3 ) 大步校正方法复杂性有所降低，为 d 徊v 石( 1 0 9n ) 1 + j ) 1 0 9 詈 王国强等【4 1 】将( 2 9 ) 和( 2 1 2 ) 结合起来，提出了 此) = 可t p + - 1 + 岩，。s p l ， 参数满足一定条件后，大步校正方法也得出了目前最好理论迭代界 垫! z 生土连左堂矍堂亟堂焦迨塞1 2 l 核函数咖( t )小步复杂性大步复杂性 文献 1 丁t 2 - - 1 一l o g t0 ( 侗l o g ；no ( n ) l o g 詈 】 2 ( t 一 ) 2o ( 洞l o g 詈 o ( n 1 ) l o gi a 0 3 司t l “丽r l - - 1 + 尕t l - 两q - - 1 + 等。一1 ) ，p 1 ，q 1 o ( e a 3 l o g ；o ( q n q ：+ 一1 ) 晚； 【3 1 4 争+ 等，g 1 o ( q 伍- ) l o g ；o ( 口n 等) 魄詈 p 2 5 学+ 年o ( v n ) l o g ； o ( v 伍l 0 9 2n ) l o g 詈【6 】 6 t t 2 - - 1 一片e 一1 武 d ( 、，曰l o g 詈d ( 何l 0 9 2 n ) l o g 詈 【6 】 7 t 一1 + 紫，q 1o ( 矿伺l o g ： o ( q n ) l o g ； f 4 】 8 争+ j ( 矿( 1 一) 一1 ) ，q 1 o ( v n 3 l o g 詈o ( 何1 0 9 n ) 1 0 9 ； 【5 1 9 霉 + ；( e t l 1 - - i ) ，q 1 o ( 侗l o g ： d ( q x 元( 1 0 9n ) 1 + h v ，si n 1 0 卧1 亍1 吐：2 y p 7 1 ，q 1 q - - 1 o ( q 2 l o g ； 0 ( q n 焉4 - ，j 邺i l q , 【4 1 】 表2 1 ：核函数 图2 1 ： ( t ，q ) 2 3 参数化核函数 正如第二节的介绍，新核函数的提出是为了减小基于核函数的原始一对偶内 点算法的大步与小步校正方法在理论迭代界上的间隙，根据表2 1 不难看出，所 有核函数对应的小步校正方法的理论迭代界基本一致1 ，因此要减小此间隙，就是 提出新的核函数来降低其大步校正方法的理论迭代界根据上一节的介绍及表2 1 不难发现，基于下列核函数 f l ( t , q ) = 而t 纠- 1 - 1 + 耥+ 等( ) j p 1 i 口 1 ( 2 1 7 ) 21： f 2 ( t ，q ) = 竿+ ；( e q ( 卜) 一1 ) ，q 1 ( 2 1 8 ) q 觚) = 等4 - 寄，o p n 纠 ( 2 1 9 ) 原始对偶内点算法的大步校正方法的理论迭代界在参数q 满足一定条件时为目 前最好的复杂性这三个含参函数的的图像分别是图2 1 、图2 2 和图2 3 本节 对这三个核函数的参数q 进行研究2 ( ，q ) 关于的一阶、二阶导数分别是 tdfl(t,q)=丽tf“-i+t1-q(可a-q)+幽(220it q ( q 1 p c l ) 出t ( p + ) 一) 。 7 1 对于也，咖和妒l o ，参数口取常效时，小步理论迭代界与d ( 侗l o g 詈一致 2 固定参数p 的情况下研究参数q 对函敷障碍性的影响 图2 2 ：，2 ( t ，q ) 图2 3 ：，3 ( t ，g ) 匿f 可 7 7 一。 t ：| ，f删 l 7园w o i ：| 、k 图2 4 ：堂唔图2 5 ：乌铲 f 嗣 。 器： 幽 噬 一_ 一一一一，一一一， 一一- 一一，一一一，_ 一一一 一一一。一一一 o ：_ 图2 6 ：笃产图2 7 唾产 掣= 百t p 4 - 1 p + 可q t l - q 而( 1 - - q ) ( 2 2 1 ) 五广2