（运筹学与控制论专业论文）无约束最优化的新迭代格式.pdf

摘要 本文以o d e 轨线为基础并运用预测一校正技巧，导出求解无约束优化问题的新迭代格 式其基本思想是：先在当前迭代点进行线搜索得到预测点，再通过这两点构造二次插值曲 线逼近某个o d e 轨线，最后沿该插值曲线搜索得到新迭代点特别地，对沿最速下降方向和 拟n e w t o n 方向的新迭代格式，本文给出了全局收敛性分析 对一组标准试验问题的数值试验获得了令人鼓舞的结果与最速下降方向，d f p 和 b f g s 公式相关的新迭代格式所需c p u 时间，函数和梯度计算次数均比传统格式有显著 减少 关键词t 无约束最优化；迭代格式；最速下降法；o d e ；拟n e w t o n 法；d f p ；b f g s a b s t r a c t b a s e do no d et r a j e c t o r y , t h i sp a p e rd e r i v e sn e wi t e r a t i o ns c h e m e s ，u s i n gp r e d i c t o r - c o r r e c t o r t a c t i c ，f o ru 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 eb a s i ci d e a ：i to b t a i n sap o i n t ( p r e d i c t o r ) b ys o m el i n e s e a r c hf r o mt h ec u r r e n tp o i n t ；t h e nw i t ht h et w op o i n t si tc o n s t r u c t saq u a d r a t i ci n t e r p o l a t i o nc u r v e t oa p p r o x i m a t es o m eo d et r a j e c t o r y ；f i n a l l yi td e t e r m i n e san e wp o i n t ( c o r r e c t o r ) b ys e a r c h i n g a l o n gt h eq u a d r a t i cc u r v e i np a r t i c u l a r ，t h i sp a p e rg i v e sag l o b a lc o n v e r g e n c ea n a l y s i sf o rs c h e m e s a s s o d a t e dw i t ht h es t e e p e s td e c e n ta n dq u a s i - n e w t o nu p d a t e s n u m e r i c a lr e s u l t so fo l l rc o m p u t a t i o n a le x p e r i m e n t s f 曲as e to fs t a n d a r dt e s tp r o b l e m sa r e e n c o u r a g i n g t h es c h e m e sa s s o c i a t e dw i t ht h es t e e p e s td e c e n ta n dd f p b f g su p d a t e so u t p e r o f o r m e dt h e i rc o n v e n t i o n mc 0 u n t e r p a r t sw i t hl e s sc p ut i m e ，a sw e l la sl e s sn u m b e r so ff u n c t i o n a n dg r a d i e n tc o m p u t a t i o n s 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 ；i t e r a t i o ns c h e m e ；s t e e p e s td e c e n t ；o d e ；q u a s i - n e w t o n m e t h o d ；d f p ；b f g s i i 一、学位论文独创性声明 东南大学学位论文 独创性声明及使用授权的说明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果 尽我所知，除了文中特别加以标明和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意 二、关于学位论文使用授权的说明 签 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复 印件和电子文档，可以采用影印、缩印或其他复制手段保存论文本人电子文档的内容和纸 质论文的内容相一致除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包 括刊登) 论文的全部或部分内容论文的公布( 包括刊登) 授权东南大学研究生院办理 签 第一章引言 1 1 无约束最优化方法概述 考虑如下的无约束优化问题： m i l l ，( z ) 写j 护，( 1 1 ) 其中，：舻一r 的二次连续可微函数 通常采用迭代的方法解决这个问题，而其中个重要的基本方法是线搜索方法，采用如 下的迭代格式由当前迭代点z 知获得新迭代点z 七+ 1 1 x k + l = z 七+ a p k ，( 1 2 ) 其中孤是搜索方向，q 是步长瓤通常是与目标函数f ( z ) 有关的下降方向，而步长a 则由 精确线搜索或非精确线搜索确定，从而实现每步迭代，目标函数值下降 例如，最速下降法使用搜索方向为 p k = 一勺，k 1 的迭代格式这种方法简单，存储量小，理论上具有至少为线性的收敛速度然而最速下降法 实际效果很差以二次函数为例，在病态情形，当等值线椭圆最长轴与最短轴的比值很大时， 迭代点序列会出现锯齿形，收敛非常缓慢 著名的n e w t o n 法使用搜索方向 p k = 一( v 2 a ) 一1 v ，( 1 3 ) 步长q = 1 n e w t o n 法是个在理论上具有局部二阶收敛速度的方法；如果收敛的话，收敛 得会很快可惜这个方法的实现却有很多困难例如，它般不具有全局收敛性当迭代点远 离最优点时，h e s s i a n 阵可能不正定，n e w t o n 方向不是下降方向；甚至h e s s i a n 阵奇异，使方法 失效另外计算中可能产生较大的误差，而目标函数二阶导数的计算也代价过大g o l d s t e i n ， p r i c e 1 6 ，f i a c c o ，m c c o r m i c k 1 2 ，以及f l e t c h e r 1 3 】等都针对n e w t o n 法的弱点进行了改进：以 使其在实践中有更好的效果，但仍不能尽如人意 于是拟n e w t o n 法应运而生：成为解决无约束优化问题的一类可靠而高效的方法，一直 被学术界所重视这种方法以h e s s i a n 阵( 或h e s s i a n 阵之逆) 的某种近似代替h e s s i a n 阵( 或 h e s s i a n 阵之逆) 本身，既有很好的收敛性质，又避免了二阶导数计算，大大节约了计算量，因 而在实践中获得了广泛的应用 东南大学硬士学位论文 2 拟n e w t o n 法的搜索方向为： 徘= 一h 羽| k 其中讯是目标函数h e s s i a n 逆的近似凤+ 1 通过对h k 进行秩校正或秩二校正得到，所有 的校正都要求仇+ 1 满足如下的拟n e w t o n 方程 王k + 1 鲰= 瓤，( 1 4 ) ( 其中搬= v l ( x k + 1 ) 一v f ( x k ) ，= ( z k + l 一瓢) ) 该方程在拟n e w t o n 法中起着中，5 - 的作用 自上个世纪六十年代以来，学者们提出了不同的拟n e w t o n 方法其中d f p 方法是最早 提出的拟n e w t o n 方法，( 首先由d a v i d o n 【8 ，9 】提出，然后由f l e t c h e r 和p o w e l l 1 4 】作了相关 的补充和证明) 其校正公式为： h k + 1 t t k + 蓑一碡h k y k y i h k ，0 s ) 这种方法很快就被b f g s 方法【6 ，7 ，1 5 ，1 8 ，3 2 1 ( 由b r o y d e n ，f l e t c h e r ，g o l d f a r b ，和s h a n n o 独 立地提出) 所超越，其校正公式为； 讯+ l - 仇+ ( 1 + y 丁y k v 七，婺一丝些篮 ( 1 6 ) 5 y k5 七y k 5 k y k 这些拟n e w t o n 迭代格式理论上能保证地正定，相应的搜索方向p k 是下降方向，通过线搜 索确定步长q ，就可以实现函数值的下降，使方法在较弱的条件下具有全局收敛性和局部超 线性收敛速度d f p 方法和b f g s 方法是两个最著名的拟n e w t o n 方法特别是b f g s 方法， 被认为是实践效果最好的拟n e w t o n 方法 要强调的是，所有上述方法无一例外地都应用传统迭代格式( 1 2 ) 1 2 本文的主要 i - 作及符号介绍 a r r o w ，h u w i c z 和u z a w a 于1 9 5 8 年提出o d e 方法【l 】将求解无约束最优化问题归结为 求解如下的个动力系统( o d e ) ： f 窘刊破 7 ， 【z ( o ) = m 在一定的条件下，o d e 定义了一条从初始点出发的轨线，其极限点即为相应无约束问题的 最优点o d e 方法就是通过数值积分的方法来逼近轨线从而求得最优点在上个世纪七十 东南大学硕士学位论文 3 年代很多学者都对o d e 方法进行了一定的推广例如，b r a n i n 和h o o 3 】以及b o t s a r i s 。和 j a c o b s o n 4 他们主要工作是将传统的方法移植到o d e 方法中潘平奇教授1 9 8 2 年提出了 带有方向矩阵和速率因子的o d e 方法【2 9 1 ，并给出了全局收敛性证明1 9 9 2 年又将带有方 向矩阵和速率因子的o d e 方法推广到求解等式约束的优化问题舯，3 1 】，并通过数值试验表 明这种o d e 方法具有很好的效率 传统迭代格式可看作是用e u l a r 数值积分方法求解o d e ，因而是个一阶方法本文在潘 老师文章的基础上，运用预测一校正技巧，提出了具有较高阶的新迭代格式每次迭代从当 前迭代点出发，按直线搜索得到预测点，并由这两点构造二次插值曲线，并沿二次曲线搜索 得到新的迭代点( 校正点) 通过一系列数值试验表叽新的迭代格式得到令人鼓舞的结果 本文的基本框架如下第二章简要介绍求解无约束优化问题的o d e 方法；第三章介绍 求解无约束优化问题的新迭代格式；第四章简要介绍与最速下降方向相关的新迭代格式以 及相应的数值试验；第五章简要介绍与拟n e w t o n 方向相关的新迭代格式以及数值试验 本文中除特别说明以外，将使用如下符号和记法： v ，( z )表示函数的梯度 v 2 ，( z )表示函数的h e s s i a n 阵 r “ n 维实向量空间，本文中向量均指列向量 驴x n m 扎阶实矩阵空间 r a n k ( a )矩阵a 的秩 向量的第歹个分量 e 第t 个分量为1 的单位向量 e 元素均为l 的列向量 第后次迭代后得到的向量 ， 矩阵或向量的转置 i | i l矩阵或向量的2 一范数 ， 单位矩阵 第二章求解无约束优化问题的o d e 方法 本章对求解无约束优化问题的o d e 方法作简要地介绍 2 1 基本思想 对于无约束优化问题( 1 1 ) ，o d e 方法首先定义条从初始点x o 出发的曲线，其上每一 点的切线方向都是该点目标函数的下降方向，然后沿着这条曲线求得最优点矿这条曲线称 为轨线这条轨线可以通过以下的常微分方程的初值问题加以描述 像? 仁， o d e 方法发展的初期，很多学者都考虑通过改进常微分方程右端项p ( z ) 来提高方法的 效率1 9 7 2 年b r a n i n 和h o o 提出【3 1 3 p ( x ) = 一v f ( x ) ，( 2 2 ) p ( x ) = 一( v 2 ，( z ) ) v f ( x ) ， ( 2 3 ) 1 9 7 6 年b o t s a r i s 和j a c o b s o n 还提出了f 4 l p ( x ) = 一( v 2 ，( z ) ) v ，( z ) ， ( 2 4 ) 这些早期提出的方程实际上移植了经典的无约束优化方法潘平奇教授1 9 8 2 年提出了带有 方向矩阵和速率因子的基本方程f 2 9 j v ( z ) = ( 土) 妒a ( v ，( z ) ) ， ( 2 5 ) 当目标函数的h e s s i a n 阵病态时，这种方程有良好的数值性质 b r o w n 和b a r t h o l o m e w - b i g g s 5 】在1 9 8 9 通过数值试验说明o d e 方法具有比采用相同方 向的传统方法更好的效率，同时也指出问题的关键是如何选择合适的积分公式求解。f 2 1 ) 2 2o d e 方法的基本概念和全局收敛性 本节首先介绍o d e 方法的一些基本定义： 4 东南大学硬士学位论文 5 定义2 2 1 1 e 9 1 设曲线零( t ) 定义在( o ，伪上，0 0 ，而当t = + 或v f ( x ) = 0 时，妒( t ，z ) 0 或 妒( t ，z ) = 0 0 ，则称妒为，在t r ，z q 上的速率因子 定义2 2 3 胆刃假设n n 矩阵函数a ( t ，z ) 在t r ，z qcr n 上连续且每个元素对于 茁各分量的偏导数亦连续，而当v f ( x ) 0 时恒有 【v f ( x ) l t a ( t ，z ) 【v ，( z ) 】 0 ， 则称a 为，在ter ，zeq 上的方向矩阵 下面介绍潘老师文章中考虑方向矩阵和速率因子的o d e 方法的全局收敛性 定理2 2 1 ，2 刃给定：g o r n ，假定水平集 s ( f ，x o ) = z ：z r ”，f ( x ) ，( z o ) ) ， 是有界闭集，在s 上二次连续可微，v f c x o ) 0 ，而妒，a 分别是，在t 0 ，z s 上的速率 因子和方向矩阵，则方程( 2 5 ) 确定的o d e 的右段轨线是，在x o 处的下降线且其极限点 是，( z ) 的驻点；若f ( x ) 是凸函数，则相应的右段轨线是正规下降线 这个定理说叽带有方向矩阵和速率因子的o d e 轨线的右端极限点就是无约束优化问 题的最优点本文考虑的是方向矩阵为单位阵，速率因子为1 的情形，显然满足上述定理 第三章无约束最优化的新迭代格式 3 1 迭代格式和算法 考虑这样的动力系统： 摩? 限1 ， 已知轨线上的当前迭代点z k ，预测点玩+ l 以及它们对应的常微分方程的右端项p k ，p k p 1 有 这些条件可以构造个二次插值函数， z ( t ) = 毗t 2 + b k t + c k ( 3 2 ) 逼近轨缆其中a k ，b k ，酝满足下面的方程组： a k t 2 + k 如+ = z 七，( 3 3 a ) n 七瑶+ l + 砭+ l + c 七= 硫+ 1 ， ( 3 3 c ) 2 a k 瓦+ 1 + b k = 藏+ 1 ( 3 3 d ) 令瓦+ l = 0 ，z ( o ) = 氟+ 1 ，由( 3 3 a ) 一( 3 3 d ) ，容易得到b k = 菇+ l ，c k = 玩+ 1 以及下面的关系： p k + 丁l + 一p kt k - - = - - x k - - 孰+ l ， n m = p k 丁- - p k + 1 用( z k i k + 1 ) r 左乘( 3 4 & ) ，可以得到“的近似解，更进一步可以得到( 3 3 ) 的近似解 0 一菇+ 1 ) ( x k 一瓢+ 1 ) 丁0 七+ 诹+ 1 ) 厕瓦= 瓦习矿一 b k = 藏+ 1 ，c k = 孑七+ i ， 显然无约束优化问题( 1 1 ) 可近似写成如下的一维最优化问题： r a i n ，( z ( t ) ) = f ( n k t 2 + b k t + o k ) t 之0 ， 可以运用非精确线搜索准则求解上述的优化问题 本文将后退方法中充分下降准则进行了一定的修改，得到如下的形式： f ( a k t 2 + b k t + c k ) f c c k ) + p t b t v f ( c k ) ， 6 ( 3 4 a ) ( 3 4 b ) ( 3 5 ) ( 3 6 ) ( 3 8 ) 其中p ( 0 ，1 ) 下面给出两个非精确线搜索的子算法：后退方法以及修改的后退方法后退方法开始时 令t = 如果z 七+ t p k 不可接受，则缩短t ，一直到x k + t p k 可接受为止 算法3 1 1 后退方法( b a c k t r a c k i n gi n e x a c tl i n es e a r c h ) 步0 给定，p ，口( 0 ，1 ) ；令t = 主 步1 测试f ( x k + t p k ) 如果 ，( z 七+ 饥) sf ( z k ) + 印j i v ， ( 3 9 ) 转步3 ；否娥，转步2 步2 令t 卜耐，转步j 步3 终止算法令“= t 修改的后退方法主要是针对一维最优化问题( 3 7 ) 首先，对二次插值函数的二次项系数 a k 进行预处理，使得目标函数能够下降，然后采用修改的充分下降准则( 3 8 ) 来判断步长t 是 否可接受 算法3 1 2 修改的后退方法( m o d i f i e db a c k t r a c k i n gi n e x a c tl i n es e a r c h ) 步0 给定tp ，q ( 0 ，1 ) 和c j 令t = 步1 判断下降方向 如果n ：v 一c 昭v 厶，那么令n 七= 0 步2 溪0 试f ( a k t 2 + b k t + c k ) ， 如果 ，( 口南t 2 + 6 七t + c k ) sf ( c k ) + b t v ( c k ) ，( 3 1 0 ) 转步彳j 否则，转步只 步3 令z o t ，转步2 步4 终止算法令坟= t 结合上述算法可以得到无约束最优化的新迭代格式每次迭代从当前迭代点z 七出发沿 直线搜索得到预测点瓦，- 由这两个点的相关信息通过( 3 5 ) ，( 3 6 ) 构造二次插值曲线滑曲 线搜索得到新的迭代点x k + ， 算法3 1 3 无约束最优化的新迭代格式 步0 给定：初始点x o ，p ，q ( 0 ，1 ) 和e ，令七：= o i 东南大学硬士学位论文 8 步1 如果0 v 一c b t v k ， 东南大学硕士学位论文 9 那么a h = 0 。结论成立如果 t vs c b t v f k 。 那么 ( 妣t 2 + k ) t v ast ( 去毗+ b k ) t v 0 v 证毕口 由此可以知道新的迭代格式的预测步是能够实现目标函数值的下降的，下面从新的迭 代格式整体考虑，给出全局收敛性的分析 定理3 2 3 考虑算法阻j 剀，其中p k 以及菇是下降方向满足 c o s ( 蜘积独 其中以是鲰和一v 的夹角，同时 ( 3 1 1 ) i i p k l l q 2 1 w f k l | ，( 3 1 2 ) 其中q l 0 和q 2 0 是常数假定，在r n 有下界并且在水平集 s ( ，x 0 ) = z ：z r “，( z ) ，( z o ) ， 上是连续可微的，梯度v ，在水平集s ( ，2 7 0 ) 上l i p s c h i t z 连续，即存在l 0 ，满足 l i v f ( x ) 一v f ( u ) i isl i i x 一可1 1 那么或者对于某个k ，有v f k = 0 成立，或者 1 卸0 v 0 = 0 詹- - 4 + 成立 以及 证明：考虑对所有的k ，v a 0 ，那么由算法( 3 1 3 ) 和定理( 3 2 1 ) ，可以得到 由条件( 3 1 6 ) 和( 3 1 7 ) ，得到 五+ 1sa + p t 七f f v f k ， f k + 1 五+ l + 多砀矗l 亏7 七+ ls 五十1 一五+ l 一p t 七f f v f k ， ( 3 1 3 ) ( 3 1 5 ) ( 3 1 6 ) ( 3 1 7 ) ( 3 1 8 ) 东南大学硬士学位论文 以及 由上面两个关系可以得到 将上式两边对k 求和，可以得到 + l 一 + l 0 一 + l 一七硬v 厶 七 f o a + i 一p t k p l v f k j = o ( 3 1 9 ) ( 3 2 0 ) ( 3 2 1 ) 由于，是有下界的，我们可以知道对于所有的k ，f o 一 + l 小于某个正数因此对( 3 2 1 ) 两边 求极限，可以得到 - t k f f v a a + p - 警p t v a ( 3 2 3 ) 同时由l i p s c h i t z 条件( 3 1 4 ) ，可以知道 | k 十l 一| k = f ( x k + t k p k 、一l k ：t 蕊v f k + l 屯i v f ( 嚣k 午s p 心一v f f p k d 3 t 礤v + 厂“s l l l p k i l 2 d s ( 3 2 4 ) = - 西v 刖( 丢) 己枷川2 纳礤v ，肋0 f l t 皆 由( 3 2 3 ) 和( 3 2 4 ) ，可以得到 t 七、2 ( p 一1 ) p t v a a 7 l l l p k l l 2 如果初始步长吾满足( 3 9 ) ，那么如= 因此， 蛇m i n 警垦 。 同时由( 3 2 2 ) 可以得到， e妻min竽铲，一醒v小j= o ”n ” ( 3 2 5 ) ( 3 2 6 ) ( 3 2 7 ) 1 0 东南大学硕士学位论文 由条件( 3 1 1 ) 和( 3 1 2 ) 可以知道， 薹酬掣刑v 砒v f k 1 1 2 m o o ( 3 2 8 ) 进步可以知道， i l v f k1 1 2 + 0 0 ( 3 2 9 ) 从而 1 i m0 v 0 = 0 ( 3 3 0 ) - * - - - o o 证毕口 这个定理说明新的迭代格式具有整体的收敛性，从理论上保证算法是有效的在下面的 章节中，我们将测试这个算法在处理实际问题的效率 第四章与最速下降方向相关的新迭代格式 4 1 算法 对于许多问题最速下降方法并不是个有效的算法，尤其当目标函数的等值线是个扁 长的椭圆时，最速下降方法尽管在开始几步有较快的下降速度，但是目标函数值接近最优值 时，最速下降法将出现锯齿现象，迭代很缓慢结合新的迭代格式的最速下降方法沿着曲线 搜索就有可能避免在最优值附近锯齿现象的发生 在算法( 3 1 3 ) 中采用最速下降方向就可以得到与最速下降方向相关的新迭代格式： 算法4 1 1 与最速下降方向相关的新迭代格式 步0 给定：初始点z o ，p ，o t ( 0 ，i ) 和，令七：= o j 步1 如果0 v | i e ，停止； 步2 计算预测点 运行算法只j j 得到k 令礅+ 1 = z 七一t k v a ， 步3 校正预测点得到新的迭代点 如果l l v f k + 1 l l ，其中v ，+ l = v f ( x k + 1 ) ，停止j 计算 硫：亟d 糯暑器掣， ( 4 - ) b k = - - v f k + l ，该= 玩+ i ， ( 4 2 ) 运行算法3 1 2 得到瓦十1 ，令z 七+ l = 矾瑶+ l + 瓦瓦+ l - i - 蕻 步4 令奄：= 奄4 - 1 ，转步f 由定理( 3 2 3 ) ，很容易得到结合新的迭代格式的最速下降方法的全局收敛性定理： 定理4 1 i 考虑算法心j u ，假定，在r n 有下界并且在水平集， 8 ( f ，2 7 0 ) = z ：z r n ，f ( x ) ，( z o ) ) ，( 4 3 ) 上是连续可微的梯度v ，在水平笑s ( i t o j 上l i p s c h i t z 连续，满足条件p ，j 彳，那么或者对 于某个是，有v = 0 成立，或者 。l i r a i l v k f l = 0 ( 4 4 ) 成立 东南大学硕士学位论文 4 2 数值试验 这一节的数值试验显示与最速下降方向相关的新迭代格式比传统的最速下降方法有一 定的优势数值实验的2 0 个问题来自于文章【2 6 1 这一节测试了如下两个算法： s t e e p ：最速下降算法 , m s t e e p ：与最速下降方向相关的新迭代格式 同时为了比较的方便，两种算法在实现过程中采用相同的参数：p = 1 0 一，o t = 0 5 ，e = l o ，c = l o e1 1 = 1 0 0 0 0 以及害= 1 所有问题都是在处理器为g e n u i n ei n t e l ( r ) c e n t r i n o - d u o t 2 3 0 01 6 6 g h z ，1 0 0 g b 内存和1 6 位精度的p c 上由m a t l a b7 0 4 执行 表4 1 给出了最速下降法和最速下降方向相关的新迭代格式的数值结果，其中，标记 的列给出的是每个问题函数值的计算次魏，v ，标记的是梯度向量的计算次数，t i m e 标记 的是计算所花费的时间一表示算法没有在规定的迭代次数内得到正确结果 从表4 1 可以看出2 0 个问题的总的函数值计算次数，新的迭代格式比传统迭代格式少 了1 6 1 0 0 5 次，梯度的总计算次数少了1 2 7 7 6 次2 0 个问题中1 2 个问题是新迭代格式有明显 的优势，尤其是对于等值线为扁长椭球型的，例如r o s e n b r o c k 函数，f r e u d e n s t e ia n dr o t h 函 数等同时我们还可以发现尽管与最速下降方向相关的新迭代格式比最速下降法有很大的 改进，但仍然无法摆脱最速下降方向产生的负面影响，例如p o w e l ls i n g u l a rg u l f 函数，r e s e a r c h a n dd e v e l o p 函数的计算量以及计算时间仍然非常可观 1 3 东南大学硕士学位论文 1 4 p r o b l e m s t e e pm s t e e p t i m e l飞| t i m e l飞| r o s e n b r o c ko 9 l1 8 2 6 91 8 3 50 5 87 7 2 78 2 8 p r e u d e n s t e i na n dr o t h1 8 34 2 4 3 63 4 3 9o 5 27 2 7 8 7 0 8 p o w e ub a d l ys c a l e d b r o w nb a d l ys c a l e do 0 54 64o 0 24 44 b 的l eo 4 14 5 8 87 0 70 2 52 1 1 3 3 5 7 j e n m i c ha n ds a m p s o n o 5 61 1 0 5 75 8 8 0 5 5 7 3 4 54 0 2 h e l i c a lv a l l y2 3 l2 8 3 5 32 7 5 50 4 74 3 7 24 4 3 b a r do 0 51 5 72 50 0 21 7 52 9 g u a s s i a no 0 5 1 9 3 5 2o 0 52 4 7 7 l m e y e r g u j fr 筠e a l c ha n dd e v e l o p2 5 7 71 9 3 3 4 02 0 0 0 02 5 7 01 7 0 7 1 61 6 3 7 7 b o xt h r e e - d i m e n s i o n a l l - 9 l1 0 6 1 12 9 7 42 1 l8 9 4 4舢 p o w e us i n g u l a r1 7 0 11 7 1 5 8 32 0 0 0 02 0 2 21 6 0 1 1 02 0 l 、) 、，o o d7 9 98 8 2 6 68 2 3 73 8 13 2 8 2 03 2 1 3 k o w a l i ka n do s b o r n e4 7 02 6 0 3 57 1 7 27 7 73 5 6 0 31 0 2 5 7 b r o w l la n dd e n n i s1 1 l1 3 0 1 36 8 4 2 1 7 2 1 1 2 61 0 9 8 b i g g se x p 6 3 2 51 0 5 6 62 3 0 63 3 l8 8 4 42 2 弭么t s o n e x t e n d e dr o e e n b r o c k2 9 51 8 4 5 31 8 5 51 的8 4 7 88 9 6 b r o y d e nb a n d e d o 1 33 8 3 4 80 1 34 0 25 3 t o t 札 7 0 9 7 6 3 7 3 4 97 2 6 8 l 6 9 25 i 4 7 6 3 4 4 5 9 9 0 5 第五章与拟n e w t o n 方向相关的新迭代格式 5 1 算法及全局收敛性 这一节我们考虑将拟n e w t o n 方向结合到新迭代格式中，每次迭代由当前迭代点z 七出 发，沿拟n e w t o n 方向孤= 一风v a ，搜索得到预测点魂+ 1 ，由这两点的相关信息可以构造二 次曲线 沿着曲线搜索得到新的迭代点z 七+ 1 ，并通过瓢和x k + l 更新风 算法5 1 1 与b f g s 相关的新迭代格式 步0 给定：初始点z o ；令七：= 0 ，办o t ( 0 ，1 ) ，n ，t t o = ，e ，e ； 步1 计算预测点 运行算法爱j f 得到“，令孰+ 1 = z 七一t k h k v k 2 如果i i v f l 。+ 1 8 e ，其中v f k + l = v ，( 玩+ 1 ) ，停止 3 计算新的迭代点 更新玩：如果订瓢e ，那么令氟+ l = i ，否则， 鼠旷凰+ ( 1 + 靠kh k y k ) 檠一篮乌尝篮， 其中孔= v f k + l v a ，瓦= 一“日七v a 计算 硫= 虻萼箍鲁掣， b k = 藏+ l ，磁= 砚+ l ， 其中p k = 一y 七v k ，藏+ l = 一鼠+ 1 开m 运行算法，j 2 得到最+ l ，令z 七+ l = 讯磋+ l + b k t k + l + 砭 4 如果0 v + 1 0 ，停止 5 更新风+ 1 如果k + 1 ( m o d n ) = 0 或者昴s 七e 那么矗七+ l = j i 否则 风+ l ：h k + ( 1 + y t r h k y k 8k y k 、s k s 钆靠h k - i - h k y k s t k ，下个 s 玑 s 七弧 其中y k = v + 1 一v a ，8 k = z _ i ：+ 1 一z 女 如果( 斋凳岛籀翻) e 或者坚删 e 满足时，仉+ 1 是正定的 ( 3 ) 本文只列出了与b f g s 相关的新迭代格式，其实与d f p 相关的新迭代格式可以很 容易得到，只要在步3 和步5 采用d f p 的更新公式 定理( 3 2 3 ) 给出了无约束最优化的新迭代格式的全局收敛性，由此同样可以得到新迭 代格式的b f g s 方法的全局收敛性定理 定理5 1 1 考虑算法弘j j ，假定，在r n 有下界并且在水平集 s ( f ，跏) = z ：z r n ，( z ) s ，( z o ) ) ，( 5 5 ) 上是：- - ；k 连续可微的，梯度v ，在水平集8 ( 1 ，x o ) 上l i p s c m t z 连续那么或者对于某个k ，有 v = 0 成立，或者 1 i m i i v i l = 0 ，( 5 6 ) 尤呻+ o o 成立 证明：考虑对所有的k ，v 0 ，那么由算法( 5 1 1 ) 的步3 ，可以得到鼠+ 1 是正定的，从 而 + ls 五十l 一破鼠+ l 订七十1 ) 丁面詹+ 1s 五+ 1 ( 5 7 ) 由算法( 5 1 1 ) 步1 ，可以知道 五+ l 一p t ( h k v a ) 丁v ， ( 5 8 ) 从而由( 5 7 ) 和( 5 8 ) 可以得到 由算法( 5 1 1 ) 步5 ，可以得到： 以及 一，七十l p t ( h k w f k ) t v ( 5 9 ) 弋j j “i l k 、l k “ v + 】洲h k + 】v a + 1 1 i 褊掣弘l l v + l i i 一一 ( 5 1 0 ) ( 5 1 1 ) 1 6 东南大学硬士学位论文 1 7 那么由定理( 3 2 3 ) ， 成立证毕0 。l i r al i v a = 0 ， 七_ 4 - 0 0 一” ( 5 1 2 ) 东南大学硕士学位论文 5 2数值试验 这一节给出数值试验的结果显示结合新迭代格式的d f p 方法和b f g s 方法，比传 统的d f p 方法和b f g s 方法有优势数值试验的问题包括两部分：第一部分2 0 个问题来 自于文章【2 6 l ，第二部分5 0 个可扩展的问题从文章【2 】2 得到，这些问题的程序同样可以从 j i 却：，：t 明唧i c i r o l m o e x u t a v a n s o # h t m 得到 5 2 1 测试算法这部分测试了如下四个算法： , d f p ：d f p 算法 , b f g s ：b f g s 算法 , m d f p ：与d f p 相关的新迭代格式 , m b f g s ：与b f g s 相关的新迭代格式 为了比较的方便，四种算法在实现过程中采用相同的参数：p = 1 0 一，a = 0 5 ，n = 1 5 ， b o = i ，e 寻1 0 6 ，n = 5 0 0 0 ，s = 1 0 1 2 以及= 1 ； 所有问题都是在处理器为g e n u i n eh t e l ( r ) c e n t r i n o - d u ot 2 3 0 01 6 6 g h z ，1 0 0 g b 内存和 1 6 位精度的p c 上由m a t l a b7 0 4 执行 5 2 22 0 个问题的结果表5 1 和表5 2 给出了与d f p 和b f g s 相关的新迭代格式以 及传统的d f p 方法和b f g s 方法的2 0 个小规模问题的数值结果，标记的列给出的是每 个问题函数值的计算次数，v ，标记的是梯度向量的计算次数，t i m e 标记的是计算所花费 的时间，单位为秒，- 表示算法没有在规定的迭代次数内得到正确结果 表5 1 给出了d f p 方法和与与d f p 相关的新迭代格式的数值结果比较尤其在解决 b o xt h r e e - d i m e n s i o n a l 函数、b r o w na n dd e n n i s 函数、以及w a t s o n 函数有很明显的优势在 函数值和梯度的总计算次数，以及总的计算时间上，与d f p 相关的新迭代格式比传统d f p 方法分别减少了6 2 3 7 ，6 1 9 3 以及5 9 8 3 表5 2 显示新迭代格式的b f g s 方法在解决 p o w e ub a d l ys c a l e d 函数、b a r d 函数以及b r o w na n dd e n n i s 函数有很好的效果尽管在总的 迭代时间上比b f g s 略微多了o 0 6 秒但是在总的函数值以及梯度的计算次数上却比传统 b f g s 方法分别减少了5 9 2 次和2 4 6 次这是因为新的迭代格式增加了二次插值函数二次项 系数口七的计算量，对于小规模的问题，a k 计算量的影响还是不可以忽略的 5 2 35 0 个问题的结果表5 3 和表5 4 显示是第二部分5 0 个问题的数值结果，这5 0 个m 题包括4 2 个1 0 0 维的l 、口j 题，4 个2 0 0 维的问题以及4 个3 0 0 维的问题表中嶂：标记的是 3 0 0 维的问题，律私标记的是2 0 0 维的问题结果显示对于规模中等的问题，新迭代格式的方 法也有优势由表5 3 可以看出与d f p 相关的新迭代格式处理中等规模的问题有很好的效 1 8 东南大学硬士学位论文 果，尤其是解决d i a g o n a l l 函数、d i a g o n a l 3 函数以及b d q r t i c 函数在函数值和梯度的总计 算次数上与d f p 相关的新迭代格式比传统d f p 方法分别减少了1 4 5 5 7 次和4 3 5 1 次表5 4 表明与b f g s 相关的新迭代格式处理p e r t u r b e dq u a d r a t i c 函数、d i a g o n a l l 函数、d i a g o n a l 3 函数、g e n e r a l i z e dp s c l 函数以及b d q r t i c 函数等等，有很好的效果在函数值和梯度的总 计算次数，以及总的计算时间上，与b f g s 相关的新迭代格式比传统b f g s 方法分别减少了 5 2 6 5 ，5 2 0 8 以及3 6 6 1 表5 5 和表5 6 中的5 0 个问题是将上述的4 2 个1 0 0 维的问题和4 个2 0 0 维的问题扩展 到5 0 0 维，对于这样的大规模的问题新的迭代格式相对于传统的迭代格式也有很好的数值结 果在总的c p u 计算时间上，与d f p 相关的新迭代格式比传统d f p 方法减少了1 0 6 2 4 4 秒， 与b f g s 相关的新迭代格式比传统b f g s 方法少了5 4 9 1 0 秒 从表5 3 - 表5 6 可以发现尽管新的迭代格式，增加了a k 的计算量，但是却减少了函数值 和梯度的计算次数对于大规模问题，a k 的计算量相对于函数值的计算量还是很小的 5 2 4 总的比较结果表5 7 给出了新迭代格式的方法和传统方法的比较结果t i m e 代 表的是传统方法和新迭代格式总的运行时间的比值，代表的是传统方法和新迭代格式的 函数值总的计算次数的比值，v ，是传统方法和新迭代格式梯度总的计算次数的比值结果 显示：三组问题的总的平均运算时间，d f p 方法是d f p 相关的新迭代格式的1 5 8 倍b f g s 方法是b f g s 相关的新迭代格式的1 2 3 倍 1 9 表5 1s t a t i s t i c so ff i r s t2 0f u n c t i o n so l id f pa n dm d f p p r o b l e m d f p v d f p t i m e | 飞l t i m e l飞l r o s e n b r o c k0 0 51 0 15 30 1 笳 f r e u d e n s t e i na n dr o t ho 0 32 21 3o 9 02 0 p o w e l lb a d l ys c a l e d - b r o w nb a d l ys c a l e do 0 2 2 0 1 4o 0 28 32 4 b e a l e0