（应用数学专业论文）最优化问题的lanczos路径方法.pdf

申史摘要 摘要 最优化( o p t i m i z a t i o n ) ，就是在复杂环境中遇到的许多可能的决策中，挑选“最好” 决策的科学。在本世纪3 0 年代末，由于军事和工业生产发展的需要，提出了一些不能用 古典微分法和变分法解决的问题。在许多学者和专家的共同努力下，逐渐产生、发展和 形成了一些新的方法，即最优化方法。它是一门应用十分广泛的学科，随着计算机的日 趋发展，以及工程设计，系统识别，管理科学等方面的不断深入，最优化的应用越来越 广泛。本文将探讨用l a n c z o s 路径方法解非线性最优化问题。 l a n c z o s 方法，是用来求解对称方程组a x = 6 的解，将对称矩阵a 进行三对角化然 后再利用回代技术求出方程的解。它也可以用来解特定的大规模稀疏对称特征值问 题a x = 船。该方法涉及到给定的矩阵a 进行局部三对角化。重要的是，在算法过程中不 会有满的子矩阵产生，同样重要的是，a 的两端的特征值的信息在三对角化完成之前早得 多就已经出现。 共轭梯度法是最优化中常用的方法之一，由于具有算法简便，只需要一阶信息，易 于编程，以及需要存储空间小等优点，共轭梯度法已经成为求解大规模问题的一种主要 方法。b u h e a u 和v i a l 在1 7 】中构造了无约束最优化问题的共轭梯度路径，其基本思想是将 标准共轭方向法应用于无约束优化e l 标函数，的局部二次近似函数，得到一组共轭方向序 列。共轭梯度路径定义为该共轭方向序列的线性组合，获得了共轭梯度路径的一些重要 性质。可以证明当共轭梯度路径中的参数趋向于无穷时，产生的搜索方向即为牛顿步或 者拟牛顿步，以导致算法局部超线性收敛的一个重要依据。 l a n c z o s 方法和共轭梯度路径法的思想启迪我们，如果将二者相结合，构造一条新的 路径，使得这条路径既具有l a l d c z o s 向量的性质，又具有共轭向量的性质。最优化问题 的近似二次模型应用l a r l c z o s 方法过程中同时应用共轭梯度法，即对问题三对角化的同 时也计算出了共轭方向序列，这样可以得到l a n c z o s 方向序列和共轭方向序列，由此生 成一条新的路径，称为l a n c z o s 路径。此路径有类似于共轭梯度路径的一些重要性质， 在合理的假设下，证明了此算法具有整体收敛性和局部超线性收敛速率。数值实验，表 明l a n c 7 o s 路径法对于解大型稀疏优化问题有更显著的收敛速率。 本文共分为四章。第一章简单地介绍了无约束优化，约束优化的一些基本概 念；l a n c z o s 法，共轭梯度法及信赖域方法等内容。第二章用l a n c z o $ 路径法求解线性等式 约束最优化问题，通过构造原问题的零空间，将l a n c z o s 法和共轭梯度法相结合应用于零 空间中的近似二次模型，构造了l a n c z o s 路径，利用线性搜索技术得到接受步长，证明了 算法既具有整体收敛性又保持了局部超线性收敛速率。在本章最后给出了部分题目的数 值结果。第三章中给出了有界变量约束优化问题的非单调预处理l a n c z o s 路径算法，先构 第j 页 申天捅耍 造预处理l a n c z o s 路径，沿这条路径获得搜索迭代方向，利用非单调回代技术得到可接受 的步长因子，从而获得新的有足够下降的迭代点。非单调能克服高度非线性化函数的最 优化问题。在本章最后给出了数值结果，表明所提供的算法有效性。最后一章，对本文 的工作进行总结，并提出进一步的研究方向。 关键词：仿射变换；共轭梯度；i a i i c z o $ 方法；整体收敛性：局部收敛速率 第1 i 页 每天摘耍 a b s t r a c t o p t i m i z a t i o nh a sav e r yw i d e l ya p p l i e di nm a n y f i e l d s i ti sat o o lw h i c hc h o o s et h eo p f f m a l m e t h o di nf i n i t eo ri n f i n i t em e t h o d s i nt h i st h e s i s ，w ep r o p o s el a n c z o sp a t ha l g o r i t h mf o rs o l v i n g 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 na n db o xc o n s 仃m n e do p t i m i z a t i o n f o rt h el a r g e s c a l es p a r s es y m m e t r i ce i g e n v a l u ep r o b l e m s ：a x = a z w es o l v et h e s ep r o b l e m b yl a n c z o $ p a t hm e t h o d t h r o u g ht r i a n g u l a t i n gt h em a t r i xa ，w e o b t a i na t r i a n g u l a rm a t r i xw h i c h w es i g na st i ti si m p o r t a n tt h a tt h e r ec a nn o tg e n e r a t eaf u l ls u b m a t r i xi nt h ea l g o r i t h mp r o c e s s ， a n dt h ee i g e n v a l u e so fam u c he a r l ya p p e a ri nt h et r i a n g u l a t i n gt h em a t r i xap r o c e s s t h ec o n j u g a t eg r a d i e n tm e t h o di st h em o s tp o p u l a rm e t h o di no p t i m i z a t i o n b e c a u s ei tc a n b ee a s f l yp r o g r a m m e da n dc o m p u t e d ，t h i sm e t h o dh a sb e c o m ea ni m p o r t a n tm e t h o df o rs o l v i n g l a r g e s c a l ep r o b l e m s b u l t e a ua n dv i a lf o r m e dac o n j u g a t eg r a d i e n tp a t ho fu n c o n s t r a i n e do p t i m i z a t i o n t h ep a t hi sd e f i n e da sl i n e a rc o m b i n a t i o no fas e q u e n c eo fc o n j u g a t ed i r e c t i o n sw h i c h a r eo b t a i n e db ya p p l y i n gs t a n d a r dc o n j u g a t ed i r e c t i o nm e t h o dt oa p p r o x i m a t eq u a d r a t i cf u n c t i o n o fu n c o n s t r a i n e do p t i m i z a t i o n w ec a ng e ts o m ep r o p e r t i e so ft h ep a t hb a s e do nt h ec o n j u g a t e p r o p e r t yo fd i r e c t i o ns e q u e n c e n o to n l yh a dt h ep a t hg l o b a lc o n v e r g e n c e ，b u ta l s oi th a sl o c a l s u p e r - l i n e a rc o n v e r g e n c er a t e i nt h i st h e s i s ，w ec o m b i n el a n c z o sm e t h o dw i t hc o n j u g a t eg r a d i e n tm e t h o d , a n dc o n s t r u c ta f l e w p a t h ，w h i c h h a s b o t h p r o p e r t i e s o f l a n c z o s v e c t o r s a n d p r o p e r t i e s o f c o n j u g a t e g r a d i e n t p a t h t h em a i ni d e ao ft h i sm e t h o di st h a tw ee m p l o yl a n c z o sm e t h o dw h i l ee m p l o yc o n j u g a t eg r a d i e n t m e t h o df o rt h ea p p r o x i m a t eq u a d r i cm o d e lo ft h eo p t i m i z a t i o n ，w ec a no b t a i nt h es e q u e n c e so f l a n c z o sv e c t o r sa n dc o n j u g a t eg r a d i e n tv e c t o r s t h e nc o n s t r u c tl a l l c z o sp a t hw i t ht h e m t h ep r o p - e r t i e so ft h i sp a t ha i es i m i l a rt ot h ec o n j u g a t eg r a d i e n tp a t h i ti si m p o r t a n tt oa n a l y s i st h eg l o b a l c o n v e r g e n c ea n dt h el o c a ls u p e r - l i n e a rc o n v e r g e n c eo ft h ea l g o r i t h m t h et h e s i sc o n s i s t so ff o u rc i l a p t e r s i nc h a p t e r1 ，w ep 陀s e n ts o m eb a s i cc o n c e p t sa b o u t o p t i m i z a t i o n s t h ep r e c o n d i t i o n i n gl a n c e sp a t hf 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 ni st h et o p i c o fc h a p t e r2 i nc h a p t e r3 ，w eg i v e sa na f f i n es c a l i n gi n t e r i o rp r o j e c t e dl a n c e sp a t ha l g o r i t h m f o rb o xc o n s t r a i n e do p t i m i z a t i o n t h el a s tc h a p t e rc o n c l u d e st h em a i nr e s u l t so ft h i st h e s i sa n d p r o p o s e ss o m ef u r t h e rr e s e a r c hd i r e c t i o n sa b o u to u rw o r k k e yw o r d s ： a f f i n et r a n s f o r m a t i o n ；l a n c z o sm e t h o d ；c o n j u g a t eg r a d i e n t ；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 第1 页 之复符号 鞭表 主要符号对照表 n 维实向量空问 礼m 维实矩阵 e u c l i d 范数 o o 一范数 r t 维决策变量 向量z 的第j 个分量 目标函数的局部极小值点 目标函数 ，在当前迭代点z 放b 的函数值 约束函数 可行集 严格可行内点集 等式约束指标集 不等式约束指标集 约束优化问题在可行点z 处的起作用集 ，在z 处的梯度 ，在z 处的h e s s e 阵 c 在z 处的j a c o b i a n a ) = y ( z ) z 。) 】ir 孑l y ( z ) 舻。m其m 列构成a ( z ) 值空间的一组标准正交基 z ( 功舻。( 一竹t )其n m 列构成a ( 茁) t 零空间的一组标准正交基 a ，p l a g r a n g e 乘子 l ( z ，a )约束优化问题的l a g r a n g e i 弱数 巩搜索方向 磋 值空间步 机扫) 目标函数在z t 处的局部二次近似 信赖域半径 c ( 铷) = 扣g p if ( x ) ，( 跏) ) 水平集 f k ( 7 ) 线性约束优化问题的l a n c z o s 路径 第1 v 页 动心 训钾 解 m 瞻 0 功加妨妨玢 鑫；舭矾，纠az荆排刖荆泐 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研 究成果论文中除了特另, j d n 以标注和致谢的地方外，不包含 其他人或机构已经发表或撰写过的研究成果其他同志对 本研究的启发和所做的贡献均已在论文中做 明确的声明 并表示了谢意 作者签名： 日期： 论文使用授权声明 本人完全了解上海师范大学有关保留、使用学位论文的规 定，即：学校有权保留送交论文的复印件，允许论文被查阅 和借阅；学校可以公布论文的全部或部分内容，可以采用 影印、缩印或其它手段保存论文保密的论文在解密后遵 守此规定 作者签名： 刷稚各桫期 第一章引言 1 1l a n c z o s 方法 第一章引言帚一早j ii l a n c z o s 方法可以用来解特定的大规模稀疏对称特征值问题a x = a z 该方法涉及到对 给定的矩阵a 进行局部三角化。然而，与h o u s e h o l d e r 方法不同的是，在算法过程中不会有 满的子矩阵产生。同样熏要的是，a 的两端特征值的信息在三角化完成之前早得多就已出 现。因此，在只需要矩阵a 的少量最大或最小特征值的时候，l a n c z o s 方法有明显的优越 性。 假定a 舻一为大型、稀疏的对称矩阵，且只需要求出它的少数几个最大或最小的 特征值。这个问题可用l a n c z o s 于1 9 5 0 年提出的方法解决。此方法产生一列三对角阵死， 其最大与最小特征值越来越好地近似a 的最大与最小特征值。本节将介绍这一技巧并研究 其确切的运算特性。在本节中，用九代表第i 个最大的特征值。 k r y l o v 子空间利用求r a y l e i g h 商r ( x ) = 7 x t 可a z ，z o 的优化问题来引入l 肋c z o s 算法， 从而它惊人的收敛性不会来的太突然。 引理( c o u r a n t 飚h e r 极小极大引理) 如果a 舻“为对称阵，则 州舻螂m a m x 船等_ 1 。，亿 由引理知，r ( x ) 的最大、最小值分别为a l ( a ) 与k ( a ) 。假设q l 舻是正交向量。令 帆呐( 簖缘) = 搿紫铺m 胃a x ( 蚴) 妯( 乱 佻= 丸( q ：a 仉) = 骧蛩紫= | | 瓣竺。r ( q 训k ( a ) 其中仉= q l q ，q k ，考虑如何产生吼，使得慨和m k 是a 1 ( a ) 和k ( a ) 越来越好的近似， 就可导, q 4 , l a n c z o s 方法。 设“s p a n ( q 1 ，q k ) ；i m k = r ( u ) 。由于r ( z ) 在梯度方向 v r ( x ) = i ；( a z r ( z ) z ) 增加最快。所以，如果选取q k + l 满足 v r ( u k ) s p a n ( q 1 ，q k + 1 ) ( 1 1 ) 我们有 缸+ 1 靠( 这里假定d r ( u k ) o ) 。同理如果设讥s p a n ( q t ，瓠) 且r ) = m k ，我们选择吼+ 1 使得 v r ( v ) s p a n ( q 1 ，吼+ 1 ) 第1 页 ( 1 2 ) 1 1l a n c z o $ 方法 因为r ( z ) 在负梯度方向一c i r ( z ) 下降最快。 要寻找一个单独的l q k + l 满足两个条件( 1 1 ) 、( 1 2 ) 。因为v r ( v k ) e s p a n ( x ，a 。) ，如 果 s p a n ( q l ，q k ) = s p a n ( q 1 ，a q l ，a 一1 q 1 ) 且选取讥+ 1 使得 s p a n ( q 1 ，q k + 1 ) = s p a n ( q 1 ，a q l ，a k q l ，a q 1 ) 很显然( 1 1 ) 和( 1 2 ) 可同时满足。于是，导致了计算k r y l o v 子空间： k ( a ，q ，k ) = s p a n ( q l ，a q l ，a k - i q l ) 的标准正交基，这恰好就是k r y l o v 矩阵 k ( a ，q l , n ) = 【q l ，a q l ，a 1 q 1 的像空间。 为了能有效地找出这组基，我们利用矩阵a 的三对角化与k ( a ，q l ，n ) 的q r 分解之间 关系。设q 7 a q = t 是三对角阵，且q e l = q l ，则 k ( a ，q l ，n ) = q e 1 ，t e l ，t k - l e l 】 这正是，q l , n ) 的q 冗分解，其中e 1 = 厶( ：，1 ) 因此，用第一列为仇的正交阵来三对角化 阵a 就能有效地来求出吼 直接计算三对角阵t = q t a q 。令q = 【q l ，训 t = j 1 他 他如加 1 k 一16 k 一1 1 k 比较矩阵方程组a q = q t ，对k = 1 ：竹一1 有 讯6 k a 吼= 饥一l 弧一1 + 以弧+ 讥弧+ 1 ，加q o = 0 利用吼的正交性可得矗= 靠a q k 。并且，如果= ( a 一6 k i ) q k 一饥一l q k 一- 非零， 则吼+ l = 卺，其中饥= i i r k l l 2 。若。r k = o , i o 迭代停止，但已得到关于不变子空间的有价值 的信息。因此，整理上述迭代公式的顺序，得如下的l a n c z o s 迭代算法： 初始步 选定参数r o = q 1 ，7 0 = 1 。q o = 0 ，k = 0 ，转主步。 第2 页 第一审 言 主步 w h i l e ( 讥o ) = 笔；詹= k + l ；以。q t a q k r k = ( a 一以1 ) q k 一弧一1 ( 1 3 ) 讯= l i r k l l 2 e ，i d 不失一般性，在上述算法中取为正数，吼称为l a n c z o s 侑1 量。 当口l 包含在一个真不变子空间时，在完全三对角化之前迭代就会停止。从而说 明l a n c z o s 方法是有限步终止的，我们将它概括如下： 定理1 1 1 设a 舻。n 为对称矩阵，q 1 舻且f 1 2 = 1 ，则l a 眦z o s 迭代( 1 3 ) 进行到 第= m 步终止，其中m = r a n k ( a ，q 1 ，n ) 此外，对所有的七= 1 ：m ，有下式成立： a q = q k t k + r k e ： 其中q k = 【q l ，叽】的列正交，r a n k ( q 女) = k ( a ，q l ，后) 。 其实定理的结论是很显然的，若a m 秩是有限，那么关于a 正交的向量个数，显然不超 过a 的秩。 1 2 共轭梯度方法 在所有需要计算导数的优化方法中，最速下降法是最简单的，但它速度太慢。拟牛 顿法收敛速度很快，但被广泛认为是非线性规划的最有效的方法。但拟牛顿法需要存储 矩阵以及通过求解现行方程组来计算搜索方向，这对于诸如一些大规模问题几乎是不可 能办到的。共轭梯度法在算法的简便性、所需存储量等方面均与最速下降法差别不大， 而收敛速度比最速下降法要快。正因为这些原因，许多实际部门的工程师十分喜欢用共 轭梯度法。 线性方程组 a z = b x 孵 线性方程组( 1 4 ) 等价于最优化问题 嬲i ，a x - b r 矗 定3 l 1 2 1 2 4 1 设a 8 妒n 对称正定，d 1 ，d 。时婀，中的一组非零向量，如果 d a 由= 00 j ) 第3 页 ( 1 4 ) ( 1 5 ) ( 1 6 ) 1 2 笋轨： g 腰方法 则称d 1 ，d m 是相互a 一共轭的。 显然可见，如果d 1 ，d m 是相互a 一共轭的，则它们是线性无关的。设，为单位阵，则 知j 一共轭就是正交。 共轭方向的优点之一是，它能将一个n 元线性方程组化为n 个单元线性方程。 定理1 2 1 设a 舻n 对称正定，d l ，厶时n 各相互a 一共轭的向量，对任意给的b g p ， 扛喜箍也 ， 是a z = 6 的解。 对线性方程组( 1 4 ) 的共轭梯度法为： 初始步 选定参数z o ，r o = a x o b ，k = 0 ，转主步。 主步 w h i l e ( r k 0 ) k = k 牟1 i fk = 1 d l = 一，b e l s e 凤= 石r t 石r a d k = 一堍+ 8 k d k 一1 e n d 。= 币r 瓦r k z k 2 x k l + o k d i r k + l = r k + o a d k e n d 这种方法也称为线性共轭梯度法，下面定理给出了线性共轭梯度法的一些基本性 质。 定理1 2 2 1 2 6 1 上述算法经过不超过n 次迭代就会终止，即存在m n ，使得 r m + 1 2 0 第4 页 ( 1 8 ) 第一章引言 而且对一切1 sk m 和l j k 一1 ，都有 d k = 一i h l l 2 r t a r j = 0 r 弛= 0 r 跏= 0 线性共轭梯度法除对病态问题尚有待深入研究外，其理论已相当完善。目前，结合 预条件技巧的先行共轭梯度法被广泛应用于线性方程组的求解。接下来我们简单的介绍 一下预处理共轭梯度法。 对于方程组( 1 4 ) ，由于共轭梯度法的收敛速度与a 的条件数紧密相关，条件数值越小 收敛速度越好。故要提高共轭梯度法的收敛速度，就要降低a 的条件数，这叫做预处理或 预条件。即找一个近似于a 的矩阵m ，它也是对称正定的。用m _ 1 左乘以方程组( 1 4 ) 两端 得到其等价的方程组 m 一1 a x = m b z 舻 ( 1 9 ) 使得m 一1 a 的条件数比a 的条件数要小，称m 为预处理阵( p r e e o n d i t i o n e r ) 。如果m - 1 a 的 条件数很小，又可以用共轭梯度法求解方程组( 1 9 ) ，那么共轭梯度法的收敛速度可以大 大提高。必须注意，即使a 和m 都对称，但是m - 1 a 未必对称，所以不能用共轭梯度法直 接求解方程组( 1 9 ) 。为了保持对称性，引入内积( ，) 肘以及它与殴几里得内积( ，) 的关 系，有如下引理 引理1 2 1 设m ，a 舻一且均为对称正定矩阵，则有下列关系式成立： ( z ，y ) m = ( m x ，y ) = ( z ，m y ) ( 1 i o ) 是一种内积，称为m 内积，它是自共轭的。从而有性质： ( m 一1 血，可) f = ( a x ，y ) = ( z ，a y ) = ( z ，m ( m 一1 a y ) ) = m x ，m - 1 a y ) = ( z ，m 。1 a y ) m ( m a x ，y ) m = ( a x ，y ) 0 且( 1 1 2 ) 式仅当z = 0 时，等号才成立。 定理1 2 3 设m ，a 舻。“且均为对称正定矩阵，b 舻，则 m 。a x + = m 。1 b 甘p ( 矿) 2 瓣p ( z ) 其中p ) = i 1 ( ，一1 a x ，z ) m 一( m 一1 b ，z ) m 由此得到m 内积下求解方程组( 1 1 0 ) 的预处理共轭梯度法 第5 页 ( 1 1 1 ) ( 1 1 2 ) 1 3 约直零至司表示 初始步 选定参数z o ，r o ；a 知一b ，m ，z o = 一m _ 1 r ok = 0 ，转主步。 主步 w h i l e ( 0 ) k = k 1 l ，k = 1 d l = z o e l s e 展= 磊r r 石z k d k = ；一z k + 8 k d k 一1 e n d a t = 币r r 瓦z k z = z k 一1 + n d k r k + 1 = r k + a k a d k e n d 在此算法中，每个迭代步k 都需要求解方程组 m z = r 所以要求预处理器不仅对称正定，尽可能近似于a ，而且应使计算式m z = r 时候，节省 存储、节省时间。 1 3 约束零空间表示 考虑问题 詈s t 八a t 引x ：b ( 1 1 3 ) = 。 a r 硝r ib 尉，l n 。以下不妨设矩阵a 满秩，即秩为z ，基于矩阵a ，可将舻划分 为两个互补的子空间：一个是由a 的列向量所生成得值空间，另一个是a 7 的零空间。 设y 为a 的值空间的一组基及所构成的矩阵，而矩阵z 的各列组成的零空间的一组 第6 页 第一章；! 言 基。因为a 的秩为z ，故y 和z 分别有z 和n f 列，即y 卵。和z 咿。( ”一) ，且【y 刁非奇 异，a t z = 0 ，a t y 非奇异，以下不妨设a r y = j ，于是由约束条件所定义的任何可行点 都可表示为 z = y b + 2 冶，岔墨p 一( 1 1 4 ) 且问题( 1 1 4 ) 可等价地转化为下列无约束优化问题 r a ，i n f ( 童) = f ( y b + z e ) ( 1 1 5 ) 圣i 卜一l 因此可以说，求解线性等式约束优化问题的关键在于如何使当地选取矩阵a r 零空间 中的一组基，即矩阵z ，现在有许多求解线性等式约束优化问题的不同方法，它们的主要 区别本质上就在于确定和表示z 的不i 司方式，尽管有些方法并没有显示形成矩阵z 。 考虑如何去确定y 和z 的问题。一个常用而且重要的方法就是基于a 的q r 分解， a = q 苫 = c q - ，q 。， 苫 = q 冗 其中q 舻。n 正交阵，q 1 g p ”，q 2 g p 。m 一) ，r 耐。上三角阵a 因为a 满秩，所 以尼。1 存在。不难看出，若取 y = q 1 r t ，z = q 2 则y 和z 具有所需的性质。 上述q r 分解法的主要优点在于其数值稳定性，这是因为作为正交矩阵的一部分，我 t f l n z r z = 一0 。( 。一j ) ，所以这种方法不会引起数值误差的增加或条件数的变坏。 1 4 约束问题的最优性条件 约束最优化问题的一般形式为 m i n ( x ) s t c ( z ) = 0 ，i ， ( 1 1 6 ) c ( z ) 20 ，i 工 其中q ( z ) 是约束函数，和z 分别是等式约束的指标集 l ，2 ，m ) 和不等式约束的指标 集 m + 1 ，m + 2 ，：p ) 定义i a 1 对于一般约束优化问题( 1 1 6 ) ，记其可行域为 d 箩 z i q ( 。) = 0 ，i ；c f ( 卫) 0 ，i z ) ( l 1 7 ) 第7 页 1 4 约衷，司趁哎最傀恒暴件 若对矿d ，存在e 0 ，使当z d 且忙一矿0 e 时，总有 ( x ) f ( x + ) ( 1 1 8 ) 则称矿为约束问题( 1 1 6 ) 的局部解，或者简称矿为最优解。若当矿d j j o ，( 矿) ( 1 1 9 ) 则称矿为约束问题的严格局部解。 在讨论矿为约束优化问题的局部极小点的最优性条件之前，我们引入约束优化问 题( 1 1 6 ) 的l a g m g e 函数 其中a 称为拉格朗日乘子。 定理1 4 1 ( 约束问题局部解的一介必要条件) 设约束问题( 1 1 6 ) 中，( z ) ，g 0 ) 具有连续的 一介偏导数，若文d 是约束j - i 题( 1 1 6 ) 的局部解，并且在z 。d 处约束限制条件成立， 则存在向量”= ( 墨，k ) t ，使得 p v 。l ( z ，a + ) = v f ( z + ) + k v c f ( z + ) = 0 ， ( 1 2 1 ) = 1 q ( z ) = 0 ， q ( z ) 0 ， w 0 ， a 麓( 矿) = 0 ， i i 2 7 i z i z ( 1 2 2 ) ( 1 2 3 ) ( 1 2 4 ) ( 1 2 5 ) 其中l ( z ，a ) 为l a 伊绷g e 上述函数。 由于这一定理是k u h n 和t u c k e r ( 1 9 5 i ) 给出的，因此称上述一介必要条件为k u h n t u c k e r 条件( k u h n - t u c k e rc o n d i t i o n s ) 或称为k t 条件。称满足一介必要条件的点为k u h n - t u c k e r 点，或简称k - t 点， 为矿处的l a g r a n g e 乘子。 由定理1 4 1 立即可得无约束最优化问题的一阶必要性条件为 v ( x 1 = 0 定理1 4 2 1 2 6 1 ( 约束问题局部解的二阶充分条件) 考虑一般约束优化问题( 1 1 6 ) ，设，( z ) 和q ( z ) ，i = 1 ，2 ，m 具有连续的二阶偏导数，若存在矿满足下列条件： ( 1 ) k - t 条件成立即存在”一( 姆，摊) t 使得 p 亿l ( 矿，”) ；v f ( z + ) + 鬈v q ( 矿) = 0 t = 1 第8 页 z q ， 一 ， = 入zl 第一章l 言 q ( z ) c ( z ) 譬 n q ( 矿) = 0 ，i ； 0 ，i z ； 0 ，i z ； = 0 i z 且w 和c f ( 矿) 0 刁不同时为零( 称为严格松弛互补条件) ( 2 ) 对于任意的d q ，有 d r y 。l ( z 4 ，a + ) d 0 其中q = d i d 0 ，v c ( z + ) r d = o ，i e u z ( x ) ) ，z ( 矿) 是矿处的有效约束指标集，则矿是 约束问题( 1 1 6 ) 的严格局部解。 1 5 算法的收敛。眭 这一节主要介绍有关算法的基本概念。 1 5 1 算法的收敛性 最优化算法是一类迭代方法，即从任意的初始点x l 出发，构造出点列 z ) ，并满足 i ( x k ) ，( z + 1 ) ，k = 1 ，2 ，( 1 2 6 ) 但这个条件并不能保证序列 ) 达到或收敛到无约束问题的最优解。 所谓收敛，是指序列 z 女) 或它的一个子列( 不妨仍记为 z k ) ) 满足 l i m x c 2 矿 这里矿是无约束优化问题的局部解。 但是通常要获得( 1 2 7 ) 这样强的结果是困难的，往往只能证明 z ) 的任一聚点的稳定 点，或者证明更弱的条件 l i 。m 一。i n f i l v f ( x k ) l l = 0 ( 这种情况也称为收敛) 。若对某些算法来说，只有当初始点z 1 充分靠近极小点矿时， 才能保证序列 z k ) 收敛到矿，则称这类算法为局部收敛。反之，若对任意的初始点x l ， 产生的序列 瓤) 收敛到矿，则称这类算法为全局收敛。 1 5 2 算法的收敛速率 如果算法产生的序列 z ) 虽然收敛到矿，但收敛的太”慢“，以致于在计算机允许 的时间内仍得不到满意的结果，那么，这类算法也称不上收敛。因此，算法的收敛速率 第9 页 是一个十分重要的问题。 这里简单地介绍一个收敛速率的有关概念。 设序列z - 收敛到矿，若极限 熙铬暑硝 z 功 存在，当o p 0 n + 1 = 巩吼一6 i w l m t 以一l ( 2 2 1 ) ( 2 2 2 ) ( 2 2 3 ) ( 2 2 4 ) ( 2 2 5 ) ( 2 2 6 ) ( 2 2 7 ) ( 2 2 8 ) ( 2 2 9 ) 这里 o i = - 九一- 巩一- m t ，屈= 翕兰罢舞 。，丸= 譬蓦警 。c z 2 其中 死为对称正定矩阵，v y k