（计算数学专业论文）全局优化中辅助函数法的研究.pdf

引言 a b s t r a c t g l o b a l o p t i m i z a t i o n a d d r e s s e st h e c o m p u t a t i o na n dc h a r a c t e r i z a t i o n o fg l o b a l s o l u t i o n st on o n l i n e a rf u n c t i o n t h em a i nt a s ko fg l o b a lo p t i m i z a t i o ni st od e t e r m i n e ( w i t ht h e o r e t i c a lg u a r a n t e e s ) a na p p r o x i m a t eg l o b a lo p t i m a ls o l u t i o no ft h eo b j e c t i v e f u n c t i o nw i t has e to fc o n s t r a i n t so ru n c o n s t r a i n t d u et ot h ed e v e l o p m e n to fs c i e n c ea n dt e c h n o l o g y , t h eg l o b a lo p t i m i z a t i o np r o b l e m s a r eo f t e nd i s c o v e r e di nt h ef i e l do fe c o n o m i cp l a n n i n ga d m i n i s t r a t i o n ，e n g i n e e r i n gd e s i g n ， p r o d u c t i o nm a n a g e m e n t ，t r a f f i ct r a n s p o r t a t i o n ,n a t i o n a ld e f e n s e sa n ds o o n i th a s a t t r a c t e de x t e n s i v ea t t e n t i o n t h ea u x i l i a r yf u n c t i o nm e t h o df o rg l o b a lo p t i m i z a t i o nh a v e b e e ne x t e n d e da n di m p r o v e di nt h i sp a p e r t h i sp a p e rc o n t a i n st h r e ec h a p t e r s ： i nt h ef i r s tc h a p t e r , s e v e r a lb a s i sc o n c e p t sa n dc h a r a c t e r so ng e n e r a l l yn o n l i n e a r p r o g r a m m i n ga r ci n t r o d u c e d t h e ns o m et y p i c a l m e t h o d sf o r g l o b a lo p t i m i z a t i o n p r o b l e m sa r eb r i e f l yp r e s e n t e d i nt h es e c o n dc h a p t e r , an e wf i l l e df u n c t i o nm e t h o do ns o l v i n gg l o b a lo p t i m i z a t i o n p r o b l e m sw i t h o u tc o n s t r a i n ti s i n t r o d u c e d an e wf i l l e df u n c t i o nf o rs o l v i n gg e n e r a l u n c 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 ma n di t sf e a s i b l ef i l l e df u n c t i o na l g o r i t h ma r eg i v e n ， t h en a t u r eo ft h ef u n c t i o ni sa n a l y z e d n u m e r i c a le x p e r i m e n t sv e r i f i e dt h ee f f e c t i v e n e s so f t h ea l g o r i t h m i nt h et h i r dc h a p t e r , an o v e lc u t p e a kf u n c t i o nm e t h o da n d ”s t r e t c h i n g ”f u n c t i o n a l g o r i t h mf o rt h eg l o b a lo p t i m i z a t i o np r o b l e m sd o s e dw i t hb o x - c o n s t r a i n ta r em a i n l y i n t r o d u c e d t h ei m p l e m e n t a t i o np r o c e d u r eo ft h et w oa l g o r i t h mi sc o m p a r e db yg r a p h i c s a n dan e wa u x i l i a r yf u n c t i o ni se s t a b l i s h e db a s e do ni t t h ea l g o r i t h mi n t e g r a t e db o t h s i d e s t h o u g h ta n di se a s yt ob em a d e k e yw o r d s ：n o n l i n e a rp r o g r a m m i n g ；g l o b a lo p t i m i z a t i o n ；f i l l e d f u n c t i o na l g o r i t h m ；c u t - p e a kf u n c t i o nm e t h o d ；s t r e t c h i n g f u n c t i o n m e t h o d 2 青岛大学硕士学位论文 目录 引言1 第一章全局优化问题及其算法3 1 1 预备知识3 1 2 几种确定性算法4 第二章一个新填充函数算法1 0 2 1 填充函数1 0 2 2 算法1 3 2 3 数值实验1 4 第三章割峰函数法和“s t r e t c h i n g 一函数法1 8 3 1 割峰函数算法1 8 3 2 “s t r e t c h i n g 函数算法2 0 3 2 1 “s t r e t c h i n g 函数及其性质2 0 3 2 2 “s t r e t c h i n g 函数算法描述2 1 3 3 一种新的辅助函数法2 4 3 3 1 辅助函数的构造2 4 3 3 2 新的辅助函数法描述2 6 结论2 8 参考文献2 9 攻读硕士学位期间撰写的论文3 2 致谢3 3 学位论文独创性声明3 4 学位论文知识产权权属声明3 4 3 青岛大学硕士学位论文 ji 士 i 亩 最优化理论和方法的问世与应用可以追溯至古老的极值问题，而直到2 0 世纪 4 0 年代末d a n t z i n g 提出了求解一般线性规划问题的单纯形算法之后，它才成为了一 门独立的学科。随着计算机技术的巨大发展以及信息时代的到来，短短几十年间， 该理论和方法得到了迅猛的发展与飞跃。现在，最优化问题的理论研究已涉及到各 种优化问题如：最优化已经成为一门十分活跃的学科并被广泛的应用于交通运输、 工程设计、经济计划、生产管理等诸多重要领域，因此受到科研机构和生产部门等 的高度重视，引发广大学者们的积极讨论和研究。 最优化主要研究某些用数学模型表述的问题，这些模型主要来源于分子生物学、 经济金融、环境工程、网络运输、与工业制造化学工程设计等。而此类最优化问题， 特别是从工程优化中设计出来的优化模型都要求的是全局解而非局部解。另外，科 学与工程的许多最新成果都依赖于计算优化问题全局解的数值技术。即得到问题的 全局最优解是最优化问题求解的根本目标。这就有了本文主要讨论的全局优化问题。 全局优化问题一般考虑的问题i l j 是 m i n 厂0 ) s t x x 其中zc 彤是可行域，厂：尺_ 呻尺是目标函数。 求解决全局最优化问题的理论与算法已被相继提出，这些方法一般可分为三类： 第一类是确定性算法，其中包含通过调用某种辅助函数，从目标函数的一个局部极 小点出发去寻找更优的局部极小点；第二类是包括了运用随机算法和启发式方法来 进行搜索；第三类是包括了限制应用到具有特殊结构的问题上的方法，如不定二次 规划，d c 规划等。 本文考虑的是辅助函数方法中的填充函数算法、割峰函数算法以及“s t r e t c h i n g 函数算法，三者实现过程分均为两个阶段，第一阶段都是极小化阶段，采用局部优 化方法寻找的一个局部极小点，第二阶段填充函数算法是填充阶段，在局部极小点 处构造填充函数，并极小化填充函数，得到的一个新极小点；割峰函数算法是利用 辅助函数去除比极小点函数值高的点，进一步极小化辅助问题，得到一个新的极小 点；“s t r e t c h i n g ”函数算法是通过“s t r e t c h i n g 函数提高目标函数高于局部极小点的函 数值，而后将局部极小值点及其邻域内的点整体向上拉伸后，局部极小化“s t r e t c h i n g ” 函数，得到一个新极小点。 本文在研究现有确定型算法的基础上，提出一些改进和创新，并对算法进行数 引言 值实验，在算法效果方面有所提高。主要研究内容如下 ( 1 ) 介绍全局优化问题基础知识及现有的算法，分析了常用的几种求解全局优 化问题的典型算法。 ( 2 ) 构造了一个新的求解一般无约束优化问题全局最优解的一个填充函数，从 而得到了填充函数算法，并给出了算法的数值试验的结果。 ( 3 ) 研究了割峰函数算法和“s t r e t c h i n g ”函数算法，利用改进的割峰函数和更易 于实现的光滑技巧构造了新的辅助函数。 2 青岛大学硕士学位论文 第一章全局优化问题及其算法 1 1 预备知识 全局优化问题一般考虑的问题【1 】 m i l l 厂o ) 1 一( 1 ) s 1 x x 其中xc 彤是可行域，：彤- 只是目标函数。 从各种各样实际模型出发，常见的全局优化问题主要有以下几种情况。 无约束全局优化问题 m i l l ，o ) 1 一( 2 ) s j x r “ 闭箱约束全局优化问题 m i n 厂o ) 1 - ( 3 ) s j x e x - 仁e r “l l js z ，“，j - 1 , 2 ，托) 线性约束全局优化问题 m i n ，o ) 1 一( 4 ) s j x e x ( x 是一个多面体) 一般地，称问题1 ( 1 ) 为原问题。 定义1 1 1 至少存在一个点x e x 使得对于任意x x 都有f ( x ) s 厂o ) 成 立，或能够证明这种点不存在性，称这样的问题为全局极小化问题。如果x 存在， 则称其为原问题1 一( 1 ) 的一个全局极小点，称对应的函数值f ( x ) 为函数f ( x ) 在z 上的全局最优值( 全局解) 。如果对所有x x rx e x ，有f ( x ) ，o ；) ，则称在五处的盆谷噬比i 处的盆谷茸低，或称盆谷研比盆谷e 高。 定义1 2 4 1 称函数f ，葛) 为，o ) 在局部极小点的填充函数，指f o ，i ) 满 足以下三个条件： ( 1 ) i 是f ，i ) 一个局部极大点， ) 在点i 的盆谷研为f ( x ，i ) 的波峰的一 部分； ( 2 ) f 0 ，i ) 在比研高的盆谷罩没有稳定点： ( 3 ) 如果存在比研低的盆谷或，则存在i 耳，使f o ，i ) 在i 和i 的连线上有 稳定点。 一般情况下，填充函数法都要求假设厂o ) 的局部极小点或局部极小值的个数是 有限的。 填充函数算法的基本思想是：首先，极小化阶段，采用局部优化方法寻找f ( x ) 的一个局部极小点；其次，填充阶段，在i 处构造填充函数f o ，i ) ，使其在某 个比葛所在盆谷低的盆谷中有一个极小点或者鞍点i ，然后以i 为初始点极小化 厂o ) ，得到f ( x ) 的一个新极小点五，使得，( i ) ，“) ，再用蔓代替，重复上 述过程，直到找到厂o ) 的全局极小点。 填充函数法的关键是如何构造填充函数，而填充函数的定义4 中条件( 3 ) 是一个 比较弱的条件，很多研究者都对此做了改进。 r g e 最早定义的是一个双参数的填充函数 机加去p 扣硎2 ，p 2 这个填充函数存在较大的两方面缺陷：一是算法的成功与否，严重地依赖这两 个参数，而且在算法执行之前我们不知道这两个参数的合适取值，只有多次的实验 才有可能找到较好的选择；二是受指数项e ” 的影响，当参数pp 太小或者 k j 带2 i x - - i i l 太大时，f ( x ，i ，r ，p ) 和v f ( x ，i ，p ) 几乎不发生变化，从而出现假的平稳点。 7 第一章全局优化问题预备知识及算法概述 为了克服这些缺陷，g e 和q i n 后来在文献n 订中进行了改进，并给出了七个不同的填 充函数。 砘。m ) | 一1 唧( - 守 g g ，x ：，驴) 一p 2 l 。gd + 厂g ) 】一0 x - x ：i | 2 占g ，x 妒) z p 2 - 。gd + ，g ) 一i i x - x ；i i q g ，工：，彳) 一一 ，g ) 一，( x ：冰x p ( 彳i l 善一石：1 1 2 ) 直x , x ：，彳) 。一【，x ) 一，k ：灌x p0 c ) k ，薪，彳) - 一可g ) 一砧仁) 一厂k 戕一毫) v k ，彳) 一一v 1 ( x ) 圳 ，g ) 一厂忱。翰l f , - x ；! z h a n g 等在文献n 们中对填充函数定义进行了改进，并给出了一个性质较好的函 数： f ( x ，i ，p ，比) - ，“) 一m i n 【，o ) ，g ) 卜j d 忙一i 8 2 + 口 m a x o ，厂o ) 一，g ) 】 2 l i a n g 等在文献啪1 中给出了一种更易于算法实现的单参数填充函数： f ( x ，x ，p ) 一一忙一硎24 p m i n 【0 ，o ) ，“) 】) 3 并详细的讨论了该填充函数的搜索方法。 上述列举的填充函数，还只停留在解决无约束全局优化问1 ( 2 ) 或者闭箱约 束全局优化问题1 ( 3 ) ，还不能直接解决如下一般的不等式约束的全局优化问题： r a i n ，o ) 1 ( 5 ) s j g i o ) s0 i ，1 ，2 ，m x x 其中厂：xi r 和g ，：x r ，i t 1 2 ，m 是连续可微的，x 是一个闭箱约束。 w u 在文献乜3 1 中对问题1 ( 5 ) 进行了分析研究，利用罚函数和分段函数思想构 青岛大学硕士学位论文 造了一个新的填充函数： p ，c ，- 彳。) 。币7 二打，c ( g ，( 厂( 工) 一，( i ) ) + 薹g r ，q ( g t ( 工) ) 一2 ，) 其中 f c o ) 一 g ，o ) 一 c，t0 一2 ，c j t 3 3 ，c z - f 2 + c ，一，fs 0 0t-r t+2t芝0 r 广- 4 t a + 2 r 厂- 。6 - t 2 + t + 2 ，一r 墨f s0 0 t 墨- r 二，g , q 幢o ) ) 是填充函数的用来惩罚不可行点的惩罚项。w u 还讨论了 p 0 ) 的一些解析性质，并给出了一种新的填充函数算法，并通过数值实验表明 _ 一, x l 其算法在解决问题1 ( 5 ) 时是有效可行的。 填充函数法的长处在于算法的设计和执行简单易行，并且它较多地运用了目标 函数的性质，因此收敛速度比较快；缺点在于目前，所有的填充函数对未知参数都 有这过高的依赖性，所以为确保能找到满意的全局最优解，要经大量的实验，来确 定参数的取值范围，从而增加了算法设计之前的工作量，另外填充函数利用的是线 搜索方法，因此对搜寻低盆谷的点也有很大难度。 9 第二章一个新的填充函数算法 第二章一个新填充函数算法 本章主要讨论求解无约束全局优化问题的填充函数算法。给出了一个求解一般 无约束优化问题全局最优解的新的填充函数，分析了此填充函数的性质，并给出了 可行的填充函数算法。对此方法的数值试验表明所给的算法是有效可行的。 考虑一般的无约束问题1 ( 1 ) 为了用填充函数法求解问题的全局最优解，我们做如下假设： ( 1 ) ，o ) 在彤上连续可微； ( 2 ) n l k l l - - + 时，o ) 一+ o o ； ( 3 ) 假设全局优化问题的局部极小点构成的集合l ( p ) 内元素的个数为有限的。 由如上假设我们可推知，一定存在一个紧集xc 彤，它的内部包含了厂o ) 的 所有全局极小点和函数值较小的局部极小点，而且可以认为目标函数在x 边界上的 函数值大于其内部的函数值，因此上述数学规划问题等价于下面的闭箱约束问题 1 - ( 2 ) 。 定义【2 1 1 函数m ，工，留，) 称为函数，( x ) 在局部极小点工处的填充函数，如果 e ( x ，z ，q ，) 满足以下条件： ( 1 ) 工是e ( x ，z ，口，) 的局部极大点。 ( 2 ) 若x s 1 ，其中s l 一协xi ，o ) f ( x ) ，x x ，则v p o ，z ，口，r ) 一0 ( 3 ) 若s ：一 x e r “：厂o ) f ( x ) ) 非空，贝l jp ( x ，x ，q ，) 在是上存在局部极小点 。 2 1 填充函数 我们利用填充函数法求解问题1 - ( 2 ) ，为保证填充函数的近似程度，以及参数的 更以调整，给出厂( x ) 在局部极小点工处的新的填充函数如下： p ( z ，工+ ，q , r ) 。一i p z 0 2 - - l n o + q m a x ( f ( x ) 一f ( x ) ，o ) ) + ，m i n ( 0 ，( x ) 一f ( x ) ) 3 其中，0 q 0 是两个参数，l ( p ) 表示问题( p ) 的极小点集合，o ) 及 1 0 青岛大学硕士学位论文 v f ( x ) ：i ! e r “上是李普希兹连续的，即x ，y 彤，z - y ，存在b 使得 i i v i x ) - v i 0 ) ，且 对于所有的z d ，口+ ) ，有， 。) sf ( x ) ，故 即，x ， ) - 一肛- - x 卜2 l n o + 留( 厂o ) 一f ( x ) ) 0 一m ，工，) 故工p ( x ，x ，q ，r ) - - 个局部极大点。 定理2 设s o xi 厂o ) 之厂o ) 工一x ，若x s ，o q 2 k ，则 v p ( x ，x ，q ，厂) 一0 。 证明由x 墨，故即，工+ ，g ，r ) 一一i i x x 0 2 - - l n ( 1 + g ( ， ) 一( x ) ) ，从而有 v p ( x ，工，q ，) 一一2 ( x 一工) 一 此外x l ( p ) ，故w o ) t0 ，由此知 q v f ) 五而两而 毗工忍，) i 乏) - 器黼 且 眺z忍r)r商l_2iij|-瓣q(vf(x)-vf(x)网x-x 丸i i x - xl l + 熟 , 2 1 k - x f i + 嘞卜x 8 一( 一2 + 嘲) 忙一z | f o , s t - x e x ，厂o ) - 厂“) + 占 c i n t x ，其中 对所有x e s 有 ，g ) - f ( x ) f ( x ) - f ( x ) 一厂g ) + 占一厂o ) o 成立，对x s 。以下两种情况： ( 1 ) 忙一x 忙i x - - x 。0 ( 2 ) 忙一工+ z 0 8 当0 i x i i 之b - x 0 时，由f ( x i ) - f ( x ) ，o ) 一f ( x ) 一，“) + - f ( x ) o 和 i x ：- x 工。悄 p g ，z ，旷) - 一l k 一工1 1 2 + r ( ，g ) 一f ( x ) ) 3 卜z | 1 2 - l i o l l 2 ( f ( x ) - f ( x ) ) 3 一( 厂g ) 一f ( x ”3 碉 i i 工- x 1 1 2 _ 忙一x i | 2 厂“厂 ) 一f ( x ”3 一( ，“) 一f ( x ) ) 3 ) 所以有 一忙一工| 1 2 + ，( ，k ) 一f ( x ) ) 3 一i i x - - x * n ，( 厂o ) 一f ( x ) ) 3 即p ( i ，x ，q ，) 0 ， 一 童璺奎堂堕主堂堡垒窒一 一_ _ _ _ _ 一。 又因为s 八s 。是一个开集，所以x oe s ：s ，ci n t x 是跑，x ，鼋，) 的一个局部极 小点，并且有卯瓴，工，留，r ) - o 由定理2 知，瓯) 0 。其中，m 是一个小的正数，弘是一个较大的正数， 给定任意初始点，七1 0 步1 以h 为初始点，求问题( p ) 的局部极小点工：+ i ，七i 七+ 1 。 步2 由工：构造填充函数 e ( x ，l ，口，厂) ；一忙一0 2 一h l ( 1 + q m a x ( f ( x ) 一，“) ，o ”+ 厂m i n ( 0 ，厂o ) 一厂“”3 ， f | 1 步3 以# 。+ 甜。为初始点，求填充函数p o ，g ，r ) 的局部极小点，在极小 化过程中，若找到霉，使厂 ) 厂“) ，以蓦置转步1 ；否则，执行步4 步4 若f 知，则f 一i + 1 ，转步3 ：否则执行步5 步5 若g ，执行步6 ，否则，若g 坍，g ：= q l o ，若厂s ，| 1 0 厂， 转步2 步6 停止，把取做问题1 - ( 1 ) 的全局最优解 注：步0 中d 集合，也可以利用随机产生现在用以上的算法，对以下几个常见 的非线性规划问题进行数值试验，通过计算来说明本文所给出的填充函数算法的有 效性。 1 3 第二章一个新的填充函数算法 2 3 数值实验 下面给出四个常用数值算例，对以上新填充函数算法进行数值试验。每个问题 的计算结果都有表格给出，表格中的符号表示如下： 我们试验中取历i i i i b1 0 - 6 ，一1 0 加，令q - 1 ，r - 1 0 0 ，口一0 0 5 。 ：给定的初始点； k ：找到第k 个局部极小点的迭代次数； + ：第k 个局部极小点； ，瓴) ：第k 个局部极小点的函数值； 例l t l f ( x ) m 4 x 一2 1 x ：+ x ? 3 + x , x 2 4 x ；+ 缸；，( 一3 s 而，工2s3 ) 这个函数的全局最优点及最优值分别为 z - ( 0 0 8 9 8 , 0 7 1 2 7 ) 或( 一0 0 8 9 8 , 0 7 1 2 7 ) ，厂- 一1 0 3 1 6 而利用本文所给算法得到其迭代步骤见表2 1 。 表2 h x o - ( 2 ，2 ) k 厂瓴) 例2 7 1f ( x ) - x ? + 工；一c o s ( 1 s x , ) 一c o s ( 1 8 x 1 ) ，( - 3 ：x 1 ，x 2s3 ) 这个函数大约有5 0 个局部极小点，全局最优点及最优值分别为 戈一( 0 ，0 ) ，一一2 而利用本文所给算法得到其迭代步骤见表2 2 。 表2 2 - x o - ( 0 5 ，1 0 ) k x ： fb ：、 1 4 青岛大学硕士学位论文 1 0 e - 0 0 9 - 0 5 7 1 0 7 4 4 2 9 8 5 7 5 6 ) 例3 t t e c c a n i 函数 z 限o ) - + 4 + 4 彳+ 其中一3 毛墨3 ，一3 x 2s 3 。这个函数有2 个局部极小值点，同时也是全局极 小点是( 2 ，o ) 和( 0 ，0 ) ，全局极小值是。而利用本文所给算法得到其迭代步骤见表2 3 。 表2 3 z 工。一( - 1 6 , 0 5 ) k 厂瓴) 例4 t h r e e h u m pc a m e l b a c k 函数 厶( 工) 一2 砰一1 0 5 x a 4 + x a 6 6 一啦+ 其中一3 s s3 ，一3 一 其中，c ( ，) 是关于已知参数，的正纯量。 注：事实上，厂和c ( ，) 可以认为是根据需要已经给定的与x 耻无关的常数。 性质3 1 1 【徊对于任意x x ，有不等式，o ) 一c ( ，) sl u ( r ，x ( ，工) s 厂o ) 成 立。 在应用割峰函数时候，为保证数值的精确性，c ( ，) 应选取适当的小。这是因为 由性质3 1 1 有0s 厂o ) 一l u ( r ，x ( 1 0 , x ) c ( r ) 成立，这意味着割峰函数肛( ，x ，x ) 在 x ( ) 处截原目标函数f ( x ) ，且其截断误差不超过c ( ，) 。 考虑如下的方法来构造割峰函数： z ( r ，z ，x ) = ，o ) 一兀( ，- ，卜工0 ) 其中a ( r ，) 满足如下三个条件： ( 1 ) 从尺+ 到j 5 c + 的函数f o ( r ，) ，是严格单调递增； ( 2 ) ，o ( ，o ) 一0 ； 1 8 青岛大学硕士学位论文 ( 3 ) l ( r ，) 有上界，即旦巴厶( ，f ) c ( ，) + 。 定义3 1 2 称，( 厂，z i ，工) 一r a i n ( f ( x ) ，l ( ，石，z ”为( x ) 在点x 的辅助函数。 由定义3 1 2 ，我们可以得到问题1 ( 3 ) 在点x ( 处的辅助极小化问题： m i nf ( r ，工，x ) 3 ( 1 ) s j x x 定义3 13 【锎给定点z ( ，称x o ) 一 x l u ( r ，工( ，x ) 一， ) ) 为问题3 ( 1 ) 的下 降区域。 不难证明，辅助函数，( ，工，x ) 有如下性质： 性质3 i 2 对任意给定的点工，对于城x 且x - 工n ，有f ( ，工，x ) 厂g ) 成立，即x 为，( ，工，x ) 的全局最大值点。 性质3 1 3 【侧若石一石( 且f ( r ，z ，工) - ，o ) ，则有厂 ) ，o ) 成立。 引理3 1 1 【侧假设x ( 不是问题1 ( 3 ) 的一个全局极小点。若给定一个初始点 i x ，辅助极小化问题3 ( 1 ) 的一个局部极小点x ( m 能够得到且有 f ( r ，工，x + 1 ) 一f ( x 雠+ 1 ) 成立，贝0 ( x + 1 ) f ( x 七) 。 定理3 1 1 i 蛔设x + 是问题3 ( 1 ) 的全局极小点，若厂o ) 在紧集x 上是连续可 微的，且局部极小点的个数是有限的，又对于任意一个局部极小点) 一工，存在 难i n t x ( x ) ，使得搜索方向： 甬印，卜划i 一 其中，e 一乜i i - 1 , 2 , ，朋) ，q 为单位径向。 则由割峰函数算法得到的解一满足os ，“) 一f ( x ) sc ( 厂) ，其中c ( r ) 是割峰函 数的最大割。 由于辅助优化问题3 ( 1 ) 的目标函数，在目标函数，o ) 和割峰函数“( r ，工，工) 第三章割峰函数法和“s t r e t c h i n g ”函数法 的交点处是不可微的，因此求接下来的解不能直接利用基于梯度的最优化算法。 w a n g 在文献【4 6 i 中用了如下光滑技巧： e ( 厂，工( ，石) 一l l o g e 。o ) + e 严( ，一，】 p 其中，p 是一个正参数。显然，函数( 厂，x n ，x ) 也是连续可微的，当原目标函数f ( x ) 和割峰函数u ( r ，x ( t ) ，石) 在可行域x 上都是连续可微的。 定理3 1 2 函数f p ( r ，工，x ) 收敛于函数f ( r ，工n ，x ) ，当参数p 呻时。 由定理3 1 2 可知，当正参数p 的选择适当大时，问题3 ( 1 ) 可以近似为下面 的可微全局优化问题： r a i ng ( r ，z n ，工)3 - ( 2 ) s j x x 文献【4 7 1 中给出了利用以上光滑技巧构造的割峰函数算法及其数值实验，从数值 效果和迭代次数上与几种经典的填充函数都做了比较，结果显示割峰函数法在求解 闭箱全局优化问题时有更好的效果。 3 2 “s t r e t c h i n g 函数算法 3 2 1 “s t r e t c h i n g 函数及其性质 设点x 是问题1 ( 3 ) 的一个局部极小点，第一步构造“s t r e t c h i n g 函数1 5 0 1 ： g o ) - 厂o ) + 鲁忙一x l l o i g n ( f ( x ) 一厂o + ) ) + 1 ) 3 ( 3 ) 其中 、6 是正常数，r s i g n ( ) 是三值符号函数。 一 兰 州5 ， 青岛大学硕士学位论文 当前的局部极小值f ( x ) 高的区域提高了，从而消除了比局部极小点高的所有局部 极小点，但不影响求值结果；第二阶段利用3 - ( 4 ) 使局部极小点x 成为e o ，工) 的 最大点。并且在x 附近形成一个较为陡峭的坡，也即e o ，工。) 在这一区域内存在比x 更低的点。 3 2 2 “s t r e t c h i n g 函数算法描述 以下是“s t r e t c h i n g ”函数算法的步骤： 步o 在可行区域x 中产生一点x o ，给定初始迭代次数七一0 ，预先给定算法中 的算法的最大迭代次数k 和参数 ，6 。 步l 从以开始，用下降搜索方法极小化目标函数f ( x ) ，得到f ( x ) 的一个局部 极小点x 。 步2 根据3 - ( 3 ) 和3 ( 4 ) 构造辅助函数e o ，工) 。 步3 从x 附近的一点i 开始极小化辅助函数e ( x ，x ) 。如果得到一个稳定点t ， 则令以i z ，；如果在极小化辅助函数的过程中存在一点满足f ( x ) ，何) ，则令 磁一x 。 步4 若k k ，令k 一k + 1 ，转步1 ：否则把坼作为目标函数的全局最小值， 停止。 现在为清楚地解释和比较以上两种辅助函数的作用效果，我们对以下二维函数 分别利用二者进行作用，并以三维图展示如下： 考虑二维测试函数l e v y n o 5 ： ，o ) 。善c o s 【( f + 魄+ f 】荟j c o s 【( j + 1 ) x 2 + ，】+ “+ 1 4 2 5 1 3 ) 2 + 化+ o 8 0 0 3 2 ) 2 ， 其中一1 0 x ；s 1 0 ，f 1 2 。它大约有7 6 0 个局部极小点和一个全局最小点 x 一( 一1 3 0 6 8 ，一1 4 2 4 8 ) ，全局最小值为f ( x ) 一一1 7 6 1 3 7 5 。图3 1 是函数l e v yn o 5 2 1 r 第三章割峰函数法和“s t r e t c h i n g ”函数法 的原始图。 青岛大学硕士学位论文 利用割峰函数，对l e v yn o 5 作第一步变换后形成的函数如图3 3 所示。我们 可以看到，比局部极小点函数值高的点消失了，然而比局部极小点低的点和全局极 小点没有受到影响。 图3 3 2 利用“s t r e t c h i n g 一函数，再对l e v yn o 5 作第二步变换得到的函数如图3 3 所示。 它很清楚地显示了除当前所得到的局部极小点的某一邻域外，其它区域被整体降低 了，从而形成下降斜坡来实现下一步的极小化过程。 o 锄 仰 伽 和2 第三章割峰函数法和“s t r e t c h i n g 函数法 2 图3 4 通过以上对比，我们可以比较直观地看出两种算法实现过程的基本思想是一致 的，那就是都是首先去除比当前极小点处函数值高的点，然后割峰函数算法是通过 光滑技巧来实现下一步的极小化过程，而“s t r e t c h i n g 函数算法则是通过压低当前极 小点以外的点的目标函数值，从而形成下降斜坡来实现下一步的极小化过程。 综合对两种