（应用数学专业论文）非线性约束优化问题的过滤线搜索两块校正序贯既约hessian方法.pdf

中文摘要 摘要 最优化理论与方法是一门充满活力的学科，其主要目的是研究如何从某些实际问题 的众多可行方案中找出最优解。非线性规划作为最优化理论的一个重要分支，随着社会 的发展和科学的进步，尤其是在计算机技术突飞猛进的背景下，在金融、贸易、管理和 国防军事等许多领域有着日益广泛的应用。 近来，f l e t c h e r 和t e y t r e r 【4 】提出了过滤方法。该方法可以代替传统的罚函数方法， 用来保证非线性优化问题的全局收敛性。该方法的主要思想是，将一个带约束的单目标 规划问题解释为一个双目标规划问题，在每次迭代中，改进目标函数值或者约束违反 度；而传统的罚函数的方法要求改进函数值和约束违反度二者的组合。f l e t c h e r 和l e y f f e r 提出过滤方法的动机是避免在使用罚函数方法时每次迭代都要确定罚参数的困难。同 时，过滤方法还提供了另外一个优点，称之为健壮性。有时，由于试探步过小，可能使 得本次迭代不能够产生足够的改进，影响收敛性，过滤方法此时可以转向可行性恢复阶 段。在可行性恢复阶段，算法试图通过降低约束违反度，找到问题的另一个可行点，使 迭代可以继续进行。 由逐次二次规划方法发展而来的既约h e s s i a n 阵方法是当今求解非线性等式约束优 化问题的重要方法之一，其基本思想是只利用l a g r a n g e 函数的h e s s i a n 矩阵的部分信息 完成迭代，从而大大减少每次迭代中所需的计算量和存储量。g u r w i t z 【3 】3 在总结n o c e d a l 与o v e r t o n 等人工作的基础上，提出了两块校正既约h e s s i a n 阵方法( 简称两块校正算 法) 。两块校正算法的基本思想是利用拟牛顿校正公式分别修正l a g r a n g e 函数的单边 既约h e s s i a n 矩阵中的两个分块子矩阵，从而改善了由n o c e d a l 与o v e r t o n 提出的双边既 约h e s s i a n 阵方法的局部收敛性态。然而，g u r w i t z 的文章中并没有涉及算法的整体收敛 性。 在这些思想的启示下，本文使用两块校正双边投影既约h e s s i a n 方法结合过滤线搜索 策略来解决带有等式约束的非线性优化问题，在确定搜索方向阶段只利用l a g r a n g e 函数 的h e s s i a n 矩阵的部分信息，减少了计算量；使用过滤线搜索方法保证了全局收敛性；为 了改进局部收敛性态，采用二阶校正步，克服m a r a t o s 效应，证明了算法的q 超线性收 敛速率。数值实验的结果表明算法是可行的和有效的，过滤方法有着广阔的发展前景。 关键词：非线性约束优化；两块校正；过滤方法：二阶校正步；整体收敛性；局部收敛速 率。 第1 贞 英文摘要 a b s t r a c t o p t i m i z a t i o n ，w h i c hi sa ne n e r g e t i cs u b j e c t ，m a k e sr e s e a r c ho nh o wt of i n dt h eo p t i m a ls o - l u t i o n sa m o n gm a n yf e a s i b l ep l a n s n o n l i n e a rp r o g r a m m i n g ( n l p ) i so n eo ft h em o s ti m p o r t a n t b r a n c h e so fo p t i m i z a t i o n ，a n dh a sb e e nw i d e l ya p p l i e di nm a n yf i e l d ss u c ha sf i n a n c e ，t r a d e ，m a n a g e m e n ta n dm i l i t a r yr e s e a r c h r e c e n t l y , f l e t c h e ra n dl e y f f e rp r o p o s e df i l t e rm e t h o d ，r e p l a c i n gt h et r a d i t i o n a lm e r i tf u n c t i o n m e t h o d ，a sat o o lt og u a r a n t e eg l o b a lc o n v e r g e n c ei na l g o r i t h m sf o rn o n l i n e a rp r o g r a m m i n g ( n l p ) t h eu n d e r l y i n gc o n c e p to ff i l t e rm e t h o d si st h a tt r i a lp o i n t sa r ea c c e p t e di ft h e yi m p r o v et h eo b j e c - t i v ef u n c t i o no ri m p r o v et h ec o n s t r a i n tv i o l a t i o ni n s t e a do fac o m b i n a t i o no ft h o s et w om e a s u r e s d e f i n e db yam e r i tf u n c t i o n t h em o t i v a t i o ng i v e nb yf l e t c h e ra n dl e y f f e rf o rt h ed e v e l o p m e n to f t h ef i l t e rm e t h o di st oa v o i dt h en e c e s s i t yo fd e t e r m i n i n gas u i t a b l ev a l u eo ft h ep e n a l t yp a r a m e t e r i nt h em e r i tf u n c t i o n i na d d i t i o n ，t h ef i l t e ra p p r o a c ho f f e r sa n o t h e ri m p o r t a n ta d v a n t a g er e g a r d i n g r o b u s t n e s s i ft h et r i a ls t e ps i z eb e c o m e st o os m a l lt og u a r a n t e es u f f i c i e n tp r o g r e s st o w a r das o i u - t i o no ft h ep r o b l e m ，t h ep r o p o s e df i l t e rm e t h o dr e v e r t st oa f e a s i b i l i t yr e s t o r a t i o np h a s e ，w h o s e g o a li st od e l i v e ran e wa c c e p t a b l ei t e r a t eb yd e c r e a s i n gt h ec o n s t r a i n tv i o l a t i o n ，o rt oc o n v e r g et o al o c a lm i n i m i z e ro fi n f e a s i b i l i t yi ft h i si sn o tp o s s i b l e r e d u c e dh e s s i a na l g o r i t h m ，w h i c hi sd e v e l o p e df r o ms 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 g m e t h o d , n o wh a sb e c o m eo n eo ft h ev e r yp o p u l a ra n dm o s te f f e c t i v em e t h o d sf o rs o l v i n gn o n - l i n e a 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 np r o b l e m s r e c e n tr e s e a r c hh a sf o c u s e do nm e t h o d st h a t s o l v es u c hp r o b l e mb yr e c u r r i n ga na p p r o x i m a t i o nt os e c o n dd e d v a t i v ei n f o r m a t i o np r o j e c t e do n t ot h et a n g e n ts p a c eo ft h ec o n s t r a i n t s t h em a i nm o t i v a t i o no fr e d u c e dh e s s i a na l g o r i t h mi s t h a to n l yt h ep r o j e c t e dm a t r i xe n t e r si n t ot h eo p t i m a l i t yc o n d i t i o n sf o rt h en o n l i n e a rp r o b l e ma n d t h i sr e d u c e dt h es i z eo fm a t r i xw h i c hn e e dt ob ec o m p u t e di ne a c hi t e r a t i o n g u r w i t z 【3 】p r o p o s e d t h et w o - p i e c eu p d a t eo fap r o j e c t e dh e s s i a nm a t r i xa l g o r i t h mf o rn o n l i n e a rp r o g r a m m i n g t h e m a i ni d e ao fh e rm e t h o di st op e r f o r mat w op i e c e - u p d a t eo fao n e s i d e dp r o j e c t e dh e s s i a n t h i s m e t h o dm a i n t a i n so n e p i e c eo ft h ep r o j e c t e dh e s s i a na sap o s i t i v ed e f i n i t em a t r i x ，w h i c hi su p d a t e d b yd f p o rb f g sm e t h o d ，a n du s e sb r o y d e n sm e t h o df o ru p d a t i n gt h eo t h e rp i e c e b u tg u r w i t z d i 血tm e n t i o nt h eg l o b a lc o n v e r g e n c e w h i c hw i l lb ed i s c u s s e di nt h i sp a p e r i n s p i r e db yt h ei d e a so ff l e t c h e r l e y f f e ra n dg u r w i t z w ep r o p o s e dal i n es e a r c hf i l t e r t w op i e a eu p d a t eo fr e d u c e dh e s s i a nm e t h o df o rs o l v i n gn o n l i n e a rc o n s t r a i n e dp r o g r a m m i n g i n o u r a l g o r i t h m ，t h es e a r c hd i r e c t i o no ft h el i n es e a r c hm e t h o di so b t a i n e db yt w op i e c eu p d a t eo f r e d u c e dh e s s i a nm e t h o d ，w h i c hr e d u c e st h es i z eo ft h em a t r i xt h a tn e e dt ob ec o m p u t e di ne a c h 第页 英文攮要 i t e r a t i o n f i l t e rl i n es e a r c hm e t h o di su s e dt oe n s u r et h eg l o b a lc o n v e r g e n c e u n d e rm i l da s s u m p - t i o n si ti ss h o w nt h a te v e r yl i m i tp o i n to ft h es e q u e n c eo fi t e r a t e sg e n e r a t e db yt h ea l g o r i t h mi s f e a s i b l e ，a n dt h a tt h e r ee x i s t sa tl e a s to n el i m i tp o i n tt h a ti sas t a t i o n a r yp o i n tf o rt h ep r o b l e m u n d e rc o n s i d e r a t i o n i na d d i t i o n ，w ea l s os h o wt h a tt h ep r o p o s e dm e t h o dd o e sn o ts u f f e rf r o m m a r a t o se f f e c tb yu s i n gs e c o n do r d e rc o r r e c t i o ns t e p c o n s e q u e n d y , f a s tl o c a lc o n v e r g e n c et os e c o n do r d e rs u f f i c i e n tl o c a ls o l u t i o n si sa c h i e v e d t h en u m e r i c a le x p e r i m e n t sa r er e p o r t e dt os h o w t h ee f f e c t i v e n e s so ft h ep r o p o s e da l g o r i t h m k e yw o r d s ： n o n l i n e a rc o n s 仃a i n e dp r o g r a m m i n g ；f i l t e rm e t h o d ；t w op i e c eu p d a t eo fr e d u c e d h e s s i a n ；s e c o n do r d e rc o r r e c t i o ns t e p ；g l o b a lc o n v e r g e n c e ；l o c a lc o n v e r g e n c er a t e 第m 页 主要符号对照丧 主要符号对照表 酞竹 佗维实向量空间 融x m 礼m 维实矩阵 i l ，1 1 2e u c l i d 范数 ” o o 一范数 l i 1 1 1 1 一范数 。 礼维决策变量 z f向量z 的第歹个分量 缸目标函数的局部极小值点 ， 目标函数 ，在当前迭代点观处的函数值 巩，在当前迭代点处的约束违反度 g k ，v f ( x k ) ，在当前迭代点瓢处的梯度 c ( z ) 约束函数 a约束函数在当前迭代点处的j a c o b i a n 矩阵 眠l a g r a n g e 函数在处的h e s s i a n 矩阵 约束优化问题在可行点z 处的等式约束指标集 z 约束优化问题在可行点z 处的不等式约束指标集 a l a g r a n g e 乘子 m第k 次迭代的搜索方向 d p 。 第k 次迭代的二阶校正步 q 七第k 次迭代的搜索步长 尸 滤子( 禁止区域) t 3 ( x ) 有效集 4 有滤子增广情况发生的迭代序列的下标集合 冗 进入可行性恢复阶段的迭代序列的下标集合 第1 v 页 致谢及声明 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研 究成果论文中除了特别加以标注和致谢的地方外，不包含其他 人或机构已经发表或撰写过的研究成果其他同志对本研究的 启发和所做的贡献均已在论文中做了明确的声明并表示了谢 二也 思 作者签名：蠢毒、记日期：乞孑y 哆 第4 0 页 致谢及声明 论文使用授权声明 本人完全了解上海师范大学有关保留、使用学位论文的规 定，即：学校有权保留送交论文的复印件，允许论文被查阅和借 阅；学校可以公布论文的全部或部分内容，可以采用影印、缩 印或其它手段保存论文保密的论文在解密后遵守此规定 作者魏蠢点五聊魏弘吼2 “y 乡 作者签名：五专钇导师签名：汗桫乙日期：2 驴卜z 歹 第4 l 页 第一章最侥化问题基本概念 第一章最优化问题基本概念 1 1 本章概述 本章将简要阐述最优化问题的概况。1 1 介绍最优化问题的一般形式和基本概 念，1 2 给出最优化问题的一阶必要条件、二阶必要条件和二阶充分条件，1 3 对最优化 方法的结构做初步探讨，最后一节介绍线搜索方法以及解约束优化问题常用的罚函数方 法，同时指出罚函数方法面临的问题。 1 2 最优化问题简介 最优化理论与方法是研究如何从实际问题的众多方案中选取最优方案的- - i 学科， 近年来随着电子计算机的普及以及优化计算方法的迅速发展，它的实际应用日益广泛， 在经济、金融、管理等领域都发挥着越来越重要的作用。 无约束最优化问题的一般形式为 m i n ，( z ) 约束最优化问题通常写为 m i nf ( x ) s t c ( z ) = 0 ，i ( 1 1 ) c ( z ) 0 ，i z 其中z 瞅为决策变量，( z ) 称为目标函数，c ( z ) 是约束函数，和z 分别是等式约束的 指标集【1 ，2 ，m ) 和不等式约束的指标集【m + 1 ，m + 2 ，订。问题( 1 1 ) 的可行域定 义为集合 q 磐 ziq ( z ) = 0 ，i ；q ( z ) 0 ，i z ) ( 1 2 ) 不等式约束中的等号不被满足时，可行成为“严格可行域，即( 1 1 ) 的严格可行域 为： i n t ( f 1 ) d = e f zic ( z ) = 0 ，i ；q ( z ) 0 ，i z ) ( 1 3 ) 对于一个可行点z ，所有的等式约束都被认为是有效约束。考虑不等式约束q ( z ) 0 ，如 果有q ) = 0 ，就称约束q ( z ) 0 在点z 是有效约束或起作用约束；如果有q ) 0 ，就 称不等式约束q ) 0 在点z 是无效约束或不起作用约束。如果所有的不等式约束都是不 起作用约束，就称z 是可行域的内点。 在一个可行点z ，所有有效约束的全体被称为该可行点的有效集，记为 召( z ) = iq ( z ) = 0 ，i ；q ( z ) = 0 ，l z ( 1 4 ) 第1 页 1 3 最优性条件 最优化问题的最优解所必须满足的条件称为最优性条件。本节将简要介绍常用的一 阶必要条件，二阶必要条件和二阶充分条件。最优性条件不仅对于最优化理论的研究具 有重要意义，而且对最优化算法的设计和终止条件的确定起重要作用。下面引入常用的 约束品性。 定义1 2 1 设双q ，召( z 。) 是起作用约束集，如果或者所有的 q ( z 。) ，i 召( 反) ) 都 是z 的线性函数，或者 v 白 。) ，i 召( z 。) ) 线性无关，则称问题( 1 1 ) 具有线性无关约束品 性。 为了更方便地讨论约束优化问题的局部极小点的最优性条件，我们引入约束优化问 题( 1 1 ) 的l a g r a n g e 函数 l ( z ，入) = ，( z ) 一九c ( z ) ， ( 1 5 ) i = 1 其中入称为l a g r a n g e 乘子。 下面我们先给出最优解的一阶必要性条件。 定理1 2 1 设双q 是问题( 1 1 ) 的局部最优解，若在z 。点线性无关约束品性成立，则存在 向量”= ( 对，k ) t ，使得 v 霉l ( 文，”) = 0 ， ( 1 6 ) n 0 ，i z ，( 1 7 ) n c 。) = 0 ，i z ( 1 8 ) 定理1 2 1 通常被称为k a r u s h k u h n t u c k e r ( 简称k - k - t ) 定理，( 1 6 ) 一( 1 8 ) 称为问题( 1 1 ) 的一阶必要性条件或k - k - t 条，满足k - k - t 条件的点被称为k k t 点。条件k q ( 双) = o 称为 互补松驰条件，因而非有效约束对应的l a g r a n g e 乘子为0 。如果所有有效约束的乘子均不 为0 ，则称为严格互补松驰条件成立。 由定理1 2 1 立即可得无约束最优化问题的一阶必要性条件可描述为 v f ( x 。) = 0 接下来我们给出最优解的二阶必要条件定理。 定理1 2 2 设z 。q 是最优化问题( 1 1 ) 的最优解，且函数，( z ) 与q ( z ) ，i = 1 ，2 ，p 二阶连续可微。又设定理1 2 1 中的约束规范条件在点& 成立，从而存在l a g r a n g e 乘子向 量九使k - k t 条件成立如果严格互补松弛条件在z 。成立，则： ，v ：z l ( x ，k ) s 0 对一切满足 s r v c i ( z 。) = 0 ，i 召( 以) 的方向8 均成立 最后，给出下面的最优解的二阶充分条件定理。 第2 页 第一露最优化问题基本概念 定理1 2 3 设最优化问题( 1 1 ) 的函数( x ) 与龟( z ) ，i = 1 ，2 ，m 均二阶连续可微，在可 行点氟处定理1 2 1 的约束规范条件成立，若存在l a g r a n g e 乘子向量a 。使k - - t 条件和严 格互补松弛条件成立，且对所有满足 s r v q ( x 。) = 0 ，i 召( 文) 的非零向量8 有 s ? v 乞二( 以，k8 0 ， 则z 。是问题( 1 1 ) 的一个严格局部最优解 1 4 最优化方法的结构 最优化方法通常采用迭代方法求它的最优解，其基本思想是：给定一个初始点z o r n ，按照某一迭代规则产生一个点列 飘 ，使得当【z 七) 是有穷点列时，其最后一个点是 最优化模型问题的最优解；当 ) 是无穷点列时，它有极限点，且其极限点是最优化模 型问题的最优解。 一个好的算法应具备的典型特征是：迭代点钆能稳定地接近局部极小值点瓢的邻 域，然后迅速收敛于瓢。当给定的某个收敛准则满足时，迭代即终止。我们给出收敛与 收敛速率的定义，设算法产生的迭代序列 瓢) 在某种范数意义下收敛，即 。l i mf i 巩一文f i = 0 ( 1 9 ) 若存在实数q 0 及一个迭代次数七无关的常数q 0 ，使得 k l i - - - m * o o 谢- g ( 1 1 0 ) z k 一双l i a 、 则称算法产生的迭代序列 矾 具有q 一口阶收敛速率。特别地， ( 1 ) 当q = 1 ，0 g 1 时，迭代序列【矾) 具有q 线性收敛速率； ( 2 ) 当l i n uf ( x k + a p k ) ，“，u 第3 页 1 。5 线搜索方法 或者若，可微选取口知 0 ，使得 q 南= m i n a o l v f ( x k - t - o t p k ) t p 知= o ) ， 这样的线搜索通常称为精确线搜索，一般有直接搜索法和插值法。 由于精确线搜索需要的计算量大，并且过分追求精度反而会降低整个方法的效 率，因此人们提出了既花费较少的计算量，又能达到足够下降的不精确线性搜索 方法。h r m i j o 和g o l d s t e i n 分别提出了不精确一维搜索过程，要求步长因子满足下面 的a r m i j o - g o l d s t e i n 准则 ，( z 七+ a 七p 奄) f ( x k ) + p a k v f ( x k ) t p k( 1 1 3 ) v y ( z k + a k p k ) t p k ( 1 一p ) v y ( x k y p , 。， ( 1 1 4 ) 其中j d 石1 。a r m i j o g o l d s t e i n 准则可能把步长因子q 的极小值排除掉了，所以w o l f - p o w e u 准则给出了一个更简单的条件代替，就是 v f ( x k + o t k p k ) t p k a v f ( x k ) t p k ，仃( p ，1 ) ( 1 1 5 ) 不精确线搜索方法由于计算量小，效率高而成了现在流行的线性搜索方法。基于该 原因，本文也采用了不精确线搜索的策略。 在求解约束优化的计算方法中有着直接应用的一类方法是罚函数法，在一定的意义 下，精确罚函数等价地描述了原约束优化问题。因此，它可以作为“价值”函数来判别 算法给出的试探点是否可以被接受。为了保证算法具有整体收敛性，通常的方法是通过 引入与原问题相关的罚函数作为价值函数进行线搜索。如果在每次迭代中价值函数都有 足够的下降量，就能保证算法产生的迭代序列逐渐趋向于优化问题的某个稳定点。常见 的比如如罚函数 九( z ) = y ( x ) + p l l c ( x ) 1 1 1 m 作为线搜索的价值函数，这里p 是一个罚参数，i i c ( x ) l l l = l q ( z ) i 。 由于可以有效的保证算法的整体收敛性，罚函数法已获得深入的研究和广泛的应 用。但其也有不足之处，比如在每次迭代中都要确定罚参数p 的值，而这恰恰是一个需 要耗费较大计算量的过程。另外，由于每次迭代都要求新的迭代点使得y ( x ) + p l l c ( x ) l l l 有足够的下降量，这个要求相对而言比较“苛刻”，降低了试探步被接受的可能性。本 文考虑采用过滤方法取代罚函数方法保证算法的整体收敛性，从而克服上述不足。 本文第二章将介绍两块校正序贯既约h e s s i a n 方法和过滤线搜索方法的主要思想，第 三章则给出过滤线搜索两块校正序贯既约h e s s i a n 法的完整算法和整体收敛性的证明，第 四章引入二阶校正步，分析算法的局部收敛性质，在第五章中，通过数值实验说明算法 的可行性和有效性，并利用图像给进一步说明过滤线搜索的迭代过程。最后一章是对本 文的总结，同时简要讨论了过滤方法的发展前景。 第4 页 第二章两块校正序贯既约h e s s i a n ) y 法和过滤方法 第二章两块校正序贯既约h e s s i a n 方法和 过滤方法 2 1两块校正序贯既约h e s s i a n 方法 我们知道，用于求解非线性规划问题的迭代算法首先需要确定搜索的方向，并且还 要求该方向是相应目标函数的下降方向，通常情况下，搜索方向的好坏，直接决定了算 法的收敛性态。因此，每次迭代中如何确定搜索方向是一个非常重要的问题。为了减 小计算量，提高运算效率，本文采用两块校正序贯既约h e s s i a n 方法( 简称为两块校正方 法) 来求解搜索方向。 在( 1 1 ) 中所表述的是约束优化的一般形式。注意到一般约束下的优化问题可以通过 起作用约束集转化为等式约束问题( 可参考第六章相关内容) ，因此本文着力于解决带 有等式约束的非线性优化问题，其一般形式如下： m i n ，( z ) s t c ( z ) = 0( 2 1 ) 其中，：r n r ，c ：础_ r m ，m 佗。c o l e m a n 与c o n n 【1 1 、n o c e d a l 与o v e r t o n 【2 】 独立的提出了使用双边投影既约h e s s i a n 的类似的s q p 方法。之后，g u r w i t z 【3 】3 提出了 两块校正方法。其基本思想可以如下表述：令g ( z ) = v f ( z ) r n ，a ) = v c ( x ) = c 1 ( z ) ，v ( z ) 】础仇。假设a ( x ) 列满秩，从而可以对其做如下q r 分解 a ( z ) = y ( z ) z 扛) l 冗孑i ( 2 2 ) 其中旷( z ) z ( z ) 】是正交矩阵，r ( z ) 是一个m 阶的非奇异上三角阵，并且z ( z ) 础m m ) 。z ( z ) 的列向量是a ( z ) 的零空间的一组正交基，y ( x ) 的列向量是a ( x ) 的值空 间的一组正交基，令 z ( z ，入) = ，( z ) 一, x r c ( z ) ( 2 3 ) 是问题( 2 1 ) 的l a g r a n g e 函数，则其h e s s i a n 矩阵可以表示为 w = v 2 f ( x ) 一( 九v 2 c i ( z ) ) ， ( 2 4 ) i = 1 而入是如下最小二乘问题的解 m i n l l a ( z ) m 一夕( z ) 0 我们知道第尼次迭代中的k 可以通过解如下的上三角方程组获得 r k a 膏= 昭鲰( 2 5 ) 第5 页 2 1 薅块校正序贯既约h e s s i a n 方法 。令w ( x ，入) = v l l ( z ，a ) 代表j ( z ，a ) 的h e s s i a n 矩阵：为了叙述简便我们以 代 替，( z 七) ，以g k 代替v f ( x k ) 。在每次迭代中，以b k 和d 知分别代替刃w ；玩和z 吾w k k 的近似。g u r w i t z 的方法通过解下面的方程组得到碟， 磁。碟= - - c k ， ( 2 6 ) 然后通过解方程组 n 。z = 一硪。鲰一d 印! ( 2 7 ) 得到厩，根据p 和唾定义搜索方向为 p k = 反嫉+ 碱， ( 2 8 ) 则新的迭代点可定义如下： x k + l = 瓢+ p k ( 2 9 ) 考虑到风是对称的，采用d f p 校正或者b f g s 校正用来得到风+ l ，而仇是非 对称的，则用b r o y d e n 校正用来得到d + 1 。但并不是每次迭代都需要校正这两个矩 阵，g u r w i t z 给出了如下的校正准则： 校正准则1 当且仅当满足如下条件时对风使用d f p 或者b f g s 校正 州i 两等而蚓l ， ( 2 l o ) 其中肛1 ，v l ，是适当选取的参数。 校正准则2 当且仅当满足如下条件时对d 七使用b r o y d e n 校正 m i 0 ，7 0 1 ，7 f 1 是常数，并且 j j m 七( 口) = o f 。! 仇( 2 2 1 ) 是目标函数沿比方向的线性模型。( 注：对于全局收敛性，7 s l 已足够，但对于局部 收敛性，需要满足更严格的条件，即7 t 2 ，这在第四章有关局部收敛速率的证明中会 有所体现，比如引理4 3 ) 如果切换条件( 2 2 0 ) 成立，则仇必然是目标函数的一个下降方向，此时算法将不再 坚持条件( 2 1 9 ) ，转而要求试探步长q 知1 满足a r m i j o 条件： ，( z 知( 口知，f ) ) ，( 瓢) + 卵f f i z k ( o l k 。f ) ( 2 2 2 ) 这里，7 7 ，( 0 ，z 2 ) 是一个固定的常数。 注意到线搜索算法中，可能试探步长q 只满足( 2 2 0 ) 而不满足( 2 2 2 ) ，因此在算法 的设计中，应该使得算法在出现上述情况时，重新考虑条件( 2 1 9 ) ，以保证算法的可行 性。 对于( 2 2 0 ) 中的右边不等式，现做如下简要讨论。此式主要目的是保证：当我们 要求迭代点满足a r m i j o 条件时，相对于当前的约束违反度( 而不是约束违反度的下降 量) ，函数值的下降要足够的大。这样的话，在可行域附近，函数的下降量就不会充 分的小，这在后面的证明中有重要作用。如果令7 i = l ，那么条件( 2 2 0 ) 就可以简化为 一m 知( q kz ) a k ，l 6 【p ( 钆) 】即，上面的表述就不难理解了。 为了表述方便，称满足切换条件( 2 2 0 ) 的q 毛l 为f 一型步长；类似地，如果q 引被接 受为第k 步的步长o t 七，称第k 步为f 一型迭代 2 2 3 禁止区域一一滤子 除了要求当前迭代有足够的下降量，过滤方法还要避免算法出现循环。例如，如果 有两个点z 1 和z 2 ，满足o ( x 1 ) o ( x 2 ) 和，0 1 ) ，( 勋) ，根据条件( 2 1 9 ) ，算法可能在这 两个点间产生循环，从而无法达到最优点。为了避免这种情况，定义一个叫做滤子的集 合。主要思想是将其作为一个禁止区域，任何在这个区域的点都被禁止在后面的迭代过 程中出现，这样将有效的避免循环情况的发生。一般情况下，这个禁止区域的初始状态 被选择为： y o ：= ( p ，f ) r 2 ：口( 2 2 3 ) 其中。是一个预先选定的较大的正数。然后，在特定的条件下，可以按以下的规则对 滤子进行增广 + l = 氕u ( 日，) r 2 ：p ( 1 一伽) 口( 钆) ，f ，( 瓢) 一竹p ( 巩) ) ( 2 2 4 ) 第8 页 第二章两块校正序贯既约h e s s i a n 方法和过滤方法 如果滤子不需要增广j 则保持其不变。称试探点z 知( q 七。1 ) 是被滤子接受的j 当且仅当这 个点所对应的实数对( 口，) 不在禁止区域内，即 ( 9 ( z j b ( q 屯1 ) ) ，( z 七( q k1 ) ) ) 岳- j 气( 2 2 5 ) 这里需要说明的是，注意到任何被滤子所包含的点都不会在后面的迭代过程中出 现。所以我们并不是在每一步都对滤子进行增广，否则可能会排除掉一些很好的迭代 点。关于在什么情况下对滤子进行增广，将在本章最后给出统一说明。 2 2 4 可行性恢复阶段 在线搜索的某次迭代中，可能会因为在多次尝试后都找不到满足下降条件的试探 点，导致o t 引一直在缩小，而试探步长太小会直接影响算法的收敛性态，因此当试探步 过小时，我们需要一个方案，使算法跳出这个区域，避免上述情况。这就需要引入可行 性恢复阶段。 可行性恢复阶段的目的是找到一个满足( 2 1 9 ) 的新的迭代点z 七+ 1 ，从而可以使算法 继续进行下去。可行性恢复阶段的算法可以是任何一种迭代算法，但此时不要求函数值 的下降，只要该算法可以找到满足更小约束违反度的点。这可以理解为一个无约束优化 问题，而且并不需要找到一个约束违反度的极小点，只需要满足( 2 1 9 a ) 式即可，这样新 的迭代点就可以被下降准则所接受。并且，在不同的优化阶段，可以选择不同的算法， 本文在此不做更多的具体说明。 那么，当试探步长小到什么