（应用数学专业论文）线性约束最优化问题的投影梯度法.pdf

硕士学位论文：线性约束最优化问题的投影梯度法 i i i 摘要 最优化是一门应用性很强的学科近年来，随着计算机的发展以及交际问题的 需要，大规模优化问题越来越受到重视于是，快速有效的算法成为研究的热门方 向 最优化问题分为无约求最优化问题( 古典的求函数极值问题) 和带约束最优 化问题对最优化闽题的研究是近年来运筹学的热门问题，在经典最优化问题的 基础上许多国内外学者对算法进行了改进和创新。提出了一大批新算法j 对于约 束最优化问题的研究一直是优化专家们研究的热门方向之一其中比较著名的有 二次规划、逐步二次规划法、罚函数法、信赖域法、约束变尺度法和可行方向法 等 在约束晟优化问题的算法中怎样了找有效的下降方向是构造算法的重要内 容，在寻找下降方向方面可行方向法中的投影梯度法有效的解决了下降方向的 寻找问题。利用线性约呔问题边界点的任意方向在边界上的投影都足可行方向， 而负梯度方向的投影就是一个下降方向6 0 年代初r o s e n 提出投影梯度法的基本思 想，自从r o s e l l 提出该方法以后，对它的收敛性问题不少人进行了研究，但一般都 是对算法作出某些修j 下后才+ 能汪明其收敛的，直到最近对r o s e n 算法本身的收敛 性的证明才予以解决般影梯度法是最速下降法对约束问题的推j 因此没有较快 的收敛速度，为了解决这个问题很多中外学者把发展得比较成熟的无约束最优化 算法作类似的推广，其中煎轭梯度方法是近年发展的很成熟的方法，它具有计算 简单，算法结构好，计算量少具自良好的收敛性等优点，而r o s e n 投影梯度法的 提出使寻找下降方向，叟得简单 本文提出基于投影梯度法与无约束最优化问题的下降类算法相结合的几类 新算法使新算法将无约束最优化问题的下降类算法推广到线性约束最优化问 题 在第一章我们简要的介绍了最优化问题的提出以及判断最优解常用的最优 性条件，回顾了最优化问题的几类芋要算法 在第二章中我们把一种新的其轭梯度法( h s d y 混合芪轭梯度法) 与p “j $ e n 投 影梯度相结合，提出了线性等式约束最优化问题的一种新算法，并在w o l f e 线搜索 下证明了算法的收敛性 在第三章中我们将无约束问题的一类下降算法与r o s e n 投影梯度法相结合将 其推j “到线性等式约束最优化问题，提出了线性等式约束最优化问题的一类投影 下降算法，并提出了基于这类算法的混合算法，在w o l f e 线搜索下证明了这两类算 法的收敛性，并通过数值试验验征了算法的有效性 ：! 兰：丝圭兰竺丝圭：垒丝竺查塞丝丝望墨竺丝丝丝塞苎 在第四章中我们提出了线性不等式约束最优化问题的一个投影梯度算法框 架，做了数值试验，但其收敛性还有待进一步研究 关键词：约束最优化，共轭梯度法，投影梯度法，收敛性，( 强) w o l f e 搜索 硕士学位论文：线性约束最优化问题的投影梯度法 v a b s t r a c t o p t i m i z a t i o ni so n eo fs u b j e e tw i t hs t r o n ga p p l i c a t i o n a st h ed e v e l o p i n go ft h e c o m p u t e rt e c h n o l o g ya n dt h er e q u i r e m e n to ft h ea c t u a lp r o b l e m s ，t h ec o s m i c a l l yo p t i m i z a t i o ni sb e e ne n l i g h t e nm o r ea n dm o r e ，a n dt h e nt h ec e l e r i t ya n de f f i c i e n c yw a yo f a r i t h m e t i ci sb e c o m i n gt oav e r yh o tt o p i ci nr e c e n tr e s e a r c h t h eo p t i m i z a t i o nc o n t a i n st w od i f f e r e n tb r a n c h e s ，o n ei st h eo p t i m i z a t i o nw i t h o u t c o n s t r a i n t ，w h i c hi st h ec l a s s i c a lq u e s t i o nt og e tt h e “t r e m u mo faf u n c t i o n ；a n dt h e o t h e ri st h eo p t i m i z a t i o nw i t ht h ec o n s t r a i n t a st h eo p t i m i z a t i o ni sav e r yi n t e r e s t i n g p r o b l e mi no p e r a t i o n a lr e , e a r c h ，m a n yo fr e s e a r c h e r sh a v ep r o p o s e dl o t so fi m p r o v e - m e n t sa n di n n o v a t i o n so fa r i t h m e t i cu n d e rt h ec o n s t r u c t i o no fc l a s s i c a lo p t i m i z a t i o n t h e o r y t h es t u d yo ft h eo p t i m i z a t i o ni sa ni m p o r t a n td i r e c t i o no ft h eo p t i m i z a t i o nr e - s e a r c h e r st o o ，a n dt h e yh a v eg o tm a n yo f a c h i e v e m e n t s ，s u c ha 8q u a d r a t i cp r o g r a m m i n g ，s e q u e n t i a lq u a d r a t i cp r o g r a m m i n g ，p e n a l t yf u n c t i o nm e t h o d ，t r u s td o m a i nm e t h o d ， c o n s t r a i n td f p ，f e a s i b l ed i r e c t i o nm e t h o d ，e t c h o wt os c a r 血t h ee f f e c t i v ed e s c e n d i n gd i r e e t i o ni sv e r yi m p o r t a n ts t e p si nt h e o p t i m i z a t i o na r i t h m e t i c t h ep r o j e c t i o ng r a d i e n tm e t h o dw i l lh eap o s s i b l ew a yt o s o l v et h ep r o b l e mt h a tw ej a s tg e t i th a sb e e ns h o w nt h a tt h ep r o j e c t i o n so ft h ee v e r y d i r e c t i o n s ，o fw h i c hi st h eb o u n d a r yp o i n ti nl i n e a rr e s t r a i n tp r o b l e m s ，a c et h ep o s s i b l e d e c e n td i r e c t i o n s ，a n dt h ep r o j e c t i o no fn e g a t i v eg r a d sd i r e c t i o ni sad e c e n td i r e c t i o n i n1 9 6 0 i k 】s e np r o p o s e dt h eb a s i ci d e ao fp r o j e c t i o ng r a d i e n tm e t h o d s a n dt h e nl o t s o fr e s e a r c h e r sh a v eb e e nt r i e dt of i n dt h ec o n v e r g e n c eo ft h i sm e t h o d b u tm o s to f t h e mg e tt h ec o n v e r g e n c ew i t ht h ec o n d i t i o nt oa m e n dt h ec o n v e r g e n c ei t s e l f u n t i l r e c e n t l y , t h ec o n v e r g e n c eo ft h ep d ) s e n sa r i t h m e t i ch a sb e e np r o v e d t h ep r o j e c t i o n g r a d i e n tm e t h o di st h eg e n e r a l i z a t i o no fs t e e p e s td e c e n tm e t h o dt oc o n s t r a i n tp r o b l e m s oi td o e sh a v eaf a s t e rc o n v e r g e n c es p e e dt h a tt h ef a s t e s td e c e n tm e t h o d t os o l v e t h ep r o b l e m ，m a n yr e s e a r c h e r sh a v eg e n e r a l i z a tt h ew e l l - d e v e l o p e do p t i m i z a t i o nw i t h u n c o n s t r a i n tt ot h er o s e n sg r a d i e n tm e t h o d t h ec o n j u g a t og r a d i e n tm e t h o di so n eo f s u c c e s st os o l v et h ep r o b l e m ，t h ec a l c u l a t i o ni ss i m p l e t h es t r u c t u r eo ft h ea r i t h m e t i c i sw e l l d e f i n e d ，a n di tg e t st h ea d v a n t a g eo fg o o dc o n v e r g e n c ea l s o s ot h er o s e n sg r a - d i e n tm e t h o dh a sp r o p o s e da ne a s ym e t h o dt os e a r c ht h ed i r e c t i o no fd e c e n tm e t h o d i nt h i sp a p e rf l o m en e wa l g o r i t h m sw i t hl i n e a rc o n s t r a i n e do p t i m i z a t i o na r ep r o - p o s e db yc o m b i n gt h ei d e ao fc o n j u g a t eg r a d i e n tm e t h o da n dt h er 0 8 e n sg r a d i e n t p r o j e c t i o n w em a k ei l s eo fu n c o n s t r a i n to p t i m i z a t i o nq u e s t i o n sm e t h o dt ol i n e a rc o n - 硕士学位论文：线性约束最优化问题的投影梯度法 s t r a i n to p t i m i z a t i o nq u e s t i o n i nc h a p t e r1w ei n t r o d u c e dt h ed e v e l o p m e n to fo p t i m i z a t i o na n ds o m ee x t e n s i v e o p t i m a l i t yc o n d i t i o n sw h i c ht od e c i d et h eo p t i m u ms o l u t i o n w er e v i e w ds e v e r a lm e t h - o d so fc o n s t r a i n e do p t i m i z a t i o n i nc h a p t e r2w ep r o p o s eal i n e a re q u a l i t yc o n s t r a i n to p t i m i z a t i o nq u e s t i o n ，t h e n e wa l g o r i t h mi sc o m b i n e dw i t ht h en e wc o n j u g a t eg r a d i e n tm e t h o d ( h s d yc o n j l l - g a t eg r a d i e n tm e t h o d ) a n dr o s e n sg r a d i e n tp r o j e c t i o nm e t h o d 。a n dh a sp r o v e ni t s c o n v e r g e n c eu n d e rt h ew o l f el i n es e a r c h i nc h a p t e r3w eh a v ec o m b i n e dad e s c e n ta l g o r i t h mo fc o n s t r a i n tq u e s t i o nw i t h r o s e n sg r a d i e n tp r o j e c t i o n a n dp r o p o s e dal i n e a re q u a l i t yc o n s t r a i n to p t i m i z a t i o n q u e s t i o n sn e wa l g o r i t h m ，a n dp r o p o s e dac o m b i n i n ga l g o r i t h ma b o u tt h i sa l g o r i t h m ，t h e n w eh a v ep r o v e nt h e i rc o n v e r g e n c eu n d e rt h ew o l f el i n e8 e a r c h ，a n dh a sp e r f o r m e dt h e n u m e r i c a le x p e r i m e n t a t i o n ， i nc h a p t e r4w ep r o p o s e dal i n e a ri n e q u a l i t yc o n s t r a i n to p t i m i z a t i o nq u e s t i n nf r a m e a b o u tp r o j e c t i o no fg r a d i e n ta l g o r i t h m ，a n dh a sp e r f o r m e dt h en u m e r i c a le x p e r i m e n t a - t i o n ，b u ti t sc o n v e r g e n c ea l s on e e d sf u r t h e rs t u d y k e y w o r d s ： c o n s t r a i n e do p t i m i z a t i o n ， p r o j e c t i o nm e t h o d ( s t r o n g ) w o l f el i n es e a r c h ， c o n j u g a t eg r a d i e n tm e t h o d ，g r a d i e n t g l o b a lc o n v e r g e n c e 硕士擘位论文：线性约束最优化问题的投影梯度法 i x z = ( z “一，) t r ” ，( 功c 1 ( _ d ) ，d c 舻 ，( z ) 俨( d ) ，d c 兄，l v ，( z ) v 2 ( x ) x k g k = 审，( k ) g k = v 2 f ( x k ) 全文通用记号 z 为实数域上的n 维向量 ，( z ) 在区域d 上一阶连续可微 ，( z ) 在区域d 上二阶连续可微 函数，( 啪梯度向量( 掣，骝) 1 函数他) 的h 砒n 矩阵( 象锯) 第k 个迭代点 函数，( ) 在z 点的梯度向量 函数，( z ) 在。k 点的h e s s i a n 矩阵 另外，若不作特殊说明，文中的所有范数| | 均指欧氏范数0 2 首都师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或 集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律结果山本人承担。 学位论文作者签名：， 、南桫开期：祷瑚硐 首都师范大学学位论文授权使用声明 本人完全了解首都师范大学有关保留、使用学位论文的规定，学校有权保留 学位论文并向国家丰管部门或其指定机构送交论文的电子版和纸质版。有权将 学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅。有权 将学位论文的内容编入有关数据库进行检索。有权将学位论文的标题和摘要汇 编出版。保密的学位论文在解密后适用本规定。 学位论文作者签名：、 。咿目r 期：。朝硐 硕士学位论文线性约束最优化问题的投影梯度法 第一章 最优化问题简介 这一章罩，第一节简要介绍最优化问题的提出以及削断最优解常用的最优 性条件；第二节简要介绍求解无约束最优化问题常用的几类导数下降类算法，第 三节简要介绍求解约束优化问题的几类丰要算法 1 1最优化问题的提出及最优性条件 为了使系统达到最优的目标所提出的各种求解方法称为最优化方法虽然最 优化问题可以追溯到十分古老的极值问题，但直至1 j 1 9 4 7 年d a n t z i g 提出一般线性规 划问题的单纯形法之后，它才成为一门独立的学科近年米，随着系统科学的发展 和讣算机的广泛应用 最优化理论与方法在工程、国防、经济、管理等领域以及许 多数学分支都有着直接或问接的应用 一般来说，最优化问题可归结为求解如下的极小值问题： 婢m ) ( 1 1 - 1 ) 其中，。d 是决策变量，( 。) 为目标函数，d 舻为可行域特别地，如果可行 域d = 酽测最优化问题( 1 1 1 ) 称为无约束最优化问题： 础r a i n 。m ) ， ( 1 1 2 ) 其中f ：r t i r 为连续函数而约束最优化| u 】题通常记为： 础m i n 。m ) s t c f ( z ) = 0 ，i = 1 ，一，m 。； ( 1 1 3 ) q ( z ) 0 ，t = m 。+ 1 ，一，m ， 其中，c i ( 。) 足约束函数，m 足一j 下整数，m 。足介于0 和m 之蒯的整数此时我们通常 e e = 1 ，2 ，m 。 ，f = m 。+ 1 ，m ，i ( x ) 一例以( z ) 0 ，i f 当目标函 数和约束函数均为线性函数时，问题( 1 1 3 ) 称为线性规划当目标函数和约束函数 中至少有一个为非线性函数时，问题( 1 1 3 ) 称为非线性规划此外，根据决策变量、 目标函数的要求不同，最优化还分成了整数规划、动态规划、光滑规划、非光滑规 划、随机规划、几何规划、多目标规划等若干分支本文丰要研究约束最优化问 题( 1 1 3 ) ：! ：堡圭兰竺丝耋垒兰丝叁叁丝丝望垒丝丝篓丝鏖苎 下面我们给出全局最优解和局部最优解的定义 定义若矿d 具有性质：坛d ，均有f i x ) f ( z ) ，则称矿为问题1 1 1 ) 的全 局最优解 定义若矿d 具有性质：存在矿的某个邻域( 矿) = 扣z 一矿8 o 为某个j 下数，使得比d n n 6 ( z ) ，均有f ( x ) f ( x 4 ) ，则称矿为问题( 1 i 1 ) 的 一个局部最优解 当目标函数，( z ) 足凸函数时，局部最优解就足全局屉优解但在一般情形下求 出全局最优解非常困难，通常在非线性优化中我们认为局部最优解即为所求的 解在实际的算法中，我们通常是求出满足局部最优解的必要条件的点下面我们 给出这些必要条件： 引理 l l f 无约束优化一阶必要条件) 若矿为问题( 1 1 2 ) 的一个局部最优解，且在的菜个邻域内，( z ) c l , 则 g ( 矿) = 、t ( z ) = 0 引理叭无约束优化二阶必要条件) 若矿为问题( 1 1 2 ) 的一个局部壤优解，且在矿的某个邻域内，( 种c 2 , 则 9 ( 矿) = 0 ，g ( 矿) ；v 2 ，( 矿) o 山于一般约束优化问题( 1 1 3 ) 的必要条件叙述起来比较复杂，我们仅给出一 个最常用的一阶必委条件 引理叭k u h i 卜1 、l c k e r 必要条件) 若矿为问题( 1 i 3 ) 的一个局部最优解，y 、t c 4 ( z 4 ) “e u l ( x ) ) 线性无关，则 必存在向量+ = ( 店，；，t ) t 使得 m v m + ) + 埘v c 4 ( x 4 ) = 0 ， ；= i p ；0 ，；v a ( z ) = 0 ，i i 1 2 无约束优化的导数下降类算法 求解无约束优化问题( 1 1 2 ) 的方法大都属于迭代法许多迭代法的基本思想 是：从某个初始点z 。出发，按照使目标函数值下降的原则构造点列 z 女 ，使得点列 项士学位论文：线性约束最优化问题的投影梯度法3 z i 中的某个点或某个极限点是问题( 1 1 2 ) 的解或稳定点这类算法因为要求函数 值要有所下降而称为下降算法它又可划分为单调下降算法和非单调下降算法单 调下降算法每进行一步都要求函数值有所下降，即要求点列 z k 满足 ，( z i + 1 ) 0 ，使得 f ( z + a d ) ，( z ) ，v a ( 0 ，a ) ， 则称d 足函数，在点。处的一个下降方向 当，一阶可导时，易证满足鳍如 o g 分小时，f ( z k + a d k ) o ，使，( z - 6o 女d k ) o 令k ：= 0 2 若i i g l l ，则终止算法，得解z 否则转3 3 确定下降方向以使得 v f ( x 女) 7 d k o ，使得 f ( x k + n k d ) 0 i n m k + q 砒 它一般只用于理论研究非精确线性搜索是一些较弱的步长原则。常用的有a n n i j o 线搜索、c o l d s t e i n 线搜索、w o l f e 线搜索等 4 硕士学住论文：线性约束最优化问题的投影梯度法 k a r m i j o 线性搜索 给定p ( 0 ，1 ) ，选取“k 满足： f ( x + o l k d k ) sf ( x k ) + p a k g ( 。) r d k r g o l d s t e i n 线性搜索 给定p l ，p 2 ，0 p l 一2 1 ，选取q k 满足： f ( x k + a k d k ) sf ( z k ) + p l a k g ( z k ) 丁d 女， ，( z 女+ o t k d k ) 2 ，( z k ) + p 2 q g ( x k ) 丁d k w o f ，e 线搜索条件： ，( z k + x k d k ) sf ( x t ) + 口a k g ( z ) 7 以d ( o ，：) ， g ( x k + a d k ) r 以国( z 女) r d k序( 口1 ) 记妒( ) = ，( 。+ a d k ) ，则，( o ) o ) 下证明了当& = m a x o 硝8 且线搜 索满足强w o l f e 线搜索时算法具有全局收敛性，而且结论对隗= m a x o 。堆8 也成 立，但p r 方法和h s 方法数值表现往往 ：l f r 方法更有效1 9 9 9 年，d a i 和y u a n l 9 l 在w o l f e 线搜索下不需给定下降条件即g 以 0 ，证明了d y 方法的全局收敛性，文献 9 】中 1 2 硕士擘位论文：线性约束最优化问题的投影梯度法 进一步研究了与d y 方法相关的混合算法，其中成= 7 1 卵7 ，丁1 【；丢，l l ，在相同 条件下证明了全局收敛性考虑到h s 方法好的数值表现和d y 方法好的收敛性，戴 志锋、陈兰平【l 目给出了一个新的h s - d y 的混合算法，其中： 凤= 澄= 硪舭“删州2 1 v 训训| 2 ； ， 新算法不需给定下降条件，在标准w o l f e 线搜索下，证明了算法的全局收敛性同 时得到： 0 口 1 2 ，雠= r 2 p 尹7 ，您【_ 1 ，i i ( 2 1 4 ) 1 2 s 口 o 使： g ( ) 一g ( y ) | | 工l i 一”，v ，ye l f 本章算法中的步长n k 由w o l f e 准则得到： f ( x k + n k d k ) ，( z 膏) + p 毗蠢也 g ( z + a k d k ) 7 d k a g d k 其中0 p 盯 0 ，k ：= 1 ，岛= 0 ，d o = 0 步2 ：如果i i p 鲰0 e ，则停止，得到问题( p ) 的k t 点；否则计算方向 d k = 一p + 8 k d k i 仇= 臀= 叫，“砌邮 啪川魄| | 2 醒8 = 髦芸裂； 酽= 聒i 而i p g k l l 2 步3 ：l h w o l f e 线搜索( 2 2 1 ) ，( 2 2 2 ) 求得o ，令 转步2 z k + 1 = x k + n d k ，k ：= 七+ 1 ( 2 2 1 ) ( 2 2 2 ) ：! ! ：丝圭兰竺查茎垒丝竺叁塞丝丝塑墨竺丝丝塑皇兰 2 3 全局收敛性 引理2 11 1 6 1 设目标函数满足假设h ，若方向d 1 使得a d l = 0 ，则按d k = 一户饥+ 鼠一。以一。式产生的方向序列 以 满足： a d k = 0 ，( p g k ) 7 d k = 蠢d k ，( p g k + 1 ) t d k = 蘸+ 1 d k ，v k 1 引理2 2 1 1 7 1 设目标函数满足假设h ，考虑一般方法z + l = x k + , 1 k d k ，其中毗满 足鲰 0 ，步长o * 山w 0 1 罐索( 2 2 1 ) ，( 2 2 2 ) 求得，则有 此关系式我们称为z o u t e n d i j k 条件 山引理2 1 和引理2 ，2 容易得到以下引理 引理2 3 设目标函数满足假设h ，考虑一般方法z i + l = 船+ o z k d k ，其中文满 ) 已( p g k ) t d k 0 。步长n 女山w i l f e 搜索( 3 1 4 ) ，( 3 1 ，5 ) 求得，则有 掣慨ild 惫 k l l 2 “ 此关系式我们称为推广的z o u t e n d i j k 条件 引理2 4 设本章算法产生的方向为出，步长n 女t l i w o l f e 搜索( 2 2 1 ) ，( 2 2 2 ) 求得，则 对所有k 1 ，有瓤t 如 0 证明： 当n = 1 时 d 1 = 一p g l ，g f d l = 一g t lp g l = 一g t p t p 9 1 等一( p 9 1 ) r p g l = 一l i p 9 l 2 。 惶lo 塑 l 竺圭兰竺丝耋垒兰丝查墨丝丝望兰竺丝丝丝皇兰 ：! 坠 对，l = k 时，我们分别讨论1 2 s ， 1 及o 茎口 1 2 两种情形 第一种情形：当l 2 茎口 1 时， 风：l 醪5 ，o 。黜 以也= 靠d k = g l ( 一p g k 十凤d 一1 ) 一2 + 鹄札- = 器正- “钏( 2 删 ( 2 ) 若晚= 醒8 ，则 0 ( 尸鲰) t p g k l a ( p g k ) r p g k 一1 ， 从而有： 靠d k 0 第二种情形：当o 1 2 f i j ， 凤= 臀= “，陆1 2 ”2 仁s 脚 1 6 硕士学位论文：线性约束最优化问题的投影梯度法 ( 3 ) 若仇= 印”，同理有( 2 3 3 ) 式成立因此有： 靠d k 0 ( 4 ) 若仇；磅8 ，因为o ( p 肌) t p 珊一1 2 1 1 p g k l l 2 1 r l l p g i u 2 所以山( 2 3 5 ) ，知鲧d k 0 引理2 5 同引理2 3 中的条件，则有( 2 1 ，4 ) ，( 2 i 5 ) t 从而帆is 印。成立 证明：当0 口 l 2 ，威按( 2 3 6 ) 取值时 若 则 0 ( p g k ) 7 p 鲰一l 2 i p g k l l 2 风= 解ks = 鼍鳅笔笋= 矽一丽( p g k ) t p g k - i 山( 2 3 1 ) ，( 2 3 7 ) 可得 山( 2 3 8 ) 可得 由( 2 3 6 ) 可知 耀- 而2 1 1 雨p g k l p 一夏( p 而g k ) 雨t p g l - i 。d 乏l ( 鲰一鲰一1 ) 、d 己l 一9 ) 一 一吾2 y ( 0 k = 百2 s ( 百0 y 以i 醒7 ( 2 3 7 ) 当l 2 口 1 ，熊按( 2 3 6 ) 取值时 若 o ( 魄) r p g c l 扣魄悒 ( 2 3 9 ) 则 8 k = 醒ks 山( 2 3 1 ) ，( 2 3 9 ) 可知 一；器 一黔 。一孑j 享j i 元_ = 面一j 夏i i 元_ = 厕u 山( 2 3 8 ) 可知 ( 1 一；) 第。 仇= 帮5 0 ，使得 0 尸鲰| | 22c k = 1 ，2 ， d k + p 鲰= 口k d k 一1 上式两端取模平方，并移项可得： i i d k l l 2 = ( 成) 2 恢一1 酽一2 ( p g k ) 7 以一8 功胛， d 1 3 1 理2 5 可知i 以i 醪7 0 d 女1 1 2 ( 面p 7 ) 2 i i d k l9 2 2 ( p g k ) 7 d k l i p g k l l 2 山( 2 3 3 ) 可知 秽= 糌 将( 2 3 1 4 ) 代x ( 2 3 1 3 ) ，两边除以( ( p 鲰) 7 d k ) 2 可得 i i d o l 2 ， ( ( p g k ) t d k ) 2 3 l i d 一i l l 2 2 l i 尸仇1 1 2 ( ( p g k 一1 ) 7 d k 1 ) 2( p g k ) t d k( ( p 饥) 7 出) 2 ( 2 3 1 0 ) ( 2 3 1 1 ) ( 2 3 1 2 ) ( 2 3 1 3 ) ( 2 3 1 4 ) = i i 五l ：l d 了k - 严, 砑r 1 2 一砸未丽+ 可t i p 鲰g j k 。l l 。k ) 2 + 1 i i p g k l l 2 2 i i 五：了严i i i 产一丽十可鲰j - n k 十 d+丽1(pgkd k ( 2 ，s m ) 2 (一1 ) 7 1 ) 2 。i i 即k ”一7 又因为 i i d l l l 2 1 币丽f 砰2 丽 1 8硕士学位论文：线性约束最优化问题的投影梯度法 所以t h ( 2 ，3 1 5 ) 递推： 山( 2 3 1 6 ) 可得： 所以 ( ( p g 网k ) t 广d k ) 2 ；i i 以0 2 一。 妻掣：+corld 鲁 k l t 2 可知上式与引理2 3 中结论矛盾。假设不成立，于是定理得征 ( 2 3 1 6 ) 本帝的创新点：萸轭梯度法是解决无约束最优化问题的一种十分有效的算 法，苁轭梯度法也是近年米已经十分成熟的方法，而h s - d y 混合苁轭梯度法兼具了 h s 和d y 两种经典算法的优点，有较快的收敛速度和良好的数值表现本文结合r o s - e n 投影梯度思想将h s - d y 混合共轭梯度法推广到线性等式约束最优化问题，使无 约束最优化问题的算法能够应用到约束最优化问题中去：本算法有效地解决了 r o s e n 投影梯度法收敛速度慢的问题，并且在w o l f e 线搜索下证明了新算法的收敛 性 七一c 一 。 一 止监 硕士擘位论文：线性约束最优化问题的投影梯度法1 9 第三章 求解线性等式约束最优化问题的一类投影下降算法 3 1 算法的构造及搜索条件 考虑无约束最优化问题 删r a i n ，m ) ， 其中，：j p r 为连续可微函数求解陔问题的一种迭代算法形式为 z 七+ i = z k + o k 以， 詹= 1 ，2 ， 其中 呶： 哪， 盯忙1 ； ， i o k + 仇矗一1 ， l ，k 22 代表搜索方向，o t k 是通过一维线搜索得到的步长，凤为一标量，鲰= 9 ( z ) 是，( z ) 在z k 处的梯度 潘翠英、陈兰平| 1 8 | 对于求解无约束优化问题提出了一类新的下降算法，其中 茚c _ p g 吾d k - 1 - t ( p a n - c h e n ) ， 这里osf l 口可以看出，当= 1 时，p c 算法( 11 6 ) 即为d y 算法当“= o 时，即为 最速下降算法 本章利用p c 算法提出了对求解线性等式约束优化问题的一类新的投影下降 算法( p - p c ) ，并且给出了与该算法相结合的一类杂交算法( p p c h s ) ，在w o l f e 线搜 索下不需给定下降条件，即证明了它们的全局收敛性 考虑线性等式约束最优化问题( p ) ： 舢m i n 。m ) s t a z = b 其中可行集骑= z i 弘l a z = b ，：j p r 为连续可微函数a 为m n 的 行满秩矩阵，定义梯度函数9 及投影矩阵p 分别为： 9 ( z ) = v f ( x ) ，鲰= v f ( x ) ，p = j a 7 ( a a r ) 一1 a 2 0 硕士学位论丈：线性约束最优化问题的投影梯度法 求解浚问题的一种迭代算法形式为 z + l = z 女+ n 女d k ，k = 1 ，2 ，( 3 1 1 ) 其中 虻 ：纛酽“，笼： 慨挖， 代表搜索方向，n t 是通过一维线搜索得到的步长馥为一标鸯 其中撵c 可以为零，当j 罗= o 时，算法即为r o s e n 投影梯度法 本章算法的翟c 为以下式子， 酽=#gtdk_l t d ( 3 1 3 ) 其中i i 表示欧氏范数，这罩o p l 口可以看出，当p = o 时，算法为m n 投 影梯度法 步长n 可通过精确线搜索或非精确线搜索求得常用的一种非精确线搜索是 标准w o l f e 线搜索，其形式如下： f ( z + a k d k ) sf ( x k ) + p o 筇毗，( 3 1 4 ) g ( x + n 以) 丁d k2a g 暑d k ( 3 1 5 ) 其中0 p 0 ，d l = 一p 9 l ，令七：暑1 步2 ：如果8p 仉 ，则停止否则转步3 步3 ：t h w o l f e 搜索( 3 1 4 ) ，( 3 1 5 ) 求得n ，山( 3 1 1 ) 求得z t + 1 步4 ：山( 3 1 ，3 ) 计算西盘，t h ( 3 1 2 ) 计算以+ l ，令女- 女+ 1 转步2 引理3 1 i i q 对于一般函数，( z )