（运筹学与控制论专业论文）线性约束优化的仿射内点共轭梯度路径方法及其应用.pdf

中文摘要 摘要 最优化技术有着广泛的应用，本文着重讨论利用仿射内点离散共轭梯度路径解含有 线性等式与线性不等式约束的非线性优化问题及相关应用。 共轭梯度法是一种常用的最优化方法，它运算方便且仅需一阶信息，并且存储空间 小，在数值计算时具有相对的优势。目前，共轭梯度法非常适合求解大规模优化问题。 b u l t e a u 与v i a l 构造了无约束最优化问题的共轭梯度路径，其基本思想是将标准共轭方 向法应用于无约束优化目标函数的局部二次近似模型，得到一组共轭方向序列，共轭梯 度路径定义为该共轭方向序列的线性组合，从而得到一组连续的共轭梯度路径。但连续 的共轭梯度路径需要先构成整个共轭梯度路径，再进行搜索，从而很大程度上增加了计 算工作量。本文则通过构造离散的路径来避免此缺陷，理论上只需构造部分共轭梯度法 解每次迭代的近似二次模型，从而提高了算法的运行效率。 另一方面，鉴于原问题中同时含有线性等式与线性不等式约束，本文将其转化为等 式约束矩阵的零空间中的一个无约束优化问题来求解。将离散的共轭梯度法应用于零空 间中的近似二次模型，得到一组共轭方向序列，由共轭方向序列生成了共轭梯度路径。 本文通过构造仿射内点离散的共轭梯度路径解二次模型获得迭代方向，在此基础上 进行内点回代线搜索获得迭代。在合理的假设条件下，证明了算法的整体收敛性与局部 超线性收敛速率。最后本文经过m a t l a b 软件演算了部分标准测试题，通过数值结果表 明了算法的有效性。 全文分为四章。第一章简要介绍最优化的基本概念以及共轭梯度法的相关算法及性 质；第二章给出相关核心算法，并对其进行理论分析；第三章在合理的假设条件下，论 证了算法的整体收敛性和局部超线性收敛速率，最后，第四章对整体论文进行了总结， 展望未来，提出进一步的研究方向。 关键词：共轭梯度；线搜索；内点法：非线性方程组；整体收敛性；局部收敛性 第1 页 英文摘要 a b s t r a c t o p t i m i z a t i o nm e t h o d sa r ew i d e l yu s e di nm a n yf i e l d s t h i sp a p e ri sd e v o t e dt oan e wa p - p r o a c ho fa f f i n es c a l i n gi n t e r i o rc o n j u g a t eg r a d i e n tp a t hf o rs o l v i n gn o n l i n e a ro p t i m i z a t i o nw i t h l i n e a re q u a l i t ya n di n e q u a l i t yc o n s t r a i n t s ，a n di t sa p p l i c a t i o n st ou n c o n s t r a i n e dn o n l i n e a rs y s t e m s c o n j u g a t eg r a d i e n tm e t h o d , w h i c hc a t lb ee a s i l yc o m p u t e da n dm e r e l yr e q u i r e st h ef i r s to r d e r i n f o r m a t i o nw i t hs m a l ls t o r a g e ，i so n eo ft h em o s tp o p u l a rm e t h o d sf o rs o l v i n gl a r g es c a l eo p t i - m i z a t i o np r o b l e m s b u l t e a ua n d a lf o r m e dac o n t i n u o u sc o n j u g a t eg r a d i e n tp a t ho fu n c o n s t r a i n e do p t i m i z a - t i o n t h ep a t hi sd e f i n e da sl i n e a rc o m b i n a t i o no fas e q u e n c eo fc o n j u g a t ed i r e c t i o n sw h i c ha l e o b t a i n e db ya p p l y i n gs t a n d a r dc o n j u g a t ed i r e c t i o nm e t h o dt oa p p r o x i m a t eq u a d r a t i cm o d e lo fa n c o n s t r a i n e do p t i m i z a t i o n b u tt h ec o n t i n u o u sg r a d i e n tp a t hn e e d st of o r mt h ee n t i r ep a t hf i r s t ，a n d t h e nt os e a r c h ，w h i c hw i l li n c r e a s et h et o t a lc o m p u t a t i o n s i no r d e rt oi m p r o v et h ec o m p u t a t i o n e f f i c i e n c y , d i s c r e t ep a t hw i l lb eu s e df o rs o l v i n gb o u n dc o n s t r a i n e dn o n l i n e a ro p t i m i z a t i o n n e o r e t i c a l l y , w eo n l yn e e dt oc o n s t r u c tp a r to ft h ec o n j u g a t eg r a d i e n tp a t ht os o l v et h ea p p r o x i m a t e q u a d r a t i cf u n c t i o na te v e r yi t e r a t i o ns u c ht h a tt h ee f f i c i e n c yo ft h ea l g o r i t h mi sg r e a t l yi m p r o v e d f r o ma n o t h e rp e r s p e c t i v e ，l i n e a re q u a l i t ya n di n e q u a l i t yc o n s t r a i n t sa r ei n v o l v e d s ot h es u b p r o b l e mi se q u i v a l e n tt oa nu n c o n s t r a i n e do p t i m i z a t i o np r o b l e mi nt h en u l ls p a c e t h ep a t hi s d e f i n e da sl i n e a rc o m b i n a t i o no fas e q u e n c eo fc o n j u g a t ed i r e c t i o n sw h i c ha r eo b t a i n e db ya p p l y - i n gd i s c r e t ec o n j u g a t ed i r e c t i o nm e t h o dt ot h ea p p r o x i m a t eq u a d r a t i cf u n c t i o ni nt h en u l ls p a c e i nt h i sp a p e r , w ep r o p o s ea l la p p r o a c ho fa f f i n es c a l i n gi n t e r i o rd i s c r e t ec o n j u g a t eg r a d i e n t p a t hf o rs o l v i n gn o n l i n e a ro p t i m i z a t i o nw i t hl i n e a re q u a l i t ya n di n e q u a l i t yc o n s t r a i n t s w eo b t a i n t h ed i r e c t i o nb ys o l v i n gq u a d r a t i cm o d e lv i ac o n s t r u c t i n gd i s c r e t ec o n j u g a t eg r a d i e n tp a t h b y c o m b i n i n gi n t e r i o rb a c k t r a c k i n gl i n es e a r c h ，w eo b t a i nt h ei t e r a t i o n b a s e do ns o m er e a s o n a b l e c o n d i t i o n s ，t h eg l o b a lc o n v e r g e n c ea n dl o c a ls u p e rl i n e a rc o n v e r g e n c er a t eo ft h ep r o p o s e da l g o - r i t h ma r ee s t a b l i s h e d f i n a l l y , w ec a l c u l a t es o m es t a n d a r dt e s te x a m p l e sb ym a t l a bt oi l l u s t r a t e t h ee f f e c t i v e n e s so ft h ep r o p o s e da l g o r i t h m t h et h e s i sc o n s i s t so ff i v ep a r t s i nc h a p t e r1 ，w es u m m a r i z et h eb a s i cc o n c e p t so fo p t i m i z a - t i o nt e c h n i q u e ，c o n j u g a t eg r a d i e n tm e t h o da n dt h ep r o p e r t i e s i nc h a p t e r2 ，w ea n a l y z er e l a t e d t h e o r i e sa f t e rg i v i n gt h ec o r ea l g o r i t h m i nc h a p t e r3 ，g l o b a lc o n v e r g e n c ea n dl o c a lc o n v e r g e n c e r a t eo ft h ep r o p o s e dm e t h o da r ee s t a b l i s h e du n d e rs o m er e a s o n a b l ec o n d i t i o n s f i n a l l y , i nc h a p t e r 4 ，w ec o n c l u d et h em a i nr e s u l t so ft h i st h e s i sa n dp r o p o s es o m ef u r t h e rr e s e a r c hd i r e c t i o n sa b o u t o u rw o r k 第1 i 页 英文摘要 k e yw o r d s ：c o n j u g a t eg r a d i e n t ；l i n es e a r c h ；i n t e r i o rp o i n tm e t h o d ；n o n l i n e a re q u a t i o n s ； g l o b a lc o n v e r g e n c e ；l o c a lc o n v e t g e n c er a t e 第1 i i 页 主要符号对照表 主要符号对照表 舻 礼维实向量空间 渺m 竹m 维实矩阵 ”i | ”1 1 2e u c l i d 范数 i f i f o 。 。范数 n 维决策变量 目标函数 约束优化问题在可行点z 处的等式约束指标集 约束优化问题在可行点z 处的不等式约束指标集 约束优化问题在可行点z 处的有效集 ，在z 处的梯度，吕p v y ( x ) ，在z 处的h e s s e 阵 l a g r a n g e 乘子 约束优化问题的l a g r a l l g e 函数 可行集 严格可行集 非线性方程组的精确解或极小化问题的k k t 点 目标函数在作者z 处的局部二次近似 水平集 第k 步迭代点 第k 步搜索方向 第k 步线性搜索因子 第页 z “ )n，) 力讯咖 删 。 。 z，z州北驴胁以q m文饥以巩醺鲰 致谢及声明 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研 究成果论文中除了特别加以标注和致谢的地方外，不包含其他 人或机构已经发表或撰写过的研究成果其他同志对本研究的 启发和所做的贡献均已在论文中做了明确的声明并表示了谢 = 亡匕 思 作者签名：喜幼砺 日期：洲。r ，8 、 d 第3 4 页 致谢及声明 论文使用授权声明 本人完全了解上海师范大学有关保留、使用学位论文的规 定，即：学校有权保留送交论文的复印件，允许论文被查阅和借 阅；学校可以公布论文的全部或部分内容，可以采用影印、缩 印或其它手段保存论文保密的论文在解密后遵守此规定 作者娩童立砺翩签名夥吼冲川2 第3 5 页 第一章最优化理论基础 第一章最优化理论基础 1 1 最优化问题简介 最优化技术在许多领域有极其广泛的应用，如农业生产、交通运输、金融、管理、 通讯国防等，而所谓的最优化问题是在若干可行方案( 决策) 中挑选最好的方案( 决策) 。 最优化理论与方法是研究如何从实际问题的众多方案中选取最优方案的一门学科，同时 它的具体算法也成为其他行业的借鉴。近年来，随着计算机以及优化计算方法的迅速发 展，最优化方法在实际应用日益广泛。为了确定最优的方案，最优化技术需要针对具体 的实际问题建立相应的最优化模型，再结合模型的具体表达形式和特性来选择合适的最 优化方法去求解。 最优化问题的数学模型一般形式为： r a i n ，( z ) s t 白( z ) = 0 ，ie ， c i ( x ) 0 ，i z ， 其中，：渺一瞬1 ，白：舻_ 瞬1 ，z 舻称为决策变量，厂p ) 称为目标函数，q ( z ) 是约 束函数，和z 分别是等式约束的指标集 1 ，2 ，m ) 和不等式约束的指标集 m + l ，m + 2 ，p ) 。定义集合q 为 q d = e f zi 龟( z ) = 0 ，i ；白( z ) 0 ，i z ) ( 1 1 2 ) 则称q 为可行域。若z q ，则称为可行点或可行解。当要求不等式约束等号不满足时， 可行域成为“严格可行域”，即( 1 1 1 ) 的严格可行域为： i n t ( q ) d = e f zc f ( z ) = 0 ，i 占；龟( z ) 0 ，i z ) ( 1 1 3 ) 对于一个可行点x ，所有的等式约束都被认为是有效约束。考虑不等式约束c i ( x ) 0 ，如果有白( z ) = 0 ，就称约束q ( z ) 0 在点z 是有效约束或起作用约束。i 如果有q ( z ) 0 ，就称不等式约束c t ( z ) 0 在点z 是不起作用约束。如果所有的不等式约束都是不起作 用约束，就称z 是可行域的内点。 若模型( 1 1 1 ) 中不含约束条件，即q = 咿，称模型( 1 1 1 ) 为无约束优化问题。若模 型( 1 1 1 ) 中含有约束条件，即称模型( 1 1 1 ) 为约束优化问题。 若模型( 1 1 1 ) 的目标函数，( z ) 和约束函数臼( z ) ( i = 1 ，2 ，p ) 均为线性函数时，则称模 型为线性规划；当目标函数和约束函数中至少有一个是变量z 的非线性函数时，称模型称 为非线性规划。 第1 页 1 2 最优性条件 1 2 最优性条件 最优性条件是指最优化问题的最优解( 局部的或全局的) 所必须满足的必要条件和 充分条件。常用的是一阶必要条件和二阶必要条件。最优性条件不仅对于最优化理论的 研究具有重要意义，而且对算法的整体构建以及有限步终止性的规定起极其重大的作 用。 定义1 2 1 设z 。q ，a ( z 。) 是起作用约束集，如果或者所有的 q ( z 。) ，i 4 ( z 。) ) 都 是z 的线性函数，或者 v q ( z 。) ，i a ( x 。) ) 线性无关，则称问题( 1 1 1 ) 具有线性无关约束 品性。 为了便于讨论约束优化问题的局部极小点的最优性条件，首先引入约束优化问 题( 1 1 1 ) 的拉格朗日函数，如下： 其中入称为拉格朗日乘子。 接着给出最优解的一阶必要性条件，即通常被称蔓j k a r u s h k u h n t u c k e r ( 简称k k t ) 定理： 定理1 2 1 ( 【2 0 】) 设z + q 是问题( 1 1 1 ) 的局部最优解，若在z 。点线性无关约束品性成立， 则存在向量a 。= ( 入：，埋) t ，使得 v 盘l ( x 。，a 。) = 0 ， a ：0 ，i z ， 入：龟( z 。) = 0 ，i z ( 1 2 2 ) ( 1 2 3 ) ( 1 2 4 ) 其中( 1 2 2 ) , - - 0 2 4 ) 称为问题( 1 1 1 ) 的一阶必要性条件或k k t 条件。满足此条件的 点称j b k u h n t u c k e r 点( k - k - t 点) ；( 1 2 4 ) 式称为互补松驰( c o m p l e m e n t a r i t y ) 条件。如果 对任意i z ，定和臼( z 。) 中有且只有一个取零值，则称为严格互补松驰条件成立。 由定理i 2 1 可知，无约束最优化问题的一阶必要性条件可描述为 v y ( z 。) = 0 无约束问题的最优点一定满足上式，但满足上式的点不一定是无约束问题的局部最 优解，因此习惯上，把满足上式的点称为平稳点或驻点。 下面给出最优解的二阶必要条件定理。 定理1 2 2 ( 【2 0 】) 设z 。q 是最优化问题( 1 1 1 ) 的最优解，且函数y ( x ) 与龟( z ) ，i = 1 ，2 ，p 二阶连续可微。又设定理1 2 1 中的约束规范条件在点z 。成立，从而存在拉格朗 日乘子向量入。使k k t 条件成立。如果严格互补松弛条件在z 。成立，则： s * v l l ( x 。，入。) s2 0 第2 页 2z 龟 入 p：l z ， = 入zl 第一章最优化理论基础 对一切满足 s r v q ( x 。) = 0 ，i 么 。) 的方向s 均成立。 最后，我们给出最优解的二阶充分条件定理。 定理1 2 3 ( 【2 0 】) 设最优化问题( 1 1 1 ) 的函数，( z ) 与q ( z ) ，i = 1 ，2 ，m 均二阶连续可 微，在可行点z ，处定理1 2 1 的约束规范条件成立，若存在拉格朗日乘子向量a 。使k t - t 条件和严格互补松弛条件成立，且对所有满足 的非零向量s 有 8 t v c i ( x 。) = 0 ，i 4 ( z 。) s t v 2l ( x 。，a 。) s 0 ， 则z 。是问题( 1 1 1 ) 的一个严格局部最优解。 1 3 最优化方法的结构 求解问题( 1 1 1 ) 通常是通过求其k k t 点的途径得到它的最优解。一般采用的是迭 代法。其基本思想为：给定一个初始点z o 辩，按照某一迭代规则产生一个迭代序 列【z 七) ，使得当 钆 是有限点列时，其最后一个点是k - k - t 点；当 z 七 是无限点列时，它 的任意一个聚点是k k t 点。 最优化问题求解的基本迭代格式如下： 算法1 3 1 ( 最优化方法的基本迭代格式) 1 给定初始点铷，k 卜0 2 按约定规则确定搜索方向p 七 3 确定步长q 知使得目标函数具备某种意义下的下降 4 寻找一个迭代点z 七+ 1 = 钆+ q 七p 七 5 判另l j x k + l 是否满足某种终止准则。若满足，则停止迭代，x k + l 是近似局部最优解； 否则，k 卜k + 1 转第2 步 在以上迭代格式中，关键的两步是构造搜索方向仇和确定步长口l | 。不同的构造方 向m 和确定步长q 南构成了不同的算法。线搜索策略和信赖域策略是保证最优化方法整体 收敛的两类技术。 好的最优化算法具备的典型特征：迭代点x 七能稳定地接近局部极小值点x 。的邻域， 并较快的收敛于x 。 所以，由算法产生的迭代序列f z 南) 的收敛速度称为评价该算法优劣的重要标准之 一。设序列 o k ) 在某种范数意义下收敛于瓦，即 1 i r ai i 瓢一z 。l | = 0 ( 1 3 。1 ) 第3 页 1 4 预条件共轭梯度法及其性质 若存在实数7 0 2 乏- - 个迭代次数后无关的常数g 0 ，使得 恕剀锄 ( 1 3 2 ) 则称算法产生的迭代序列 z 惫】具有q q 阶收敛速率。特别地， ( 1 ) 当r = 1 ，1 q o 时，迭代点列 z 岛) 叫做具有q 线性收敛速率； ( 2 ) 当1 0 时，迭代点y u x k q 做具有q 二阶收敛速率。 另一种收敛速度是r 一收敛速度( 根收敛速度) ，即设 若r 1 = 0 ，则称x k 是r 超线性收敛于z 。：若0 r l 1 ，则称是r 线性收敛于x 。； 若r 1 = 1 ，则称x k 是r 次线性收敛于x 。 类似，若r 2 = 0 ，则称z 惫是r 超平方收敛于z 。；若0 0 ，令r o = h x o + b ，令p o = 一r o ，后：= 0 。 步2 如果t i r o l i ，停止。 步3 计算 n 七2 币r t 厩y k ， x k + l2x k + q 七p 知， 凤：r z + f l r k + l ， r j ； p k + 1 = - - r k + 1 4 - 3 k p k 步4 令k ：= k + 1 ，转步2 。 定理1 4 1 ( 【2 0 】) 对于正定二次函数，采用精确线性搜索的共轭梯度法在仇礼步后终止， 且对于1 i n 有以下各式成立： p t h p j = 0 ， j = 0 ，1 ，i 一1 g t g j = 0 ， j = 0 ，1 ，i 一1 m_ p i9 j = 一g ：9 t ， s p 口n g o ，g l ，夕) = s p a n g o ，h g o ，日。夕0 】， s p a n p o ，p l ，a 】= s p a n g o ，h g o ，日。9 0 ) 第5 页 1 4 顸条件共轭梯度法及其性质 其 s p a n g o ，g l ，鲰】i 和s p 口n _ p o ，p l ，轨】分别表示由9 0 ，g l ，g , 及p o ，p 1 ，鼽张成 的子空间； 【g o ，h g o ，日g o 表示卯的i 阶脚l o v 子空间，4 5 c ( r o ；k ) = s p a n g o ，h g o ，日跏) 。 另外，我们可知共轭梯度法产生的序列( 巩 满足 蚓坯( 蒜一矿蚓b 4 力 其中入1 和k 分别是目的最大和最小特征值，圪( 日) = 0 日f 日_ 1 1 1 2 = 磬1 是矩阵h 的条件数。 “ 由( 1 4 2 ) 可以看出，共轭梯度法的收敛速度依赖于 可可，而不是k ( 日) ，因此如果 能够采取某种措施改善日的条件数，就可以加快收敛速度。下面给出了解决这个问题的 一个办法。 设c 是某个非奇异矩阵，令岔= c x ，则二次目标函数( 1 4 1 ) 变成 唾nm ) = 丢2 t ( c t h c 一1 ) 岔+ ( c 嘞) 丁宕+ c ( 1 4 3 ) 这时，方法的收敛速度依赖于c t h c 一1 的条件数而不是h 的条件数。如果能够选择非奇 异矩阵c 使得c - t h c 一1 的条件数明显好于h 的条件数，则收敛速度将明显改善。根据这 个思想，我们定义m = c t c ，并给出下面的预条件共轭梯度法。 算法1 4 2 ( 预条件共轭梯度法) 步1 初始步：给定z o ， 0 ，预条件矩阵m ，令伯= h x o + b ，解m 珈= g o 得y o ， 令p o = 一y o ，k ：= 0 。 步2 如果i h | | g ，停止。 步3 计算 解m y = r 七+ l 得可南+ 1 步4 令k ：= k + 1 ，转步2 。 r 弧 a 七2 p t 土h p k x k + l2z 知+ a 芦， r k + l = + a k h p k ， 尻：毕t ， 吒纨 p k + 1 = 一纨+ 1 + 凤m ， 第6 页 第一章最优化理论基础 如果m = ，则预条件共轭梯度算法就是标准的共轭梯度算法。 类似于标准的共轭梯度算法，预条件共轭梯度算法也有如下性质： 定理1 4 2 对于正定二次函数，采用精确线性搜索的共轭梯度法在m 佗步后终止，且对 于l 七n 有以下各式成立： r t p ，= 0 ， 歹= 0 ，l ，1 0 0k1 r 奄乃2 ， ，2 ，l ， r 蚕m 一1 勺= 0 ， j = 0 ，1 ，k 一1 s p a n c t 珊，c t r l 一，c r ) = s p a n c t ，( c t h c 一1 ) c r o ， ，( c t h c 一1 ) 。c t r o ) ， s p a n e p o ，唧l ，c p k ) = s p a n c t r o ，( c t h c 一1 ) c r o ， ，( c t h c 一1 ) 。c t r o ) ， 磙。h p i = 0 ， i = 0 ，1 ，k 一1 记，l i j = 一吧m r j ， j = 0 ，1 ，n 其中m = 矿c ，而n 为第k 次迭代算法第3 步被执行的次数 证明：当c = i ，即c 为单位矩阵时，由定理1 4 1 可知结论显然成立。 当c j 情况，使用数学归纳法如下证明。 当k = 0 时，( 1 4 6 ) 和( 1 4 7 ) 式成立； 当k = 1 时，( 1 4 9 ) 式成立： 当k = 2 时，( 1 4 4 ) 和( 1 4 8 ) 式成立； 假设以上各式对k 成立，下证对k + 1 也成立。 首先证明( 1 4 6 ) 式成立。 由假设可知c - t r k s p a n c - t r o ，( c - t h e 一1 ) c r r o ，( c - t h c _ 1 ) 知c - t r o ，即 同理可知， 故 c r s p a n c 一? r o ，( c t h c 一1 ) c t 铂，( c r h c 一1 ) 2 c t 绚) = s p a n r o ，h m 一1 r o ，c r ( c r h c 一1 ) 七c r t o p 七c 一1 s p a n c t r 0 ，( c t h c 一1 ) c t r o ，( c t h c 一1 ) 知c t t o h p k h c 一1 s p a n c t r o ，( c t h c 一1 ) c r r o ，( c t h c 一1 ) 七c r r o ) = s p a n h m r o ，( h c 一1 ) ( c t h c 一1 ) c t r 0 = s p a n h m r o ，( c t c t ) ( 日c 一1 ) ( c r h c 一1 ) 七c t r o = s p a n h m 一1 r o ，c r ( c r h c 一1 ) 膏+ 1 c t t o 由r 知+ l = 弦+ a k h p 南知 ，_ 七+ 1 s p a n r o ，h m r o ，矿( c r h c 一1 ) 川c t o ， 第7 页 ( 1 4 4 ) ( 1 4 5 ) ( 1 4 6 ) ( 1 4 7 ) ( 1 4 8 ) ( 1 4 9 ) 所以 c r 飞+ 1 唧佗 c r r o ，( c 一，h c 一1 ) c 一丁 ，( c - r h c 一1 ) 一t 咱l s p 口扎 c t ，c t r l ，c - t + 1 _ 印口n c - r r o , ( c t h c 一1 ) c 一丁， ，( c r h c 一1 ) 蠡+ 1 c 下r 0 ( 1 4 1o ) 由( 1 。4 7 ) 式的假设可知 而 ( c t h c 一1 ) 后c 一丁8 p a n c p o ，c p l ， ，印七) ( c - t h c 一1 ) 七+ 1 c r = ( c 一? 日c 一1 ) ( c r t h c 一1 ) 奄c - t r o j ( c 一? h c ) s p a 见 c p o ，唧1 ，一，嘞， = c - t s p a n h p o ，却1 ，h p k 由如= r t - r 。l 。- - r i 所以 ( c - r h c 一1 ) 七+ 1 c 一7 c - t 聊礼 r o m 一，7 州 。印。n c 一，c - t r l ，c 一、+ 1 ) 跚佗 c r t 伯，c t 7 1 ，c - t + 1 ，聊孢 c - f r o , ( c t h c 一1 ) c 一2 咱， ，( c r h c 一1 ) 七+ 1 c t o ( 1 4 11 ) 结合( 1 4 1 0 ) 和( 1 。4 11 ) 式，显然( 1 4 6 ) 式成立。 下证( 1 4 7 ) 式成立。 由仇+ l = 一y 奄+ l + 忍挑知 聊扎 ，锄，c p k ，锄+ l = 册扎f ，嘞，陬+ 1 ) = s p a n c t 伽，c r n ，c t r k ，c 玑+ 1 = s p a n c t r o ，c r n ，c - t r 七，c + l = s p a n c 一? r 0 ，c r r l ，c 一2 r k + l = s p a n c t r o ，( c t h c 一1 ) c 一丁 ，( c ? h c 一1 ) 知+ 1 c t 吣 从而( 】4 7 ) 式也成立。 第8 页 第一章最优化理论基础 接着证( 1 4 4 ) 式成立。 由仇+ l = r k + o t 七h p k 知 磊1 乃= ( + a k h p k ) ? 乃 = r 醌+ c e k p t h p j u = 0 ，1 ，k 1 ) 由( 1 4 。4 ) 和( 1 4 8 ) 式的假设可知, - 暑p j = 0 ， 又 p k r - p , = 0 ( j = 0 ，1 ，k 一1 ) 故 晤1 聊= 0 ，j = 0 ，1 ，k 一1 m mt + 1 鲰= 依+ a k p ：h p k = r 轨+ 鑫加m m = r ；p k + r iy k 而由( 1 4 9 ) 的假设可知r t p k = 一r 蚕m 一1 1 k = 一t 玑，故 r 玉l p k = 0 结合( 1 4 1 2 ) 和( 1 4 1 3 ) 式，显然( 1 4 4 ) 式成立。 再证( 1 4 9 ) 式成立。 因张t r 七+ 1 = 0 ，从而 最1 + 1 = ( 一玑+ 1 + 风m ) t r k + l 故( 1 4 9 ) 式成立。 下证( 1 4 8 ) 式成立。 由i f + 1 = 一吸，+ 凤+ 1 露，有 又 = 一可1 r m + 风西r m ，瑶1 + 1 r 七+ 1 = 一y k + 1 r 七+ 1 = 一吸1 m - 1 r m 厩t + 1 h p i = 一薅1 地+ 风+ 1 p t 知日纯 i f + 1 h p i = ( m 。“+ 1 ) t h p i = r 玉l m h p i = r 玉1 c 一1 c 坷h p i 第9 页 ( 1 4 1 2 ) ( 1 4 1 3 ) ( 1 4 1 4 ) 1 4 预条件共轭梯度法及其性质 故( 1 4 1 4 ) 式可转化为 又 而 = r 玉l c 1 c 坷t t c c p t = ( r 玉1 c 。) ( c 坷h c 1 ) ( ) p r ， l h p i = 一( r 玉1 c 一1 ) ( c r h c 一1 ) ( c p i ) + 尻+ 1 p 七t h 轨 ( 1 4 1 5 ) ( 蠡1 c ) ( c v d = r 1 p i = 0 ， i = 0 ，1 ，k ( c t h c 一1 ) ( c p i ) ( c t h c 一1 ) s p a n c 一? r o ，( c 一? h c 一1 ) c t r o ，( c t h c 一1 ) c 一? r o ) = s p a n ( c r h c 一1 ) c 一? r o ，( c t h c 一1 ) 2 c t r o ，( c t h c 一1 ) + 1 c t r o ( 1 4 1 6 ) cs p a n c p o ，c p l ，c p i + 1 ) ， i = 0 ，1 ，k 一1 ( 1 4 1 7 ) 从而由( 1 4 1 6 ) 和( 1 4 1 7 ) 式，有 ( 7 & 1 c 。1 ) ( c 廿h c 。) ( ) = 0 ， i = 0 ，1 ，k 一1 结合假设以及( 1 4 1 5 ) ，有 故( 1 4 8 ) 式成立。 最后证( 1 4 5 ) 式成立。 由巧= 一物+ 1 + 岛纺一1 知 p l l h p i = 0 ， i = 0 ，1 ，k y a s p a n p 3 ，乃一1 ) j = l ，k 一1 而当后为【1 ，2 ，n 一1 ) 中任意数时，有 故 又协= m 一1 乃，从而有 显然( 1 4 5 ) 式也成立。 吒乃= 0 ，j = 0 ，1 ，k 一1 嚏珊= 0 ， j = 0 ，l ，k 一1 r 蚕m 一1 吩= 0 ，j = 1 ，2 ，k 一1 第1 0 页 第二章仿射内点共轭梯度路径法 第二章仿射内点共轭梯度路径法 2 1引言 本文考虑带有线性约束的非线性优化问题： m l n s t 其中，矩阵ad = e f l ? 1l 舻跏，a t = a l ，m 】舻x 和a ；= a l + 1 ，a m l 2 j i、 舻( m - 1 ) ，m z ) ： n s bd = e fl ：1l = ( 6 1 ，矿，b t + l ，6 仇) t 妒。可行解集记为qd = e f d 2 一 x l a l z = b 1 ，a 2 z 6 2 ) ，并假设“严格内点可行集”i n t ( f 2 ) d = e f zla 1 z = b 1 ，a 2 z 6 2 ) 非空。这里f ：舻_ 跄是在q 上连续可微的非线性函数。 文献f 1 6 1 使用了共轭梯度法解信赖域子问题获得连续路径，而本文采用了离散的预条 件共轭梯度方法来求解该问题，降低了路径构造的复杂度，同时也减少了计算的步骤。 问题( 2 1 1 ) 的拉格朗日函数为： c ( z ，p ，王，) = y ( x ) 一a t ( a l z b 1 ) 一t ( a 2 z 一5 2 ) ， 其中拉格朗日乘子弘噼，咿一。 局部最优解z 。的一阶必要条件为：存在以噼，以泞n 一。使得以下方程成立： fv y ( x 。) 一a k a t # + = 0 ， a l x 。= b l ， i - d i a g a 2 x 。一6 2 ) 纵= 0 ( 2 1 2 ) 暇一撼d k 惟 l z x 纵h j - 月a 兹r a k - 碍鲰 工3 ， 其中d 七d = e fd i a g a 2 砜一6 2 ，c kd = e d i a g l p 七i ) ，第惫+ 1 迭代点定义为： 卧封 第1 1 页 阢阮 = 一 力z 渖扎a 如 修正牛顿步是渐进充分接近于精确牛顿步的，因此具有较快的收敛速率。 作变换p ：d i 5 1a 2 p ，定义鼠：v 2 ，可得原始变量空间中的子问题如下： ，是也。砂七( d ，面d = e fv f t d + 丢d t b k d + 当护瓯c ； ( d ，d ) 亨p + mz2 ( 瓯) s t a 1 d = 0 ，d ；( ；= a 2 d ( m ，仇) 看成子问题( 鼠) 的解，则对于 0 有 其中最小二乘乘子入知+ 1 和地+ 1 定义如下： 曙墨脸州针 ( 2 1 4 ) ( 2 1 5 ) ( 2 1 6 ) v 舷= 一钏 = 一( i i v a a a 詹+ l a 手，z k + l l i ；+ l l d ；1 l 。k + l | i ；) = 一慨幢 ( 2 1 7 ) 假设a 1 一三未 行满秩，则进行q r 分解，即 a a 。l 一三未 t = 【k 磊】 言 c 2 ，8 ， 况 是正交矩阵，凡是非奇异上三角矩阵。磊的列向量构成零空 一三未 ，的正交基，即 三：一：； 磊= 。 第1 2 页 肛 ， 12七 碍口 一 + 一舯叭 第二章仿射内点共轭梯度路径法 定义 鬟 = 刁 d 以k ，则 c 露 矧么， ；| = 一霹附 故，基于c 2 可得零空间人厂c 2 一三未 ，上的二次模型 m t n 饥c 扩，乎，磐雪蚕 耋 + 丢 荔 t 矾 荔 址刁阱矾= 刁 矧= 斟舻斟 讥扩) ：露p ；+ 昙p z t 觑矿 ( 2 1 9 ) ( 2 1 1 0 ) ( 2 1 11 ) 本章对问题( 2 1 1 ) 的求解即相当于求解( 2 1 1 1 ) ，列出了离散的共轭梯度路径以及相应 的二次模型的一些性质。 2