（计算数学专业论文）解凸规划问题的一种半内点法.pdf

大连理工大学硕士学位论文 摘要 1 9 8 4 年，k a r m a r k a r 提出求解线性规划的新方法称为内点法，并证明该方法不但具 有多项式复杂性，而且实际计算对大规模线性规划问题的效果优于单纯形方法该算法发 表后，掀起研究内点法的热潮但是内点法要求解集有界性和对数障碍函数的一致凸性， 为此冯果忱、于波、林正华提出了利用牛顿同伦和不动点同伦组合的组合同伦内点法，该 算法对凸规划问题取消了解集有界性和对数障碍函数的一致凸性并且可以求解非凸规划 问题，并在一定条件下证明了同伦路径的存在性和收敛性但是组合同伦内点法需要可行 内点作为初始点 最近，于波、商玉凤提出动边界组合同伦算法，该算法取消了初始点必须为内点的限 制，并能够求解更广泛的非凸规戈问题由于动边界组合同伦路径有可能从可行域外部 趋近最优解，近似计算可能使得最后得到的近似解不满足约束条件，对很多实际问题不 能满足要求本文我们给出一种改进的动边界组合同伦算法，使得同伦路径对任意初始 点，同伦路径的后半段都在可行域的内部，这样可以通过数值跟踪同伦路径得到在可行 域内的近似解我们给出同伦路径的存在性和收敛性证明，并通过数值实验验证新算法 的有效性 关键词：凸规划；内点法；可行解；同伦算法 解凸规划问题的一种半内点法 as e m i i n t e r i o r p o i n tm e t h o df o rc o n v e xp r o g r a m m i n g a b s t r a c t i n1 9 8 4 ，k a r m a r k a rp r e s e n t e dan e wm e t h o dc a l l e di n t e r i o r - p o i n tm e t h o df o rs o l v i n g h n e a rp r o g r a m m i n g ，w h i c hw a sp r o v e dap o l y n o m i a la l g o r i t h m ：a n di t se f f i c i e n c yi sh i g h e r t h a ns i m p l e xm e t h o di np r a c t i c a la p p l i c a t i o n ，s i n c et h ep u b l i c a t i o no fk a r m a r k a r sp a p e r ， i n t e r i o r p o i n tm e t h o db e c o m e sah o tt o p i cf o rr e s e a r c h b u tb o u n d e d n e s so fs o l u t i o na n d u n i f o r mc o n v e x i t ya r en e e d e df o ri n t e r i o r p o i n tm e t h o d ，t h e r e f o r ，f e n gg u o c h e n ，y ub o a n dl i nz h e n g h u ap r o p o s e dt h ec o m b i n e dh o m o t o p yi n t e r i o r - p o i n tm e t h o du s i n gn e w t o n h o m o t o p ya n df i x e dp o i n th o m o t o p y , a n dp r o v e dt h ee x i s t e n c ea n dc o n v e r g e n c eo ft h e h o m o t o p yp a t hu n d e rt h ec e r t a i nc o n d i t i o n a n dt h i sm e t h o dn e e d saf e a s i b l ei n t e r i o r - p o i n ta st h ei n i t i a lp o i n t r e c e n t l y ) y ub oa n ds h a n gy u f e n gp r o p o s e dt h ec o n s t r a i n ts h i f t i n gc o m b i n e dh o - m o t o p ym e t h o d ( c s c h m ) ，w h i c hd i d n th a v et h ec o n s t r a i n tt h a tt h ei n i t i a lp o i n tm u s t i nt h ef e a s i b l er e g i o na n da a ns o l v em o r eg e n e r a ln o n c o n v e xp r o g r a m m i n gp r o b l e m sa l s o s o m e t i m e s ，h o m o t o p yp a t ho fc s c h mw a l k su pt ot h eo p t i m a ls o l u t i o no u t s i d et h e f e a s i b l er e g i o n ，w h i c hr e s u l t e di na p p r o x i m a t es o l u t i o ns o l v e di sn o t , f e a s i b l ef o ra l lt h e c o n s t r a i n t s i nt h i st h e s i s ，w eg i v eam o d i f i e dc s c h mf o rc o n v e xp r o g r a m m i n g ，t h e s e c o n dp a r to fh o m o t o p yp a t hi si nt h ef e a s i b l er e g i o nf o ra l lt h ei n i t i a lp o i n t s s ow e c a l lg e tt h ef e a s i b l ea p p r o x i m a t es o l u t i o nb yt r a c i n gh o r n o t o p yp a t hn u m e r i c a l l y t h e e x i s t e n c ea n dc o n v e r g e n c eo ft h eh o m o t o p yp a t ha r ep r o v e d ，a n de f f i c i e n c yo fo u rm e t h o d i si l l u s t r a t e db yt h en u m e r i c a le x p e r i m e n t a t i o n sa tl a s t k e y w o r d s ：c o n v e xp r o g r a m m i n g ；i n t e r i o r - p o i n tm e t h o d ；f e a s i b l es o l u t i o n ；h o - m o t o p ym e t h o d i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工作 及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学或 其他单位的学位或证书所使用过的材料。与我一同工作的同志对本研究所做 的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：堑毽：日期：竺：! ：! ：! ： 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连理工大学硕士、博士学位论文版权使用规 定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子版， 允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名； 舀笙： 导师签名 兰丛 丝! !年月j 三日 3 7 大连理工大学硕士学位论文 1 绪论 1 1 数学规划问题模型 在生产实际中，有大量的问题都可化为数学规划问题来处理例如，关于物质运输 的组织，在一定要求之下厂房建筑的最优结构、厂址的选择、水利资源的分析等等数学 规戈问题也称为最优化问题，而在很多实际问题中，一般的优化模型统称为数学规划模型 按照数学规划模型的具体特征，可以将数学规划分为： 线性规划模型( 目标函数和约束条件都是线性函数的优化问题) ； 非线性规划模型( 目标函数或者约束条件是非线性的函数) ； 整数规划( 决策变量是整数值得规划问题) ； 多目标规划( 具有多个目标函数的规划问题) ； 目标规划( 具有不同优先级的目标和偏差的规划问题) ； 动态规划( 求解多阶段决策问题的最优化方法) 数学规划是研究在变量z = ( 茁2 ，x 3 ，z 。) 受到某些条件约束之下，如何寻求一 ，使得某一个协个) 给定的函数在处取极小( 或极大) 值的一门学科用n 表示满足 所给定的条件的x 的全体，则数学规划的主要内容就是要对某函数f ( x ) 寻求一矿q ， 使得对于所有的z n ，都有f ( x 4 ) ，( g ) ，或者f ( z + ) s ，( z ) ，f ( x ) 被称为问题的目标 函数，n 被称为约束集，属于q 的x 被称为问题的可行解，扩被称为问题的一个最优解， 也称之为总体最优解若存在护q 的一个领域u ( x o ) n n 中之都有，( 矿) 茎f ( x o ) ， 则称z o 为问题的一个局部最优解，若q = r n ，即i 2 维欧氏空间，则上述规划被称为无约 束规划，否则被称为带约束规划 数学规划问题的基本形式为： 一一 r a i n ( m a x ) f ( x ) ， 一一 s t g ( x ) ( 2 ) 0 其中文为决策变量向量，为目标函数( 单目标规划只有一个函数，多目标规划可以理解 为一个向量函数的最优化问题) ，a ( 文) ( ) o 为约束条件，记d = ( 。x i 。g ( 1 x ) 茎( ) o ) 为可行集，因此规划的本质就是在可行集中选择使得目标最优的点若d = r n ，则该问 题为无条件约束问题 解凸规划问题的一种半内点法 本文主要研究考虑如下的凸规划问题 ( c n l p ) 篡描驯0i 1 州 ( 1 1 2 ) 8 t 仇( z ) ，( = ，m ) 。 其中。彤，并且，) 吼：口1 一r 是至少二次连续可微的凸函数 1 2 同伦算法 在非线性分析中 同伦方法( 或称连续延拓法) 是证明解的存在性定理的经典方法例 如，h a d a m a r d1 9 0 6 年就曾用连续延拓方法证明了关于研中非线性方程组解的中心存 在定理同伦方法的思想简单：为推断所研究问题解的存在性，先选择与之相似的适当问 题，称为同伦映射，当参数取适当值时，同伦映射的解即为所研究问题的解确切地，视同 伦映射为含参数方程，当解为该曲线上一点，追踪该曲线，可以得到所需解上述论述表 明，同伦算法是解的存在性的一种构造性方法进一步，通过对同伦映射的解曲线的跟踪， 则可实际求出问题的解因而，同伦算法实际给出求非线性方程组的一种算法一路径跟踪 算法 同伦本身是拓扑学中的一个概念，自从1 9 7 6 年，k e l l o g g ，和y o r k e l i 利用微分拓扑 工具解决了同伦算法的全局收敛性问题，并用之给出了b r o u w e r 不动点定理的构造性证 明，于是引起了人们对同伦方法的重新研究接着s m a l e 发表了全局n e w t o n 法的文章 c h o w ，m a l l e t p a r e r 和y o r k e 利用他们构造的同伦给出了一系列重要定理的构造性证明 同时给出了可用的算法，此后同伦算法的研究蓬勃发展，几十年来，人们成功地把它用于 经济学、电子线路设计、自动控制、计算机辅助设计和制造等许多领域中，成为引人注目 的算法 同伦算法是证明非线性问题解存在性的有效方法，它可以表述成下列形式：若求非 线性方程组f ( x ) = 0 的解，首先选取一个易于求解的方程组c ( x ) = 0 ，然后构造一个 带参变量的映射h ( x ，芦) ( 称为同伦映射) ，使得a ( z ) 能连续形变到f ( z ) 即构造同伦 日：舻( 0 ，1 一舻满足 h ( x ，p ) = ( 1 一p ( s ) ) f ( z ) + p ( s ) g ( ) ，、 h ( x ，1 ) = g ( o ) ，日( o ，0 ) = f ( z ) 、。 在一定假设条件下，存在一维光滑流形( 髫( s ) ，弘( 5 ) ) ( 称为同伦路径) ，将g ( z ) 的解护与 f ( x ) 的解。+ 连接起来，跟踪这条路径就可以从z o 出发找到z + 应当指出，在非线性分析中利用同伦不变性证明解的存在性的经典方法是非构造性 的，它不构成算法1 9 5 3 年d a v i d e n k o 把这种方法改造成一种算法，称为参数微分法，其作 2 大连理工大学硕士学位论文 法如下：设h ( x ，肛) 充分光滑，并且h ( x ，p ) = 0 的解x ( p ) 是光滑曲线，则由h ( x ，肛) = 0 对p 微分得到 聪( z ，p ) 署+ 或( z ，p ) = 0 ( 1 2 2 ) u i 于是求z ( p ) 问题转化成求( 1 2 2 ) 满足初始条件x ( 0 ) = 。o 的解曲线，如果解存在，并且 达到卢= 1 ，那么就证明了f ( x ) = 0 有解，而且可以通过解微分方程( 1 ，2 2 ) 的初值问题 求得问题的解g a v u r i n 更进一步发展了这种思想，提出了所谓迭代法的连续模拟，而这 种模拟恰是形如( 1 2 2 ) 的微分方程的初值问题，这就是最早的同伦算法d a v i d e n k o 与 g a v u r i n 的工作，以及这以后的一系列研究都只考虑了局部收敛同题，即仅当假定。o 充 分接近解时，才能证明z ( p ) 存在，并且当p 一1 时，x ( p ) 一 同伦映射有多种形式，常用的同伦有如下几种： 不动点同伦：h ( x ，肛) = ( 1 一p ) f ( z ) + p ( z 一。o ) 牛顿同伦：h ( x ，p ) = f ( z ) 一卢f ( 扩) 线性同伦：h ( x ，p ) = ( 1 一p ) f ( z ) 一卢g ( 。) 解有限维方程组f ( z ) = 0 的同伦算法按如下步骤获得解的存在性证明，并将计算解 的问题化为常微分方程的初值问题 视h ( x ，灿) = 0 为礼+ 1 维空间的确定区域昂x 0 ，1 ) 上的方程组，当h ( x ，肛) 关于 。，p 连续可微时，根据隐函数存在定理，如果对任何( 窖，肛) r n f 0 ，1 ) ，矩阵 日7 ( 。，肛) = ( 爿：( 。，p ) ，日：( z ，肛) ) 珥( 。川生d s + 晖( 茁川等= o ( 塞) 2 + ( 等) 2 “ c 竺蛳) 。 | j ( 塞，鲁) | | =1 ” 解凸规划问题的一种半内点法 我们可以通过数值跟踪解曲线来求解不同的曲线跟踪方法有不同的形式，但都具 有如下的基本结构： 1 初始化步；确定以下三个量： ( 1 ) 初始点( z ，t ) o = ( z ( m ，t o ) ； ( 2 ) 初始步长h ； ( 3 ) 容许误差e 。 2 预估步 利用各种预估方法，例如；f ( x ，t ) 在( 。，t ) 0 = ( 。( ，t o ) 处的一阶及二阶t a y l o r 展式 或3 次h e r m i t e 插值，或利用割线公式，得到预估点 ( z ，t ) 1 = ( 。( ，t 1 ) 3 校正步： 以( z ，) = ( z ( ”，t 1 ) 为初值，利用迭代方法产生一个序列 ( 。，) t ) 警l ，使( z ，t ) + = ( 。，t ) k 为f - 1 ( o ) 中的点的近似且其误差不大于如果迭代不收敛，则缩小步长转回预 估步 4 调换步： 根据某判别准则，若( z ，t ) + 满足要求，则置( z ，t ) 0 = ( z ，t ) + ，并调整步长h ，否则缩 小步长转预估步。 5 校验步： 如果( z ，) 。达到目标点，则停止否则转预估步。 1 3 预备知识 下面给出本文用到的一些基本定义和定理 定义1 3 1 设映射f ：dcj p r ，g o d ，如果存在线性映射l ：曰“一r “，使得 l i m 。螳盟掣 胛j 一0 | | | 则称f 在z o 处可微这里i l 是欧式空间的通常范数，h 一0 表示向量依范数趋于零 此时易验证线性映射；是唯一的，称为f 在z o 处的导映射，记为d l o 4 大连理工大学硕士学位论文 定义1 3 2 如果映射f ：dcr ”一舻在定义域d 中每点都具有r 阶连续偏导 数，则称f 为映射：如果对人一个正整数r ，映射f 是映射，则称f 是光滑映射 特别地，光滑映射在其定义域内的每一点处都是可微的 定义1 3 3 ( i n 性) 设f ：dc 曰“+ r “是光滑映射，对任意y r ”，记f _ 1 ( ) 为y 在映射f 下的逆象，即f _ 1 ( ) = z df ( z ) = 可) 对d 中的某一点x o ，如果 f 在z o 处的j a c o t ，i 矩阵笨( 。o ) 行满秩，则称x o 是映射f 的正则点若扩不是映射 f 的正则点，即映射f 在护处的d a c o b i 矩阵行降秩，则称x o 是映射f 的临界点设 y o 毋，如果所有z o f 一1 ( o ) 都是f 的正则点，则称y o 为映射f 的正则值；如果y o 不是映射f 的正则值，亦即存在护f - 1 ( y o ) 使得护是映射f 的临界点，则称y 。为映 射f 的临界值特别地，如果y ogf ( d ) = f ( z ) l z d ，即y 。r “f ( d ) ，则y o 是 映射f 的正则值 定义1 3 4 设x 、y 分别是两个欧氏空间中的子集，如果映射f ：x y 是双射， 且f 与f 的逆映射f _ 1 都是光滑映射，则称f 是x 到y 的一个同胚微分如果这样的 同胚存在，则称x 与y 是微分同胚的如果f 给出x 中点z o 的某个邻域到l ，中f ( x o ) 的某个邻域的微分同胚，称映射f ：x 一】，在x o 点处是局部微分同胚；如果f 在x 的 每一点处是局部微分同胚的，则称f 是x 与y 的一个局部微分同胚 定理1 3 1 ( 反函数定理) 设f ：r ”一印在z o i n t ( d ) 处有强f 导数，f ( x o ) 非 奇异则f 在。o 处为局部同胚映象，并且如果u 是z o 的任一开邻域，f 在其上是一对 一映象，r ，是f 对u 的限制，那么耳，在s ( x o ) 处有强f 一导数且 ( f 5 1 ) 7 ( f ( 扩) ) = f7 ( 护) 一1( 1 3 ) 又若f 7 在z o 的开邻域u 内存在且连续，( 艺一1 ) 在f ( z o ) 的一个开邻域内存在且连续 隐函数定理是反函数定理的推广隐函数是讨论代参数的非线性方程，我们可将彤 视为参数所在的空间隐函数定理是研究参数方程的基本工具 定理1 3 2 ( 隐函数定理) 设f ：dcp 。r p 一舻在点( x o ，y o ) 的开邻域d ocd 上连续，f ( 一，y o ) = o ；又设0 1 f 在点( x o ，y o ) 存在且是强的( 或者0 1 f 在( 护，y o ) 的一个 邻域内存在，并且在( x o ，y o ) 处连续) 且0 1 f ( x o ，y o ) 非奇异则分别有。o 与y o 的开邻域 s l 舻，岛r p ，使得对任何y ，方程f ( x ，y ) = 0 有唯一解z = h ( y ) s 1 ，并且 映象日：岛一r “是连续的此外，若a 2 f 在( x o ，y o ) 存在，那么，日在y o 处是f 一可导 的，且 h ( y o ) = 一 0 1 f ( x o ，口o ) 。1 0 2 f ( x o ，g o ) 5 解凸规划问题的一种半内点法 定义1 3 5 设x 是只1 的一个子集，如果对任意z x ，存在x 在x 的一个邻域 ycx ，使得y 与钟的一个开集微分同胚，则稚x 是k 维光滑流形若光滑流形的x 子集y 也是光滑流形，就说y 是x 的子流形 定理1 3 3 ( 逆象定理) 设x 和y 分别是k 维的和f 维的光滑流形，k f ，f ：x ，y 是光滑映射，如果y 是映射f 的正则值，则f o ( 可) 或者是空集，或者是x 中的k 一2 维 子流形 特别地，当k f = 1 时，_ 1 ( ) 是一维光滑流形，f - 1 ( ) 是由简单的光滑曲线组成 定理1 3 4 ( s a r d 定理) 设x 和y 是光滑流形，k f ，f ：x _ + y 是光滑映射记 _ d 是f 的临界点集，则f 的临界点集f ( d ) cy 在y 中的测度为零 定理1 3 5 ( 参数化s a r d 定理) 设ucj 与vcr q 是非空开集f ：u xv ，f p 为伊( uxv ) 类，其中r m a x ( o ，佗一m ) 如果0 r m 是f 的正则值、则对几乎所有 的点u v ，0 是限制映象f ( ，口) ：u 一r m 的正则值 6 大连理工大学硕士学位论文 2 解凸规划问题的组合同伦算法 2 1 组合同伦内点法 1 9 4 9 年，g b d a n t z i g 提出了用于求解线性规划问题的一个有效方法一单纯形方法 单纯形算法是从约束区域的一个顶点走到另一个顶点，不断改进目标的函数值，最后走 到最优解1 9 7 9 年，l g k h a n c l f i a n 证明了与单纯形根本不同的“椭球法”单纯形法采 用指数的逐次迭代来寻找一个最优解，椭球法则在一个多项式时间内找到线性规划的一 个最优解遗憾的是虽然在椭球法理论上保证了多项式时间的存在性，但是大量数值计算 表明在实际问题上，椭球算法在计算不比单纯形方法优越 1 9 8 4 年，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 多年里，学者们对k a r m a r k a r 的算法进行了广泛深入的研究，一些新的变 型算法相继出现，对其分类方法有很多在实际应用方面一般有以下三类：投影尺度法 ( p r o j e c t i v es c m i n gm e t h o d s ) ；仿射尺度法( a f f i n es c a l i n gm e t h o d s ) ；路径跟踪法( p a t h f o l l o w i n g 又称中心跟踪跟踪法) 1 9 8 6 年，g i l le ta l 首先证明了k a r m a k a r 算法本质上等价于对数障碍函数法，并给 出一种实用的内点法把内点法与利用障碍函数的路径跟踪算法联系在一起，出现了所谓 的内路径跟踪方法( 内点同伦算法) 由于极值问题没有同伦不变性，因此同伦算法一般用 于其一阶必要条件求解，无约束优化问题可以直接转化成方程组求解，但对于约束优化问 题，问题就困难了，因为约束优化问题的一阶必要条件( k k - t 系统) 既包括等式又有不 等式 考虑如下非线性规划问题 记 v ，( 。) = ( ，7 ( z ) ) t 为f ( x ) 的梯度； v g ( x ) = ( v 9 1 ( z ) ，( z ) ) ； n = z 彤：肌( 。) o ，1 i m ) 为可行域 7 ( 2 1 1 ) m 功 一 八功骞咖 解凸规划问题的一种半内点法 q o = z r n ：肼( 。) 列满秩的条件下：利用法锥 条件证明了非凸规划的大范围收敛性同伦f 2 1 8 ) 的显著优点不要求解集有界性和对数 障碍函数的一致凸性，这改进了g a x c i a 和z a n g w i l l 和中心路径同伦的结果 定理2 1 2 ( 1 7 1 ) 若，和虮是二次连续可微的凸函数并且伊非空，那么( 2 1 7 ) 的 解集 ( 。( 肛) ，p ) ：p ( 0 ，1 ) 是q o ( 0 ，1 】上的一条光滑曲线，且有l i m 。一o ，( z ( p ) ) = i n 却，( z ) 特别的，当( 2 1 1 ) 的解集非空有界时，忙江) ：p ( o ：i 】) 有界且芦一0 时 其聚点是( 2 1 1 ) 的解 2 2 动边界组合同伦方法 对于内点法，都要求一个初始可行点进行迭代最近，于波、商玉风 2 8 】提出动边界 组合同伦算法，该算法取? 肖了初始点必须为内点的限制，并能够求解更广泛的非凸规划问 题 动边界组合同伦方程为： 啪，牡一蒜苗鬈鬻黼葛二魏叩州，) = 0 1 。f 2 2 1 1 其中y = d i a g ( y ) ，y ( o ) = d i a g ( y ( o ) ，扛【，g ( o ) 曰4 r m ，+ ，e = ( 1 ，1 ) ? 舻， e = d i a g ( 0 1 ，e m ) ， 忙r 描棚 q ( t ) = 。i 函( 。) 一t 吼( 肌( z ( o ) + 1 ) 0 ，i = 1 ，m ) ，t 0 ，1 ， n o ( t ) = 。玑( 。) 一t o i ( g i ( x ( o ) + 1 ) 6 ， n ( t ) = ( 卜j ) 4 5 ( o ，1 ) 【o ，t d 吼： 0 肌( z ：? 0 j i ：1 ，m i1 ，q d x ( o ) 0 ， 记 n ( t ) = z i 吼( z ) 一a ( t ) o i ( g i ( x ( o ) + 1 ) 0 ，i = 1 ，m ) q o ( t ) = x l g t ( x ) 一n ( t ) 臼；( 肌扛o ) + 1 ) 0 ，i = 1 ，m ) a q ( t ) = a ( t ) n o ( ) ， ，( z ，t ) = i ( 1 ，m ) i 肌( z ) 一。( t ) 日。( 吼忙o ) + 1 ) = o ) 0 ，1 ， 0 ，1 ， 0 ，1 】， 0 ，1 t 对于任意给定的( 口( 0 1 ，可( o ) 尼。r m + ，h ( x ，可，t ) 的零点集记为h 一1 ( 0 ) ，即 h 一1 ( o ) = t ( 0 ，1 ，。q ( t ) ，y r ? ：h ( x ，y ，t ) = o ) 3 2 同伦路径存在性和收敛性证明 为了证明同伦路径的存在性和收敛性，我们先给出如下假设和引理 假设条件1 n o 非空( s l a t e r 条件) 1 3 堡些塑型塑翌塑二壁堂直盛蓬一 命题3 2 1 ( 1 2 2 j ，t h 5 3 4 ) ：若仇扛) 0 = 1 ，m ) 是凸函数，则n o 非空的充 要条件是：妇a q ， v 肌( z ) ，i ( z ) ) 是正独立的，即如果e a 。v 毋( z ) = 0 ，且 t e t zj ，0 ( i ，( 。) ) ，m i 】必有a i = 0 ( i ，( z ) ) 3 2 1 可行集有界 引理3 2 1 设，( z ) ，肌( z ) ( i = 1 ，m ) 是至少二次连续可微的凸函数，假设条件l 成立，则日一1 ( o ) 是一条通过点( z ( 0 ) ，v ( ，1 ) 的可以以t 为参数参数化的光滑曲线，记为 r 其中 于是 a = ( 1 一t ) ( v 2 ，( z ) + v 2 9 ( z ) 可) + t i b = ( 1 一t ) v 9 ( z ) ， c = y v g ( x ) t d = d i a g ( g ( x ) 一( t ) 0 ( 夕( z ( o ) ) + 1 ) ) d e t 嘭，= d e t ( ：一b ，d 。1 ) ( g ad b ) = d e t c a 一日。一1 g ，d e t 。 当t ( o ，1 ，z n o ( t ) ，y r m + 时，若血( t ) = 0 ，由0 的选取及同伦方程第二式 y g ( x ) 一t y ( o ) 0 ( o ) 一0 ( g ( z ( o ) ) + e ) ) = 0 知9 ( z ) 0 ，g ( z ) 一口( t ) e ( g ( z ( o ) + e ) 0 ， 知a b d 一1 c 为正定矩阵，d e t d 0 ，从而d e t 娥，。0 ，即0 是h ( x ，y ，t ) 的正则 值由( z ( 0 l ，( o ) 是h ( x ，y ，1 ) = 0 的唯一解和隐函数定理，可知h 。( o ) 是一条通过点 ( z ( 0 1 ，”( o ) 11 ) 的光滑曲线 u 定理3 2 。1 设，( 茁) ，吼( z ) ( i = 1 ，m ) 是至少二次连续可微的凸函数，假设条件 1 成立，映射h 由( 3 1 1 ) 定义对任给的( 。( 0 1 ，可( o ) 尼3 r m + ，h 1 ( o ) 是一条通过 点( 。( 0 ) ，可( ，1 ) 可以以( 0 ，1 】为参数参数化的有界光滑曲线当t 一0 时，h 1 ( o ) 的 极限点记为( z + ，矿，o ) 则( 矿，y + ) 是( 2 1 2 ) 的解，是( 2 1 1 ) 的最优值，y + 为相应的 l a g r a n g e 乘子 则 阵 矩bh 的 ， ，、 哪 口日d 于 a e 关i | | 玑 ，州 蟊 h h 示表 ”y z 嘭 甩明证 使得 大连理工大学硕士学位论文 证明：假设( 。+ ，y + ，t + ) 是曲线f 的另一端的极限点，则存在点列 ( z ( 舢，( ，“) ) b + ：o o 。 ( 1 一“) ( v f ( x ( 2 ) + v g ( x ( 。) 可( ) + t k ( 。( ) 一z ( o ) ) = 0 y ( k ( g ( 。( ) 一凸( 札) e ( g ( 。( o ) + e ) ) 一t k y ( o ( 口( z ( o ) 一e ( 9 ( 。( o ) + e ) ) = 0 ， 且( 。( ，可( 剐，t k ) 一( x + ，y + ，圹) 那么只有以下几种情况可能发生： ( i ) t + = 1 ，z + q ( 1 ) ，y + 艘； ( i i ) t + 0 ，1 ) ，i i x l f = + o 。，+ r ? ； ( i i i ) t + o ，1 ) ，x + n ( t + ) ，j l y + | | = + o 。； ( i v ) r ( 0 ，1 ) ，矿o a ( t + ) ，y + 蜀并且l i x + | | + o 。，i l y + | | + o 。； ( v ) t 4 ( 0 ，1 ) ，z + n ( t + ) ，l i x + | | + 。o ，l 矿| | + o o ，存在i ( 1 ，m 使得拼 ( v i ) t + = 0 ，矿n ，y + 砰并且i i x 4 | j + 。，j l 矿0 扩 p + = 圹且 矿n 矿丑 果成如不 呲盛 十 k z 鲰 v k 0 | i z 吼 v 0 m 呲 解凸规划问题的一种半内点法 其中拶是由讲。10 ，( 矿，t + ) ) 所构成的向量则 l = 1 ，a t20 ，i l ( x + ，t + ) 方程( 3 2 3 ) 左右两端同除1 | 尹忆并令k 一+ o o ，则有 f 九v g ( x + ) = 0 i e l ( g 。，t + ) 这与命题3 2 1 矛盾，表明( i i i ) 不能发生 3 2 2 可行集无界 对于可行集无界情形，我们先给出如下假设： 假设条件2 x = 蚓，( z ) s ，( 牙) ，g ( x ) o ) 有界，即3 m ，s t z x ，忪| | m 由假设条件2 可以得下面引理： 引理3 2 2 设，( 口) ，吼( z ) ( i = 1 ，m ) 是至少二次连续可微的凸函数，且假设条件 1 、2 成立，则由h ( x ，y ，t ) = 0 所确定的光滑曲线f 上的点争分量是有界的 证明：假设存在r 上的点列 ( z ( 妣，可( ，“) ) 酱，当k 一+ o c 时，1 1 t ( ) | 1 一十。 由同伦映射( 3 1 1 ) 有 ( 1 一t k ) ( v ，( z 砷) + v 9 ( 。砷) f 砷) + t k ( z 砷一z 。) ；o ： f 3 2 4 1 y ( 2 ) ( 夕( z ( 2 ) 一n ( “) e ( 9 ( z ( 砷) + e ) ) 一y ( 0 ( g ( z ( ) 一e ( g ( z ( o ) + e ) ) = 0 ， 、 因为i i x ( 2 | | 一+ o o ，故j i x ( 。| f 隹x ，结合方程( 3 2 4 ) 的第二式有 由f ( x 1 为凸函数，则有 即 ， ) ，扛) + 一z ( ) t v ，( z ( ) ( 岳一z ( ) t v f ( x ( ) ) 0 在( 3 2 4 ) 一式两端同时左乘( z ( ) 一圣) ( 其中击q o ) ，有 ( 3 2 5 ) ( 1 一“) ( z ( 七) 一量) t ( v ，( z ( 七) + v g ( z ( ) 可( ) + “( 。( ) 一圣) t ( 。( 七) 一茁( o ) = 0 ，( 3 2 6 ) 1 6 查堡里三查兰堡主兰垡堡塞 所以 首先有 | i 。( “) 一。( o 1 1 2 一lj 圣一z ( o 1 1 2 2 ( z ( ) 一圣) t ( z ( 砷一。( o ) ) = | | 。( ) 一z ( o 1 1 2 + ( z ( ) z ( o ) r ( 亩一z ( q ) 一i l 圣一z ( o 1 1 2 一扛 ) 一圣) t ( z ( ) 石( 0 1 ) = 扛( 一z o ) t ( 。( 七) 一。( 0 ) 十童一z ( ) 一f l 峦z ( 0 ) 1 1 2 一( z ( ) 一士) ? ( z ( 血) 一z ( o ) = ( z ( 后一z f ) t ( 圣一z f o ) 一f 圣一卫( o ) f f 2 一扛( 七) 一圣) 丁( 。( 七) 一z ( o ) = ( 。( ) 一圣) t ( 士一。( o ) ( z ( 七) 一岔) t ( z 【 ) 一。( o ) ) = ( 。( ) 一岔) t ( 圣一z ( 2 ) n ；( 1 l z ( 埘一z ( 。1 1 2 一n 2 - x ( 。) i i 。) ( z ( 砷一童) t ( 茁( 砷一。( 。) 改写方程( 3 2 6 ) 为 ( 1 一缸) ( z ( ) 一牙) r v f ( x ( 2 ) ) = 一( ( 1 一缸) ( 。( 耐一圣) t v g ( x ( 2 ) 可( 七+ t k ( x ( ) 一畲) r ( 。( 砷一z ( o ) )( 3 2 7 ) 札国( 茁。) 一 ( 9 ( z ( 。) + e ) ) t ( 。) 一( 9 ( 童) 一n ( 如) e ( g 扛。) ) + e ) ) t 掣( q 由g ( 仝) o 及0 的定义，得到夕( 圣) 一a ( t k ) e ( g ( x ( o ) ) + e ) 如( 夕( z 。) 一e ( 夕( 。( 。) + e ) ) ，一 f 3 2 9 ) ( 3 2 9 ) 代入( 3 2 7 ) ，得 ( 1 一如) ( ( ) 一圣) t v f ( z ( 女) ) 一t k ( 1 一如) ( g ( z ( 。) 一 ( g ( 。( 。) + 已) ) t ( 。j 一 如( 1 因为“( 0 ，1 ，当忙2 l i 一+ 。时，有 ( 。( 。) 一圣) t v ，( z ( ) 0 1 7 z ( o ) | j 2一忪一。( o ) ， ( 3 2 1 0 ) ( 3 2 1 1 ) 解凸规划问题的一种半内点法 ( 3 2 1 1 ) 式与( 3 ，2 5 ) 式矛盾 口 类似定理3 2 1 ，利用引理3 2 2 ，我们有如下无界情形收敛性定理： 定理3 2 2 设，( z ) ，m ( z ) ( i = 1 ，m ) 是至少二次连续可微的凸函数，假设条件 l ，2 成立，映射h 由( 3 1 ，1 ) 定义对任给的( 卫( 叭：笋( o ) ) r n 冠，h 一1 ( o ) 是一条通过 点扛( “，g ( m ，1 ) 可以以te ( 0 ，1 为参数参数化的有界光滑曲线当t 一0 时，日一1 ( o ) 的 极限点记为( 。+ ，y 4 ，o ) 则( x + ，y ) 是( 2 1 2 ) 的解，x 是( 2 1 1 ) 的最优值，y + 为相应的 l a g r a n g e 乘子 3 3 算法描述 酬胁瓤圳一o ， ( 3 3 1 ) ( 3 3 2 ) 并且，如果扛( s ) ，萝( s + ) ，t ( s + ) ) 是( 3 ，1 1 ) 的解，则有t ( s + ) = 0 时如( s 4 ) ，影( s + ) ) 是( 2 1 2 ) 的解 我们采用预估一校正法数值跟踪同伦路径，具体算法过程如下： 令枷= = ( z ，y ) r m ，u ( o ) = ( 。( o ) ，可( o ) ) q ( 1 ) s t e p0 ：给出初始点( 叫( 0 1 ，t o ) ，步长h o ，0 d o ) 构造动边界组合同伦 = ( 删如低( 1 - t ) 拶( c + 哟a 州t y ( t ，二并 勰卅m ， ( 3 4 2 ) 计算上式第二式 1 0 ) 卜z 1 ( ) 一t t ? l ( 1 一z o ) ) + t 陋( 0 ) 可 0 + 口i 甜( 1 一。p ) 】= of 34 灿 i 耽( ) + 一z 2 0 ) 一t 目。( 1 一。笋) + 陋妒如+ 目2 9 5 。( 1 一。严) ：o 、“。 把( 3 4 。3 ) 式代入( 3 4 2 ) 得第一式解得 t x l ( t ) 2 + b l x l ( t ) + c 1 = 0 t x 2 ( t ) 2 + 6 2 2 2 ( ) + c 2 = 0 ( 3 4 4 ) 、， 堡鱼塑型囹墨堕= 登兰堕生鲞一 其中 6 1 ：1 一t t z ；0 + t 2 6 1 ( 1 一。i o ) ， 。1 一一( 卜t ) t 石p + ( 1 _ z ) 州1 一。陬1 一) 一t 2 9 - z ( 0 )