（运筹学与控制论专业论文）梯度法的步长与收敛性.pdf

摘要 梯度方向在无约束最优化技术的发展中起着重要的作用梯度 法是求解无约束最优化问题的一个基本迭代方法，它在迭代的每一 步沿着当前点的负梯度方向搜索下一个点步长的选取对梯度法的 收敛速度影响非常大，经典的梯度法一最速下降法在大多数情况下 收敛得相当慢的原因在于最优步长的选取本文研究了梯度法的收 敛速度和全局收敛性首先，对于n 个变量的一般形式二次正定目 标函数提出了一个步长选取的准则，并在此准则下证明了梯度法从 任意的初始点开始迭代，不超过n 步就能达到函数的极小点其 次，对于n 个变量的非二次目标函数也提出了一个步长选取的准 则，并在此准则下证明了当目标函数满足一定的条件时，梯度法具 有局部m 步二阶收敛速度最后构造了两种混合梯度法并证明了 它们的全局收敛性 关键词：无约束最优化，梯度法，收敛速度，二次终止性，n 一步 二阶收敛，全局收敛性 a b s t r a c t t h e g r a d i e n td i r e c t i o nh a sp l a y e da ni m p o r t a n tr o l ei nt h ed e v e l o p m e n to fu n c o n s t r a i n e do p t i n f i z a ti o nt e c h n i q n e s t h eg r a d i e n t m e t h o di sab a s i ci t e r a t i o nm e t h o df o rs o l v i n gu 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 m s ，t h em e t h o ds e a r c h e sf o rt h en e x tp o i n ti nt h e d i r e c t i o no ft h en e g a t i v eg r a d i e n ta tt h ec u r r e n tp o i n t t h ec h o i c e o f s t e p l e n g t hs t r o n g l ya f f e c t st i l ec o n v e r g e n c er a t eo ft h eg r a d i e n t m e t h o d ，t h ec l a s s i c a lg r a d i e n tm e t h o d t i l em e t h o do fs t e e p e s t d e s c e n tc o n v e r g e sr a t h e rs l o w l yi nm o s tc a s e s ，t h ep o o rb e h a v i o r o ft h em e t h o di sd u et ot h eo p t i m a lc h o i c eo fs t e p l e n g t h i nt h i s p a p e rt h ec o n v e r g e n c er a t ea n dt h eg l o b a lc o n v e r g e n c ep r o p e r t i e s o ft h eg r a d i e n tm e t h o da r es t u d i e d f i r s t l y ，ar u l eo ft h ec h o i c e o fs t e p l e n g t hi s t n e s e n t e df o rag e n e r a lp o s i t i v ed e f i n i t eq u a d r a t i c o b j e c t i v ef u n c t i o no fnv a r i a b l e s ，a c c o r d i n gt ot h er u l ew ep r o v e t h a tt h eg r a d i e n tm e t h o d s e q u e n c ew i t ha n yi n i t i a lp o i n tr e a c h e s t h em i n i m u m p o i n ti nn om o r et h a nni t e r a t i o n s s e c o n d l y ，ar u l e o ft h ec h o i c eo fs t e p l e n g t hi s p r e s e n t e df o ran o n q u a d r a t i co b j e c l i v ef u n c t i o no fn v a r i a b l e s ，a c c o r d i n gt ot h er u l ew ep r o v et h a tt h e g r a d i e n tm e t h o dh a sl o c a ln - s t e pq u a d r a t i cc o n v e r g e n c er a t ef o ra n o n q u a d r a t i cf u n c t i o nu n d e rc e r t a i nc o n d i t i o n s f i n a l l y ，t w oh y b r i dg r a d i e n tm e t h o d sa r ec o n s t r u c t e da n dt h eg l o b a l c o n v e r g e n c e p r o p e r t i e so ft i l et w om e t h o d sa r e1 n o v e n k e yw o r d s ：u n c o n s t r a i n e do p t i m i z a t i o n ，g r a d i e n tm e t h o d ，c o n v e r g e n c er a t e ，q u a d r a t i ct e r m i n a t i o n ，n s t e pq u a d r a t i c c o n v e r g e n c e ， g l o b a lc o n v e r g e n c e 致谢 首先我要特别感谢恩师侯定丕教授，自1 9 9 8 年以“四一五” 分流的身份进入硕博连读阶段学习以来，作者在侯教授的悉心指导 下，进行最优化理论与方法的研究在平时的学习、工作中，侯教 授渊博的知识，严谨的治学态度，为人的谦逊都深深地影响着我； 他不仅传授给我大量最新的专业知识，也教给我进行学术研究的方 法本文正是在侯教授悉心指导下完成的，作者谨向侯教授致以崇 高的敬意和衷心的感谢! 其次，我还要感谢我的师兄和师弟们，与他们的讨论使我受益 匪浅；另外，我的同学们也给了我很多的支持和帮助，在此一并致 谢。 同时，作者在数学系的学习和生活中得到了系领导和各位老9 f 的诸多关照，在此向他( 她) 们表示深深的谢意 最后，我要特别感谢我的父母和家人，感谢他们这么多年来的 全力支持，使我能够安心学习 2 0 0 3 年4 月 序言 谯鼯中求解给宛函数f ( x ) 的微小点的问题被称为无约柬最优化问题， 记为 翼器儿。j 翔果，妇) 连续可徽盈x 为，扛) 懿一个极，j 、点，粼x + 满建v ，和4 ) = o ，这 是n 个未知量、似个方程的方程组，并且一般是非线性的。只有在比较特殊 酌谤澄下，才霹潋求馥浚方程缀的精确躲在般情况下，试图通过解析方法 求解 v f ( x + ) = 0( 0 0 ，1 ) 魏糖鞴解来穗淹f ( x ) 懿驻熹遴常不太实际，嚣照常鬻奄不可貔实褒，溉寝糍 够找到f ( x ) 的驻点，鼹判断驻点是否为极小点也不容易因此在处理融约束 最挽化趣瑟融，逶常鼹数值方法逐步求o 矗1 ) 静近似瓣，这重掰说的数值方 法就是各种迭代方法。迭代方法的基本思想是：酋先给趣，茁) 的极小点r 的 一个初始估计髫l ( 称为初始点) ，然后按照一定的迭代准则计算出一系列的点 3 3 2 ，岛，x k ，并鼗期望当歹缸) 漆是一定懿条 警时，迭代序刭 魏 我稷 限就是f ( x ) 的一个极小点所谓的遮代准则就是如何产生这个迭代序列? 迄就是落在蠢了鬈之詹，强秘求褥。女+ l ? 可淡这撵寒考虑，因戈嚣女+ l 一嚣 是一个向量，而向量是由它的方向和长度来确邂的，即 x k + l 一。2v c k d ki e ：u k + l 。x k + o e k d k 其中敷是一个离蟹漭隽搜索方蠢) ，挫是一个委实数( 称势步长) 警 和d & 确定之后，由姒就可以啦一确定弧+ l ，如此反复进行就可以确定逼近 极，j 、赢的一个序列 ，从丽也就确定了一个迭代方法选取搜索方向文 秘步长雠的方法不同，特别是选取蟊的方法不同，靛形成各种不霹的迭代 方法 1 中国科学技术大学博士学位论文 2 1 8 4 7 年法国数学家c a u c h y 研究了函数值沿什么方向下降最快的问题， 首先提出了一个求解无约束最优化问题的迭代方法f 9 1 ，由于该方法在每一步 迭代中都以负梯度方向作为搜索方向，因此被称为梯度法又因为函数f ( x ) 在z 处的负梯度方向恰好是函数，( ) 在z 处的最速下降方向，所以梯度法也 被称为最速下降法现在梯度法【5 ，1 0 ，1 4 ，1 5 ，3 0 ，3 2 ，3 3 ，3 5 】已经成为众所周 知的一种最基本的迭代方法，它具有重要的理沦意义，对其它迭代方法的研究 也很有启发作用，因此在最优化方法中占有重要地位。梯度法具有简单、可靠 等优点，但是它收敛较慢，这与梯度法中的步长选取有很大关系 梯度法的迭代过程按照下面的公式进行： x k + l = x k n k v ( x k ) ，k = 1 ，2 其中a k 是沿着z k 处的负梯度方向一v y ( x k ) 最小化( x ) 的最小的非负数 即 o t k = a r g m i n ，( z k o v ，( z 女) ) ， 由此可以看出在迭代过程中的每一步，步长a 女的确定实际上是求解一个一维 最小化问题，这一求解过程通常被称为精确一维搜索c u r r y 1 1 证明了由上 述过程产生的梯度法迭代序列 的任何一个极限点z + 满足v f ( x + ) = 0 对于精确一维搜索下的梯度法，a k a i k e 1 ，f o r s y t h e 1 9 】，k a n t o r o v i c h 和 a k i l o v 2 7 1 先后证明了其收敛速度是线性的，而且收敛性质与极小点处h e s s i a n 矩阵的特征值有关甚至对于二次正定函数f ( x ) = g t z + x t 日茁( 显然唯一的 极小点是= 一h - 1 9 ) ，其中g 融，h 融“对称正定，梯度法的收敛 速度也仅是线性的f o r s y t h e 1 9 】还证明了：如果x 2 ，则对一切k 均有 z k z + ，且存在常数e 0 ，使得 盟f ( x k 瘩筹c 。) 一，( z + ) 7 。 中国毒每攀技术丈学撵掌靛论文 3 对 壬簿奄均箴立，_ 薅瞧警自爱：势夫霹v ，z j 婚在两拿方良上来回摆动，邵 v ，f m - 1 。l i r a 。；- 。- 。7 ；t e 2 d 恕糕“ 都存在 建予当迭 点离极小点缀遮时，糖确一继搜索通黎不是十努有羧，嚣踅 更有效的一维搜索的产生是十分必要的。a r m i j o 2 和g o l d s t e i n 2 4 分别提 窭了不精确一绦搜索，嚣来箴淹黉爱麓一弹不精确一维接索，键将其合称蠢 a r m i j o m g o l d s t e i n 不精确一维搜索准则。a r m i j o 在【2 1 中提出了种自动选取 步长熬娣度法；任意搔嶷一个燕数，；。，考惑穿列弘。一蒜譬，m = 1 ，2 ， 迭代序列定义为 x k + l = z 女一f z 。女v ，( z 女) ，奄。1 ，2 其中7 1 k 是潞怒 ，( 譬$ 一拶。v f ( x 女) ) 一，嚣女) ；p 。t i v f ( x k ) 1 1 2 的最小正整数他还证明了在一定条件下梯度法的收敛性在f 2 3 】的基础上， g o l d s t e i n 2 4 j 器癌了确定步长酌一个公式，在一定条 串下证翡了梯震法翡牧 敛性，并且给出了收敛速度的一个估计，但是其收敛速腰仅是线性的。 1 9 8 8 年b a r z i l a i 和b o r w e i n 3 j 提出了一个黼点步长梯度法，其基本思想是 零j 瑁遗代当蕊焱以及蘩一点的臻患寒确定步长因子。饿们把迭代公式墓+ l = x k 一“k v f ( x k ) 看成是 z b ￥i = z t 蛰i 霹 嫱心， 其中= 魂囊涵楚摊拜擎使矩簿) 为了艇矩终具毒8 投牛顿”性爱 【1 6 ，2 6 ，3 1 ，5 0 ，5 1 ，5 8 ，5 9 ，6 0 】，求o l k 使其满足 m i n | & 一1 一玩鑫一l 0 0 2 ) 中国科学技术大学博士学位论文 4 或者 m i n l i d i l 矗l 一靠一l ( 0 0 3 ) 其中靠一1 = x k m k l ，靠一l = v f ( x k ) 一x t f ( x k 1 ) 由( 0 02 ) 和( 0 0 3 ) 我 们可分别求得 a t = 勰 ( 0 0 4 ) 和 一糌 ( 0 0 s ) 两点步长梯度法的初始步长利用一维搜索确定，其它步长由( 0 0 ，4 ) 或( 0 0 5 ) 给出b a r z i l a i 和b o r w e i n 3 还讨论了目标函数是两个变量的二次函数时的 收敛速度，证明了若。- 由精确一维搜索确定，其它步长由( 0 0 4 ) 或( 0 0 5 ) 给出，则几乎对所有的初始点，两点步长梯度法r 一超线性收敛于极小点， 且r 一超线性收敛阶为以两点步长梯度法不足一个下降方法，因此当目 标函数不是二次函数时，要加以适当修改才可应用之后，r a y d a n 3 6 】给出 了，n 个变量的严格凸二次函数情形下两点步长梯度法的全局收敛性，d a i 和 l i a o 1 2 】证明了两点步长梯度法的收敛速度是r 一线性的 由于梯度法中步长的选取对梯度法的收敛性及收敛速度影响十分大，近 几年来还有不少学者对此问题进行了研究，可以参考b i r g i n 6 ，7 ，8 】，d a i 、 j y u a n 和y y u a n 1 3 】，f l e t c h e r 1 8 】，f r i e d l a n d e r 2 0 ，r a y d a n 3 7 ，3 8 ， v r a h a t i s 、a n d r o u l a k i s 、l a m b r i n o s 和m a g o u l a s 3 9 】等 梯度法在大多数情况下收敛得相当慢，其收敛速度与目标函数的形态密 切相关如果在极小点矿处函数f ( x ) 的h e s s i a n 矩阵v 2 f ( x + ) 的最大特征 值与最小特征值的比很大，则梯度法在z + 的邻域中以锯齿形移动【1 5 】而且 以往的结论表明梯度法最小化二次正定函数通常不是一个有限过程实际上 导致上述结果的原因在于步长的选取本文正是在此基础上，对梯度法进行进 一步的研究我们将对以下几个问题着重在理论方面进行探讨： 中莺辜； 攀接米太攀媾士拳垃谂文 s i 。黠予一般二趺正定邋数，设计步长选取准粼，研究梯度法鲍收敛性与收敛 逮凝； 2 ，黠予嚣二凌舔羧，设诗步长选取建瓣，璐究撵度法弱皎敛瞧与牧毁逮整； 3 步长的选取与全周收敛性、二次终止性的研究 蘧过鼹上述漓瑟懿深入磷究，我鳃芰疆；只要遗淑逶姿翡步长，撵褒溶瞧其膏 相当好的收敛性质 第一章准备工作 本辩酾裔静憋葶i 避臻基本概念和麓率结聚，为班腐错章作礴铸在1 1 中鼗 l 徐澎缒薄靛特征多项式、最小多磺式酶悫哭著照不黼谣瓣滚毅述了与 艇蹲静将蔹多项式、最小多项式露关翡几个基本定理，这些定理谯以尉露节 中媾多扶穗舞。瓢2 串蔑鬈 套缁了茏鳕策聚餐纯黼壤翡簸德淫条终，雹耩 蹬、二玲必螯絷搏，二龄楚分条抟及热墩 芄健袋终。l 。3 中攘述了迭技方法 懿基本愁徽势魏绦窝了逡壤穷法敝敛速窿辩定义。1 4 审穷嚣了缀典懿糖爱 浚拳耩串骥浚著整幂鸯谖骥戆救遴了它魍翡牧敛逮凌定褒。 耋王。薹翘阵峰特征多项式鸯蠡夺参壤式 零节将鹜麟一些美予筑箨懿黪征多矮姣毽谂懿基本糕念秘零文孛将娶援 戮翡一麓蒺零绫聚，其辫疆葫戳参考 2 l ，2 5 ，2 ，4 6 ，4 7 ，鹅，s 2 ，鑫3 ，斓 窥义l 。1 1 经凝a 是敷城f 上薛一夸椎x 耗方漆，炙楚嚣繇尊位始蹲， 即a 琶f “8 ，则薄款 妒f 秘一d e t ( 矗一a l 、l 、1 ) 避楚美譬太秘一夺站袭多颁式，谈多磺式凝拣舞方滓a 妁栲强多项式。黪鼹 多颂式妒蜀鼹珏夸狠a l ，a 2 ，k 甓舞旁簿a 蟪耱缸谯。 宠义l 。l 。2 缀设旁淬a 掌“”，藏薅零多磺式，q ；f f a 茹幕弘 一疆， 蝌，弘) 称为方踌矗砖一个纯零多项式。 京义1 , 1 。3 方簿冀秘魏骞纯零多囔式审次数最小秘曹一多磺式称海旁漆矗 的最小多项式，记为呶协) 。 美子方簿鹣褥征多矮蔽，鸯下瑟鳃黎簧定壤。 定理羔。1 4 c a y l e y 。h a m i l t o n 髭攫) a 遣一个秣l q , 孝簿，如暴a 的特瓴多 磺点秀妒，瓣妒固一尊， 8 串潜辩攀攘术大学博士学位论文 7 鲡皋椎霸鬟短簿a 是一个怼嚣楚簿，裁有下嚣懿定理 宠理1 1 5 假设a 是一个娃? b 寡对称方阵，且l l 方降a 最史牺姝q - 砖鸯形 d i a g o l ，a 2 ，k ) ，即存在一个7 。7 。寅正交方阵o ( o r o 一霸，o ，表示0 姆转置 。，建缮 a = 0 7 d i a g ( a 1 ，a 2 ，k ) 0( 1 1 ，2 ) 蕊中走，a 2 ，墨是旁鞯a 酶奎毒跨强谖 关乎最小多项式，以下性质成立 鬈l 瑾1 1 。6 最小多磺式妁畦绫 l ，方阵a 妁最小多磺式屯( 整除方潍a 的佟一 匕零多囔式芦 ；特嬲， 出( a ) 整除方阵a 的耱征多硕式妒( a ) ； 2 ，方海建妁菠小多项式蟊 a ) 囊在唯一； 3 相似方阵具宥相同的最小多项式 壶蠢獯i ，l ，5 裙弓l 璎1 1 藩，我秘冒羧嚣蘩熬下定壤。 宠理1 1 7 假设a 是一兮n 扎嶷对称方阵，则a 的簸小多项成为 d ( a ) = ( a a 1 ) ( a a z ) ( a a )( 1 1 3 ) 其中a 1 ，如，丸是旁簿a 的套鄙不褥的特征值 1 2 无约柬问题的最优性条件 奉帑缭毒芜鳓束簸优纯阏瑟 震蒜终) 1 , 2 1 ) 酶最霞瞧条 誓；雹篷摇一浚条簿鞫二酚袈律 凳娑，2 2 ，毒l ，4 承辩，蠡l ) + 极小点的类测有局部极小点和全局檄小点两种 中国科学技术大学博士学位论文 8 v m ，= ( 掣，掣) ， 叻= 蟹 中重辩攀技术大攀博学髓论文 9 孽l 理1 2 4 4 4 】觳设函数歹 。) 在点量可擞，如暴存在方向d ，使褥v 歹( 童) 丁d 0 ，使得对每个n ( 0 ，7 ) ，有 ，( 面+ a d ) 0 ，使得 熙躐硼 ( 1 。，) 则称迭代方法产生的迭代序列 x k ) 具有q 一卢阶收敛速度特别地， 1 当卢= 1 且口 0 时，迭代序列 z ) 叫做具有q 一线性收敛速度； 2 当1 1 则： l ，当r 1 = 0 时，称茁k 是r 一超线性收敛于z + ； 2 当0 r 1 1 时，称。k 是r 一线性收敛于茁+ ； 3 当r l = 1 时，称是r 一次线性收敛于x + 类似地， 1 当r 2 = 0 时，称。是r 一超平方收敛于x + ； 2 当0 r 2 1 时，称x k 是r 一平方收敛于+ ； 中国科学技术大学博士学位论文 1 2 3 当r 2 1 时，称x k 是r 一次平方收敛于z + 在下文中，所用到的收敛速度均为q 一收敛速度，为简便起见，我们用 线性收敛、超线性收敛和二阶收敛分别代替q 一线性收敛、q 一超线性收敛 和q 一二阶收敛 1 4 经典的梯度法与牛顿法 众所周知，梯度法和牛顿法是处理无约束最优化问题 础r a i n 。m ) 的两种基本方法，为我们提供了简单而直接的求解方案后来提出的一些方法 都是在这两种方法的基础上经过改进和发展而得到的，如共轭梯度法、拟牛顿 法等关于上述几种迭代方法的详细讨论可以参考 1 6 ，2 6 ，3 1 ，5 0 ，5 1 ，5 8 ，5 9 ， 6 0 1 。 1 4 1 经典的梯度法 经典的梯度法( 最速下降法) 是以负梯度方向作为每一步迭代的下降方 向，是无约束最优化中最简单的方法 假设函数f ( x ) 在x k 附近连续可微，且v f ( x k ) o 由t a y l o r 一展开式 ，( 。) = f ( x k ) + ( 茁一z k ) 7 r v f ( x k ) 十o ( 1 l x x k l l ) 可知，若记。一x k = a d k ，则满足蛭w ( x k ) 0 的方向也是下降方向当a 取定后，露v f ( x k ) 的值越小，即一耀v f ( x k ) 的值越大，函数下降得越快 由c a u c h y s c h w a r t z 不等式 v f ( z k ) l i $ d k h l w f ( x k ) l ， 故当且仅当d k = 一v f ( x k ) 时，d 1 1 v f ( x k ) 的值最小，从而称一v f ( x k ) 是最 速下降方向 中国科学技术大学博士学位论文1 3 经典的梯度法可以简单地描述为： 化当前点负梯度方向的函数而获得的 代序列 x k ) 由如下迭代公式定义： 在迭代的每一步，下一个点是通过最小 如果2 2 t 是任意给定的初始点，则其迭 x k + l = 3 ：k n 女v ，( 。 ) ，( 1 4 1 ) 其中a 由精确一维搜索确定，即使得 m k 一。k v m k ) ) 2 卿m k n v m 女) ) ， ( 1 4 2 ) 由此得到的o m 称为最优步长因子 下面，我们先介绍二次函数情形下经典的梯度法的收敛速度，然后介绍一 般函数情形下经典的梯度法的收敛速度。 当目标函数