（计算数学专业论文）一种解无约束优化问题的过滤集信赖域线搜索方法.pdf

摘要 摘要 n i m g o u l d c s a i n v i t u 和p h l t o i n t 将过滤集技术推广到 无约束优化问题上以此为基础，缪卫华提出了一种新的无需判断 信赖域子问题凸性的方法本文采用了非单调信赖域方法，并结合 过滤集技术和线搜索技术，在一定的条件下证明了新算法的收敛 性数值试验表明，本文的新算法相对于经典的信赖域算法取得了 一定的成效 关键词：无约束优化，非单调，信赖域方法，过滤集技术，线搜索 a b s t r a c t a b s t r a c t g o u l d ，s a i n v i t ua n dt o i n tp r e s e n t e daf i l t e rt e c h n i q u 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 b a s e do nt h i sw o r k ，m i a oa n ds u np r e s e n t e da f i l t e rt r u s t - - r e g i o na l g o r i t h mw i t h o u tj u d g e m e n to fc o n v e x i t yo ft h et r u s t - r e g i o ns u b p r o b l e m i nt h i sp a p e r , w ep r e s e n tan e wn o n m o n o t o n et r u s t r e g i o nm e t h o dt h a tc o m b i n e sf i l t e rt e c h n i q u ea n dl i n es e a r c h t h eg l o b a l c o n v e r g e n c eo ft h en e wa l g o r i t h mi sg i v e nu n d e rc e r t a i nc o n d i t i o n s n u m e r i c a lr e s u l t ss h o wt h a tt h en e wa l g o r i t h mp r e s e n t e di nt h isp a p e ri s m o r ee f f i c i e n tt h a nt h eb a s i ct r u s t r e g i o na l g o r i t h m k e y w 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 ，n o n m o n o t o n e ，t r u s tr e g i o n m e t h o d ，f i l t e rt e c h n i q u e ，l i n es e a r c h 本文创新点 本文给出了一种新的求解无约束优化问题的方法创新点在 于：我们在m i a oa n ds u n 1 7 提出的方法的基础上采用了非单调信 赖域方法，并运用了线搜索，提出了一种组合的非单调过滤集信赖 域线搜索方法在新方法中，采用了过滤集技术和线搜索方法，减 少了重新求解信赖域子问题的次数，从而降低了计算量在一定的 条件下，证明了该算法的全局收敛性我们用标准测试函数进行了 数值试验，数值结果表明新方法对于中大型优化问题有一定的成 效 _ j l 一 刖舌 考虑一般的无约束极小化问题( p ) m i ny ( x ) ：r e r n 其中，( z ) 是r n 上二次连续可微函数解问题( p ) 的优化方法有很多，并且新 方法还在陆续出现我们把这些方法归纳起来分为两大类：一类是仪用计算函 数值所得到的信息来确定搜索方向，通常称它为直接搜索法，简称为直接法； 另一类需要计算函数的一阶或二阶导数值所得到的信息来确定搜索方向，这 一类方法称为解析法直接法不涉及导数，适应性强，但收敛速度一般较慢：解 析法收敛速度一般较快，但需要计算梯度甚至h e s s e 矩阵一般地，在可能求得 目标函数的导数的情况下，我们还是尽可能地使用解析法在这里，我们主要 介绍几种求解问题( p ) 的解析法 解无约束优化问题的总体化策略一般为两种：线搜索方法和信赖域方法 这两种方法都是迭代法，在适当的条件下，都能够保证算法产生的迭代点列收 敛到一阶或二阶稳定点 对于经典的线搜索方法，在每一步迭代中，通常先选择搜索方向8 良，然 后沿着选定的方向进行搜索，寻找一个合适的步长o l 七，这样就构成了一步迭 代，重复这个过程直至收敛为了保证线搜索方法产生的迭代点列能够收敛 到二阶稳定点，在迭代的过程中往往需要充分利用目标甬数的曲率信息，见 文献【2 1 这类方法的主要思想是：在每一步迭代中，都选择一对下降方向 ( 8 k ，毗) ，其中鼠是梯度相关方向，d k 是负曲率方向，然后沿如下曲线进行搜索， x k + l ( q 惫) = z 七+ q k 2 s 七+ a k d k ，其中步长因子。七由二阶线搜索准则确定 根据方向8 七的不同，线搜索方法分为最速下降法，共轭梯度法，牛顿法和 拟牛顿法等同样的，步长因子q 屉的选择是线搜索方法的另一个关键性的问 题主要分精确线搜索和不精确线搜索，精确线搜索主要有0 6 1 8 法，插值法等， 不精确线搜索又有a r m i j o 准则。g o l d s t e i n 准则，w o l f e p o w e l l 准则等，具体的描 述可见文献【6 ，2 1 1 信赖域方法以其卓越的理论性质和良好的数值表现而备受青睐，并且克 服了线搜索的一些缺点在每一步迭代中，信赖域方法首先在当前迭代点附近 h u苗 定义一个可以信赖的区域，在此区域内，我们认为模型函数是目标函数的一个 充分的近似然后，我们在此区域内选择模型函数的一个近似极小点作为下一 步迭代点这种方法即具有牛顿法的快速局部收敛性，又具有理想的总体收敛 性由于步长受到使t a y l o r 展式有效的信赖域的限制，故此方法义称为限步长 方法对于信赖域方法产生的迭代序列能够收敛到一阶或二阶稳定点已得到 了证明在标准信赖域算法框架( 文献【l ，1 2 ，2 1 ) 中，迭代点列是单调下降的， 对于一些坏条件问题，会出现收敛非常缓慢的情形针对这种问题，人们提出 了非单调技术( 文献 1 ，1 2 ，1 3 ，1 9 ，2 0 】) ，来加速算法在实际计算中的收敛速度， 并取得了很好的数值结果 定义信赖域子问题需要用到范数，其中最常用的是欧氏范数| i | i 和无穷 范数i i | | 。，及其某些加权形式若我们用无穷范数，实际上就相当于在变量的 两侧加卜简单界约束一般情况卜，基于解无穷范数的信赖域子问题总比基于 解欧氏范数的信赖域子问题要容易一些，但是，在理论上相对要弱一些因此， 在本文中，我们用欧氏范数定义信赖域子问题 另外，在相邻的两个不同的迭代点之间，信赖域方法有可能需要解模型函 数相同但信赖域半径不同的多个信赖域子问题，这主要是由于一开始选择的 信赖域半径偏大造成的注意到解一个信赖域子问题需要消耗大量的计算时 间，因此，我们不必局限于简单的缩小信赖域半径，而是沿着信赖域迭代步进 行后退线搜索( 见文献【7 】) 这样做一方面可以避免解信赖域子问题，节约了计 算时间，另一方面可以找到一个更好的近似最优点，促进迭代点列逼近最优点 过滤集( f i l t e r ) 技术首先由f l e t c h e r 等人于1 9 9 7 年在文献【1 5 】中提 出( 2 0 0 2 年发表) ，其目的是保证约束优化算法的全局收敛性为了找到约束 优化问题的最优点，我们一方面需要减小目标函数值，另一方面需要将约束违 反度函数降为零一般的方法是将这两个目标通过一个参数组合成一个罚函 数，这两个目标之间的权重就是由这个参数来调节，即罚函数法但是如何选 择这个参数是一个麻烦的问题过滤集的思想来源于多目标优化，为了避免罚 函数中这个麻烦的参数的选取，我们将减小目标函数值和降低约束违反度函 数看成是两个独立的，不相干的目标，从而将约束优化问题看成是一个双目标 优化问题来进行处理 随着过滤集技术的提出，在约束优化问题中被深入研究和j “泛应用( 见文 献【2 _ 4 ，1 4 ，1 6 】) 同样地，在无约束优化领域也有了一定的应用和发展首先， g o u l d 等人在文献【9 】中将多维过滤集技术应用到非线性方程组和非线性最小 二乘问题上文献【1 1 】和文献【8 】利用目标函数梯度构造多维过滤集，进一步将 一2 一 前言 过滤集技术推广应用到一般的无约束优化问题上，从而获得了较好的数值结 果但在文献【1 l 】巾的求解策略显得有些繁琐，故文献【1 7 1 中直接从标准的信赖 域框架出发，应用过滤集技术构建算法，在不牵涉仇k ( z 七+ 8 ) 凸性判断的情况 下给出了算法的收敛性结果从而简化了信赖域子问题的求解过程，获得了一 个较为简洁实用的算法形式 在本文中，我们不用判断信赖域子问题的凸性，将非单调信赖域方法结 合线搜索方法，并在算法中加入了过滤技术，提出了一种新的信赖域线搜索方 法即在本文的算法中，当试验点迭代不成功时，就采用过滤集技术和线搜索 方法，尽量地减少重新求解信赖域子问题的次数，从而降低了计算量在一定 的条件下，我们证明了该算法的全局收敛性，并且取得了不错的数值结果 本文在第一章给出了解问题( p ) 的新算法，并证明了该算法的收敛性最 后，在第二章中，我们通过了一组数值试验检验了本文提出的新算法的实际运 行效果通过数值结果可以看出，本文的算法是有效的 一3 一 第l 章过滤集信赖域线搜索方法 第1 章过滤集信赖域线搜索方法 本文考虑无约束优化问题 1 1 引言 御m i n 。m ) ， 其中f ( x ) 是一个二次连续可微函数运用迭代法求解问题( 1 1 1 ) 的关键是从 目前的迭代点z k ，计算+ 一个试探步s 知，从丌1 了产生个新的试探点 z j = x k + 8 k 如何求得试探步s 惫呢? 一般地，我们取目标函数f ( x ) 在z 七处的泰勒展式的前 三项，然后最小化这个t a y l o r 模型，求得8 七然而这个算法并不总是好的，例如 t a y l o r 模型是非凸的情形为了克服这个困难，我们采用了信赖域技术，且| j 在当 前迭代点定义一个邻域。并假定在这个邻域内t a y l o r 模型和目标函数一致，即 二次模型是目标函数f ( x ) 的一个合适的模型，然后用这个n 维二次模型米确 定试探步s 七 1 2 信赖域子问题 在介绍新算法之前，我们先来看试探步8 七的具体求法我们知道，求试探 步s k ，实际上就是解一个信赖域予问题，所以，我们首先给出无约束优化问题 ( 1 1 1 ) 的信赖域子问题为 m i nm k ( x k + s ) = f ( z k ) + 夕2s + s h k s s t 忪怪 ( 1 2 1 ) 其中，g a = v 厂( z 女) ，h k 是v z z f ( x a ) 的一个对称近似矩阵，a k 0 在实际计算 中，为了算法的高效性，我们通常并不要求精确求解上述问题，而是要求其满 足一定充分下降条件的近似解我们先给出问题( 1 2 1 ) 的下降性条件 我们记问题( 1 2 1 ) 的柯西点为s 拿，即问题( 1 2 1 ) 沿负梯度方向一9 k 前进 一4 一 第l 孥过滤集信赖域线搜索方法 时的解，满足下面的充分下降条件 毗) - m 如m 舵下i i 鲰i i m i n 黼a ( 1 2 2 ) 其中参数7 ( 0 ，1 ) 这个下降性条件在算法的收敛性证明中，起着至关重要的 作用并且对于这个条件，有很多有效的数值方法来计算s 南，以保证此条件的 成立( 见文献1 5 ，l o 】) 下面的一个定理为信赖域子问题( 1 2 1 ) 的数值解法提供了一个理论基础 定理1 2 1 设s ；是信赖域子问题( 1 2 1 ) 的解的允要条件是：i ls ：i l ， 并且存在a + 20 ，使得 ( b + a + 1 ) 4 = - 9 ， ( b + 入+ ，) 0 ， a 4 ( 一i is 圳) = 0 证明见文献【2 l 】中定理1 3 1 7 的证明该定理给出了s ；是信赖域子问题 ( 1 2 1 ) 的精确解的一个充分必要条件由此定理我们可以得到解信赖域子问题 ( 1 2 1 ) 的一个算法，见文献【7 】中的a l g o r i t h m 2 6 据此算法，我们可得到试探步 8 尼此试探步s 七不仅满足充分下降条件( 1 2 2 ) ，也满足条件 9 s k 7 7 1 时才接受z 去，否则，我们改变信赖域半 径，重新解信赖域子问题( 1 2 1 ) ，这样势必耗费大量的计算时间现在我们考虑 用过滤集技术米加大试验点z 古的被接受的几率，从而减少了重新解信赖域子 问题的次数，节省了计算时间 我们把梯度v 厂( z ) 记成分量形式，即v f ( x ) = a ( z ) = ( 夕1 ( z ) ，鼽( z ) ) t ， 过滤技术的基本概念是”占优”，故我们先来看”占优”的定义 定义1 3 1 1l 】任给两个点z l ，x 2 ，当 f f i ( x 1 ) i ig i ( x 2 ) i ，vi = 1 ，扎 一5 一 第l 争过滤集信赖域线搜索方法 时，我们称z 1 占优于z 2 ，也称z 2 被z 1 占优 这样，当我们仅关注迭代点列是否收敛于一阶稳定点时，点z 2 就完全没有 意义了下面我们再引入多维过滤集的定义 定义1 3 2 【1 1 】令厂= ( g k ，l ，g k ，n ) 乏工，其中9 k ，t = g i ( x k ) 是点x k 处的 梯度向量的第i 个分量，z 足一个指标集若任取k ，f z ，都有lg k ，ii ig z ，il ， 对至少一个i ( 1 ，扎) 成立，我们即称尸是由n 维梯度向量组成的过滤集 过滤集方法就是当试验点z 吉不次子相应过滤集中任意点时，就接受试验 点的方法实际计算中，当z 古非常接近于过滤集中的任一点时，我们也不打算 接受之，为此，【l l 】给出如下定义 定义1 3 3 【l l 】试验点z 老被过滤集厂接受，当且仅当v g t 厂，ji ( 1 ，n ) ，使 i 吼( z 吉) i i9 z ，ii 一l 9 1l l ， 其中( o ，击) 是一个正常数 我们称x + k 可被过滤集歹所接受( 实际上是夕可被厂所接受，其一t - g - ：= 夕( z 毒) ) ，当z 吉被其相应的过滤集厂接受时，我们将9 亭加入到厂中，并从中去 除所有满足i9 l ，ii ig k ，ti ，vi ( 1 ，n ) 的向量g l ，从而实现了过滤集的更 新 1 4 一种组合的非单调过滤集信赖域线搜索技术 根据上面的讨论，我们可以给出一种组合的非单调过滤集信赖域线搜索 技术我们先通过求解信赖域子问题( 1 2 1 ) 得到试探步s k ，它满足充分下降条 件 亿岛( z 七) 一”。( z 七，) 丁l il l 1 1g k1 18kg k m i n i ，z 南 m 岛( z 七) 一m ( z 七+) 7 ，l i | l i ，南i 和( 1 2 3 ) ，从而得到试探点z 毒= x k + 8 k 接下来判断试探点z 毒是否被接受 在这里，我们采用文献【2 0 】中的非单调信赖域技术，即计算 m 2 。蹋惫) 一j ， 其中 一j = f ( x k 一) ，r e ( o ) = 0 ，0 m ( 忌) m i n 【m ( 七一1 ) + 1 ，m ，七21 ，m 是 一6 一 第l 带过滤集f 等赖域线搜索方法 非负整数，则得比率 p k = ( f ( z z ( k ) ) 一，( z j ) ) ( m 惫( o ) 一m 惫( s 七) ) 通过p k 的值，我们来判断能否接受试探点z 去，并且在算法中以此来更新信赖 域半径a k 若p k 7 7 1 ，我们称之为充分下降的迭代，接受z 吉，令x k + l = z 毒；否 则，利用过滤集技术判断能台接受z 毒，若能接受到过滤集厂中，令z + 1 = z 去， 否则对步s 七采用后退线搜索方法，得到s g ，使得 ，( z + s g ) f ( x 惫) ， 其中s g = s 七，( o ，1 ) ，8 7 = s 南子序列s g 满足 s g + 1 l i e 川i is g i i , 0 l “ l ， 和 c o s ( ) c o s ( ) ， i = 0 ，1 ，2 令s 惫+ 1 = s 譬，由文献【7 】中的引理2 5 可知，由后退线搜索得到 的试探步8 七+ ，与信赖域方法中减小信赖域半径重新求解信赖域子问题得到 的8 k + l 是一致的，故也是满足条件( 1 2 2 ) 和( 1 2 3 ) 的 由此可以看出，在新方法中，当试探点不成功时，我们不是马上改变信赖域 半径重新求解信赖域子问题，而是采用了过滤集技术和线搜索方法，这样就增 大了试探点被接受的机率，减少了求解信赖域子问题的次数，从而降低了计算 量并且，在一定的条件下，我们能够证明此方法的全局收敛性，也可以得剑不 错的数值结果 1 5 新算法 综合上述各点，给出本文的算法如下： 算法1 5 ( 过滤集信赖域线搜索算法) 步0 取初始点x o 和初始信赖域半径a 0 ，常数( o ，而1 ) ，0 7 7 l 叩2 1 ，0 ，y 1 忱 1 怕，0 z k l ，k u f h 1 ，使得对所有k ， 厂( z ) 【七l ，七u 】，l iv z f ( x k ) | l k u f h 结合( 1 2 2 ) 和( 1 2 3 ) ，则存在一个正常数胁满足 和 毗) _ m 七( z k + s k ) 删n 高a 纸t - - # m i n 高a 同时，我们定义z 是满足p k r t 2 的指标七的集合由算法1 5 ，我们可得 ( 鼬一m m ) ) k e z 叼2 ( m 岛( z 七) 一m k ( z k + s 南) ) k e z ( 1 6 1 ) s + 岛 z ，j 一 砷 脚 南 mm 鼬 c 外 一 第l 孥过滤集信赖域线搜索方_ 上 令 m k2 1 + 1 m i a x kl i 凰l l ， ( 1 6 2 ) 1 i 由假定( a 1 ) - ( a 3 ) , - i 矢n ， 厂( z 七) ) 有界，故由( 1 6 1 ) 和( 1 6 2 ) 可得 e min卜瓦1k 0 ，使得a k k t b a 对所有的k 都成立 证明：见文献【1 】中定理6 4 3 的证明 口 由此引理可知。只要迭代点偏离一阶稳定点，则迭代半径就不会太小下 面我们从两方面来证明算法的收敛性首先证明算法产生有限次成功迭代时 的收敛性 定理1 6 1 设假定( a 1 ) ( a 3 ) 成立，信赖域子问题的解满足( 1 2 2 ) 和 ( 1 2 3 ) ，且在算法中成功迭代次数有限，即l s u 人厂i 1 ，x 4 = ：r k o + l = x k o + j ， 筇1 节过滤集f 二赖域线搜索办 ：上 有 p k o + j 1 ，都| j 1 ，礼) ，使得 i g k 。，j | - l g k ，j i 一i i 一， 故当f 充分大时，存在j t 1 ，礼) 有 夕觑，州一1 9 h “川 0 ，| | 鲰i i g ，v k ，则 存在，y 0 ，有 其中 证明：令 s 七| i 7 帆，k = 0 ，1 ，2 m k2 1 + m i a x | | h i lk n i ( 1 6 8 ) ，y ：1 1 1 i n o m t m 丁郇咱) ) ( 1 6 9 ) 下面用数学归纳法证明此引理成立 当1 1s 七l i 时，由s 南的最优性假设可知 9 k + h k 8 k = 0 ， 于是由0 3 1 1 ，有 i i s k 险涮= 南知袁( 1 6 1 0 ， 当| | s o | i = o 时，有i i8 0 | l = a o 7 ，故当k = 0 时，不等式( 1 6 8 ) 成 一1 2 一 第l 草过滤浆f 奇赖域线馊索力法 立假设不等式( 1 6 8 ) 对k 成立，下面证明不等式( 1 6 8 ) 对k + 1 成立 当| l8 惫+ 1i i - i is 七| | ，由归纳假设得七+ 1 7 慨由算法中的步4 知，我们只 需考虑七+ 1 3 1 a k ，7 2 a k 的情形若 由( 1 6 9 ) 有 s 圳罨， t 独啦7 1 1s k 罨引驯慨 所以，在剩下的证明中，可假设 又因为 故由算法可知m 叼2 ，即 虬 忪川 _ r e m i n l ( 1 6 1 6 ) 将( 1 6 1 6 ) 两边同时乘以( 1 一r 2 ) 加到( 1 6 1 5 ) ，结合| | s 七1 日岛| | 一8 t h k s k ， 可得 训1 2 i l 驯却一仇) 7 - e r a i n m 南一i is 刘 ( 1 6 1 7 ) 根据( 1 6 1 7 ) 可得| | 鼠ih l | ( 1 一叩2 ) 7 - e 或 ls 七肌f i e 成立，从而由 ( 1 6 9 ) 有 i i s 川仇l i m i n 丁( 1 7 7 2 ) ，】丢， 所以 a k + l2 ，y 1 忌，y 1j | s 七l | 7 1 综上可得，存在，y 0 ，有 成立 口 而2 向 疵 1，y，v s 七怆7 慨，k = 0 ，1 ，2 一1 4 笕1 节过滤集f 矗赖域线搜索方法 引理1 6 3 设 七) 和 m k ) 是任意两正数数列，且满足 七袁o ， 对所有的k 成立，其中 0 如果存在铂 1 ，0 7 2 1 ，以及 1 ，2 ，3 ) 的 一个子集z ，使得 七+ l 7 3 詹，i z ；( 1 6 1 8 ) 则必有 则 a k + a 7 2 七，i z ； m k + 1 m k ，v k ； 篆瓦1 。o ， 证明：见文献【2 1 】中引理1 3 1 5 的证明 口 下面我们来证明算法的伞局收敛性定理 定理1 6 3 设假定( a 1 ) ( a 3 ) 成立，且1 5 u i = + o 。，i a i o ，v k 由引理1 6 2 知，存在1 0 ，使得对充分大的尼，有 r 2 的指标k 的集合，则有( 1 6 1 8 ) ( 1 6 2 0 ) 成立 由 和( 1 6 3 ) 可得 故 从而，由引理1 6 3 知 这与已知中的 矛盾，所以假设不成立即得 惫袁 1 1 i m _ - = 0 ， k - - - - , o c ，k e 2 朋七 、1 笔瓦一 薹袁 l i r ai n fl ig ki l = 0 尤。 成立口 综合上述定理1 6 1 ，定理1 6 2 和定理1 6 3 ，我们得到这样的结论：算法 1 5 产生的点列或者达到一阶稳定点，或者至少有一个聚点为一阶稳定点 土地 腻 第2 孥数f 矗试验 第2 章数值试验 2 1 引言 本章中，我们主要利用一组中人规模的标准试验函数来检验算法1 5 ( 记作 f i l t e r n m n t r ) 试验环境为w i n d o w s x p 专业版下的m a t l a b 7 1 算法中的参数选 择如下： 3 1 = 0 0 6 2 5 ，1 2 = 0 2 5 ，3 3 = 2 ； 7 7 1 = 0 5 ，叩2 = 0 7 5 ，a o = 1 ， 1 = m m 0 0 0 1 , 疬】，k 0 2 9 5 , u _ 0 固 设定的终止准则是 | iv f ( z k ) 怪1 0 本文主要测试了e x t e n dr o s e n b r o c kf u n c t i o n ，p e n a l t y if u n c t i o n ，t r i g o n o m e t r i cf u n c t i o n ，v a r i a b l yd i m e n s i o n e df u n c t i o n ，e x r o s e n b r o c kp e n a l t yf u n c t i o n ，h e l i c a l v a l l e yf u n c t i o n 。b i g g se x p 6f u n c t i o n 和g a u s s i a nf u n c t i o n 这八个基本函数在这 里，我们记变量的维数为礼，非单调参数m ，在解点z + 处的函数值为f ，计算函 数值的次数为f ，计算梯度的次数为n g ，运行时间为c p u ( 单位为秒) ，记号 a ( b 1 表示数值a ，i c1 0 6 2 2 数值结果 首先，我们将本文的算法与基本信赖域算法( b t r ) ( 参见文献【l 】) 进行比 较数值结果见表2 1 第2 争数倩试验 表2 1 中大型问题的数值结果 f i l t e r n m n t rb t r p r o b l e m s nm ( n f n g c p u f )( n f n g c p u f ) 3 3 0 3 0 3 1 ( 一2 ) 1 3 ( 一2 0 ) 1 0 05 2 6 2 6 1 6 ( 一2 ) 1 3 ( 一1 7 )4 2 2 0 2 0 ( 2 ) e x t e n d1 0 2 1 2 0 1 6 ( 一2 ) 2 o ( - 1 2 ) r o s e n b r o c k3 2 8 2 8 4 3 ( 0 ) 4 4 ( 一17 ) 2 0 0 01 5 2 5 2 5 4 1 ( 0 ) 2 2 ( 一18 )4 1 2 3 6 ( 一1 ) 4 0 ( 3 ) 5 0 0 03 3 0 3 0 3 3 ( 1 ) 6 6 ( 一1 5 )4 3 2 1 5 ( 0 ) 1 0 ( 3 ) 1 0 01 0 3 3 3 3 1 6 ( - 2 ) 9 0 ( 一4 )5 5 4 5 3 1 ( 一2 ) 1 9 0 ( 一4 ) 5 0 01 0 3 3 3 3 4 5 ( 一1 ) 4 8 ( 一3 )4 4 4 0 5 9 ( 1 ) 4 8 ( - 3 ) p e n a l t y l 1 0 0 01 0 3 5 3 5 2 1 ( 0 ) 9 7 ( 一3 )4 5 3 9 2 6 ( 0 ) 1 9 7 ( 一3 ) 2 0 0 0l o 3 6 3 5 9 0 ( 0 ) 2 0 ( 一2 )3 9 3 7 9 6 ( 0 ) 2 0 ( 一2 ) 2 0 01 0 4 2 4 2 3 4 ( - 1 ) 8 8 ( 一1 4 )4 1 2 6 1 7 ( 一1 ) 4 9 ( 一6 ) t r i g o n o m e t r i c 5 0 01 0 5 4 5 4 2 9 ( 0 ) 1 7 ( 一1 6 )4 5 3 3 1 6 ( 0 ) 9 o ( 一7 ) 1 0 0 01 0 6 2 6 2 1 5 ( 1 ) 4 1 ( 一1 8 )5 2 3 3 7 5 ( 0 ) 1 1 ( - 6 ) 1 0 01 0 2 8 2 8 1 6 ( 一2 ) 5 0 ( 一2 0 )2 8 2 8 1 6 ( - 2 ) 5 0 ( 2 0 ) v a r i a b l y 5 0 01 0 3 7 3 7 4 7 ( 1 ) 2 2 ( - 11 )3 7 3 6 4 7 ( 一1 ) 2 2 ( 一11 ) d i m e n s i o n e d1 0 0 01 0 4 1 4 0 2 3 ( 0 ) 7 3 ( 1 4 )4 1 4 0 2 3 ( 0 ) 7 3 ( 一1 4 ) 1 0 0 1 5 3 1 3 1 0 1 4 0 ( 2 )3 2 0 4 0 ( 2 ) e x r o s e n5 0 01 5 4 4 1 3 ( 1 ) 2 0 ( 3 )3 4 3 2 2 ( 一1 ) 2 0 ( 3 ) b r o c k p e n a l t y 1 0 0 01 5 4 4 5 o ( 一1 ) 4 1 ( 3 ) 3 6 3 9 7 ( 一1 ) 3 9 ( 3 ) 1 0 05 2 2 1 2 2 0 4 9 f 一2 4 )1 7 1 1 4 0 1 2 ( 一18 ) h e l i c a lv a l l e y5 0 05 2 2 2 2 1 6 ( 一2 ) 4 9 ( 一2 4 )1 7 1 4 0 1 1 2 ( 一1 8 ) 1 0 0 05 2 2 2 2 1 6 ( 一2 ) 4 9 ( 2 4 )1 7 1 4 1 6 ( 一2 ) 1 2 ( 一18 ) 1 0 0 3 5 3 5 2 6 3 ( 一2 ) 2 2 ( 0 )3 6 9 2 4 7 1 1 ( 一1 ) 2 4 ( 一1 ) b i g g se x p 6 5 0 03 5 3 5 2 7 8 ( 一2 ) 1 2 2 ( 0 )3 6 9 2 4 7 1 1 ( 一1 ) 2 4 ( 一1 ) 1 0 0 0 3 5 3 5 2 1 1 ( 一1 ) 2 2 ( 0 ) 3 6 9 2 4 7 1 3 ( - 1 ) 2 4 ( 一1 ) 1 0 03 1 0 7 1 0 6 1 3 ( 1 ) 1 2 ( 1 6 )8 7 1 6 ( 一2 ) 1 1 1 ( 一8 ) g a u s s i a n5 0 03 1 0 7 1 0 6 1 6 ( 一1 ) 1 2 ( 1 6 )8 7 1 6 ( 一2 ) 1 1 1 ( 一8 ) 1 0 0 03 1 0 7 1 0 6 1 4 ( 1 ) 1 2 ( 1 6 )8 7 1 6 ( 一2 ) 1 1 ( 一8 ) 对于e x t e n dr o s e n b r o c kf u n c t i o n ，由于m 的值对本文算法的影响较人，故 取几个不i 一的m 值进行测试；而对于其它的测试函数，m 的取值对其数值结 第2 审数值试验 果影响不大，故只取其中一个m 值 通过表2 1 中的数值结果，我们可以看出，对于e x t e n dr o s e n b r o c k 问题， b t r 算法失效，而本文的算法是成功，并且取得了较好的数值结果对于 p e n a l t y i 问题，本文的算法( f i l t e r n m n t r ) 在函数值计算次数，梯度计算次数和 计算耗时上都少于b t r 算法对于t r i g o n o m e t r i c 和h e l i c a lv a l l e y 问题，本文的 算法虽然在迭代次数上略多于b t r 算法的迭代次数，但得到了更小的函数值 对于v a r i a b l yd i m e n s i o n e d 问题，f i l t e r n m n t r 算法中的过滤技巧和线搜索技术 都没有发挥作j j ，实际计算表现和b t r 算法几乎是一致的对于e x r o s e n b r o c k p e n a l t y 问题，这两种算法给出了几乎相同的函数值，但本文算法在迭代次数 和c p u 时间方而明显优于b t r 算法对于b i g g se x p 6 问题的执行效果不是 很好。虽然迭代次数明显少于b t r 算法的，但是没有达到理想的最小值对于 g a u s s i a n 问题，本文的算法失效 同时，我们又将本文算法与非单调的信赖域算法( n m n t r ) ( 见文献【2 0 】) 进 行了比较数值结果见表2 2 通过表中的数据我们可以看出，本文算法相对于 n m n t r 算法也取得了一定成效 表2 2 f i l t e r n m n t r 与n m n t r 的数值结果 f i l t e r n m n t rn m n t r p r o b l e m s 佗m0 n f j n g c p u 7f 、)i 、n f n g | c p u f 、 3 3 0 3 0 3 1 ( 一2 ) 1 3 ( 一2 0 )4 3 5 2 ( 一2 ) 2 0 ( 2 ) 1 0 05 2 6 2 6 1 6 ( 一2 ) 1 3 ( 17 )4 5 7 0 2 0 ( 2 ) e x t e n d r o s e n b r o c k 3 2 8 2 8 4 3 ( 0 ) 4 4 ( - 17 )4 6 5 7 0 ( 一1 ) 4 0 ( 3 ) 2 0 0 01 5 2 5 2 5 4 1 ( 0 ) 2 2 f 一18 )5 3 1 7 2 0 ( 0 ) 4 0 ( 3 ) 5 0 0 03 3 0 3 0 3 3 ( 1 ) 6 6 ( 一15 ) 4 5 5 4 3 ( 0 ) 10 ( 3 ) 5 0 05 3 3 3 3 5 - 3 ( 一1 ) 4 8 ( 3 ) 3 1 3 1 3 3 ( 一1 ) 4 8 ( 3 ) p e n a l t y l 1 0 0 05 3 5 3 5 1 7 ( 0 ) 9 7 ( 一3 )3 8 3 5 1 6 ( 0 ) 9 7 ( - 3 ) 2 0 0 05 3 6 1 3 5 9 3 ( 0 ) 2 0 ( 一2 )3 9 3 7 9 7 ( 0 ) 2 0 ( 一2 ) 2 0 01 0 4 2 4 2 3 4 ( 一1 ) 8 8 ( 一1 4 )5 6 5 3 3 3 ( 一1 ) 9 6 ( 12 ) t r i g o n o m e t r i c 5 0 01 0 5 4 5 4 2 9 ( 0 ) 1 7 ( 一1 6 )4 2 3 7 1 8 ( 0 ) 1 1 2 ( - 1 2 ) 1 0 0 01 0 6 2 6 2 1 5 ( 1 ) 4 1 ( 一1 8 )5 7 4 8 9 6 ( 0 ) 3 6 ( - 16 ) 5 0 05 2 2 2 2 1 6 ( 一2 ) 4 9 ( 一2 4 ) 2 5 19 0 1 5 ( - 2 0 ) h e l i c a lv a l l e y1 0 0 05 2 2 2 2 1 6 ( 一2 ) 4 9 ( 2 4 ) 2 5 19 1 6 ( 一2 ) 1 5 ( 2 0 ) 最后，我们将本文算j 玄与过滤集信赖域算法( f i l t e r t r ) ( 见文献 1 7 】) 相比较 第2 章数值试验 数值结果见表2 3 通过表中数据，我j f f n - q - 以看出本文算法相比过滤集信赖域算 法也取得了很好的效果 表2 3 f i l t e r n m n t r 与f i l t e r t r 的数值结果 f i l t e r n m n t rf i l t e r t r p r o b l e m s nm( 、n f n g f c p u f 、 ( 、n f | n g c p u f 、 1 0 01 0 2 1 1 2 0 1 6 ( - 2 ) 2 o ( 一1 2 )3 0 2 9 1 6 ( - 2 ) 3 8 ( - 11 ) e x t e n d r o s e n b r o c k2 0 0 0 1 5 2 5 2 5 4 1 ( 0 ) 2 2 ( 一18 )3 0 5 3 0 5 3 9 ( 1 ) 3 2 ( 一1 4 ) 5 0 0l o 3 3 3 3 4 5 ( 一1 ) 4 8 ( 一3 )3 5 3 5 5 3 ( 1 ) 4 8 ( 一3 ) p e n a l t y i 1 0 0 01 0 3 5 3 5 2 1 ( 0 ) 9 7 ( 一3 )3 7 3 6 2 2 ( 0 ) 9 7 ( - 3 ) 5