（运筹学与控制论专业论文）非线性最优化问题中若干重要算法的理论研究.pdf

非线性最优化问题中若干重要算法 的理论研究 摘要 本文主要是对非线性最优化问题中的若干重要算法的理论分析作了探讨，包括约束 最优化问题中的梯度投影方法以及求解变分不等式和互补问题的几类算法，主要是集中 在这几种算法的收敛性分析上。 第一章是绪论部分，简单介绍了变分不等式与互补问题，本文所研究的内容，以及 本文的主要工作。 第二章研究了通过广义d 一间隙函数求解变分不等式问题的一种方法的收敛性和误 差界估计。我们知道，通过广义d 一间隙函数，可以将变分不等式问题转化为一个无约 束极小化问题。近来，p e n g 和f u k u s h i m a 提出了一种混合n e w t o n 类型的方法来极小化 一个特殊的广义d 一间隙函数，在本章中，我们将这种方法用来极小化一般形式的广义 d 一间隙函数g 甜a 我们证明了算法具有更强的收敛性质。在合适的条件下，证明了算法 的全局收敛性和局部二次收敛性。更进一步，当广义d - 间隙函数g 。中的参数取值于 某一区间时，证明了函数g 。对于强单调变分不等式而言，具有有界的水平集，同时， 给出了算法的一个误差界估计，它部分回答了y a m a s h i t a 等人提出的一个问题。 第三章对求解互补问题的阻尼g a u s s n e w t o n 方法作了研究，这种方法最早是由 s u b r a m a n i a n 提出的。本章主要研究了阻尼g a u s s - n e w t o n 方法的全局收敛性，在较弱 的条件下，获得了一个更强的全局收敛结果，该结果推广了相应文献中算法的全局收敛 性结果。同时，我们给出了种不需要线性搜索的新的步长选择方法，研究了在此步长 规则下的阻尼g a u s s n e w t o n 方法，得到了一个更好的全局收敛结果。 第四章对求解互补问题的可微的无约束优化法作了研究。在将互补问题转化为一个 无约束优化问题的基础上，给出了一种求解互补问题的混合方法，证明了该算法的全局 收敛性。 第五章研究了求解约束最优化问题的梯度投影方法，在步长的选取时采用了一种新 的策略，这种策略不需要进行传统的线搜索旦包含步长取常数这种特例，在较弱的条件 下，证明了梯度投影方法的全局收敛性。进一步给出了目标函数- 厂( x ) 是凸函数和拟凸 函数时的更强的收敛性结果。 i 第六章是结论部分，主要对本论文的内容作了简单的概括和分析。 关键词：变分不等式问题：互补问题：梯度投影方法；无约束最优化；收敛性 l j o n t h e o r y o fs o m e i m p o r t a n ta l g o r i t h m s i n n o n l i n e a r o p t i m i z a t i o n p r o b l e m s a b s t r a e t s o m ei m p o r t a n ta l g o r i t h m sf o rn o n l i n e a ro p t i m i z a t i o np r o b l e m s a x es t u d i e di nt h i s d i s s e r t a t i o n t h ea i mo f t h i sd i s s e r t a t i o ni st og i v es o m et h e o r e t i c a la n a l y s i s c h a p t e r 1i st h ei n t r o d u c f i o no ft 1 1 i sd i s s e r t a t i o n ，w h i c hi n t r o d u c e st h ev a r i a t i o n a l i n e q u a l i 母p r o b l e ma n d t h ec o m p l e m e n t a r i t yp r o b l e m ，t h ec o n t e x to ft h i sd i s s e r t a t i o na n dt h e m a i nr e s u l t so b t a i n e di nt h i sd i s s e r t a t i o n a h y b r i dn e w t o n t y p em e t h o df o rs o l v i n gt h ev a r i a t i o n a li n e q u a l i t yp r o b l e m ( v i p ) i s s t u d i e di nc h a p t e r2 i ti sk n o w nt h a tt h ev i pc a l lb er e f o r m u l a t e da sa nu n c o n s t r a i n e d m i n i m i z a t i o np r o b l e mt h r o u g ht h ed g a pf u n c t i o n r e c e n t l y , ah y b r i dn e w t o n t y p em e t h o d w a sp r o p o s e db yp e n ga n df u k u s h i m a ( 1 9 9 9 ) f o rm i n i m i z i n gt h ed g a pf u n c t i o n i nt h i s c h a p t e r , t h eh y b r i dn e w t o n - - t y p em e t h o di s e x t e n d e dt om i n i m i z ea g e n e r a l i z e dd - g a p f u n c t i o n g 。日i nm eg e n e r a lf o r m i t i ss h o w nt h a tt h ea l g o r i t h mh a sn i c ec o n v e r g e n c e p r o p e r t i e s u n d e rs o m er e a s o n a b l ec o n d i t i o n s ，i ti sp r o v e dt h a tt h ea l g o r i t h mi sl o c a l l ya n d g l o b a l l yc o n v e r g e n t m o r e o v e r , w h e n t h ep a r a m e t e r i sc h o s e ni nac e r t a i ni n t e r v a l ，i ti s p r o v e dt h a tt h eg e n e r a l i z e dd g a pf u n c t i o ng 础h a sb o u n d e dl e v e l s e t sf o rm es t r o n g l y m o n o t o n ev i p a ne r r o rb o u n de s t i m a r i o no ft h ea l g o r i t h mi so b t a i n e d ，w h i c hp a r t i a l l y9 1 v e s a l la n s w e rt ot h eq u e s t i o nr a i s e d b yy a m a s h i t a ( 1 9 9 7 ) c t a 1 t h ea u t h o r ss t u d yt h ec o n v e r g e n c ep r o p e r t i e so ft h ed a m p e dg a u s s - n e w t o na l g o r i t h m w h i c hw a s o r i g i n a l l yp r o p o s e db ys u b r a m a n i a nf o rt h ec o m p l e m e n t a r i t yp r o b l e m i nc h a p t e r 4 t h ea i mo ft h i sc h a p t e ri st og i v eag l o b a lc o n v e r g e n c er e s u l tu n d e rw e a k e rc o n d i t i o n s t h e r e s u l t sh e r ei m p r o v ea n dg e n e r a l i z et h o s ei nt h el i t e r a t u r e i na d d i t i o n ，an e w s t e p s i z er u l e ， w h i c hn e e dn o tal i n es e a r c h ，i sp r e s e n t e df o rt h ed a m p e dg a u s s n e w t o na l g o r i t h m an i c e g l o b a lc o n v e r g e n c e r e s u l ti so b t a i n e d i nc h a p t e r 4 ，an e wa l g o r i t h mf o rt h es o l u t i o no fn o n l i n e a rc o m p l e m e n t a r i t yp r o b l e m si s d e v e l o p e d t h ea l g o r i t h mi sb a s e do nar e f o r m u l a t i o no f t h ec o m p l e m e n t a r i t y p r o b l e ma sa l l u n c o n s t r a i n e d o p t i m i z a t i o n i ti sp r o v e d t h a tt h ea l g o r i t h mi sg l o b a l l yc o n v e r g e n t i n c h a p t e r5 ，t h ea u t h o r ss t u d yt h ec o n v e r g e n c ep r o p e r t i e so f t h eg r a d i e n tp r o j e c t i o n m e t h o df o rt h 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 i nt h i sc h a p t e r ，an e w s t e p s i z er u l e ，w h i c h a v o i d sf n l f i l i n gt h ec l a s s i c a ll i n es e a r c ha n di n c l u d e sc h o o s i n gac o n s t a n ta st h es t e ps i z ea sa s p e c i a lc a s e ，i sp r e s e n t e da n da n a l y z e d s o m ec o n v e r g e n c er e s u l t so ft h eg r a d i e n tp r o j e c t i o n i i m e t h o du n d e rm i l d e rc o n d i t i o n sa r eo b t a i n e d f i n a l l yw ec o n c l u d et h ed i s s e r t a t i o nw i t hs o m er e m a r k si nc h a p t e r6 k 。y w o r d s ：v a r i a t i o n a li n e q u a l i t yp r o b l e m ；c o m p l e m e n t a r i t yp m n e m ；g r a d i e n tp r o j e c t i o n m e t h o d ；u n c o n s t r a i n e do p t i m i z a t i o n ；c o n v e r g e n c e p r o p e r t i e s v 查垄堡三奎堂堡主堂焦丝苎 第一章绪论 非线性最优化是运筹学的一个重要分支，研究求解极值问题与约束极值问题的有关 理论和算法，在近几十年来迅速发展并日趋成熟。随着电子计算机的发展和普遍采用， 作为一种有效的最优化方法，非线性最优化在工程设计优化、管理优化、系统分析等多 方面的应用日盏开拓，愈来愈受到应用部门的重视，非线性最优化自身，也在方法和有 关理论的研究方面形成特色，取得很大的进展。 本文将对非线性最优化问题中的几种算法的理论作研究，包括求解变分不等式与互 补问题的几种方法以及求解约束优化问题的梯度投影算法，重点放在对这些算法的收敛 性分析上。 1 1 变分互补问题 变分不等式与互补问题是应用数学中一个十分重要的研究领域，这不仅仅是由于它 在非线性最优化方面具有相当广泛的应用，而且在微分方程、力学、控制论、对策论、 工程学、经济均衡理论、社会和经济模型等许多方面都有着重要的作用( 见文献 卜3 ) 。 变分不等式问题最初作为研究偏微分方程的工具，首先由p h i l i ph a r u n a n 和g u i d o s t a m p a c c h i a 在1 9 6 6 年提出( 4 ) ，接着由g u i d os t a m p a c c h i a 在文献 5 - 6 3 中加以推广， 七十年代以后逐渐引起人们的重视。到目前为止，变分不等式与互补问题，已发展成为 一门内容十分丰富并具有广阔的应用前景的边缘学科，随着科技与经济的发展，它必然 会受到越来越大的重视。 首先，我们来看一下什么是变分不等式问题，什么是互补问题。 定义l _ l ：记z 是倪”的子集，f 是毗“到吼”的映射，变分不等式闻题( 简记为 v m ( x ，f ) ) 就是：求向量工，使得 f ( x ) 7 ( x x ) 0 ，v x e 肖( 1 1 ) 如果f 为线性映射，则称( 1 t ) 为线性变分不等式问题，否则，称为非线性变分不等式 问题。 变分不等式问题的一个最简单的例子就是方程组f ( x ) = 0 ，事实上，在定义1 1 中， 当z 为开集时，v z p ( x ，) 就等价于求解方程组，( 石) = 0 。 变分不等式问题的另一个很重要的特例就是互补问题( c o m p l e m e n t a r i t y p r o b l e m ) ，互补问题首次出现是在r i c h a r dc o t t l e 的博士论文 6 1 中，以后在文献 6 2 中出版。当时还不叫“互补”问题，在后来由c o t t l e ，h a b e t l e r 和l e m k e 在处理线 兰二童丝塑 性情况的文献 6 3 中，才真正被称为互补问题。其标准形式是： 定义l _ 2 ：给定向量函数f ：飒”斗贸”，求一向量x m ”，使得 x 0 ，f ( x ) 0 ，x 7 f ( x ) = 0 ( 1 2 ) 当f ( x ) 为线性函数( 令f ( x ) = 脓+ g ，m 吼，q 巩“) 时，称( 1 2 ) 为线性互补问题 记为l c p ( m ，g ) ；否则，称( 1 2 ) 为非线性互补问题，记为n c p ( f ) 。 显然，在定义1 1 中，当彳为吼“的非负卦限，即， x = 孵：= 扛孵“lz 0 时，v i p ( x ，f ) 与以上n c p ( f ) 是完全等价的。同时，我们也可以看出，变分不等式问 题是互补问题的一个自然的推广。变分不等式问题和互补问题恰似相伴而生的孪生兄 弟，常常出现在有关的书籍和文献中。 关于变分与互补问题的研究，大致分为理论和算法两大研究方向，理论方面的研究 焦点集中于变分不等式与互补问题的解的存在性，唯一性等：而算法方面主要是研究如 何引进和借助有关技术，概念和思想以设计出各种类型的具体的求解方法。 近几年来，变分不等式与互补问题进一步受到广泛和高度的重视，引起许多学者， 尤其是国外学者浓厚的研究兴趣，无论是理论研究还是算法研究都取得了长足的发展， 仅就算法方面来看，研究不仅十分活跃，优秀成果也很丰富，就变分不等式而言，有连 续算法 7 9 ，6 7 ，( 拟) 牛顿型算法 1 0 1 2 ，投影算法 1 3 一1 6 ，6 6 ，投影收缩算法 1 7 2 0 等，它们都是v i p 具有重要意义和代表性的求解方法。对于互补问题，也有许多学者对 此作了单独的研究( 5 4 ) ，到8 0 年代中后期，经过2 0 余年的努力，在算法方面也取 得了丰硕成果：( i ) 对线性互补问题，有直接方法( 如l e m k e 法，c o n i c d e n t z i g 法) 和迭代法( 如m a n g a s a r i a n 法) ：( i i ) 对非线性互补问题，有不动点法，同伦法，投影 法，n e w t o n 法等。9 0 年代以后，人们也提出过许多有效算法，如光滑方程组法 2 卜2 6 ： 非光滑方程法 2 7 2 9 ，7 0 ：可微无约束优化法 3 0 3 5 ；g l p 投影法 3 6 ，3 7 ，1 7 2 0 ；内 点法 3 8 4 2 ，6 9 ；磨光与非内点连续法 4 3 4 5 j ；路径跟踪算法 6 8 等。 以下我们先来回顾一下变分不等式与互补问题的某些概念、结论、以及变分不等式 问题与非线性最优化问题之间的关系。 定义1 2 ( 2 ) ：映射f ：吼“一般”称为在集合x 上是： 1 ) 单调的( m o n o t o n e ) ，如果 ( ，( x ) 一，( y ) ) 7 ( x y ) 0 ，v x ，y x ； 2 ) 严格单调的( s t r i c t l ym o n o t o n e ) ，如果 ( f ( z ) 一f ( y ) ) 。( x y ) 0 ，v x ，y x ，x y ： 查堕型三盔兰堕主堂垡堕墨 3 ) 强单调的( s t r o n g l ym o n o t o n e ) ，如果存在口 0 ，使得： ( f ( x ) 一f ( y ) ) 7 ( x y ) a l l x y 2 ，v x ，y x ： 其中1 2 称为映射f 的单调模( m o n o t o n e m o d u l u s ) 定理1 1 ( 2 ) ：如果映射f 在集合z 上连续可微，则 1 ) 映射f 在集合x 上是单调的，当且仅当对任意x x ，其j a c o b i a n 矩阵v f ( x ) 半正定： 2 ) 映射f 在集合x 上是强单调的且单调模为a ，当且仅当 d r v f ( x ) d 口l l d l l 2 ，v x x ，d 孵”； 3 ) 若对所于有的x x ，映射f 的j a c o b i a n 矩阵v f ( x ) 正定，则f 在集合x 上是 严格单调的。 定义1 4 ( 2 ) ：1 ) 如果映射f 在集合上是单调的，则称变分不等式问题 z i p ( x ，f ) 是单调变分不等式问题； 2 ) 如果映射f 在集合x 上是严格( 强) 单调的，则称变分不等式问题v i p ( x ，) 是 严格( 强) 单调变分不等式问题。 在许多的实际应用中，z l p ( x ，f ) 的可行集x 为闭凸集，且具有以下结构形式： x = x 。：= 婀”i g 。o ) o ，i j = l ，删 ； j ( z ) = 0 ，j j = 埘+ 1 ，卅+ r ) 其中g i ( x ) ( f _ 1 ，m ) 为连续可微凹函数，h j ( x ) ( j = m + 1 ，埘+ ，) 是仿射实值函数。 定义1 5 ( 2 ) ：称集合x 在x 处满足线性无关约束规范，如果有效不等式约束 的梯度，( x + ) ( f + = ，i 晶( z ) = 0 ) 是线性无关的。 变分不等式问题( v z p ( x ，f ) ) 和非线性规划( n p ) 之间存在着密切的关系，这可 以由以下定理得到体现。 定理1 2 ( 2 ) ：( 1 ) 如果f ( x ) 为某个实值函数厂( x ) ：吼“_ + 婀的梯度v f ( x ) ，则 z m ( x ，) 等价于非线性规划m i n 纱( x ) x z 的平稳条件；进一步，如果厂( 砷是伪凸 ( p e s u d o c o n v e x ) 函数( 即由v f ( y ) 7 0 - y ) 0 = ，f ( x ) ，( y ) ，v x ，y 肖) ，x 为凸集 时，v m ( x ，f ) 的每一个解都是该非线性规划的整体最优解。 苎二兰堕堕一 ( 2 ) 当可行集x 取x 。，且满足某种约束规范( 如线性无关约束规范) 时，v i p ( x 。, ，) 等价于以下k k t 条件，即混合线性互补问题n p ： f ( 一v g ( x ) y v h ( x ) z = 0 ( 1 3 ) g ( x ) o ，y o ，g ( 力r y = 0 ( 1 4 ) ( x ) = 0 ( 1 5 ) 其中v g ( x ) = ( v g ，( 石) ，f n v h ( x ) = ( v l ( x ) ，) ；特别地，当f ( 砷= v f ( x ) 时 ( 1 3 ) 一( 1 5 ) 为非线性规划p ( z o ，厂) ：m i n ( f ( x ) l 工z o 的k k t 条件，即v i p ( x ，f ) 等 价f f - n p ( x o , ，) 的艇r 条件。通常称满足( 1 3 ) 一( 1 5 ) 的点为v i p ( x ，) 的k k t 。 定理1 2 较好地刻画了h p ( x ，f ) 和n p 之间的内在联系，即变分不等式问题 v i p ( x ，n 虽然在许多不同分支里有着十分广泛的应用，但它也只能反映p 的一个侧 面。 关于v ；p ( x ，) 的解的存在性，唯一性等的结论，可参见文献 2 ，以下我们只列出 两个比较常用的结果。 定理1 3 ( 2 ) ：如果映射，在集合并上是严格单调的，则变分不等式问题 v i p ( x ，f ) 至多有一个解。 定理1 4 ( 2 ) ：设j 是辨“的非空闭凸子集，f 是x 哼孵”的连续映射。如果f 在 集合石上是强单调的，则变分不等式问题v ；e ( x ，f ) 有且只有一个解。 定义1 6 ( 2 ) ：设x + 是变分不等式问题v i p ( x ，f ) 的解，如果z 满足以下条件( a ) 和( b ) ，则称z 为变分不等式问题v i p ( x ，f ) 的正则解： a ) 存在z 的一个邻域及常数占 0 ，使得对于每一个满足 0 ，使得 4 盔婆望三盔羔竖主堂焦鲨塞一一 i x ( y ) 一x ( ：) l l 蔓l i l y - z 1 ，v y ，z ：i 叫l j ， z 8 s j 1 2 研究内容 本文主要是对变分不等式和互补问题以及非线性规划中的几个算法作了探讨，主要 是集中在这几个算法的理论分析上。以下简单介绍下本文所涉及算法的一些内容。 ( 一) 求解变分不等式问题的基于最优化的方法，这种方法是通过引入有效的效用 函数和采用线性搜索技术，将变分不等式问题转化为约束或无约束最优化问题。如 m a r c o t t e 和d u s s a u l t 在1 9 8 7 年首先利用间隙函数( g a p f u n c t i o n ) g ( 工) = m a x ( x y ) 7f ( x ) 幢 给出了求解单调变分不等式问题的间隙函数下降法( 4 6 ) 。在f 为强单调及严格互补性 成立的条件下，算法整体收敛且局部等价于基本n e w t o n 法。但是间隙函数g 一般是不 可微的。f u k u s h i m a 在1 9 9 2 年构造出了一个可微的价值函数厂，将一般非对称变分不 等式问题v i p ( x n 转化为一等价的最优化问题： r a m i n ，( z ) 并给出了求解该等价最优化问题的一个下降方法( 3 3 ) 。只要映射f 连续可微，函数厂 也连续可微，当v f ( x ) 对任意x x 正定时，价值函数f ( x ) 的任意稳定点也是其整体极 小值点，从而是v i p ( x ，f ) 的解。在x 为紧凸集，v f ( x ) 对任意x x 正定的条件下，所 给下降算法整体收敛需要精确线性搜索；所给下降算法允许a r m i j o 非精确线性搜索也 能整体收敛的条件是：x 为紧凸集，f 强单调，f 及v f 均l i p s c h i t z 连续。对集合x 的 紧性要求降低了方法的实用价值，因为大部分实际问题中的集合彳只是非空闭凸集。 t a j i ，f u k u s h i m a 和i b a r a k i 于1 9 9 3 年利用 3 3 中f u k u s h i m a 可微价值函数， ( x ) ，对一 般的非空闭凸集合z ，采用a r m i j o 非精确线性搜索技术，给出了求解强单调变分不等 式问题的另一整体收敛下降算法【1 2 当x 为多面体凸集，v f 在x 的一个邻域内 l i p s c h i t z 连续及严格互补性条件在x 成立时，方法局部等价于基本n e w t o n 方法，从而 有二次收敛速率。l a r s o n 和p a t r i k s o n 于1 9 9 4 年在文献 4 7 中推广了a u c h u t y 的1 9 8 9 年的结果( 4 8 ) ，给出了包括原始对偶间隙函数、f u k u s h i m a 价值函数在内的一类新的 笙= 童 堕鲨 价值函数，研究了变分不等式问题解集的特征并给出了一个求解非对称变分不等式问题 新的下降算法，其中f u k u s h i m a 的下降算法是它的一个特例。同时，z h u 和m a r c o t t e ( 4 9 ) 在1 9 9 4 年通过引进包括f u k u s h i m a 价值函数在内的两类可微价值函数，给出了求解非 对称单调变分不等式问题的一类非常一般的整体收敛下降算法，该算法包括了1 9 9 3 年 w u ，f l o r i a n 和m a r c o t t c 提出的求解变分不等式问题的一般下降算法( 5 0 ) 及t a j i ， f u k u s h i m a 和i b a r a k i 算法 1 2 ，但是上述算法都需要f 满足强单调性条件来保证每次迭 代能产生可行下降方向。要求映射f 强单调的条件是非常苛刻的，所以构造适应非强单 调变分不等式问题的类似整体收敛算法是相当有价值的。最近，p e n g 3 4 和 y a m a s h i t a ，t a j i 与f u k u s h i m a 5 1 等人利用f u k u s h i m a 价值函数，相继将可行集x 取x o 且 满足非线性规划中基本约束规范的一类变分不等式问题v i p ( x ，f ) 转化成一等价的无约 束优化问题： m i n 甲( x ) j e m “ 在适当的假设条件下，证明了该类变分不等式问题的解不仅是函数w ( x ) 的整体极小值 点而且是其严格局部极小点，从而可用n e w t o n 法或拟n e w t o n 法求得其解。 ( 二) 求解互补问题的光滑方程法。这类方法就是把互补问题转化为一个与之等价 的光滑方程组，然后用n e w t o n 类型的方法法求解。m a n g a s a r i a i l 于1 9 7 6 年在文献 2 1 中首先提出此种方程组： i 庐( 而，e ( 曲) i g ( x ) ：= l i l = 0 ， ( 1 6 ) i 庐( x 。，e ( x ) ) j 庐( 口，b ) = o ( 1 a b l 一o ( a ) 一o ( b ) ， ( 1 7 ) 这里，f ( x ) 是f ( x ) 的第f 个分量，i = l ，2 ，”，o ( t ) ：贸哼婀是个严格递增的函数 满足口( o ) = 0 ，称庐( 口，6 ) 为n c p 函数或势函数。在文献 2 1 中，m a n g a s a r i a n 证明了非 线性互补问题( 1 尸( f ) 的解与光滑方程组( 1 6 ) 解的等价性。 为了保证这种方法的整体收敛性，w a t s o n 2 3 建立了个同伦算法( 取目( f ) = t 3 ) s u b r a m a n i a n 则提出了一个带阻尼因子的g a u s s - n e w t o n 法( 取臼( r ) = ，| f | ) ( 2 2 ) ，其迭 代格式为： x 删”：= x + a p ，p = ( a ( x ) + ( z ) ，) _ 1 1 咯( x ) ( 1 8 ) 大连理工大学博士学位论文 这里口 0 为步长，由非精确a r m i j o 搜索求得，a ( x ) = v g ( x ) 2 v g ( x ) ；五( x ) = g ( x ) ；1 1 表示适当维数的单位矩阵；g ( x ) = 剖g ( x ) 。f e n i s 和l u c i d i 在文献 5 2 中用非单调线 z 性搜索技术改进程序( 1 8 ) ，得到了好的数值结果。s u b r a m a u i a n 和北方交通大学的修 乃华老师合作证明了：在f ( x ) 连续可微时，算法( 1 8 ) 是整体收敛的；在某些合适的条 件下，其点列是局部超线性收敛的( 2 4 ) 。基于n c p 函数( 1 7 ) ，k a n z o w ( 2 5 ) 考虑下面2 胛阶光滑方程组： h ( x ，y ) = y f ( x ) ( x i ，y 1 ) ( x 。，y 。) = 0( 1 9 ) 他给出了j a c o b i a n 矩阵v h ( x ，y ) 在n c p ( f ) 的非解点处存在逆的几个充分条件。显然 算法的整体收敛性与水平集 ( x 。，y 。) = w ) 婀2 “il l h ( x , y ) 日( x 。，j ，。) 9 的有界性有密切联系。对此，文 2 5 也做了研究。t s e n g ( 2 6 ) 则把( 1 9 ) 变成方程 9 ( z ，y ) = ( ) ，一，( 工) ) 9 庐( x l ，y 1 ) 庐( x 。，y 。) = 0 p 0 进而研究1 1 日和i 旧，0 的增长行为。 这类方法具有一定的优越性，但也存在着缺点，即使一个线性互补问题，转化后的 方程往往是非线性的，且非线性程度较高，这就导致了理论与计算的复杂化。 ( 三) 求解互补问题的可微的无约束优化法。这种方法是把互补问题转化为一个与 之等价的可微无约束优化问题，然后用某种整体或n e w t o n 类型法求解。m a n g a s a r i a n 和 s o l o d o v 3 0 又先于他人，给出了一个可微的势函数 ( x ) = x 7 f ( 工) + 去( 一a v ( x ) + x ) + 卜删2 + i l ( c d c + f ( x ) ) + 一l i f ( z ) 0 2 ，口 0( 1 i 0 ) 这里川表示2 - 范数，称为隐l a g r a n g e 函数。同时，他们证明了势函数( 1 1 0 ) 的全 局最小解与n c p ( f ) 的解的等价性。文 3 1 研究了稳定点与n c p ( f ) 的n 2 _ n n 关系 证明了如果n c p ( f ) 的映射f 有一个正定的j a c o b i a n 矩阵，则势函数( 1 1 0 ) 的任何稳 7 墨= 重一堑兰一 定点都是n c p ( f ) 的解。文献 3 2 对文献 3 0 做了统一处理a 在文献 3 2 中，k a n z o w 提出了一类函数，这其中就包括势函数( 1 1 0 ) ，通过这类函数，将非线性互补问题转 化为一个无约束最优化问题，并且证明了对于正定互补问题而言，无约束目标函数的稳 定点和非线性互补问题的解是等价的。 基于f u k u s h i m a ( 3 3 ) 的结果，中国科学院的彭积明老师在文献 3 4 中给出了变分 不等式问题的的可微无约束优化再生。有趣的是，它恰是隐l a g r a n g e 函数在变分的推 广。自此以后的一段时间里，出现了构造n c p 函数热。关于这个方向的综述，可见 f u k u s h i m a 的文献 3 5 。 另外，我们还对非线性规划中的梯度投影算法作了探讨，这种方法由于其固有的优 点，也吸引了不少学者对它的深入的研究，对于它的内容，作者在此不再赘述，可参阅 文献 5 5 - 6 0 ，在本文中，我们主要是集中于对这种方法的步长选取的探讨上。 1 3 本文的主要工作 本文主要是对l - 2 中提出的一些研究内容作了探讨，取得了几个结果，现具体分 析如下。本文的第二章到第六章，分别讨论了通过广义d 一间隙函数求解变分不等式问 题，求解互补问题的g a u s s - n c w t o n 方法，求解互补问题的种混合方法，以及非线性 规划中的梯度投算方法。 第二章研究了通过广义d 一间隙函数求解变分不等式问题的一种混合n e w t o n 型方法 的收敛性和误差界估计。我们知道，在求解变分不等式问题的基于最优化的方法中，通 过广义d 一间隙函数，可以将变分不等式问题转化为一个无约束极小化问题。最近，p e n g 和f u k u s h i m a 提出了一种混合牛顿类型的方法来极小化一个带有特殊距离的广义d 一间 隙函数，在本章中，我们将这种方法推广到用来极小化带有广义距离的广义d 一间隙函 数g 。口。这种函数是由y a m a s h i t a ，t a j i 和f u k u s h i m a 等人在文献 5 1 中提出来的，它是 p e n g 和f u k u s h i m a 研究的广义d 一间隙函数的一种推广。我们证明了算法的一个更强的 收敛结果。在合适的条件下，证明了算法的局部二次收敛和全局二次收敛。更进一步， 当广义d 一间隙函数g 。中的参数取值于某一区间时，我们证明了对于强单调变分不等 式而言，g 。具有有界的水平集，同时，给出了算法的一个误差界估计，它部分回答了 y a m a s h i t a 等人在文献 5 1 中所提出的问题。 第三章对求解互补问题的光滑方程法中的阻尼g a u s s n e w t o n 方法作了研究，这种 方法是由s u b r a r n a m i a n 提出的。我们主要是对阻尼g a u s s n e w t o n 方法的全局收敛性作 了探讨。分别在较弱的条件下和一个新的步长规则下，获得了一个更强的全局收敛性结 果，该结果是s u b r a m a n i a n 在文献 2 2 中相应结果的一个推广。 第四章对求解互补问题的可微的无约束优化方法作了研究。在文献 3 2 中，k a n z o w 将非线性互补问题转化为一个无约束最优化问题，我们对此无约束最优化问题提出了一 查垄堡王查堂竖圭堂篁丝皇 种混合方法，证明了该算法的全局收敛性。 第五章研究了在一个新步长规则下的梯度投影算法。众所周知，梯度投影方法是求 解约束最优化问题的一种最简单的方法。我们在此对该算法的步长规则作了初步探讨， 在步长的选取时采用了种新的策略，讨论了在该步长规则下，梯度投影算法的收敛性， 进一步给出了目标函数是凸函数和拟凸函数时的更强的收敛性质。 第一章绪论 参考文献 【1 g i a n n e s s i ，f ，t h e o r e m so ft h ea l t e r n a t i v e ，q u a d r a t i v ep r o g r a m s ，a n dc o m p l e m e n t a r yp r o b l e m s ，i n ： c o r l e ，r w ，g i a n n e s s i ，f ，l i o n s ，j l ，e d s ，v a r i a t i o n a li n e q u a l i t ya n dc o m p l e m e n t a r i t yp r o b l e m s ， j o h nw i l e ya n ds o n s ，n e wy o r l1 9 8 0 ，1 5 1 - 1 8 6 2 】h a r k e r , p t ，a n dp a n g ，j s ，f i n i t e d i m e n s i o n a lv a r i a t i o n a li n e q u a l i t ya n dn o n l i n e a rc o m p l e m e n t a r i t y p r o b l e m s ：as u r r e yo f t h e o r y , a l g o r i t h ma n da p p l i c a t i o n s ，m a t h p r o g r a m m i n g ，1 9 9 0 ，4 8 ( 2 ) ：l6 3 - 2 2 0 3 张石生，变分不等式和相补问题理论及应用，上海科技文献出版社，上海，1 9 9 1 【4 】h a r t m a n ，p ，a n ds t a m p a c c h i a , g ，o ns o m en o n l i n e a re l l i p t i ed i f f e r e n t t i a lf u n c t i o n s ，a c t a m a t h ，19 9 6 ， 1 1 5 ：15 3 一1 8 8 【5 1m a n c i n o ，0 ，a n ds t a m p a c c h i a ，g ，c o n v e xp r o g r a m m i n ga n dv a r i a t i o n a li n e q u a l i t i e s ，l o p t i t h ，a p p l ， 1 9 7 2 ，9 ：3 - 2 3 ， 6 】s t a m p a c c h i ag ，v a r i a t i o n a li n e q u a l i t i e s ，i nt h e o r y a n d a p p l i c a t i o n s o fm o n o t o n e o p e r a t o r s p r o c e e d i n g so ft h en a t oa d v a n c e ds t u d yi n s t i t u t e ，v e n i c e ，i t a l y ( e d i z i o n io d e r i s i ，g u b b i o ，i t a l y ， 1 9 6 8 ) ，1 0 2 1 9 2 7 】c h e n ，b a n dh a r k e r , p t ，ac o n t i n u a t i o nm e t h o df o rm o n o t o n ev a r i a t i o n a l i n e q u a l i t i e s m a t h p r o g r a m m i n g ，1 9 9 5 ，6 9 ( 2 ) ：2 3 7 2 5 3 8 】k a n z o w , c ，a n dj i a n g ，h ，ac o n t i n u a t i o nm e t h o df o rs t r o n g l ym o n o t o n ev a r i a t i o n a l i n e q u a l i t i e s m a t h p r o g r a m m i n g ，1 9 9 8 ，8 1 ：1 0 3 - 1 2 6 9 】简金宝。单调变分不等式的可行与非可行点组合的连读算法。运筹学学报，1 9 9 7 ，( 1 ) ：7 6 8 5 1 0 s u n ，d ，f u k u s h i m a ，m ，q i ，l ，ac o m p u t a b l eg e n e r a l i z e dh e s s i a no fd g a pf u n c t i o na n dn e w t o n t y