（运筹学与控制论专业论文）求解无约束与简单界约束优化问题的非线性共轭梯度法.pdf

河南大学硕士学位论文 摘要 本论文研究求解无约束优化问题和简单界约束优化问题的非线性共轭梯度法， 主要讨论这些方法的全局收敛性和数值表现 第二章，我们提出一个改进的共轭梯度算法，此算法是对l s 共轭梯度法的一种 改进在适当的假设条件下，我们将非单调技术应用到所提算法中，并证明了所提算 法在非单调线搜索下的全局收敛性 第三章，我们将非线性共轭梯度方法应用到求解简单界约束优化问题中，并证 明了所提算法的全局收敛性并对所提算法做了数值试验，结果表明我们的算法是 适定的 关键词：无约束优化；简单界约束优化问题；共轭梯度法；线搜索；全局收敛性 河南大学硕士学位论文 a b s t r a c t i i lt b j st h 商s ，w es t u d yn o i l l i n e 龃0 0 n j u j 蛳f a d i e n tm e t h o d 8f o r 慨 c 0 瑚t r a i n e d 觚db d l m d - c 咖t r a j n e do p t i m i z a t i 9 np r 0 b l e m s ，w ea l s od i s c u 鼹t h e 酉o b a lc o n v e r 群m c e p r o p e r t y 孤mm 加斌a lp e i f ( ，玎吡a n o eo ft h e s e 加毗h d d 8 h c l l a p t e r2 ，w e 舯叩o a 的d i 丑e dn o m i 舶a rl s c o n j u g a t e 翠a d i e n tm e t h o df b r 叫o n s t r a i n e d 叩t i 面z a t i o n u n d e ra p p r ( 删g 乞e0 0 n d i t i o n 8 ，w ec s i d e rt h eu 8 eo fa n o n m o n o t o n el i n e 踟日r c ht e c h l l i ( 薹u ei n 址屺p r o p 0 6 e dm e t h o d ，a n dw ep 】r o v et h e9 1 0 b a lc o d v 卅 g l m o eo ft h em o d m e dn o i l l i n e a rc o n j u 9 8 乞e 廖弛n t 如l e t h o d i nc h a p t e r3 ，w ep r o p 0 8 ea m l i 】n e a l rc o n j u g a t e 盯a d i e n m e t h o df 0 r8 0 l 证n gb o u i l 【- c o n s t r a i l l e do p t i m i z a t i o np r o b l 伽明，姐de s t a l ) i hi t sg l o b a lc ( 舡垤堰j g e n c et h 孢m w r ea l s 6 d o8 0 m ei m m e r i c a le x p e r i m e m st 08 l l o wt h a tt h ep r o p 0 8 e dm e t h o di sd f 赫i v e k e y w o r 凼： u n c 伽毗r a j n e d0 p t i m i z a t i o n ；b o u n d c o n 8 t r a i n e do p t i m i z a t i o n ；c 0 n j u - g a t e 伊础e n tm e t h o d ；l i n e 删；g l o b a lc o 矾- e r g e n c e i i 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位中请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成酌，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注乖致谢的地方外，论文中不包括其他人已经发表或撰 写过酌研究成果，也不包括其他人为获得任何教育、科研机构的学位或证书而 使用过的材料。与栽一同工作魄凰赢蒜瘸斑陵斯徽的任何贡献均已在论文中作 段保存、汇编学位论文( 纸质文本和电子文本) 。 ( 涉及保密内容的学位论文在解密后适用本授权书) 学位获得者( 学位论文作者) 釜名： 2 0 口寥年多月7 日 学住论文指导教师釜名： 2 09 肛月f 日 第一章绪论 最优化理论与方法是一门应用非常广泛的学科，在自然科学，社会科学，生产实 践，工程设计中都有直接的体现近年来，随着高新技术，计算机技术及信息技术的 高速发展，最优化理论与方法在实际生活中的应用越来越广泛，为此，也为最优化理 论与方法的发展提供了广阔的空间 在所有需要计算导数的优化方法中，最速下降方法是最简单的，但它的收敛速 度较慢拟牛顿方法的收敛速度很快，被广泛认为是求解无约束优化问题中最有效 的方法之一，但拟牛顿方法需要存储h e 8 8 i o n 矩阵，并通过求解线性方程组来计算搜 索方向，这对于求解大规模问题几乎是不可能办到的共轭梯度法的算法简单，存储 需求方面与最速下降方法差别不大，且收敛速度比最速下降方法快，。可与拟牛顿方 法相媲美，因此特别适合于求解大规模问题这也是共轭梯度法一直为广大工程师 和科技人员所重视并积极研究的原因 2 0 世纪5 0 年代初，计算数学家h 铝t e n 昀【1 】和几何数学家s t i e f e l 【2 】在求解线性方程 组 a z = 6z r n ( 1 1 ) 时，分别独立提出了共轭梯度法，他们合作的著名文章【3 1 ，被认为是共轭梯度法的奠 基性工作该文章详细地讨论了线性方程组的性质以及它与其它方法的联系在a 为 正定矩阵时，线性方程组( 1 1 ) 就等价于下面的最优化问题 i i l i n 去，血一矿z z ( 1 2 ) 二 因此，h e s t e n e s 和s t i e f e l 提出的方法也可视为求解二次函数极小值的共轭梯度方法 1 9 雠年，f k t h e r 和r e e v e 8 【4 】将该共轭梯度法推广到求解非线性极小化问题中，提出了 求解非凸函数极小值的共轭梯度法随后，又出现了f l e t c h e r ，p o w e l l ，b e a l e 等学者，他 们对非线性共轭梯度法展开了进一步的研究，并取得了很大的成就近年来，随着大 规模问题在实际生活中的出现，而共轭梯度法正是求解大规模优化问题的一种有效 1 河南大学硕士学位论文 方法，特别是g 拍e r t 和n o c e d a l 【5 】给出p 尉，+ 方法对非凸函数的全局收敛性结果，以 及p r p + 方法良好的数值表现后，使得共轭梯度法的研究再次受到关注其中比较成 功的是由g r i p p 0 和l u c i d i 【6 l 设计的新的心z 蝎。线搜索证明了标准的p r p 方法的收敛 性d a i 和y u a n 【7 】提出的杂交共轭梯度方法，它们的共同点就是搜索方向的下降性 依赖于所采用的线搜索h 孵r 和z h 锄g 【8 ，9 】提出了一个下降的共轭梯度法，此方法 产生的方向总是下降的，并与所采用的线搜索无关后来，z h 8 n g ，z h o u 和l i f l o ，1 1 】提 出了一种三项共轭梯度下降法，此方法也具有下降性，并与所采取的线搜索无关关 于共轭梯度法其它方面的介绍，如预条件共轭梯度法，基于割线方程的共轭梯度法， 杂交共轭梯度法等，可看h 姆e r 和z h a n g 的综述性文献【1 2 j 及d a i 和y u 觚关于非线性共 轭梯度法的专著1 1 3 】 1 1求解无约束的非线性共轭梯度法 1 1 1单调下降的非线性共轭梯度法 1 9 6 4 年，f l e t d l e r 和将求次函数极小值问题的线性共轭梯度方法推广到 一般的非线性最优化问题中，即： i n i n ，( z )z 豫住， ( 1 3 ) 其中，( z ) ：豫n r 是连续可微函数对于无约束优化问题，通常是采取迭代法来 寻求最优解其基本思想是：给出一初始值护，由算法迭代产生点列z ，z 2 ，我们 希望某一扩是( 1 3 ) 的解在第七次迭代时，设当前迭代点为扩，非线性共轭梯度法的 一般迭代形式如下： z 知+ 1 = z 詹+ a 知扩，后= 0 ，1 ， ( 1 4 ) 其中，步长扩是由某种线搜索决定，搜索方向驴由下面的形式确定 毗= b 删，葚 5 ， 2 q 河南，大学硕士学位论文 凤是参数，矿为，( ) 在处的梯度每一次的迭代都是由两部分组成的：第一部分是 步长舻的计算，第二部分是搜索方向驴的计算，搜索方向铲的计算一般要求具有下降 性即： 一 1 ( 驴) t 矿 o ，有 ，( 扩+ a 驴) o ，满足 ，( 茁七+ q 七驴) = m i n ，( z 知+ q 矿) la o 河南大学硕士学位论文 c u r 珂准则：取步长 o ，使得 a 知= 如【i n oi ( ) t 9 ( 髫知+ 口矿) = o ) 精确线搜索要计算目标函数的梯度与二阶导数矩阵，因此计算量较大，所以在 实际中人们并不经常使用为此，我们可放松对步长舻的要求，只须保证目标函数在 每一次迭代都有充分的下降即可，这样即节省了时间量，从而也提高了方法的效率， 所以我们可以采用一些较弱的步长准则，即非精确线搜索，来确定步长 非精确线搜索方法主要有以下几种： 心n l i j o 准则：选取步长舻= 矿，m 是使得下式成立的最小非负整数： ，( z 血+ 矿d 七) 一，( z 七) 西尹( 驴) i 矿，( 1 6 ) 其中p ( o ，1 ) ，j ( o ，1 ) 标准w b l f e 准则：给定参数o 6 盯 l ，取步长a 七满足： ，p 七+ a 詹矿) ，( z 七) + 如知( 驴) 秒， ( 1 7 ) 9 ( 茁知+ q 七矿) t 驴口( 9 ) r d 知( 1 8 ) 第一个不等式要求函数的下降至少与切线的下降成比例，第二个不等式可以限制步 长扩过小，从而保证目标函数有足够的下降 强w 矾f e 准则：给定参数o 6 仃 1 ，若步长舻满足( 1 7 ) 与下式： l ( 9 2 ) t d ( z 惫+ q 奄d 奄) i 口l ( 9 毫) ? d ki ， ( 1 9 ) 则称舻满足强w b l f e 准则当盯= o 时，则( 夕七+ 1 ) r 驴= o 因此强w - 0 l f e 准则可看作精确 线搜索的推广 推广的w b 准则：若步长q 知满足( 1 7 ) 与下式： 盯l ( 矿) r 驴sg 七+ 驴) r d 七一a r 2 ( 扩) t 驴， ( 1 1 0 ) 4 河南大学硕士学位论文 其中o 6 o g o l 蛐【2 1 】提出的g o l 凼t i 曲线搜索，要求步长扩 o ，并满足下面的条件： 6 1 a 蠡( 夕七) t 矿，( + 铲) 一，( 矿) 如口七( 矿) t 矿， 其中o 如 1 2 o ， 只要| l 矿0 e ，则可认为为一近似解验证算法对任何e o 都能找到满意的近似 解，只须1 i mi i l fl l 矿0 = o 即可为证明上式成立，我们通常采取反证法，即假定存在 常数叩 o ，使得i 旷0 叩，垤 1 ，推出矛盾 对于非线性共轭梯度法的收敛性分析，国内与国外的不少学者已经取得了很好 的成果下面对已有的非线性共轭梯度法的收敛性结果作一简要概述 5 河南大学硕士学位论文 我们首先给出以下假设条件： 假设a ( 1 ) ，( z ) 在水平集c = 扛舻：，( z ) 、， o ) 上有下界且是紧集 ( 2 ) 存在的某个邻域虬使得，( z ) 在该邻域上连续可微且导数满足豇p 3 曲统z 连续条 件，即存在一常数己 o ，使得 0 9 ( z ) 9 ( ) h 三l l z z ，0 比，耖m 由假设a 可知，存在常量p o ，使得 9 知h 弘， c 最早的非线性共轭梯度法是f r 方法早期对f r 方法的研究主要是基于精确线 搜索1 9 7 0 年，z o u t e n d i j k f ，叫证明了采用精确线搜索的f r 方法在假设a 成立的条件下 具有全局收敛性迄今为止，关于f r 方法的收敛性理论的研究取得了很大的成就， 然而，在数值计算上f r 方法并不理想p o w e n f 2 5 】在精确线搜索下分析了f r 方法可能 连续产生小步长的性质，即如果f r 方法在某一步产生一个很小的步长，则相继的许 多步长也可能很小这就说明f r 方法的收敛速度可能非常慢，从而，在理论上给出 了f r 方法在实际数值中表现不好的原因 1 9 8 5 年，a 1 b 鼯l i l 2 6 】第一个给出了f r 方法在非精确线搜索下的全局收敛结果， 证明了在参数仃 吾的情况，也给出了反例，说明f r 方法此时可能产生一个上升方向而导致方法 失败d 越和y u a n f 2 3 】提出了一种广义线搜索，并证明了f r 方法在广义w 6 1 f e 线搜索下 具有全局收敛性但这种广义w r o l 碰戋搜索可能破坏算法的共轭性。 6 河南大学硕士学位论文 p i u p 方法被认为是目前数值表现最好的方法之一，当算法产生小步长时，p r p 方 法的搜索方向驴能自动地靠近负梯度方向，从而具有自动重新开始的功能，有效地避 免了f r 方法可能连续产生小步长的缺点p o w e n 在【2 5 】中证明了当_ o ，= 扩+ 1 一 时，p r p 方法的全局收敛性，并且证明了采取精确线搜索的p r p 方法对一致凸函数 是全局收敛的但对一般的非凸函数，p o w r e 【2 8 】举出了反例，表明即使按c 邺r 原则选 取步长，p r p 方法也可能在几个迭代点附近循环，而其中任意一个迭代点都不是目标 函数的稳定点，从而破坏了算法的全局收敛性如果使用非精确线搜索如强w o 线 搜索，d a i f 2 9 1 举出例子说明，即使，( z ) 一致凸，且矿( o ，1 ) 充分小的情况，p r p 方法都 有可能产生一个上升方向但如果每一个搜索方向是下降的，则不难证明p r p 方法 在采取非精确线搜索时对凸函数是全局收敛的对一般非凸函数，p b e n 【3 0 l 建议限 制p r p 方法中的参数卢p p 为非负，即： 凤= m a x 茚r p ，o ) 从而避免了当0 驴i l 彳艮大时，相邻两个搜索方向会趋于相反的情况g i l b e r t 和n o 静 跚【5 】考虑了此建议，建立了修正的p r p 方法，即p 即+ ，并证明了在合适的线搜索 下，此方法对非凸函数全局收敛，但他们也举出例子表明，即使目标函数是一致凸的， 卢f 兄p 也可能为负 为了使p r p 方法能产生下降的搜索方向，g r i p p o 和l u c i d i 【3 1 】设计了一种新的a m i j o 线搜索，并证明了原始的p r p 方法在该线搜索下，对于一般的非凸函数是全局 收敛，他们的结果是基于驴：z 七+ 1 一很小时，p r p 方法的搜索方向靠近于最速下 降方向的性质d a i 和y u a n 在【1 3 】中讨论了p r p 方法的一个新性质，证明了采取常数 步长因予的p r p 方法在每次迭代中都能产生一个下降方向，而且全局收敛但是，这 种常数步长因子的选取依赖于l i p s c h i t z 常数厶而五往往不能预先估计，所以在实际计 算中不易操作 尽管p r p 方法在实际计算中是数值表现最好的，但是理论上却不如f r 方法完善 从上面的分析我们也可以看到，p r p 方法在实际中同样不能保证产生下降方向，并 且它的全局收敛性往往需要使用强w b l f e 线搜索 7 河南大学硕士学位论文 h s 方法的许多性质与p r p 方法相似，并且数值结果也很好同时与p 砒，方法相 比h s 方法有一重要的性质为共轭性，坞即： 矿) 一l = o ， 其中纨一l = 矿一矿，此关系式不论线搜索是否精确，上式总是成立的由于和p r p 方 法有类似的性质，在采取精确线搜索时，根据( 驴一1 ) t 弧一l = 9 七一1 | 1 2 ，于是有： 醒s = 醒即 因此可从前面对p r p 方法的研究知道，h s 方法在采取精确线搜索时对一般的非凸函 数不一定收敛g i 】b e r t 和n 0 c e d a l l 3 2 】证明了若觖= m a x 雎s ，o ) ，则在适当的线搜索 条件下，此方法具有全局收敛性 c d 方法就是共轭下降法，它具有一个重要的特性，即线搜索采取强w | o e 时，如 果参数矿 o ，d a i 和y u 锄发现，此时| | 舻h 2 可能以指数级数增长虽然一 般参数的强w o l f b 线搜索即可保证c d 方法在每一步产生一个下降方向，但c d 方法的 收敛性质并不好此外，由于当线搜索精确时，有露? = 雏r ，因此c d 方法与f r 方法 有着相同的数值缺陷，即由于可能连续的产生小步长而降低方法的收敛性在实际 计算中，c d 方法的数值表现与f r 方法相差不大，但逊于p r p 方法的数值表现 8 河南大学硕士学位论文 d 呖法是d a i 和y u 缸【1 9 l 在1 9 9 5 提出的一种新的共轭梯度方法，当线搜索精确时， 卯y = 卢舻，此时具有与f r 方法一样的全局收敛性，在采取标准w 础b 线搜索时，d y 方 法在每一步都能产生一个下降方向，并且是全局收敛的由此可见，共轭梯度法领域 不使用强w r 0 线搜索而使用标准w - 0 线搜索也能得到很好的收敛结果对于d y 方 法，d a i 【3 5 1 在不使用任何线搜索的情况下，分析了其内在性质，证明了方法在远离最 优点时，充分下降条件( 矿) t 驴- 一c 矿2 对大部分迭代点成立利用该性质，可以证 明d y 方法在一般的线搜索下是全局收敛的另外，对采取标准w b 线搜索的一般共 轭梯度法，也给出了一般性的收敛结果 除对以上常用的共轭梯度法的收敛性做出总结之外，关于对共轭梯度法的修正 算法及相关算法的收敛性分析，以及共轭梯度法的其它问题都没有涉及，可看h a g e r 和 z h a n g 的综述性文献【1 2 】及d 8 i 和y u 姐关于非线性共轭梯度法的专著【1 3 】 1 1 2 非单调下降的的非线性共轭梯度法 前面，我们介绍了选取步长舻的一些线性搜索方法，即精确线搜索方法和非精 确线搜索方法这些方法均要求函数在每一步搜索中具有下降性，即满足： ， 蚪1 ) o ，仃( o ，1 ) ，y ( o ，1 ) ，m ( o ) = o ，o m ( 七) s l i n 【m 一1 ) + 1 ，删，后1 ，m 是某个非 负整数容易看出，上式中若m ( 七) = o ，这种非单调线搜索就还原为通常的心m i j o 线 搜索 g r i p p o 等人较详细的分析了非单调线搜索牛顿法的收敛性，并给出了非单调线 搜索的一些特殊性质，通过数值试验说明非单调线搜索技术可以降低搜索次数和函 数的计算次数，从而提高了算法的效率总之，非单调技术的特点就是，在算法中并 不要求式( 1 1 1 ) 在每一步都得到满足，往往是对于迭代给出一个更为宽松的条件，但 是可以保证算法的收敛性，在实际计算中也有很好的计算效果，为此引起了国内国 外的许多学者的兴趣，并对此方法作了进一步的研究近年来，l i u ，h 缸和s 蛆f 3 6 】等 提出的非单调拟牛顿法和l u c i d i 和r o m a 3 7 】提出的非单调的f r 算法，都取得了不错 的数值效果后来，l i u ，j i n g 和h a n 【3 8 】等将非单调技术迸一步应用于共轭梯度法，采 用( 1 1 2 ) 和( 1 9 ) 式构成的非兽调线搜索技术，在一定条件下证明了共轭梯度法的全局 收敛性 此外，关于非单调线搜索技术的研究还有许多学者，如p t l i u i p el t o i n t ，n y d 锄g 和f j z h o u 等也对这方面做了许多工作，并取得了很好的研究成果详细内容可参见 文献1 3 9 ，4 0 ，4 1 】本文的第二章，我们将把非单调技术应用到共轭梯度法中，并研究 相应算法的收敛性 1 2求解简单界约束优化问题的方法 考虑下面简单的有界约束优化问题 m i n ，( z ) z q ，( 1 1 3 ) 其中，( z ) ：p 卜_ r 为连续可微函数并且导数是l i p s c h i t z 连续的，我们定义可行域 1 0 河南大学硕士学位论文 为q ，即： q = z 舻：z z 钍，( 1 1 4 ) z ，t i 为任意的向量，且满足一 k 啦 + o o 求解( 1 1 3 ) 的方法很多，c 0 衄，g o u l d 和t 心】提出的信赖域方法，n o c e d a l 【4 3 】和 b y r d 等人 蜘提出的有限记忆方法，m o 诧和t o r a l l d o 【4 5 】以及n i 卜1 6 1 提出的序列二次规划 方法都是一些有效的方法但是这些算法在每一步迭代中都需要解决一个子问题 简单界约束的许多算法都是基于积极集的基础上【4 7 ，4 8 ，4 9 】，在这些方法中，通常我 们是用一个工作集去估计当前的积极集约束，然后把它从当前的迭代点更新到下一 个迭代点早期的积极集方法对中小规模的优化问题非常有效，但是对大规模优化 问题却收效甚微【5 0 】主要的原因是，在每一步迭代中最多有一个约束被增加到积极 集或从积极集中减少，从而降低了算法的收敛速度为此，激励了大批的学者和专家 去研究积极集方法，希望找到一个可以迅速改变这种缺陷的方法 梯度投影方法【5 0 】在解决大规模优化问题中是一个非常有效的方法，此方法在 每一步迭代中可以使多个约束被增加到积极集或者从积极集中减少出来从而提高 了算法的收敛速度在解决非线性优化以及简单的线性优化和有界约束优化问题方 面，投影梯度法已经被进一步的研究在最近的几十年中，有界约束优化问题已经受 到了广泛的关注，并且取得了不错的成绩，有兴趣的读者可以参考文献 5 1 ，5 2 1 河南大学硕士学位论文 1 3本文的主要工作 本文对非线性共轭梯度法求解无约束与简单界约束优化问题的全局收敛性进 行了进一步的讨论，在第二章与第三章分别就相关l s 共轭梯度法，p r p 共轭梯度法 作了修正，并对它们的收敛性进行了探讨，所得结果包含并推广了前人的有关结果， 现具体分析如下： “ 第二章，我们提出了一种求解无约束优化问题的非线性共轭梯度方法，这种方 法是对l s 共轭梯度法的一种改进然后，我们将非单调技术应用到所提的非线性共 轭梯度法中，并证明所提方法的全局收敛性 第三章，我们考虑到御i u p 算法好的性质，提出了一种求解简单界约束优化问题 的共轭梯度法，并证明该方法全局收敛性，同时验证了此方法的数值表现，结果显示， 我们的算法是适定的 1 2 河南大学硕士学位论文 1 4 本文所用的记号 实变量 目标函数 目标函数的维数 所考虑问题的解 解矿的第七次近似 全体实数组成的集合 全体n 维实向量组成的集合 目标函数，( z ) 在点扩处的梯度 n 阶单位矩阵 向量的欧氏范数 向量的无穷模 1 3 匕 ： 叶阽；八嗽矿矿础矿盯 第二章修正的l s 共轭梯度法 2 1引言 l s 共轭梯度法是由l i u ，s 呻【1 8 j 在1 9 9 1 共同提出的一种非线性共轭梯度法，这种 方法具有如下的迭代形式： z 1 = z 蠡+ a 南矿，七= o ，l ， ( 2 1 ) 拈 一矿二。蓦 仁2 ， 其中参数凤由以下公式计算： 凤= 磁s = 一龋 在文献【5 3 】中对l s 共轭梯度法进行了改进，并证明了其收敛性在文献【1 1 】中，给出了 一种改进的p r p 算法一m p r p 算法，并在一种改进的a 皿啕。线搜索下证明了m p r p 算 法的全局收敛性，同时也得到了较好的数值计算结果本文考虑到m p r p 算法的全 局收敛性和好的数值表现，我们借助于其思想，在【5 3 】中改进的l s 共轭梯度方法的基 础上，提出了一种三项共轭梯度方法，使得这种改进的方法能产生充分下降条件同 时，我们考虑到非单调线搜索的优势，将非单调线搜索应用到所提的方法中，并证明 其全局收敛性 2 2算法设计 下面给出修正的l s 共轭梯度法的迭代形式，设扩为当前迭代点，驴由下式定义： 铲：善。，。= _ 2 皓。， ( 2 3 ) 【一9 七+ 砖s + d 七一1 + 巩皖一1 七1 、 河南大学硕士学位论文 其中 ( 矿) r 虻一。 2 一万习而两 幽= 产岛产1 ， 以= 筹篙 由以上条件我们很容易得出：对任意的七o ，都有 ( 驴) t 矿= 一胪1 1 2 这表明驴是目标函数，( z ) 在扩处的一个充分下降方向此外，如果线搜索是精确的， 则( 矿) t 驴一1 = o 所以，我们有 靠= 普篙一o 则上面的方法就变为文献【5 3 】中的方法 我们的线搜索是基于如下的非单调性线搜索： 令o a l 久2 ，口( o ，1 ) ，j ( o ，】) ，m 为一正整数，在第七次迭代后，给定舻 ( a 1 ，a 2 ) ，求步长舻= m a x 舻盯h ，饥= o ，1 ，2 ，) 满足 m 七+ 矿驴) 。蕊妨m 七。) 】- 6 ( q 硼柙 ( 2 4 ) 其中m ( o ) = o ，o m ( 七) m i n 胁一1 ) + 1 ，m 】，忌1 容易看出，当m ( o ) = o 时，非单 调线搜索( 2 4 ) 式就还原为l e o n e 2 0 】提出的舡m i j o 线搜索另外，为方便起见，我们引 入记号z ( 后) ，其巾七一m ( 后) z ( 后) 七，且 m 呻2 。当篓m 七一歹) 】 ( 2 5 ) 基于上面非单调线搜索，我们给出下面修正的l s 共轭梯度算法： 算法2 2 1 河南大学硕士学位论文 步o 给定微o 入1 o ，正整数m ，初始点z o 舭， 并今后：= o ? 步1 计算矿，若0 矿0 ，则停止；否则由式俾砂计算驴j 步2 给定步长舻( a l ，a 2 ) ，由线搜索一 单调线搜索夕计算步长口蠡，即： 舻= m 腻 舻砝，j i = o ，l ，2 ，) ， 且满疋( 2 ，4 ) ； 步3 锄知+ 1 = 扩+ 舻驴，且m ( 七) m i n f m 佧一1 ) ，m j 步4 令七：= 七+ 1 。转步1 2 3 收敛性分析 本节我们利用非单调线搜索证明修正的l s 共轭梯度法的全局收敛性如无特别 声明，我们的算法均建立在假设a 成立的前提下，下面给出几个引理及其证明 引理2 3 1 设q 七，沙由算法2 2 j 产生，则 。l i 乎矿0 扩0 = o ( 2 6 ) 七+ + o o ” 、7 证明：由文献p q 中的证明可知，序列，( 一( 七) ) 是单调非增的事实上，由m ( 七+ 1 ) m ( 七) + 1 及式( 2 5 ) 可知 m 忡) 。o 1 都成立从而，对v 七n 有： 艮知) 一蠡一1 z 州= z 氏七) 一n “七) 一j 以七h ( 2 1 1 ) j = 1 又因为f ( 七) 一七一1 = z ( 七+ m + 2 ) 一七一1 m + 1 ，所以由( 2 7 ) 和( 2 1 0 ) 可知： 1 i mi i z 知+ 1 一z 。( 七) | i = o ( 2 1 2 ) 疗+ 1 7 河南大学硕士学位论文 又因序列，( ( 知) ) 存在极限且，( z ) 具有连续性，所以有： 。l i m ，( 矿) = ，l i m ，( ( 蠡) ) ( 2 1 3 ) 詹+ 席_ 而，( z 七+ 1 ) ，( ( 七) ) 一6 ( ) 2 0 驴| f 2 所以由( 2 1 2 ) ，( 2 1 3 ) 式可知 ，l i m 矿0 扩0 = o ( 2 1 4 ) 嚣 即结论成立 引理2 3 2 设扩是由算法2 幺f 产生的，若存在常量7 o ，使得对于任意的老n ， 有i 旷0 ，y ，则存在常量c o ，满足 0 矿0sc 8 矿1 1 ( 2 1 5 ) 证明：有驴的定义可知： l i d l l 幽i + 2 訾鞴簖 l | 纠i + 2 型铲 叫l l + 2 塑刽铲 刈i l + 2 业型薯嘉塑 州i i + 2 幽些坐篙等幽 ：l i 幽黜岛产o p + 丝学渺。1 1 由( 2 6 ) 可知，存在常量r ( o ，1 ) ，及整数硒，使得对所有的后，都有 警a 扩- l i o 满足 i i 矿i l c 怕七i j ，垤= o ，1 ， 且由引理2 3 1 ，若。l i mi n f q 七 o ，则，l i mi i l f0 矿0 = o ，则与假设矛盾 蓐+ r + 若 1 i mi n f q 知= o ， 席+ o o 则存在无限子集k ，满足 l i ma 后：0 七 由( 2 4 ) 式知，对任意的后k ，有 m 知+ ( 口七盯) 扩) 。g 羚七一) 卜舻呐邢 ，( z 南) 一6 ( a 知盯) 2 0 d 知1 1 2 1 9 河南大学硕士学位论文 由中值定理和引理2 3 2 及l 触i t z 连续式可知，对充分大的七k ，存在常数( o ，1 ) ， 使得： ，( z 奄+ ( 口七口) d 知) = ，( ) + ( q 奄口) 9 ( z 七+ ( q 磨仃) 驴) t 驴 =，( z 詹) + ( 矿口) ( 9 七) t 铲十( 口詹仃) ( 9 ( z 七十妒( q 七口) 矿) 一g 七) t ，( 矿) + ( 矿口) ( 矿) t 驴+ 三( 口七盯) 20 矿0 2 由上面两个不等式及( 驴) v = 一0 矿1 1 2 可知，对充分大的七k ， n 9 七0 2 ( l + 6 ) ( 舻盯) i l d 七0 2 又因为 扩= o ， 蠡k 所以 。h mi n fi 旷0 = o ， 詹+ 这与假设矛盾，即结论成立 第三章共轭梯度法解简单界约束优化问题 3 1引言 对于简单界约束优化问题( 1 1 3 ) ，我1 l j 说虿是它的稳定点，如果z q 满足下面的 条件： z i = 夏 k o 对于 任意z q ，指标集工( z ) ，f ( z ) 和u ( z ) 定义如下： l ( z ) = i ：z 如+ o i ( z ) v ( z ) ， u ( z ) = t ：甄+ k ( 茁) v 矗( z ) 】 ( 3 2 ) f ( z ) = 1 ，扎 ( u u 三) 2 1 l & o o 0 一 = 啦 当i p 时，雌定义如下： 砖= ( 玩矛) ， 矿， ( 3 6 ) 其中e i 是单位矩阵i 的第i 列，瓦是由列向量 色i i ) 组成的矩阵矛表示非积极变 量的调整搜索方向，定义形式如下： 矛= 二；+ 熊矛一巩矿，：三： c 3 i 一矿+ 熊矛一巩矿，南 o ， 、 其中 成= 管，而钆= 备， 其中矿= 砑9 七，雪七一1 = 扩一矿，并且讯= 忍( 扩一矿) 一并且矛具有充分下降性， 即： ( 矿) t 矛= 一渺| | 2 ( 3 8 ) 河南大学硕士学位论文 所以搜索方向舻有如下定义： ， i 如一砖，l 胪， 毋= 崛一砖，l 扩， ( 3 9 ) i ( 玩矛) i ， 庐 下面的结论表明当驴o 时，驴总是目标函数，( z ) 在当前迭代点扩处的一个下降 方向这个性质对于我们建立算法的全局收敛性非常重要，并且它的结论是显然的， 在此我们略去证明为了建立我们的全局收敛性，下面我们给出几个重要引理 引理3 2 1 如果舻是由阻珊到的，则 ( 矿) t 驴o 等式成立的充要条件是驴= o 证明：根据驴的定义有： ( 3 1 0 ) ( 矿) t 矿= ( 毋) t ( 如一砖) + ( 费) t ( u t 一砖) + 一( 毋) t ( 级矛k o l 上l u 七f 七 由矛的定义及( 3 2 ) 知，上式显然成立并且也意味着当且仅当砂= o 时，0 七) t 驴= o 成 立 引理3 2 2 设驴是由p 砂得到的，并假设驴o ，那么 觚n 1 警) “i i l i n n 赢 ( 3 1 1 ) 其中靠= s u p o 1 j + 吼( z 缸) v ( z 知) ， 砖 z + ( 一玩( ) v 五e 矿) ) z + e 七稆砖+ 磊毋 类似地，对于v 五( 矿) o 时，我们有磅+ 厶露如从上面的结论我们知道，当i f 奄时，职( 扩) = o ，即结论成立，其中i = l ，2 ，n 上面的引理说明当舻充分小时，我们有 昂( 2 知+ 口七矿) = 扩+ a 七驴，若o q 七矗( 3 1 3 ) 并且下面的投影心n l i j o 型线搜索成立：给定常数6 ( o ，l 2 ) ， 矿，m 是使得下式成立的最小的非负整数， ，( 忍( + 矿驴) ) ，( 扩) 一刚矿扩1 1 2 下面我们给出解决简单界约束优化问题( 1 1 3 ) 的算法如下： p ( o ，1 ) ，步长a 奄= ( 3 1 4 ) 算法3 2 1 步o 给定初始点z o q ，常数j ( o ，1 2 ) ，计算，( 。o ) ，9 ( 雾o ) 并且设南：= o ，若l l 傀i i o ，上式右边的不等式意味着v ( 扩) o 如果t 泸，我们可 类似的证明结论成立并且如果l 矿我们可以从( 3 7 ) 和( 3 1 0 ) 得v p 奄) = o 现在 假设扩是( 1 1 3 ) 的一个稳定点，由( 3 1 ) 可得： l = l ：z ；= 如，f 蠡= i ：矗 谚 咙) ，u 知= i ：砖= 让1 )( 3 1 6 ) 那么由( 3 7 ) 和( 3 8 ) 可以得到畦= o ，诒= o ，及砟= o 因此我们有沙= o 引理3 3 2 设，驴是由算法只2 j 产生的迭代列，则有 i i 驴1 1 2 o ，使得 1 1 9 0 ) 0 p ，v z 三( 3 1 8 ) 2 5 河南大学硕士学位论文 由引理3 9 可知， 七) 单调下降并且是下有界的，因此，( ) 是一个收敛序列由投 影a r i r 嘶。型线搜索的条件，可得 ，( 户h ( z 知+ q 后驴) ) ，( z 七) 一6 i l a 七d 七0 2 ，( 3 1 9 ) 即 6 q 七扩1 1 2s ，( 矿) 一，( 危( z 七+ a 七矿) ) ( 3 2 0 ) 对上式两端从七= o ，1 ，分别相加，同时由假设我们可以得到 即 ( 刚扩扩0 2 ) 【，( 矿) 一，( 昂( 矿+ 舻驴) j o ，使得 由( 3 1 0 ) ，我们有 1 9 ( z ) l l o ，使得 8 ( 如一z ；) 0 毛，t l 七， 0 ( 讹一砖) 0 ，i u 蠡 下面我们证明如果i 最，那么0 ( 最硭矛) i 0 是有界的首先，我们证明8 矛0 是上有界 的如果七= o 因为孑= 一卯，那么0 矛0 尬如果七 o 我们有： 剥 ，下面的不等式 成立： 学脚h 因此对任意的七 ，我们很容易的得到： o 矛o m + r i | 矛_ 1 0 + r 扣幻。矛。o 口南= o ，1 ，2 ， 河南大学硕士学位论文 由此可得 。1 i mi l 驴0 = o ， 万l j 上面的不等式和引理3 3 2 表明当奄一。时，萨_ o 因此，由引理3 3 1 知，是稳定点 这就意味着 啦i n f0 饥0 = o ， 一l ，u 与假设矛盾，所以结论成立 3 4数值实验 本节，我们将给出一些数值结果来验证算法3 。2 1 的实际表现所有的算法均采 用f o r t r 缸7 7 进行编程，初始参数设置如下：p = o 2 9 ，j = 1 0 ，吼( z ) = 1 0 一6 且玩( z ) = 1 0 一，终止准则为： i i 忍( z 七一9 南) 一z 七0 1 0 一5 或i l 忍( z 七一夕七) 一z 七i f 1 0 一5( 3 2 7 ) 其中忍( ) 表示z 在q 上的投影，如果求解某个测试函数时迭代次数超过1 0 0 0 0 ，或者函 数计算次数达到2 0 0 0 0 次，那么我们就说此时的算法就不具有收敛性，程序将被迫终 止我们的数值实验全部在c p u 处理器为1 6 g m 内存为2 5 6 m 的个人电脑上实现。所 有的试验函数都来自于c u t e r 【5 7 】，并且是变量超过5 0 个的简单界约束优化问题，数 值试验的结果我们将在附表中列出，下面我们给出表中各列的意义： p r o b l e m ： 问题的名称； d i m ： 问题的维数： i t e r ： 迭代次数： f c n t ： 函数的计算次数； g c n t ：梯度的计算次数； t i n