（计算数学专业论文）一类解无约束最优化问题的锥函数插值模型算法.pdf

南京航空航天大学硕士学位论文 摘要 本文主要研究锥函数插值模型算法及其数值实现，共有五章。 首先介绍了直接搜索方法的发展概况，归纳总结了目前比较有效的各种算法。 其次论文对于数值试验结果较好的二次模型插值算法和发展概况做了概要性的介 绍。 第三章我们介绍了锥模型的起源和算法的发展过程，并着重对于算法模型的确 立，算法的详细步骤，算法所具有的优势及存在的问题做了较详细的介绍。 第四章是本文的主要部分，探讨了锥模型信赖域子问题的求解及不完全锥函数 插值模型算法的数值实现。在分析子问题最优性条件的基础上，我们给出了锥函数 模型信赖域子问题的求解算法；并从数据拟合的角度提出了对锥模型中参数向量的 另外一种选择方案。 第五章是算法的实现及数据试验部分。对算法的实现过程作了实质性的改进， 使得计算过程更加简洁有效，并通过一定数量的数据试验对于算法的参数做出了合 理的选取。试验结果表明锥函数插值模型算法是一类有效的直接方法，值得进一步 研究。 关键词：最优化，直接搜索算法，二次插值模型算法，锥函数插值模型算法， 信赖域。 一类解无约束最优化问题的锥函数插值模型算法 a b s t r a c t t h i sp a p e rm a i n l yc o n c e r n st h ec o n i ci n t e r p o l a t i o nm o d e lm e t h o df 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 a n di t si m p l e m e n t a t i o n t h es t r l l c n l r eo f w h i c hi so r g a n i z e da sf o l l o w s ： f i r s t l y , w es u r v e yt h eh i s t o r yo f t h ed i r e c ts e a r c hm e t h o d sc o n c i s e l y , a n ds t t r o _ r n a r i z e t h em e t h o d st h a ta r ec u r r c n d yc o n s i d e r e dt ob ee f f e c t i v ef 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 s e c o n d l y , t h eq u a d r a t i ci n t e r p o l a t i o nm o d e lm e t h o d ( q i m ) ，w h i c hn o w i s s u p p o r t e db y p r o f o u n dt h e o r ya n dg r a c e f u lt e s tr e s u l t s ，i sd i s c u s s e d i nt h et l l i r dc h a p t e r , w ee x p l o r et h ec o n i ci n t e r p o l a t i o nm o d e l ( c i m ) 。i n c l u d i n gi t s o r i g i n ，i m p r o v e m e n tc o n t r a s t e d 谢mq i m e s p e c i a l l y , w eg i v et h ec o m p u t i n gs t e p sa n d c o n v e r g e n tp r o p e r t yo f t h em e t h o d p r o p o s e db y n ia n d h u , b e c a u s eo b rf t l r t h e rr e s e a r c hi s b a s e do nt h i sm e t h o d m e a n w h i l e ，w e p o i n t o u tt h ep r i v i l e g ea n dd e f e c t i v eo f c i m n ef o u r t hc h a p t e ri st h em a i nb o d yo ft h i sp a p e r w ee x p l o r eh o w t oa p p l yt h ec i m t os o l v eu 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 se f f e c t i v e l y a tf i r s t ，o nt h eb a s i so ft h e s u f f i c i e n ta n dn e c e s s a r yo p t i m a l i t yc o n d i t i o n s ，w eg i v eac e r t a i na l g o r i t h mt oc o m p u t et h e t r u s tr e g i o ns u b p r o b l e m ；t h e n ，w ed r a wo u tad i f f e r e n ts c h e m ef o rp a r a m e t e rv e c t o ri n c i m i nt h el a s tc h a p t e r , s e r i e so fn u m e r i c a le x p e r i m e n t sa r em a d e t h er e s u l t ss h o wt h a t c o n i ci n t e r p o l a t i o nm o d e lm e t h o di sa ne f f i c i e n td i r e c ts e a r c hm e t h o d t 1 l i ss h o u l db e f u r t h e rr e s e a r c h e d k e yw o r d ：o p t i m i z a t i o n ， d i r c c ts e a r c hm 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 ， c o n i cm o d e l ，t r u s t r e g i o n 。 2 南京航空航天大学硕士学位论文 前言 自9 0 年代以来，直接搜索方法由于工程与生产实践上的迫切需要，成为人们的 研究热点，它是目前最优化研究领域内十分活跃的分支之一，而且在某些实际应用 中已经取得了很大的成功。到目前为止，直接搜索方法已经发展起来众多的算法， 相应的理论研究也得到了极大的发展。其中，二次模型插值算法以良好的数值试验 结果与较完备的理论支持，显示了它对解决无约束最优化问题的有效性。但是对于 一些二次性态不强、曲率变化剧烈的函数，采用二次模型插值算法通常达不到理想 的效果。为克服二次模型插值算法在解决这一类问题上的不足，s o r e n s e n 在1 9 8 0 年首先提出了锥模型算法。由于锥模型增加了一个新的向量，可以引入更多的插值 条件，在理论上具有一定的优势，所以从一开始就受到了广泛的关注与深入研究。 s o r e n s e n m l 的拟牛顿算法，d e n g t “l ，杨”1 的b f g s 算法，埘和s u n t 。3 1 的信赖域 算法，等等一些不同的算法相继从不同的角度被提出来。但是由于锥插值模型算法 需要较多的函数值计算，收敛速度相对比较缓慢，因此目前的数值试验结果并不理 想。 由于二次插值模型算法目前具有较好的数值试验结果以及较完备的理论支持， 且相对于锥插值模型算法来说，所需要的插值点数目较少，在吸取了这些优势的基 础上，结合锥插值模型，f 和h u 【1 q 提出了一种新的算法( 本文在此称为不完全锥插 值模型算法) 。但是此方法也带来一些新的问题。本文的工作是围绕不完全锥插值模 型算法的数值实现展开的。全文共有四章，内容分别如下。 第一章简单地介绍了直接搜索方法的发展概况。第二章介绍了二次插值模型算 法。对二次插值模型算法的基本思想、目前流行的算法、发展概况做了概要性的介 绍。第三章我们介绍了锥插值模型的起源，算法的改进。由于f 和h u 提出的不完 全锥插值模型算法是本文进一步研究所要采用的主要算法，所以对该算法从模型的 确立，算法的详细步骤，算法本身所具有的优势及存在的主要问题做了较详细的介 绍。第四章是本文的主要部分，针对不完全锥插值模型算法实现的目前存在的主要 问题进行了探讨。第一节介绍锥模型信赖域子问题的求解。我们根据极小解存在的 最优性条件，提出了新的求解方法。第二节提出了对锥模型引入的新的参数向量的 另外一种选择方案。第四章是算法的实现及数据试验部分。我们对算法的实现过程 作了一定的改进，使得计算过程更加简洁有效。数据结果表明了我们所提出的求子 问题的方法及算法的实现是有效的，这对以后的进一步研究打下了一个良好的基础。 一类解无约束最优化问题的锥函数插值模型算法 第一章直接搜索方法简介 直接搜索方法( d e r i v a t i v ep e em e t h o d 简称d f m ) 是一类不利用函数的导数值 而直接利用函数值信息的求解优化问题的方法。它起源于2 0 世纪5 0 年代，在6 0 ， 7 0 年代，d f m 方法得到了很大的发展，相关的算法也得以很大的丰富。许多的国 内外学者从不同角度提出了一系列的算法，如n e l d e r ，m e a d 1 1 等人在1 9 6 5 年提出的 单纯形方法；p o w e i l 在1 9 6 4 年提出的共轭方向法等等。但是这些早期的方法由于 理论上的缺乏以及在实际使用中的结果不理想，导致在8 0 年代期间，对d f m 方法 的研究进入了一个相对缓慢的时期。到了9 0 年代，由于工程上及生产实践中的迫切 需要，该类方法又一次成为优化学者及相关人员的研究热点。他们或是在原有的算 法进行改进的基础上，或是从全新的角度，提出了多种不同的算法。如t o r c z o n1 2 1 ， p o w e l l 和t o i n t 等人的研究工作。而且这时直接搜索算法的理论证明和数值分析都 有了很大的发展。随着d f m 算法在实际应用中不断取得极大成功的诸多事例的出 现，目前d f m 算法已经成为国际优化界一个热点研究方向。 由于直接搜索方法只利用了函数值信息，这使得它在求解诸如工程上通过实验 测量而得到的一类优化问题中，有着其他方法无可比拟、不可替代的作用。总之， d f m 方法在如下二个方面有着很好的应用：( 1 ) 函数的梯度无法求解或求解十分困 难；( 2 ) 函数值的计算工作量很大。 d f m 法研究至今，已经产生了许多不同的算法，从本质上大致可归纳为以下六 类：( 1 ) 单纯形法；( 2 ) 模式搜索法；( 3 ) 线性搜索法；( 4 ) 插值法；( 5 ) n 发式算法；( 6 ) 有限差分法。由于有限差分法是利用有限差分来近似函数的梯度，从严格意义上来说， 已不属于直接搜索算法。( 1 ) ( 2 ) ( 3 ) ( 5 ) 类方法在很多的文献中有较详细的介绍，如可 参见文献 3 等。在第二章中，我们将主要介绍一下插值方法类中的二次模型插值 方法。由于约束最优化问题我们可以通过罚函数方法或增广l a g r a n g e 函数方法等将 其转化为无约束优化问题，所以耳前研究的一系列算法大都是解无约束问题的。本 文也着重讨论以下无约束最优化问题： m i n f ( x ) 其中f ( x 1 一般为连续函数。 2 南京航空航天大学硕士学位论文 第二章二次函数插值模型方法 插值方法的基本思想是在某一搜索区域内，不断地用简单的低次插值多项式来 近似目标函数，并逐步用插值多项式的极小点来逼近原目标函数的极小点。二次插 值方法即在当前迭代点h 的某一邻域b 。内不断地建立f ( x ) 的二次近似函数m 。( z ) ， 然后在此邻域内通过极小化( z ) 所得的极小点，来确立新的迭代点，同时不断调 整插值点集，以保证( x ) 是在r ”整个空间上逼近丫x j ，从而最终求得原问题的极 小点。在该类方法中，一般取迭代点x 。处的二次插值函数m 。( x ) 为 聊t ( x ) = f ( x 女) + 6 7 ( x x ) + ( x x t ) 7 a ( x x 女) 2 ( 2 1 ) 其中a r ，b e r “是待定的矩阵和向量，它们可以利用函数值信息，由万个插值 条件 m 。( y ) = f ( y ，) i = 1 , 2 万 来确立，其中鬲：= 1 + 1 ) 0 + 2 ) 。 i n f 把l d f 一1 在6 0 年代首先提出了二次插值方法，并于1 9 7 3 年对该方法作了进一 步的改进，从而提出如下的算法框架。 算法2 1 ( 1 ) 记插值点集，r 为前面所有迭代步中计算过函数值的所有点的集合，即 y = “，v ：_ ) ( 日 ) ，p = 鱼芈。选取满足 x y ，f ( x i ) o ，给定常数o 编 1 ， 0 y o y 1 1 y 2 令k = 0 。 步2 ：利用插值点集y 建立- f ( x ) 的插值模型m 。( x ) 。 步3 ：极小化插值模型 计算x ：，使得m ( x ；) = m 砸m 女( x ) z e d 计算，( 工：) 及比值凤2 瓦f i ( x i k ) j - 丽f ( x ；) ( x km k 。 朋女j 一【工i ) 步4 ：修正插值点集 如果p 。仇，把x ；增加到y 中去，并去掉y 中某一点； 如果p 。 k 。( k 。的含义见定理2 5 ) 的任意正数。 t o i n t 嘲证明了可以经过有限步修正就可使得】，在b 中是充分的( 具体的修正 过程可以参见文献 1 0 ) ，并且给出了利用二次模型的插值模型算法的全局收敛性 定理。 定理2 7 ：设f ( x ) 二阶连续可微且f ( x ) 下有界，f ( x ) 的一阶导数与二阶导数均 有界，m 。( z ) 的二阶导数也一致有界。则由二次插值模型算法产生的序列k ) 的每 一个极限点x + ，均有可丁( x ) = 0 。 下面讨论锥函数插值模型。 一类解无约束最优化问题的锥函数插值模型算法 第三章锥函数插值模型方法 二次插值模型是在当前迭代点x 。的邻域吼内用二次多项式去逼近原函数，这对 于许多问题是很有效的。但是对于一些非二次性态强、曲率变化剧烈的函数，采用 这种方法通常达不到理想效果。为了解决这种情况，d a v i d o n 在1 9 8 0 年，提出了无 约束极小化的锥模型方法，这种方法不但成功地解决了二次模型在逼近原问题上的 不足，而且较多的利用了函数及梯度信息。此后s o r e n s e n ，d i 和s u n 等众多研究人 员在此方面作了大量的工作，使得锥模型方法如今已经发展成为一类具有一定理论 基础的，在实际计算中具有某些方面优势的算法。因此本文所要讨论的一个有挑战 性的研究工作便是通过函数插值建立一类解无约束优化的问题直接方法一锥函数插 值模型方法。 d a v i d o n i “1 ( 1 9 8 0 ) 针对求解如下问题： m i 。1 1 妒( x ) ：兰：堕；掣 r一，x，口，6rn,ct,ar 。i 旷妒( x ) 2 1 ：亍；j 矿 r ”，x ，口，6 采用了变换： jw 5 ( w ) 2 x + r 丽 ，r “，6 r ” 将问题转化为下列形式： 妒0 ( 们) = 妒( x ) + ( x ) 。，w + 圭w 7 w 并证明了至多( 玎+ 1 ) 步可以求得妒( x ) 的极小点。 s o r e n s e no z l ( 1 9 8 0 ) 年提出了一个一般的锥函数模型： 妒。c x ，= ，c x 。，+ 端+ i 盂! 嬲 其中b k r “”是h e s s e n 近似，g i = v f ( 坼) ，a ie r ”且满足如下条件 1 一d ：( x x ) o r v x b k = x ：i i x - x t | | s a i ) 对于模型( 3 1 ) 的求解，他提出了如下的方法。首先采用变换： ( 3 1 ) ( 3 2 ) 南京航空航天大学硕士学位论文 x = 坼+ 1 + j , 醒w w ( 其中以r 且，女可逆，阮r ”) 把空间转换到w 空间中去，然后在w 空间建寸r - - 次函数模型仇( w ) 去逼近函数 f ( x 。+ 等 ) ，并对该二次函数模型极小化，把所得到的极小点通过变量的共线 i + n i w 调比再转换到原空间中去，如此不断的迭代下去，直至找到最优解为止。在此基础 上，利用在最近两次迭代的函数值与导数值的信息，从共线调比的角度，s o r e n s e n 导出了锥模型方法满足的广义拟牛顿方程，并证明了方法的收敛性。 目前模型( 3 1 ) 已经被普遍采用。对于该模型的有效求解，已有一些不同的算法 从不同的角度提出，各自的试验数据结果都表明了其方法的可行性及在解决特定问 题上的优势。 d f 和s u n t ”1 ( 1 9 9 6 ) 提出了求解锥模型( 3 2 ) 的信赖域算法。锥模型的信赖域子 问题是： m 她i n c p t ( x ) 对于该问题，d ，和s u n 讨论了极小解存在的充分和必要条件，给出了锥模型的信赖 域算法，并建立了算法的收敛性理论，并证明了算法具有q 超线性收敛速度。同时 对1 9 个优化问题进行了数值实验，与二次模型的信赖域算法进行了比较，试验结果 均表明锥模型的信赖域算法要比二次模型的信赖域算法更有效。d e n g i “11 9 9 5 年在 一般的无约束优化问题的b f g s 方法的基础上，利用对当前迭代及前一次迭代的对 函数值和梯度值的插值条件，得出了求解问题( 3 1 ) 极小值的b f g s 方法 ( c o n i c b f g s 法) 。在适当的合理的假设条件下，d e n g i “ 也给出了方法的超线 性收敛性的证明。 可见，要运用锥模型的方法解决问题( 1 1 ) ，关键是如何确立一个合理的锥模型 ( 3 1 ) 。如果要完全通过仅用函数值信息的插值方法来确立模型( 3 1 ) ，需要利用鬲+ 行 个插值点，这相对于二次插值方法来说，插值点的数目明显增多。又由于在对插值 点集进行修正，保持y 的几何充分性问题的问题上，二次插值方法已经有了相对完 整的理论，并且二次插值模型算法的数值结果及理论证明都表明了该方法是目前一 类较好的d f m 算法。考虑到这二方面的原因，f 和胁5 1 提出了一种将二次插值 与完全锥插值结合起来的求解方法，在此称为不完全锥模型插值方法。由于本文将 9 一类解无约束展优化问题的锥函数插值模型算法 在此模型的基础上进一步进行研究，所以以下对此模型及不完全锥模型插值方法作 一个详细的介绍。 不完全锥插值模型的确立 可归纳为以下几个步骤： ( 1 ) 首先利用插值点集j ，建立厂( x ) 的二次插值模型聊。( x ) ，m 。( x ) 的表达式如下 m i ( x ) = f ( x t ) + 6 j ( x x i ) + ( x x i ) 7 a i ( x x 女) 2 。 ( 2 ) 利用共线调比公式和二次逼近思想推出仇( x ) 伊tc x ，= ，c x t ，+ 端+ 兰二兰j 嚣：；：；：；笋c s ， 在仇( 功的表达式中，钆和a 。由插值模型( 2 1 ) 确定。a 。的确定将在下面讨论。 ( 3 ) 为了确a k ，引进如下的插值条件： 仇( x n ) = f ( x ) 此外，a 。必须满足以下保持吼( x ) 有定义的条件 对v x b k ，都有 1 一a ：o 一孔) 0 令y i = 1 + a r s i l ，其中s 女一l = x 一x 一l ，贝0 有： ( 3 4 ) 南京航空航天大学硕士学位论文 ” 1 ：- 撬 若y r 1 和醵矗一1 0 ，我们选择 吼：b k 5 t 一1 否则，选取吼= 0 。由此可得以下的算法 算法3 1 ( 不完全锥插值模型算法) ( 3 5 ) ( 3 6 ) 步0 ：初始化。 给定初始插值点集y ，初始信赖域半径。，终止误差占，给定常数0 口。 0 ，0 r osr 1 l ，0 0 ，给定初始向量口0 ，计 算，使得x o = a r g r a m i n y j ，令七= 0 。 步1 ：检验终止条件。 如果i s ，停止迭代输出札 步2 ：建立二次插值模型。 用插值点集y 各点的函数值建立，( x ) 的二次插值模型历。( x ) ，设m 。( x ) 的表达 式如下： r a i ( z ) = f ( x t ) + 醪( x z t ) + ( x x t ) 7 a k ( x x t ) 2 如果慨忙气且y 在集合4 = 秒r ”川y h 1 1 - 占。，则转步3 。否则修正插值点集y ，直到y 在 g = 抄i i y - x 。忙以 ( 其中以( o ，慨阳) 是充分的，转步3 。 步3 ：建立锥插值模型仇r x j 1 1 一一 一二耋坚歪丝塞墨垡些间璧堕丝堕塑堡焦堡型篁鲨 步4 ：求锥插值模型的极小点。 计算z ：，使得x ：= a r g l ，妥怯。吼( x ) 。 如果吼( ) 一吼( x ：) ，则修正插值点集y ，转步7 ；否则，转步5 。 步5 ：计算比率见，并修正插值点集。 企一一啦2二篷!： 。k c , o k ( x i ) 一纯( x ：) 如果以碣，则把x ：增加到y 中去，并从中去掉一点，转步6 ： 如果p 。 0 ，使得对v x r “，都有 1 1 1 盯( x ) 0s 七磨，l i v 2 ，( x ) 0 七斗： ( 2 ) 下水平集缸r “i 厂( 力厂( ) ) 是有界集合； ( 3 ) 二次插值模型函数的一阶导数和二阶导数均一致有界。即存在常数 k 。 o ，k m 0 ，使得对v 七n ，均有慨i i k 。，i 阻。0 k 。 南京航空航天大学硕士学位论文 设序列 ) 是由算法3 1 产生的，若上述三个条件均成立，则序列 “) 的每一个极 限点x ，均有v ( x ) = 0 。 从算法3 1 的实现步骤可以看到，它是一种将二次插值模型方法与锥模型方法 紧密结合在起的算法，算法3 1 的理论分析表明该算法具有一定的优势，值得进 一步的探讨和研究。本文对算法3 1 的实现和数值计算进行了深入研究，主要探讨 了如下问题： ( 1 ) 锥模型信赖域子问题有效解。 ( 2 ) 模型( 3 1 ) 中的参数向量a 。的取值与锥函数模型的逼近的关系。 ( 3 ) n e w t o n 基插值多项式的数值计算和存贮技术。 这些问题在下一章将进行详细的讨论。 二类解无约束最优化问题的锥函数插值模型算法 第四章锥函数插值模型算法的数值实现 在这一章中，我们讨论了算法3 1 的数值实现，首先讨论信赖域子问题。 4 1 信赖域子问题 锥函数插值模型算法是一种基于信赖域技术的求解算法，所以子问题的求解成 功与否是求解整个问题的关键。 在第k 步迭代点札处的锥模型信赖域子问题一般采用如下形式： r a i 。n 唧( x ) ( 4 1 ) i ，一h 阻 、 其中，仇( x ) 由( 3 2 ) 式定义，是信赖域半径。 首先提出该问题并进行研究解法的是d f 和勋玎n 2 1 ，他们还以此为基础证明了算法 的q 超线性收敛性。本节首先分析了i b i s ( 4 1 ) 的最优性条件，得到了两个重要的结 果，然后在此基础上，提出了一种新的求解算法，在进行的局部数值试验中，也证 明了这种算法的有效性。 首先导出问题( 4 1 ) 解的必要条件，为简便起见，引入如下记号： s = x - - x 女，峨= a i 一口女6 f b k 口；，妒= 以，厂= f ( x t ) 则子i 司越相应地转化为 删讥h g t s 矿j 1 蔫( 4 ：) n 例 d a v i d o n 在文献 1 1 】中，给出了如下的一个结果： 引理4 1 ：妒( s ) 由问题( 4 2 ) 定义，则：v 妒( s ) = ( ，一a s 7 ) - 1 ( v g + b s ) ，其中 v ：1 一d t p 0 。 下面的引理来自d i 和s u n m l ，由于表达式有了适当的变化，因此同时给出了弓 理的证明。 1 4 堕室：堕窒璺丕盔堂堡主堂垡堡塞 引理4 2 ：假设g o ，b 0 , 1 一口7 j 0 ，若j + 为( 4 2 ) 的解，则存在0 ，使得 f ( b + z ，) j + = _ v g + a a 2 a i 刈一) = o 其e p ，v = 1 一a t s 。 证明：记吲州s h 贝 j v 吣) 2 赢，同时记吣) - 1 玎s 。 由l a g r a n g e 乘子准则，以及k t 条件得 f v q ( s ) + u v q ( s ) = 0 b ，7 ( s ) = 0 将引理4 1 的结果带入( 4 1 ) 式，则有 芦1 一* t - 1 * g 拙儿“南- o 化简得 v ”麒+ 谛”甜”n _ 0 令 。v * 3 u 扯丽 ( 4 3 ) 整理得 ( b + r ，) j = - v + g + r 口 ( 4 4 ) 又由如谛腽州( s ) “玳s ) - o 口 将( 4 3 ) 与( 4 4 ) 式合并，即证明此定理。 在引理4 2 的基础上，与d i 和s u n m l 一样，给出如下的解的充分条件。 引理4 3 ：在引理4 2 的条件下，如果百= b + 2 一搿船7 半正定，并且j 和五满足 一类解无约束最优化问题的锥函数插值模型算法 ( b + z o s = 一( 1 一a t s ) g + 旯2 a 旯( j 阈j 一) = 0 旯o ，i l s l i a ( 4 5 口) ( 4 5 6 ) ( 4 5 c ) 则5 为问题( 4 2 ) 的解。 引理4 2 和4 3 为解决子问题( 4 2 ) 提供了一个有效的方法。 下面着重讨论如何有效地求解( 4 5 ) 中的s 和五。 若占+ 甜是非奇异矩阵，且满足1 + a t ( b + 盯) “g 0 ，根据矩阵逆的秩一校正 的s h e r m a n m o r r i s o n 定理，s 可以表示为 j ( 九) = ( b + l 一g a 7 ) 一1 ( 一g + x a 2 a ) = ! ；芝；掰卜c b + 2 , 3 ) - l g ，+ 九? c b + u ，。1 口4 6 在实际计算中，由于曰+ 盯一g a 7 是非对称的，因此直接求逆比较困难，通过( 4 6 ) 式， 我们可以只考虑b + 甜的求逆问题。此时分如下两种情况进行讨论： ( 1 ) 若f = 0 ，且l l s ( o ) l i o ，即此时慨o ) l | 。以下求取z ，使慨z ) i i = 。 设b 的特征值为u 1 u 2 u 。，则b + 甜的特征值为 u l + a s i 2 + u 。+ a ，显然当旯 一时，“，+ 丑 0 ，f = 1 , 2 n 。而 ( b + 甜) 。忆= j ，从而得到如下的结论： ” u 十 当旯斗佃时 1 + a t ( b + x z ) 一1 9 叶1 粕+ u ) 。g | | 一o 代入( 4 6 ) ，得l i i n 愀a ) i 【= 2 | | 口| | 。因此若先假设刮口忙c o ，满足慨) i i = a 。此时 s ( z ) 为问题( 4 5 ) 的解。 在上面的讨论中，我们事先假设向量口满足c l 0 ，常数毛，占2 0 步1 ：取 = 2 0 + ，计算s ( ) ， 若慨a ) 卜f 毛，则停止，输出j + = s ( ) ；否则若愀 ) ij + q ，转步2 若慨 ) _ | 0 其次，a 。应满足插值条件的要求。由于引入通常锥函数附加的插值条件： 吼( 扎一，) = f ( x ) ，有等式( 3 5 ) 的约束，即 ( 4 7 ) 其中h 的选择参见( 3 6 ) 。 最后，锥插值模型极小点的存在性对吼的选择也是有限制的。为了保证锥模型子问 题的求解实现，在第k 步迭代时a 。应满足 i 慨i 【c 1 ( 4 8 ) 显然，对于锥函数( 3 3 ) 有：v 十。( 坼) = v f ( 坼) = g i ，为了使( 3 3 ) 在札的邻域 b 。内更好的拟合于厂( x ) ，应使v 2 f ( x 。) 与v 2 吼( 以) 充分靠近。直接计算，得 v 2 平t ( x ) = a + 口t g ：+ g t 口； 两边同时右乘s 。( = 一x ) ，得 v 2 甲t ( x i ) 占i l = 4 s i l + 口 ( g r k s t 1 ) + g k ( 口：s i 一1 ) ( 4 9 ) 用g 。一g k - i 近似代替上式左边部分v 2 仇r 以j s 。，整理得 ( g t t s t 1 ) 口i + ( 口；占女一1 ) g i = g i - ( g 一l + 4 s t 1 ) f 4 1 0 ) 由于( 4 9 ) 式涉及到g k qg 。，a 。s 。三个方向，并考虑到等式的特点，取q 的形式结构 如下： 吼= t i ( a j + g ) + t 2 9 t ( 4 1 1 ) 将( 4 1 1 ) - 与( 4 7 ) 代入( 4 1 0 ) 式，计算得 忙未 = 急 m 南京航空航天大学硕士学位论文 为了以下讨论的方便，我们再引进如下的记号 则吼的表达式为 + 鼬) + 独 “ ( 4 1 3 ) 从( 4 9 ) 可知，当i g ：s h i 很小时，吼几乎不起作用，因此可取鲰= o 。此外，i g j 一。 这个量可以看成锥模型函数仇( x ) 与二次模型函数m 。( x ) 接近程度的一个判别量。 一类解无约束最优化问题的锥函数插值模型算法 第五章算法的实现和数值试验 本章对不完全锥插值模型算法3 1 进行了数值试验。数值计算是在多媒体p c 机 奔月2 0 0 0 6 3 0 0 上，采用双精度运算进行的。w o o d 等六个函数选自【2 8 等。直接 搜索方法由于不利用导数信息，所以需要较多的函数值计算，而且同时其收敛速度 相对比较慢，因此直接搜索算法数值试验的主要目的是计算适量的试验函数，以便 选取较好的控制参数。 5 1 基函数的计算与存贮技术 对于算法3 1 的步2 中二次插值模型的确立，s a u c e r 和尬【”1 给出了一个有效的 算法，即n e w t o n 逐次插值方法。但是该算法每一次迭代，均需要进行许多的递归运 算。这种运算，不仅使得占用的存贮空间及运算量显著增大，过程的实现变得十分 困难，而且由于误差的传播积累，使得结果非常不稳定。针对上述困难，我们采用 存贮二次函数的基函数的系数，以及基函数的梯度的系数的方法，较好的克服了上 述的困难。基本思想如下：首先选定二次函数的插值基函数( 除去1 1 依次排序为 _ ，x 2 ，x 。，x 扎x 1 x 2 ，x l x 。，x 2 2 ，x 2 x 3 x ：( 共有亓一1 个) ，然后在每一次迭代时，只保存 各个基函数相应于插值基函数的系数，这样大大节省了存贮空间与运算量，而且这 时各个基函数的梯度计算也是非常简单的。具体由算法5 1 实现。 算法5 1 ( n e w t o n 基函数的求解算法) 设n 为求解问题的维数，则初始插值基的个数为h ，将插值点集的各插值点排列 为向量：y = ( 一，z 2 ，) ；将相对于第i 个插值点y i j 】的各初始插值基的值( 除去第 一项1 ) 排列为向量：r ，= ( x f l ，x 1 2 _ 。，x ：，x x2 x 1 1 ，x ，2 z n ，z ：) ，用茚阶矩阵g 存 储，这个矩阵的初始值取为单位矩阵，即第i 行( 记为g f 】) 的第i 个元素为1 ，其余为 0 ；选取与q 相同的矩阵p ，并引入如下记号：对任意两个向量f ，u ，t r u 表示两向量 的内积。令f _ o ；进行如下的迭代计算： 南京航空航天大学硕士学位论文 步1 ：选取x ，】，计算相应的向量，c ：= t f “f 不为0 ；对于p 【f ，求 p i 】：= c p i 】。 步2 ：对于1 j i 一1 ，计算 c ；t f 烈儿 t e m p ：= c p i 】： p j 】：= p j 一t e m p 。 步3 ：校正q 函数。对于i o 2 7 r x l 土+去tail一(量)，耶022 石、工”1 p = ( - 1 ，0 ，0 ) 7 ，x + = ( 1 ，0 ，o ) 7 ，f = 0 计算的数值结果见表一。 表一 问题名称问题维数声迭代次数 i24 4 0 4 8 8 5 e 0 0 54 8 i i41 4 5 6 7 6 2 e 一0 0 39 5 i41 9 4 7 2 8 7 e 0 0 56 3 49 0 4 5 5 7 0 e - 0 0 35 6 v 21 7 3 5 8 7 e 0 0 18 7 32 2 0 6 4 9 7 e 0 0 11 1 2 南京航空航天大学硕士学位论文 由表l 中的数值结果，结合【9 ， 1 8 】等文献中的数值试验结果，我们有如下的 分析结果： ( 1 ) 对于问题( i ) - ( v i ) ，我们能够在较少的迭代次数内求得较好的结果。这说明 我们的研究方向是对的，有进一步思考的价值。 ( 2 ) 锥模型由于增加一个向量口，自由度增加了，从而可以引入更多的插值条件， 所以锥函数插值模型算法从理论上来说，在解决某些问题上，相对于二次插值方法 具有一定的优势，值得深入研究。但是从数值试验结果上看，并不比二次插值方法 有明显的改进，所以如何进一步改进、完善锥函数插值模型算法，提高算法的可靠 性及有效性，有待于进一步的研究与探讨。 一类解无约束最优化问题的锥函数插值模型算法 参考文献 1 】j a n e l d e ra n d r m e a d ，as i m p l e x m e t h o d f o r f u n c t i o n m i n i m i z a t i o n ，c o m p u t e rj o u r n a l 7 ，3 0 8 - 3 1 3 ，1 9 6 5 【2 v t o r z o n ，m u l t i - d i r e c t i o n a ls e a r c h ：ad i r e c ts e a r c ha l g o r i t h m f o rp a r a l l e lm a c h i n e s p h d t h e s i s ，r i c eu n i v e r s i t y , h o u s t o n ，t e x a s ，u s a ，1 9 8 9 3 p o w e l l ，d i r e c t s e a r c hm e t h o d s f o ，o p t i m i z a t i o nc a l c u l a t i o n s ，a c t a n u m e f i c a t ，p p 2 8 7 3 3 6 ，c a m b r i d g eu n i v e r s i t yp r e s s ，1 9 9 6 4 】d w i n f i e l d ，f u n c t i o na n df u n c t i o n a lo p t i m i z a t i o nb yi n t e r p o l a t i o n 加d a t at a b l e s p h k t h e s i s ，h a r v a r du n i v e r s i t y , c a m b r i d g e , m a ，1 9 6 9 【5 d w i n f i e l d ，f u n c t i o nm i n i m i z a t i o nb yi n t e r p o l a t i o ni na d a t a t a b l e ，j i n s t m a t h a p p l 1 2 3 3 9 - 3 4 7 ，19 7 3 6 】m j d p o w e l l ，a d i r e c ts e a r c h o p t i m i z a t i o n m e t h o dt h a tm o d e l st h e o b j e c t i v eb y q u a d r a t i ci n t e r p o l a t i o n ，p r e s e n t a t i o n a tt h e5 t hs t o c k h o l m o p t i m i z a t i o nd a y s ，1 9 9 4 7 】m j d p o w e l l ，a d i r e c ts e a r c ho p t i m i z a t i o nm e t h o dt h a tm o d e l st h e o b j e c t i v e a n d c o n s t r a i n t f u n c t i o n sb y l i n e a r i n t e r p o l a t i o n ，i n a d v a n c e si no p t i m i z a t i o na n dn u m e r i c a l a n a l y s i s ，p r o c e e d i n g s o f t h es i x t hw o r k s h o po n o p t i m i z a t i o na n d n u m e r i c a la n a l y s i s ， o a x a c am e x i c o ，v o l u m e2 7 5 ，p a g e s5 1 6 7 ，d o r d r e c h t ，n l ，1 9 9 4 k l u w e ra c a d e m i c p u b l i s h e r s ，1 9 9 4 【8 a r c o n n ，k s c h e i n b e ra n dp h l t o i n t ，o nt h ec o n v e r g e n c eo f d e r i v a t i v e f r e em e t h o d s 力ru n c o n s t r a i n e do p t i m i z a t i o n , i na i s e r l e sa n dm b u h m a n n ，e d i t o r s ，a p p r o x i m a t i o n t h e o r ya n do p t i m i z a t i o n ：t r i b u t e st om j d p o w e l l ，8 3 1 0 8 ，c a m b r i d g eu n i v e r s i t y p r e s s ，c a m b r i d g e ，u k ，1 9 9 7 9 a r c o m a ，a n dp h l t o m ，a na l g o r i t h mu s i n gq u a d r a t i ci n t e r p o l a t i o nf o r u n c o n s t r a i n e d d e