（应用数学专业论文）线性约束优化问题的仿射内点最优路径方法.pdf

y 7 0 8 幸 s 7 fa 5 摘 任石 3七 最优化理论与方法是决策科学和系统分析中的一个重要工具， 在很多领域都有着非 常广泛的应用。本文主要针对线性的等式和不等式约束的非线性优化问题， 提出了结合 非单调内点回代线搜索技术的仿射最优路径算法。 信赖域策略是解非线性规划问 题的基本逼近方法，它能保证算法的整体收敛性。 对 于无约束优化问题，信赖域方法的思想非常的简单与直 观。但是， 对于约束优化问题， 由于约束的存在， 通常很难构造一个类似的 信赖域子问题。 最近， c o l e m a n 和l i 针对仅 具有线性不等式约束的优化问题， 提出了 ” 双信赖域方法” ( t r a m) ， 通过仿射变换，成功 的构建了一个近似二次函数和信赖域子问题，克服了由约束带来的困难，并进一步证明 了 该方法的收敛性。但是作者并没有给出求解信赖域子问题的具体方法。事实_ 匕 对于 具有严格可行约束的信赖域子问题，在每一迭代步， 往往要重复多次求解该子问题，才 能获得可接受的严格内点可行步，因此，每得到一步新的迭代步，总的计算量会很大。 为了克服解信赖域子问题时带来的困难，可以借助于曲线路径来搜索，而这些路径可以 使用精确或非精确h e s s e 矩阵的特征值和特征向量表示出来。 本文中，引进仿射变化矩阵， 基于一般曲线路径的思想，构造一条特殊的近似于仿 射信赖子问 题的最优曲 线路径。考虑将信赖域子问 题中的信赖域约束去掉，沿着这条曲 线路径去搜索得到迭代方向。当该迭代方向 步不严格可行时， 利用非单调回代线搜索技 术得到可接受的步长因子，从而获得新的有足够下降量的迭代点。在线搜索求迭代步长 的过程中，利用非单调技术得到使目 标函数非单调下降的迭代点，因为非单调克服高度 非线性化函数的求解问题，从而避免了只使用单调搜索在” 峡谷” 现象局部最优解被卡的 情况。 本文先对最优化理论与方法的一些相关概念和理论进行简单的回顾，作为进一步研 究的基础，接着给出了仿射最优路径的具体形式。然后，结合最优路径的技巧、内点仿 射变换和非单调回代搜索， 描述了仿射内点最优路径算法。基于最优路径的良 好性质， 证明了算法在合理的假设条件下，不仅具有整体收敛性，而且保持局部超线性收敛速 率。数值计算结果表明了 算法的实际有效性。 关键词:非线性约束优化; 仿射变换;内点法;非单调技术;最优路径;整体收敛性;局 部收敛速率 第i 页 英 文摘 要 ab s t r a c t o p t i m i z a t i o n i s a n i m p o r ta n t t o o l i n d e c i s i o n s c i e n c e a n d i n t h e a n a l y s i s o f p h y s i c a l s y s - t e m s . i n t h i s t h e s i s , w e p r o p o s e a n a f fi n e s c a l i n g o p t im a l p a t h a p p r o a c h i n a s s o c i a t io n w i t h n o n - m o n o t o n i c i n t e r i o r b a c k t r a c k i n g l i n e s e a r c h t e c h n i q u e f o r n o n l i n e a r o p t i m i z a t i o n s u b j e c t t o l i n e a r e q u a l i t y a n d i n e q u a l i t y c o n s t r a i n t s . t rus t r e g i o n s t r a t e g y i s a w e l l - a c c e p t e d m e t h o d in t h e n o n l i n e a r p r o g r a m m i n g t o a s s u r e g l o b a l c o n v e r g e n c e . t h e i d e a b e h i n d a tr u s t r e g i o n m e th o d f o r u n c o n s t r a i n e d m i n i m i z a t i o n i s i n t u i t i v e a n d s i m p l e . b u t f o r c o n s t r a i n e d m i n i m i z a t i o n , c o n s t r a i n t s w i l l m a k e i t d i f fi c u l t t o f o r - m u l a t e a s i m i l a r s u b p r o b l e m . r e c e n t l y , c o l e m a n a n d l i p r e s e n t e d a tr u s t r e g i o n a f fi n e s c a l i n g i n t e r i o r p o i n t a l g o r i t h m f o r t h e m i n i m i z a t i o n p r o b le m s u b j e c t o n l y t o l i n e a r i n e q u a l i t y c o n s t r a i n ts . b y u s i n g a f fi n e s c a l i n g t o f o r m u l a t e a n a p p r o p r i a t e q u a d r a t i c f u n c t i o n a n d t r u s t r e g i o n , d i f fi c u l - t i e s i m p o s e d b y c o n s t r a i n t s a r e o v e r c o m e . a n d f u r t h e r m o r e , t h e a u t h o r s a n a l y z e d a n d p r o v e d t h e c o n v e r g e n c e p r o p e r t i e s o f t h e p r o p o s e d m e t h o d . b u t i n t h a t a r t i c l e , t h e a u t h o r s d i d n t g i v e t h e m a t e r i a l m e t h o d s t o s o l v e t h e s u b p r o b l e m . i n f a c t , i t i s p o s s i b l e t h e t rus t r e g i o n s u b p r o b l e m w i t h t h e s t r i c t l y f e a s i b l e c o n s t r a i n t n e e d s t o b e r e s o l v e d m a n y t i m e s b e f o r e o b t a i n i n g a n a c c e p t a b l e s t r i c t i n t e r i o r f e a s i b l e s t e p , a n d h e n c e t h e t o t a l c o m p u t a t i o n f o r c o m p l e t i n g o n e i t e r a t i o n m i g h t b e e x p e n s i v e a n d d i f fi c u l t i e s . i n o r d e r t o o v e r c o m e t h e d i f fi c u l t i e s b r o u g h t b y s o l v i n g t h e t ru s t r e g i o n s u b p r o b l e m , w e m a y r e s o r t t o u s e s o m e c u r v i l i n e a r p a t h s t o s e a r c h f o r t h e t r i a l s t e p s , a n d u s u a l l y t h e s e p a t h s c a n b e e x p r e s s e d b y t h e e i g e n v a l u e s a n d e i g e n v e c t o r s o f t h e e x a c t o r i n e x a c t h e s s i a n m a t nx . i n t h i s p a p e r , w e i n t r o d u c e t h e a f fi n e s c a l i n g m a t r i x , s i m i l a r t o t h e c u r v i l i n e a r p a t h , t o g e n - c r a t e a n a f fi n e s c a l i n g o p t i m a l p a t h i n w h i c h w e u s e t h e c u r v i l i n e a r s e a r c h i n s t e a d o f th e t r u s t s t r a t e g y . u s i n g b o t h t h e a f fi n e s c a l i n g o p t i m a l p a t h s e a r c h s t r a t e g y a n d l i n e s e a r c h t e c h n i q u e , t h e q u a d r a t i c m o d e l a t e a c h i t e r a t i o n g e n e r a t e s a b a c k tr a c k in g s t e p t o o b t a in a n e w a c c e p t e d s te p . t h e e n f o r c e m e n t o f a m o n o t o n i c d e c r e a s e o f t h e o b j e c t iv e f u n c t i o n v a l u e s m a y h a v e d a n g e r o u s e f f e c t s i n t h e m i n i m i z a t i o n o f h i g h l y n o n l i n e a r f u n c t i o n s w i t h th e p r e s e n c e o f s t e e p - s id e d v a l l e y s , s i n c e t h e s e a r c h f o r l o w e r f u n c t i o n v a l u e s m a y c a u s e a n y m i n i m i z a t i o n a l g o r i t h m t o b e t r a p p e d i n th e b o t t o m o f a v a l l e y . t h e n o n m o n o t o n i c i d e a m o t iv a t e s t o f u r th e r s t u d y a n a f fi n e s c a l i n g o p t i m a l p a t h a p p r o a c h i n a s s o c i a t i o n w i t h n o n m o n o t o n i c i n t e r i o r b a c k t r a c k i n g l i n e s e a r c h t e c h n i q u e f o r n o n l i n e a r o p t i m i z a t i o n s u b j e c t t o l i n e a r e q u a l i t y a n d i n e q u a l i t y c o n s t r a i n t s ( 1 . 2 ) . i n t h i s t h e s e s , w e fi r s t l y s u m m a r i z e s o m e r e l a t i v e c o n c e p t s a n d t h e o r i e s o f o p t i m i z a t i o n te c h - n i q u e , a s t h e b a s i s m a t e r i a l f o r t h e f u r th e r s t u d y , t h e n p r o p o s e a n a f fi n e s c a l i n g o p t i m a l c u r v i l i n e a r 第1 1 页 英文摘要 p a t h . f u r t h e r m o r e , w e d e s c r i b e t h e a l g o r i t h m w h i c h c o m b i n e s t h e t e c h n i q u e s o f o p t i m a l c u r v i l i n - e a r p a t h , i n t e r i o r p o i n t , a f fi n e s c a l in g a n d n o n m o n o t o n i c b a c k t r a c k i n g s e a r c h s t r a t e g y . f o l l o w i n g t h a t , b a s e d o n t h e g o o d p r o p e r ti e s o f t h e o p t i m a l p a t h , w e a k g l o b a l c o n v e r g e n c e a n d s t r o n g g l o b a l c o n v e r g e n c e a n d l o c a l c o n v e r g e n c e r a t e o f t h e p r o p o s e d m e t h o d a r e e s t a b l i s h e d u n d e r s o m e r e a - s o n a b l e c o n d i t i o n s . n u m e r i c a l r e s u l t s i n d i c a t e t h a t t h e a l g o r i t h m i s u s e f u l a n d e f f e c t i v e in p r a c t i c e . k e y wo r d s : n o n l i n e a r c o n s t r a in e d p r o g r a m m i n g ; g l o b a l c o n v e r g e n c e ; l o c a l c o n v e r g e n c e r a t e ; t r u s t r e g i o n m e t h o d ; n o n m o n o t o n i c t e c h n i q u e ; i n t e r i o r p o i n t m e t h o d 第m页 主要符号对照表 主要符号对照表 时 ! r n x m 11 ， ! ， 11 112 - x x i 劣* f f k c ( x ) h i n t ( q ) i ( x ) a ( x ) v f ( x ) 入 ，u l ( x , a ) 二 维实向量空间 。x。维实矩阵 e u c l i d 范数 cc 一范数 。 维决策变量 向 量x 的 第 9 个分量 目 标函数的局部极小值点 目标函数 f 在当前迭代点 x k 处的函数值 约束函数 可行集 严格可行集 约束优化问 题在可行点二 处的 有效不等式约束集合 约束优化问题在可行点二 处的有效集 f 在二 处的梯度 l a g r a n g e 乘 子 约束优化问 题的 l a g r a n g e 函 数 9 ( x ) g ( x ) 二一 ( o f ( x ) 一 a t a 一 a 2 u ) f 在x 处的 投影 梯度 ，.j 拜 - 9 ( x ) - d ( x ) 12 o f ( x ) w k ( b k , a k ) k ,c ( x o ) = x r n l f ( x ) 0 , i =m e +1 , ， 二 其中 x g r ” 为决 策 变量， f ( x ) 称为目 标函 数， c ( x ) 为 约 束向 量函 数， mm 。 是 两 非负 整 数。如果约束条件m二m 。 二0 ，则最优化问题( 1 . 1 ) 称为无约束最优化问 题。为了 方便数 值 计 算 ， 这里 我 们 定 义的目 标函 数 f ( x ) 与 约 束 函 数 c ( x ) 均 为 实 值 可 微函 数。 特别地，当模型( 1 . 1 ) 中所有约束都是x 的线性函数时称为线性约束优化问题， 它的一 般形式为 5 ， t 为了下面叙述方便起见，定义 e= 2 i f ( x ) a 1 x= 瓦， a z x b2. ( i . 2 ) z= i z ( x ) = i i =1 , ， 二 已 ; i =。 。 +1 , ， m ; c i ( x ) 。 ， 、 。 z 第1 页 ( 1 . 3 ) 第一章最优化问题基本概念 第一章 最优化问题基本概念 最优化问题简介 最优化理论与方法是一门应用相当广泛的学科，它讨论决策问题的最佳选择之特 构造寻求最佳解的计算方法，研究这些计算方法的理论性质及实际表现。因为最优 jl， l.性 化问题广泛见于经济计划、工程设计、生产管理、交通运输、国防等重要领域，它己受 到政府部门、科研机构和产业部门的高度重视。伴随着计算机的高速发展和优化计算方 法的进步，规模越来越大的优化问题得到解决。通常，为应用最优化技术确定最优的方 案，需要针对具体的实际问题建立相应的模型，再根据模型的具体形式和特性选择适当 的最优化方法求解。 约束最优化问题通常写为 m i n f ( x ) s .t , c ; ( x ) = 0 , i =1 , 2 , ， m e c i l x ) 0 , i =m e +1 , ， 二 其中 x g r ” 为决 策 变量， f ( x ) 称为目 标函 数， c ( x ) 为 约 束向 量函 数， mm 。 是 两 非负 整 数。如果约束条件m二m 。 二0 ，则最优化问题( 1 . 1 ) 称为无约束最优化问 题。为了 方便数 值 计 算 ， 这里 我 们 定 义的目 标函 数 f ( x ) 与 约 束 函 数 c ( x ) 均 为 实 值 可 微函 数。 特别地，当模型( 1 . 1 ) 中所有约束都是x 的线性函数时称为线性约束优化问题， 它的一 般形式为 5 ， t 为了下面叙述方便起见，定义 e= 2 i f ( x ) a 1 x= 瓦， a z x b2. ( i . 2 ) z= i z ( x ) = i i =1 , ， 二 已 ; i =。 。 +1 , ， m ; c i ( x ) 。 ， 、 。 z 第1 页 ( 1 . 3 ) 1 .2 最优性条 件 称为问题( 1 . 1 ) 的可行域。不要求不等式约束等号满足时，可行域成为” 严格可行域” ，即 i n t o 4-2 , 二 l q ( - ) 二 0 ， ， 。 ; c ( 二 ) 0 , i e e l ( 1 . 4 ) 称为问 题( 1 . 1 ) 的严格可行域。 对于 一个可行点 二 ， 考虑 不等式约束 c ; ( x ) 0 ，如 果 有 c ; ( x ) =0 ， 就称约束 c i ( x ) 。 在点 二 是 有 效 约 束 或 起作 用 约 束， 并 称可 行 点 x 位于 约 束 c ; ( x ) 。 的 边界。 如 果 有 c a ( x ) o , 就 称 不 等式 约 束 c , ( x ) 0 在点 x 是 无 效约 束 或不 起 作 用 约 束， 并 称 二 是 约 束 c ( x ) 0 的内点。在任意可行点，所有的等式约束都被认为是有效约束。 定义1 . 1 . 1在一个可行点 x ，所有有效约束的全体被称为该可行点的 有效集，记为 a ( x ) =e u z ( x ) . ( 1 .5 ) 对于一可行点二 ，如果没有一个不等式约束是有效的，就称x 是可行域的内点。不是 内点的可行点就是可行域的边界。 显然， 在边界点至少有 一个不等式约束是有效约束。 当存在等式约束时，任何可行点都要满足等式约束，因此不可能是等式约束的内点。 定义1 . 1 .2 设二 。 q ，若对任意工任q有 f ( x . ) _ f ( x ) , 则称x 。 是问 题( 1 . 1 ) 的整体极小值点。 进一步， 若对一切x e5 2 且x ,a x * 有 f ( x . ) 。 为半 径，以 二 ， 为中 心点的 邻j a iv ( x . , e ) ， 使得 对 任意x 。 n 万( 二 二 ， : ) 有 f ( x . ) 0 ，如 果 有 c ; ( x ) =0 ， 就称约束 c i ( x ) 。 在点 二 是 有 效 约 束 或 起作 用 约 束， 并 称可 行 点 x 位于 约 束 c ; ( x ) 。 的 边界。 如 果 有 c a ( x ) o , 就 称 不 等式 约 束 c , ( x ) 0 在点 x 是 无 效约 束 或不 起 作 用 约 束， 并 称 二 是 约 束 c ( x ) 0 的内点。在任意可行点，所有的等式约束都被认为是有效约束。 定义1 . 1 . 1在一个可行点 x ，所有有效约束的全体被称为该可行点的 有效集，记为 a ( x ) =e u z ( x ) . ( 1 .5 ) 对于一可行点二 ，如果没有一个不等式约束是有效的，就称x 是可行域的内点。不是 内点的可行点就是可行域的边界。 显然， 在边界点至少有 一个不等式约束是有效约束。 当存在等式约束时，任何可行点都要满足等式约束，因此不可能是等式约束的内点。 定义1 . 1 .2 设二 。 q ，若对任意工任q有 f ( x . ) _ f ( x ) , 则称x 。 是问 题( 1 . 1 ) 的整体极小值点。 进一步， 若对一切x e5 2 且x ,a x * 有 f ( x . ) 。 为半 径，以 二 ， 为中 心点的 邻j a iv ( x . , e ) ， 使得 对 任意x 。 n 万( 二 二 ， : ) 有 f ( x . ) 0 成 立， 则 我 们说严格互补松驰条件成立。 当 9 u z=0时问题( 1 . 1 ) 为无约束最优化问 题 mi n f ( x ) . ( 1 . 1 4 ) s 任 况n - ， 它的一阶最优性条件可描述为 定 理1 .2 .2 设x* 是 f ( x ) 的 局部 极小 值 点 ，且 f 在 x ， 的 一 个 开 邻 域内 可 微测 o f ( 二 。 ) =o .( 1 . 1 5 ) 接下来我们给出最优解的二阶必要条件定理如下。 定理1 .2 .3设 x , q 是最 优化问 题( 1 . 1 ) 的 最 优解， 且函 数f ( x ) 与 c i ( x ) , i = 1 , 2 , . . . ， 二二 阶连续可微。又设定理1 . 2 . 1 中的约束规范条件在点 x ， 成立， 从而 存在拉格朗日 乘子向 量a 。 使k - k - t 条件成立。如果 严格互补松弛条件在x 。 成立，则: 8 t v 呈 , l (x + , a , ) 8 0 第3 页 1 . 3 最优化方法的结构 对一切满足 8 t v c ; ( x . ) = 0 , i =1 , 2 , ， 二 ， i g i ( 二 * ) 的方向s 均成立 最后，给出下面的最优解的二阶充分条件定理。 定理1 .2 .4 设最优 化问 题( 1 . 1 ) 的 函 数 f ( x ) 与 c ; ( x ) , =1 , 2 , ， 二 ， m均 二阶 连续 可 微， 在 可 行点x ， 处定理1 .2 . 1 的约束规范条件成立，若存在拉格朗日 乘子向量入 ， 使k - t t 条件和严 格互补松弛条件成立，且对所有满足 8 t v c , ( x . ) = 0 , i =1 , 2 , ， m , i e t ( x , ) 的非零向量。 有 3 t v 呈 . l ( x . , a * ) s 0 , 是问 题( 1 . 1 ) 的一个严格局部最优解. 最优化方法的结构 最优化方法通常采用迭代方法求它的最优解，其基本思想是:给定一个初始点x o 任 几八、 j“j. 价乃，.1 r r ， 按照 某一 迭代规则产生一 个点 列 x k ， 使 得当 x k 是有 穷点 列时， 其最 后一 个点 是 最优化模型问 题的 最优解; 当 l x k f 是无穷点列时， 它 有 极限 点， 且其极限点 是最 优化 模 型问题的最优解。 设x 为第k 次迭代点， 乓为第k 次 搜索方向， a * 为第k 次步长因子， 则第k 次 迭代格 式为 x k + l =2 k +a k d k( 1 . 1 6 ) 从这个迭代格式可以 看出， 不同的 步长因 子a k 和不同的 搜索方向 d k 构成了 不同的 方法。 一个好的算法应具备的典型特征是: 迭代点 x ; 能稳定地接近局部极小值点 x ， 的邻 域，然后迅速收敛于x . 。当给定的某个收敛准则满足时，迭代即终止。如果对任意的初 始点 x o e s l ，由 算法产生的点 列都收敛于最优点 x . ，则称该算法具有整体收敛性。一个 算法 是 否 可 行， 分 析 其 是否 具 有 整 体 收 敛 性， 一 般 地， 可以 通 过证明 迭代点 列 二 、 的聚 点 ( 即子序列的极限点) 为一局部极小值点。 一 个 算 法 收 敛的 速 度是 衡 量 算 法 有效 性的 重 要 方 面。 如 果点 列 x k 虽 收 敛 到 x , ， 但 收敛得太慢，以 至在允许的时间内 不可能达到满意的 迭代结果，则算法可能没有实际的 应 用价 值。 现 在我们给出 收 敛 速率的定 义，设 算法 产生的 迭 代序列 二 * 在某 种范 数意义 下收敛，即 limk - - x 、 一- . 11 =0c 1 . ; 第4 页 1 . 3 最优化方法的结构 对一切满足 8 t v c ; ( x . ) = 0 , i =1 , 2 , ， 二 ， i g i ( 二 * ) 的方向s 均成立 最后，给出下面的最优解的二阶充分条件定理。 定理1 .2 .4 设最优 化问 题( 1 . 1 ) 的 函 数 f ( x ) 与 c ; ( x ) , =1 , 2 , ， 二 ， m均 二阶 连续 可 微， 在 可 行点x ， 处定理1 .2 . 1 的约束规范条件成立，若存在拉格朗日 乘子向量入 ， 使k - t t 条件和严 格互补松弛条件成立，且对所有满足 8 t v c , ( x . ) = 0 , i =1 , 2 , ， m , i e t ( x , ) 的非零向量。 有 3 t v 呈 . l ( x . , a * ) s 0 , 是问 题( 1 . 1 ) 的一个严格局部最优解. 最优化方法的结构 最优化方法通常采用迭代方法求它的最优解，其基本思想是:给定一个初始点x o 任 几八、 j“j. 价乃，.1 r r ， 按照 某一 迭代规则产生一 个点 列 x k ， 使 得当 x k 是有 穷点 列时， 其最 后一 个点 是 最优化模型问 题的 最优解; 当 l x k f 是无穷点列时， 它 有 极限 点， 且其极限点 是最 优化 模 型问题的最优解。 设x 为第k 次迭代点， 乓为第k 次 搜索方向， a * 为第k 次步长因子， 则第k 次 迭代格 式为 x k + l =2 k +a k d k( 1 . 1 6 ) 从这个迭代格式可以 看出， 不同的 步长因 子a k 和不同的 搜索方向 d k 构成了 不同的 方法。 一个好的算法应具备的典型特征是: 迭代点 x ; 能稳定地接近局部极小值点 x ， 的邻 域，然后迅速收敛于x . 。当给定的某个收敛准则满足时，迭代即终止。如果对任意的初 始点 x o e s l ，由 算法产生的点 列都收敛于最优点 x . ，则称该算法具有整体收敛性。一个 算法 是 否 可 行， 分 析 其 是否 具 有 整 体 收 敛 性， 一 般 地， 可以 通 过证明 迭代点 列 二 、 的聚 点 ( 即子序列的极限点) 为一局部极小值点。 一 个 算 法 收 敛的 速 度是 衡 量 算 法 有效 性的 重 要 方 面。 如 果点 列 x k 虽 收 敛 到 x , ， 但 收敛得太慢，以 至在允许的时间内 不可能达到满意的 迭代结果，则算法可能没有实际的 应 用价 值。 现 在我们给出 收 敛 速率的定 义，设 算法 产生的 迭 代序列 二 * 在某 种范 数意义 下收敛，即 limk - - x 、 一- . 11 =0c 1 . ; 第4 页 第一章最优化问 题基本概念 若存在实数a ( o , ) ， 使 l i mk - - i lx k + l 一 x 11 llx 、 一 二 ， a ,( 1 . 1 8 ) 则称算法产生的迭代序列 二 * 具有q一 阶线性收 敛速率。 若 imk - - 二 * + ， 一 x - 11 iix 、 一x . 11 二o ,( 1 . 1 9 ) 则 称算 法产生的 迭代序列 x k 具 有q一 阶 超 线 性 收敛 速 率。 最优化中，牛顿法和拟牛顿法都具有很好的局部超线性收敛速率。牛顿法对非二次 函数不能保证有整体收敛性，但当初始点靠近极小值点时，收敛速度一般是快的。 算法的另一个重要特征为终止迭代所需要的收敛准则。对使用者来说，最有用的也 许是要求f ( x k ) 一f ( x . ) i 或ix 、 一 x 川e ， 其中 参数。 由 使用者提供。 但由 于上述准 则需 要 预先 知 道解的 信息， 因 而是不实 用的 。 事实上，由 于!lx k + l 一 x k l 是 误差ix 、 一 x 11 的一个估计，因此我们有时采用 il x k + l 一 x k l l :( 1 .2 0 ) i ( x k + l ) 一( x k ) % l 兰氏 ， 叭( 1 .2 1 ) 其中 ( x k ) ， 表 示向 量 二 * 的 第i 个分 量。 另 一 个 可以 采用的 终止 准则 是 f ( x k ) 一 f ( x k + 1 ) : .( 1 . 2 2 ) 值得注意的是，以上的终止准则并不是万能的。在不同的最优化方法中往往采用不同的 终止准则，有时甚至是同时采用几个不同的收敛准则。 1 .4 两类常用的最优化的整 体收敛性方法简介 从 ( 1 . 1 6 ) 式可以 看出，不同的步长因子 a k 和不同的搜索方向 b k 将构成不同的 迭代方 法。其中，线搜索方法与信赖域策略是保证最优化方法总体收敛的两类技术。 下面我们 分别作一下简单的介绍。 1 .4 . 1 线搜索方法 从当 前迭代点x k 出 发，设 搜索方向 a k 己 知且为 下降 方向， 确定步长因子 。 * ， 使 f ( x k + a k 6 k ) ) ， 使 l i mk - - i lx k + l 一 x 11 llx 、 一 二 ， a ,( 1 . 1 8 ) 则称算法产生的迭代序列 二 * 具有q一 阶线性收 敛速率。 若 imk - - 二 * + ， 一 x - 11 iix 、 一x . 11 二o ,( 1 . 1 9 ) 则 称算 法产生的 迭代序列 x k 具 有q一 阶 超 线 性 收敛 速 率。 最优化中，牛顿法和拟牛顿法都具有很好的局部超线性收敛速率。牛顿法对非二次 函数不能保证有整体收敛性，但当初始点靠近极小值点时，收敛速度一般是快的。 算法的另一个重要特征为终止迭代所需要的收敛准则。对使用者来说，最有用的也 许是要求f ( x k ) 一f ( x . ) i 或ix 、 一 x 川e ， 其中 参数。 由 使用者提供。 但由 于上述准 则需 要 预先 知 道解的 信息， 因 而是不实 用的 。 事实上，由 于!lx k + l 一 x k l 是 误差ix 、 一 x 11 的一个估计，因此我们有时采用 il x k + l 一 x k l l :( 1 .2 0 ) i ( x k + l ) 一( x k ) % l 兰氏 ， 叭( 1 .2 1 ) 其中 ( x k ) ， 表 示向 量 二 * 的 第i 个分 量。 另 一 个 可以 采用的 终止 准则 是 f ( x k ) 一 f ( x k + 1 ) : .( 1 . 2 2 ) 值得注意的是，以上的终止准则并不是万能的。在不同的最优化方法中往往采用不同的 终止准则，有时甚至是同时采用几个不同的收敛准则。 1 .4 两类常用的最优化的整 体收敛性方法简介 从 ( 1 . 1 6 ) 式可以 看出，不同的步长因子 a k 和不同的搜索方向 b k 将构成不同的 迭代方 法。其中，线搜索方法与信赖域策略是保证最优化方法总体收敛的两类技术。 下面我们 分别作一下简单的介绍。 1 .4 . 1 线搜索方法 从当 前迭代点x k 出 发，设 搜索方向 a k 己 知且为 下降 方向， 确定步长因子 。 * ， 使 f ( x k + a k 6 k ) ) ， 使 l i mk - - i lx k + l 一 x 11 llx 、 一 二 ， a ,( 1 . 1 8 ) 则称算法产生的迭代序列 二 * 具有q一 阶线性收 敛速率。 若 imk - - 二 * + ， 一 x - 11 iix 、 一x . 11 二o ,( 1 . 1 9 ) 则 称算 法产生的 迭代序列 x k 具 有q一 阶 超 线 性 收敛 速 率。 最优化中，牛顿法和拟牛顿法都具有很好的局部超线性收敛速率。牛顿法对非二次 函数不能保证有整体收敛性，但当初始点靠近极小值点时，收敛速度一般是快的。 算法的另一个重要特征为终止迭代所需要的收敛准则。对使用者来说，最有用的也 许是要求f ( x k ) 一f ( x . ) i 或ix 、 一 x 川e ， 其中 参数。 由 使用者提供。 但由 于上述准 则需 要 预先 知 道解的 信息， 因 而是不实 用的 。 事实上，由 于!lx k + l 一 x k l 是 误差ix 、 一 x 11 的一个估计，因此我们有时采用 il x k + l 一 x k l l :( 1 .2 0 ) i ( x k + l ) 一( x k ) % l 兰氏 ， 叭( 1 .2 1 ) 其中 ( x k ) ， 表 示向 量 二 * 的 第i 个分 量。 另 一 个 可以 采用的 终止 准则 是 f ( x k ) 一 f ( x k + 1 ) : .( 1 . 2 2 ) 值得注意的是，以上的终止准则并不是万能的。在不同的最优化方法中往往采用不同的 终止准则，有时甚至是同时采用几个不同的收敛准则。 1 .4 两类常用的最优化的整 体收敛性方法简介 从 ( 1 . 1 6 ) 式可以 看出，不同的步长因子 a k 和不同的搜索方向 b k 将构成不同的 迭代方 法。其中，线搜索方法与信赖域策略是保证最优化方法总体收敛的两类技术。 下面我们 分别作一下简单的介绍。 1 .4 . 1 线搜索方法 从当 前迭代点x k 出 发，设 搜索方向 a k 己 知且为 下降 方向， 确定步长因子 。 * ， 使 f ( x k + a k 6 k ) f ( x k )( 1 . 2 3 ) 的问题就是关于a的线搜索问题。 第5 页 1 . 4 两类常用的最优化的整体收敛性方法简介 由于精确线搜索需要的计算量大， 而且在实际上也不需要。因 此， 人们提出了 既花 费较少的计算量，又能达到足够下降的不精确线性搜索方法。 一般地，线性搜索算法分成两个阶段。第一阶段确定包含理想的步长因子( 或问题最 优解) 的 搜索区间; 第二阶段采用某种分割技术或插值方法缩小这个区间。 要求每步迭代都有充分下降的线搜索技术，我们称为单调的线搜索。对于单调线搜 索， a fm ij o 和g o l d s t e i n 分别 提出了 不精 确一 维 搜索过 程， 要 求步 长因子 满足 f ( x k + a k b k ) :5 f ( x k ) + p a k ) f ( x k ) t b k ( 1 .2 4 ) o f ( x k + a k b k ) t 6 k ? ( 1 一 p ) o f ( x k ) t b k , ( 1 .2 5 ) 其 中 。 盖 。 ( 1 .2 4 ) 和 ( 1 .2 5 ) 称 为 a r m ij o - g o ld s te in 准 则。 a r m ij o - g o l d s t e in 准 则 可 能 把 步 长 因 子。 的极小 值排除掉了， 所以 w o l f - p o w e l l 准则给出 了 一个更简单的条件代替， 就是 o f ( x k + a k b k ) t b k ! a v f ( x k ) t b k , 。 ( p , 1 ) . ( 1 .2 6 ) 1 9 8 6 年， g r ip p o 等 人 在1 8 1 中 提出 了 非 单 调的 线 搜 索 技术， 它不 要 求 每 一 步 线 性 搜 索 产 生 的 方向 是下降 的， 放 宽了 对 线 搜 索 的 要 求。 在 搜 索 过 程中 利 用前 q ( q ? 0 ) 次函 数 值 信 息， 使 得f ( x ) 非 单 调 下降 ， 但 仍 保 证 整 体 收 敛性， 从 而 提高 了 线 搜 索的 效