（运筹学与控制论专业论文）不等式约束线性规划问题的一个内点算法.pdf

摘要 本文将仿射尺度法与路径跟踪法相结合，提出个求解线性规划问题的内点算法其 中对约束矩阵进行l u 分解，把不等式约束同题化为标准问题，并保持矩阵的稀疏性新算 法通过求解一系列障碍子问题，其可行域向最优解集收缩，有望减少迭代次数，提高计算 效率 初步的数值试验表明，新算法优于仿射均衡尺度法和路径跟踪法，看来对大规模问题 的求解有其潜在优势，是个有希望的算法 关键词：线性规划，不等式约束，内点算法，仿射均衡尺度，路径跟踪 a b s t r a c t t h i sp a p e rp r o p o s e sa ni n t e r i o rp o i n ta l g o r i t h mf o rs o l v i n gl pp r o b l e m sb yc o m b i n i n go f t h ea f f i n e - s c a h ga l g o r i t h ma n dt h ep a t h - f o l l o w i n ga l g o r i t h m i tu s e st h el u - d e c o m p o s i t i o no f t h ec o n s t r a i n tm a t r i xt ot r a n s f o r mt h el pp r o b l e mw i t hi n e q u a l i t yc o n s t r a i n t st ot h es t a n d a r d p r o b l e m ，w h i l em a i n t a i n i n gs p a r s i t y i ts o l v e sas e r i e so fb a r r i e rs u b p r o b l e m sw h o s ef e a s i b l e r e g i o n sc o n t r a c t st o w a r dt h es e to fo p t i m a ls o l u t i o n s i ti se x p e c t e dt h a tt h ep r o p o s e da l g o r i t h m r e d u c e st h en u m b e ro fi t e r a t i o n sr e q u i r e da n di sh e n c eo fh i g h e re f f i c i e n c y t h ep r e l i m i n a r yc o m p u t a t i o n a le x p e r i m e n t ss h o wt h a tt h en e wa l g o r i t h mi ss u p e r i o rt o e i t h e rt h ea f t m e - s c a l i n ga l g o r i t h mo rt h ep a t h - f o l l o w i n ga l g o r i t h m t h en e wa l g o r i t h ma p p e a r s t ob ep r o m i s ef o rs o l v i n gl a r g e - s c a l el pp r o b l e m s k e y w o r d s ：l i n e a rp r o g r a m m i n g ，i n e q u a l i t yc o n s t r a i n t ，i n t e r i o r - p o i n ta l g o r i t h m ，a f f i n e s c a l i n g ，p a t h - f o l l o w i n g 东南大学学位论文 独创性声明及使用授权的说明 一、学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果尽我所知，除了文中特别加以标明和致谢的地方外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的 材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示了谢意 二、关于学位论文使用授权的说明 锄：洱晰一7 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文本人电子文档的内容 和纸质论文的内容相一致除在保密期内的保密论文外，允许论文被查阅和借阅，可以公 布( 包括刊登) 论文的全部或部分内容论文的公布( 包括刊登) 授权东南大学研究生院办 理 签 名：阻导师签名嘲删 第一章引言 1 9 4 7 年，g b d a n t z i g 【9 ，1 0 l 提出了线性规划模型和单纯形方法，标志着线性规划学 科的创立，可以看作是线性规划发展史上的第个里程碑用单纯形方法求解线性规划问 题般是很有效的，在实际中获得了广泛的应用但1 9 7 2 年，美国学者k l e e 与m i n t y 【2 0 】 发现在最坏的情形单纯形算法所需迭代次数是指数的，会使求解大规模问题的效率大大 降低 许多学者因而致力于寻找求解线性规划问题的多项式时间算法1 9 7 9 年，k h a e h i y a n 【1 9 】在非线性规划的椭球方法的基础上，提出了求解线性规划问题的第个多项式时间算 法( 椭球算法) ，被看作是线性规划理论的个重大突破，被视作线性规划发展史上的第二 个里程碑可惜，不久人们就发现它的实际计算效果并不理想，远远不如单纯形算法 1 9 8 4 年，k a r m a r k a r 【1 8 】提出一个多项式时间内点算法与主元算法不同，内点算法 的迭代点列不是沿可行域边界，而是沿其内部逼近最优解k a r m a r k a r 算法不仅在理论上 比椭球算法有更低的多项式阶，且在大规模稀疏问题上的数值效果超过了传统的单纯形算 法这一突破被看作线性规划发展史上的第三个里程碑，引起学术界的广泛关注，激发了内 点算法的研究热潮t o d d 、b u r r e l l 、m e g i d d o 、g i l l 、g o n z a g a 、r o s s 、b a r n e s 、a d l e r 、v a n d e r b e i 【2 _ 4 ，2 1 ，4 3 ，4 4 】等众多学者多方面的研究发展了三大类内点算法第一类是势函数投影变 换方法( 如k a r m a r k a r 算法) 每步迭代，先作投影变换，将迭代点变换到可行域的中f t ，然 后在中心对势函数使用最速下降方法第二类是仿射尺度法每步迭代，先作仿射尺度变 换，然后使用最速下降法，再返回到原空间第三类是( 中心) 路径跟踪法。中心路径”的 概念最早是由h u a r d 和s o n n e v e n df 1 7 】提出；1 9 8 5 年g i l l 与m u r r a y 【1 4 】等学者发现对线 性问题可用非线性规划中的内点障碍函数法求解这个结果引起了学术界的极大兴趣，并 迅速加以推广，形成了一类路径跟踪法 潘平奇、胡剑峰和李琛提出的求解标准线性规划问题的可行域收缩内点方法，在数值 试验中有很好的表现【3 6 】本文将仿射尺度法与路径跟踪法相结合，提出个求解不等式 约束线性规划问题的内点算法其中对约束矩阵进行i 。u 分饵把不等式约束问题化为标 准问题，并保持矩阵的稀疏性该算法通过求解一系列障碍子问题使其可行域向最优解 东南大学硕士学位论文第章引言 2 集收缩，有望减少迭代次数，提高计算效率 本文中除特别说明以外，将使用如下符号和记法； 矩阵用大写的英文字母表示，如a 、b 、l 、u 等 向量用小写的英文字母表示，如a 、b 、c 等 r n n 维实向量空间，本文中向量均指列向量 胛黼仇xn 阶实矩阵空间 r a n k ( a )矩阵a 的秩 向量的第j 个分量 e 第i 个分量为1 的单位向量 e 元素均为l 的列向量 一 第k 次迭代后得到的向量 ， 矩阵或向量的转置 v f ( x )，( z ) 的梯度 v 2 f ( x )，( z ) 的h e s s i a n 矩阵 矩阵或向量的2 一范数 i i 数的绝对值 j r 单位矩阵 o 空集 本文的基本框架如下：第二章简要介绍相关的基础概念，求解标准线性规划问题的仿 射均衡尺度法，路径跟踪法，以及初始内点的寻求方法第三章给出不等式约束l p 新的 内点算法第四章报告了我们的数值试验结果，将新的算法与仿射均衡尺度法，路径跟踪 法进行了比较和分析，最后总结本文的创新点并讨论进步的研究方向 第二章基础知识 。本章首先简要地回顾线性规划一些相关的基本概念，然后简要介绍求解线性规划问 题的仿射均衡尺度法，路径跟踪法以及初始内点的寻求方法，其中的某些思想和技巧将运 用到新算法中 2 1 基本概念 作为本章的开始，让我们先回顾一些相关的基本概念 考虑标准线性规划问题： m i n ，z ( 2 1 a ) s t a x = b ( 2 1 b ) z 0 ( 2 1 c ) 其中a 矽黼，r a n k ( a ) = m ，c 、z r n ，b ，并且c 、b 以及a 的行与列均为非零向 量c t x 称为该线性规划问题的目标函数，式( 2 1 b ) 和( 2 1 c ) 称为该问题的约束条件 定义2 1 1 在线性规划问题( 2 1 ) 中，满足约束条件( 2 1 b ) 和( 2 1 c ) 的向量z = ( x l ，2 ：2 ，z 。) 丁称为( 2 1 ) 的可行解或可行点所有可行点组成的集合称为( 2 1 ) 的可行 域，记作： d = z r aia x = b ，z20 )( 2 2 ) 其中使得目标函数取得最小值的可行解称为( 2 1 ) 的最优解 定义2 1 2 我们定义可行域d 的内部为： d o = z r ” a x = b ，z 0 ) 若z d o ，则称z 为问题( 2 1 ) 的内点可行解，简称内点若向量z d 且z 至少有个 分量为零，则称z 为问题( 2 1 ) 的边界点 一般情况下，假设线性规划问题的可行域d ( 9 3 苎曼奎兰里苎兰丝坠叁丝兰 坠墅b 4 定义2 1 3 设矩阵a 行满秩，则a a r 可逆，称 p = i a t ( a a r ) 一1 a 为矩阵a 的零子空间中的正交投影矩阵 2 2 仿射均衡尺度法 仿射尺度内点算法的基本思想是：通过仿射变换，将当前迭代点移至充分远离可行域 边界的点，即利用仿射变换将当前内点矿映射到像空间中的点e ，然后从点e 沿着最速下 降方向在某个零空间的投影移动，且移动距离不超过1 ，以保证新的迭代点仍为内点，然后 再进行逆变换，在原空间中得到个改进的新内点解 对于线性规划问题( 2 1 ) ，假设有个内点一= x k = d i a g ( x ) = 引 o - o 0 ，我们定义对角阵 显然x k 是非奇异矩阵，则其逆矩阵) 1 存在考虑仿射尺度变换： y = x i l z( 2 3 ) 则问题( 2 1 ) 可变换为： m i n 矿秒( 2 4 a ) s t 而= b ( 2 4 b ) y2 0 ( 2 4 c ) 其中石= x a c ，a = a x k 易见仿射变换( 2 3 ) 是把正卦限映射到自身将x 。变换成向量e 从而离各个坐标平 面等距离，从某种意义上局部地均衡了各个变量的尺度如果e 点在五的零空间中沿着下 5 降方向移动不到1 的步长至新内点，则矿也在原空间中沿着下降方向得到个改进的内 点+ 1 因此，对于线性规划问题( 2 4 ) ，我们采取最速下降策略，选取负梯度方向一苔在 矩阵j j f 的零空间中的投影为搜索方向，即， 砖= 只( 一刁 ( 2 5 ) 其中的投影矩阵z r = 卜斧( 解) 一1 互= 卜x k a t ( a x ；a t ) 一1 a 虬 ( 2 6 ) 则搜索方向为t d ：= 一【，一凰a r ( a 磺a r ) 一1 a x k x k c ( 2 7 ) 在变换后的像空间中，从点矿= e 沿着呜的方向移动到个改进的新内点解矿+ 1 0 。 即： 矿+ 1 = 矿+ a k d k v 0 ( 2 8 ) 其中步长取为： 驴7 咧袁蛳 0 ，而+ 1 有个零分量z p l = 0 ，则z 七+ 1 为( l p ) 问题( 2 1 ) 的最优解 ( 详细证明见【4 9 】) 根据上述讨论，得出如下求解线性规划问题的仿射均衡尺度算法： 算法2 2 1 ( 仿射均衡尺度算法) 0 0 初始化给定一充分小的数e 0 ，令k = 0 ，找出初始内点；g o 0 ，使得a x o = b 1 0 计算对偶变量 u = ( a 瑶a r ) 一1 a 磙c 2 0 计算下降费用 s 七：c a t u k 3 0 检查最优性如果0 ，且对偶间隙e t x k s f ，停止，已得到问题( 2 j ) 的最 优解扩 4 0 求迭代方向 硝= 一s 七 5 0 检查无界性和目标函数值若砖0 ( 但磅o ) ，停止，问题( 2 j ) 无界；若 砖= 0 ，停止，问题( 2 j ) 已达到最优 6 0 计算迭代步长 o l k2 7 叫袁蛳 o ) 其中0 0 都有唯一的最优解 对于后一种情况，我们把唯一的最优解表示为z ( p ) ，且把曲线 z ( p ) i p 0 称为一条中心 路径m e g g i d o 进一步证明了当p ，0 时 z ( p ) + 矿，而矿为( 2 1 ) 的最优解之后一 些学者据此提出各种不同的障碍子问题从而产生了一类方法，统称路径跟踪法 下面主要介绍路径跟踪法的推导过程 对于任一给定的p 0 ，问题( 2 1 0 ) 的n e w t o n 搜索方向由解下面的二次规戈4 得到： m i n 去唯t v 2 ，扛) 叱+ 【v ，( z ) 】t 叱 ( 2 1 l a ) s t a 叱= 0( 2 1 l b ) 其中v f ( z ) = c p 义i l e ，v 2 f c x ) = p 肖2 ，故牛顿方向是在a 矩阵的零空间中极小化，( z ) 的二阶近似所得引入问题( 2 1 1 ) 的l a g r a n g i a n 函数： l ( z ，入，p ) = 吉v 2 ，( z ) 叱+ f v ，( z ) 】丁叱一a t ( a d ) 由最优性条件可得： p 叉i 2 叱一a 丁a p = 一( c p x f l e )( 2 1 2 a ) a 叱= 0( 2 1 2 b ) 求解( 2 1 2 ) 可得迭代点z 七的牛顿搜岩；方向1 ： 叱= 一去m 1 i 一扎以丁( a x ；a 丁) 一a x k ( x k c p e ) ( 2 1 3 ) 船 n：i p z， = 功八 蓦 东南大学硕士学位论文第二章基础知识8 我们比较n e w t o n 搜索方向( 2 1 3 ) 和原仿射尺度法的方向礁可知： d p 一1 “x k p k x k c + 托【，一讯矿( a x 矽) 一1 a x e e = 去讯呓+ x k p k e 前一项是原仿射尺度方向的线性组合，而后一项称为中心方向当p 一0 时，前个分量 就会无穷大因此，当，- _ 0 的极限方向就是仿射尺度算法的迭代方向 k a r m a r k a r 投影方法对于标准问题( 2 1 ) 产生的方向也是讯p k x k c 和x k p k e 的线性 组合，故也被称为是一种路径跟踪法算法的实现依赖于参数p 的选取g o n z a g a 在【1 5 l 中最初提出k i n - m a r k e r 投影算法等价于路径跟踪法，d f s h a n n o 和a n s u l n s t nb a g c h i 给 出了证明 4 1 1 下面给出路径跟踪算法： 算法2 3 1 ( 路径跟踪算法) 0 0 初始化令七= 0 ，给定一充分小的数 0 ，找出初始内点z o ，使得a z o = b ，置 p = 矿 i o 计算n e w t o n 迭代方向 = 一去【，一a 丁( a x ；a 丁) a x k ( x pp e ) 2 0 检验无界性如果d ：o 汜o ) 则问题化i ) 无界，停止若吐= 0 则问题 仁砂已达到最优，停止 3 0 计算步长 q e2 口中 - 赢i ( 畦) t o ) 其中0 q 1 为安全因子 4 0 迭代到新解 + 1 = 矿+ 口女畦 5 0 检验最优性 | ，t 一c 丁：i l 1 矿“ 否则k ：= k + 1 ，p 。+ 1 = 肚，0 0 ，则原问题( 2 1 ) 无可行解：如果问题( 2 1 4 ) 的最优值 r 个。 z “l = 0 ，则由问题( 2 1 4 ) 的最优解i 4 i 得到原问题( 2 1 ) 的一个初始可行解z 【0j 通常，在最初的时候，我们取虿= e r ”来构造辅助问题求得初始内点，即： ( 2 1 5 a ) 查童叁兰堕苎叁墅壑坠曼坠塑塑丝一 1 0 s t a x + ( 6 一a e ) x n + l = 6( 2 1 5 b ) o ，x n + l 0( 2 1 5 c ) 显然， ： 舻t 1 是辅助问题c 2 拍，的初始内点 因此，我们可以得到求初始内点的一阶段算法t 算法2 4 i ( 一阶段算法) o o 引入人工变量z 。+ 1 ，并构造辅助问题 1 0 置初值，x 0 = e ，七= 0 ，e = 1 0 一 2 0 计算辅助问题的最优值 3 0 若( 2 1 5 ) 有最优值且不等于零二则原问题无可行解，停止 4 0 若最优值等于零，则z 就是原规划问题的初始可行解 2 大m 方法 引入人工变量x n + 1 ，将原规划问题转化为以下形式： r a i nc t x + m x n + l ( 2 1 6 a ) s a x + ( b a e ) x 。+ 1 = b( 2 1 6 b ) z 0 ，z n + 1 之0( 2 1 6 c ) m 为给定的足够大的正数用内点算法求解，判断无界或者得到最优解z + 存在最优解当 且仅当z 。+ l = 0 ，所得最优解就是原问题的最优解由于实际计算时，大m 的取值难以确 定，且当m 取很大值时，计算稳定性差些，故多数商业软件的实现常采用两阶段法 第三章不等式约束l p 新的内点算法 3 1 基本思想 前面一章分别介绍了求解标准线性规划问题的仿射均衡尺度法和路径跟踪法实际 中存在大量的不等式约束最优化问题，本章我们将给出求解不等式约束线性规划问题的 基本思想，搜索方向的导出以及新的算法其基本思想是：通过对约束矩阵进行l u 分解 来减少问题规模，进而把不等式约束问题化为标准的线性规划问题，然后结合仿射均衡尺 度方法和路径跟踪方法，提出求解不等式约束线性规划问题的新的内点算法 3 2 搜索方向的导出 本节将介绍不等式约束线性规划问题内点方法的搜索方向的导出 考虑如下形式的不等式约束线性规划问题： r a i nc t x ( 3 1 a ) s a x b ( 3 1 b ) 其中a r m n ，b 驴，c 、ze 舻，且扫、c 以及a 的行与列均为非零向量，0 0 由于，u 一1 h l b 是常量，故求解上述问题等价于求解： r a i n 透r s t h 2 r = 6 1 r 0 ( 3 3 口) ( 3 3 b ) ( 3 3 c ) ( 3 4 n ) ( 3 4 6 ) ( 3 4 c ) 其中c l = 一 甲( u f l ) r c r ”，b l = h 2 b ，p 一” 通过上述转化，把不等式约束线性规划问题转化为标准问题我们对问题( 3 4 ) 进行 求解，在r 空间第k 个迭代点一处，增加新的含有目标函数的约束： 进而可构造障碍子问题 彳r + t m + l = 刁r + 6 6 0 ( 3 5 ) ( 3 6 0 ) m ra n n m 嘲 一 j rnm 其中a 1 为个给定的常数 令 s t h 2 r = b l 4 r + r m + l ：c f 一+ 6c ir + r m + l = i ，+ 6 r ，n + l 0 皂= 6 l =6 ) 尹= 其中百| 2 r ( m n + 1 ) ( m + 1 1 ，面，p n + l ，尹r ：r r i + 1 问题( 3 6 ) 可以转化为： r a i n 令 n n + l 0 暾= 俐曰2 尹= 匠，尹 0 ( 3 6 6 ) ( 3 蚴 ( 3 6 d ) ( 3 7 8 ) ( 3 7 6 ) ( 3 7 c ) 问题( 3 7 ) 是一个在q 七内求极小的规划问题，对目标函数求极小就是让每一个n “= 1 m + 1 ) 都增大，由新增的约柬( 3 5 ) 可知，r m + 1 增大可迫使问题( 3 4 ) 的目标函数 值下降两且r m + l 增量越大，问题( 3 4 ) 的目标函数值下降就越多极小化问题( 3 。7 ) 也就 是让n ( 江1 m + 1 ) 增大 并且希望r m + 1 增大得更陕 问题( 3 7 ) 的初始内点产= ( ( 一) r ，6 ) r ，考虑仿射变换： i ，= 或1 f + a一 矗 绍 m 崩 一 l l r ，j 东南大学硕士学位论文第三章 不等式约柬l p 新的内点算法 1 4 其中仇= 出叼( r ，馕，6 ) 障碍子问题可转化为t m m i n 一z n t k l i a + 1 ( 3 8 d ) i = 1 s t f i 2 d k v = h( 3 8 b ) v m + l 0( 3 8 c ) 关于t ，的搜索方向： 砖= ，镜d 。( 一v ，( e ) ) = ，霄2 d 。芭 ( 3 9 ) 其中正交投影矩阵仇= j 一夙扇t ( 扇磁岛t ) 一1 曰2 仇，芭= ( e t ，入6 ) t 故关于f 的搜索方向d t 本= ( ( d j ) t ，( 本) 。+ 1 ) t = d k p 露t d t 龟 砗就是问题( 3 4 ) 的迭代方向 引理3 2 1 如果c t z 在可行域内非常数，则乏1 不在虎的值域内其中乏l = d 七c 1 ，觑= h 2 d k ，d k = d i a g ( r k l ，r ，愫) 证明：假设1 在虎的值域内，那么存在向量r 1 r m ，满足觑1r 1 = 6 l ，即 d k h t r l = d k c l ，由于仇为对角线元素均大于零的对角矩阵，故c 1 = h 2 t r l 而i r = r t n 2 r = r 1 6 1 ，故巧r 为常数，z = c t u f l h ： 一印r 也为常数假设不成立，故结论成立 证毕 定理3 2 1 如果c t 2 ；在可行域内非常数，则本是问题( 3 4 ) 的下降方向，同时也使不 等式约束问题( 3 1 ) 的目标函数值下降 证明：易证日2 磷= 0 下面只证：彳雌 0 ，故只需证明( 仇) m + l ，州1 0 ，就有彳母 0 令 扇仇= h 2 d k o ) 圭占( 筹：) 仇= ，一仇霹( 疗2 犀霹) - 1 岛风 ：，一6 ( 之t ) ( 6 ( 嚣：) 占( 之t ) ) 一1 艿( ：) 。一) ( 薯。磐丘) 1 ( 掌：) 一比叫忘，翰端，。：) 其中 1 。 = - - - - - - = = ，= = - - - - - 一 l + a t 西一a r 玩1 ( 也或1 ) 一1 也矗 1 1 + 0 酬2 故( p 吼d ) m + 1 m + 1 = 1 7 - 由假设知丘不在膏2 的值域内，故l l p 篪西i i 0 ，故( 仇k + l 。+ l 0 ，故本为问题( 3 4 ) 的下降方向 由问题( 3 1 ) 、( 3 2 ) 、( 3 3 ) 、( 3 4 ) 之间的相互转化可知，不等式约束问题( 3 1 ) 的目标函 数值也下降证毕 定理3 2 2 如果砟o ，则问题( 3 4 ) 无下界，从而不等式约束问题( 3 1 ) 也无下界 证明：因为本0 ，故对任意步长进行迭代，下一步迭代点仍在定义域内又由定理 ( 3 2 1 ) 可知c 砟 0 故当步长无限增大时，问题1 3 4 ) 的目标函数值无限下降故问题 4 ) 无下界 东南大学硕士学位论文第三章 不等式约柬l p 新的内点算法一一一1 6 由问题( 3 1 ) 、( 3 2 ) ( 3 3 ) 、( 3 4 ) 之间的相互转化可知，不等式约束问题( 3 1 ) 的目标函 数值也无下界证毕 为确保迭代点是问题的可行内点，步长由下列给出： 妒q 乎 一扣 。) 其中0 0 当一与r 七+ 1 很接近时，有 l 刁一一i 一+ 1 i 一0 我们就可以认为达到最优点因此 ! 生! 二望! 二，一o 1 l c i _ r p 7 - - 一l - i i ” 可作为终止性条件 2 由定理( 3 2 2 ) 可知，磷0 可作为无界性终止条件 基于上述讨论，下面给出不等式约束线性规划新的内点算法： 算法3 3 1 ( 不等式约束线性规划新的内点算法) 0 0 令a 1 ，0 6 l ，0 a 0 1 0 对a 进行l 【，分解： a = l u = l ( 象) m 二n 2 0 寻找初始内点r o ，使得r o = 6 1 3 0 计算搜索方向本j 迭代 砖= ( 仇仇芭) t i = l ，m 4 0 若砟0 ，则问题无下界，停止否则转入5 0 5 0 确定步长： 一唧 一扣 。 r + 1 = r 七+ q k 砟 塞塞叁型坠塑垡堂皇里坠塑垂塑型堑墅塑塑匕1 8 6 0 若 计算： 停止 ，7 0 令k ：= k + 1 ，转入3 0 e z 七+ 1 = 町1 h l ( b - r 七+ 1 ) 第四章数值试验 4 1 数值试验及结论 前一章阐述了不等式约束线性规划新的内点算法的基本过程为了进步了解该算 法的实际表现，我们进行了初步的数值试验和比较本章将报告数值试验所得到的有关结 果，并对这些结果进行相应的分析 我们试验了如下三个程序： c o d ei l p l ：仿射均衡尺度算法 c o d ei l p 2 ：路径跟踪算法 c o d ei l p 3 ：新的内点算法 以上三个程序是用标准c 语言编写，在m i c r o s o f tw i n d o w sx p 操作系统上利用m i - c r o s o f tv i s u a l 环境进行编译和运行的数值试验所使用的计算机为i n t e l ( r ) p e n t i u m ( r ) 4 c p u3 0 0 g h z 的兼容机，内存5 0 4 m b y t e s ，机器精度3 2 位所有程序都采用一阶段方法求 解初始内点，求解迭代方向均使用了q r 分解，这三个程序均使用了尺度技术，其中的安 全系数都取为o 9 9 9 ，在i l p 2 中p o = 0 1 ，i l p 3 中a = 1 0 5 ，6 = o 0 1 这三个程序均采用稠 密的数据存储结构计算，且采用了相同的预处理过程计算运行时间所用的工具为v i s u a l c + + 6 0 的标准库函数 t i m e ，以秒为单位，不包括数据预处理的时间 我们测试了一组来自h t t p ：w w w n e t l i b o r g l p d a t a 的标准的1 2 个线性规划问题的对 偶问题，数据中的零元素比较多，为稀疏问题 表1 给出了用仿射均衡尺度算法( i l p i ) 测试1 2 个标准线性规划问题的对偶问题所 得到的结果表格的第一列列出的是标准线性规划问题的名称，第二、三、四列列出了问 题的规模( 分别是问题的行数m 、列数n 及行列数之和r e + n ) 第五、六两列分别列出仿 射均衡尺度算法总迭代次数和时间 表2 给出了用路径跟踪算法( i l p 2 ) 测试1 2 个标准线性规划问题的对偶问题所得到 的结果表格的第一列列出的是标准线性规划问题的名称，第二、三、四列列出了问题的 规模( 分别是问题的行数t n 、列数n 及行列数之和- n + n ) 第五、六两列分别列出路径跟 踪算法总迭代次数和时间 1 9 2 0 表3 给出了用新的内点算法( i l p 3 ) 测试1 2 个标准线性规划问题的对偶问题所得到 的结果表格的第列列出的是标准线性规划问题的名称，第二、三、四列列出了问题的 规模( 分别是问题的行数m 、列数1 1 及行列数之和r e + n ) 第五、六两列分别列出新的内 点算法总迭代次数和时间 然后我们对这三种算法分别测试1 2 个标准线性规划问题的对偶问题所得到的结果 进行了比较，其比较结果在表4 中列出，表格的第一列列出的是问题的名称，第二、三、四 列列出了问题的规模( 分别是问题的行数m 、列数及行列数之和m + n ) 第五、六两列 分别列出仿射均衡尺度算法( i l p l ) 与新的内点算法( i l p 3 ) ，路径跟踪算法( i l p 2 ) 与新 的内点算法( i l p 3 ) 总迭代次数之比和总时间之比 东南大学硕士学位论文第四掌数值试验 2 1 表1 t c o d ei l p l 数值结果 p r o b l e m仇n仃l + nt o t a li t e r st b t a lt i m e a f i r o2 73 25 92 10 0 2 s c 5 0 a 4 8 9 84o 0 3 s c 5 0 b5 04 89 87 3o 1 6 b l e n d7 48 31 5 71 70 1 3 s h a r e 2 b 9 6 7 91 7 52 4o 5 2 s c l 0 51 0 51 0 32 0 850 2 3 s t o c f o r l1 1 71 1 12 2 85o 2 3 s c a g r 71 2 91 4 02 6 92 90 6 4 i s r a e l1 7 41 4 23 1 61 72 5 3 s h a r e l b1 1 72 2 53 4 21 81 5 6 s c 2 0 52 0 52 0 34 0 8 5 25 9 4 l o t e l1 5 33 0 84 6 16 97 1 5 t o t a l1 2 9 71 5 2 22 8 1 93 3 41 9 1 4 东南大学硕士学位论文第四章数值试验 2 2 表2 t c o d ei l p 2 数值结果 p r o b l e mmnf l i t + nt o t a li t e r st o t a lt i m e a f i r o 2 73 25 91 8o 0 2 s c 5 0 a5 04 89 81 2o 0 3 s c 5 0 b5 04 89 82 0o 0 5 b l e n d”8 31 5 71 80 1 3 s h a r e 2 b9 67 91 7 51 70 3 1 s c l 0 5 1 0 5 1 0 32 0 81 3o 2 8 s t o c f o r l1 1 71 1 12 2 81 3o 2 7 s c a g r 71 2 9 1 4 0 2 6 91 60 4 1 i s r a e l1 7 41 4 23 1 61 62 3 8 s h a r e l b1 1 72 2 53 4 21 32 0 3 s c 2 0 52 0 52 0 34 0 82 63 0 4 l o t e l1 5 33 0 84 6 12 8 4 4 6 t o t a l1 2 9 71 5 2 22 8 1 92 1 01 3 4 1 2 3 表3 ：c o d ei l p 3 数值结果 p r o b l e mm 1 7 , m + nt o t a li t e r s t o t a lt i m e a f i r o2 73 25 97o 0 2 s c 5 0 a5 04 8嬲 2 50 0 5 s c 5 0 b5 04 89 82 2o 0 5 b l e n d 7 48 31 5 75o 1 6 s h a r e 2 b9 67 91 7 5 7o 2 2 s c l 0 51 0 51 0 32 0 850 2 2 s t o c f o r l 1 1 71 1 12 2 81 80 2 7 s c a g r 71 2 91 4 0 2 6 91 20 3 6 i s r a e l1 7 41 4 23 1 61 22 3 6 s h a r e l b 1 1 72 2 53 4 21 91 5 2 s c 2 0 52 0 52 0 34 0 82 61 7 8 l o t e l 1 5 33 0 84 6 14 55 5 4 t o t a j l1 2 9 71 5 2 22 8 1 92 0 31 2 3 5 东南大学硕士学位论文第四章数值试验 2 4 表4 ti l p l 与i l p 3 及i l p 2 与i l p 3 的数值结果比较 i l p l 。7 儿p 3i l p 2 i l p 3 p r o b l e m仇nm + nt o t a li t e r st o t a lt i m et o t a ii t e r st o t a lt i m e a f i r o2 73 25 93 0 01 0 02 5 71 0 0 s c 5 0 a5 04 8 9 8 0 1 6 0 6 0 o 4 8o 6 0 s c 5 0 b5 04 89 83 3 23 3 20 9 11 0 0 b l e n d 7 4 8 3 1 5 7 3 4 0 o 8 l3 6 0o 8 1 s h a r e 2 b9 67 91 7 53 4 32 3 62 4 31 4 1 s c l 0 51 0 51 0 32 0 81 o o1 0 52 6 01 2 7 s t o c f o r l1 1 71 1 l2 2 80 2 80 8 5o 7 21 0 0 s c a g r 71 2 91 4 02 6 92 4 21 7 81 3 31 1 4 i s r a e l1 7 41 4 23 1 61 4 21 0 71 3 31 0 1 s h a r e l b 1 1 7 2 2 5 3 4 2 o 9 51 0 30 6 81 3 4 s c 2 0 52 0 52 0 34 0 82 0 03 3 41 0 01 7 1 l o t e l1 5 33 0 84 6 11 5 31 2 9o 6 20 8 1 t o t a l1 2 9 71 5 2 22 8 1 9 1 6 5 1 5 51 - 0 31 0 9 东南大学硕士学位论文第四章数值试验 2 5 由表1 、3 可以看出，在这1 2 个问题中，对于迭代次数，其中8 个问题i l p i 明显多于 i l p 3 ，1 个问题持平3 个问题i l p i 略少于i l p 3 ；而迭代时间，其中8 个问题i l p i 明显多 于i l p 3 ，1 个问题持平，3 个问题i l p l 略少于i l p 3 由表2 、3 可以看出，在这1 2 个问题中，对于迭代次数，其中6 个问题i l p 2 明显多于 i l p 3 ，1 个问题持平，5 个问题i l p 2 略少于i l p 3 ；而迭代时间，其中6 个问题i l p 2 明显多 于i l p 3 ，3 个问题持平3 个问题i l p 2 略少于i l p 3 由表4 可以看出，对于总迭代次数，i l p l i l p 3 ，i l p 2 i l p 3 的值分别为：1 6 5 、1 0 3 ；对 于总的运行时间，i l p i i l p 3 、i l p 2 i l p 3 的值分别为，1 5 5 、1 0 9 可见，不等式约束线性规 划的新的内点算法在迭代次数和运行时间上比仿射均衡尺度算法i l p l 有明显的进步；但 是，i l p 3 和i l p 2 比较，差别不很明显，基本无法确定孰优孰劣目前我们只是进行了初步 的数值试验，还需要更多的数值试验去检验 4 2 本文的创新点和进一步的研究方向 一本文的创新之处在于： 1 新算法将仿射尺度法与路径跟踪法相结合，并引入可行域收缩技术，有望减少迭代 次数，提高计算效率 2 不等式约束添加松弛变量后，问题规模变为m ( m + 扎) ，而我们通过矩阵l u 分解化 为标准问题，其规模为( m n ) 仇，减少了2 r a n ，因而问题的规模大为减少；同时l u 分解也 很好地保持了矩阵的稀疏性 初步的数值试验表明，新算法与路径跟踪算法相比计算效果差别不大；但是，比仿射 均衡尺度算法有较高的计算效率，因此仍是个有希望的新算法 二进一步的研究方向： 1 目前我们仅证明新算法具有下降性质，对其进行完整的收敛性分析是个困难的课 题，将留待今后去完成 2 另外，目前所进行数值试验还很初步；新算法对于求解更大规模的问题表现如何， 有待采甩稀疏矩阵技术进一步试验同时如何确定参数 a 使赁：法有更高的效率? 目前尚 难回答也是需要进一步探究的问题 致谢 首先向我的导师潘老师致以最诚挚的谢意一直以来，潘老师在学习及生活各- - 1 - 7 r 面 都给予我无私的帮助和热情的关怀，使我的论文得以顺利完成潘老师不仅在学习和生活 上给予我无微不至的关怀，而且以渊博的知识，严谨的治学态度，敏锐的洞察力，坦荡的胸 襟以及谦逊的学者风范影响和教育着我，使我终身受益 感谢数学系各位老师在我的学习期间给予我的教导和帮助从他们那里，我学到了很 多知识，为本篇论文的完成打下了坚实的基础我还要感谢我的师兄、师姐，我的搭档他 们对我的论文的完成提供了全面的帮助 感谢我的父母，是他们的无微不至的培养与关怀使我长大成人，我要感谢他们在我硕 士期间的悉心照顾和理解支持! 衷，t ；- 的感谢在百忙之中评阅论文和参加答辩的各位专家，教授 参考文献 【1 li a d l e r ，n k a r m a r k a r ，m r e s e n d ea n dg v e i g a , d a t as t r u c t u r e sa n dp r o g r a m m i n gt e c h n i q u e sf o r t h ei m p l e m e n t a t i o no fk a r m a r k a r sa l g o r i t h m ，o r s aj o u r n a lo nc o m p u t i n g ，v 0 1 1 ，n o 2 ( 1 9 8 9 )