（应用数学专业论文）非线性全局优化的辅助函数方法.pdf

内容摘要最优化是- - f 应用相当广泛的学科，它讨论决策问题的最优选择，构造寻求最优解的计算方法并研究这些方法的理论性质及实际计算表现。最优化理论和方法的出现可以追溯到十分古老的极值问题，然而，它成为一门独立的学科还是在上世纪四十年代末，是由线性规划问题的创始人一美国人g b 丹齐克( d a n t z i n g ) 在1 9 4 7 年提出求解一般线性规划问题的单纯形算法之后。随着社会的进步和科学技术的发展，至今短短的几十年，最优化问题得到了迅猛的发展。现在，解线性规划、非线性规划以及随机规划、多目标规划等各种最优化问题的理论研究发展迅速，新方法不断涌现。在经济计划、工程设计、生产管理、交通运输、国防军事等重要领域得到了广泛的应用，成为了一门十分重要的学科。全局最优化是最优化的一个重要分支。相对于线性规划等其它的分支，它的理论和计算方法远没有那么成熟、完善。但是现实社会中的许多问题都与非线性全局最优化问题密不可分，所以全局最优化工作者利用不同的数学理论和工具，提出了各式各样的算法。例如：在函数变换的基础上，提出了填充函数方法；在非线性方程理论的基础上，提出了打洞函数方法；在微分方程动力系统的基础上，提出了动力打洞函数方法；在积分原理的基础上，提出了积分水平集方法；在组合理论的基础上提出了分支定界算法；在随机和启发式基础上提出了模拟退火法、遗传算法等等。这些理论和算法虽然都具有强大的生命力，但许多方法还需要迸一步的完善和深化。伴随着计算机的高速发展和最优化工作者的努力，非线性全局最优化的理论分析和计算方法得到了极大提高。尤其是在上世纪七十年代，随着两个文献| 6 2 ，6 3 】的出现，全局最优化的方法得以大量的涌现。从算法的构造上，全局最优化算法大体可以分为两大类：确定型算法和随机算法。其中的填充函数法和打洞函数法属于确定型算法；模拟退火法、遗传算法属于随机算法。由于填充函数法和打洞函数法等都是利用一个辅助变换函数来实现求全局极小点的过程，所以，我们把它们统称为辅助函数方法。这篇文章的主要工作是研究非线性全局最优化的辅助函数法。全文共分六章。第一章简述了全局最优化问题以及目前国内外几种主要的全局最优化方法。第二章对连续全局最优化的情况，改进了早期文献f 3 1 1 中的定义，在文献 1 2 0 1 的基础上，设计了一个新的填充函数( 见文献 9 1 1 ) ，该填充函数不仅只有【一个参数，而且优化了文献【1 2 0 】中给出的算法，克服了文献 a 2 0 算法的不足之处。第三章，首先回顾了文献 1 3 5 1 中给出的整数规划问题的填充函数定义，然后在文献 1 2 9 1 和1 1 3 5 的基础上，构造了一个满足该定义的只含一个参数的填充函数，该函数不带指数项，而且在实际计算的时候，比文献【1 3 5 】中提出的函数要更有效，尤其是对高维的情况。第四章对尼空间箱子约束连续全局优化问题，给出了个新填充函数定义，设计了一个全局优化算法，并且还进行了数值计算。第五章是对第四章的一个拓广，核心内容是将箱子约束连续优化的填充函数理论和算法拓宽到整个j p空间中。讨论了尼z 空间上的带不等式约束的非线性全局规划问题的填充函数理论和算法。第六章讨论了箱子约束非线性整数规划的打洞一填充函数。文献i l l s 在连续全局优化问题中，讨论了填充函数与打洞函数的统一问题，并且给出了打洞一填充算法。本章在文献 a 3 s 的基础上，对箱子约束非线性离散全局优化问题，提出一个新的同时具有打洞性质又具有填充性质的函数形式，讨论了它的有关性质，设计了一个打洞一填充算法，并进行了数值计算。关键词全局最优化，非线性规划，非线性整数规划，局部极小点，全局极小点，填充函数，填充函数方法，打洞函数，打洞函数方法，打洞一填充函数。i ia b s t r a c tm a n yr e c e n ta d v a n c e si ns c i e n c e ，e c o n o m i c sa n de n g i n e e r i n gr e l yo nn u m e r i c a lt e c h n i q u e sf o rc o m p u t i n gg l o b a l l yo p t i m a ls o l u t i o n st oc o r r e s p o n d i n go p t i m i z a t i o np r o b l e m s g l o b a lo p t i m i z a t i o np r o b l e m sa l - ee x t r a o r d i n a r i l yd i v e r s ea n dt h e yi n c l u d ee c o n o m i cm o d e l i n g ，f i n a n c e ，m a n a g e m e n t ，n e t w o r k sa n dm e c h a n i c a ld e s i g n ，c h e m i c a le n g i n e e r i n gd e s i g ne n dc o n t r o l ，m o l e c u l a rb i o l o g y , a n de n v i r o n m e n t a le n g i n e e r i n ga n ds oo n d u r i n gt h ep a s tf o u rd e c a d e s ，m a n yn e wt h e o r e t i c a l ，a l g o r i t h m i c ，a n dc o m p u t a ，-t i o n a lc o n t r i b u t i o n sh a v eh e l p e dt os o l v eg l o b a lo p t i m i z a t i o np r o b l e m sa r i s i n gf r o mi m p o r t a n tp r a c t i c a la p p l i c a t i o n s t h ea u ) 【i n a r yf u n c t i o nm e t h o d s ，i n c l u d et h ef i l l e df u n c t i o nm e t h o d s a n dt u n n e l i n gf u n c t i o nm e t h o d sa r ea m o n gt h ec o n t r i b u t i o nl i s t t h ef i l l e df u n c t i o na n dt h ef i l l e df u n c t i o nm e t h o dw a sf i r s tp r o p o s e db yr e n p ug ei nt h e1 9 9 0 s 3 1 】i t sb a s i ci d e ai sb yc o n s t r u c t i n ga u x i l i a r yf u n c t i o n s ，n a m e l yt h ef i l l e df u n c t i o n ，t of i n dg l o b a ls o l u t i o n so fo r i g i n a lo b j e c t i v ef u n c t i o ns t e pb ys t e p t h et u n n e l i n gf u n c t i o na n dt u n n e l i n gf u n c t i o nm e t h o dw a sf i r s tp r o p o s e db ya v l e v ya n da m o n t a l v oi nt h e1 9 8 5 s 2 】_i nr e c e n ty e a r s ，m a n yk i n d so ff i l l e df u n c t i o n sw i t hp a r a m e t e r sh a v eb e e np r e -s e n t e d h o w e v e r ，t h o s ep a r a m e t e r sa r et o oh a r dt oa d j u s ta n di t i sm o s tp r o b a b l et h a tg l o b a lo p t i m i z e r sa r el o s to rf a k eb e t t e rm i n i m i z e r sa r ef o u n d t h e r e f o r e ，h t r -t h e rr e s e a r c hi sw o r t h yo fc o n t i n u i n go nh o ww ec a nc o n s t r u c tf i l l e df u n c t i o n sw i t hs i m p l e rf o r m s ，b e t t e rp r o p e r t i e sa n dm o r ee f f i c i e n ta l g o r i t h m s t h i sd i s s e r t a t i o nm a 自u l yc o n c e r n st h em o d i f i e d 锄e df u n c t i o nm e t h o d sa n dt u n n e l i n gf u n c t i o nm e t h o d sf o rn o n l i n e a rg l o b a lo p t i m i z a t i o np r o b l e m s i tc o n s i s t so fs i xc h a p t e r s i nt h ef i r s tc h a p t e r ，g l o b a lo p t i m i z a t i o np r o b l e m sa n ds o m eo fi t sm a i nm e t h o d sa r eb r i e f l yi n t r o d u c e d i nt h es e c o n dc h a p t e r 。t h ed e f i n i t i o no ft h em l e df u n c t i o nf o rc o n t i n u o u sg l o b a lo p t i m i z a t i o ni np a p e r 3 1 】i sm o d i f i e da n dan e wf i l l e df u n c t i o ni sp r e s e n t e d ，an e wf i l l e df u n c t i o nw i t ho n ep a r a m e t e ra r er e q u i r e dt oh a v el o c a lm i n i m i z e r si n s t e a do fb e i n gm i n i m i z e do nt h el i n es e g m e n t ，w h i c hi sv e r yi m p o r t a n ta n dm e a n i n g f u lt or e a c hag l o b a ls o l u t i o ns u c c e s s f u l l y i nc h a p t e rt h r e e ，ad e f i n i t i o ni i io ft h ef i h e df u n c t i o nf o rn o n h n e a ri n t e g e rp r o g r a m m i n gp r o b l e m ，w h i c hi sm o d i f i e df r o mt h a to ft h eg j o b a n yc o n v e x i z e df i l l e df u n c t i o ni np a p e r 3 3 1 ，i sg i v e n af i l l e df u n c t i o ns a t i s f y i n gt h ed e f i n i t i o ni sp r e s e n t e d ，w h i c hi sm o d i f i e df r o mt h a to ft h eb o xc o n s t r a i n e dc o n t i n u o u sg l o b a lo p t i m i z a t i o n 1 2 9 ja n dd i f f e r e n tf r o mp a p e rf 1 3 5 j t h ep r o p e r t i e so ft h ep r o p o s e df i l l e df u n c t i o na n dt h em e t h o du s i n gt h i sf i l l e df u n c t i o nt os o l v en o n l i n e a ri n t e g e rp r o g r a m m i n gp r o b l e ma r ea l s od i s c u s s e di nt h i sc h a p t e r i nc h a p t e rf o u r ，ad e f i n i t i o no ft h ef i l l e df u n c t i o nf o rt h eb o xc o n s t r a i n e dg l o b a lo p t i m i z a t i o np r o b l e mi n 彤i sg i v e n t h e naf i l i e df u n c t i o nm e t h o df o ro b t a i n i n gag l o b a lm i n i m i z e ro ft 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 mi sp r e s e n t e d ag e n e r a lf o r mo ft h ef i l l e df u n c t i o np r o p o s e di nt h ef o u rc h a p t e ri sp r e s e n t e di nt h ef o l l o w i n gc h a p t e r i nc h a p t e rs i x w ei n t r o d u c ean e wb ff u n c t i o nf o rs o l v i n gd i s c r e t eg e n e r a lm i n i m i z a t i o np r o b l e m sw i t hag e n e r a lf u n c t i o no v e rb o x - c o n s t r a i n e dd o m a i n at -ff u n c t i o ni sc o n s t r u c t e da tal o c a lm i n i m i z e ro ft h eo b j e c t i v ef u n c t i o ns u c ht h a ti ta c h i e v e sl o c a lm a x i m u ma tt h ec u r r e n ts o l u t i o n m o r e o v e r ，al o c a lm i n i m i z e ro ft h et - ff u n c t i o nl e a d st oan e ws o l u t i o nt ot h eo r i g i n a lp r o b l e mw i t hl o w e ro b j e c t i v ef u n c t i o nv a l u e i t e r a t i o nf o l o w si nt h i sm a n n e rt or e a c hag l o b a lm i n i m i z e r p r o m i s i n gc o m p u t a t i o n a lr e s u l t sa r ei n c l u d e da n ds h o wt h ee f f i c i e n c yo ft h et - ff u n c t i o nm e t h o d k e yw o r d s ：g l o b a lo p t i m i z a t i o n ，n o n l i n e a rp r o g r a m m i n g ，l o c a lm i n i m i z e r ，g l o b a lm i n i m i z e r ，f i l l e df u n c t i o n ，f i l l e df u n c t i o nm e t h o d ，t u n n e h n gf u n c t i o n ，t u n n e l i n gf u n c t i o nm e t h o d ，t - ff u n c t i o n i v同济大学博士后研究论文第一章最优化问题概述及基础知识1 1最优化问题概述最优化是一门应用性很强的学科。简单地讲，它研究某些用数学模型表述的问题，并求出其最优解，即对于给出的实际问题，从众多方案中选出最优方案。具体来说，它讨论决策问题的最佳选择之特性，构造寻求最佳解的计算方法，研究这些计算方法的理论性质及其实现。虽然最优化可以追溯到古老的极值问题，然而它成为一门独立的学科是在上世纪4 0 年代末，在1 9 4 7 年d a n t z i g 提求解一般线性规划问题的单纯形法之后。现在，对线性规划、非线性规划以及随机规划、非光滑规划、多目标规划、几何规划、整数规划等各种最优化问题的理论研究发展迅速，新方法不断涌现，实际应用日益广泛。最优化理论和方法在自然科学、经济计划、工程设计、生产管理、交通运输、国防等重要领域，已受到政府部门、科研机构和产业部门的高度重视，成为一门十分活跃的学科。伴随着计算机的高速发展和优化计算方法的进步，规模越来越大的优化问题可以得到解决。最优化作为应用数学领域的重要组成部分，它研究的阅题广泛见于自然科学、金融经济、工程设计、生产管理、网络交通、农业预测、国防军事等重要领域。因此受到高度重视。最优化包含很多分支，如线性规划、非线性规划、组合优化、多目标规划、随机规划等等。本论文主要讨论非线性规划中全局优化问题。非线性规划被用来识别和计算多个变量的非线性函数的最优解。如果这些变量受到一些条件的限制时，称其为约柬最优化问题；如果交量可以自由变动不受约束的限制，则称其为无约束最优化问题。最优化问题的般表达形式为， 咖m ) ，( 1 1 1 )【8 t z 义其中z j 矿是决策变量， ) 为目标函数，xcj 护为约束集或可行域。特别地，如果约束集x = r “，则最优化问题( 1 1 1 ) 称为无约束最优化问题：枷m i n 。他)1( 1 1 2 )同济大学博士后研究论文约束最优化问题通常写为：im i n ，( z ) ，p 国= 0 晒e( 1r 1 3 )i吼( z ) 0 ，i i 这里e 和，分别是等式约束的指标集和不等式约束的指标集，鲰( z ) 是约束函数。当目标函数和约束函数均为线性函数时，问题( 1 1 3 ) 称为线性规划。当目标函数和约束函数中至少有个是变量x 的非线性函数时，问题( 1 1 3 ) 称为非线性规划。此外，根据决策变量、目标函数和要求的不同，最优化还分成了整数规划、网络规划、非光滑规划、随机规划、几何规划、多目标规划等若干分支。本论文主要研究求解无约束全局优化问题( 1 1 2 ) 的理论和方法。从形式上我们已经区别了无约束最优化问题和有约束最优化问题，下面我们将给出鳃的精确定义以区分全局极小点和局部极小点。为方便统称问题( 1 1 2 ) 和问题( 1 1 3 ) 为原问题定义1 1 1 至少有一个茁玉x 使得v x x 有f ( x ) 之， 各) ，或证明这种点不存在，这样的问题称为全局极小化问题令”| j 代表尼中的e u c l i d e a n 范数，则有定义1 1 。2 设矿x ，如果( x ) ，( 矿) ，x ( 1 1 4 )成立，则称矿是问题一j ，的全局极小点如果对所有z 善+ 和矿x ，f ( z ) ，( 矿) 成立，则称矿为p j 砂的严格全局极小点定义1 1 3 设矿x ，如果对莱一j o 和z 的邻域o 往，6 ) = 扛酽：忙1 | b + ) 戍互，灿稳矿为 i ，l ，i ) 的严格局部极小点关于算法的搜索方向有下面的定义定义1 1 4 设z o x ，若有方向d 舻且d 0 使得d r y f ( 2 ；o ) 0 使得对所有的o ( o ，咖) 成立z o + a d x ，则称d 为o o 处的可行方向2同济大学博士后研究论文另外有定义定义1 1 5 对于函数，( z ) ，若有单变量函数( t ) 使得【，( z ) 】改变了，( z ) 的函数形态和性质，则称【，q ) 】为，( $ ) 的变换函数下面我们将分别介绍已经存在的全局优化问题的一些算法。由于科学和工程等领域所需要解决的问题大都可以归结为求全局解的问题，从而促使过去三、四十年里，关于全局最优化的理论和算法层出不穷。由于很可能在一个全局优化问题里有许多局部极小点，因此全局优化问题不能简单的用通常意义下的求解目标函数局部极小的方法。这些多极小值点的函数一般会导致两个比较困难的问题：一个是怎样离开一个局部极小值点到一个值更小的极小点；第二个是怎样判断当前的极小值点是否为全局最优解。现在有很多方法研究解决第一个问题，而第二个问题一全局最优性条件的研究仍然比较困难，尚需进一步研究。全局优化问题的特点导致了其算法不同于传统的局部优化方法。一般的讲，求解全局优化问题的方法可分为两类：一类是确定性算法，一类是随机算法。确定性算法是利用问题的解析性质产生一确定性的有限或无限的点序列使其收敛于全局最优解。如区间算法、分枝定界方法、填充函数法、打洞函数法和积分水平集方法f 1 3 7 1 等。凸性、单调性、稠密性、等度连续性、李普希兹常数、高阶导数一致性、水平集等通常称为全局性的解析性质。随机算法利用概率机制而非确定性的点列来描述迭代过程。随机投点方法、遗传算法，模拟退火算法是常用的随机算法。这些方法以及禁忌搜索、人工神经网络等被称为现代优化计算方法。现代优化算法通常是通过模拟生物进化、人工智能、数学与物理科学、神经系统和统计力学等概念，以直观为基础构造的，此类算法我们亦称为启发式算法。很多实际闯题的目标函数解柝性态差甚至没有解析式，传统的建立在梯度计算基础上的非线性规划算法受到限制。随机方法f 如遗传算法) 的并行性，广泛的可适用性( 如对目标函数的性态无特殊要求，特别可以没有明确的表达式) 和较强的鲁棒性、简明性等优点受到关注。下面简单概述几个全局优化的确定及随机算法。3同济大学博士后研究论文1 2 几种确定算法介绍1 2 1区间算法设冗”是扎维实欧氏空间，x 是n 维闭子箱，函数，：x 一兄是连续的，那么总极值问题为：晒p ，( z ) ( 1 2 1 )区间分析的基本思想是用区间变量代替点变量迸行计算。区间方法是求解问题( 1 2 1 ) 的一种可行的方法。该方法以区间分析为基础。利用分支定界的思想，求出目标函数在子箱x 的总极值，和总极值点集x 。在介绍区问方法之前，先给出一些定义、记号和区间运算。记，为实闭区间陋，6 】集合，其中a ，b 兄，口sb 。对任意a ，b 珀q 运算定义为：a b = 口 bfa a ，b 口) ，其中+ 可以是加、减、乘和除的运算，对除法运算，要求o 乏b 。如果a i ，我们可以写a ；f l b a ，p 6 刎，其【 a l b a ；# b a 分别为a 的上下界。闭区间的宽度定义为u ( 且) = b 一口如果d 兄，那么，( d ) = y y ，y d ) 。类似地，可定义n 维的区间向量，m 。接下来我们叙述扩张函数的定义，设d 卯嘞f ：d r ，且d ，( 1 厂) = ，( ) jz y ，表示函数，在y j ( x ) 的取值范围。如果函数f ：x ( d ) 一j 满足d ，( y ) cf ( y ) ，v y i ( x )贝口称f 是，的扩张函数。m o o r e 7 3 首先发现了区间分析是计算一个函数在子箱x 上、下界的有效工具，它可用来计算总极值f + 。1 9 7 4 年。s k e l b o e 8 9 把m o o r e 的一部分思想与分支定界原理结合起来。最后，m o o r e 再次修改，得到 m o o r e - s k e l b o e 算法。该算法是求问题( 1 2 1 ) 的总极值广。算法的主要思想是：先作目标函数，：x 一尉拘扩张函数f ：i ( x ) 一，然后利用分支定界的思想，把x 逐步细分，在某个子箱上搜索，最后找到最优值广。4同济大学博士后研究论文m o o r e - s k e l b o e 算法：步1 令y ：= x 。步2 计算f ( y ) 。步3 令：= m i n f ( y ) 。步4 令初始集合l = ( ( y ，秒) ) 。步5 选择坐标方向 tfu ( y ) = u 似) ) ，其是与予箱y 的具有最长的棱平行。步6 用垂直于方向露的超平面把y 分成两个子箱k ，坞，使得y = ku 。步7 计算f ( k ) ，f ( ) 。步8 对t ；1 ，2 ，令饥= t b f ( y , ) 。步9 把( 矿秽) 从集合l 中去掉。步1 0 把m ，奶) 和( k ，地) 加入到集合l 中去，而且使l 中的对m ，地) 从小到大排列。步1 1 记集合己的第一对为( ) 。步1 2 若“，( f f k ) ) ，( 霉：) ，存在一条从茁到z j 的下降路径若z ：是，扛) 的局部极大点，则一，如) 在局部极小点z ；处的盆谷称为，0 ) 在局部极丸最z ：的峰定义1 2 2 设z ：和z ；是函数，( z ) 的两个不同的极小点，如果，( z ：) ，( 呓) ，则称在$ ；处的盆谷彩比。；处的盆谷日低，或称目比垅高早期的填充函数方法还要求具有下面的假设：假设1 2 2 函数， ) 只有有限个极小值点假设1 2 3 函数，( z ) 只有有限个极小值孤立点z ；处盆谷b ；的半径定义为；r = i n fl i x z ：i j z 暑如果，p ) 在$ ：处的h e s s i 8 n 矩阵v 2 ，( z ：) 正定，则r 0 。填充函数算法由两个阶段步组成：极小化阶段和填充阶段。这两个阶段交替使用直到找不到更好的局部极小点。在第一步里，可以用经典的极小化算法如拟牛顿法、最速下降法等，寻找目标函数的一个局部极小点。：。然后第二步，主要思想是以当前极小点：为基础定义一个填充函数，并利用它找到z 7 z ：，使得，( z ，) ，( z ：) ，而后以z 7 为初始点，重复第一步。重复下去一直到找不到更好的局部极小点。设z ：是，p ) 的一个局部极小点，文献 3 l 】中给出填充函数的定义如下：7同济大学博士后研究论文定义1 2 3 函数p ( z ，童：) 称为， ) 在局部极小点：处的填充函数，如果满足：( 1 ) z ：是p ( z ，岳；) 的一个极大点，( z ) 在点。；处的盆谷研成为p ( z ，z ：) 的峰的一部分( 2 ) p ( z ，z ：) 在比蛾高的盆谷里没有稳定点( 引如果存在比研低的盆谷届，刖存在z ，b t ，使得p ( 而z ：) 在和z i 的连线上有极小点在各种文章中对填充函数的定义有所不同。尤其上面定义中的第三条是一个很弱的条件，很多文章做了改进。葛等人给出了一个带两个参数的填充函数函数，形式如下：脚，卯) ；南唧( 一与掣) r 4 - 歹( 。：) 0 ，这里p 是很小的参数。后来他们注意到这个函数存在缺陷。由于受到指数项e x p ( 一! 笋) 的影响，当p 2 太小或i i x z 州太大时，v p ( z ，z ：，r ，p ) 几乎都接近于零，从而出现假的平稳点。为了克服这个缺陷，葛和秦在文献【3 2 j 中给出了七个不同形式的填充函数；地球叫= 南唧( 一宁) g ( z ，z ：，r ，p ) = - p 2 l n r 4 - ，( z ) 】一0 z z ：8 2 ，o ( z ，z ：，r ，p ) = 一矿l n 【r + ，( 聋) 1 0 z x ；l l ，q ( z ，z ：，a ) ；- f ( x ) 一，( z ：) 】e x p ( a l l z z ：1 1 2 ) ，审( z ，z ：，a ) = 一f ，( z ) 一，( z ：) 】e x p ( a l l x z ：1 1 ) ，v e ( z ，$ j ，a ) = - - v f ( x ) 一2 a l f ( x ) 一，( 苟) 】( 霉一z ：) ，v 雪( ez ：，a ) = 一v f ( z ) 一以i f ( z ) 一，( z ：) 1 _ f 耋 禹他们指出后四个函数是较好的填充函数。l i u 在( 2 0 0 0 ) 文献( 5 3 j 中给出一个克服以上缺陷的填充函数：日忙，口) 2 可巧者厕叫 r - - x ；1 1 2 ，其中口 o 充分大。8同济大学博士后研究论文随后，x u 在( 2 0 0 1 ) 的文献i r i s 提出了一族性质类同的填充函数y ( x ，z ，a ，) = 一f 7 ( ，( z ) 一f ( x + ) ) 一e x p ( a w ( 1 l x 一茹+ i f 9 ) )函数叩( ) ，u ( ) 和参数a ，p 满足一定条件。这族填充函数在理论上较为完善，揭示了构造填充函数时，( z ) 一f ( z 。) 和忙一矿l l 两项的重要性，但仍含有指数函数。另一类关于前置点o o 的填充函数u ，a ，h ) = n ( 1 l z x o l l ) 妒( a ( z ) 一，0 ：) + 1 )是由g e 和q i n ( 1 9 9 0 ) 在文f 3 3 】中提出，并且随后1 妇l u c i d i 和p i c c i a l l i ( 2 0 0 2 ) 在文1 9 9 1 中进行了深一步的讨论。张连生，李端和n g ，c k 对填充函数的定义进行了改进，给出了一些性质较好的函数，如文献1 1 2 6 1 e p 定义的v ( z ，n p ) = ，p ) m i i l 扩忙) ，0 ：) 】一州0 2+ 以m a x 【o ，y ( x ) 一，( z ；) 】) 2 该文章的另一特点是他们对填充函数的迭代搜索方法进行了详细的讨论，得到了计算方法上的一些结论。进一步他们把改进后的填充函数用于求解非线性整数规划，从而为求解非线性整数规划提供了一个途径。参见1 7 4 1 1 1 2 5 1 等。由于填充函数法只需应用成熟的局部极小化算法，因此受到理论以及实际工作者的欢迎。了解填充函数算法的背景及发展，能为我们今后的研究提供明确的方向。改进其算法使之适合于应用就显得尤为重要。由于填充函数是目标函数的复合函数，且目标函数本身可能很复杂，所以构造的填充函数形式应尽量简单，参数应尽量少。以便节约许多冗长的计算步骤及调整参数的时闯，提高算法的效率。本论文便在这种指导思想下，针对以上谈及的问题加以研究。下面各个章节的内容为：第二章对连续最优化的情况，改进了早期文献 3 1 1 中的定义，并且给出了一个填充函数，设计了算法，给出了数值计算结果。第三章，在文献f 3 3 1 中连续全局优化的具有强制性的填充函数定义的基础上，提出了非线性整数规划问题的填充函数定义，在文献 1 2 9 f l 基础上，给出一个单参数的填充函数，设计了算法并且进行了数值计算。第四章对第三章的单参数填充函数形式进行了推广，对几个不同形式的填充函数进行了数值计算结果比较。第五章给出了含两个参数的填充函数，设计了算法并且给出了数值计算结果，有效解决了第三章中单参数填充函数在计算时遇到的问题。9同济大学博士后研究论文1 2 4打洞函数方法下面介绍l e v y 和m o n t a l v o 【2 】提出的打洞函数方法。考虑问题( 1 1 1 ) ，其中，( z ) 是在x = z 舻 a z s6 ，8 ，b 舻上的二次连续可徽函数。而且假设，扛) 的极小点都是孤立极小点，个数有限。该方法由两个过程组成：极小化过程和“打洞”过程，这两个过程交替进行，从而求得目标函数的全局极小值。具体描述如下：( 1 ) 在极小化过程中，从某个初始点出发，用任何一个有效的求局部极小的方法，求得函数， ) 的一个极小点。( 2 ) 在“打洞”过程中，构造打洞函数t ( x ，矿) ，从矿的一个邻域中的任意一点出发，比如也可以从矿出发，要找到某个点一，满足t ( 矿，矿) = 0 营，( 扩) = ， + )为此，l e v y 和m o n t a l v o 给出的打洞函数为：t = 茫鹎，( 1 z 2 )其中盯是参数。由( 1 2 2 ) 定义的函数，当玎充分大时，点矿为极小点：希望在极小化打洞函数过程中求到且对所有的z o z = 伽xf ( x ) ，( ) ，z o 矿，满2 ：t ( z o ) s0 。于是，我们可以求得丁佃) 的一个非芷的极小点。在实际计算时，经过若干次的两种过程的交替，函数丁( z ) 用如下的表达式：t ( z ) ；，( z ) 一广 nf ( z z ；) f ( z 一) 】m ) i ( z l 。) t ( z 一正。) 】1 0i = l式( 1 2 3 ) 中各项的目的是：分子为了消除所有满足，( 。) 广的解。分母的第1 项为了避免把前面已得到的，满足，( z ：) = ，( ) = = ，( z ；) = ，+ 的点。：，i =1 ，2 ，z 作为本过程的解。分母的第2 项是为了消除满足v t ( z ) = o ，t ( x ) o 的z 缸) 的局部极小点z 。这一求解途径的主要困难是哺 0 ，知 0 很难确定，从而使工作量增大。y a o 1 2 3 j 丕有0 b l o w 【7 5 】对原有的打洞函数方法作了重要改进，提出了动态打洞算法，但必须求解常微分方程组，这也是比较困难的工作，这里不再赘述。1 0同济大学博上后研究论文1 2 5d c 规划当日标函数和约束函数均为凸函数时，此类凸规划问题局部解就是全局解，很多非常有效的经典算法可以解决这类问题。但当目标函数和约束函数至少有一个不是凸函数时，问题就变德相当复杂了，且至今尚缺少非常有效的求解方法。然而，在实际问题中经常会遇到下述问题：ir a i nf ( x ) = c o ，l ( 。) 一c o ，2 ( z ) ， 5 ，五( z ) 一a ，( z ) 一q ，2 ( z ) 0 ，( i = l ，2 ，m ) ，( 1 2 4 )【ze x c r n 其中x 为尼坤的紧凸集且c ，l ) ，c ，2 扛) 0 = 0 ，l ，m ) 均为凸函数，通常我们称表示为两个凸函数差的函数为d c 函数，上述问题( 1 2 4 ) 称为d g 规划问题。下面简单地介绍一下d g 规划中的一些性质：1 ) 任意一个定义在舻的紧凸集上的二次可微函数( 特别是多项式函数) 为d c 函数。2 ) 任何闭集sc 彤都能表示成d d 不等式的解集：s = 矗pjm ( z ) 一忙| f 2so 其中函( z 1 为j p 上的一个连续凸函数。3 ) 设 ( z ) ，厶( z ) 是d c - 函数，则函数兰。n 。五( z ) ，( o t t r ) ，m a x - b i ，i l ，2 ，m ) = 0 ，即矿d ，则算法终止；否则转步3 。步3 选择j j ( ) ，令r + - = p k n z i 西s 如) ，计算y ( r + 1 ) ，转步1 。外逼近方法的步骤非常简捷。它已被广泛用于凹规划、反凸规划和d c 规划及单调规划问题，详尽的结果可参见文献【4 2 】。外逼近方法的收敛性已由h o r s t 等人在文献f 4 3 1 给出。基于上述的外逼近方法，算法具有m 步终止。1 2 6 单调规划在经济、工程及其它一些领域中的大量数学模型通常都具有某些变量或所有变量的单调性的性质。在最优设计的相当多数量的文章中，单调性在数值方法的研究中起着相当重要作用。当单调性与凸性和反凸性结合在一起时，产生了乘积规划【4 2 1 ，c 一规划1 5 2 】等等低维的非凸问题。在过去的十年间，参数方法、对偶基的补偿方法对求解低维的上述问题的速度是相当快的。下面我们考虑下述问题：r a i n f ( x ) lg ( z ) s1s ( z ) ，z r ；) ，( 1 2 ，6 )此处，( 盘) ，夕( z ) ，h ( x ) 都是单调增加的( 即当o 霉z 7 ，f ( x ) 2 ，( ) ，称，( z ) 为增加的) 。由考虑的抽象凸性。在某种特殊假设下，此类问题可由广义外逼近方法来处理。然而，纯单调结构的最重要的优点在于利用全局信息，通过在可行域的限制区域上的极限的全局搜索，可以用来简化问题。事实上，当( 1 2 6 ) 的目标函数是单调增加的，若2 为可行域已知的可行点，因在z + 冠没更好的可行解，故z 在z + 肥上】2同济大学博士后研究论文为不起作用的。类似地，当函数g ( x ) ( 相应地h ( x ) ) 是单调增加的，z 为在2 - t - 艘上对于约束g ( x ) 1 ( 相应地h ( x ) 1 ) 为不可行点，则整个z 十殿可以不予考虑。基于上述观察，外逼近或分支定解等有效方法来可以用求解易处理的单调规划。如果存在一单调增加函数口( z ) ，使得g = o 霹1 9 ( z ) 1 ) ，其形如g =u ：z 【o ，z 】。其中g = u z e z i o ，：】为箱子簇i o ，z 】的和集，z z ，则称g 是正规的。当z为有限集时，正规集称为多胞块。正像紧凸集是一簇多胞体的交集，紧正规集是一簇多胞块的交集。由此，单调系统的解集结构的特征可以被建立起来，用于单调不等式和单调优化词题的数值分析。更重要的是，多胞块逼近方法可以推广到求解两个单调增加函数羞的优化问题( 亦称为d j 函数的规划问题，比如问题( ? ? ) ) 。参见文献 1 0 4 ，1 0 5 。由于n 个变量的多项式可表为两个正系数的多项式之差，即两个j 强上的单调增加函数之差，由w e i e r s t r a s s 定理可知，在【o ，b 1 = 茁酽i osz 好上的d j 函数在【o 6 1 上为稠密的，因此，d ，最优化的适用范围包括多项式规划( 特别是非凸二次规划) 和各类全局和组合优化问题。虽然如此，但到目前为止，解d f 藏划问题仍然是一个较困难的问题，在理论和算法上都没有d ，c 规划完备。1 2 7分枝定界方法在组合最优化中解全局最优的最普遍工具是应用分支定界原理，特别地在求解f 1 2 5 ) 时，将区域口划分成多面体子集，即划分成单纯形( 单纯形剖分) ，划分成超长方体( 超长方体剖分) 或划分成锥体( 锥剖分) 。通常情况下，在小区域上易确定目标函数值的上下确界，从而逼近全局最优值。该方法已广泛应用于凹规划口d 规划及l i p s c h i t z i a n 规划。首先用分支定界方法求解下述全局优化问题：r a 卿i n 弛)其中，：舻一尼d c 舻，d 为紧集，在d 上连续。下面介绍分支定界方法的主要步骤。步1 选择初始可行域 如，m o ) d ，把 如划分为有限个子集脱，i i 。，是指标集。这里划分要满足条件：m o = u 眠，jn = a 觚n a 坞，j ，t j 其中a 0 表示鸩的边界。1 3同济大学博士后研究论文步2 对每个子集坛确定满足下面条件的上，下界q ( 尬) ，卢( 磊) ：p ( 尬) i n f ，( 旭n d ) n ( 坛) 再令卢= m i n b ( m i ) l i j ) ，n = m a x a ( ) i j ) ，贝0 有卢m i n ( d ) a 步3 若= 声或。一声，e 为充分小的正数，则算法终止。否则转步4 。步4 选择适当的子集坛，作更细的划分，转步2 。分支定界方法的实现主要是划分、选择和定界三个运算步骤。划分、选择和定界的不同，产生相应不同的实现算法。一般地，多面体或者凸多面体的划分的最简单形式是：单纯形、超长方体和多面锥。从而划分集合螈由它们所组成，并且一般都假定细分是彻底的。“细分是彻底的”的定义如下：定义1 2 4 多面体的一个细分是彻底的，如果由连续细分多面体所产生的每一个下降子列 鸩) 趋r o - t - 单点集j 凸多面体的一个细分是彻底的，如果由连续细分凸多面体所产生的每一个下降子列趋向于一条射线 l a y 等在 1 0 7 1 q a 讨论了一大类单纯形的彻底的细分。用的最多的是二等分，参见【3 7 】， 3 s ，1 3 9 。其主要思想是：设m 是一个札维单纯形，它是由n + 1 个仿射独立的顶点所组成的凸包。设【口j i f ，吒r 】是肘的最长的边，令 = 孙1v f r ，”j ：f ) ，用口分别代替顶点 玉和 暑f ，这样产生二个单纯形，其体积之和等于m 的体积。这就是单纯形的二等分。设s 是一个内部含原点0 的单纯形，( 比如，令s 的n + 1 个顶点为= e “=1 ，2 ，n ) ，口蚪1 = 一e ，其中e 是第i 个分量为1 的舻中的单位向量，e = ( 1 ，1 ) r 舻) 。考虑s 的竹+ 1 个斜面最，每一个最是礼一l 维单纯形。对每个最，令g 是一个凸锥，它的顶点是原点0 ，住条边是从0 开始，通过e 的佗个顶点的射线。于是 gfi =1 ，2 ，z + l 是舻的一个锥划分。如果对初始的斜面进行细分，就可以导致锥的细分。所以，对佗一1 维单纯形的二等分导致的锥的细分，就是锥的二等分。设m = qig 茹s6 是一个孔维的超长方体。用一个通过点 ( o + 6 ) 的超平面垂直割该矩形的最长的边，这样把矩形m