（计算数学专业论文）解无约束优化问题的非单调修改的bfgs方法.pdf

摘要 对于一般的无约束优化问题，拟牛顿法是一种非常有效的方法丽魄的修 正对算法的收敛性和收敛速度起着重要的作用，b f g s 方法的一个重要性质是自 我纠正功能f 1 9 ，由f 5 】中的分析可知，b f g s 方法纠正小特征值的效果比较好， 为了能更好的纠正大特征值问题，a i p i n g l i a o 在文【a 7 中给出了一种b f g s l 算法。袁亚湘在文【2 6 】中也给出了一种b f g s 7 算法，把拟牛顿方程看作为二次 模型的梯度值满足插值条件，b f g 妒算法要求函数值满足插值条件，从而得出 额的修正反的公式，该算法具有全局收敛性和局部超线性收敛性。 本文将文f 1 7 1 中给出的b f g s 算法，与当前流行的非单调技术相结合，给 出了求解无约束问题的带不精确线搜索的非单调b f g s 算法；又将文【2 6 】中的 b f g s r 算法与不精确线搜索和非单调技术相结合，给出了求解无约束阀题的带 不精确线搜索的非单调b f g s ”算法，文中给出了新算法的全局收敛性，数值实 验表明了i 幺算法的有效性。 关键词：无约束优化，非单调线搜索，修改的b f g s 算法 a b s t r a c t q u a s i n e w t o nm e t h o di sak i n do fe f f i c i e n tm e t h o d st os o l v em eg e n e r a l u 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 eu p d a t eo fb ki si m p o r t a n tf o r t h ec o n v e r g e n c e o fa l g o r i t h m s o n e p r o p e r t y o f t h e b f g s m e t h o d i s i t s s e l f - c o n e c t i n g m e c h a i l i s m 【1 9 1 w i t h i n t h ef r a m e w o r ko fb y r da n dn o c e d a l t h e s l ，b f g sm e t h o di sb e t t e ra tc o r r e c t i n g s m a l le i g e n v a l u e st h a nl a r g e 豁t of i n dam e t h o dw i t hb e t t e ra b i l i 哆t oc o r t e c t l a r g ee i g e n v a l u e s ，a i p i n gl i a op r o p o s e dab f g s m e t h o d 【1 7 y u a n 2 6 】p r o - p o s e d ab f g 铲a l g o r i t h m i n w h i c h q u a s i - n e w t o n c o n d i t i o n c a n b e i n t e r p r e t e d a st h e i n t e r p o l a t i o nc o n d i t i o nt h a tt h eg r a d i e n t v a l u eo ft h el o c a l q u a d r a t i cm o d e l m a t c h e st h a to ft h eo b j e c t i v ef u n c t i o na tt h ep r e v i o u si t e r a t e t h eb f g s a l g o - r i t h m r e q u i m s t h a t t h e f u n c t i o n v a l u e o f t h e l o c a l q u a d r a t i c m o d e l m a t c h e s t h a t o f t h eo b j e c t i v ef u n c t i o na tt h ep r e v i o u si t e r a t e t h i sa l g o r i t h mp r e s f v e st h eg l o b a l a n dl o c a ls u p e r l l n e a rc o n v e r g e n c ep r o p e r t i e so ft h eb f g s a l g o t i i nt h i sw o r k , w ec o m b i n et h eb f g s a l g o r i t h m 【1 7 1w i t ht h ep o p u l a rn o n - m o n o t o n et e c h n i q u e w ea l s oc o m b i n et h eb f g s 7a l g o r i t h m 【1 7 w i t ht h ei n - e x a c tl i n es e a r c ha n dt h en o n m o n o t o n et e c h n i q u e n u m e r i c a lr e s u l t st oc o m - p a r et h eb e h a v i o ro ft h i sm e t h o d sw i t hm o d i f i e dt h eb f g sa l g o r i t h m sa 坨p r e - s e n t e d t h e s er e s u l t si n d i c a t et h a tt h en o n m o n o t o n eb f g s a l g o r i t h m , t h en 彻? m o n o t o n eb f g s yi se f f i c i e n t 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 ，n o n l n o n o t o n el i n es e a r c h , m o d i - f l e db f g s a l g o r i t h m v 学位论文独创性声明 本人郑重声明： 1 、墼持以。求实，创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 ，本论文中除引文和致谢的内容外，不包含其他人或其它机构已经发表或撰 写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示了谢意。 作者签名： 日 期： 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版；有权将学 位沦文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅；有权将学 位论文的内容编入有关数据库进行检索；有权将学位论文的标题和摘要汇编出 版。保密的学位论文在解密后适用本规定。 作者签名： 只期； 致谢 首先，缀荣幸有这样的机会来感澍我的导师孙文瑜教授。谢谢他在我的研究 及论文写作方面给予的重要指导，同时也感谢他在其他方面给我的巨大帮助。我 的毕业论文能够顺利地完成完全离不开孙老师的认真阅读及其给予的宝贵的指导 意见。再次向孙老师表示衷心的感谢! 其次，我要感谢在研究生阶段为我们授课的老师：陈金如教授、谢四清教授， 颜世建教授、王雨顺副教授、魏红副教授等，在他们的谆谆教导下，我打下了进 一步学习和研究的基础。同时我要感谢朱诚、朱安友，徐倩等老师，感谢他们给 予我的关心和帮助 在学习的过程中，我还得到了师兄弟姐妹以及众多同学的关心和帮助在这个 充满友爱的集体里，使我得以轻松愉快的学习和工作谢谢我的同学，我的朋友! 借此机会我要感谢我的亲属，谢谢他们对我学业的支持。 最后，祝愿所有关心，支持和帮助过我的人身体健康，工作顺利! 江苏南京 2 0 0 7 年3 n 朱琴 本文的创新点 本文考虑求解一般的无约束优化问题，从有效节省计算量和提高解的精度的 角度考虑，将文【1 7 】中的b f g s 算法，与当i i i 流行的非单调技术相结合，给出 了求解无约束问题的带线搜索的j 单调b f g s l 算法。将文【2 6 l 中的b f g s v 算 法与不精确线搜索和非单调技术相结合，给出了求解无约束问题的带不精确线搜 索的非举调b f g , 9 7 算法。文中给出了新算法的全局收敛性的证明，并进行了数 值实验，数值实验结果表明我的算法是有效的。 第1 章引言 最优化是一门应用性很强的学科，最优化问题的一般形式可表达成 r a i n f ( x ) s t q ( j ) = 0 ，i z c i ( f ) 0 z 其中，c l 都是变量z 的数量函数， i z l = m l ，并记m = 仉+ 佻。 ( 1 1 ) ，z 是指标集，的模吲= m 。，z 的模 根据( 1 1 ) 中函数的具体性质和复杂程度，最优化问题又有许多不同的类 型。根据是否有约束函数分为无约束最优化和约柬最优化；根据决策变量z 的取 值是离教的还是连续的分为离散晟优化和连续最优化；连续晟优化里又根据函数 的可微性分为光滑最优化和非光滑最优化；本文中，我们主要考虑无约束最优 化，并假定，是二次连续可微的。 1 1 解最优化问题的基本方法 本文主要讨论无约束优化问题 。r a p i n m ) ( 1 2 ) 迭代法是解非线性优化问题的基本方法。其中线搜索方法又是个很重要的策 略。 在线搜索策略中，在每步迭代点f 处，算法需要确定一个搜索方法比和沿 此方向的搜索步长o k ，从丽迭代过程就可以表达成2 “i = z + o t k 颤。 一般来说，线搜索算法要求也是一个t i 蜂：z ri , jt 即耀v 0 ，从而产生下一个迭代点 - r k + l = 取+ o r k 矗( 2 5 ) 我们采用如下公式修正反+ l b k + 1 = 取一最鬻+ 磋； 其中 如= a k d k ，弧= v f ( x k + 8 k ) 一v f ( x k )( 2 7 ) 令= e - l 胪 如果 币磊s r b i k s 瓦靠， 则 ( 咖) - ( 煮，磊磬磊) ( 2 8 ) 如果 煮纸 剐 ( 以，讥) = ( 靠，1 ) ， ( 2 9 ) 这是对传统的b f g s 算法加以修改的算法，该算法对凸函数具有全局收敛 性，并有超线性收敛性。 我们用文【? 】e e 介绍的非单调线搜索技术来汁算沿方向d k 的搜索步长。女。 下晒我们介绍一下这个方法： 第2 章解无约束优化问题的非单调b f g s 算法 6 算法1 ：非单调线搜索算法( n l s ) 步0 g g k ，g l , ，d k ，盯( 0 1 ) ，了( 0 ，1 ) ，正整数m 0 ，m ( o ) = 0 ，m ( k ) 一 m i n m ( k 一1 ) + 1 ，j l 彳 ，( z ( 1 ( 科) = m a x o j 。( 舢【，( z 一) 1 步1 置口= 1 步2 计算厶= f ( x k + a d k ) 如果厶5 ，( z ( 1 ( 女) ) + 7 口靠出，则 置n t = n ，并停机；+ 否则 转步3 结束( 如果) 步3 置o ；仃q ，转步2 注意到，m ( ) 是每次迭代中确定，( 霉( f 忙) ) 时需要考虑的以前的迭代点数。着 假定对所有的外迭代km ( 动是一致有上界的，别有如下的定理。 定理2 1 ：设z 是由所生成的序列，并假定： ( i ) 存在与k 无关的正常数c l ，饧使得 蠢d ks c 1 i i g 女l | 2 ，d ksc 2 1 1 9 k l i ( i i ) 步长口由算法n l s 确定 则下面结论成立： ( a ) 序列 。k 保持在水平集内，且每个极限点i 都满足g ( 牙) = o ； ( b ) 。女 的每个极限点都不是，的局部极大值点； ( c ) 若r 在内的稳定点数是有限的，则序列 瓢 收敛 证明；见【? 】 一 我们把上面的非单调技术和前面给出的b f g s l 算法相结合，得出我们的非 单调b f g 铲算法： 第2 章解无约束优化问题的非单调b f g s 算法 7 算法2 ：( 菲单调b f g s l 算法) ( n b f g s 。) 步0 给定初始条件z l 舻，b 1 对称币定，0 0 若如 0 ，所以x t b k + 1 茹 0 ； 若矗= 1 则饥g 筹 0 ，所以x t b k + 1 z o 引理2 2 ：在假设b 的条件下，我们有 m 忙t i l 2 _ 0 ( 2 1 6 ) j = l 注意到对任意的t 0 ，总有h 7 ( ) = t i n t 1 ，因此， 1 一t + i n t 0 t 0 ， 我们估计h e s s i a n 逼近阵风+ 1 的迹： ( 2 1 7 ) 纵b ) - f 假m 糕+ 仉铿 9 一彘+ 蹉唧 5 l 理2 4 ：举用n b f “5 。甲的公式计畀执+ 1 ，君b k 走正是的，刖 她( b k + 1 ) d c 2 【酬蒜) 证明； 两次运用s h e r m a n m o r r i s o n w o o d b u r y 准则，我们有 如t ( 玩+ - ) = d e t ( b t ) ( 1 一以+ ( 1 一以) 警 碱鑫) 如( 段) ( 1 一如+ 知s t 焦b 女s k ) 币蕊s b 疆k s k 磊 蕊s r v k b k s k + 最瓠” 1 一以+ 饥盘 由( 2 2 0 ) 和( 2 2 2 1 ) 知引理成立 叫，+ 盎) = 彘警 s v k 。s t b , s k f 2 2 1 ) ( 2 2 2 ) 一 定理2 2 ：如果函数f 满足假设条件，则对讹 1 ，下列关系式时至少 j 【1 ，k 】中的个值成立 证明： 啦独m s 毋鲰呸掣忱 她+ 1 ) 矧驴募+ 必s t y k 地袭+ f n 瓠 圳+ 糕一1 岫磊s r v k f 碱 + l n c o s 2 0 k + 1 - 盖+ j ”旒 州蝴2 以+ 1 一旒“”丽6 q k ) 第2 章解无约束优化问题的非单调b f g s l 算法 1 l + e ，( i n c o s 2 岛“一器“n 貉) ) j = l 7 。 定义协0 轳_ f 一 【1 蔬“n 蔬】| ( 2 2 4 ) 以下是对1 5 1 冲定理( 2 1 ) 的推广( 1 膏) 女珊 0 ，使得 对v k 0 ，不等式c d s 岛p ，8 岛is j i i 对至少j f 1 ，k 】中至少睛嘲个 值成立。那么“一矿；而且墨l0 z 一r | | 。c ，存在常数0 r 1 使得对 v 七， + l 一 s k ：【，1 一工j 成立 证明：见【5 】 定理2 - 4 ； 如果函数，满足假设条件，则对任惠的。1 对称正定矩阵b l ，非 单调b f ( j s 得出的序列 执 收敛到最优解r 。，而且芒l i i z t 一矿0 o 。，存 在常数0 r 0 从而产生下一个选代点 z k + 12 x k + o k d k 我们采用如下公式修正b k + l 其中 s k + 1 凤一警i “装y ks i 石k 8 七s i 乱= o ：k d k ，弧= v f ( x k + 8 k ) 一v ，( 。) ( 3 4 ) ( 3 5 ) ( 3 6 ) 岱7 “2 纛i f ( z ) 一m 州) + 8 ：v ，( ) 】 ( 3 _ 8 ) 这是对传统的b f g s 算法加以修改的算法，该算法对凸函数具有全局收敛性，并 有局部q - 超线性收敛性 我们把非单调技术与不精确线搜索方法和前面给出的b f g s 算法相结合， 得出我们的非单调b f g s 7 算法： 。 算法3 ：( 非单调b f g s r 算法) ( n b f g s 7 ) 步0 给定仞始条件z l 胛，b 1 对称正定，0 u o ，则由n b f g s 7 算法定义的凤+ 1 也是正定的 证明： 由c a u c h y s c h w a r t z 不等式我们得到 ( 8 t 8 ) 2 s t b s ，8 z 第3 章解无约束优化问题的非单调b f g s 算法 当且仅当s 与z 共线时，等号成立， 对比0 ，有 = ，船一可( z r b 石k s d 2 “髻 x t b = z - - x t b k x + t k ( z ，r f y k ) 2 8 i 弧 ：“g 蟛 o 5 ；y k ( 3 1 2 ) 推论3 2 ：m ，以仙饥1 由算法n b f g s y 给出，且对，2 r ，l ，z r g ( x ) z 0 ，刘b k + l 是正定的 引理3 3 ：在假设a ，b ，c 的条件下，算法n b f g s r 产生一个无穷序列 丁k ) ，则 翔鲰1 1 2 ( 一g t d * ，2 0 ，使得 。 j m s a 。x ( 纠f 一j | - m l , 7 1 t g k l l 2 v 七 证明：令k 1 = k a k = 1 ) ，k 2 = k l n k 1 ) 以下我们分类讨论： 如果k k 1 ，则由( 3 9 ) 和( 3 1 4 ) 得 ( 3 1 5 ) 岣m a 。x ( ”限一j 一 + - 一口簖噍+ j 礤尻如】 = 一i o 纨t 呶 南。船暇v ke 以 ( 3 1 6 ) 第3 章解无约束优化问题的非单调b f g s 算法 1 8 如果配，由于口i 1 ，剐n p 一1 1 ，芦，俨 令n = 鲰孑一，我们可以推 出( 3 9 ) 不成立，即 。g i n & 们x 【 - j 】一，( z 七+ 。声一1 也) 一( 1 一；n 扩1 ) 靠也一菇如 = 一( 1 - - o + 互1 慨菇如， n 一坐掣豁 掣c 一器a k i 工， 文 a k l ，搬鲍 ( 3 1 9 ) 第3 章解无约束优化问题的非单调b f g s 算法1 9 由( 3 9 ) ( 3 1 4 ) ( 3 1 9 ) 知，对v k 2 ，戎们有 所以 。黑埘【 一】一a + l 一盯n g i r l , + a t b * 也】 2 一盯? 1 a x ( 1 簖以+ 去n 艮d k l o i ( d 1 = 一口o ：【9 手d + 妻a ：耀b k d ； 一一n ： 1 一：。麓靠岳 一矿【1 一互1j 鲰t 以 笔( 一薪) 2 掣# 洲，v k 屹 蟛m ，m ( a x 砷帆一j l - + 1 呜铲2 ，v 女扔 由( 3 1 6 ) ( 3 2 0 ) ，令 ，= 南厕”( 1 ，m f l a ( 1 _ - 一a ) )7 ，。而”( 1 ，广) 从而。匀m s p 。, x ；( 埘f 一，1 一 + l q l l g k l l 2 ( 3 2 0 j 定理3 2 ： 如果函数f 满足假设条件，则对任意的z 1 对称正定矩阵韪，非单 调b f g s 。得出的序列( f t ) 收敛到最优解以，而且墨。“札一z 0 , 3 0 ，存在常 数0 sr 1 使得对讹， + 1 一 s l , q 一，】成立 证明： 由定理( 2 1 ) ，定理( 3 1 ) 可得 3 4 数值结果和结论 我们采用【1 8 】中的1 8 个测试函数，对b f g s y 算法，及新给出的非单调 8 f g s 7 算法进行测试，募法参数选挎如下：c l = 0 1 ，白= 0 9 m = 1 0 ，设定的 第3 章解无约束优化问题的非单调b f g s o 算法 终止准则是v f ( x k ) 1 0 实验结果见表【3 1 】，在表中我们记变量的维数为n ， 在解点r 处的函数值为，算法迭代的次数为n ，从结果上看，我们的新算法有 效地减少了迭代步数，廷高了解的精度。时一些问题的求解更加有效 第3 章解无约束优化问题的非单调b f g s 算i 去 2 1 b f g s y口f g s y p r o b l e m s n 2 ，r h| h e l i c a iv a l l e y 23 13 0 2 3 0 e m 2 02 76 3 3 7 7 e _ 0 2 1 b i g g se x p 6 64 00 0 0 5 74 70 0 0 5 7 c , a u s s i a n 3 5 1 1 2 7 9 0 0 851 1 2 7 9 e 0 0 8 p o w e l lb a d l ys c a l e d21 4 86 5 2 1 & 如2 71 8 92 0 6 8 5 枷2 8 b o xt h r e e - d i m e n s i o n a l 31 25 4 6 6 6 e - 0 2 11 11 ，2 1 3 3 e 0 2 0 v a r i a b l yd i m e n s i e n e d 61 42 1 3 2 1 e _ 0 2 11 42 1 3 2 1 e 0 2 1 v a r i a b l yd i m e n s i o n e d 6 03 33 s 7 6 3 鲫2 3o v e r f l o wo v e r f l o w v a r i a b l yd i m e n s i o n e d 1 8 05 44 4 3 0 e - 0 2 1o v e r f l o wo v e r f l o w w a t s o n63 6o 0 0 2 33 6o 0 0 2 3 w h t s o n 1 2 7 92 6 6 4 2 e - 0 0 9 1 0 81 3 9 3 5 e _ o w a t s o n3 01 0 41 0 4 1 1 e 0 1 11 0 11 0 4 1 4 e - 0 1 1 p e n a l t v22 1 48 3 5 疆b 0 0 6o v e r f l o wo v e r f l o w p e n a l t yf u n t i e ni i 21 28 0 6 6 4 e - 0 0 71 28 0 6 6 4 e - 0 0 7 b r o w n b a d l ys c a l e d 21 40 1 3 o b r o w na n dd e n n i sl1 51 5 伽吼 0 2 6 2 0 5 5 0 5 4 e - 0 2 2 g u l fr e s e a r c ha n dd e v e l o p m e n t 3 3 6 3 8 9 9 0 0 2 03 7 4 ，8 0 1l e - 0 2 0 t r i g o n o m e t r i c 1 02 92 7 9 5 1 e 0 0 52 92 7 9 5 1 e 枷5 t r i g o n o m e t r i c 6 06 72 4 3 9 8 e - 0 0 6o v e r f l o wo v e r f l o w e x t e n d e dr o s e n b r c c k 1 09 52 2 2 0 7 e - 0 2 01 3 31 2 7 6 0 e 0 2 0 e x t e n d e dr o s o n b r o c k 2 01 6 41 7 2 4 5 e - 0 2 22 3 71 4 2 1 4 e - 0 1 9 e x t e n d e dr o s e n b r o c k3 02 0 46 3 0 9 2 e 0 1 82 7 24 3 6 5 7 e 0 1 7 e x t e n d e dr o s e n b r o c k4 02 4 64 7 9 9 8 e - 0 1 73 2 22 2 0 9 2 e 0 1 7 e x t e n d e dr o s e n b r o c k5 02 7 95 1 5 2 1 种1 7 3 8 02 4 8 1 皓0 1 7 e x t e n d e dr o s e n b r o c k6 0 3 1 34 ，9 2 9 1 e - 0 1 74 1 94 2 船7 e - 0 1 7 e x t e n d e dr o s e n b r o c k1 0 04 3 364 6 ”每0 1 7 6 5 11 7 9 9 1 印1 7 e x t e n d e dp o w e l ls i n g u l a r 4 4 3 3 8 7 7 5 e - 0 1 35 13 3 2 7 6 e 0 1 6 e x t e n d e dp o w e l ls i n g u l a r6 0垃91 9 6 7 r 6 e - 0 1 2o v e r f l o wo v e r f l o w b e a l e21 62 4 0 6 1 e - 0 2 11 66 0 9 6 5 咖2 3 w o o d45 41 u 5 4 0 咖2 19 61 4 3 6 2 e - 0 2 0 c h e b y q u a d 92 53 8 4 5 7 枷1 93 41 8 0 6 5 e - 0 1 7 c h e b y q u a d 1 03 5 n o d e 石 4 6o 6 5 c h e b y q u a d 2 0 5 1 0 0 0 4 66 7o j o d 4 6 袁3 1 ：数值结果 参考文献 【1 1 袁亚湘，孙文瑜最优化理论与方法科学出版社，北京，1 9 9 7 【2 】m a v r i e l ，n o l i n e a rp r o g r a m m i n g ：a n a l y s i sa n dm e t h o d s ，p r e n t i c e - h a l l , i n c ，e n g l e w o o ac l i f f s ，n e wj e r s e 弦1 9 7 6 【3 jk wb r o d l i e ，a na s s e s s m e n to ft w oa p f r o a c h e st ov a r i a b l em e t r i cm e t h o d s , m a t h ，p r o g ，v 1 2 ( 1 9 7 7 ) ，p p 3 4 4 - 3 5 5 1 4 】c g b r o y d e n ，c l a s so f 酗地q d s f o rs o l v i n gn o n l i n e a rs i m u l t a n e o u s e q u a t i o n s ，m a t h , c o m p ，1 9 ( 1 9 6 5 ) ，p p 5 7 7 - 5 9 3 【5 】r h b y r da n dj n o c e d a l ，at o o lf o rt h ea n a l y s i so fq u a s i - n e w t o nm e t h o d s w i t ha p p l i c a t i o nt ou n c o n s t r a i n e d 蚴t i o n , s i a mj n u m e r a n a l 2 6 ， 7 2 77 3 9 ( 1 9 8 9 ) 【6 】x c a ia n dw s u n , an o n m o n o t o n el i n es e a r c ha l g o r i t h mf o rn o n s m o o t hd 讳 c r e t em l n i _ q m xp r o b l e m - j o u r n a lo fn a n j i n gn o r m a lu n i v e r s i t y ( n a t u r a ls c i e n c e ) 2 6 ( 4 ) ：1 6 - 2 1 ，2 0 0 3 f 7 】w ：c d a v i d o n , v a r i a b l em e t r i cm e t h o df o rm i n i m i z a t i o n , r e p a n l 一5 9 9 0 r e p a r g o n n en a t i o n a ll a b o r a t o r i e s , a r g o n n e ，i i i ，1 9 5 9 【8 】，e d e n n i s , j ra n dj ，m o r ：q u a s i n e w t o nm e t h o d s ，m o t i v a t i o na n d t h e o r y , s i a mr e v i e w , 1 9 ( 1 9 7 7 ) ，n o 1 ，p p 4 6 - 8 9 【9 】r f l e t c h e r , m ，j d p o w d lo nt h em o d i f i c a t i o no fl d i , tf a c t o r i z a t i o n , m a t h , c o m p ，v 2 8 ( 1 9 7 4 ) ，p p 1 0 6 7 - 1 0 8 7 ， 1 1 0 】j f ua n dw s u n , n o n m o n o t o n ea d a p t i v et r u s tr e g i o nm e t h o df 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 a p p l i e dm a t h e m a t i c sa n d c o m p u t a t i o n , 1 6 3 ：4 8 9 - 5 0 4 , 2 0 0 5 【1 1 】f l e t c h e r , rp r a c t i o n a lm e t h o d so fo p t i m i z a t i o n , u n c o n s t r a n i n e do p t i m i z a - l i o n , j o h nw i l e ya n ds o n s ，n e wy o r ka n dt o r o n t o ，v o l1 参考文献2 3 【1 2 l g r i p p o ，f l a m p a r i e l l o ，a n ds l u c i d i an 帆m o t o n el i n es e a r c ht e c h - n i q u ef o rn e w t o nm e t h o d s i a mj o u r n a lo nn u m e r i c a la n a l y s i s , 2 3 ：7 0 7 - 7 1 6 ，1 9 8 6 【1 3 1l g n p p o , el a m p a r i e l l o , a n ds l u d d i at r u n c a t e dn e w t o nm e t h o dw i t h n o r u l l o n o t o n el i n es e a r c hf 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 i o u r n a lo fo p t i - m i z a t i o nt h e o r ya n da p p l i c a t i o n s ，6 0 ：4 0 1 4 1 9 ，1 9 8 9 1 1 4 】l g r i p p o , el a m p a r i e l l o , a n ds l u d d i aq u a s i - d i r e c t i v en e w t o na l g o r i t h mw i t han o n m o n o t o n es t a b i l i z a t i o nt e c h n i q u e j o u r n a lo f o p t i m i z a t i o n t h e o wa n da p p l i c a t i o n s ，6 4 ：4 9 5 - 5 1 0 ，1 9 9 0 【1 5 1l g r p p o , el a m p a r i e l l o , a n ds l u c i d la c l a s so fn o n m o n o t o n es t a b i l i z a - t i o n m e t h o d s i n u n c o n s t r a i n e d o p t i m i z a t i o n n “帕撕砌p m 蒯切朋f 比5 9 ：7 7 9 - - 8 0 5 ，1 9 9 1 【1 6 】ee g i l l , wm u r r a y , q u a s i n e w t o nm 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 f i o n , ，i n s tm a t h sa p p l i e s , 9 ( 1 9 7 2 ) ，p p 9 1 1 0 8 【1 7 a i p i n gl i a o , m o d i f y i n gt h eb f g sm e t h o d ，o p e r a t i o n sr e s e a r c hl e t t e r s2 0 ( 1 9 9 7 ) 1 7 1 1 刀 【1 8 】j j m o r ，b s g a r b o wa n dk e h i u s t r o m , r e s t i n gu n c o n s t r a i n e do p f i m i z a - t i o ns o f t w a r e ”，a c mt r a n s m a t h s o f t w a r e7 ，1 7 4 1 ( 1 9 8 1 ) 【1 9 lj n o c e d a l ，”t h e o r yo fa l g o r i t h m 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 n “，a c t a n u m e r i c a1 ，1 9 9 - 2 4 2 ( 1 9 9 2 ) 【2 0 jm j d p o w e l l , an e wa l g o r i t h mf 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 ，n o r i l i n e a r p r o g a m m i n g ，j b r o s e n ，o l m a n g a s a r i a na n dk r i t t e t r e d s z ，a c a d e m i c p r e s s , n e w 、b r k ，1 9 7 0 f 2 1 】m j d p o w e l l , ”s o m eg l o b a lc o n v e r g e n c ep r o p e r t i e so fav a r i a b l em e t d c a l g o r i t h mm i n i m i z a t i o nw i t h o u te x a c tl i n es e a r c h s ，i n ：r w c o m ea n d c e l e m k e ( e d s ) ，n o n l i n e a rp r o g r a m m i n g , a m e r i c a nm a t h e m a t i c a ls o c i e t y , p r o v i d e n c e ，r i 1 9 7 6 ，p p ，5 3 - 7 2 参考文献2 4 2 2 1m a r c o sr a y d o n , t h eb a r z i l a ia r i db o r w e i ng r a d i e n tm e t h o df o rt h el a r g e , s c a l eu n c o n s t r a i n e dm i n i m i z a t i o np r o b l e m , s i a m j o p 血v 0 1 7 ，n o 1 ， p p 2 6 - 3 3 ，f e b 1 9