（应用数学专业论文）优化问题的几种算法.pdf

摘要 本文针对几种重要的优化模型，对近几年备受关注的几种新型优化算法( 如 极大熵函数法、同伦算法、填充函数法等) 作了比较深入的研究，在此基础上将 这些算法有机结合并作了进一步的改进、推广和应用，取得了比较满意的效果，、 详细内容如下： 1 对熵函数法作了进步的研究，对改进的熵函数法作了较深入的理论分析， 给出了误差估计，并将其用于解一般的约束问题、多目标规划问题在此基础上 叉构造了一种新的对偶算法，并给出数值实验和收敛性证明 2 对同伦算法作了进步的推广应用，并利用熵函数法思想，给出了多目标 规划的一种连续同伦算法，此外对非线性方程组提出了一种路径跟踪算法，理论 分析与数值实验表明本算法比其它算法具有更快的收敛速度，且数值稳定性较好 3 对填充函数法作了较深入的研究，在已有算法的基础上提出了一种单参数 填充函数法，理论分析与数值实验表明该算法明显优于已有的算法 、 关键词：改进的熵颇数法对偶算法连续同伦算法路径跟踪算法单参数填充函数 小、 法 l n 盯 a b s t r a c t t h i st h e s i si sd e v o t e dt os o m en u m e r i c a lm e t h o d s s u c ha se n t r o p ym e t h o d ，f i l l e d f u n c t i o nm e t h o da n dh o m o t o p ym e t h o d t h e i rp r o p e r t i e sa n de x t e n d e da p p l i c a t i o n sa r e d i s c u s s e do ne m p h a s i s t h em a i nw o r ko ft h ed i s s e r t a t i o n c a r lb es u m m a r i z e da s f o l l o w s ： e s s e n t i a l p r o p e r t i e s o ft h e a d j u s t e d m a x i m u m e n t r o p y f u n c t i o na n dt h e c o n v e r g e n c ea n a l y s i so f t h em e t h o da r ei n v e s t i g a t e da tf i s t t h e nt h ee f f e c t i v i t yo ft h e m e t h o di si l l u s t r a t e db yu s i n gt os o l v et h eg e n e r a lc 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 a n dt h em u l t i o b j e c t i v ep r o b l e m f u r t h e r m o r e ，a ne x t e n d e dd u a la l g o r i t h mi sd e s c r i b e d f i n a l l y ，n u m e r i c a lr e s u l t sa r eg i v e na n da n a l y z e d s o m en e we x t e n s i o na n da p p l i c a t i o n so ft h eh o m o t o p ym e t h o da r ed i s c u s s e d f i r s t ， a nc o n t i n u e dh o m o t o p ym e t h o d ，b a s e do nt h ee n t r o p yf u n c t i o n ，i sa p p l i e dt os o l v et h e m u l t i o b i e c t i v ep r o b l e m t h e na np a t hf o l l o w i n gm e t h o do nt h eb a s i so ft h ee n t r o p y f u n c t i o ni s a p p l i e d t os o l v en o n l i n e a re q u a t i o n s t h e o r ya n a l y s i s a n dn u m e r i c a i e x p e r i m e n t ss h o w t h a tt h em e t h o di se f f e c t i v e b e s i d e sa l lo ft h ea b o v e an e wm o d i f i e df i l l e df u n c t i o nm e t h o di sg i v e nt os o l v e t h el i p s c h i t z p r o b l e m ，a n dt h ec o n v e r g e n c ea n a l y s i sa n d t h en u m e r i c a lr e s u l t ss h o wt h i s n e wm e t h o di sp r a c t i c a la n de f f e c t i v e k e y w o r d s ：a d j u s t e d m a x i m u me n t r o p yf u n c t i o ne x t e n d e dd u a la l g o r i t h m t h e h o m o t o p y m e t h o dp a t hf o l l o w i n gm e t h o dm o d i f i e df i l l e df u n c t i o nm e t h o d 第一章绪论 本章介绍了论文的写作背景，并对近几年备受关注的几种解优化问题的算法 介绍了它们的研究现状，最后给出了本文的主要工作 1 1 引言 优化问题广泛出现在信号处理、系统识别、滤波设计、函数逼近、自动控制等 科学技术领域，在这些领域中如何运用定量分析计算来提高预定的精确度，一 直是优化研究者不断追求的目标通常，研究者把所处的环境看作一个系统，通过 系统仿真、系统模拟，再运用最优化手段，最终达到预期的目的，因而能够定量 分析的系统，最优化方法是实现上述目标的一个有效途径，故优化方法进一步的 研究是研究者一直努力的方向 本文的内容属于算法研究，主要针对管理科学与工程领域中一些重要优化模 型，结合近几年备受关注的几类优化算法，如极大熵方法、同伦算法等，对算法 的性质、收敛性及推广应用进行了深入的研究 下面将对极大熵方法、同伦算法等算法的研究现状作一些介绍，最后节介绍 本文的主要工作 1 2 极大熵方法的研究现状 在工程与管理科学领域中，许多问题的数学模型都直接或间接的涉及到最大 值函数如有限的、半无限的极小极大问题，由于这类函数本身是不可微的，这就 使得求解可微优化问题的优秀算法不能直接用来求解此类问题，因此，构造可微 的函数去逼近最大值函数，用可微的优化问题的解去近似原问题的解，这无疑给 不可微优化问题的求解带来了很大的方便 极大熵方法就是在上述思想指导下发展起来的一种较新颖而且实用的优化方 法“，它主要对于极大极小问题 ( 尸)r a i n f ( j ) = m 。a ；。x f i ( x ) s t g ( x ) 0 ，= l ， 先通过最大值函数将( p ) 转化为单约束问题 i n _ f ( 鼻) m i nf ( x ) 2 役野，( x ) 5 。黝g j ( 。) s o 再用极大熵函数构造与( 只) 等价的问题 ( b ) m i n ( 炉刍1 n 量i = 1 e x p ( 一( 砌 s - g 。( x ) 2 ；l n3 壹= 1 e x p ( q g ，( x ) ) 最后利用罚函数法等方法解可微优化问题( b ) 1 6 - 1 3 1 ，用( b ) 的解去近似( p ) 的解，从数值实验角度来看这种方法存在着很大的优点 经过十多年的发展，主要取得的成果如下： ( i ) 对于极大极小问题( 包括无约束极大极小问题与带约束的极大极小问题) 李兴斯川利用j a y n e s 熵原理给出了极大极小问题目标函数对应的极大熵函数，并 证明了当参数趋于无穷大时，熵函数的解是所求问题的解此后，李兴斯、唐焕文、 万仲平、王云诚等都在这方面作了大量工作1 6 ”o ” ( 2 ) 一般的约束优| 化问题这类优化问题的极大熵函数法最早也由李兴斯【4 】给 出，由于这种方法要求约束区域非空，因而仅适用于不等式约束问题一般的约 束优化问题的极大熵函数法是由唐焕文岬1 等给出的这种方法是将 ( g p )r a i nf ( x ) s r g ，( x ) 0 ，i = l ，k h ，( x ) = 0 j = l ，m 用下述问题来近似 ( g p ) m i n 厂( x ) s t g 。( x ) 0 h 。( x ) 6 ( q ) 其中g ，( x ) = j 1 i n t 。= l 。( x ) ) ，h 。( x ) = i 1 1 e x p ( p g 1 1 n ；，e x p ( q b j ( x ) ) ，s ( g ) 2 詈1 n ，”，另其中g 一( x ) 2 j 1 n 俐h 。( x ) 2 ，- 1“) “( g ) 2 ；1 n m 另 外，对一般约束优化问题还有另一种实现形式，详见王云诚1 2 2 1 、旌保昌”1 ( 3 )多目标优化问题 施保昌 2 4 1 、胡新生i 硼对形如 m i nf ( x ) = ( 一( x ) ， ( x ) ，厶( x ) ) s r x = z r 41 9 j ( x ) 0 ， ，= 1 ，一，” 其中，( x ) 。m 。a 。x l ( x ) ，f _ 1 ，卅，对目标函数的成员函数，( x ) 用熵函数 ，( ，p ) ：! i n 圭e x p ( p f , j ( z ) ) 代替，相应的约束也用熵函数代替，施保昌1 、胡新 p = 1 生1 2 6 还给出了收敛性分析 王雪华和秦学志7 1 对常规的多目标函数也构造了以最大值函数作为评价函数 时的极大熵函数法本文在极大函数法的基础上，也给出了一种解多目标规划的方 法，此方法具有熵函数法与同伦方法的共同特点，是一种行之有效的方法，详见 本文第三章 ( 4 ) 半无限优化问题 半无限优化( s e m i - - i n f i n i t ep r o g r a m m i n g ) 是工程设计领域常见的种求解 有相当难度的问题，1 9 9 5 年，周广路】针对下述半无限优化问题： ( s p ) m i n f ( x ) s j 以( ，r ，) 0 ，f ，口，i = 1 ，。一，f 利用j a y n e s 熵原理建立了极大熵方法即 ( s p l ) m i n f ( x ) j t ( x ，p ) 0 其中删w ) = 吉l n 砉志小x p ( 刚x , l i 减) ，v ( 鳓表示紧集q 踟慷j 该 文还证明了若z ：是( s p ，) 的解，则当p _ 。时，其极限点x 是问题( s p ) 的最优 解 另外，黄震宇田1 利用j a y n e s 熵原理也给出最大值函数的一个近似函数： 1 硼厂 土l n 圭蜡e x p ( ( x ，o d t ) ，并研究了该函数的一些性质及算法的实现策略王长钰与 p r = l 韩继业【2 1 1 以周广路构造的方法为基础，对算法的收敛性及稳定性进行了深入的分 析研究，万仲平、胡新生也在这方面做了进一步的研究 此外，极大熵方法在线性规划( 唐焕文、张立卫0 9 1 ) 、模糊优化1 3 0 i 、大系统 优化问题【2 0 1 等领域也有广泛的应用，这些文献见h a j e l a i j 杨海霞m 等 极大熵函数法虽然结构简单，方法易实现且计算速度快，但当参数充分大后， 熵函数便趋于病态 12 - 1 4 1 ，使得算法无法进行下去，这便是当前研究者研究改进的 方向张立卫”、杨庆之等03 1 分别给出了一种带有新参数的熵函数方法，与原方法 相比，这种方法更加稳定、有效虽然，这种熵函数与一种罚函数等价】其原理 也与原熵函数相差太大但两个函数本身在形式上类似故在这儿仍称这种熵函 数是原熵函数的一种改进 本文对熵函数方法的改进做了进步的研究，给出了详细的理论分析及误差 分析，结果表明改进的方法比原方法更优，内容详见第二章 1 3 同伦方法及其研究现状 同伦方法( h o m o t o p ym e t h o d ) 作为数学概念已有一个世纪，直到1 9 5 3 年 d a v i d e n k o 【3 6 】给出了“p a r a m e t i cd i f f e r i e n t i a t i o nm e t h o d ”，同伦算法才正式的成为求 解数学问题的真正工具，1 9 7 4 年，k e l l o g g 、l i & y o r k e 3 7 1 利用微分拓扑工具，成功 的用同伦方法给出了b r o u w e r 不动点定理的构造证明，并且阐明了同伦路径的存 在性及光滑性是平凡的，同时解决了该方法的整体收敛性，其后，s m a l ea n dc h o w 等又推广和发展了同伦算法提出了一系列可行算法，而用同伦算法解数学规划 问题则是在1 9 7 9 年，g a r c i aa n dz a n g w i l l 在文m 1 中，对凸规划构造了一种同伦算 法，并证明了算法是整体收敛的 1 9 8 4 年k a r m a r k e r 算法m 1 发表后，使研究者在研究线性规划的内点算法的 同时，又重新开始研究求解非线性规划的内点算法，由于同伦算法的优点，研究 者将同伦算法与内点算法相结合便产生了一系列的新的内点算法一路径跟踪算 一一孤硼r 一 法m o n t e r i o & a d l e r ，k o j i m a 等。4 4 1 分别将线性规划原始对偶算法( p r i m a l - - - d u a l p a t h - - f o l l o w i n gm e t h o d ) 推广到二次规划与一些特殊的凸规划问题，随后， k o r t a n e k ，p o r t r a & y e ，z h u ，王宇”。4 7 1 等各自独立的推广到一般的凸规划问题m c c o r m i c ，f i a c i o 等【4 9 1 对凸规划问题借鉴线性规划的k a r m a r k a r 算法也建立了相应的 路径跟踪算法 为了研究非凸规划的整体求解问题，冯果忱、于波、林正华1 5 1 , 5 5 1 提出了利用牛 顿同伦与不动点同伦组合的组合同伦内点方法( c o m b i n e dh o m o t o p yi n t e r i o rp o i n t m e t h o d ) 求解非凸规划问题，并在一定条件下证明了算法的迭代点列收敛到问题的 k t 点 刘庆怀 6 7 1 又将组合同伦内点方法用于求解多目标规划问题，在特定假设条件 下，证明了算法收敛到多目标规划的一个弱有效解本文也利用该思想，借助熵函数 法思想，给出了求解多目标规划问题的连续同伦方法，并证明了该方法的可行性及 有效性，详见本文第三章 由于该方法在求解线性规划、凸规划、非凸规划、变分不等式等方面都取得了 良好的结果，故该方法的应用前景比较广阔但现行算法总有些不足之处，如在求 解非凸规划时，只有在很强的条件下才能保证算法的整体收敛性，故需研究者进一 步的研究 1 4 填充函数法及其研究现状 填充函数法( f i l l e d f u n c t i o n m e t h o d ) 是葛人溥1 7 7 提出的求解多变量函数全局 极值点的一种有效算法，它的主要思想是构造一个辅助函数填充函数，此函数 在所求函数任何一个极小值点的山域( 定义见第四章) 中没有极小值点或鞍点，但 在局部极小值点的谷域( 定义见第四章) 中有一个极小值点或鞍点，在每次求解到 原函数的极小值点后构造一次填充函数，然后求解构造的填充函数将得到的填充 函数的极小值点或鞍点作为新的起始点，重新求解原函数的极值点，这样依次下去 便可求得原函数的全局极小值点 葛提出的填充函数法主要针对凸可微优化问题，庄建南m 1 、孔敏与庄建南1 7 4 1 提 出了求解非光滑优化问题总体极小值点的填充函数法，但是以上文中提出的填充函 数法都是基于双参数，给实际计算带来了困难李宝秀、沈愉【7 5 】提出的求解l i p s c h i t z 叽哪一 规划的一种单参数填充函数法，且收敛条件也比前面文中弱的多本文基于以上思 想提出了一种新的求解l i p s c h i t z 规划的单参数填充函数法，理论分析及数值计算 表明要比前文提出的算法优越的多，算法详见第四章 1 5 本文的主要工作 本文的主要工作是对优化算法的研究： 1 对熵函数法做了进一步的研究将原熵函数法做了改进并做了深入的理论分 析，给出了误差估计，并将算法推广到求解单目标规划与多目标规划问题在此基 础上又给出了一种求解约束问题的对偶算法，并给出了大量的数值结果 2 介绍了同伦算法的思想，且在熵函数法思想与同伦方法思想的基础上，提出 了求解多目标规划的连续同伦方法，并给出了深入的理论分析作者又在熵函数法的 思想上给出了求解非线性方程组的路径跟踪算法，理论分析及数值结果表明本算法 是可行且有效的 3 针对一类规划问题提出了一种改进的单参数填充函数法，数值实验及计算结 果表明该算法优于以往的算法 第二章熵函数法的改进及推广应用 本章对熵函数的改进做了进一步的研究，在进行理论推导的同时，也将改进 的方法推广到求解多约束单目标问题与多目标规划，并提出了一种新的对偶算法， 理论分析与数值结果表明，改进的熵函数法的确比原有的熵函数法优越 2 1预备知识 科学计算中的许多问题都归结到求解如下问题： ( p )r a i nf ( x ) = m a x 工( x )( 2 11 ) 其中，正( x ) 是光滑函数，由于f ( x ) 2 m a ；。x f , ( x ) ( m 2 ) 是不可微的，所以以梯度为 基础建立起来的许多优秀算法不能直接用于求解上述问题 用熵函数法求解问题( p ) 是利用函数 ( x ) = 二i n y e x p ( 形( x ) ) ( 2 1 2 ) p t ；i 来近似问题( 2 1 1 ) 中的f ( x ) ，虽然该方法在实际计算中有很大的优点，但当约束 增加，维数变大且当参数趋于无穷大时l ( z ) 的h e s s i a n 矩阵趋于奇异出现病态 故该方法的改进一直是研究者不断努力的方向 本章将进一步研究熵函数的改进，并进行理论分析和推广应用下面给出一些 预备知识： 定义a = 兄r ”， o ，f = 1 ，m ， ，= l ，易知 ，= 】 f ( x ) = 毋野 工( x ) ) 4 e d ，一t 其极大熵函数是按信息论中的最大熵原理得到的 1 3 l ，其定义为： ( x ) ：m 。a x 州y 3 i 工( z ) 一言1 酗1 毗 脚m 经过简单计算，便可得熵函数( 2 1 2 ) ，同样，我们可用信息理论来改进熵函数法， 如果将x 看作信息，“_ ( x ) 等于f ( x ) ”看作一个事件， 看作z ( 工) 等于f ( 工) 的概率， b e l i s 和g u i a s u 为更合理的刻画质与量在s h a n n o n 熵中引入有效分布因子 = ( h ，一：，u 。) 7 ，“表示信息对第i 个事件的效果，修正后效果更好同样 将此因子引入熵函数，定义： ( 丘们2 嘴 喜 ，( x ) 一刍喜 l n 砉) 经计算得： ( x ，) 2 = 11 n “e x p ( p z ( x ) ) ( 2 l 3 ) ， ，= 1 则称( 2 1 3 ) 为改进的熵函数其中a = 一只”，“0 ，i = 1 ，m 定义，= f l - ，：( x ) = f ( 石) ，i = 1 ，棚) ，a ，= 舡4 且若i 仨，有“= 0 ) 2 2 改进熵函数法的理论探讨 考虑问题( 2 1 1 ) ： ( p ) m i n f ( x ) 2 燃：( x ) 这里：( x ) ( i = 1 ，m ) 是r ”中的连续可微凸函数，( p ) 是常见的一类非光滑问题，实际 中的许多问题的模型可转化为( p ) 的形式，所以如何求解( p ) 是一个关键问题- 这儿我 们用改进的熵函数法( 2 1 3 ) 求解下面给出收敛性分析与误差估计 2 2 1 收敛性分析 由上一节司得改进的墒函数为 驰肋。1 酗e x p ( 顽( x ) ) 定理2 1若对固定 o 且卢0 ，确- ( 1 n hm a x “) p ( x ，) 一f 0 ) 0 ， 且当p 斗+ 。时，e ( x ，) 一致收敛到f ( x ) 证明 由( l ) 2 1 。1 n “c x p ( o ) ) ) ，则 ， j i ( l ) 一f ( x ) 2 吉1 n 善“e x p ( 顽( z ) ) 一古1 n e x p ( p 恐笛，o ) )，j = l一 2 如酗e x “州础m a 。x f ( 曲) 1 p i n 善一，r t l一， ，；1 由a ，调节，使得“一1 ，结论成立 由题设，一定存在i ，使得z ( x ) = f ( x ) ，所以 ( l 肋。石11 n 喜he x p ( 形( 瑚) 古l n 一, e x p ( ：( 瑚) ：f ( x ) + 上l n “ p 故有c ( x ，) 一f ( x ) ( i n m a x 2 ，) p 对固定 0 且0 ，由( 1 n d m a x 4 ) p ( x ，) 一f ( x ) s 0 ，易得当p 斗+ 时，c ( x ，) 一致收敛到f ( x ) 由上可知文【1 4 中的结论( 1 n “p ) g ( x ，) 一f ( x ) s 0 是错误的，因为改 r e ， 进的熵函数法与一种罚函数法等价，2 是罚因子，所以e r ”，1 0 且 2 ，= l ( n t 方n 仍将集合记为a ) 故1 n 1 p 2 0 ，这样，其文中估计式就 j e ， 没有任何意义了 定理2 2 对于x 月”及p r + l ( x ，) 2 f 0 ) 当且仅当a s 以上两个定理表明，我们不仅调节p ，而且可通过调节一t 吏g ( x ，) 更快速逼 近f ( x 1 下面讨论l ( x ，) 的h e s s i a n 矩阵性质，经过计算可得 v ，g ( x ，) = ( x ，) w ( x ) v ：f ( x ，) = ( x ，) v 2 ，( x ) + p v f ( 工) ( d ( x ，) 一d ( x ，a ) e e 7 d ( x ，) ) v f ( x ) 些些塑巡 其中_ ( x ，卢) = ( “e x p ( p z ( x ) ) ) ? he x v ( p f , 工) ) ，v f ( z ) ：( w ( j ) ，既( 。) ) ， d ( x ，2 ) = d i a g 】。；。( ( x ，) ) ，p = ( 1 ，1 ) ： 设 x l , ( 见，“) ) 是迭代得到的点列( “( n ，以) 简记为 ) ，则对任意z r n 有 ：7 v f ( x , ) ( d ( j 。，“) d ( x k , 女) e e r d ( x , 1 2 k ) ) v f ( x 。) z r = ：( d ( ，t ) 一d ( x f ，p t ) e e 7 d ( x 女，。) ) 三 ( 2 2 1 ) 其中，z = v f ( x 。) 7 z ，e d ( x 。，“) p = 五( h ，“) ，所以( 2 2 1 ) 式可化为 ；7 d ( 工。，“) ；一力( 坼，以) ( _ ，以) ； 2 ( 1 l d ( x 一，a t ) z i i ) 2 一( 【( 石( 以，“) ；) j ( “，胁) 2 ， 其中d ( x l ，“) 2 = d ( 以，以) ，j ( _ ，以) 2 = 工( ，胁) 类似文 1 4 ，注意到| | j ( 以，以) f f 2 = 1 ，应用l a g r a n g e 恒等式有 2 d ( x t ，“弦：1 2 ( x t ，“) 五7 ( _ ，以) ；= 暑( 以，“m ，( _ ，以) ( ；，一；，) ， 设五。，k 。为v ：f ( h ，“) 的最大最小特征根，4 l = 芝 ( t ) v ：( ，) ，则有 五m 。2 雩磐z 7 v ：f ( ，“) z l l = 1 1 2 嘧，l z l l = n p m 。i 。n ( h ，“) - ( h ，m ；，一一z j ) 2 巾z i i z ( 2 心 五一。m a x z 7 v ：r ( x 。，d z l lz l l 2 咖z t z 。l lz n p m a x y z 工, ，“) 乃( 以，肌) ( i z j ) 2 巾：旷( 2 2 3 ) 因为，( z ) 是非光滑函数，设一j ，五( ，胁) 斗兄( t 呻+ ) ，则有 五( ，g d 2 ( x 。，以) ( 一；巾z 忪。 且m 。i n z r l z z 旷为有限数，所以有 1 4 i m 。1 1v ：f ( e ) i i = + m 上面分析表明，如果一直在调节p ，使p 充分大，仍然会出现c ( z ，) h e s s j a r i 矩阵 的病态情况，所以改进的熵函数法在取得充分大的p 后，便不再增加p 的值，而是 而是通过调节，使得c ( x ，2 ) 收敛到，( x ) 但是，如何选取合适p ，才能使结果 更精确，这便是下面要讨论的 不妨假设，= 1 ，l , is ，蔓m ，定义d ，( x ，一) = d a g 。；，( 丑( z ，) ) ， u = d i a g l ；，“( ，) ，v ，f ( x ) 2 ( ( x ) ，。，v f , ( x ) ) 定理2 3设( x ，) 为l ( x ，) 的稳定点，p ，= 1 1v ：f ( x ，) l l ， p z = n ! i n 2 , ( v ，f ( x ) u ，v ；f o ) ) ， ( 一) 表示矩阵a 的特征值- 令p = p ? ( p ：口) 一p ，p ：，0 0 为常数，则当p p 时，v ：( x ，) 为半正定的 证明由 v 2 ，f ( x ，) = ( x ，) v 2 ，( x ) + p v f ( ) ( d ( 五) 一d ( ，。t ) e e 7 d ( j ，) ) v f ( j ) 则 7 2 f ( x ，) = ( x ，1 ) v 2 l ( x + ) + p v ，f ( x ) ( d ，( ，+ ) 一d ，( x ，f + k ，p 7 d ，( z ，) ) v ，f ( x ) 类似文【1 6 的证明，便可得证 推论2 3 1 定理2 3 条件满足，若p p ，则v ：( x ，) 为正定的 定理2 4 ，( z ) 如前定义，p 的定义见定理2 3 且p p ，若h ( 儿，u 。) 是 l ( z ，) 的稳定点，则 屯( 仇，t 。) ) 的聚点是，( x ) 的极小点 证明因为_ ( n ，心) 是( z ，) 的稳定点则由推论2 3 1 可得坼( 仇，纨) 是 只( x ，) 的局部极小点故有 ( 以，以) w ( 札) = 0 设h ( 以，脚) 一；， ( h ，肌) 斗五五0 ，所以有 五，w ( ；) = 0 j = l 由非光滑理论得0 o f ( x ) ，所以；是f ( x ) 的稳定点，又，0 ) 是凸函数，所以f ( x ) 是凸函数，故x 是f ( x ) 的极小点 2 , 2 2 误差分析 这一部分将对改进的熵函数法产生的近似解与精确解之间的误差进行分析， 通过分析可以得到，在相同的条件下，改进的熵函数法产生的近似解的确比原熵 函数法有更高的精度 定理2 5 若- ，：( x ) 是凸函数，x 为f ( x ) 的精确解，对于k t a ，p p ( p 的定 义见定理2 3 ) ，则有 i ix ( p ，) 一x i 蓐o ( 苫) p 证明由t a y l o r 展式得 ( z ) = ( z ( p ，) ) + ( x - x ( p ，) ) 7 v ，( j ( p ，) ) ( + 一x ( p ，) ) 十( x + 一x ( p ，) ) 7 v ：( x ( p ，) ) ( x 一x ( p ，p ) ) 2 由v 。c ( x ( p ，) ) = o 得 c ( x ) = f a x ( p ，) ) + ( x 一x ( p ，) ) 7 甲：( x ( p ，) ) ( x 一x ( p ，) ) ，2 所以有 ( x ) 一( x ( p ，一) ) = ( x 一x ( p ，) ) 7v ：( x ( p ，) ) ( x 一x ( p ，口) ) 2 ( 2 2 - 4 ) 由已知p p ，得v ：v a ；( p ，) ) 是半正定的，故存在k 0 使 ( x 一x ( p ，) ) 7 v ：巴( ；( p ，一) ) ( x + 一x ( p ，) ) k | | x + - x ( p ，1 ) 幢 ( 2 2 5 ) 事实上k 可取v ：c ( x ( p ，) ) 的最小特征根 又 f a x ) 一只( x ( p ，卢) ) = c ( x ) 一f ( x ) + f ( x ) 一，( x ( ，p ) ) + f ( x ( u ，p ) ) 一( 工( ，p ) ) ! p i n z 。“一吉l n wm a x “2 一上p l n 。，m a x ， ( 2 2 ，6 ) 由2 2 4 ，2 2 5 ，2 2 6 得 量三童墅鱼墼鎏墼重鲎堡望量垄墼坠：；：= = = = = = = = x * - - x ( 删) i 一去l n “一即即 i ix 一x ( p ，卢) 1 1 2 x - ( 1 n , 。m a x , u , ) k p ( 2 2 - 7 ) 只要适当调节，便有l n 。，m a x 2 ，_ + 1 ，由文【1 4 】，原熵函数的近似解及最优解的误 差为 i ix 一x ( p ，) i i ：c 扛 ( 2 2 8 c 为常数，由2 2 8 可得，只要适当调节便有 i lx ( p ，) 一x i | 。( ) 、p 由2 _ 2 7 、2 2 8 得在相同的熵参数下，改进的熵函数法有更高的精度，所咀，改进的 熵函数法有更广的使用范围 推论2 _ 5 1 在定理2 5 的条件下，n p p 时，有忙( p ，) 一x 临。( 刍) 2 2 3 算法及数值例子分析 算祛2 2 1 2 s t e p l 给出充分大的尸 o ( p 的选取可按本文中定义的方法) ， o ，p 。 o x 。 掣? ：土，i ：l ，删，f 1 ，k = o ； s t e p2 以x t 为初始点解m i nf 。( 石，。) ，得x ，若| | x k + l x i l 0 且0 ，有( 1 n e ，m a x a ，) p c ( x ，) 一，( x ) o ， ( i n m a x v ) q g ，( z ) 一g ( 了) o ，且当p ，q 斗+ 时，c ( z ) 一致收敛到 f ( z ) ，g q ( t ) 一致收敛到g ( z ) 证明利用本章的第二节即可得证 定理2 4 2 m 1 问题( m s p ) 的解是问题( m p ) 的弱有效解 下面给出数值实验结果与结果比较 ( 1 ) 1 i ，1 9 9 4 m i n 厂( ) = ( ( x ) ，j ( * ) ，f 3 ( x ) ) ( x ) = 2 e x p ( - x 1 + x 2 ) x 】+ 。2 2 = 0 ( 2 ) 旋，1 9 9 7 1m i n ( x ) = ( 工( t ) ， ( x ) ， ( x ) ) ( x ) = 2 e x p ( 一x 】+ x 2 ) 一x i + 1 1 3 9 0 3 0 x 1 。2 3 o ，。2 0 初始点参考近似解参考晟本文近似解本文晟优 优值值 ( 1 )( 1 0 ，一8 )( 1 3 5 3 5 5 9 ， 2 2 5 ( 2 3 5 3 5 3 1 ， 2 2 4 9 9 7 8 0 6 4 6 4 4 3 )0 6 4 6 4 7 8 ) ( 2 )( 2 ，2 )( 1 3 9 0 4 ， 1 9 5 2 2 ( 2 1 3 9 0 0 2 ， 1 9 5 2 2 5 2 0 8 9 9 5 )0 8 9 9 5 8 7 ) 以上数据表明本算法是有效的 考虑问题 ( p b ) 2 5 求解约柬优化的对偶算法 s t g ，( x ) 0 ，i = 1 ，m 其中厂 ) ，g ( x ) 是连续可微函数，求解( p b ) 的方法很多，如传统的乘子法，序列 二次规划法等，但近年来发展起来的原始一对偶算法的研究已成为非线性规划领域 新的热点 4 0 , 4 u 3 ，尽管这些算法具有好的收敛性和计算效果，但其结构相对复杂， 文【3 3 】构造了一种易于实现的对偶模型，它不需初始可行点的计算，且理论分析表 明这一算法具有良好的收敛结果，本文利用其思想，构造一种更为一般的形式，且 数值实验和数值结果表明本文提出的算法比文 3 3 中的算法有更广泛的应用 定义 弘川叫卅暑弘e x p ( 刚功 ( 2 5 1 ) 其中p 0 ，u e 月? ，口 0 ，显然，( 2 5 1 ) 的第二项便是本章重点研究的改进的 熵函数，由于只( 工，肋具有良好的性质( 详见本章第二节) ，下面给出基于( 2 5 1 ) 的对偶算法： 算法l 2 5 1 s t e p l 选取p ( 可按第二节的标准选取) ，口 0 ，1 月? ，令k = 1 s t e p2 求解 x = a r g m i n m 。( * ，) s t e p3如果卢? i ：0 ) = 0 ( i = 1 ，m ) 成立n x 。是( p b ) 的稳定点否则， 转s t e p 4 s t e p4 修正， “= ? e x p ( p g ( x ) ) ，i = 1 ， s t e p5令k = k + l ，口= 2 a 转s t e p 2 只( x ，+ ) 的性质详见本章第二节，下面给出几个定理 定理2 5 1若( x ) ，毋( x ) 是二次连续可微函数，记2 = ( x ，u ) 为问题( p b ) 的k t 点，严格互补松弛条件成立，若甲g ( x ) 满足列满秩，则存在p 0 ，当 p p 时，v ：c ( z ，) 严格正定 证明由本章第二节的定理及文 3 3 便可得证 定理2 5 2 若定理2 5 1 的条件成立，则存在占 0 ，p 1 及z 的邻域u ( x ，s ) 满足：对任意的p ；及j ( ，s ) = 卢l i i t - k t 忙s ，畔) ，有以下结论成立 ( 1 ) 存在x = x ，( “) e i n t u ( x , 占) 满足v ，( j ，) = o ( 2 ) x = a r g m i n f p ( x ，) lx u ( x ，s ) 证明由本文第二节及文( 3 3 定理3 1 便可得证 下面给出数值实验结果与数值比较： ( 1 ) 胡运权r a i n ，( x ) = x ；+ x ；+ 2 x ；+ 0 5 x 2 x 3 4 x 1 - g x 2 1 0 x j s t g l ( x ) = 4 x i + 2 x 2 + x 3 1 0 0 9 2 ( z ) = 2 x l + 4 善2 + 工，一2 兰0 g 3 ( x ) = 一一s o ，g ( x ) = 一x 2 o ，9 3 ( x ) = 一x 3 曼0 ( 2 ) r o s e n s u z u k i r a i n ，( 工) = x ；+ x ：十2 x ；一5 x i 一5 x 2 2 1 x 3 + 7 x 4 s t g l ( x ) = 工? + x ：+ x ；+ x ；+ x 1 一工2 + x 3 + 7 x d 0 9 2 ( x ) = z ? + 2 x ；+ x ；+ 2 x ；一x 1 一x 4 8 0 9 3 ( 工) = 2 x ? + 工；+ r ；+ 2 x l f 2 一j d 一5 0 表4 数值结果