（运筹学与控制论专业论文）二次三对角插值模型的直接搜索方法.pdf

南京航空航犬人学硕士学位论文 摘要 直接搜索方法在六七十年代曾成为国内外学者研究的热点t 在九十年代， 由于工程上的迫切需求，浚方法又一次成为人们研究的热点 本文主要研究了直接搜索方法的算法和理论特别研究了二次三对角插植 模型算法，得到了丰富的理论和数值结果本文共有两章，其内容如下： 第一章介绍了直接搜索方法的发展概况对单纯形法、模式搜索法、线性 搜索法、二次插植模型法这四类主要的直接搜索方法的主要思想、算法的起源、 发展状况及其特点分别作了介绍第二章给出了解无约束最优化问题的二次三 对角插值模型算法，对二次三对角插值模型算法与一般二次插值模型算法的数 值结果进行了比较，并对二次三对角插值模型算法的收敛性进行了简单的分析， 证明了算法的整体收敛性在第二章的最后，我们对直接搜索方法作了总结， 并提出了直接搜索方法中值得进一步研究的一些问题 关键词：直接搜索方法，单纯形法，模式搜索法线性搜索法，二次插值模型 法，二次三对角插值模型法，无约束最优化 - 二次三对角插值模型的直接搜索方法 a b s t r a c t d i r e c ts e a r c hm e t h o d s e n j o y e dg r e a t i n t e r e s t a m o n g s t b o t hd o m e s t i ca n d o v e r s e a sr e s e a r c h e r sb e t w e e nt 9 6 0 sa n d1 9 7 0 s ，b e c a u s ei th a sh i g hd e m a n df r o m p r a c t i t i o n e r s n o w ，i ti sa l s oh i g hd e m a n d t h a tm a k e st h er e s e a r c ho nt h ed i r e c ts e a r c h m e t h o dr e v i v e i nt h et h e s i sw em a i n l yd i s c u s st h e a l g o r i t h m sa n dt h e o r yo fd i r e c t s e a r c h m e t h o d s ，e s p e c i a l l yo ft h eq u a d r a t i ct r i d i a g o n a li n t e r p o l a t i o nm o d e lm e t h o d t h e s t r u c t u r eo f t h i sp a p e ri so r g a n i z e da sf o l l o w s i nt h ef i r s tp a p e r ，w e s u r v e yt h eh i s t o r yo f d i r e c ts e a r c hm e t h o d a n dd i s c u s sf o u r d i r e c tm e t h o d sr e s p e c t i v e l ytw h i c ha r es i m p l e xm e t h o d ，p a t t e r ns e a r c hm e t h o d 1 i n e s e a r c hm e t h o da n d q u a d r a t i ci n t e r p o l a t i o n m o d e l m e t h o d t h e y a r e c u r r e n t l y c o n s i d e r e dt ob ee f f e c t i v em e t h o d sf o ru 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 i ne a c h s e c t i o n ，w ed i s c u s st h em a i ni d e a ，t h ed e v e l o p m e n t ，r e c e n t p r o g r e s sa n dp r o p e r t i e so f t h e s em e t h o d s i nt h es e c o n dc h a p t e r ，w ed e v e l o pa nq u a d r a t i ct r i d i a g o n a li n t e r p o l a t i o nm o d e l a l g o r i t h m f o ru n c o n s t r a i n e d o p t i m i z a t i o n ，e x p l o r e i t s c o n v e r g e n tp r o p e r t y a n d c o m p a r ei t sn u m e r i c a lr e s u l tw i t ht h er e s u l to fg e n e r a lq u a d r a t i ci n t e r p o l a t i o nm o d e l a l g o r i t h m a nt h el a s to f t h es e c o n d c h a p t e r - w e s u m m a r i z et h ec o n t e n t so f t h ea b o v et h e s e c h a p t e r sa n dp r o p o s es o m ep r o b l e m si nd i r e c ts e a r c hm e t h o d st h a ta r ew o r t h w h i l et o f u r 【h e rr e s e a r c h k e y w o r d s ：d i r e c ts e a r c hm e t h o d ，s i m p l e xm e t h o d tp a t t e ms e a r c hm e t h o d ，l i n e s e a r c h m e t h o d ，q u a d r a t i ci n t e r p o l a t i o n m o d e lm e t h o d ，q u a d r a t i c t r i d i a g o n a l i n t e r p o l a t i o nm o d e lm e t h o d u n c o n s t r a i n e do p t i m i z a t i o n 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立 进行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容 外，本学位论文的研究成果不包含任何他人享有著作权的内容。对本 论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明 确方式标明。 本人授权南京航空航天大学可以有权保留送交论文的复印件，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或其他复制手段保存论文。 作者签名：遣叠座 日 期：丝q ! ：翻 南京航空航天人学硕士学位论文 绪论 直接搜索方法是只使用目标函数值，而不用目标函数导数值的一 种最优化方法陔方法最早可以追溯到2 0 世纪5 0 年代，它在工程上 有着广泛的应用工程中形成的许多最优化问题其函数值都是通过实 验测量或者是通过模拟软件包获得的，因此该类最优化问题具有如下 两个特点：一是计算函数值的工作量很大：二是函数的梯度不能直接 求出 在六七十年代，直接搜索方法曾成为国内外研究的热点，并发展 了很多算法，像n e l d e r 和m e a d 的单纯形法、p o w e l l 的共轭方向法等但 是这些早期的算法存在的一个普遍问题就是缺乏理论上的证明，并且 在实际操作过程中数值结果也不十分理想，从而使得当时的学者都普 遍误认为用直接搜索方法来解决实际问题是不可行的，因而导致在8 0 年代对这类方法研究的很少但是到了9 0 年代，由于工程上的迫切需 要，浚方法又一次成为人们研究的热点通过对原有算法进行改进、 创新，不少算法已经得到了理论上的证明，像模式搜索法、线性搜索 法、二次插值模型法都已经被证明是收敛的，并且这些算法在实际应 用中也取得了不少成功的事例例如c o l i n 、g o u l d 和t o i n t 等人用他 们发展起来的二次插值模型算法解决了直升飞机水平旋翼叶片的设计 问题、发动机喷油嘴的设计问题等，这些成功的事例都表明了用直接 搜索方法解决实际问题是可行的 尽管直接搜索方法己取得了一些令人可喜的成果，但是无论从理 论上还是从应用上讲，直接搜索方法还远远没有发展成熟其理论还 有待于进一步的完善，其应用领域还有待于进一步的开拓，直接搜索 方法仍然是一个非常值得研究的方向 本文中，我们将用一章的内容概述至今为止被认为是比较有效的 四种直接搜索方法，即单纯形法、模式搜索法、线性搜索法、二次插 值模型法每种方法的主要思想、起源、发展及算法的优缺点都作了 较为系统地阐述由于二次插值模型方法是第二章中提出新算法的基 j 二次二对角插值模型的直接搜索方法 础，所以对浚方法作了详尽的讨论在第二章中，提出了一种新的插 值模型法一一二次三对角插值模型法对该算法的建立、算法的描述、 收敛性分析及其数值结果都给出了详尽的讨论通过与一般二次插值 模型算法进行比较，我们得出结论：随着问题维数的增大，二次三对 角插值模型算法在存储方面、函数值计算次数方面、迭代次数方面和 运行时i b j 方面都具有明显的优越性在第二章的最后，我们对前两章 的内容作了总结，并提出了直接搜索方法中值得继续研究的一些问题 南京航空航大大学硕十学位论文 第一章直接搜索方法 直接搜索方法研究至今，已经发展起来了很多算法但是从本质 上来说大致可以归纳为如下六类：1 、单纯形法：2 、模式搜索法；3 、 线性搜索法；4 、二次插值模型法：5 、启发式算法；6 、有限差分洼前 四种方法都是属于不直接计算函数梯度的近似值而涮接利用导数信息 的方法，因此被t o i n t 等人在文献【3 2 】中称为d f o ( d e r i v a t i v e f r e e o p t i m i z a t i o n ) 算法 由于约束最优化问题可以通过罚函数法转化为无约束最优化问 题，因此现在发展起来的大多数直接搜索方法都是用来解无约束最优 化问题的，所以在本章中我们主要介绍的是无约束最优化问题的d f o 算法，这罩无约束最优化问题为 r a i n 。厂( x ) 其中厂：r ”呻r 是光滑非线性函数，对于v x ，v 厂( x ) 的值都无法计算出 来 1 1 单纯形法 单纯形法最初是由s p e n d l e y 、h e x t 和h i m s w o r t h 提出来的，为了 提高算法的有效性，n e l d e r 和m e a d 在继c a m p e y 和n i c k o l s 之后也对 该算法进行了改进，这个算法在提出之后的3 0 年罩，一直是工程界使 用最广泛的直接搜索方法 算法1 1 ：n e l d e r 和m e a d 算法 步0 ：初始化在r ”空矧中选择”+ 1 个点k ，匕，使得这”+ 1 个点构成 一个单纯形给定常数s 0 ，反射系数口 0 ，扩张系数y 1 ，收 缩系数( o 1 ) 二次三对角插值模型的直接搜索方法 步1 一“m 。a x ，八一) f x m = a r g r e , i n f ( x , ) t “寺l 擎“n j 步2 ：如果圭( ，( ：卜，1 - 2 ) ) 二 f ( x ，) ，f - 0 ，1 ，月但i ；h 反射运算 失败，进行收缩运算，转步5 ；否则，用x 。l 代替 转步1 步4 ：扩张运算令x 。2 = i + y ( x 。一f ) ，如果f ( x 。：) 厂( ，。) ，用x 。二代 替x 否则，用x 。i 代替x 转步1 步5 ：收缩运算如果f ( x 。) 0 步l ：阢户a r g 璁一。l 擎m j 步2 ：如果r 一, 1 a xl l x ，一r s ，则停止迭代且输出x = x ， 步3 ：反射步：令r ，。x 。+ ( x 。+ x ，) ，i = f ) f n 如果e r a 。i n ，( i ，) 1 ， p 0 口r 一，玎，j cz ，并且万o 0 ，q o f - 1 , 2 p ，令口= r 4 ， 毛a = “一r 一。 ，t ：0 步1 ：如果 p ，停止迭代，并输出x 。 步2 ：计算搜索步长s 。，如果m i n 厂( h + y ) | y b f k 0 ，给定常数0 ，7 l 1 ，0 h 一 2 ”1 的任意正数 这罩r 的值一般很大，除非对于较小的 和d 。因此它只有理论上 的意义在实际操作中，我们把判断插值点集的适定性问题同n e w t o n 基本多项式联系起来，在建立这些多项式的时候，c n p 程序需要单位 化这些多项式，即执行除数为i ：l ”j ( y ”) i 的除法运算从理论观点来看， 这一项是非零数即可但是在实际中我们必须保证对某个参数0 0 ， 使得 j 酬一) i 目 ( 1 4 8 ) 二次二对角插值模型的直接搜索方法 成立，i s _ 罩，l 州”1 ( y _ ) 的值称为主元to n n 主元阈值，只要条件( 1 4 8 ) 满足，我们就称插值点集是强适定( w e l lp o i s e d ) 的 根据定义1 2 ，可以给出修币y 的具体办法，f 面分两种情况讨论： 1 p 。，7 的情况 如果l y j l + 目t 则令y 一= ，儿= a r g 嬲l ( x ) l ：否 v e 凡l 7 l 。 t e 心l 。 则y 就是几何充分的 t o i n t 等人在文献 3 1 中证明了利用此方法进行修f 插值点集y 经 过有限步就可以使得y 在b + 中是几何充分的并且还证明了利用此方 法进行修f 插值点集y 的二次插值模型算法具有全局收敛性 一塑塞塾皇堕垄叁鲎堡主堂垡堕苎 第二章二次三对角插值模型的直接搜索方法 2 1 基本思想 在解一般情况的无约束最优化的二次插值模型的直接搜索方法 中，一般选择 1 ，。 纠。，b ，i 。， ( 2 1 1 ) 作为仞始多项式基，通过算法1 6 的c n p 程序得到n e w t o n 多项式基在 建立了n e w t o n 多项式基之后。插值多项式m k ( x ) 就可以表示为 d 1 f m k ( 工) = 一( ) x l ”】( x ) ， ( 2 1 2 ) n = 0i = l 这罩系数0 ( 一”】) 是由如下公式定义的广义有限微分 2 0 ( x ) ：厂( x ) ， 力+ i ( ，) ：。( x ) 一胪, e ”i 以( y 州，1 ( x ) ，p ：。，d 一1 = 厂( x ) ， 力+ i ( x ) = 0 ( x ) 一九( y ”】l 彬川( x ) ，= o 一，一 在不考虑目标函数h e s s i a n 阵的结构的一般二次插值模型算法中， 每一次迭代至多产生一个新的迭代点 一个模型i f - 少需 q 一1 = ( h ：十3 n ) 2 个自h 面迭代点的信息，在迭代过程中，每一个新模型 函数需o ( q ：) 次运算才得到然而，对于n 很大的时候，这个计算量是 很大的- 因此，一般二次插值模型算法不适合解大规模无约束最优化 问题 t o i n t 和c o l s o n 在文献 3 4 1 中给出了解稀疏h e s s i a n 阵的无约束 最优化的二次插值模型的直接搜索方法若h e s s i a n 阵v 毳，( x ) 是稀疏 矩阵，则存在着对称的下标集合 s = 川ls f ， ( 印v 二厂( x ) p ，) ：0 帆r 味( 2 1 3 ) 次二对角插值模删的直接搜：粜方法 他们利用h e s s i a n 阵的简化结构来减小满足( 2 1 3 ) 的二次多项式集合 的近似空问，即在( 2 11 ) 中排除满足( i ，) s 的多项式x t x ，即可这 个算法在减少函数值计算次数、减少c p u 运行时间、减少迭代次数方 面具有很好的优越性，但是需要明确知道h e s s i a n 阵的稀疏情况，因此 这个算法并不适合解一般无约束最优化问题 在本文中，我们考虑“人工稀疏”的思想，即假定二次插值模型 的某些二次项系数为零一种简单的想法是在二次插值模型多项式中， 限定二次项系数矩阵为三对角对称矩阵这种限定的主要依据一是许 多工程应用中产生的优化问题的h e s s i a n 阵类似于三对角对称结构二 是三对角阵只使用h e s s i a n 阵的主要部分，而忽略非主要部分p o w e l l 在文献【3 5 】中提出了限制二次项系数矩阵是对角矩阵的思想，但是这种 限制由于忽略了太多信息而使得数值结果并不理想 在建立目标函数的二次插值模型的时候，利用3 ”个单项式 l ，。， x 强。扛，x 以。i ( 2 1 5 ) 作为初始基向量，利用算法1 6 建立n e w t o n 基本多项式，继而根据 ( 2 1 2 ) 式建立插值多项式二次项系数矩阵结构确定后我们需要 解一个如下形式的信赖域子问题： ( 【)m i nm ( x + 5 ) = f ( x t ) + g ：s + s 。日 s z s t i 1 , 2 1 is 。 其中凰是三对角对称矩阵在解这个信赖域子问题时，需要确定五0 满足 ( + m ) s = 一g ， ( 21 4 ) 并保证。+ 五，是正半定圩。是三对角对称矩阵将使得子问题( i ) 的求 解更容易 这种限制得到的模型，出于含有部分二次项，既比线性模型有优 势叉比一般二次插值模型需要较少的插值点 南京航空航天人学硕士学位论文 下面我们给出二次三对角插值模型的无约束直接搜索算法 2 2 算法 算法2 1二次三对角插值模型的直接搜索算法 步0 ：初始化： 给定初始插值点集y 及初始的信赖域半径。，终止误差g ，0 ，常 数0 r n 蔓r i 1 ，0 y ( isy l 1 t 0 s 。 1 给定初始向 量“，使得= a r g m i( j ，) ，令= 步l ：如果信赖域半径。, n s 。，则转步3 ； 如果恬。1 1 - s 。，且y 在集合a 。= 每r ”l l l x - x 。i t - “t l g 。i ) 中是几何充分 的，则停止迭代并输出最优值k ；否则，如果恬。忙s 。，且r 在a 。 中是几何不充分的，则修正插值点集y ，直到y 在 g ( 瓯) = 扛tr ”l 忙一以0 瓯 ( 其中坑( o ，恬。小中是几何充分的， 转步3 步3 ：最小化二次插值模型： 计算。+ “，使得删t ( h + s k ) = m 。忧i n m * ( 工) ：计算厂( _ + ，* ) ，及比值 n ：兰婴塑等掣 门7 0 ( 工j 一丹7 ( t + s ) 步4 ：修正插值点集： ( 22 2 ) 次二对角插值模璎的直接搜索方法 如果p 。叩lt 把x 。+ s 。增加到y 中去，在l y l 3 n + l 时去掉y 中的某 一点；如果p 。 0 ，使得对v x r “， 有 i 彤( 刮i r 。，护厂( x ) 忙盯。； a 2 ：目标函数在上有下界； a 3 ：二次插值模型函数的二次项系数矩阵( 为三对角对称矩阵) 均一 致有界，即存在常数r 。， 0 ，使得对所有的x b 。= 扛忪一k 忙a k ， 均有 惮。忙r 。 为了以下论述的方便，我们令r 。= m a x x 。k t h r 。，】 对于二次三对角插值模型的直接搜索方法，我们以文献 31 1 中的类 _ 二次二对角插值模删的直接搜索方法 似定理为基础得剑f 向的引理 引理2 1 假设a 1 和a 3 成立，对于模型( 2 2 1 ) ，以及在眈中几 何充分的插值点集r ，存在与k 无关的常数_ ， o k 0 ，对于b 。中所 有的x ，均有 i 厂( z ) 一m ( x ) i r 。m a x a ：i ， ( 2 31 ) 1 w ( x ) - g 。l r 。m a x a 。，：】， ( 23 2 ) 证明 由假设a l 和t + 的定义t 我们有! i s i i e k s , 因为，在b 。中是 几何充分的，从而有 忱一_ 忙a 。 ( 扛1 ，q ) ，q = 3 n 和 j | y y “2 a 。 ( f = l ，2 ，一q f ) 成立由r 的几何充分性知，( 14 6 ) 和( 14 7 ) 成立 ( 即次数为l 和2 ) ，由定理1 3 可得，当d = 1 时，有 | 厂( x ) 一朋。( 工) l 门3 盯。r ? ：， 当d = 2 时，有 对于d = 1 和d = 2 ( 2 3 3 ) | 厂( 上) 一酢( x ) i s 月5 一，一3 ： ( 23 4 ) 针 根据( 2 33 ) 和( 23 4 ) 式，以及r 是大于2 l 。的币数，有 陟( x ) - - t 。( x ) i 2 n ! 0m a x a ：。m 记t ，= 2 n j k - h k ，( 2 31 ) 式成立 由假设a 1 和a 3 知，厂( x ) 和月? 。( 工) 都是二次连续可微的泰勒定理 表明，当1 i h l l s 。时，有 f ( x 。+ ) = f ( x ) + 7v ，( x 。) + 7 v ：厂( 品) ， m ( x + 矗) = ( x ) + 7 9 + 矗7 h h 这咀。是三对角对称矩阵，六“札。+ 所以 一 亘至堕至堕盔查堂堡主堂垡丝苎 7 ( v f ( x ) 一g 。) = f ( x + h ) - m 。( x 。+ ) 一 7 【v 二厂( 氕) 一何。】 ， 利用( 2 3 1 ) 式，假设a 1 、a 3 ，s 和c a u c h y s c h w a r z 不等式 有 取 则有 厅( v ，( _ ) 一鼠) t ，m a , x f a ；，： + i 。v ! 厂( 氧) 卉| + 圭p h , h f r “m m x a ：，： + f ：， t ，蒜尚 l i v f ( x ) 一g 女1 1 盯m m x a 女：】+ 盯h j 墨( 芷。，+ h ) m a x a + ，：】， 令k 。= 盯“+ r ( 2 3 2 ) 式成立证毕 引理2 2 设矗由算法2 1 产生，如果l i g 。忙s 。，且y 在a 。中是几何 不充分的，则当v f ( x 。) 0 时，经过有限步的修j 下可以使得y 在g ( 瓯) 中 是几何充分的 证明选择常数v ( o ，1 ) ，令或= 函，修正插值点集y ，使得j ，在 。 ( v 5 。) 中是几何充分的( 根据y 几何充分的定义，这个过程可以有限 终止) ，此时可得到一个新的二次插值模型，设其梯度为g 。”，如果 卢0 或“i i - ”，则终止此过程并令瓯= k e g 否则l 陂1 | ”，修f 插值点 集y ，使其在q 。( v 。) 几何充分，下一步或者停止或者p + 的半径再乘以 只有对所有的i o 均有掣恬圳 v 。时，这个步骤才能够无限进行。对 每一个，0 ，因为y 在g ( v 。) 中充分，并且、o 气 0 ，对所有的女，都有 。 符、 ( 2 36 ) 南京航空航天人学硕士学位论文 证明我们假定k o 是第一个满足 一叫- 赢x o , r ( t 习- 1 7 i ) ， 的f 整数，所以有a “+ l ( a ，出算法2 1 步5 知，有7 0 a “蔓+ 1 成立， 因此有 妯i n ，涮葛 s 根据算法的假设，r ( o ，i ) ，并且根据引理2 3 有 k 。( 1 一r l i ) 1 ， 那么根掘( 2 3 8 ) 及本引理假设条件，我们有 。k _ ，l i g 。i l i a , ， ( 2 3 9 ) 再次根据引理2 3 有 ，”。(