（应用数学专业论文）一个无惩罚型两步线性搜索算法.pdf

个无惩罚型两步线性搜索算法 中文摘要 中文摘要 无惩罚方法是目前非线性优化领域的研究热点，过滤方法和u l b r i c h - u l b r i c h 非单调信赖域技术是其中比较成熟的两种方法本文受u l b r i c h - u l b r i c h 方法 的启发，提出了两步线性搜索算法在算法中，每次计算一个切方向和一个 法方向，再通过后退线搜索技术确定步长通过要求法向下降量、切向下降 量和函数下降量满足一定的关系来保证全局收敛性该算法不需要使用罚函 数，搜索方向的计算量比较小最后，通过数值试验来验证算法的有效性 关键词：非线性优化，等式约束，线性搜索，无惩罚型方法 作者：孙刘平 指导老师：陈中文 ap e n a l t y - f r e e - t y p et w os t e pl i n es e a r c hm e t h o d a b s t r a c t a b s t r a c t p e n a l t y - f r e e - t 帅em e t h o d ，w h i c hd o e sn o tu s ea n ym e r i tf u n c t i o nt og u r a n t e e g l o b a lc o n v e r g e n c e ，h a sb e c o m ea na c t i v ea r e ao fr e s e a r c h a m o n ga l lt h ep e n a l t y - f r e e - t y p ea l g o r i t h m s ，f i l t e rm e t h o d sa n du l b r i c h - u l b r i c hn o n m o n o t o n et r u s tr e g i o nm e t h o d a r et w oc l a s so fp r a c t i c a la n de f f e c t i v ea p p r o a c h s i n s p i r e db yt h ew o r ko fm u l b r i c h a n ds u l b r i c h ，w ep r e s e n th e r eat w o - s t e pl i n es e a r c ha l g o r i t h m ，w h i c hd o e sn o tu s e a n yp e n a l t yf u n c t i o n ，e i t h e r a te v e r yi t e r a t i o n ，w ec o m p u t ean o r m a ld i r e c t i o na n d at a n g e n t i a ld i r e c t i o n ，t h e nw ef i n das t e pl e n g t hb yb a e 龇r a c i n gt e c h n i q u e t og l o b - a l i z eo u ra l g o r i t h m ，w en e e dt h ep r e d i c t e dn o r m a lr e d u c t i o n ，t h ep r e d i c t e dt a n g e n t i a l r e d u c t i o na n dt h ep r e d i c t e do b j e c t i v ef u n c t i o nr e d u c t i o nt os a t i s f yac e r t a i nc o n d i t o n t h ec o s ti nc o m p u t i n gn o r m a la n dt a n g e n t i a ld i r e c t i o ni ss m a l l a n dt h ea l g o r i t h m d o e sn o tn e e dt or e c o m p u t et h e s et w od i r e c t i o n sw h e nt r i a ls t e p sw e r er e j e c t e d t h e b a c k t r a c i n gt e c h n i q u ew a su s e d f i n a l l y , p r e l i m i n a r yn u m e r i c a lr e s u l t sw e r er e p o r t e d t ov e r i f yt h ee f f i c i e n c yo ft h ea l g o r i t h m k e y w o r d s ：n o n l i n e a ro p t i m i z a t i o n ，e q u a l i t yc o n s t r a i n t ，l i n es e a r c h ，p e n a l t y - f r e e - t y p em e t h o d ， i i w r i t t e nb ys u nl i u p i n g s u p e r v i s e db yp r o f c h e nz h o n g w e n 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名：二蝉日 期：型啤盟 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名：勤塑车日期：型艺：查 导师签名：王皇章是 日 个无惩罚型两步线性搜索算法一引言 第一章引言 最优化在航空航天、生命科学、水利科学、地球科学、工程技术等自然科 学领域和经济金融等社会科学领域有着广泛和重要的应用，它的研究和发 展一直得到广泛的关注最优化的研究包含理论、方法和应用最优化理论 主要研究问题解的最优性条件、灵敏度分析、解的存在性和一般复杂性等， 而最优化方法研究包括构造新算法、证明算法的收敛性、算法的收敛速度及 数值试验等，最优化的应用研究则包括算法的实现、算法的程序、软件包及 商业化、在实际问题中的应用等 我们考察如下非线性等式约束最优化问题 m i n x r nm ) ， ( 1 1 ) s t c ( x 1 = 0 、 其中f ( x ) ：p _ r 二阶连续可微，c ( z ) = ( c 1 ( z ) ，c 2 ( z ) ，( z ) ) r ，q ( z ) ： r 竹一r 1 ( i = 1 ，2 ，m ) 二阶连续可微 为解决问题( 1 1 ) ，人们已经提出很多成熟的算法，如线性搜索算法【1 ，2 ，3 】， 共轭梯度法 4 】，序列二次规划方法( s q p 方法) 5 】，信赖域方法【6 】等等各种 算法的收敛性和有效性在不同的文献中已得到证明( 【2 】) 在各种算法中，信 赖域方法是比较有效的算法，而信赖域算法中b y r d - o m o j o k u n 型两步信赖域 方法( 【7 ，8 ，9 】) 是比较实用，有效的方法 约束优化问题需要解决两个问题：最优性和可行性遗憾的是很多时候 这两大目标是冲突的，为协调问题的最优性和可行性，人们一般借助于某个 效益函数，通过调整效益函数中的罚因子在最优性和可行性之间找到一个 一个无惩罚型两步线性搜索算法一引言 平衡这一类方法统称为罚函数法，主要有外罚函数法和内函数法两种 总的来说，罚函数法是比较有效的但是它也有明显的缺陷：罚因子很 难确定以及可能出现的计算溢出问题 为了克服罚函数的缺陷，f l e t c h e r ( 1 0 ) 等提出了以过滤方法为代表的无 惩罚型方法在过滤方法中，f l e t c h e r 用“滤子静来代替罚函数他们巧妙 地将最优化问题转化为双目标规划问题，即函数值最小： r a i n ，( z ) ， 以及不可行度最小： m i n ( c ( z ) ) ， 其中 ( c ( z ) ) ：舻_ r + 是用来衡量可行性的函数，它满足 z 可行甘 ( c ( z ) ) = 0 如果在一点z 处的函数值和不可行度都比另一个点y 处小，则称z 优于y 过滤方法正是通过一个任一点都不优于其它点的滤子集来协调最优性和可 行性这两大目标当算法遇到子问题不相容等问题时，暂时退出过滤算法而 进入一种称之为可行性恢复的程序一般说来可行性恢复过程本身就是一 个非线性优化问题 过滤方法现在已经被应用到序列线性规划( s l p ) 方法、序列二次规划 ( s q p ) 方法、信赖域方法和线性搜索方法等领域( 见【1 0 ，1 1 ，1 2 ，1 3 ，1 4 ，1 5 ， 1 6 ，1 7 ，1 8 】) ，在理论上和数值计算上都取得了较大的成功 过滤方法不是唯一的无惩罚型方法，m u l b r i c h 和s u l b r i c h ( 【19 】) 受过 滤思想的启发，在b y r d o m o j o k u n 型两步信赖域算法的基础上提出了另一种 2 一个无惩罚型两步线性搜索算法 一引言 无惩罚型方法在这种方法里，u l b r i c h 和u l b r i c h 首先求解两个子问题：法 向子问题和切向子问题，所得的解称为法向步和切向步，其作用分别为减小 函数值和改善可行性，然后通过协调所谓的法向下降量、切向下降量、函数 值下降量的三者之间关系来达到协调最优性和可行性的目的这种方法的 优点是： ( 1 ) 不需要保存滤子集，从而节省内存，同时也可以避免因滤子集元素 过多而导致内存不足 ( 2 ) 不需要可行性恢复过程 c h e n 在【2 0 】中，将u l b r i c h 等的技巧应用到等式和简单界约束问题上 信赖域方法具有算法稳健有效的特点，对于求解中小规模非线性优化问题 十分有效但是信赖域方法要求每次都求解一个信赖域子问题而信赖域子 问题的求解需要较大的计算量，故信赖域方法对于求解大规模问题不大适 用因此，基于信赖域技术的u l b r i c h - u l b r i c h 型方法求解大规模问题时计算 量过大 其它无惩罚型方法还有，z o p p k e - d o n a l d s o n ( 【2 1 】) 的“t o l e r a n c et u b e ”方 法和g o u l d 和t o i n t ( 【2 2 】) 的“t r u s tf u n n e l 舛方法等 本文是在u l b r i c h 等和c h e n 的方法的基础上，用线性搜索技巧来代替其 中的信赖域技巧，从而使算法更为简洁，计算量更小，以期在将来可以应用 到大规模优化问题我们从法向子问题和切向子问题导出两个搜索方向：法 方向和切方向然后通过线性搜索技术获得相应的步长，为协调最优性和可 行性，我们同样要求法向下降量、切向下降量、函数值下降量的三者之间满 3 一个无惩罚型两步线性搜索算法一引言 足一定的关系 本文的结构如下，第二章我们提出算法，第三章讨论算法的定义和全局 收敛性，第四章给出数值算例，最后，对文章作一总结 4 一个无惩罚型两步线性搜索算法 二 算法 第二章算法 考虑非线性等式约束优化问题 等t 锄浆0 仁l ， s c ( z ) = 其中f ( x ) ：舻_ r 二阶连续可微，c ( x ) = ( c - ( 。) ，c 2 ( z ) ，( z ) ) t ，龟( z ) ： 舻一r 1 二阶连续可微 设当前迭代点为z 七，一般地，为获取搜索方向8 七，可求解以下二次规划 ( q p ) 子问题， m l n 吼( s ) ：夕蚕s + s t b 七s ，( 2 2 ) 8 t 仇+ 雒s = 0 、7 其中，b 知舻加是问题( 2 1 ) 的l a g r a n g e 函数的h e s s e 矩阵的对称近似矩 阵 a k = ( v c l ( z 奄) ，v c 2 ( z 知) ，v c 。( 。知) ) 舻m 一般情况下，子问题( 2 2 ) 可能不相容我们受b y r d - o m o j o k u n 的两步信赖域 方法及m u l b r i c h 和s u l b r i c h 的无惩罚方法思想的启发，提出了一种两步线 性搜索无惩罚型算法 在我们的算法中，我们将搜索方向d k 分为法方向露和切方向嚷，法方 向雄是如下法向子问题的下降方向 m 饥三l i c k + a t d = 1 1 2 ， ( 2 3 ) 由于 三l i c k + a t a m 2 = 到1 吼| 1 2 + ( a 七仇) r 扩+ 三( 扩) t a 七a 暑d ，1 个无惩罚型两步线性搜索算法 二 算法 则d ：；= 一a 七c k 是子问题( 2 3 ) 的一个下降方向设步长为口，s j = q d ：，切方向 魂是切向子问题 l i n 吼( s ：+ ) ， ( 2 4 ) s t a ：。= 0 的下降方向这两个方向的优点是计算简单，计算量小实际上，其它的下 降方向也是可行的，如拟n e w t o n 方向，s q p 方向【3 ，1 ，2 】和共轭梯度方向 【4 】等由于 q k ( d 譬k + ) = 蘸s 嚣+ 互1 ( s 嚣) r 风s ：+ ( 鼠s ： + 鲰) 丁+ 三( ) t 取， 故子问题( 2 4 ) 等价于 其中， 令 其中， m i n 雪手+ ( ) t b 七， s t 雒= 0 饥= b k s ：+ g k = z k u 玩舻( 俨删，a t z k = 0 ，磊磊= ，( 单位矩阵) 即磊的列向量是雒的零空间的一组基，则( 2 5 ) 变成为 ( 2 5 ) m 溉( 刃饥) t u + 丢钍t 翟鼠磊u ( 2 6 ) 易知，让= 一刁鲰子问题是( 2 6 ) 的一个下降方向，总的搜索方向就是 d j , = 露+ 哦= 一a c k z k 露饥 6 一个无惩罚型两步线性搜索算法 二 算法 因此，尝试步 8 = q 呶= 一a ( a k c k + 磊召o k ) 为了衡量算法的下降性，我们定义可行性约束条件的法向实际下降量 。r e = 2 1 1 c k l l 2 - 1 1 c ( 钆+ s ) 1 1 2 可行性的法向线性预测下降量 e 耀= a l l a k c 知1 1 2 目标函数线性预测下降量 p r e d f = 一9 1 8 = 一口夕舌d 譬一q 翻? 磙 = 一口( 纸t a 七c 七+ 夕七t 厶七厶七t 9 七) 目标函数切向线性预测下降量 r , e 4 = q 多手磙= 口纨 t 厶七t 玩饥= a 0 器纨| | 2 受m u l b r i c h 和s u l b r i c h ( 1 9 ) 的启发，我们希望法向线性预测下降量， 切向线性预测下降量和函数线性预测下降量之间满足一个特定的关系，使 得切向步口晚获得的下降量不被法向量口靠所破坏，具体地，要考察是否有 p r e 矾e 且p r e d f r p r e ，r ( o ，1 ) ( 2 7 ) 成立，如果( 2 7 ) 成立，我们可以通过选取适当的步长o t = o t 七，使得可行性和 目标函数值同时得到改善，否则的话，我们只要求取适当的步长o t = o t 知，使 得可行性得到改善 一个无惩罚型两步线性搜索算法 二 算法 当以下条件之一被满足时，接受尝试步 ( i ) ( 2 7 ) 成立，且a r e d 缈e 嚷和a r e d 缈e 都成立，其中p ( o ，1 ) ， ( i i ) ( 2 7 ) 不成立，且a r e d p p r e d 这样，我们得到如下算法 算法2 1 步0 ( 初始步) 取定z o ，口( 0 ，1 ) ，7 ( 0 ，1 ) ，p ( 0 ，1 ) ，b o 酽n 为对称矩 阵，令k ：= 0 步1 计算f k ，仇，g k ，a k ，z k ，z 9 k ，h ，选择初始步长q 步2 若i i 0 + i i z g 知l i = 0 ，则算法停止 步3 计算霞，戤，令d k = d ：；+ 嚷 步4 计算a r e d ，p r e d 嚣，a r e d ，p r e d ，e 磙 步5 若( 2 7 ) 成立，则转步5 1 ，否则转步5 2 步5 1 若a r e d p p r e d 或者a r e d 0 ， 当步长q 0 使得 i i c k l i = i i ( a t a 知) _ 1 a t a k c k l l i i ( a t a k ) - 1 雒l a c k l | m 1 l l a 知c k l l 故 i i a 七c k 怆击壶 ( 3 1 ) 于是 p r e d 叫酬z 嘉， 又 i a r e d 嚣一p r e d i = o ( a 2 i i d j c l l 2 ) = q 2 0 ( 1 l d k l l 2 ) 口2 尬为大于0 的常数，故而 + q 以1 1 2 一q i i a 七c 奄1 1 2 l - i - q a t d k l l 2 + o ( 1 l c y d k l l 2 ) 一c y l l a 七吼吲 一q ( a 七c 南) t d k a l i a 奄c 七1 1 2 + d ( 0 2 i l d k l l 2 ) i ( 3 2 ) a r e d ：一p r e d t 。 l p r e d 。，q 2 葫 q 尬脚 2 f 1 0 z z i 银 “ 仇 121212 一 一 一 隗 酝 酝 12l一212 一个无惩罚型两步线性搜索算法 三全局收敛性 令6 0 = 矧， 而0 7 e 嚷 则q r p r e 4 r p r e q 丢， a r e d 一e d l = l ，( z 七) 一，( z 七+ a d 知) 一a g t d k 坛是大于0 的常数，则 当 时， 从而， l q 夕舌以+ 等露v l s ( z 七) d k - - a g t 也 隆v ：卅岫也i n x 7 。2 z ，( z 七) l1 2 m 3 a 2 a r e d p r e d p r e d l k斋r 口e 坦f ，r e 2 ( 1 一p ) a 1 扫矿 a r e d p r e d p r e d g k q m 3 m 2 万。r e 1 一p a r e d p p r e d z k 由算法知8 七= a d 七为可接受尝试步 - 1 1 ( 3 3 ) 从 试 一个无惩罚型两步线性搜索算法 三全局收敛性 ( 2 ) i i 刃蚓i e 这时 1 1 名t 鲰i l = i i z ( m b k d ： + 鲰) = i i 耀9 k + q 刃风旗“ 1 1 耀g k l 卜c , i i z i b k l l l l d 嚣i i i i z 蚕g k l i q 地 m 4 为大于0 的常数若 6 2 m 4 则 i i 刃训丢 从而， p r e 矾：口i | 耀钏i e 2 口 若e 畦 e 啦，贝i jp r e d 嚣譬口，由( 3 1 ) ， 则当 时， l_ared2-pred,丽am3=丁4m3pred量 a ， l e 2 4 e 2 。1 6 6 时， a r e d l k p p r e d 1 一个无惩罚型两步线性搜索算法 三全局收敛性 由于这时p r e = p r e d 譬q ，再由( 3 2 ) 得： 令 警l 0 ，当口 0 ，正整数 o ，k 尬时，均有 此时，由( 3 2 ) 知， 仇i i e 刈酬2 筹 1 3 一个无惩罚型两步线性搜索算法 三 全局收敛性 又对于可接受尝试步有 e = 1 1 魄1 1 刈i i n z r e d c 等 这意味着 即 j i ma 七= 0 詹 - - * 0 0 又由引理3 1 的证明，存在n 0 ，当口 口口删n 这与l i m h q 知= 0 矛盾从而 再证 假设 。l i mi n f l l c 七l f = 0 七- + 1 i ms 叩0 觎i i = 0 七+ o 。 ( 3 6 ) ( 3 7 ) 则存在e 0 ，及k 的一个子列露，使得慨0 2 e ，由( 3 3 ) 对每个忌，存在不 后， 使得 慨+ 10 0 ，存在k 2 0 ，当k 鲍时， 刃鲰| i 2 6 1 5 一个无惩罚型两步线性搜索算法 三 全局收敛性 i i z o d l = 0 刀( q 七b k d ； + g k ) l l = i i z 蚕g 七+ 刀口风露l l i i z g 七0 一口- - c l i 刃鼠露| | i i 刀鲰i l 一口知i i z , b k l ii i l i i i 露g k l l a 七i i z b 知i i 击- - - ；l l c , 1 l = i i z e g 七i i - 却刃鼠i i i i c 七l l = 懈t 夕七i i _ 篱i i 刀b k l l l l c 七l i 其中，a 为最大步长，由算法给出由引理3 3 知，恕i | c k i i = 0 则我们 可以适当增大鲍，使得 i i z 0 i l e ，鲍 从而 p r e d t k 口七e 2 ，k 鲍( 3 8 ) 另一方面 p r e d i = a k l l a k c k l l 2 a k l l a 南1 1 2 i i c , , 1 1 2 从而适当增大鲍， p , - e a k l l a 七1 1 2 i i c i j 2 p r e 魄( v k 鲍) 又因为 i p r e d k p r e d t ki = 恢夕蚕榷 1 6 一个无惩罚型两步线性搜索算法 三 全局收敛性 从而，存在娲 0 ，k 时，有 口七l 阢| | i | 露0 a 七i | 鲰i a k l i | i c k l l p r e d r p r e d 2 且e 磙e 从而对于可接受尝试步，由算法，必有 上式结合( 3 8 ) ，便有 由于 故而l i m 口七= 0 令 a r e d l k p 矿e q 七e 2 易知， 。l i m a r e d i k - - i r e d i k = p r e d ，i - o 七l 叫i ma r e d 2 - e d c p r e d ，l = o o 。le d ci 其中，a r e d i k ，孑珥，石碡，p r e d 为以乱为步长的下降量，从而k 充分大时， a r e d p p r e d ，a r e d 撅 这意味着，靠= 瞰d 南也是可接受尝试步，与算法中o 七的取法矛盾证毕 由引理3 3 和引理3 4 可得到算法2 1 的下面的收敛性结果 1 7 一个无惩罚型两步线性搜索算法 三 全局收敛性 定理3 5 设 孤) 为算法2 1 产生的无限迭代序列，则至少存在一个聚点 是问题( 2 1 ) 的k k t 点 1 8 一个无惩罚型两步线性搜索算法 四数值试验 第四章数值试验 为了验证算法的有效性，我们对算法2 1 作初步的数值试验，我们的算 例都取自h o c k 和s c h i t t k o w s k i 的测试问题集【2 3 和s c h i t t k o w s k i 的【2 4 】表4 1 中，问题的编号和文献【2 3 中一致，如h s 5 0 表示文献中的第5 0 个算例 表中其它符号的意义为：佗，m 分别代表问题的变量个数和约束条件个 数，n f ，n 9 代表计算函数值，函数梯度的次数，e r r 表示计算精度，f ( x ) 是 所得到的目标函数的极小值 终止准则：当r e 8 = i i 耀鲰0 + i i c l l 1 0 - 5 时，终止计算，输出计算结果 算法中的参数p = r = 1 0 4 ，程序中矩阵鼠用b f g s 校正公式产生 表4 1 算例和计算结果 问题 扎mn f n g f ( x ) 7 - e s h s 7213 82 11 7 3 2 16 4 6 7 6 争0 6 h s 9 2 11 01 00 58 3 0 3 7 争0 7 h s 2 831 3 7 3 31 0 8 e - 1 09 9 3 6 3 争0 6 h $ 4 0438 35 00 2 57 8 5 6 4 1 争0 6 h $ 4 852 4 2 3 91 8 3 e - 1 18 0 6 6 2 争0 6 h $ 5 1532 82 45 7 5 e - 1 25 3 8 5 8 争0 6 h $ 6 1325 53 11 4 3 6 56 5 1 8 8 争0 6 $ 3 3 83 2 7 9 4 7 7 2 0 5 75 3 9 9 5 争0 6 从表4 1 可以看出，算法是比较有效的，计算的主要工作量是作为内循 环的后退线搜索由于计算搜索方向时的运算主要是向量乘积，而且不需要 做额外的迭代，所以计算搜索方向所需的计算量较小另一方面，每次拒绝 1 9 个无惩罚型两步线性搜索算法 四 数值试验 尝试步，进行内循环时，不需要重新计算搜索方向，所以算法完成一次迭代 所需的时间很少，因此总的计算速度较快 一个无惩罚型两步线性搜索算法 五结论 第五章结论 本文提出一个无惩罚型两步线性搜索算法来求解等式约束的最优化问 题给出了其全局收敛性分析，并结合数值算例说明了算法的有效性我们 的主要想法是在每一次迭代过程中，通过求解法向子问题和切向子问题获得 法向和切向两个搜索方向，利用后退线搜索获取适当的步长：利用u l b r i e h - u l b r i c h 无惩罚技术，协调可行性和最优性，保证算法收敛到k k t 点在理论 上我们证明了算法的收敛性，但收敛速度的分析有待于进一步的深入探讨 本文算法的优点：一是与罚函数法相比，不需要借助于罚因子；二是与 u l b r i c h - u l b r i c h 方法相比，搜索方向的计算简单易行，所需的计算量很小，而 且每次内循环中，不需要重新计算搜索方向但是由于本文是u l b r i c h - u l b r i c h 技术结合线性搜索技术的一次尝试，虽然搜索方向简单易行，但是对算法的 收敛速度也造成一定的影响，算法的迭代次数较多在进一步的研究中，我 们将考虑更为合理有效的搜索方向，期待进一步提高算法的计算效果 另外，我们的算法目前只适用于等式约束优化问题，如何将其应用到不 等式约束问题也是下一步研究工作的重点目前我们有两个思路：一是结合 c h e n 4 的思想，将其应用到等式和简单界约束问题中，二是结合内点法将 其应用到一般约束优化问题 本文算法的另一个可能的应用方面是用于求解大规模优化问题，我们将 在后续研究中考虑这方面的应用 2 1 个无惩罚型两步线性搜索算法五结论 就数值试验而言，目前仅仅计算了文献【2 3 ，2 4 】上的若干问题，尤其是对 于非线性程度较高的问题，中大规模问题，新算法的优越性没有充分显现出 来因此，有必要改进算法并进行更多更大规模的数值试验 一个无惩罚型两步线性搜索算法参考文献 参考文献 【1 】黄红选，韩继业，数学规划，清华大学出版社，北京( 2 0 0 6 ) 【2 】n o c e d a lj ，w r i g h ts j ，n u m e r i c a lo p t i m i z a t i o n ，s c i e n c ep r e s s ，b e i j i n g ，c h i n a ， ( 2 0 0 6 ) 【3 】袁亚湘，孙文瑜，最优化理论与方法，科学出版社，北京( 2 0 0 3 ) 【4 】戴虹，袁亚湘，非线性共轭梯度法，上海科学技术出版社，上海( 2 0 0 0 ) 【5 】5b o g g sb t ，t o l l ej r ，s e q u e c t i a lq u a d r a t i cp r o g r a m m i n g ，a c t an u m e r i c a ， 1 9 9 6 4 ：1 - 5 1 【6 】c o n na r ，g o u l dn i m ，t o i n tp h l ，t r u s t - r e g i o nm e t h o d s ，s i a m ， p h i l a d e l p h i a ，2 0 0 0 【7 b y r dr h ，s c h n a b e lr b ，s h u l t zg a ，at r u s tr e g i o na l g o r i t h mf o rn o n l i n e a r l y c o n s t r a i n e do p t i m i z a t i o n ，s i a mj n u m e r a n a l ，1 9 8 7 ，2 4 ：1 1 5 2 1 1 7 0 【8 】o m o j o k u ne 0 ，t r u s tr e g i o na l g o r i t h m s f o ro p t i m i z a t i o nw i t hn o n l i n e a re q u a l i t y a n di n e q u a l i t yc o n s t r a i n s ，p h dt h e s i s ，u n i v e r s i t yo fc o l o r a d oa tb o u l d e r ，u s a ， ( 1 9 8 9 ) 【9 】d e n n i sj e ，e 1 - a l e mm ，m a c i e lm c ，ag l o b a lc o n v e r g e n c et h e o r yf o rg e n e r a l t r u s t r e g i o nb a s e da l g o r i t h m sf o re q u a l i t yc o n s t r a i n e do p t i m i z a t i o n ，s i a mj o p t i m ，1 9 9 7 ，7 ：1 7 7 - 2 0 7 一个无惩罚型两步线性搜索算法参考文献 【1 0 】f l e t c h e rr ，l e y f f e rs ，n o n l i n e a rp r o g r a m m i n gw i t h o u tap e n a l t yf u n c t i o n ，m a t h p r o g ，s e r a ，2 0 0 2 ，9 1 ：2 3 9 - 2 6 9 【1 1 】c h i nc m ，f l e t c h e rr ，o nt h eg l o b a lc o n v e r g e n c eo fa ns l p - f i l t e ra l g o r i t h m t h a tt a k e se q ps t e p s ，m a t h p r o g ，2 0 0 1 ，9 6 ：1 6 1 - 1 7 7 【1 2 】c h i nc m ，r a s h i da h a ，m o h a m e dn o rk ，g l o b a la n dl o c a lc o n v e r g e n c e o faf i l t e rl i n es e a r c hm e t h o df o rn o n l i n e a rp r o g r a m m i n g ，o p t i m i z a t i o nm e t h o d s a n ds o f t w a r e ，2 0 0 7 ，2 2 ：3 6 5 3 9 0 【1 3 】f l e t c h e rr ，l e y f f e rs ，t o i n tp l ，o nt h eg l o b a lc o n v e r g e n c eo fa ns l p f i l t e r a l g o r i t h m ，n u m e r i c a la n a l y s i sr e p o r tn a 1 9 7 ，d e p a r t m e n to fm a t h e m a t i c s ， u n i v e r s i t yo fd u n d e e ，s c o t l a n d 【1 4 f l e t c h e rr ，g o u l dn i m ，l e y f f e r s ，w a t c h e ra ，t o i n tp l ，g l o b a lc o n v e r - g e n c eo ft r u s t - r e g i o ns q p f i l t e ra l g o r i t h m sf o rg e n e r a ln o n l i n e a rp r o g r a m m i n g ， s i a mj o p t i m ，2 0 0 2 ，1 3 ：6 3 5 6 5 9 【1 5 】u l b r i c hs ，o nt h es u p e r l i n e a rl o c a lc o n v e r g e n c eo faf i l t e r - s q pm e t h o d ，m a t h p r o g ，s e r b ，2 0 0 4 ，1 0 0 ：2 1 2 4 5 【1 6 】u l b r i c hm ，u l b r i c hs ，v i c e n t el n ，ag l o b a l l yc o n v e r g e n tp r i m a l - d u a li n t e r i o r - p o i n tf i l t e rm e t h o df o rn o n f i n e a rp r o g r a m m i n g ，m a t h p r o g ，2 0 0 4 ，1 0 0 ：2 3 1 2 5 2 【1 7 w a c h t e ra ，b i e g l e rl t ，l i n es e a r c hf i l t e rm e t h o d sf o rn o n l i n e a rp r o g r a m m i n g ： m o t i v a t i o na n dg l o b a lc o n v e r g e n c e ，s i a m j o p t i m ，2 0 0 5 ，1 6 ：1 3 1 一个无惩罚型两步线性搜索算法 参考文献 【1 8 】w a c h t e ra ，b i e g l e rl t ，l i n es e a r c hf i l t e rm e t h o d sf o rn o n h n e a rp r o g r a m m i n g ： l o c a lc o n v e r g e n c e ，s i a mj o p t i m ，2 0 0 5 ，1 6 ：3 2 4 8 【1 9 】u l b r i c hm ，u l b r i c hs ，n o n m o n o t o n et r u s tr e g i o nm e t h o d sf o rn o n l i n e a re q u a l i t y c o n s t r a i n e do p t i m i z a t i o nw i t h o u tap e n a l t yf u n c t i o n ，m a t h p r o g ，2 0 0 3 ，9 5 ：1 0 3 - 1 3 5 【2 0 c h e nz w ，ap e n a l t y - f r e e - t y p en o n m o n o t o n et r u s t r e g i o nm e t h o df o rn o n - h n e a r 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 dc o m p u t a t i o n ，2 0 0 6 ，1 7 3 ： 1 0 1 4 - 1 0 4 6 【2 1 】z o p p k e - d o n a l d s o ng ，at o l e r a n c e - t u b ea p p r o a c ht os e q u e n t i a lq u a d r a t i cp r o - g r a m m i n gw i t ha p p l i c a t i o n s p h dt h e s i s ，d e p a r t m e n to fm a t h e m a t i c sa n dc o r n - p u r e rs c i e n c e ，u n i v e r s i t yo fd u n d e e ，d u n d e e ，s c o t l a n d ，u k ，1 9 9 5 2 2 】g o u l dn i m a n dt o i n tp h l ，n o n l i n e a rp r o g r a m m i n gw i t h o u tap e n a l t y f u n c t i o no raf i l t e r ，m a t h p r o g ，( t oa p p e a r ) 【2 3 】h o c kw ，s c h i t t k o w s k ik ，t e s te x a m p l e sf