（计算数学专业论文）一种自适应过滤信赖域算法及其应用.pdf

题目：一种自适应过滤信赖域算法及其应用 摘要 信赖域方法对于无约束优化问题的求解，关键问题在于对信赖域子问题的求 解，但对于信赖域子问题的求解，信赖域半径的选取起及实验点的选取对于整个 问题的求解起着非常重要的作用。一方面在标准的信赖域算法中，迭代点列是单 调下降的，对于一些坏条件的问题，会出现收敛非常缓慢的情况；另一方面，传 统信赖方法中对于信赖域半径。的选取一般采用人为规定的规则进行修改而与 和毋无关，而信赖域子问题又与繇和忍有着密切的联系，因此依照传统的信 赖域半径的选择我们并不清楚是否一定适合算法本身，这样必然会降低算法的效 率。 针对上述两个问题，本文首先引入了过滤技术，加入过滤技术可以加大实验 点工：被接受的几率。同时对于信赖域半径采用自适应的选取办法，使得信赖域 半径与繇和b 密切相关，以求对于传统信赖域算法的改进。 与此同时讨论一类仅含有线性约束条件的优化问题，在每次迭代过程中，用 二次近似模型近似目标函数，从而构造一个子问题，以便于确定迭代方向对每 个子问题求解时引入一组共轭方向，将子问题可以转化为一个线性规划问题和一 个一维约束优化问题为了保证算法的总体收敛性，应用信赖域算法代替维搜 索，确定下一个迭代点 关键词： 信赖域，自适应，过滤，线性约束 a b s t r a c t t r u s tr e g i o nm e t h o df o rs o l v i n gu 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 ， t h ek e y p r o b l e mi st ot r u s tr e g i o ns u b p r o b l e m s ，b u tf o rs o l v i n g s u b p r o b l e m s ，t h es e l e c t i o no ft r u s tr e g i o nr a d i u sa n dt r yp o i n tf o rt h e e n t i r ep r o b l e ms o l v i n gp l a y sav e r yi m p o r t a n tr o l e h a n di nt h es t a n d a r d o ft h et r u s tr e g i o na l g o r i t h m ，t h ei t e r a t i o ni sm o n o t o n o u s ，f o rs o m eb a d t h ed e c l i n eo ft h ep r o b l e m ，c a na p p e a rt h ec o n d i t i o no fc o n v e r g e n c ei s y e r ys l o w l y ：o nt h eo t h e rh a n d ，t h et r a d i t i o n a lm e t h o do ft r u s ti nt h e t r u s tr e g i o nr a d i u sf o rs e l e c t i n gr u l e so ft h ep r o v i s i o n sf o rg e n e r a lu s e b u tw i t hg ka n d 最n o t h i n g ，b u tt r u s tr e g i o ns u b p r o b l e m sh a s t h ec l o s e r e l a t i o nw i t h g ka n db k 。t h e r e f o r ea c c o r d i n gt ot h et r a d i t i o n a lt r u s t r e g i o nr a d i u so ft h ec h o i c ew ed o n tk n o ww h e t h e rf o ra l g o r i t h mi t s e l f ， t h i sw il lr e d u c et h ee f f i c i e n c yo ft h ea l g o r i t h n l 研i e wo ft h ea b o v et w op r o b l e m s t h ep a p e rf i r s t l yi n t r o d u c e s f ii t r a t i o n ，j o i nf i l t e rt e c h n o l o g yc a ni n c r e a s et h er i s ko ft r yp o i n t a c c e p t e d a tt h et r u s tr e g i o nr a d i u su s i n ga d a p t i v es e l e c t i o nm e t h o d ， m a k i n gt r u s tr e g i o nr a d i u sc l o s e l yr e l a t e dw i t hg a n db ，i no r d e rt o i m p r o v et h et r a d i t i o n a lt r u s tr e g i o na l g o r i t h m am e t h o dw a sp r o p o s e dt os o l v ec 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 sw i t h 1 i n e a rc o n s t r a i n t s a te a c hi t e r a t e ，t h eo b j e c t i v ef u n c t i o nw a sa p p r o a c h e d b yaq u a d r a t i cm o d e lf u n c t i o nf o rs e a r c h i n gt h ei t e r a t e dd i r e c t i o na n d as u b p r o b l e mw a sc r e a t e d t h es u b p r o b l e mw a st r a n s f o r m e dt oa1 i n e a r p r o g r a m m i n ga n dao n e 。d i m e n s i o nc 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 mi nt h i s p a p e r ，af i l t e rt r u s t r e g i o nm e t h o d sw h i c hw e r er e p l a c e db y1 i n es e a r c h m e t h o d sw e r ea d o p t e dt oa s s u r et h eg l o b a lc o n v e r g e n c e k e y w o r d s t r u s t r e g i o nm e t h o d s ， s e l f - a d a p t i n g ，f i i t e r ，1 i n e a rc o n s t r a i n t i i 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。 本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研 究所等机构将本学位论文收录到中国学位论文全文数据库或其它 相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名：答鋈塞 指导教师签名： ) 呻年月印 上咋厂月o f t 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，本论文 不包含其他人已经发表或撰写过的研究成果，也不包含为获得西北大学或其 它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：霹渤 2 叫年石月7e l 西北大学硕士学位论文 1 1 研究背景 第一章绪论 信赖域算法为数值优化中一种基本的方法，该算法的一个显著优点是其稳定 的数值性能，它具有强收敛性i l l ，不仅能够很快解决良态问题，也能有效求解病 态问题，是近2 0 年来一直是非线性优化研究的热点问题之一【2 l 。 信赖域方法就其思想萌芽而言，可以追溯到二十世纪四十年代对最小二乘问 题的研究，但作为一种求解优化问题的系统方法起源于p o w e l l l 9 7 0 年的工作【3 1 ， p o w e l l 首先提出了一个求解无约束优化问题的算法，他提出了一个求解无约束优 化问题的算法，该算法在每次迭代式时要求新的迭代点与当前迭代点之间的距离 不超过某一控制量控制步长实质上等价于以当前迭代点为中心的一个邻域内对 一个近似于原问题的简单模型的求极值利用这一技巧的方法。信赖域的大小通过 迭代逐步调节，一般的说，如果当前的迭代模型较好的逼近原问题，则信赖域可 以扩大，否则信赖域应该缩小。p o w e l l 提出的信赖域算法的基本框架，并且于 1 9 7 5 证明了算法的收敛性，就构成了经典的信赖域算法，并且沿用至今f 4 l 。后 来在研究中发现信赖域方法的基本技巧在一定意义下等价于求解非线性最小二 乘问题的l e v e n b e r g m a r q u a d t 方法。 1 9 8 2 年，国际著名优化专家f l e t c h e r r 提出了用信赖域算法求解复合非光滑 优化问题，他给出了一个模型算法，并且在模型二次函数的h e s s e n 矩阵一致由 界的假设下证明了该算法的全局收敛性”。 在我国，优化专家袁亚湘教授在收敛性研究方面得到了一系列的成果，并被 国际上多次被引用。他在仅要求近似h e s s e n 矩阵满足l l 鼠f 0 | j d 临a i 其中纯( d ) 称为近似于f ( x k + d ) - f ( x k ) 的锥模型，皿为( x ) 在t 点处近似 于f ( x ) h e s s e n 矩阵的对称矩阵。 若吼= 0 ，则锥模型可以简化为通常所见到的二次函数模型，因此锥模型也 可以看为是二次函数模型的扩展。 对比于二次函数模型，锥模型具有许多的优点l 1 0 1 ： 1 当目标函数的非二次性态较强或者曲率变化较为剧烈的函数，二次函数 模型在极小化目标函数过程中容易生成不太好的预测结果。然而由于锥 模型在形式上具有较好的自由度，在近似目标函数的结果上要优于二次 目标函数。 2 二次函数模型并没有把对于算法结果有较大影响的先前迭代点的函数信 息加入到新的迭代过程中，而锥模型则把当前迭代点的函数信息和之前 迭代点的信息加入到了模型中来，包含了关于迭代点更多的信息。 3 锥模型和二次函数模型相比，其全局收敛性和局部收敛性不弱于二次函 数模型。 - 2 - 西北大学硕上学位论文 1 2 2 非单调信赖域算法 利用非单调性策略这一技巧提出了一类具有强收敛性的非单调信赖域算法 】，该算法的数值实验表明：非单调性策略对相当部分实验函数可以明显加 快算法在其最优点附近的收敛速度，得到精度更高的最优解l j 2 。 1 2 3 结合近代优化算法的信赖域算法 目前，已有学者将具有并行性能的遗传算法用于求信赖域子问题的解，并建 立起一种具有全局随机搜索性能的信赖域遗传算法f 1 3 】f l4 1 。，该算法将遗传算法和 信赖域方法进行了结合。利用了遗传算法繁殖算子的随机性和信赖域方法求解二 次优化问题的高效性，该算法能够克服信赖域方法的缺点同时能够有效求解一类 欺骗性问题。 另有其他学者把信赖域技术引入p s o 算法中进行惯性权重的动态调整，提出 一个新的微粒群优化算法一基于信赖域技术的局部收缩的微粒群算法】。算法 ( n p s 0 ) 保持了p s o 算法结构简单的特点，改善了p s o 算法的全局寻优能力， 提高了算法的收敛速度和计算精度。 1 3 本文主要工作和内容 本文立足于求解无约束问题，加入了过滤技术，并对信赖域半径采用自适应 调整，以求对于算法的改进。本文主要内容包括：介绍了信赖域算法的基本理论； 并对过滤技术进行了描述；构造自适应过滤信赖算法，并对自适应过滤信赖域算 法进行了收敛性分析。最后讨论一类仅含有线性约束条件的优化问题，在每次迭 代过程中，用二次近似模型近似目标函数，从而构造一个子问题，以便于确定迭 代方向在每个子问题求解时引入一组共轭方向，子问题可以转化为一个线性规 划问题和一个一维约束优化问题为了保证算法的总体收敛性，应用信赖域算法 代替维搜索，确定下个迭代点证明了算法产生的点列如有聚点，则必有一 个聚点是原问题的k - t 点 - 3 - 西北大学硕士学位论文 2 1 经典的信赖域算法 考虑无约束优化问题 第二章信赖域算法 m i n f ( x ) ( 2 1 ) 其中f ( x ) ：r ”_ r 1 为二阶连续可导函数。假设t 为某个迭代点，通常我们利用 某个模型函数m k ( d ) 在t 的某个邻域内近似目标函数f ( x k + d ) 。如果函数的 光滑比较好，那么函数与目标函数在迭代点附近的误差就比较小。尽管这两个函 数在较远点的性能可能有所差异，但是在t 的某个邻域内完全可以通过极小化 m ；( j ) 寻找目标函数的改进点。即通过构造迭代点的信赖域，寻找一个薪的改进 点，然后在改进点附近构造另外一个信赖域，寻找更好的改进点；这个过程循环 往复，直至求出满足一定要求的优化问题的近似解【1 11 1 6 1 。 在信赖域内寻找改进点，需要借助于某个模型函数。一般的，人们把模型 函数取为二次函数，信赖域取为球型i ir i l l 2 a ，其中a o 为信赖域半径2 1 插1 。 于是信赖域问题在迭代中涉及的问题( 子问题) 可以描述为： m i n m k ( d ) = 五+ ( v f t ) 7 d + 昙d ，最d ， ( 2 2 ) 盯 i i d i l 2 a 其中五，夥，忍分别为( 工) 在以的函数值、梯度和h e s s e 矩阵或者它的 某个近似矩阵。 若毋= o ，则( 2 2 ) 的最优解为 喀咄高 ( 2 3 ) 这对应着非精确搜索的最速下降法，其中移动方向为一夥，移动步长等 于。川可吣 - 4 - 西北大学硕士学位论文 若b = v 2 厂( 以) ，则子问题( 2 2 ) 对应着信赖域n e w t o n 方法i 舶。 若最取拟n e w t o n 矩阵，并按照b f g s 或者d f p 等校正公式进行修正，则 得到信赖域拟n e w t o n 方法【 1 6 1 。 在实现信赖域策略时，人们一般是通过比较迭代过程中模型函数和目标函数 的下降量，确定下一个迭代过程的信赖域半径，记 实际下降量： a r e d k = ( 以) 一( 而+ 哦)( 2 4 ) 预期下降量： p r e d k = m k ( 0 ) 一( 盔) 下降比率： 反= 等 ( 2 5 ) ( 2 6 ) 若办0 ，则( ) 厂( 坼+ 喀) ，说明可以拒绝当前的改进量以，并且需要 减小信赖域半径。 若屏接近于l ，则在当前的信赖域内，模型函数较好的接近了目标函数，这 样在下次迭代过程中可以适当地增加信赖域半径。 无约束问题信赖域传统算法1 l1 2 1 1 1 4 】： s t e p l ：初始化 给定初始点x 。, er ”，对称矩阵风尺“”，最大信赖域半径五 0 ；取初始信 赖域半径。( 0 ，五) ，容许误差s 0 ，参数7 7 o ，l 4 ) ；k = 0 s t e p 2 ：收敛性检验 若i i 夥1 1 2 - r x k + j2 1 以，如果, o k 7 7 【以 ，则未 s 7 7 新的信赖域半径为： a 女+ l2 1 1 d , 1 1 4 ，如果岛 三，l | 喀归色 a t ，其他 s t e p 4 ：校正矩阵 令v f “1 = 哪雄+ ，) ，修正矩阵辟得到新的对称矩阵最卅；令后= k + l 转s t e p 2 算法结束。 2 2 子问题求解方法 求解信赖域子问题的方法很多，分为精确求解和近似求解。首先给出一个定 理，其描述了信赖域子问题最优解的特征。1 1 6 1 定理2 1向量d 是信赖域子问题( 2 2 ) 的最优解当且仅当存在实数a 0 ， 使得下面的条件都成立： ( b + 旯j ) d = 一v 厂， ( 2 7 ) 五( 扣l i d 1 1 2 ) = 0 ， ( 2 8 ) 嚣毒越) 是半正定矩阵， ( 2 9 ) 该定理实质揭示了求解子问题的算法。可以看出，或者名= 0 满足条件( 2 7 ) ， ( 2 9 ) ，使得| jd | j ：，或者对于比较大正数名 0 ，矩阵( b + 彳，) 正定，并且 d ( a ) = 一( b + ；t 1 ) - 1 v f ( 2 1 0 ) 从而存在某个万 0 满足方程 l l d ( a ) f i ：= a ( 2 1 1 ) 求解子问题( 2 2 ) 的目的是通过对迭代点在信赖域内进行最大限度的改进， - f i - 西北大学硕士学位论文 保证迭代序点列具有较好的收敛性能。为了保证信赖域算法的全局收敛性，在理 论上只需要找5 0 - 个合适的近似解，使得模型函数有充分的下降量即可i 引p 4 。 2 2 1d o g i e g 算法1 2 1 1 1 7 1 假设子问题( 2 2 ) 的反正定，则当模型函数m ( d ) 无约束最小点为 以= - b v f 。当| l 以i i ，则寻找步长f o 使得l l4 + f 咯 1 ：= ，并且令近似解d = 反+ q ， 算法停止；否则转s t e p 3 s t e p 3 ：迭代改进 令g = g + b 咯，若l lg 1 1 2 引ig 。| | ，则近似解d = 以+ l ，算法停止；否 则，令 蒯酬2 k k 幢| j 2 气+ l = 一g i + l + 展气 令k _ k + 1 ，转s t e p 2 2 3 信赖域问题的收敛性 一般情况下我们希望信赖域子问题( 2 2 ) 的近似解d 对应的模型下降量能够 - 8 - 西北大学硕士学位论文 满足如下的关系式【2 1 ： 忉( 0 ) 嗍( 面- q 2m i n ( ，潞) ，其中c je ( 0 ，1 】 ( 2 1 6 ) 引理2 2 信赖域子问题( 2 2 ) 的c a u c h y 点以满足( 2 1 6 ) ，其中q ：i 1 。 对于2 2 1 ，2 2 2 ，2 2 3 介绍的d o g l e g 算法，二维子空间极小化法和s t e i h a u g 算法来说，由于求解出来的近似解d 满足m ( d ) 聊( 以) ，则有 r e ( o ) 一肌( 矛) r e ( o ) 一m ( d a ( 2 1 7 ) 则这些近似解孑都满足( 2 1 6 ) 1 1 1 定理2 4 ：对于信赖域算法，若下面条件成立： ( 1 ) 函数厂是l i p s c h i t z 连续可微的，即存在l 0 ，使得少r ”，有 v f ( x ) - v f ( y ) 临l | l x - y l l ； ( 2 ) f 在水平集s = x i f ( x ) f ( x o ) ) 上有下界。 ( 3 ) 信赖域子问题( 2 2 ) 的近似解哦满足条件( 2 1 6 ) ，并且存在厂1 ， 使得| i 攻1 1 2 雄。 则下面的条件成立： ( 1 ) 在信赖域算法中控制参数7 7 = 0 时，i i mi n f l l 1 1 2 = 0 ； f + o o ( 2 ) 在信赖域算法中控制参数7 7 ( o ，1 4 ) 时，j i m = 0 。0 6 1 * - - - k o o 西北大学硕士学位论文 第三章自适应过滤信赖域算法 3 1 信赖域子问题 仍然考虑无约束问题 m i n f ( x ) 其中f ( x ) ：r ”一r 1 为二阶连续可导函数。 ( 3 1 ) 信赖域问题通过求解如下信赖域子问题得到实验步矾 m i n 州) = 彩+ p 聃 ( 3 2 ) j j j i d 2 a i 其中g 。和风分别为( z ) 在t 处的梯度和近似h e s s i a n 矩阵。 3 2 过滤算法 在标准的信赖域算法中，迭代点列是单调下降的，对于一些坏条件的问题， 会出现收敛非常缓慢的情况。因此，提出了非单调的技术来加快实际计算中的收 敛速度。 过滤技术( f i l t e r ) 是首先由f l e t c h e r 在1 9 9 7 年提出来的【1 8 j ，并迅速在约 束优化领域取得了长足的进步。后来过滤技术又进一步发展到一般无约束问题 上，取得了较好的数值结果1 1 9 1 。 在标准的信赖域算法中只有当岛 r 时才接受新的改进迭代点= 气+ 盔， 加入过滤技术可以加大实验点被接受的几率。 对于过滤的定义是基于对优势的定义，我们把梯度盯( x ) 记为分量的形式， v f ( x a = g = ( ( 坼) ，( 矗) ，岛( 毛) ) r = ( 1 ，颤2 ，。) 7 对于任意给的两个点 五、恐，当且仅当 lg i 0 ：取初始信 赖域半径。( o ，五) ，容许误差占o ，参数，7 【o ，1 4 ) ；p = 0 ，k = 0 。初始化 过滤集f 为空集 s t e p 2 ：收敛性检验 若l l v f l | ：，则t 为近似最优解，算法停止； s t e p 3 ：子问题近似求解 求解子问题( 3 2 ) 得到可能的移动量破。记= 五十4 ； s t e 4 ：实验点检验 计算羼= 嬲 若级 7r 则t + l = ，转s t e p 6 ： 否则计算g ( ) ， 若被过滤集，所接受，则诈卅= ，更新过滤集f ，把加入到过 滤集f 中，转s t e p 6 ： 否则k = k + 1 转s t e p 4 西北大学硕上学位论文 s t e p 5 ：信赖域更新 p = p + l ，新的信赖域半径为：a 。= c p l l g 。l l q ，转s t e p 3 ； s t e p 6 ：模型参数修正 令夥“1 = v f 0 ，使得v x ，y r ”，有 f l v f ( x ) - w ( y ) i i l ij 工一y u ；2 5 1 ( 3 4 ) a 3 ：序列 b 一致有界。即对于任意的七，存在两个正整数所，刀使得l l 忍1 1 - ，7 证明：假设算法在s t e p 3 s t 印5 之间无限次循环，则存在正整数k ，使得 i l g k0 占，且对于所有的正数都有以 1 7 。 定理3 3 假设a l a 4 成立，算法或有限步终止，只有有限的的实验点加入到 过滤集中，或者生成一个无穷点列 矗) 使得 ! i m 。i n f 蚓g = 0 - ( 3 1 0 ) 证明：若有有限实验点加入到过滤集中，令k i = kl 以加入过滤集中 ，由过滤集 的定义可得： 名| i 岛l i q 岛。，i - i 吕( ) i 由假设可知 吕( ) ) 有界而且存在 g ( ) ) 一个子列收敛。不失一般性，我们假设 一1 5 西北大学硕士学位论文 g ( 耳) ) 收敛，则当k 寸o o 时，i 昌，j - i 吕( ) 卜0 。 因此可得 受i n f | | 繇i l = o 。 若算法不能有限步终止，利用反证法。 假设! 受i n f j f 繇j | = o 不成立，贝, u3 e o o ，v k ，使得l l l l 民。 另一方面屏 r l ， ( 气) 一f ( x d ) - , ( r l p r e d , ) = 力( 纯( o ) 一纯( 反) ) 】 加川m i n ( “) 】 ( 3 1 1 ) 芝2 1 2 8 0m i n ( t ，静 由于 f ( x k ) ) 单调下降，可知一om 1 ，这又与定理3 2 相矛盾。因此假设不成 立。 综上可得算法或有限步终止，只有有限的的实验点加入到过滤集中，或者生成一个无穷点列 矗 使得! 受i n f l l 4 = o 3 6 数值实验 以下测试函数均来源于参考文献【2 8 】，程序语言为m a t l a b 7 0 所有终止条件为：i i g , i f 1 0 。6 在自适应过滤信赖算法中初始矩阵鼠= j ，c = o 7 5 ，p = o 7 5 ，= 0 7 5 ， r = 0 7 5 。 在下表中： d i m ( d i m e n s i o n ) ：测试函数的维数： ni ( t h en u m b e ro f i t e r a t i o n s ) ：迭代次数； nf ( t h en u m b e ro f f u n c t i o ne 妇l u a t i o n s ) ：函数值的计算次数； ng ( t h en u m b e ro f g r a d i e n te v a l u a t i o n s ) ：梯度的计算次数。 一1 6 西北大学硕士学位论文 溺试函数m r o s e b e a l e h e l i x g a u s s b o x s i n g b i g g s l i n l i n l i n t r i g t r i g 经典算法 ( n l 憎f 烈g ) 3 1 6 2 3 2 1 5 2 5 1 6 2 7 5 8 2 7 自适应过滤信赖算法 ( n i 卜限n g ) 2 8 6 0 2 9 1 5 2 5 1 6 2 4 5 5 2 6 4 7 5a | 1 | s 3 3 4 2 3 33 5 4 4 3 5 3 6 巧6 8 63 4 5 2 3 5 4 1 4 8 4 14 l 4 8 4 l l 3 2 l 3 2 1 3 2 15 2 5 1 9 l 3 2 1 3 2 1 3 2 1 3 2 l 1 5 4 4 4 8 4 54 3 4 6 4 3 ( 表1 改进算法与经典算法实验数据对比) 通过实验数据对比，改进后的算法在迭代次数、函数值计算次数及梯度值计 算次数上都有一定改进。由此可知该算法具有一定的有效性，这种自适应过滤信 赖算法是可行的。 一1 7 2 2 3 3 3 4 6 2 卯 姗 3 弼 西北大学硕士学位论文 第四章线性约束优化问题基于信赖域的求解方法 4 1 问题的描述 考虑卜面的优化i 司题 m 。r i n 。f ( x ) ，s j q 7 x = 匆，i c e( 4 1 ) a j r x 匆，f 1 其中扛) 是二次可微的实函数，v 2 厂o ) 对称正定，e 是等式约束指标集，i 是不等式约束指标集。当( z ) 是一个二次函数时，问题( 4 1 ) 就变成了一个二次规 划问题，本文二次规划问题的求解思路出发，对其进行了一定的改进，并对该问题 进行的相关讨论，构造出了i h - 题( 4 1 ) 的求解思路2 9 1 。 4 2 问题的分析 4 。2 。1 目标函数t a y l o r 展开。 取x k r ”，将厂( x ) 在附近作t a y l o r 展开2 1 ： ( j ) = f ( x k ) + v 7 厂( 吒) ( x - - 曩) + i 1 ( x 一坼) 7 v 2 厂( 以) o x k ) + o ( 1 1 x 一毛0 2 ) ( 4 2 ) 记s = x - - x k ，g i = v f ( 砟) ，b k = v 2 f ( x k ) ，五= f ( x k ) ，令 吼( s ) = 五+ r j + 去s 7 b s ( 4 3 ) 二 则级( s ) 是( x ) 在五处的近似，称吼( s ) 是，( x ) 在t 处的二次近似模型函数。 4 2 2 子问题的求解 构造子问题： m i n q , ( s ) ：f t + g ? s + s t b t s s ，q 7 s = 6 ，f e ， ( 4 4 ) q 7 ( x k + s ) 6 ，i 1 易看出，问题( 4 4 ) 是一个二次规划问题，沿照文献 2 9 1 q b 对于二次规划问题的求解 一1 8 一 西北大学硕士学位论文 方法，引入一组共轭方向：设h ? ，h ! ，群是一列关于b ( 最为对称正定矩阵) 共轭的非零向量。即对于任意的i ，j 1 ，2 ，n ) ： 当i 弓时，( 研) 最彤 0 ； 当i j 时，( 研) t 叫= o a 现给定以r ”，令气o ，口= ( 口。，瓯。) 。当s = q h ；】乙时，由 j = l t a y l o r 级数展开得： q k ( s ) - q k ( 0 ) = q k ( 0 ) + v t q k ( 0 ) s + 去s r v 2 q k ( 0 ) s q 女( o ) 。 。 ( 4 5 ) = 【耻g 。r h ；】z 。+ 【i i i , ( 耻) 2 ( ( h ：) 7 统h j hj j 乙2 易知【圭喜( 啪2 ( ( h ；心咖t 2 狐 对于v ，v z k ， q k 。所有吼( s ) 一吼( o ) 0 的必要条件是： 【o ! j ( k g , r h 拟o ( 4 6 ) 为此构造下面的线性规划问题舯1 ： 吧i n 妒一g kh ； “矾蛳= 匆，f e ， ( 4 7 ) 卢l a z t ( x 。+ 铲h ；) 6 ，f 户l 若问题( 4 7 ) 无解，则终止计算，原问题无解；否则可以得到最优解( 若有无穷 多个解，任取其一即可) 记作& = ( 画，或) 。若得到的最优值为正，则终止计 算；否则，我们可以得到一个可能的下降方向岛仲h ：。现在利用参数乙确定最 j 皇1 终的迭代方向。 令q , ( s ) - q k ( 0 ) 0 ，得 一1 9 西北大学硕士学位论文 令z = 【0 ，一 z 一 n 尸 掣j g k r h ； ( 龟耻) 2 ( ( 可) t 忍群) 产1 龟耻7 h ； ( 秽) 2 ( ( h ；) t b k h ；) 卢1 】，现构造如下一维约束优化问题： m a x z k “( x 。+ z k 龟舛) 匆，f ， 0 z t 一 j = l 吃g k r h ； 卢l n ( 色) 2 ( ( h ：) t b k h ：) ( 4 9 ) ( 4 8 ) j 。l 在问题( 4 9 ) 中，因为目标函数为严格单调递增函数，所以该问题只可能 是无解或者有唯一最优解，并且最优解只可能在边界处取得现将等式约束进行 整理得： 矽彰6 - o ( x , ，i e i j = l c t ，定义指标集，+ 为，+ = ， 记z ： =一 ( 4 1 0 ) 一彰叫k o ，f ， ，则由式( 4 1 0 ) 可得 = ii 乙单 矿& h j j = l b i 一菌x k 矿彰”嘭 j = l 无解，否则记 ( i ，+ ) + o oi ( i i + ) j 弘s u p ( o z ， ，、 若ln z ；l b “+ )7 l n z = ) c t t ，同理，定义指标集，一为厂= ， n z = ，则表示问题( 4 9 ) r 耖嘭姐川 ，则由式 ，皇ll - 2 0 - 西北大学硕士学位论文 可得乙j 立( f 厂) 彳彤”霉 = 1 晦m i n h 赫 喜( & 孵( ( 矿) 7 n ，k ) ( & 孵( 矿) 1 ， ，0 看筇= 0 ，则1 日j 题( 4 9 ) 尢角竿 综上，则乞= m i l l k ，筇) 为问题( 4 9 ) 的解则下一个迭代点为 k 。吨+ ( 耖嘭卜尸i 注：( a ) 在问题( 4 9 ) 中略掉了下面的约束条件： 矿( 乙嘉掣嘭) - 0 c 眦， 这是因为觏是问题7 ，的解，则一l 喜彰) = o c ，一定成 立 ( b ) 当确定了三。，五。后，在搜索方向窆彰t 彰上，目标函数在屯+ 。处取得 4 3 引入过滤信赖域算法 为了保证算法的总体收敛性，引入信赖域算法我们把第三章所介绍的自适 应信赖域算法加入到该问题中来。 算法描述： s t e p l ( 初始化) 给定初始迭代点d ，精度要求s 0 ，迭代计数器七= o ， 初始信赖域半径0 - - l g o l l s t e p 2 ( 找迭代方向) ( 1 ) 计算，毋，构造共轭方向研，厅! ，磁； ( 2 ) 求解线性规划问题( 4 7 ) ，如果有非负最优值，则终止迭代，墨为最 一9 1 西北大学硕士学位论文 优解；否则，可以得到最优解为舀= ( 舀：，碰，磁。) 进行如下一维搜索 s t fx k + 口h ； 龟，f ， 荟矽彰 ( 4 1 1 ) 0 磊一上兰一 砉( 州 ( 彤) t 忍彤 隆”喇卜 得到最优解乏，记第1 j 次迭代方向为喀= l 彰”嘭i 乏，r = x k + 矾 ，= l s t e p 3 计算羼：黧， p r e d 忱。j 若风 r ，则五，= x ：，转s t e p 6 ； 否则计算g ( ) ， 若被过滤集f 所接受，则以+ 。= ，更新过滤集f ，把加入到过滤集f 中，转s t e p 6 ； 否则k = k + l ，转s t e p 4 s t e p 4 ：信赖域更新 p = p + l ，新的信赖域半径为：a 。= ，i i g , l l q ，转s t e p 3 ； s t e p 6 ：模型参数修正 令v f “l - 趴t + 。) ，修正矩阵盈得到新的对称矩阵b + 。； 令k = k + l 转s t e p 2 算法结束。 4 2 收敛性分析， 定理设厂( x ) 在可行域d 上连续可微，羼一致有界，即存在m 0 ，使对任 意的k ，i i b , i i - o ，使有无穷多个k ，a 万且 岛o 2 5 成3 f f _ 记瓦= k la - g h p k o 2 5 ) ，不妨设! 骢以。舅，根据假设，i 不是原问题的k t 点，故j = 0 不是问题( 4 1 2 ) ： m 瞄i n ，g ( i ) t s + o 5 m i i j i i ； s t 矿s = o i c e ( 4 1 2 ) 彳( 孑+ s ) 包i j 俐。o 5 d 的解 记i 是式( 4 1 2 ) 的解，则有7 7 = g o ) t y + o 5 m i i 了u i o 对所有 k - a o 充分大的k k 。都成立 利用q t ( o ) 一q 。( s 1 ) - - 0 5 r o 和风0 2 5 ，即知f ( x k ) - f ( x 川) - 8 17 7 o 对所有 充分大k k 。的均成立 由于2 粤( 屯) - - - ( i ) ，f ( x k ) 一f ( x k + 。) 一8 叫r o 不可能对无穷多个丘成立此 矛盾说明了只要定理不成立，则必有j i i l l a 。= 0 如果j 蚰t = o 成立，则必存在一个子序列k 。，使得p k 0 2 5 ( v k k ，) 不妨设j 囊黾= 圣根据假设，叠不是k - t 点，令；是问题 r a 础i n 。g ( 曼) tj + o 5 圳j i i ； s t a 1s = 0 i e 矿( 曼+ s ) 匆i 1 。1 的解，则必有， = g ( 叠) 7 ；+ o 5 m 睁4 ； o 。 由于；是问题 - 2 3 西北大学硕士学位论文 r a 斌i n 。g ( 讪+ o s m i 5 嵯 j j a j t $ = 0 f e ( 4 1 3 ) 圣 a t ( y c + s ) 厶f ， 。- a i 的可行点，则只要。墨l ，就有g ( d t ；+ o 5 m i i i i i 历，则当。1 时i 是问题 ( 4 1 3 ) 的解, i j 用胤l i m x k = 立，g ( 主) 7 j + o 5 肘； a k 矛，即知 i 。 g i ( o ) 一吼( 墨i ) - - o 5 私i ( 4 1 4 ) 对所有充分大足k 。的都成立由于厂( x ) 连续可微及舾。 _ 一致有界，有 q k ( 0 ) - q 。( s 。) 厂( 坼) 一( ) + d ( 1 i s 。0 ) ( 4 1 5 ) 从式( 4 1 4 ) 及式( 4 1 5 ) 可证! 囊办= l ，这显然与办 o 2 5 ( v k x ，) 相矛 量_ z - 2 4 - 西北大学硕士学位论文 第五章展望 作为传统优化计算的重要算法之一，信赖域算法近2 0 年来一直是非线性研 究的热点和关注点。并且有了较快的发展。但是仍然在一些新的领域可以继续进 行新的研究： 1 除了与遗传算法进行结合的算法已经有了一定的研究，但是与其他近代 优化算法，比如蚁群算法和神经网络等的结合研究还比较少，仍有待进 一步的研究。 2 信赖域算法的基础在于对于二次模型的构造和信赖域半径的选取方法， 对于二次模型除了传统的利用泰勒展开的方法等到和锥模型，还没有其 他的模型进行对比改进，而对于信赖域半径的选取。对于自适应的半径 选取办法，大部分只是对其利用数值方法进行了验证也缺乏完整的理论 证明。 3 信赖域算法对于求解小规模问题一般比较好，但是对于大规模及坏的问 题的求解任然需要进步的进行改进。 - 2 5 - 西北大学硕士学位论文 参考文献 【1 】袁亚湘，孙文瑜，最优化理论与方法北京：科学出版社，1 9 9 7 ，5 5 9 - 5 9 9 。 【2 】j o r g en o c e d a l ，s t e p h e nj ，n u m e r i c a lo p t i m i z a t i o n 北京：科学教育出 版社，2 0 0 6 ，6 4 - 1 0 0 。 【3 】欧宜贵，非线性优化问题的信赖域方法研究综述，海南大学学报自然科学版， 2 0 0 3 ，2 1 ( 3