（运筹学与控制论专业论文）基于局部selfconcordant障碍函数的内点算法.pdf

摘要 1 9 9 4 年数学规划专家y u r i in e s t e r o v 教授和a r k a d in e m i r o v s k i i 教授首次提出了 s e l f - c o n c o r d a n c e ( s c ) 函数以及s c 障碍函数的理论，并基于s c 障碍函数设计了统 一求解一般凸优化问题的内点算法，给出了算法复杂性的统一分析这个研究工 作是前沿性和高度有影响的，2 0 0 6 年a r k a d in e m i r o v s k i 教授被邀请在西班牙数学 家大会做了一小时报告 对s c 函数以及s c 障碍函数的研究由c r o o s 教授领导的研究团队进行了推 广2 0 0 6 年，他们首次提出了局部s c ( l s c ) 障碍函数的概念，试图将已有的基于 核函数的障碍函数和s c 障碍函数统一起来在这几位研究者工作的基础上，本文 研究了两个由核函数确定的障碍函数的l s c 障碍性质这两个函数的l s c 障碍性 质的体现主要是通过对它们的两个重要参数的计算，由于这两个重要参数与优化 问题的维数有关，因此也与算法的计算复杂性有关其次，本文设计了求解自对偶 线性规划问题 ( s p )m i n q t x ：m x 一口，z o 的纯n e w t o n 步内点算法其中，m 为斜对称矩阵( 即m r = 一m ) ，0 q r n ，z 钟我们分析了算法的复杂性，得到此算法具有多项式时间算法复杂性的结论最 后，我们给出了一个数值计算实例来说明l s c 障碍函数的参数对算法复杂性的影 响 全文共分为六章：第一章是绪论，综述了内点法和s c 函数、s c 障碍函数的 历史发展，介绍了内点法的基本思想及分类第二章介绍了s c 函数和s c 障碍函 数的概念和性质，给出了解线性规划问题的纯n e w t o n 步内点算法第三章通过对 l s c 函数和l s c 障碍函数的介绍，给出了基于核函数的l s c 障碍函数理论第四 章研究了两个基于核函数的障碍函数的l s c 障碍性质，给出了解自对偶线性规划 问题的纯n e w t o n 步内点算法，分析了算法的复杂性第五章是数值实验部分，通 过一个数值算例说明l s c 障碍函数的参数对算法复杂性的影响第六章是结论部 分，是对本文研究成果的总结及对今后研究的展望 关键词：线性规划，原始一对偶内点算法，纯n e w t o n 步，小步校正算法，s e l f - c o n c o r d a n t 函数，多项式时间算法复杂性 a b s t r a c t p r o f y u r i in e s t e r o va n da r k a d in e m i r o v s k i if i r s tp r e s e n t e dt h et h e o r yo fs e l f - c o n c o r d a n t ( s c ) f u n c t i o na n ds cb a r r i e rf u n c t i o ni n1 9 9 4 m o r e o v e r ，t h e yd e s i g n e dt h e i n t e r i o r - p o i n ta l g o r i t h mf o rc o n v e xo p t i m i z a t i o np r o b l e mb a s e do ns cb a r r i e rf u n c t i o n s t h ep o w e ro ft h ea l g o r i t h mi st oa n a l y z et h ep o l y n o m i a l - t i m ec o m p l e x i t yo ft h ea l g o r i t h m u n i f o r m l y t h e nt h eg r o u pi nn e t h e r l a n d sl e db yp r o f c r o o sd e v e l o p e dt h er e s e a r c ho ns c f u n c t i o na n ds cb a r r i e rf u n c t i o n t h e yf i r s tp r e s e n t e dt h ec o n c e p t so fl o c a ls c ( l s c ) f u n c t i o na n dl s cb a r r i e rf u n c t i o n 。a n di n t e n d e dt oe s t a b l i s ht h er e l a t i o nb e t w e e ns c b a r r i e ra n dt h eb a r r i e rf u n c t i o nd e t e r m i n e db yk e r n e lf u n c t i o nw h i c hi sf i r s tp r e s e n t e db y b a l ie ta 1 f 3 7 i n s p i r i t e db yt h e i rw o r k i nt h i sp a p e rw ee x p l o i tt h el s cb a r r i e rp r o p e r t yo ft w o b a r r i e rf u n c t i o n sw h i c ha r ed e t e r m i n e db yt h ec o r r e s p o n d i n gk e r n e lf u n c t i o n s w ef i r s t s t u d yt w op a r a m e t e r sf o rt h eb a r r i e rf u n c t i o n sb e c a u s et h e s et w op a r a m e t e r sa r ec r u c i a l f o rt h el s cb a r r i e rp r o p e r t y f u r t h e r m o r e ，t h e s et w op a r a m e t e r sc a nb eu s e dt oc o m p u t e t 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 ms i n c et h e yr e l a t et ot h ed i m e n s i o no fap r o g r a m - m i n gp r o b l e m t h e n w ep r e s e n ta na l g o r i t h mw i t hf u l l - n e w t o ns t e pf o rs e l f - d u a ll i n e a r o p t i m i z a t i o np r o b l e mo ft h ef o r m ( s p )m i n q t z ：m x 一q ，z 0 ) w h e r et h em a t r i xmi ss k e w - s y m m e t r i c ( i em t = 一m ) a n dt h ev e c t o rqi sn o n n e g a - t i v e ( e n t r y w i s e ) a n dn o n z e r o w ed e r i v et h ei t e r a t i o nc o m p l e x i t yo ft h i sa l g o r i t h m f i n a l l y , n u m e r i c a lr e s u l t ss h o wt h a tt h ec o m p l e x i t yb o u n di si n f l u e n c e db yt h e s et w op a r a m e t e r s 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 ef i r s t l yr e c a l lt h eh i s t o r yo fi n t e r i o r - p o i n tm e t h o d s ( i p m s ) t h e nw eo v e r v i e wt h eb a s i cc o n c e p t so fl p m sa n d a l li t sa l g o r i t h m s i nc h a p t e r2w ei n t r o d u c et h ep a r a m i l i t a r i e so fs cf u n c t i o na n ds cb a r r i e rf u n c t i o n ， i n c l u d i n gt h ed e f i n i t i o n sa n dt h e i rp r o p e r t i e s w ea l s op r e s e n t t h ei n t e r i o r - p o i n ta l g o r i t h m w i t hf u l l - n e w t o ns t e pf o rl i n e a ro p t i m i z a t i o n i nc h a p t e r3w eb r i e f l yr e c a l lt h en o t i o n s o fl s cf u n c t i o na n dl s cb a r r i e rf u n c t i o na sw e l la st h et h e o r yo fl s cb a r r i e rf u n c t i o n s d e t e r m i n e db yk e r n e lf u n c t i o n s i nc h a p t e r4w es t u d yt h el s cb a r r i e rp r o p e r t i e so f t w ob a r r i e rf u n c t i o n sd e t e r m i n e db yk e r n e lf u n c t i o n sa n dc o m p u t et h el o c a lp a r a m e t e r s o ft h e m ，t h e nw ep r e s e n ta ni n t e r i o rp o i n ta l g o r i t h mw i t hf u l l n e w t o ns t e pf o rs e l f - d u a l l i n e a ro p t i m i z a t i o na n df i n a l l ya n a l y z et 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 r5 w es h o wa ne x a m p l ea n dp r e s e n ti t sn u m e r i c a lr e s u l t s f i n a l l y , c h a p t e r6c o n t a i n ss o m e c o n c l u d i n gr e m a r k s w es u m m a r i z et h em a i nr e s u l t so ft h et h e s i sa n ds u g g e s ts o m ef u t u r e r e s e a r c hd i r e c t i o n si nt h i sc h a p t e r k e y w o r d s ：l i n e a ro 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 ，f u l l - n e w t o ns t e p ， s m a l l - u p d a t em e t h o d ，s e l f - c o n c o r d a n tf u n c t i o n ，p o l y n o m i a lc o m p l e x i t y 至塑墨生连盍堂垄堂亟堂焦迨塞墨 l i s to fn o t a t i o n s s o m en o t a t i o n su s e dt h r o u g h o u tt h ep a p e ra r ea sf o l l o w s ：f i r s t ，r n ，衅a n d 衅+ d e n o t et h es e to fv e c t o r sw i t hnc o m p o n e n t s ，t h es e to fn o n n e g a t i v ev e c t o r sa n dt h es e t o fp o s i t i v ev e c t o r s ，r e s p e c t i v e l y f u r t h e r m o r e ，l l z 0 = z r zd e n o t e st h e2 - n o r mo ft h e v e c t o rz ，w h e r e a s8 2 8 d e n o t e st h ei n f i n i t yn o r m i fz ，8 l p ，t h e nx 8d e n o t e st h e c o o r d i n a t e w i s ep r o d u c to ft h ev e c t o r sza n d8 ed e n o t e st h ea l lo n ev e c t o ro ft h el e n g t h n i fz 础( 衅) ，w ew r i t ez o ( x o ) i fz r na n df ：衅一舯，t h e n ，( z ) d e n o t e st h ev e c t o ri nr 翌w h o s ei t hc o m p o n e n ti sf ( z o ，w i t h 盈0 ，1 i 佗a s s u m e t h a t ：d _ r ，di sa no p e nc o n v e xs u b s e to fr n ，f o ra n yz da n dh 兄_ r 1w eu s e t h eu n i v a r i a t ef u n c t i o n 九， ( n ) ：= ( z + a h ) w h e r enr u n 8t h r o u g ha l lv a l u e ss u c ht h a t z + a h d t h ef i r s tt h r e ed e r i v a t i v e so f 札hw i t hr e s p e c tt o 口a r ed e n o t e da s ( 加轴掣 醒，l ( 口) = 冬l 凳1 峨幻1 0 2 丽( x + f a h ) 蝼小) = 冬。翠。酣蚴七鬻 a n dt h ef i r s tt h r e ed e r i v a t i v e sa to f 如j ia to l = 0a r ed e n o t e da s 妃i i l ( o ) = 护v 审( z ) = v 咖( z ) 【明 j i l ( o ) = r v 2 咖( z ) 九= v 2 ( z ) 【 ，纠 髻l l ( o ) = 矿v 3 咖( z ) 【，司九= v 3 ( z ) 【 ，h ， 4 f i n a l l y , g ( x ) = d ( ，( z ) ) m e a n st h a t ( x ) c g ( z ) f o rs o m ep o s i t i v ec o n s t a n tc 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作除了文中特 别加以标注和致谢的地方外，论文不包含其他人已发表或撰写过的研究成果参与 同一工作的其他同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示了谢意 签名：伶丕舒 日期：少富f ；i 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有权保留论 文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容 ( 保密的论文在解密后应遵守此规定) 豁信台骛导师豁白够喊根西一 2 0 0 8 年上海大学理学硕士学位论文 1 第一章绪论 在本章中，首先，我们回顾了内点法的历史背景，概述了内点法的基本思想 和分类，详细介绍了内点法中常用的路径跟踪法其次，在讨论了n e w t o n 法的传 统分析理论的缺陷后，我们概述了s c 函数和s c 障碍函数提出的背景和意义最 后，我们介绍了本文所做的主要工作 1 1内点法的历史背景 线性规划( l i n e a ro p t i m i z a t i o n ) 是数学规划的一个重要分支，历史比较悠久， 理论比较成熟，方法比较完善数学规划方面的主要突破总是来自于线性规划的 创新线性规划是处理一类简单的数学模型，它可以被考虑为是连续的组合问题 它的连续性是基于它可被看作是在一个连续凸多面体约束集上求目标函数的全局 极小值；它是组合问题的描述是基于它可被看作是在一个凸多面体的顶点集上寻 求最优值线性规划的一系列算法，都是基于杰出数学家d a n t z i g 1 1 在2 0 世纪4 0 年代提出的单纯形法，这是沿着规划问题可行域的相临顶点搜索而达到最优顶点 的方法然而，在最坏的情况下，单纯形法可能会走遍( 或几乎走遍) 所有顶点， 于是迭代次数将会随问题规模增大而呈指数级上升考虑到这种情况，人们自然 会提出疑问；单纯形法是不是好的算法【2 ，3 】? 为评估算法的性能优劣，2 0 世纪7 0 年代提出了一个评价体系，即所谓算法 复杂性，它是指一个算法在最坏情况下的计算量随问题规模增大而增长的速度估 计，一个算法的计算量随问题规模变化而变化，按最坏情形衡量，算法的计算量 可视为问题规模的函数，称此函数为算法复杂性函数当算法复杂性是一个多项 式函数时，称该算法具有多项式时间复杂性，或称该算法是一个多项式时间算法 【4 ，5 ，6 】所谓多项式时间是指；若令工为问题的规模( 指问题的各种数据编译成二 进制代码后，输入计算机的强度) ，对给定的算法t ，t ( l ) 表示求解任何规模为l 的问题所需计算机执行时间的上界如果存在三的某个多项式p ( 工) ，使得 t ( l ) = o ( p ( l ) ) ， 则称算法t 是问题的一个多项式时间算法，t 的时间复杂性为o ( p ( 三) ) ，即算法t 在时间o ( p ( l ) ) 内收敛到问题的解如果一个算法是多项式时间算法，就称此算 法是有效的；否则，是一个无效算法 一系列的研究表明，单纯形法从严格意义上来说不是多项式时间有效算法， 单纯形法的迭代次数是指数次运算，需要2 n 一1 次迭代于是，人们不禁产生这样 的疑问：是否存在多项式时间算法解线性规划问题? 为此许多专家和学者多年来开展了大量的理论研究，力图找到具有多项式时 间算法复杂性的新的线性规划算法第一个这种新算法是苏联学者k h a c h i y a n ( 哈 奇扬) 1 9 7 9 年提出的基于收缩球体的非线性集合理论的椭球法【6 】，并且证明了计算 复杂性是o ( n 4 l ) ，是多项式时间算法，这一结果在全世界引起很大轰动，被认为 是线性规划理论方面的历史性突破，然而该算法并没有如其所希望的那样在计算 速度上超过单纯形法原因主要有- - z 一是迭代次数仍然很多；二是不便应用稀疏 矩阵技术，每次迭代的计算比单纯形法慢很多椭球法肯定了线性规划问题存在 多项式时间算法的问题，这必然引发人们探索时间次数更低、实用性更强的多项 式时间算法 1 9 8 4 年，k a r m a r k a r 7 1 提出了第一个具有多项式时间算法复杂性和实用性的内 点法，称为k a r m a r k a r 法，它是求解线性规划问题、线性约束规划问题的一类重 要方法它的计算复杂性为o ( n 3 与) ，比哈奇扬法好该类算法的基本思想是在可 行域内部生成收敛于最优解的序列，并使得它在多项式时间界限内收敛到最优解 今天看来，k a r m a r k a r 显然开创了线性规划一个新的领域一内点法内点法的提出 激发了学术界的极大兴趣，出现了从理论到实践全方面对k a r m a r k a r 法进一步研 究的热潮 在k a r m a r k a r 首次提出具有多项式时间算法复杂性的内点法后2 0 年，经过众 多优化专家的共同努力，许多专家和学者提出了很多种内点方法，也取得了大量 的理论成果( 【8 】，f 9 】，f 1 0 ，【1 1 ，【1 2 ，【1 3 】) ，有关内点法的数值软件的计算效率也明 显提高 1 9 8 6 年，j r e n e g a r 和c g o n z a g a 提出了所谓的路径跟踪算法( t h ep a t hf o l - l o w i n ga l g o r i t h m ) 【1 4 ，将计算复杂性提高到o ( n 3 l ) 路径跟踪算法的提出是内点法 发展史上又一具有里程碑意义的事件，此算法反映了内点法的本质，使解线性规 划的内点算法推广到解更一般化的凸规划问题成为可能 1 9 9 4 年，内点法的理论已经发展得比较成熟，在此期间数学家n e s t e r o v 和 n e m i r o v s k i i 作出了主要贡献，在他们的专著中提出了所谓的s e l f - c o n c o r d a n t 障碍 函数( 1 5 】的概念，基于对数障碍函数的多项式时间内点算法被推广为求解更复杂 的规划问题，诸如非线性凸规划、非线性互补规划、半正定规划和二次锥规划等 此后，n e s t e r o v 和t o d d 进一步研究了更为一般的基于所谓的s e l f - s c a l e dc o n e s f 1 5 ，1 6 】的线性规划内点算法，而且也推广到半正定规划和二次锥规划，从k a r m a r k a r 提出k a r m a r k a r 算法至今，关于内点法的文献专著已数不胜数内点法的研究范围 不断扩大，应用范围也涉及生活的方方面面，具体可参考 1 3 ，1 7 】欲对线性规划 内点算法进行深入研究，可参考优秀专著【1 2 ，1 3 ，1 6 ，1 8 ，1 9 ，2 0 】 至q q 墨生土连太堂翌堂亟堂焦迨塞墨 1 2内点法的基本思想及分类 内点法的基本思想是从问题的可行域内选一个严格内点，在可行域的内部生 成一个点列，同时要求整个迭代过程始终在可行域内部进行，在可行域边界设置 一道“障碍”以阻止迭代点到可行域边界上去，迭代点一旦接近可行域边界，就要 受到很大惩罚，迫使迭代始终停留在可行域内部，逐渐趋近于最优解在迭代的每 一步，目标函数的值都有充分减小，从而使算法得以多项式时间次数收敛 根据生成点列的不同，内点法可以分为。 射影变换法( t h ep r o j e c t i v em e t h o d s ) 【1 7 仿射变换法( t h ea f f i n es c a l i n gm e t h o d s ) 2 1 路径跟踪法( t h ep a t hf o l l o w i n gm e t h o d s ) 1 4 路径跟踪法是在深入研究射影变换法和仿射变换法的基础上发展起来的，其 本质是将带约束的规划问题转化为一系列的无约束规划问题进行求解 考虑非线性规划问题 ( p )m i n ，( 引 【1 1 ) s t 仇( z ) 0 ，i = 1 ，礼 其中，z r n ，f ( x ) 和g i ( x ) 都是二次可微的凸函数 现将( p ) 的可行域记作 g = 伽舻lg i ( x ) o 我们假设g 是有界的，且绌( z ) ) 满足s l a t e r 条件f 2 2 】t 了z ： 夕i ( z ) 0 为罚参数障碍函数f ( x ) 满足如下条件： 1 f ( x ) 是定义在i n tg 上的光滑( 至少二次可微) 的凸函数 2 f ( x ) 是严格凸的，即 v 2 f ( z ) 10 ， z i n tg 3 f ( x ) 具有障碍性，即 z _ 阳净f ( x ) _ + f ( x ) 是由约束函数构造出的惩罚项，它的两种重要的形式为t m ) = 蚤n 丽1 和 n f ( z ) = 一l o g ( 一矶( z ) ) i - - - - - 1 当初始点向g 的边界趋近时，增广目标函数九( z ) 的值将无限增大如果原 问题( p ) 的最优解在g 的内部，则当p 取某一个适当的值时，钆( z ) 的最优解可以 达到它如果( p ) 的最优解在g 的边界上，则随着p 的减小，相应的钆( z ) 的最优 解点列将向g 的边界上的最优解逐渐逼近，最优解点列的收敛性证明详见参考文 献【2 3 ，2 4 因此，我们可以通过求解下列( p ) 的参数化问题得到约束问题( p ) 的 近似解。 ( 昂)m i n 钆( z ) s t z i n fg ( 1 2 ) 由于f ( x ) 的存在，在可行域边界形成“围墙”因此，( 丘) 的解必含于可行域 的内部 ( 咒) 仍是约束问题，看起来它的约束条件比原来的约束条件还要复杂，但是， 由于f ( x ) 的阻拦作用是自动实现的，因此，从计算的观点看，( 昂) 可当做无约束 问题处理 对于给定的p ，( 兄) 存在唯一最优解z ( p ) z ( p ) 是关于p 的连续函数，当p 变 化时，p ( p ) ip o 将形成( p ) 的一条中心路径( c e n t r a lp a t h ) 2 5 ，2 6 显然，p 取 值越小，( r ) 的最优解z ( p ) 越接近( p ) 的最优解当p _ 0 时，z ( p ) 的极限点就 是( p ) 的最优解根据这样的思想，一些学者提出各种不同的( 巳) ，产生不同的路 径z ( p ) ，从而形成一类方法，称为路径跟踪方法 由此可见，路径跟踪方法的本质是将带约束的规划问题转化为一系列的无约 束规划问题，一般选用n e w t o n 法【2 7 】这种解无约束规划问题的方法求解每一个 无约束规划问题同时，在每步迭代中，让罚参数以某个固定的比例缩减，从而 保证算法是多项式时间算法引进中心路径这一概念，并将问题的最优解看成该 路径的极限点，那么同样可以利用n e w t o n 法求解中心路径上的解，并且沿着中 至q q 墨生盘太堂垄堂亟堂焦迨塞 墨 心路径逼近最优解，基于这种思想的内点算法为路径跟踪算法( t h ep a t hf o l l o w i n g a l g o r i t h m ) 求解( p ) 的路径跟踪算法的步骤： s t e p l 寻找初始点z o i n tg ；给定p o o ；给出检验终止条件的误差e o ； 令k ：= 1 ； s t e p 2 进行一次外迭代矿：= ( 1 一口) 矿，0 口 0 ，使 铸、毒0 1 r n 奄 i i v 2 ( ) 一v 2 ( z ) i i l l l z 一x l l ， 则对于任意k ，迭代步有意义，并且迭代点序列 ) g a y - 阶的收敛速度收敛到矿 事实上，n e w t o n 法在以z + 为中心、r 为半径的区域内具有二次收敛性【2 2 】s 3 r 0 ，c 0 ，b 兰 z ：0 z z 。0 t o cd o m ， 一，z b 兮0 v 2 ( 一) 一v 2 ( ) i f l i i x 7 一x 1 1 、l 1 分别为v 2 ( z ) 的最小、最大特征值 0 l o l 1 ，l o ! v 2 ( z 事) 蔓l 1 显然，r o 和三。越小，l 1 和l 越大，则n e w t o n 法的二次收敛区域将越小，收 敛性越好然而在路径跟踪迭代过程中，随着罚参数的减小，相应增广目标函数的 h e s s i a n 矩阵会变得愈来愈病态，于是r 0 、l o 、l 1 和l 的值将变得越来越坏，这就 使得n e w t o n 法的迭代过程变得越来越复杂，从而在理论上减缓了收敛速度 算法的分析结果表明，计算复杂性是由l o 、厶和工这些值确定的【2 2 】 6 + 而采桀研叭一) ) _ p 1 ( 1 7 ) 该式中q 、p 和矿与本文关联不大，这里不作具体说明由于r o 、l o 、l 1 和l 在迭 代的过程中是变化的，因此这一分析结果没有表明算法具有多项式时间算法复杂 性 r e n e g a r 和g o n z a g a 1 4 】经过研究发现，对于线性规划问题 r a i n ( x ) = ，z ( 1 8 ) s t 仇( z ) 兰口 z 一坟0 ，i = 1 ，n 其中，z 俨，此问题的可行域 g = z 月p in z b i o 为一个多面体当我们用路径跟踪法求解时，若引入多面体g 上的经典对数障碍 函数 f ( z ) = 一l o g ( b i n z ) ， i = 1 则算法在多项式时间次数内收敛到最优解这就与n e w t o n 法的分析理论产生了矛 盾 矛盾的产生是由于下述原因：n e w t o n 法本身的仿射不变性表明n e w t o n 法的 局部二次收敛性应该仅依赖于本身然而，n e w t o n 法的局部二次收敛性分析 2 0 0 8 生上瀣太堂理堂亟士堂焦论文 9 和复杂性分析不仅依赖于本身，同时也取决于变量空间的内积结构，这是因为 r o 、l o 、l 1 和l 2 这些量不仅依赖于咖，同时也取决于变量空间中范数1 1 1 l 的定义 因此，n e w t o n 法的分析理论不具有仿射不变性 因此，n e w t o n 法的分析理论存在缺陷我们需要引入新的欧几里德结构( 内 积结构) ，以保持n e w t o n 法的仿射不变性在分析中得到应用 1 4s c 障碍函数的提出和意义 由上节可知，n e w t o n 法的分析理论依赖于变量空间的特定的欧几里得结构， 违背了n e w t o n 法本身的仿射不变性这就引发我们作这样的思考。能否从( z ) 本 身提炼一种欧几里得结构，使得对n e w t o n 法的分析不需要借助变量空间的欧几里 得结构 一个重要的发现是，对于光滑( 至少二次可微) 的严格凸函数咖( z ) ，由v 2 咖( z ) 可以定义一种内积和范数 v 2 咖( z ) = v 2 咖( z ) 【u ，叫= u t v 2 ( z ) 秒， 0 u i i v 2 任) = 、u r v 2 ( z ) t 1 v 2 v ( 。) 称为z 点处牡和 的局部v 2 咖( z ) 内积，l l u l l v ：咖( z ) 称为z 点处u 的局 部v 2 ( z ) 范数由此可见，由( z ) 本身就可以定义一种欧几里得结构 n e s t e r o v 和n e m i r o v s k i 1 6 1 经过长期的研究发现，基于对数障碍函数f 的路径 跟踪算法在多项式时间次数内收敛是由于j f l 具有以下两个良好的特性【1 6 】s s e t l - c o n c o r t a n c e i 嘉i 脚砸+ 州i 2 ( 豢i t _ 。聊+ 埘汽v h ，比锄汜 f i n i t e n e s so yt h eb a r r i e rp a r a m e t e r j y 0 ，满足 i v 3 ( z ) 【 ，h ，h ii 2 k ( v 2 咖( z ) 【九，司) l ，v z d v h r n ，( 2 1 ) 则称西为一个k s c 函数 由范数i v 。妒( 霉) 的定义，我们有 l v 3 ( z ) 陋，h ，嘲l 2 k ( v 2 ( z ) 【九，叫) 差= 2 k i l 0 弓。咖( 甸 因此，妒( z ) 为s c 函数表明，v 2 ( z ) 是l i p s c h i t z 连续的，l i p s c h i t z 常数为2 尤【3 l 】 对数障碍函数是s c 函数的经典实例 例2 1 2 对数障碍函数 函数( z ) = 一e 磐1l o g x i ，0 z r n 为1 - s c 函数由于 a ( z ) 一1 护咖( z ) 1 泸咖( z ) 一2 面。i 巧矿。虿1 矿。虿 其它二次和三次偏导数为口，任给h r n ，我们有 v 2 如) h 叫：壹墨，v 3 她) 阮h ，：一厶n 万2 h 3 hh i v 2 ( z ) 胁，叫= 笺，v 3 ( z ) 【 ，= 一厶万 i = l l i = l l 令& ：= 羔，则 z t v 2 ( z ) 限，纠= 孽，i v 3 咖( z ) ，h ，酬= 2 1 孽| i = li = l 由不等式 i 孽l l 已1 3 ( 1 9 2 i ，3 。 至q q 垦生上连太堂堡堂亟堂焦诠塞 ! 垒 可得 i v 3 ( z ) 【九，h ，h i l 2 ( v 2 ( z ) 【 ，嘲) 盖 取，c = 1 ，不等式俾砂成立 s c 函数具有如下重要性质 定理2 1 3 ( 仿射不变性，【3 1 】中p r o p o s i t i o n2 1 1 ) 设：d _ r pcr n 为 非空开凸集j 为一个s c 函数，x = a y + b 为褂到舻上的一个仿射变换，象集为 q n 舻，则逆象集为融上的一个开凸子集 q + = 暑，r k l a y + b q ) 同时，复合函数 矿( 可) = 咖( a ! ，+ 6 ) ：q + _ r 为q + 上的一个s c 函数 2 2n e w t o n 减量 由上文可知，s c 函数在z 点的n e w t o n 步为 a x 一一( v 2 ( z ) ) 一1 v ( z ) 设西的最优解为z ，我们该如何度量当前迭代点z 与z + 之间的距离呢? 人们 会很自然地想到用欧几里得范数l i x 一矿i i 作为度量工具然而，矿的未知性使这 种度量方法显得比较困难 于是，我们需要借助新的度量工具，即z 点处a x 的局部v 2 ( z ) 范数记 a ( z