（基础数学专业论文）求解非线性规划问题的光滑牛顿法及minimax问题的sqpfilter算法.pdf

福建师范大学硕士学位论文 a b s t r a c t i nt h i st h e s i s ，w ed i s c u s ss m o o t h i n gn e w t o nm e t h o df o rn o n l i n e a rp r o g r a m m i n g p r o b l e ma n ds q p f i l t e rm e t h o df o rc o n s t r a i n e dm i n m a xp r o b l e m i nc h a p t e r1 ，an e ws m o o t h i n gn e w t o nm e t h o di sp r o p o s e df o rs o l v i n ge q u a l i t ya n d i n e q u a l i t y c o n s t r a i n e dn o n l i n e a rp r o g r a m m i n g p r o b l e m t h i s m e t h o di sb a s e do n s m o o t h i n gm i n f u n c t i o n ，b yk k to p t i m a l i t yc o n d i t i o n s ，o r i g i n a lc o n s t r a i n e do p t i m i z a t i o n p r o b l e mi sc o n v e r t e di n t ot h es o l u t i o no fe q u i v a l e n ts m o o t h i n ge q u a t i o ns e t a n d ，t h e p r o p o s e da l g o r i t h mi sp r o v e dt ob ew e l l d e f i n e da n dc o n v e r g e n tg l o b a l l yu n d e rw e a k e r c o n d i t i o n s n u m e r i c a le x p e r i m e n t ss h o wt h em e t h o di se f f e c t i v e s q pm e t h o di sam o s te f f e c t i v ew a yt os o l v ec o n s t r a i n e dn o n l i n e a rp r o g r a m m i n g p r o b l e m ，b u ti t i sd i f f i c u l tt oe l e c t i n gt h ep e n a l t yf a c t o r , f i l t e rs k i l lc a l la v o i di t s o ，i n c h a p t e r2 ，as q p f i l t e rm e t h o di sp r o p o s e df o rs o l v i n ge q u a l i t ya n di n e q u a l i t yc o n s t r a i n e d m i n i m a xp r o b l e m e a c ht i m eb ys o l v i n gt h es e c o n ds u b - p r o g r a m m i n gt og e tt h es e a r c h d i r e c t i o n ，a n da l o n gt h ed i r e c t i o nf o rl i n es e a r c h t h i sm e t h o da v o i d st h ed i f f i c u l tp r o b l e m o fs e l e c t i n gt h ep e n a l t yf a c t o r , a n do v e r c o m e sm a r a t o se f f e c t ss u c c e s s f u l l y i t sg l o b a la n d s u p e r - l i n e a rc o n v e r g e n c ea r eo b t a i n e du n d e rs o m es u i t a b l ec o n d i t i o n s l a s t ，w em a k eac o n c l u s i o no ft h ew o r k i nt h i ss e c t i o n ，w es i m p l yi n t r o d u c er e s e a r c h p r o g r e s sa n da c h i e v e m e n to ft h es u b j e c t ，a n dp o i n to u tt h ep r o b l e mn e e dt ob es o l v e d k e y w o r d s ：n o n l i n e a rp r o g r a m m i n gp r o b l e m ；m i n f u n c t i o n ；m i n i m a xp r o b l e m ； s q p - f i l t e rm e t h o d ；g l o b a l c o n v e r g e n c e ；s u p e r l i n e a rc o n v e r g e n c er a t e ，n u m e r i c a l e x p e r i m e n t s n 。p 福建师范大学硕士学位论文 中文文摘 非线性规划问题是计算数学与运筹学一门重要交叉研究领域，军事、工程、经济、 管理、科研等诸多方面最优化问题的求解，大都可以转化为求解非线性规划问题因此 研究该问题具有十分重要的现实意义本文主要探讨非线性规划问题的数值算法文章 的结构安排如下： 绪论概括了国内外关于非线性规划问题的提出背景以及研究现状和成果，指出这些 问题有着广泛的实际应用和重要的理论意义之后我们简要论述了本文的主要内容和安 排 第一章，我们构造了求解非线性规划问题的光滑牛顿法 引言介绍说明了求解非线性规划问题重要现实意义，并简要说明本章的内容安排 第二节预备知识，我们给出非线性约束优化问题( n l p ) ： m i n i o ) x e r 4 豇黔) o ( 1 ) i 0 ) 一0 其中，：f r ，石- “，j r 2 ，) 7e r “二次连续可微然后构造其拉格朗日乘子函数： l ：= 工( a ，工) ti ( x ) + 7 g ( 工) + a 7 日( 石) ， 给出k k t 条件：v ，( 石，万，习- 0 ；o ( x - ) s 0 ，万2 0 ，p t g ( x - - ) 一o ；日0 ) = o 然后我们利用n c p 函 数的性质，构造了一个光滑化的m i n 函数( ，口，6 ) = 口+ 6 一石一6 ) 2 + 4 t 2 ，证明了若 a p ( 叻i l l p ( t ，a ，力= h 0 ) 垂l v ，l = o f 妒( ，一g t ( x ) ，p - ) 1 所得到的解就是( 1 ) 的最优解( 其中m 。- m 。( ，工) 1 妒( f ，一g ：( z ) ，p ：i ) 我们又证 【妒( f ，一g l ：( 工) ，_ ) j 明了如果g 0 ) 、日 ) 行满秩，p ( w ) 是非奇异的第三节，提出了一个求解非线性约束优 化问题的一步光滑牛顿法，由于每次迭代只需要求一个线性方程组 尸( 矿) + p ( ) 矿一见面，和执行一次不精确a r m i j o 线搜索，所以称之为一步牛顿法之 后我们证明了如果函数厂o ) 二次连续可微，g 0 ) ，h ( x ) 连续可微且其j a c o b i a n 阵是 l i p s c h i t z 连续的，g g ) 、o ) 行满秩，那么算法是适定的第四节我们在非线性约束 优化问题( 1 ) 的解集是非空有界的条件下，分析了该算法的全局收敛性最后一节做 了几个数值实验，表明这一算法是有效的 1 l i p 福建师范大学硕七学位论文 第二章，我们给出约束m i n i m a x 问题的s q p f il t e r 算法引言说明了m i n i m a x 问 题是最优化理论中常见的一种类型，它有着广泛的应用并简要说明了s q p 及“f i l t e r ” 技术的发展，及本文的思路第二节预备知识，我们考虑如下的m i n i m a x 优化问题： m i n m a x 五 ) f g j 0 ) s o ， ( 1 ) s l 1 0 ) 一0 ， 其中五o ) 、g ，o ) 、氏g ) ：r 4 一r 都是二次连续可微n 元实函数，i 一卜，p ，j ；，t n ， z = 1 , - - , q 将其转化为： f 五o ) 弘i e i , ( 2 ) s t g j o ) 0 ，- 厂， i o ) - 0 ，i e l ， 类似第一章我们得到( 2 ) 的k k t 条件，同时给出一些基本概念、定义第二节我们 给出该问题的s q p f i l t e r 算法第三节，我们在某些假设前提之下证明了算法的全局收 敛性第四节，在适当的条件下，我们证明了算法的超线形收敛性 最后一章，对本文的工作进行总结，简要介绍本文研究的进展和成果，指出尚待解 决的问题 p q 福建师范大学硕十学位论文 r所有实数的群体 r 。所有实r l 维列向量的群体 r所有非负实数的群体 记号与约定 r + 所有正实数的群体 z +所有正整数的群体 矩阵4 的转置 j r单位矩阵 ( 口，卢)向量( 口7 ，7 ) r 1 日i 欧式范数 s t “满足于，“s u b j e c tt o 的缩写 d i a g a ，i e n ) 对角线为q ，口：，口。的n 阶对角矩阵 f o )函数f ：r 。一彤在觑e r ”的j a c o b i a n 矩阵 v f ( x ) f 0 ) 的梯度，或者记为g ( x ) tv f ( x ) v 2 f ( x )f g ) 的h e s s a n 梯度，或者记为日 ) tv 2 f o ) b 0 ，g ) 以x 为中心，为半径的领域 口= o ) 对任意的口，r + ，当芦- o ，詈一致有界 口= 。够) 对任意的口，卢足+ ，当卢_ o 詈趋于o v 福建师范大学硕上学位论文 中文摘要 a b s t r a c t 中文文摘 目录 绪论 目录 l i i i 第一章求解非线性规划问题的光滑牛顿法 1 1 引言 1 2 预备知识 1 3 算法的构造 1 4 算法的收敛性分析一一一一9 1 5 数值实验 第二章约束m i n i m a x 问题的s q p f i l t e r 算法 2 1 引言 2 2 预备知识 2 3 算法的构造 2 4 算法的收敛性分析 第三章总结与展望 参考文献 福建师范大学学位论文使用授权声明 个人简历 致谢 l 4 4 4 5 6 4 5 8 9 o t 玉 玉 l l 2 2 2 2 3 福建师范大学硕十学位论文 近几年探究s q p 方法，并将之与其他技巧结合的文献愈来愈丰富如文献降l 提出一类 积极集s q p 滤子方法，其特点在于对约束的求解更有效，而且降低子问题不相容的可能 性文献1 6 1 提出信赖域s q p 滤子方法，而文献在此基础上加入一种新的方法，即若完 全牛顿步不被滤子接受，就对它进行一个二阶校正( s o c ) 来使得它容易被接受这种算 法可以避免m a r a t o s 效应，从而使算法达到局部超线性收敛但s q p 方法也有局限性， 文献1 6 2 】提出了求解非线性最优化问题的序列线性方程组算法线性方程组求解理论相对 二次规划来说较完善，它可有效地利用系数矩阵的稀疏性、对称性较快地求解一个线性 方程组问题，而且所需的存储量、精确度、稳定性较好，该文献对国内外学者在q p f r e e 和序列线性方程组算法研究领域的一些成果进行总结，介绍了几个具有代表性的算法， 提出几个值得进一步研究的课题 ( 三) 本文主要工作及内容安排 非线性规划问题是诸多领域的热门课题研究这些问题的求解方法不但在理论上具 有重要价值，而且有广泛的应用前景本文的内容安排如下： 第一章，给出了求解等式和不等式约束非线性规划问题的种新的光滑牛顿法这种 方法是基于光滑化m i n 函数，通过k k t 条件，将原约束优化问题转化为等价的光滑方程 组来求解，该方法只需要求一个线性方程组和执行一次不精确a r m i j o 线搜索，同时在 较弱的条件下我们还给出该算法全局收敛性的证明 第二章，探讨了等式与不等式约束的m i n i m a x 问题的s q p f i l t e r 算法该算法每步 通过求解两个二次子规划来得到搜索方向，并沿该方向做线搜索，因此避免了较难的罚 因子的选取，同时克服了m a r a t o s 效应，在一定的假设下，我们证明了算法的全局收敛 性和超线性收敛性 第三章，对本文的工作进行总结，并对今后的工作做了展望 2 绪 论 绪论 ( 一) 研究背景与意义 现实生活中，常常遇到如何设计或求解最优化问题例如，如何将有限的资源在 不同的部门分配，使得方案达到最佳，即获得最好的经济效益；农作物生产安排时，如 何布局才会使农田发挥地区优势，稳定高产；军事作战时，怎样确定作战方案，才能以 最小的代价夺取最大的胜利；工程设计中，如何选择参数才能使方案既满足各项要求， 又使成本最低 两次世界大战，尤其是二战中提出了许多军事最优化问题这些问题及解决方法是 很有特点的：数据是现实实践的来源，解决问题是多学科的，处理问题的方法基本渗透 着物理和数学的思想二战后最优化的应用开始由军事领域转入民用方面，特别是近3 0 年，由于科技进步，尤其是计算机和计算技术的快速发展，为解决各种复杂的最优化问 题提供了强有力的保障和手段因此最优化的应用范围越来越广，它涉及操作、设计、 工业过程，生产装置的分析以及生产计划的制定，经济运作的决策等问题由于最优化 方法是寻找最好效果的条件之方法，可以预见，最优化方法和技术将在2 l 世纪这个信 息时代发挥出巨大的作用，因此研究该问题具有十分重要的现实意义 ( 二) 研究现状 非线性规划问题( n l p ) 是计算数学与运筹学- f l 重要交叉研究领域，军事、工程、 经济、管理、科研、等诸多方面最优化问题的求解，大都可以抽象为求解非线性规划问 题非线性规划( 约束与无约束) 问题内容十分丰富，求解非线性规划问题的优化方法 更加繁多包括无约束优化问题的线搜索方法、共轭梯度法、拟牛顿法；约束优化问题 的可行方向法、有效集方法、罚函数法、乘子法、序列二次规划方法( s q p 方法) 等 非线性规划问题的基本形式是： m i n f o ) 工r “， f a ( x ) 墨o 其中，：尺“一r ，x = ( 而，x 2 ，) 1 尺“ j j l h ( x ) 一0 ， 该问题首先由h w 库恩和a w 塔克提出的，其1 9 5 1 年发表的关于最优性条件( 后 来称为库恩一塔克条件) 的论文是非线性规划正式诞生的一个重要标志在5 0 年代还得 出了可分离规划和二次规划的n 种解法，它们大都是以g b 丹齐克提出的解线性规划的 单纯形法为基础5 0 年代末到6 0 年代末出现了许多解非线性规划问题的有效算法，7 0 年 代又得到进一步的发展，为最优设计提供了有力的工具非线性规划问题的出现引起了 人们浓厚兴趣，目前许多人对该问题的求解方法纷纷进行探讨研究而经验表明s q p 方 法是求解非线性约束优化问题的一类最有效的算法s q p 方法的基本思想是：在每一迭代 点，构造一个二次规划子问题，以这个子问题的解，作为迭代的搜索方向d ，并且沿 该方向作一维搜索，即 x “- j + a k d ， 得到，“，重复上述迭代过程，直到点列p ”，k 。o 1 ，夸1 最终逼近原问题的近似约束最优 点x 第一章求解非线性规划问题的光滑牛顿法 第一章求解非线性规划问题的光滑牛顿法 1 1 引言 现实生活中，常常遇到如何设计或求解最优化问题例如，如何将有限的资源在不 同的部门分配，使得方案达到最佳，即获得最好的经济效益；农作物生产安排时，如何 布局才会使农田发挥地区优势，稳定高产；军事作战时，怎样确定作战方案，才能以最 小的代价夺取最大的胜利；工程设计中，如何选择参数才能使方案既满足各项要就，又 使成本最低 非线性规划问题是最优化理论与方法的基本问题，因此如何研究和求解该问题具有 十分重要的现实意义 本文提出了求解等式和不等式约束非线性规划问题的一种新的光滑牛顿法这种方 法是基于光滑化m i n 函数，通过k k t 条件，将原约束优化问题转化为等价的光滑方程组 来求解本文第二节介绍了一些基本概念和引理：第三节介绍了一种新的光滑牛顿法； 第四节分析了该算法的全局收敛性最后一节做了几个数值实验，表明这一算法是有效 的 1 2 预备知识 我们考虑求解下列的非线性约束优化问题( n l p ) ： m i n ，o ) 工彤， 珐g o ) s o ( 1 2 1 ) l h o ) 一0 ， 其中 厂：彤一r ，石i l l 瓴，屯，) ，e r 。， 二次连续可微，g o ) 一k ) ，g ：o ) ，靠o ) r ，日o ) - ) ，o ) ，鸣) r ，且g o ) ，日o ) 连续可微且其j a c o b i a n 阵是l i p s c h it z 连续的 我们定义非线性约束优化问题( 1 2 1 ) 的可行域为： q 一 工科i g o ) s 0 ，胃o ) - 0 ) 一 非线性约束优化问题( 1 2 1 ) 的拉格朗日乘子函数为： l ：- l ( a ，工) 。，0 0 + r g ( 砂+ a 7 h ( z ) ， ( 1 2 2 ) 其中一( 一：，p ) re r ”，a 一( a ，如， ) 7 硝，均为乘子向量为了记号方便，我们用 ( a ，肛，工) 7 表示( a tl z r , x r ) 7 设问题( 1 2 1 ) 的k k t 点为( 石，万，习，则它应该满足的一阶最优必要条件的为： 3 ? 、 第一章求解非线性规划问题的光滑牛顿法 的性质容易得到： 一g f o ) 乏o ，以z 0 ；舶g f g ) 。o ；1 s i s m 所以 g ( x ) 墨0 ，肛2 0 ；弘g ( x ) = 0 由以上推导可得：k k t 最优条件( 1 2 3 ) 等价于方程组( 1 2 6 ) 证毕# 引理1 2 3 设p ：足x r 。r “x r 4 一尺( 1 山) ，则有 ( i ) 由( 1 2 5 ) 式可知p 在rx r 7x r “x r “上连续可微的，并且其j a c o b i 矩阵为： p ( w ) = 其中l ；1 + 1 + 朋+ ，1 10oo 000v h t t ，0 v 。哦v ，电 0 v ， lv 。工v 。l r 。i，( 1 2 7 ) ( i i ) 如果g o ) 、日 ) 行满秩，可以得到尸( w ) 在r + x r 7x r “x r “上是非奇异的 证明：先看( i ) ：实际上，矩阵( 1 2 7 ) 的第一、第二行容易得到，接下来观 察第三行，因为庐( ，一，一g ；o ) ) 在( 占，卢，工) r 1 + 肿”是连续可微的( 1 f f i is 坍) ，所以有： q ”飓，。o ) ) _ 一了i i 赢，v ，_ r 5 j 4 ，- r o 因此： 其中 西lq ，石，) - 纯p ，朋，一 ) ，。岛一了盂乎恭 、f 产r 5 l ，t o 卟意赫t 心- 、，i ，r 5 ，t - r ( f ，_ 晶似“) 彩( f ，似鸬) 群( f ，_ g m 似心) 0 尤 ，- g l ( 矽，一) 0 无p ，- g ：似鸬) ； 0 尤( 占，- 似心) 碰( 岛- 9 1 似一) p ，似鲍) ( 易嚅0 ) ，心) ：- ( 抄0 已也v 3 , 1 ) 一卜。一揣帅+ 器刚) ， 5 、 福建师范大学硕- i ：学位论文 v ，l ( x - ，万，x - - ) ；o ；g ( 习so ，万o ，万r g ( x - 0 f f i 0 ；m x ) - o ( 1 2 3 ) 。定义1 2 1 称( 口，b ) e r 2 为n c p 对，如果满足口z 0 ，b z 0 ，a b = o 定义1 2 2 函数妒：尺2 一r 称为n c p 函数，如果妒( 口，b ) 一0 当且仅当( 口，6 ) 为n c p 对 引入m i n 函数 驴( 口，6 ) - m i n ( a ，6 ) = 三【口+ 6 一f 而】 显然它在r ： ( c ，c ) ) 上是连续可微的，其中c r 为了研究方便，本文提出m i n 函数的 光滑化形式【1 1 类似的光滑函数： 妒( 占，口，6 ) 。口+ 6 一t ：j 丽， ( 1 2 4 ) 其中 0 为光滑参数 引理1 2 1 2 1 设函数驴：一只，显然有如下的性质：妒( o ，a ，6 ) = o 尊口z 0 ，b 2 0 ，a b o 为求解问题( 1 2 3 ) 我们令：w 罨( ，a ，x ) r r r “x r “， 其中 p ( w ) 一p ，a ，t ，工) = 日o ) m l v ，l m l ：一m l ( e ，i l ，x ) = 驴( ，- g 。( 工) ，) ( f ，- 9 2 0 ) ，：) 妒( ，- g 。( 工) ，。) 北以，一g j o ) ) ；一g f g ) + 以一厄忑而而7 ( 1 s is m ) ( 1 2 5 ) 矿t 饼，霉，) 7 ，- ( 露，成，戚厂 a = ( 对，笱，对) r ，p = p ( ) = p ( e k , 九, k , 工) 引理1 2 2 方程组 p ( 们。0 ， ( 1 2 6 ) 等价于 v , l ( 2 - ，万，习一0 ；g ( 习o ，万0 ，万7 g ( d = i f , h ( x ) - 0 证明：由( 1 2 6 ) 可知耻何，面，x - - ) = o ，t t ( x ) t 0 ，并且有a o ，电= o ，再由n c p 函数 4 0 、 福建师范大学硕l - 学位论文 2 c 一了蠢亍杀，一了露i 希，一了露：拓) r r 。 v g ( x ) 7 。( v g i tw ：r ，v g 。7 ) 7e r ：，是历m 单位矩阵；阳7a ( v 【l i r , v h ：7 ，v 岛7y “ 接着看矩阵( 1 - 2 7 ) 的第四行，因为 - l ( a 舶x ) l ，o ) + 酗o h + 善吃o ) 所以 v ，= v f + v g , 吩+ z ；v 厂o ) + v g ( x ) 比+ g ) a 则 v ， l 一( ，v h , ) = 阳，v ，lt ( v g 。，v 9 2 ，v g 沪w ， v 。工一v 2 ，+ v 2 g + v 2 日a 至此我们完成对矩阵( i ) 的证明 ( i i ) 令 p ( w ) 一 10 00 抄0 0v h 0 o d i a g 仇) ， v g 其中讲唱c 仇，为对角元素，是仇41 一了荔兰特的对角阵， m 为l 的h e s s e 阵，d i a g ( g ；) 表示对角矩阵，它的对角线上的每一个元素 白。一( 1 + f ：丝兰兰鞫，( i ；1 ，m ) ( 雎+ g i o ) ) 2 + 4 e 2 先对某个 ，声) 尺”。，有 先证舭= ( 之m 户奇撇首 彳一。 其中口。( 口l ，口2 ，a 。) r ，卢一h i ，6 2 ，以) r ，贝u 有 ，口+ d i a g ( 身) v g 7 卢= 0 飞g a m 4 0 所以由( 1 2 9 ) 得： 口；一d i a g ( 岛) v g 7 夕，再将代入( 1 2 1 0 ) 左乘r 有： 芦7 ( v g a + m 罗) 一一卢7 - v g d i a g ( ；t ) v g 7 声+ 芦m 芦7 = 0 6 ( 1 2 8 ) ( 1 2 9 ) ( 1 2 1 0 ) g r o删蚴m 第一章求解非线性规划问题的光滑牛顿法 因为v g d i a g ( 善。) v g 7 是半负定的，所以卢= 0 ，代入( 1 2 8 ) 得到口一0 ；因此 a 。f ， d a g ( 岛) v g 71 是非奇异的，再结合日o ) 为行满秩的条件，可得到矩阵p ，( w ) 为 lv gmj 、7 。 非奇异的p j 证毕# 1 3 算法 首先令，7 0 5 ，1 1 6 ( o ，1 ) ，定义函数：p ：r + r “r 。一足如下： p ( w ) ：= 61 l p ( w ) rm i n1 ，i i p ( w ) l r 基于m i n 函数( 1 2 4 ) ，下面给出一个求解非线性约束优化问题( 1 2 1 ) 的一步光滑牛 顿法： 步骤i 选取参数r ( 0 ，1 ) ，仃( 0 ，1 ) ，o 0 令工oe r “， 形i ( e o , o ，0 ，0 ) e r + x r x r ”x r “ 且矿：i ( 气，九，以，) ，选取6 ( 0 山使得& o 1 令七_ 0 步骤2 若0 p ( 矿) 1 1 ；0 ，则算法终止；否则，令n p ( ) 步骤3 解方程组： 以矿) + p ( 矿) 矿= 反面， 可以得到：- ( & ，咄，a p k ，甜) 步骤4 设 为使下式成立的最小非负整数， i i p ( + p ) 忙1 一o r ( 1 一如。弦 】| f p ( ) | f ( 1 3 1 ) ( 1 3 2 ) 并令嚷一f 步骤5 令矿+ 1 一矿+ 幺矿，七：i 七+ 1 ，转步1 算法的每次迭代只需要求一个线性方程组和执行一次不精确a r m i j o 线搜索，所以 称之为一步牛顿法令 q 。= wt ( f ，a ，肛，工) r + + 科x 肜r 。：2p ( w ) 占。) ( 1 3 3 ) 定理1 3 1 如果函数f ( x ) 二次连续可微，g o ) ，h ( x ) 连续可微且其j a c o b i a n 阵是 l i p s c h i t z 连续的，g o ) 、h 0 ) 行满秩，那么算法是适定的 7 福建师范大学硕士学位论文 证明： 事实上由引理1 2 3 的( i i ) 可知，p ( w ) 在尺+ + x r r ”xr 。上是非奇异的， 即为可逆矩阵，( p ( w ) ) 一1 存在，故方程组( 1 3 i ) 的解存在并且是唯一，接下来证明算 法的适定性任意给定正整数k 0 ，对于口( o 朋，定义： ，( 口) = p ( 矿+ 口彬) 一p ( 矿) 一a p ( ) ，i ， ( 1 3 4 ) 那么由( 1 3 1 ) 式可得到p ( ) 彬= 一p ( ) + 风诫代入( 1 4 ) 后整理则有： 以矿+ a a w ) = ( 1 一口) h ) + a p i 万+ r ( a ) 又由p ( ) 得定义可知： 当| i p ( 矿) 忙1 时，有： 若8 p ( 矿) 0 1 时，则有： p ( ) ；6 l l p ( 矿) 1 1 2 4s 60 p ( 矿) | i ， p ( ) 一6 | | p ( 矿) 卜6 1 1 p ( w k ) 1 1 ( 1 3 5 ) ( 1 3 6 ) ( 1 3 7 ) 结合( 1 3 5 ) 、( 1 3 6 ) 、( 1 3 7 ) ，利用范数三角不等式即司得到： p ( ，+ 口) l i s 1 - 口( 1 - 6 e o ) 】l l p ( ) f f + i i ，( 计 ( 1 3 8 ) 下面我们要估计l i r 0 即可下 面使用归纳法加以证明 因为算法规定初值f 。 0 ，现在假设对于某个k 0 ，有。d 0 ，接着证气 o 成 立由( 1 3 1 ) p ( 矿) + p ( 矿) - n 面展开整理得到： 所以对任意的口( 0 朋，有 一l - 一气1 + 见一l f o ， 吼一气i + a a e t l 一( 1 - a ) e t l + 口“一l o 0 ， ( 1 3 9 ) 所以由归纳法原理可知，对于任意的七0 ，均有。 0 ，这样我就完成了对p 在处 8 第一章求解非线性规划问题的光滑牛顿法 是连续可微的证明再由( 1 3 4 ) 的定义可得到忆口) | l 叠口( 口) ，所以由( 1 3 8 ) 可知：存 在一个万( 0 朋，使得对任意的口( 0 ，刎有： 成立证毕# 1 4 算法的收敛性 0 p ( + 4 ) 忙【1 一盯( 1 6 ) 口 l i p ( ) i | 下面我们要验证算法的全局收敛性，为此我们做如下假设： al ：非线性约束优化问题( 1 2 1 ) 的解集是非空有界的 引理1 4 1 设厂o ) 二次连续可微，且g o ) ，h ( x ) 连续可微且其j a c o b i a n 阵是l i p s c h i t z 连续的，并且 w i ) 为算法1 所产生的迭代序列则： ( i ) 对任意的k 0 ，都有t 0 ； ( i i ) 对任意的七苫0 ，都有q 。； ( i i i ) 叠。 是一个单调下降的序列 证明：( i ) 根据前面的定理1 3 1 立即可以得到( i ) 的结论 ( i i ) 下面也使用归纳法来证明，根据初始点的选择标准，容易得到w o q 。先 假设对于某个七 0 ，有矿一q 。，即占“之p o 接下来证明q 。，也就是要证 t 苫p i 占o 由( 1 3 1 0 ) 式和上面的假设，立即可以得到： 气一以气= ( 1 一幺1 ) “一l + 吃一l 以一l 气一以2 ( 反1 一p , ) e o ( 1 4 1 ) 根据算法所定义的p ( ) ：若l l p ( ) i l 0 ， 所以一以卢。2o ，即占t p t a o ，得到q 。证毕# ( i i i ) 对于任意的七0 ，由( 1 3 1 0 ) 得： 占i 一( 1 一日i ，1 ) i 1 + p t l p i l o 由匕面( i i ) 的证明过程可得： 9 福建师范大学硕上学位论文 七s ( 1 一口七一1 ) 量1 + o k - 1 七1 _ f 鼍一i 所以扛。 是一个单调下降的序列证毕# 接下来我们要证明算法的全局收敛性 定理1 4 2 设f ( x ) 二次连续可微，g 0 ) ，h ( x ) 连续可微且其j a c o b i a n 阵是l i p s c h i t z 连 续的，并且b 为算法所产生的迭代序列如果彳1 成立，那么： ( i ) | i p ( 矿) l i ) 是一个单调下降的序列且收敛到0 ； ( i i ) 密i m 。气一0 ，且序列 ) 有界； ( i i i ) 迭代序列 ) 的每一个聚点都是非线性约束优化问题( 1 2 1 ) 的一个解 证明： 假设w = ( ，z ) ，是序列 矿= ( 气，) ，k e z + ) 的一个聚点不失一般性，现在假设 w k 呻旷 ( i ) 算法已经给出了序列 j i p ( ) i i ) 是单调下降的，对于任意的七20 ，有j j p ( ) | j 苫0 因此存在两个非负数p 和p 使得 叻l i p ( ) i | - p 。和 鳃p ( ) 一p 由p 的连续性得到 l p ( w ) i | 一p p ( w + ) = p 若p 一o ，那么l j p + ) l | 0 ，所以( i ) 成立。 现在我们假设p 0 ，那么依据算法中p ( w ) 的定义得np 0 ，由引理1 4 i 可知： 对于任意的kzo ，有f 。乏p k 。，又因为矗。 是- - + - g 降序列，进一步可得到 暑。l 芑p ( w ) o ，( ! 觋e t2 。) 再由算法可以得到： l | p ( + p 1 ) 8 1 一a 0 一& 。弦4 】l | p ( 矿) 0 ， 整理得： 坦兰竺g a 。- i 牡则 一仃( 1 一酬p ( ) l | ( 1 4 2 ) 由( 1 3 2 ) 式可得! 受吼，o 即当七呻时，p 1 o ；对( 2 2 ) 两边同时取极限 得： p ( w ) 7 p ( w ) a w 盯( 加。一1 ) 0 p ( w ) 8 2 ( 1 4 3 ) 另外我们对( 1 3 1 ) 两边同时求极限得到： 1 0 第一章求解非线性规划问题的光滑牛顿法 p ( w ) + p 【w ) a w = p ( w 。) w ， 所以有 尸( w ) 矿一- p ( 旷) + p ( w ) 面， 将之代入( 1 4 3 ) 式左边便有： e ( w ) 7 p ( w 。) a w - 一e ( w + ) 7 p ( w ) + p ( w 炉( w ) 7 面 而当0 p ( ) 8 1 时，p k = 6 忙( 岷) l | 2 叩同时注意到，7 【o 5 ，1 】因此： e ( w ) 7 p ( w ) w + 墨一慨w ) 8 2 + 晚i i p ( w 臂”s ( c s e 。一1 ) 愀) 8 2 ； 若当p ( ) 忙1 时，有n = 刚p ( ) n 所以也有： e ( w ) 7 p ( w ) ws i i p 0 不成立，所以p = 0 ( i i ) 由( i ) 的证明显然可以得到；i mg t = 0 ；再利用文【3 】定理3 2 ( i i ) 的证明可 得到序列 ) 有界 ( i i i ) 利用函数p ( w ) 的连续性和前两点证明可得到迭代序列 矿) 的每一个聚点都是非线 性约束优化问题( 1 2 1 ) 的一个解证毕# 1 5 数值实验 本节，我们给出两个数值试验例子，验证算法1 3 的有效性所有的程序都在 w i n d o w sx p 系统，c p u2 6 6 g h z ，7 0 4 m b 内存，m a t l a b7 环境下编写并运行的 例题1 ： r a i nf ( x ) 一o 气一1 ) 2 + 0 2 2 ) 2 黾+ 石2 2s o ， - - x 1s 0 ， - - x 2s 0 ， 一而+ 戈2 - 1 = 0 ， 最优解与最优值是： z = ( 0 5 , 1 5 ) r ，厂o 。) ；0 5 福建师范大学硕上学位论文 在试验中，算法1 3 的参数取为： 占o i io 0 5 ， z ；0 5 ，盯- - 0 2 ， 6 = o 0 1 表1 1 例题1 的数值试验结果 初始值迭代次数运行时间近似解残差 ( o ，o ) r 50 1 2 5 07 0 4 9 i d e 0 0 7 ( 0 5 , 1 5 ) f 7 7 1 1 8 e 0 0 7 ( 1 ，1 ) 丁 2 0 ( 0 5 ，1 5 ) r ( 1 0 0 ，l o o ) r 30 0 1 6 0 ( 0 5 ，1 5 ) r 7 4 8 7 6 e 0 1 0 6 1 1 4 9 e 0 0 7 ( 一1 0 0 , 1 0 0 ) r 4 0 0 1 5 0 ( 0 5 ，1 5 ) r 终止准则为：l i p ( w ) 忙1 0 。4 表1 2 例题1 的数值试验结果 初始值迭代次数运行时间近似解残差 ( o ，o ) r 60 1 1 0 0o ( 0 5 , 1 5 ) r ( 1 ，1 ) r 4 0 0 3 1 0 ( 0 5 ，1 5 ) r 0 ( 1 0 0 ，1 0 0 ) r 50 0 1 5 01 1 1 0 2 e - 0 1 6 ( 0 5 , 1 5 ) r ( 一1 0 0 ，1 0 0 ) r 50 0 3 1 0o ( 0 5 ，1 5 ) r 终止准则为：i i p ( w 堋s l o 例题2 ：考虑下面的约束规划问题： m i nf ( x ) io q 一2 ) 2 + ( j 吃一1 ) 2 s t j o 掰+ x ；1 s o ， l 葺一+ 1 ；0 该问题有精确解工i ( o 5 ( 歹一1 ) ，0 2 5 ( , 4 t f f + 1 ) ) ， ) 一9 2 8 7 5 t 7 在试验中，算法1 3 的参数取为： s o 一0 0 5 ， f1 0 5 ， 仃- , 0 2 ， 61 0 0 1 1 2 第一章求解非线性规划问题的光滑牛顿法 一 表1 3 例题2 的数值试验结果 初始值迭代次数运行时间近似解残差 ( o ，o ) 丁 5o8 2 2 3 2 e 0 1 0 ( o 8 2 2 9 ，0 9 11 4 ) t q 1 ) r 305 4 0 2 0 e 0 0 8 ( 0 8 2 2 9 ，0 9 11 4 ) t ( 1 0 0 ，1 0 0 ) r 1 002 5 7 8 7 e 0 0 7 ( 0 8 2 2 9 ，0 9 11 4 ) t ( 一1 0 0 ，1 0 0 ) r 1 20 0 1 5 01 4 6 9 0 e 0 1 0 ( o 8 2 2 9 ，0 9 11 4 ) t 终止准则为：肛( ) i a 1 0 4 表1 4 例题2 的数值试验结果 初始值迭代次数运行时间近似解残差 ( o ，o ) r 601 1 1 0 2 e 0 1 6 ( o 8 2 2 9 ，0 9 1 1 4 ) t ( 1 ，1 ) r 4o1 6 3 9 2 e 0 1 5 ( o 8 2 2 9 ，0 9 1 1 4 ) t ( 1 0 0 ，1 0 0 ) z 1 1 0 0 1 6 0 5 3 8 7 1 e 0 1 4 ( 0 8 2 2 9 ，0 9 114 ) t 1 60 0 1 6 02 4 8 2 5 e 0 1 6 ( 一1 0 0 0 ，1 0 0 0 ) 丁 ( o 8 2 2 9 ，0 9 11 4 ) t 终止准则为：l l p ( ) 1 1 1 0 。1 。 从以上两个例子的数值试验可以看出：初始值的选取并不对算法的收敛速度产生很 大的影响而且在精度要求较高的情况下，算法的迭代次数较少，所运行的时间几乎为 零，说明算法的收敛效果是很好的 1 3 福建师范大学硕上学位论文 第二章约束m i n i m a x 问题的s q p - f i l t e r 算法 2 1引言 m i n i m a x 问题即极大极小问题，是最优化理论中常见的一种类型，它在许多领域， 如电子线路规划、对策论、工程设计等都有着广泛的应用 序列二次规划算法，简称s q p 方法，该方法最早由w i l s o n ( 1 9 6 3 ) 提出，但是直到2 0 世纪7 0 年代中期才引起人们的重视并得到发展其中，h a n ( 韩世平) 和p o w e l l 的工作最 重要，所以s o p 方法有时候也被称为w i l s o n h a n p o w e l l 方法，它是求解非线性约束 优化问题的一类非常重要的方法 然而s q p 方法的局限性是原约束优化与子规划的相容性问题，所以一般引入势函数 来确定步长，h a n 建议使用厶精确罚函数作为势函数，但有时罚因子的选取很难，正是 这种情况下“f i l t e r 技术( 见文献 8 、 1 2 、 1 3 、 5 9 ) 产生了，它是2 0 0 2 年由 f