（应用数学专业论文）非线性等式约束优化问题的信赖域滤子算法研究.pdf

11，l ；iji11 i嗣 摘要 摘要 逐步二次规戈j j ( s q p ) 是求解中小规模非线性约束优化问题最常用、最有效的方法之 一为了使优化算法具有更好的收敛性和数值效果，近几年来学者们将非单调技术、自 适应技术和过滤技术等优化策略应用于优化方法中，取得了较好的结果本文主要研究 求解非线性等式约束优化问题的信赖域s q p 算法，基本思想是将各种优化策略引入信 赖域s q p 算法，以期得到良好的收敛效果和数值结果 本文共分四章，第一章首先介绍了信赖域s q p 算法，然后介绍了几种常用的优化 策略，最后详细介绍了信赖域s q p 滤子算法在第二章中，首先简单介绍了解决信赖 域子问题不相容的方法和子问题求解的方法，接着介绍了m a r a t o s 效应出现的原因和常 用的解决m a r a t o s 效应的方法最后介绍了本文所用到的测试函数 苏珂等学者的研究成果表明，在算法框架的改进方面引入非单调技术，以非单调的 过滤技术来判断试探步的可接受性可以排除m a r a t o s 效应的干扰本文第三章，在苏珂 等学者研究的基础上，提出了两种非单调的信赖域s q p 滤子算法在一定的假设条件 下，对这些改进后的算法框架进行收敛性分析最后将本文的两种非单调信赖域s q p 滤子算法与苏珂的非单调信赖域s q p 滤子算法应用于优化测试模型中，得到了较好的 数值结果数值实验显示，本章所提出的算法具有更好的数值效果 考虑信赖域半径的选择也会影响算法的效率第四章以第三章提出的算法为基础， 在信赖域子问题求解的改进方面，引入自适应技术，提出一种自适应的信赖域s q p 滤 子算法在一定条件下，证明了算法的全局收敛性数值实验表明了该方法的有效性， 并且在一些问题中取得了比第三章的算法更好的结果 关键词：信赖域算法；s q p ；滤子，非单调技术；自适应技术 非线性等式约束优化问题的信赖域滤子算法研究 a b s t r a c t f e a s i b l ed i r e c t i o nm e t h o d ，p e n a l yf u n c t i o n m e t h o d ，s e q u e n t i a lq u a d r a t i c p r o g r a m m m gm e t h o da n dr e d u c e dh e s s i a nm e t h o da r ea p p l i e dm o r ee x t e n s i v e f o r s l o v i n gn o n l i n e a rc o n s t r a i n e do p t i m i z a t i o n p r o b l e m s e q u e n t i a lq u a d r a t i c p r o g r a m m i n gm e t h o di ao n eo ft h em o s ti m p o r t a n tm e t h o df o rs o l v i n gm i d d l e s c a l ea n ds m a l ls c a l en o n l i n e a rc o n s t r a i n e do p t i m i z a t i o n i no r d e r t om a k et h e o p t i m i z a t i o na l g o r i t h mh a sb e t t e rc o n v e r g e n c ea n dn u m e r i c a lr e s u l t s r e c e n t l y y e a r s ，o p t i m i z a t i o ns t r a t e g ya r ea p p l i e di no p t i m i z a t i o nm e t h o db ys c h o l a r s ，a n d g o o d r e s u l t sa r ea c h i e v e d s u c h a sn o n m o n o t o n i c t e c h n o l o g y a d a p t i v e t e c h n o l o g ya n df i l t e rt e c h n o l o g y i nt h i sp a p e r ，t h et r u s tr e g i o ns q p a l g o r i t h mf o r s o l v i n gt h en o n l i n e a re q u a t i o n so p t i m i z a t i o np r o b l e m sa r es t u d i e d a l g o r i t h m 1 m p r o v e m e n t si nt r u s tr e g i o ns u b p r o b l e m sa n da l g o r i t h mf r a m e w o r k ，t h eb a s i c i d e al st oi m p r o v ev a r i o u so p t i m i z a t i o ns t r a t e g yi n t os q p t r u s tr e g i o na l g o r i t h m i no r d e rt og e tg o o dc o n v e r g e n c ea n dn u m e r i c a lr e s u l t s i nc h a p t e r1 ，t h eb a s i ct h e o r yo fn o n l i n e a ro p t i m i z a t i o na n dt h i s p a p e r m a i n l ys t u d i e st h es q pt r u s tr e g i o na l g o r i t h ma r ei n t r o d u c e d ，t h e ns e v e r a l c o m m o no p t i m i z a t i o ns t r a t e g ya r ei n t r o d u c e d f i n a l l y ，t h et r u s tr e g i o ns q p f i l t e r a l g o r i t h ma r ei n t r o d u c e d i nc h a p t e r2 , t h es u b p r o b l e mi n c o m p a t i b l ea n dm a r a t o s e f f e c t si nt r u s tr e g i o ns q p a l g o r i t h mf o rs l o v i n gt h ec o n s t r a i n e do p t i m i z a t i o n p r o b l e m a r ei n t r o d u c e d s i m p l y f i r s t ，s o l v e t r u s t r e g i o ns u b p r o b l e m s i n c o m p a t i b l em e t h o da n dp r o b l e ms o l v i n gm e t h o da r ei n t r o d u c e d ，t h e nt h e r e a s o n sa n dm a r a t o se f f e c t so fc o m m o n l yu s e dm e t h o d so fs o l v i n gm a r a t o s e f f e c ti si n t r o d u c e d f i n a l l y ，t h eu s eo f t e s tf u n c t i o ni si n t r o d u c e d s u k e sr e s e a r c hr e s u l ts h o w st h a tt h ei m p r o v e da l g o r i t h mf r a m e w o r k i nt h e a s p e c t so fn o n m o n o t o n et e c h n i q u et oj u d g et h e a c c e p t a b i l i t yc a nm a k et h e t e s t i n gs t e p so v e r c a m et h em a r a t o se f f e c t s i nc h a p t e r3 ，o nt h eb a s eo fs u k e r e s e a r c h ，t h et w on o n m o n o t o n et r u s tr e g i o ns q pf i l t e ra l g o r i t h mi sg i v e n i nt h e a s p e c to ft h et r i a ls t 印，w ec o m p u t eaq u a s i n o r m a ls t 印a n da t a n g e n t i a ls t e pf o r s o l v i n gt h et r u s tr e g i o ns u b p r o b l e m t h e n ，t h ec o n v e r g e n c eo ft h e i m p r o v e d a l g o r i t h m su n d e rc e r t a i nc o n d i t i o na r ea n a l y s e d f i n a l l y ，m a k et w on o n m o n o t o n e t r u s tr e g i o na l g o r i t h ma n ds u k e ss q pf i l t e rn o n m o n o t o n es q pt r u s tr e g i o n l v 目录 目录 第1 章绪论1 1 1 非线性约束规划基本理论i 1 2 信赖域s o p 算法4 1 3 几种常用的优化策略6 1 3 1 非单调技术6 1 3 2 自适应技术7 1 3 3 预条件技术7 1 4 信赖域s q p 滤子算法8 第2 章预备知识11 2 1 子问题求解11 2 1 1 子问题的分解，j 2 1 2 子问题的求解，3 2 2m a r a t o s 效应1 4 2 2 1w a t c h d o g 技术，彳 2 2 2 二阶校正步技巧，4 2 2 3 采用光滑效益函数，5 2 3 本文所选用的测试函数1 5 第3 章两种非单调的信赖域s q p 滤子算法2 1 3 1 引言2 l 3 2 算法2 1 3 3 算法的适定性及全局收敛性2 4 3 4 数值试验2 8 第4 章一种自适应的信赖域s o p 滤子算法。3 1 4 1 算法3l 4 2 算法的适定性与全局收敛性3 2 4 3 数值试验3 5 结论3 7 参考文献。3 9 致谢4 3 硕士期间发表的论文4 5 v 信赖域滤子算法研究 第i 章绪论 第1 章绪论 对于非线性约束优化问题的求解，目前应用比较广泛的方法有：可行方向法、罚函 数法、逐步二次规划法( s q p ) 和既约h e s s i a n 法非线性优化的传统方法几乎都是线 搜索类型的方法，常常由于步长过大而导致算法失败，特别，当问题是病念时尤为如 此信赖域算法则是近年来所提出的一类新的方法，能有效的求解病念的优化问题，它 和线搜索方法并称为目前求解非线性规划的两类主要的数值方法，是当今寻求如何构造 新的优化计算方法的主要途径 信赖域方法的关键部分是信赖域试探步的求解和试探步是否可接受的测试试探步 一般通过子问题来求解；而决定试探步是否可被接受通常是利用某一价值函数，看试探 步能否使价值函数下降在无约束优化问题中，价值函数是目标函数而在约束优化问 题中，为了协调约束优化问题的最优性和可行性，价值函数常常是一罚函数总体来说， 罚函数法是比较有效的但它也有明显的缺陷：罚因子很难确定并且可能出现计算溢出 问题为了克服罚函数的缺陷，f l e t c h e r 1 l 等提出了以过滤方法为代表的无惩罚型方法该 方法放宽了迭代步的接受条件，实际起到的是和非单调技术类似的加速迭代收敛的作 用过滤技术不光可以应用于信赖域s q p 框架和线搜索s q p 框架它还可以向非光滑 优化、无约束优化等问题推广，在理论上和数值计算上都取得了较大的成功 从8 0 年代中期开始，许多学者对非线性等式约束问题的信赖域算法进行了研究， 构造了不同的信赖域算法，使等式约束优化问题的研究不论从理论上还是实际计算上都 得到了较好的结果如文献 1 8 1 【2 6 】非线性等式约束问题的一个主要工作是相容子问 题的建立与求解，大多数的信赖域子问题可视为s q p 子问题的修改 为了使优化算法具有更好的收敛性和数值结果，近几年来学者们将非单调技术、自 适应技术和过滤技术等优化策略应用于优化方法中，取得了较好的结果本文主要研究 滤子技术、非单调策略和自适应策略在求解非线性等式约束优化问题的信赖域s q p 算法 中的应用本章主要介绍非线性约束规划的基本理论、信赖域s q p 算法、几种常用的优 化策略以及信赖域s q p 滤子算法 1 1 非线性约束规划基本理论 非线性优化问题通常可以写成 m i n f ( x 、 ( 1 1 ) ( 胛) s ，q ( 力= o ，e = l ， ( 1 2 ) 非线性等式约束优化问题的信赖域滤子算法研究 q ( z ) o ，f ，= m e + 1 ，m ( 1 3 ) 其中，( x ) ，q ( x ) ，汪( 1 ，2 ，m ) 是定义在尺”上的实值连续函数，且至少一个是非线性 的m m e 0 是两个非负整数，f ( x ) 是目标函数，c ( x ) 是约束函数满足约束条件的 点称为可行点，所有可行点的集合称为可行域，一般记为x ： x = x i g ( x ) = o ，i = 1 ，屯；c f ( x ) o ，f = ，+ l ，刀) 当m = 0 时，问题( n p ) 称为无约束优化问题，否则称为约束优化问题在约束优 化中，如果只有等式约束，即m = m e 0 ，则称为等式约束优化问题，即 ( p )r a i n 厂( 工) ( 1 4 ) s ，q ( x ) = o ，f ，= 1 ，2 ，肌) ( 1 5 ) 其中，x r ”，函数f ：r ”一r ，q ：r ”寸r 均是二次连续可微的，一般用v y ( x ) 表示厂 在x 处的梯度，记为g ( x ) ，用( v c l ( x ) ，v c ：( x ) ，v c 。( x ) ) 表示约束函数 c ( x ) = ( q ( x ) ，c ：( x ) ，c m ( x ) ) 1 的梯度，记为a ( x ) 迭代法是解非线性优化问题的基本方法，在具体实现上，可分为线搜索框架和信赖 域框架 线搜索框架，就是在每一个迭代点赡处，算法需要求解一个搜索方向矾和沿此方向 的搜索步长吼，从而迭代过程就可表示为x k + 。= x k + 嚷畋大多数线搜索算法，如牛顿 法，共轭梯度法，要求吃是一个下降方向，即刃夥( ) 厂( x + ) 成立，则称x 是全局严格极小点 定义1 5 【1 2 】设r d ，如果对某一万 0 有 厂( x ) 厂( x + ) ，诋d n b ( x * , 万) 成立，则称石+ 是问题州p ) 的局部极小点如果对一切z d nb ( x ，6 ) 且x x + 有 f ( x ) 厂( x ) 成立，则称x + 是局部严格极小点 定理1 1 【1 3 1设x 是等式约束优化问题( p ) 的局部最优解，并设在x 。处 v q ( x + ) ( f = 1 ，2 ，m ) 线性无关，则存在向量刀= ( 彳，正，屯) 7 使得： v x l ( x + ，旯) = o ( 1 6 ) 丑+ o ，彳c ( x + ) - - o ，f l ，2 ，肌 ( 1 7 ) 上述定理也称为k k t 定理，( 1 6 ) ( 1 7 ) 称为等式约束优化问题的一阶必要条件或 3 1 f 线性等式约束优化问题的信赖域滤子算法研究 k - k t 条件，满足( 1 6 ) ( 1 7 ) 的点x 。称为等式约束优化问题的k k t 点在约束函数梯 度线性无关的假设下，最优解必定是k k t 点，但在约束函数梯度线性无关时，等式约 束优化问题不一定有k k t 点我们扩充稳定点的定义： 定义1 6 【1 3 】如果x + r ”满足： z ( x ) 。g ( x ) = 0 ( 1 8 ) c ( x ) = 0 ( 1 9 ) 则x + 称为等式约束优化问题的一阶点其中z ( x ) 是彳( 石) 7 的核空间的正交基，即 彳( x ) 7z ( x ) - - o 且z ( x ) 2z ( x ) = ，定义所描述的条件叫做等式约束优化问题的稳定性条 件满足稳定性条件的点称为等式约束优化问题的稳定点 1 2 信赖域s q p 算法 s q p 方法可以看作是无约束优化的牛顿法在约束最优化中的推广，最早眭1 w i l s o n 在 文献 1 7 】中提出，具有较为成熟和易运算操作的特点它的基本思想是：由于q p ( 二次规 划) 问题的成功解决，就想到在当迭代点致处，利用目标函数的二次近似和约束函数的 线性近似构成一个二次规划通过求解这个二次规划得到下一个迭代点x k + ， 用信赖域s q p 方法求解等式约束优化问题( p ) ，在当前迭代点而，信赖域q p 子问 r d r r q e ( x , ，a i ) 为 m i n 去d 7 1 h k d 十夥( 坼) 7 d s a t a ( x k ) d + c ( 黾) = 0 ( 1 1 0 ) i i d l l - 0 ，在点坼处计算出试探步以后，由雎计算肌， p k2段_ l ，都，巩u k _ 2 l v k ， 一2 u k + ，否则 唯 ( 1 1 6 ) 算法1 1 ( 信赖域s q p 算法) 步0 ( 初始化) 选取常数丽。 0 ，。 0 ，a 。i 。a o a 。，f ( o ，1 ) 1 ， 0 r 1 0 ，肛l = l ，取初始对( 而，五) ，初始矩阵凰，计算z o ，令 k ：= 0 步1 ( 终止准则) 若0 刃厂( 五) | i + 忙( ) e ，停止，得解以；否则，转步2 步2 ( 计算试探步) 解信赖域子问题( 1 1 0 ) ，得解吨 步3( 修币乘子五) 在以+ 巩处用最小二乘估计( 1 1 3 ) 计算五+ 。，并计算力= 五+ 。一以 步4 ( 修正罚参数2 ) 用公式( 1 1 6 ) 计算版 步5 ( 测试试探步的可接受性) 计算珞：丝萼 p rc u k 若 仍，拒绝试探步以，取。= i l 以l l ，返回步2 若r 1 圪，接受试探步，设扳+ l = 坼+ 以，且若吆 r 2 ，令a 川：= m a x h ，a 。i 。) ；否则 a 川：= m i n a m a xm a x a m i n 口2 a 步6 选取适当的方法修正以得巩+ 令k ：= k + 1 转步1 注：算法1 1 中的步1 给出的终止准则等价于而是问题( p ) 的k k t 点 5 非线性等式约束优化问题的信赖域滤子算法研究 1 3 几种常用的优化策略 1 3 1 非单调技术 最优化方法通常是用迭代法来产生它的最优解，它总是要求新的迭代点比以前的迭 代点有所改进这一思想在求解过程中的直接体现就是要求： 厂( 稚+ 1 ) s ( x k ) ，k = l ，2 ， 满足这样要求的算法，我们称之为单调类算法但这种要求也有它的缺点一个典型的 情况就是当目标函数的图像在可行域中存在细长弯曲的峡谷时，一旦迭代进入峡谷，它 只能沿着峡谷缓慢前进，产生l l i l d , 的步长，甚至出现锯齿现象，于是超线性收敛步不一 定被接受，从而破坏收敛性( 即m a r a t o s 效应) 基于对以上这种现象的观察，人们要求 新的迭代点在前面数步迭代的基础上有所改进，其典型形式就是要求 s ( x k + ) 躐【一j 其中m 是个大于零的常数，这种类型的算法称之为非单调算法，其实质是把单调下降 的要求放松为多步下降，从而可把非单调技术看成是对算法框架的一种改进 非单调算法起源于文 2 7 中针对一类约束优化方法的m a r a t o s 效应提出的 “w a t c h d o g ”技术从2 0 世纪8 0 年代中期开始，g r i p p o 等人对线搜索框架下的非单 调技术做了系统的研究( 2 8 1 一 3 1 】) ，极大地推动了非单调技术研究工作的丌展关于非 单调线搜索的进一步结果可见文 3 2 1 与 3 3 1 随着非单调技术在线搜索框架中的成功应 用，研究者们自然试图将其应用到信赖域框架中，我国学者对这方面的早期成果做出了 很大的贡献，如文【3 5 】与 3 6 1 随后，柯小伍和韩继业也分别在文 3 7 】和【3 8 】中针对等式 约束优化问题和无约束优化问题给出了有效的非单调信赖域算法t o i n t 在文【3 9 】与 4 0 】 中针对文 3 5 】中的算法框架做了一些改进，并做了大量的数值试验，表明非单调技术在 实际计算中效率有明显的改进，进一步的结果可见文 4 0 1 与 4 1 1 非单调技术在数值优化中的应用已经深入到很多方面了例如，在自适应信赖域方 法中的应用可见文【4 5 】，在锥模型信赖域方法中的应用可见文【3 1 】在非光滑无约束优化 问题中的应用可见文 4 6 1 文 4 7 】对非单调技术的思想和发展作了一个全面的综述 滤子算法中，常用的非单调格式有以下两种： r 脚( 后) 一i1 ( 1 ) 办( x ) 嘶m 驯a x 州忽一，或巾) - 0 ，初始对称矩阵，定义各个参数，并初始 化滤子，令k ：= 0 步1 ( 终止准则) 若i 露厂( ) | | + 肛( 吒) i e ，停止，得解；否则，转步2 步2 ( 计算试探步) 若信赖域子问题( 1 1 0 ) 不相容，进入还原阶段，找到一个可被过 滤接收的点；若信赖域子问题( 1 1 0 ) 相容，解得以 步3 ( 测试试探步的可接受性) 令z ( 川) = x ( ) + d ( ) 计算( 五+ l ，吃+ 1 ) ； 如果( 六小+ 。) 可以被过滤接受，则将( 五+ l ，h k + 。) 加入该过滤； 从过滤中删除被( 以+ ，吃+ 。) 占优的点对； 9 赖域滤子算法研究 第2 章预备知识 第2 章预备知识 在信赖域s q p 算法的实际计算中，有两个问题需要进一步考虑：其一是信赖域子 问题，包括子问题的相容性和子问题的求解，其二是克服m a r a t o s 效应因此，本章详 细介绍子问题求解和m a r a t o s 效应的避免本章的最后还介绍了本文用到的优化测试模 型 2 1 子问题求解 2 1 1 子问题的分解 对于信赖域q p 子问题( 1 1 2 ) ，两个约束条件有可能不一致，从而导致整个子问题 没有解，即子问题不相容如图2 1 所示 以。 a i d + c k = 0 、。 图2 1 子f * q 题不相容 f i g u r e2 1i n c o n s i s t e n tc o n s t r a i n t si nt r u s t - r e g i o nm o d e l 为了保证子问题的相容性，我们可以对子问题进行修改，在每个迭代步不要求子问 题中的等式约束精确满足，而是逐步提高相容性，直到在极限点满足可行性条件基于 这种思想，一般有以下几种方法： ( a ) 移位法：将子问题中约束的可行域往原点方向压缩： m 删i n 咖+ k 2 d 7 h k d s j ， a k d + e k h k = 0 l i d l l - a 。 为使变换后的子问题与原问题的解尽量一致，一方面，我们应当选取皖尽可能靠近 1 另一方面，为了使问题能有一定的自由度，不能使最过大常用的选取皖的方法是 利用g a u s s n e w t o n 步 ( b ) 罚函数方法：构造如下子问题： 黑爵d + 吉d r 吼d + 吼0 c 。+ a ：d 0 1 卜线性等式约束优化问题的信赖域滤子算法研究 妣l a a t 该方法对罚因子的选取比较敏感，并司能因为罚函数的不司微性导致局部收敛性分 析中的m a r a t o s 效应 ( c ) 两球约束法： m 出i ? n 或n 即 盯i i a , a + o a i l 2 磊 2 ： 其中彘是保证上面子问题相容的参数 ( d ) 方向分解法： 将试探步的计算分为两个阶段，第一阶段，我们忽略目标函数， 研究满足线性化的约束条件的试探步求解如下法向子问题： 哪n l l a , y + q i i ： j j i l v l l ：弘。 这里0 f 0 设d o = 0 ，r o = v j ( x ) ，p o = - r o ，令j ；0 步1 若忙占，取d = 嘭为问题的解，算法终止否则，转步2 步2 若锄o ，确定f 使得d = 嘭+ r p j 满足恻l = ，d 作为子问题的近似解，停止计 算否则，计算： 仅j = t r j l l p l j h p l 、，d j n = dj + 仅j p j 步3 若l k + 。忙，确定f o 使得d = 嘭+ f 马满足俐l = ，d 作为子问题的近似解，停止 计算否则，设o l = ，：+ 口j h p j 步4 若忆+ 。l l 占蚓l ，设d = d j + 。为子问题的近似解，停止计算；否则设： p j n = r 1 j “| r ：r j ，p j h = r j n + p j n p j 步5 设：= j + l ，转步1 2 2m a r a t o s 效应 若信赖域s q p 算法中单位步长可以接受，即当k 充分大时，= l ，则算法具有超线 性收敛性，然而很多情况下，不能保证单位步长被接受，这种现象称为m a r a t o s 效应克 服m a r a t o s 效应通常有如下三种方法 2 2 1w a t c h d o g 技术 此方法是一种非单调技术，算法按“标准型搜索”与“松弛搜索”进行在“标准 型搜索 中要求： ( 垓+ l ，) ( ，) 而在另一些迭代中进行“松弛搜索”，如简单取步长瓯= 1 “松弛搜索”计算的前提是 在某次迭代中产生的点比所求迭代点中最好点处效益函数有足够的下降，则下次迭代用 “松弛搜索 ，即松弛搜索的起点是所求点中“最好”的点 由于标准型搜索要求效益函数的下降性，因此标准搜索后的点比松弛型搜索的终点 要好，但不一定比已求得的“最好 点好，经过几次标准型迭代后，应可求得比原“最 好”点更好的点一般我们设松弛型搜索后的标准搜索最多进行f 次，若，次后我们仍找 不到比已有“最好”点更好的点，说明“松弛搜索”是不恰当的，要再次回到该次松弛搜 索的起点重新进行标准搜索这样，最多作t + 2 次迭代，我们总可以找到比原来“最好 点更好的点，因此算法总体是下降的 2 2 2 二阶校正步技巧 二阶校正步是指在吒处求得s q p 子问题的解以后，对巩进行二阶修正，即求巩使 1 4 第2 章预备知识 得： l i 反0 = o ( 1 巩1 1 2 ) ，( + 巩+ 反) ( ) 显然，之+ 以仍是一超线性收敛步 2 2 3 采用光滑效益函数 效益函数应满足的条件： ( 1 ) 应易于计算且避免太多的参数； ( 2 ) 对的极小应能最终找到原问题的最优解x ，且x + 为的一个极小点； ( 3 ) 的值沿矾总可以下降； ( 4 ) 全局收敛性； ( 5 ) 应有一定的光滑性，以便不影响最终的收敛速度 对于等式约束问题，我们可用f l e t c h e r 精确罚函数作为效益函数 2 3 本文所选用的测试函数 针对等式约束问题，我们给出几种经典的测试函数，主要检验新算法的可行性及收 敛效果以下给出具体的优化测试问题及其图示 ( 1 ) m i n f ( x ) = 五 “q ( x ) = 薪+ 一2 = 0 p - - ( 7 ，9 ) 7 ( 2 ) m i n f ( x ) = m ( 1 + 彳) 一x 2 妣q ( x ) = ( 1 + 彳) 2 + 2 - 4 = 0 p = ( 2 ，2 ) 7 m i n m 阳；n ( 引c o s ( 吾恐) “c l ( x ) = 4 五一3 x 2 = 0 x o = ( o ，o ) 1 ( 4 ) m i n m ) 7 1x 2 也t + 哮 5 j q ( x ) 2 i ：_ 兰芝f t = 。 1 5 一 1 f ：线性等式约束优化问题的信赖域滤子算法研究 二= 二二二二= = 二= = 二二z 二一 妒= ( 2 ，1 ) r ( 5 ) m i n f ( x ) = ( x , + 恐) 2 + ( 恐+ 而) 2 ， j j q ( 石) = x i + 2 x 2 + 3 x 3 1 = 0 x 。= ( _ 4 ，i ，1 ) r ( 6 ) m i n 厂( x ) = ( 五- 1 ) 2 + ( 葺一x 2 ) 2 + ( 一屯) 4 s j q ( x ) = 五( 1 + ) + 一8 2 4 2 6 = 0 妒= ( 1 5 ，1 5 ，1 5 ) 7 ( 7 ) m i n f ( x ) = - ( o 0 0 l x i + ) s f q ( x ) = 1 0 0 0 x i ! + 1 0 0 x ；一x 3 = 0 c 2 ( x ) = 1 0 0 x ? + 4 0 0 x 2 2 + x 3 0 0 1 = 0 p - - ( o 1 ，0 1 ，0 1 ) r ( 8 ) m i n 厂( x ) = ( 五一x 2 ) 2 + ( x 2 + x 3 2 ) 2 + ( 心一1 ) 2 + ( 毛一1 ) 2 s j 五+ 3 x 2 4 = 0 恐+ 毛一2 黾= 0 一= 0 x o - - ( 2 5 ，0 5 ，2 ，一1 ，0 5 ) 7 图2 3 测试函数1 f i g u r e2 3t e s tf u n c t i o n1 1 6 第2 章预备知识 图2 4 测试函数2 f i g u r e2 4t e s tf u n c t i o n2 图2 5 测试函数3 f i g u r e2 5t e s tf u n c t i o n3 。：，彭，等，；， 图2 6 测试函数4 f i g u r e2 6t e s tf u n c t i o n4 ，| 移弘弘黔矿歹骆。钆弘彩免貉瓢雾；。轧”，?勘。务，：，。、，： 1 卜线性等式约束优化问题的信赖域滤子算法研究 图2 7 测试函数5 f i g u r e2 7t e s tf u n c t i o n5 图2 8 测试函数6 f i g u r e2 8t e s tf u n c t i o n6 图2 9 测试函数7 f i g u r e2 9t e s tf u n c t i o n7 第2 章预备知识 图2 1 0 测试函数8 f i g u r e2 10t e s tf u n c t i o n8 1 9 - f 线性等式约束优化问题的信赖域滤子算法研究 2 0 第3 章两种非单调的信赖域s q p 滤子算法 第3 章两种非单调的信赖域s o p 滤子算法 考虑到非单调策略在信赖域s q p 滤子算法中的成功应用本章提出了应用两种不 同非单调技术的非单调信赖域s q p 滤子算法，并证明了两种算法的全局收敛性和超线 性收敛性数值实验表明这两种算法是有效的 3 1 引言 2 0 0 9 年，k es u ，d i n g g u op u t 6 1 ，分别对于约束违反度和目标函数的实际下降量，应 用非单调策略，采用非单调格式的滤子形式： rm ( t ) 一i1 办( x ) 哳m 酬a x 咿。魂一，或m ) m a xif ( x k ) ，萎2 k r f ( x k - ，) p ( 工) 这里，0 ，m ( k ) - i ，并且0 m ( k ) _ 0 ，初始对称矩阵h o r “”初始化滤 子f = ( h o ，厶) ，令七= o ，m ( 后) = o ；o 户 1 ，o y 1 ，0 五l ， 0 r o 1 r 2 ，m 1 步l 计算五，反，c k ，乙如果j l 或| j + 魂 s ，停止 步2 分别对子问题( 3 2 ) ，( 3 3 ) 进行求解，求得群，令以= 碟+ 研 步3 测试试探步是否被算法接受 计算办( 稚+ 以) ，f ( x k + 以) ，通过( 3 4 ) - ( 3 5 ) 式所示的滤子形式来判断试探步的 可接受性如果