（运筹学与控制论专业论文）连续与离散单调优化和不定二次规划算法研究.pdf

摘要 全局优化问题主要研究如何寻找一个非凸优化问题的全局最优解随着社会的 进步以及科学技术的发展，全局最优化广泛应用于企业生产管理、金融工程、工程 设计及控制、交通运输、农业预测、国防军事等重要领域因此研究全局优化问题 在理论和应用方面都有重要的意义 本论文主要研究两类特殊结构的全局优化问题单调优化和不定二次规划 单调优化是指目标函数和约束函数都是单调函数的全局优化问题把单调优化问题 中的变量取值限制为整数，即为离散单调优化问题( 通常也称为多维不可分离背包 问题) 单调优化问题的目标函数和约束函数不要求是凸的或是可分离的不定二次 规划问题是指目标函数是不定二次函数，约束函数是线性函数或二次函数的全局优 化问题把不定二次规划问题中的变量取值限制为整数，即为整数( 离散) 不定二次 规划问题本文将着重研究带线性约束的连续和离散不定二次规划问题 本论文分为七章，各章内容简要介绍如下： 第一章给出了单调优化和不定二次规划及其离散问题的描述及一些应用模型， 同时对本论文的主要工作作了简要介绍 第二章首先介绍了一般全局优化的基本算法，然后介绍文献中连续和离散单调 优化及不定二次规划的现有算法 第三章给出了一个求解单调优化问题的精确算法该算法的框架是分枝定界， 并且与区域剖分、凸化、局部搜索三种基本策略相结合区域剖分就是把区域剖分 成若干个子箱的并集，而且这些子箱的并集覆盖了可行域的边界；在每个子箱上使 用凸化外逼近方法得到目标函数最优值的上界；再结合局部搜索改进下界我们对 该算法进行了数值实验，数值实验结果表明该算法是有效的，能在合理的时间内求 解中小规模的单调优化问题 第四章对离散型的单调优化问题进行研究，提出了一个离散的p o l y b l o c k 算法， 并且在此基础上结合凸化思想，对离散p o l y b l o e k 算法进行改进，提高了界的质量， 从而提高算法效率数值实验结果表明两个算法是有效的，而且数值比较结果表明 i 改进后的算法对具有较大区域的问题计算效果优于改进前的离散p o l y b l o c k 算法 第五章给出了一个求不定二次规划问题全局最优解的新算法首先我们给出了 不定二次规划问题的三种下界的确定方法：线性逼近、拉格朗日对偶松弛和凸松弛 然后利用这些下界并结合超长方形的两分法建立一个分枝定界算法而且我们还证 明了经正交变换所得的不定二次可分离问题的凸松弛与拉格朗臼对偶松弛是等价 的数值实验结果表明该算法是有效的 第六章给出了不定二次整数规划问题的几种新的下界并且证明了它们之间的 关系首先我们构造了问题的线性下方估计，以及通过d c 分解构造了问题的两 种凸松弛；然后通过矩阵的c h o l e s k y 分解把不定二次整数规划化为等价的可分离问 题，进而应用对偶分解导出两种拉格朗日对偶界，并建立了凸松弛界和拉格朗日对 偶界的关系本章提出的某些下界估计方法也可以应用到求( 连续) 不定二次规划问 题的算法中 最后，我们在第七章总结了本文的主要工作，并讨论了有待进一步研究的问题 关键词：全局最优化，单调优化，凸化方法，分枝定界，不定二次规划，凸松弛，拉格 朗日松弛 1 1 a b s t r a c t g l o b a lo p t i m i z a t i o na i m st of i n dt h eg l o b a lo p t i m a ls o l u t i o no fan o n c o n v e x o p t i m i z a 土i o np r o b l e m w i t ht h ep r o g r e s so ft h em o d e ms o c i e t ya n dt h ed e v e l o p m e n t o fs c i e n c ea n dt e c h n o l o g y , g l o b a lo p t i m i z a t i o np l a y s 吼i m p o r t a n tr o l ei nm a n yf i e l d s s u c h 聃p r o d u c t i o np l a n n i n ga n dm a n a g e m e n t ，丘眦c h le n g i n e e r i n g ，e n g i n e e r i n g d e s i g na n dc o n t r o lt r a f f i ct r a 地p o r t a t i o n ，a g r i c u l t u r a lf o r e c a s t ，n a t i o n a ld e f e n c ea n d s oo n t h es i g n i f i c a n c eo ft h ea l g o r i t h m i cs t u d i e so ng l o b a lo p t i m i z a t i o ni 8t h e r e f o r e e v i d e n t i nt h i st h e s i s ，t w oc l a s s e so fg l o b a lo p t i m i z a t i o np r o b l e m sw i t hs p e c i a ls t m c t u r e s a r es t u d i e d ：m o n o t o n eo p t i m i t i o np r o b l e ma n di n d e f i n i t eq u a d r a t i cp r o g r a m m i n g p r o b l e m m o n o t o n eo p t i m i z a t i o nd e a l sw i t ht h ep r o b l e m so fo p t i m i z i n ga m o n o t o n e f u n c t i o ns u b j e c tt om o n o t o n ec o n s t r a i n t s d i s c r e t em o n o t o n eo p t i m i z a t i o np r o b l e m j 8am o n o t o n eo p t i m i z a t i o np r o b l e mw i t ha l lv a r i a b l e sr e s t r i c t e dt oi n t e g e r s s u c h p r o b l e m sa r ea l s or e f e r r e dt o 柏m u l t i - d i m e n s i o n a ln o n s e p a r a b l ek n a p s a c kp r o b l e m s t h eo b j e c t i v ef u n c t i o na n dt h ec o n s t r a i n tf u n c t i o n so fam o n o t o n eo p t i m i z a t i o n p r o b l e ma r en o tn e c e s s a r i l yc o n v e xo rs e p a r a b l e i n d e f i n i t eq u a d r a t i cp r o g r a m m i n g d e a sw i t ht h ep r o b l e m so fo p t i m i z i n g 曲i n d e f i n i t eq u a d r a t i cf u n c t i o ns u b j e c tt o l i n e a zc o n s t r a i n t so rq u a d r a t i cc o n s t r a i n t s i n d e f i n i t eq u a d r a t i ci n t e g e r ( d i s c r e t e ) p r o g r a m m i n gi 8a ni n d e f i n i t eq u a d r a t i cp r o g r a m m i n gw i t ha l lv a r i a b l e sr e s t r i c t e d t oi n t e g e r s i nt h i st h e s i s ，w ef o c u so nc o n t i n u o u sa n dd i s c r e t ei n d e f i n i t eq u a d r a t i c p r o g r a m m i n gw i t hl i n e a rc o n s t r a i n t s t h i st h e s i sc o n s i s t so fs e v e nc h a p t e r s i nc h a p t e r1 ，m o n o t o n eo p t i m i z a t i o n p r o b l e m ，i n d e f i n i t eq u a d r a t i cp r o g r a m m i n gp r o b l e ma n dt h e i rd i s c r e t ev e r s i o n sa r e f o r m a l l yd e s c r i b e d s e v e r a le x a m p l e so fa p p l i c a t i o n so fc o n t i n u o u sa n dd i s c r e t e m o n o t o n eo p t i m i z a t i o na n di n d e f i n i t eq u a d r a t i cp r o g r a n m n i n ga r ep r e s e n t e d f i - n s j l y , t h em a i nc o n t r i b u t i o n so ft h et h e s i sa r eb r i e f l yi n t r o d u c e di nt h i sc h a p t e r i i i i nc h a p t e r2 ，s o m eb a s i cs o l u t i o na l g o r i t h m sf o rg e n e r a lg 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 ef i r s ti n t r o d u c e d ，w et h e ng i v el i t e r a t u r es u r v e yo fa l g o r i t h m sf o r c o n t i n u o u sa n dd i s c r e t em o n o t o n eo p t i m i z a t i o np r o b l e m sa n di n d e f i n i t eq u a d r a t i c p r o g r a m m i n gp r o b l e m s i nc h a p t e r3 ，an e we x a c tm e t h o df o rm o n o t o n eo p t i m i z a t i o np r o b l e m si sp r o - p o s e d t h em e t h o di so fb r a n c h - a n d b o u n df r a m e w o r kt h a tc o m b i n e st h r e eb a s i c s t r a t e g i e s ：p a r t i t i o n ，c o n v e x i f i c a t i o na n dl o c a ls e a r c h t h ep a r t i t i o ns c h e m ei su s e d t oc o n s t r u c tau n i o no fs u b b o x e st h a tc o v e r st h eb o u n d a r yo ft h ef e a s i b l er e g i o n t h ec o n v e x i f i c a t i o no u t e ra p p r o x i m a t i o ni st h e na p p l i e dt oe a c hs u b b o xt oo b t a i n a nu p p e rb o u n do ft h eo b j e c t i v ef u n c t i o no nt h es u b b o x t h ep e r f o r m a n c eo ft h e m e t h o dc o nb ef u r t h e ri m p r o v e db yi n c o r p o r a t i n gt h em e t h o dw i t hl o c a ls e a r c h p r o c e d u r e t h en u m e r i c a lr e s u l t ss h o wt h ef e a s i b i h t ya n de f f e c t i v e n e s so ft h ep r o - p o s e da l g o r i t h m ，a n dt h ea l g o r i t h mc a l ls o l v em e d i u ms i z em o n o t o n eo p t i m i z a t i o n p r o b l e m si nr e a s o n a b l et i m e i nc h a p t e r4 ，w es t u d yd i s c r e t em o n o t o n eo p t i m i z a t i o n ad i s c r e t ep o l y b l o c k a l g o r i t h mi sf i r s tp r o p o s e d t h ep o l y b l o c ka l g o r i t h mi st h e ni n c o r p o r a t e dw i t hc o n - v e x i f i c a t i o nm e t h o dt oi m p r o v et h ee f f i c i e n c yo ft h ea l g o r i t h m n u m e r i c a lr e s u l t s s h o wt h a tt h et w oa l g o r i t h m sa r ee f f e c t i v ef o rd i s c r e t em o n o t o n eo p t i m i z a t i o np r o b - l e m sa n dt h ec o m p a r i s o nr e s u l t si n d i c a t et h a 七t h ei m p r o v e da l g o r i t h mo u t p e r f o r m s t h ed i s c r e t ep o l y b l o c ka l g o r i t h mf o rt h ep r o b l e m sw i t hl a r g ed o m a i nr e g i o n i nc h a p t e r5 ，w ep r e s e n tan e wa l g o r i t h mf o rf i n d i n gg l o b a ls o l u t i o no fi n d e f i n i t e q u a d r a t i cp r o g r a m m i n gp r o b l e m s t h r e el o w e rb o u n d i n gt e c h n i q u e s ，l i n e a ra p p r o x - i m a 土i o n ，l a g r a n g i a nd u a lr e l a x a t i o na n dc o n v e xr e l a x a t i o n ，a r ed e r i v e d ab r a n c h - a n d - b o u n da l g o r i t h mb a s e do nt h e s el o w e rb o u n d i n gt e c h n i q u e sa n dr e c t a n g u l a r b i s e c t i o ni se s t a b l i s h e d w ea l s o8 h o wt h a tt h ec o n v e xr e l a x a t i o no ft r a n s f o r m e d s e p a r a b l ei n d e f i n i t eq u a d r a t i cp r o b l e mb yo r t h o g o n a lt r a n s f o r m a t i o ni se q u i v a l e n t t ot h el a g r a n g i a nd u a lr e l a x a t i o n p r e l i m i n a r yc o m p u t a t i o n a lr e s u l t si n d i c a t et h e e f f e c t i v e n e s so ft h ep r o p o s e da l g o r i t h m i v i nc h a p t e r6 ，s e v e r a ln e wl o w e rb o u n d sa l ed e r i v e df o ri n d e f i n i t eq u a d r a t i ci n - t e g e rp r o g r a n n i n gp r o b l e m sa n d t h e i rr e l a t i o n sa r e 髑怕山l i s h e d w ef i r s tc o n s t r u c t c o n v e xr e l a x a t i o n sb yd ( 1d e c o m p o s i t i o na n dl i n e a rt m d 懈t i 切- 8 七i o n c h o l e s k y f a c t o r i z 8 _ t i o ni su s e dt or e d u c et h eo r i g j i l 越p r o b l e mi n t ot h es e p a r a b l ep r o b l e m s t w o l a g r m a g i a nb o u n d sa r et h e nd e r i v e db ya p p l y i n gd u a ld e c o m p o s i t i o ns c h e m e st ot h e p 甜8 b kr e f o r m u l a t i o n s r e l a t i o n s h i p sb e t w e e nt h ec o n v e xr e l a x a t i o nb o u n d sa n d l a g r a n g i a nb o u n d sa f f ea l s o t a b l i 8 h e d t h e s eu n d e r e s t i m a t i o nm e t h o d sa r ea p - p l i c a b l et ot h ea l g o r i t h m sf o r ( c o n t i n u o u s ) i n d e f i n i t eq u a d r a t i cp r o g r a m m i n gp r o b - l e m s f i n a l l y , w ec o n c l u d et h et h e s i si nc h a p t e r7b ys u m m a r i z i n gt h em a i nr e s u l t s a n dd i 8 c u s s i n gs o m ep o s s i b l ef u t u r er e s e a r c hd i r e c t i o n s k e yw o r d s g l o b a lo p t i m i z a t i o n ；m o n o t o n eo p t i m i z a t i o n ；c o n v e x i f i c a t i o nm e t h - o d s ；b r a n c h - a n d - b o u n d ；i n d e f i n i t eq u a d r a t i cp r o g r a m m i n g ；c o n v e xr e l a x a t i o n ；l a - g r a n g i a nr e l a x a t i o n v 0 d c 符号说明 全体实数的集合 n 维实向量空间 分量全为非负数的n 维向量的集合 分量全为负数的n 维向量的集合 r n 中全体整数向量的集合 n 阶单位阵 矩阵a ，向量z 的转置运算 各分量均为l 的n 维列向量 第j 个分量为1 ，其余分量全为0 的n 维列向量 向量的欧几里德范数 向量的无穷范数 以r , 维向量e 的分量为对角元的n 阶对角阵 多元函数 0 ) 的h e s s i a n 阵 问题( ) 的最优值 r t , 维整数向量，其分量是小于或等于的最大整数 n 维整数向量，其分量是大于或等于墨的最小整数 集合y 中所含元素个数 空集 两个凸函数之差 v i z r职贮驴晶删。一诽嘶啪m m m 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究 工作。除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已发表和撰写过的研究成果。参与同一工作的其他同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示了 谢意。 签名：筮丝丛日期：星。1 2 ： 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定， 即：学校有权保留论文及送交论文复印件，允许论文被查阅和 借阅：学校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：筮丝丛导师签名碰日期：掣。 上海大学博士学位论文 第一章绪论 随着社会的进步以及科学技术的发展，全局优化问题广泛应用于企业生产管 理、金融、经济、工程设计及控制，网络交通、农业预测、国防军事等重要领域， 因此对全局优化的研究越来越受到国际优化界的普遍关注，研究异常活跃，尤其是 近二十年，取得了很多新的进展，有关专著和综述见文献【1 4 】【5 0 】【5 4 】【5 5 】【5 8 j 1 7 0 】【7 1 】 8 7 9 8 1 0 3 1 1 2 1 1 1 问题描述 1 1 1 全局优化问题 全局最优化问题是求一个实值目标函数在某个给定区域的全局最优解，而非局 部最优解其一般形式为 ( p ) r a i nf ( x ) s t 石d ( 1 1 1 ) 其中f ( x ) ：p r 是连续函数，d 为p 中的紧集全局最优化问题按约束性质可 分为无约束全局优化问题和约束全局优化问题： 无约束全局优化问题：d = 仁p l0 坳，j 一1 ，n ； 约束全局优化问题：d = p pl 取( z ) 0 ， = 1 ，2 ，竹l ，特别地，线性约 束d = 伽皿nia x 6 善o ，其中a 是m t l 矩阵，b r 下面先介绍局部极值点和全局极值点的定义( 见文【l l 】) ： 定义1 1 1 设r d ，如果存在某个正数e 0 ，使得当z d 且忙一矿0 e 时 有f ( x ) ，( $ ) ( ，( 矿) ，( 。) ) 成立，则称矿是，( 。) 的局部极小体最，o i ( x ) 是 局部极小体胜 定义1 1 2 设矿d ，如果对所有的z d 有f ( x ) ，( z ) ( ，( 矿) ，( 石) ) 成立， 别称是，( z ) 在d 上的一个全局极小体j 点，称，( 矿) 是，( 。) 在d 上的全局极小体，值 1 上海人学博士学位论文 由于m 喊 f ( x ) iz d ) = 一m i n 一f ( x ) lz d ) ，所以，全局极大化问题 也可化为全局极小化问题( p ) 而且，由于g i ( x ) 0 等价于- g i ( z ) 0 ，g i ( x ) = 0 等价于鼽( z ) 0 和一鳜0 ) 0 ，所以问题( p ) 包含了许多其它类型的约束 众所周知，在非凸情况下，非线性规划的极小( 大) 化方法一般只能收敛到k k t 点， 同时，由于缺少有效的判别准则来判别一个局部极小点是否是全局极小点，现有非 线性规划中求局部解的技术和方法不能直接被用于求解全局优化问题另一方面， 在实际应用中，对很多有全局特性的模型和问题只求出局部解是远远不够的，还需 考虑全局最优性，因此研究全局优化算法在理论和实际应用中都很有意义。并具有 挑战性 根据目标函数和约束函数的特性，全局优化问题可划分为很多类别，包括凹极 小问题、d c 优化、单调优化、l i p s c h i t z 优化、二次优化等，本论文着重研究单调 优化和不定二次规划 1 1 2 单调优化问题 单调优化问题是一种特殊结构的全局优化问题，它的目标函数和约束函数都 是单调函数为描述之方便，我们先给出相关的记号和多元单调函数的定义( 见 文f 9 8 j 1 1 3 】) ： 对于任意两个向量z 1 ，。2 r “，记号z 1 茹2 意指z ：孑 ，vi = l ，n ；记 号z 1 z 2 意指。j z i ，v i = 1 ，n 且至少有一个z z i ，i 1 ，n 定义1 1 3 设，：珉，一职，如果对于z 1 ，z 2 渺且z 1 z 2 ，有f ( x 1 ) f ( x 2 ) ( ，( z 1 ) f ( x 2 ) ) ，则称，( z ) 是皿”上的单调增加限少j 函数 若上述严格不等式成立，则称，扛) 是瑕一上的严格单调增加( 减少) 函数 单调优化问题可表示为 ( m p ) m a xf ( x ) ( 1 1 2 ) s t 吼( z ) b i ，i = 1 ，m ， 。x = 。r ”ib 1 ，j = 1 ，佗 ， 其中，和吼在【f j ，哟】上关于巧单调，j = 1 ，n ，而且，和m 不要求是凸的或是可分 2 上海大学博士学位论文 离的由单调性可知，问愿( m p ) 总可化为下面两种非平凡的情形： f 和m 在x 上都是单调递增的； f 和吼在x 上都是单调递减的 若把问题( m p ) 的变量取值限制为整数，即可得到下列离散单调优化问题： ( m ，p ) m 腿，( z ) s t 皿0 ) k ，i = 1 ，m ， z x = z z p lb s 巧1 ，j = 1 ，n ， 其中f 和霸在如，训上关于巧单调，0 ，吩是整数且0 坳，j = l ，n 函数 ，和当不要求是凸的或可分离的问题( m i p ) 通常也称为多维不可分离的背包问 题 在实际应用中很多优化模型是单调优化问题的特例或它的等价形式例如复杂 网络系统的可靠性问题，最优设计问题等等( 具体应用模型下节给出) 还有，被广 泛研究的连续资源分配问题是问题( m p ) 的一种特殊情形，其中只带一个可分离 的凸约束，目标函数，是可分离的( 见文1 4 5 1 5 9 6 5 ) 离散单调优化问题( m i p ) 的 应用模型包括离散二次背包问题，选址问题，交通设施最优设置问题和经济中的增 长和竞争模型等( 见文【1 6 】【5 9 】【8 3 】1 1 0 9 】【1 1 6 】) 求解问题( m p ) 和问题( m i p ) 的主要困难在于函数，和m 的非凸非凹性和 不可分离性传统的全局优化的求解方法，如分枝定界法、外逼近法、割平面法等 都不能直接用于解单调优化问题( m p ) ，非线性整数规划的传统方法如分枝定界法， 拉格朗日分解法也不能直接用于求解问题( m i p ) 因此设计单调优化问题的有效 算法具有相当的困难和挑战性 本文将在第三章和第四章分别给出求解问题( m p ) 和问题( p ) 的新算法， 这些新算法基于单调函数的凸化技术，充分利用了问题的单调性结构，并且使用了 新颖的区域剖分技术 1 1 3 不定二次规划问题 不定二次规划问题是指目标函数是不定二次函数，约束函数是线性函数或二次 3 上海人学博士学位论文 函数的全局优化问题本文研究线性约束不定二次规划的全局优化问题，其形式为： ( q p ) m i nl ( x ) = x t q 。+ ，z ( 1 1 3 ) s t a x s6 善0 ， 其中q 是n n 阶实对称不定矩阵，以是mxn 阶矩阵，c r ”，b r ” 若把问题( q 尸) 的变量取值限制为整数，即可得到离散( 整数) 不定二次规划问 题： ( q i p ) m i nf ( x ) = z 丁+ ，z s t a x sb ， z 0 z z “ 连续和离散二次规划问题在工程设计、生产计划、资源分配、设施定位、经 济金融等方面有广泛的应用( 见文f 3 2 】【8 8 】) 不定二次规划可以应用于大规模集成电 路( v l s i ) 芯片设计中( 见文【2 3 】 6 1 】【7 8 】) 不定二次规划问题在许多非线性规划方法 中也起着重要的作用，例如，信赖域方法中的不定二次规划子问题f 见文1 1 0 0 1 ) 不 定二次规划也是序列二次规划( s q p ) 方法的基本子程序，因此，研究连续和离散不 定二次规划问题在理论和应用方面都有重要的意义 由于其应用的广泛性。不定二次规划问题已成为当今优化领域的一个研究热点 众所周知，不定二次规划问题是n p - 难问题( 见文 9 0 1 ) ，已经证明，甚至验证不定二次 规划的局部最优解是全局最优解也是n p 难的( 见文 8 9 1 ) 故研究问题( q p ) 和( q j p ) 的 算法极具挑战性 本文将在第五章给出一个求解不定二次规划问题( q p ) 的新算法，该算法是一 个分枝定界算法，下界是由线性逼近和凸松弛确定在第六章给出了不定二次整数 规划问题的几种新下界，并证明了它们之间的关系利用这些下界可以进一步构造 求解不定二次整数规划的分枝定界算法 4 上海大学博士学位论文 1 2 应用模型 1 2 1 单调优化问题的应用模型 单调性是很多经济、管理和工程设计等实际问题中函数的自然性质下面给出 单调优化在复杂可靠性网络系统中的应用例予 例1 2 1 ( 复杂网络系统的可靠性问题) 随着现代科学技术的发展，出现在入们实际生活中的各种网络系统日趋复杂， 人们在依赖科技的同时也对系统的可靠性提出了更高的要求而系统可靠性的提高 可以通过采用高可靠性的单个部件或子系统来提高复杂网络系统的可靠性问题是 确定每个子系统的可靠性承平，从而使整个系统的可靠性最大化其优化模型为一 个连续的单调优化问题： m a xf ( r l ，k ) s t e i ( r z 。，r n ) q ，i = l ，m ， 0 0 勺 1 ，j = 1 ，n ， 其中 ，表示整个系统的可靠性； 毋表示第i 个资源( 费用，重量和体积等) 消耗，m 关于每个r j 是严格单调增加 函数： a 表示第1 种资源的总量： r j 表示第j 个子系统的可靠性水平，r ( 0 ，1 ) ； f j ，t | 厂一分别表示。的下界和上界，0 b ，( z ；) ， 曼1 3 称在呓处的盆谷磁比。 处的盆谷b ；低，或称霹比现高 填充函数法的主要思想是：首先用求局部极值的方法( 如拟牛顿方法，梯度投影 法，共轭梯度法等) 求出目标函数，( 善) 在_ d 中的一个局部极小点z j ；然后以z ：为 基础定义一个填充函数，并利用它找到，q ) 在d 中的另一个局部极小点霉；，且 要求满足如下不等式： ，0 ；) 0 1 3 上海人学博士学位论文 填充函数( 2 1 2 ) 存在缺陷由于受到指数项唧( 一二亏严) 的影响，当矿太小或 忙一z 川2 太大时，尸( z ，z ：) 和v p ( x ，z ：) 变得很小，几乎接近于零，从而产生假的 平稳点为了克服该缺陷，葛和秦在文1 3 4 1 , 给出了七个不同形式的填充函数： 托一川= 南唧( 一宇) ， g ( ，。：，r ，p ) = 一p 2 l o g r + ，( z ) 】一茁一z ：f 1 2 ， 0 ( z ，z ：，r ，力= 一p 2l o g r + ，( z ) 1 一i i 一z ：i | ， q ( 。，z ：，a ) = 一【，0 ) 一，( 。：) 1 e x p ( al i x z ：酽) ， q ( 。，。：，a ) = 一【，( 。) 一，( z ：) 】e x p ( a i l ：c z ：0 ) ， w e ( x ，z ：，a ) = - - v f ( x ) 一2 a f ( x ) 一，0 ：) 】0 一z ：) ， v 亩扛，z ：，a ) = 一v f ( z ) 一 【，。) 一，( z ：) 】i i ! 三詈知 他们指出后四个函数是较好的填充函数 l i u 在文1 7 7 j 中也给出了一个克服以上缺陷的填充函数： 日( 叫：，口) 2 可可者= 了砑一训i 。一础t 其中参数a 充分大 随后。x u 在i e 1 2 1 l q a 提出了一族性质类似的填充函数 ，仁，z + ，a ，卢) = 一叼( ，( 。) 一，( z ) ) 一, x p ( a u ( 1 l x 一$ + “9 ) ) ， 其中函数叩( ) ，u ( ) 和参数a ，卢满足一定条件这一族填充函数在理论上较为完善， 揭示了构造填充函数时，( 。) 一，( r ) 和忙一矿0 两项的重要性但这些函数中仍 含有指数函数 张连生教授等人在文【1 2 5 】中对填充函数的定义进行了改进，并给出了一个性质 较好填充函数： ；，。( z ) = ，( z ：) 一m i n f ，( z ：) ，( z ) 】一p i z z ；j 1 2 + p i n 8 x 【o ，( z ) 一，( z ：) 】) 2 ， 这里z ；是当前局部极小点，p ，p 为参数，该文还对填充函数的迭代搜索方法进行了详 细的讨论，他们还进一步把改进后的填充函数应用于求解非线性整数规划，建立了 一个近似算法，从而为求解非线性整数规划提供了一个新的途径( 见文【8 1 】) 1 4 上海大学博士学位论文 2 1 1 3 积分水平集方法 积分水平集方法是郑权教授首先提出来的该方法不同于前面所介绍的方法。 它是利用了函数的整体性质来解决全局优化问题( 见文【1 】【2 2 】f 1 2 6 1 ) 郑权教授等人在文【1 】中给出了问题( 2 1 1 ) 的最优性条件： 定理2 1 1 设c r j f t 3 c = p di ，( z ) 曲口，p 是l e b 铡g u e 测度若下列务 件之一成立： 例p ( 致) = 0 i 例p ( 凰) 0 且忍= c ，其中e 是均值 e = 志厶m ) 毗 纠p ( f l ) o 且方差 厕1f x o ( i ( z 卜e ) 2 印= 。； 则c 是f 在d 上的全局最小值，以是全局最小点集合 下面我们给出积分水平集的概念性算法： s t e p1 取t 0 d ，给定一个充分小的正数，令c o = f ( x o ) 月矗= p di ，( 。) s 句) 口，女= 0 s t e p2 若肛( h ) = 0 ，则靠为全局极小值，凰。为全局极小值点集，转s t e p6 s t e p3 计算均值 = 志厶。他) 咖， q + 1 - 硪丽厶。他) 印， 且令鼠。= 和di ，( z ) q + 1 ) 若吼+ l = 佩，则q + l 为全局极小值，段。 为全局极小值点集，转s t e p6 ；否则，转s t e p4 。 s t e p4 计算均方差 v f 2 志k l 一c 对如 s t e p5 若矿f g ，则令k ：= + 1 ，转s t e p2 ；否则，转s t e p6 s t e p6 令，= c k + l ，且日= 凰* 算法终止。为，( z ) 在d 中的近似全局 极小值点集，i 为相应的近似全局极小值 1 5 上海大学博士学位论文 积分水平集算法具有很好的收敛性准则，并且该算法仅需要计算目标函数值， 故适用于较大范围的全局优化问题但在一般情况下，水平集不易求得，所以实现积 分水平集算法有一定的难度在实际应用中往往使用随机方法来实现，通过m o n t e c a r l o 随机取点取得近似水平集并缩小搜索范围 2 1 1 4 随机算法和启发式算法 随机算法是指算法过程和结果具有随机性的方法，它是为解决实际应用的很多 复杂和大规模全局优化问题而提出来的随机算法主要包括二阶段方法、箍机搜索 方法和随机函数方法等( 见文 6 3 9 4 1 1 9 5 ) 因为许多全局优化问题的结构无法知道， 而且有很多问题本身就没有任何结构，有些甚至连目标函数的表达式都难以获得， 所以，对于这类问题我们无法利用函数的解析性质，e p i c 难用确定性算法求出全局 最优解另外，有很多确定性算法在使用时有一定的难度随机算法一般仅需要对 问题作非常弱的假设，因而适合于上述问题的求解，所以这类算法在全局最优化中 也起着非常重要的作用许多随机算法具有简单易行的优点，但它们也存在着些 难以克服的缺点，其中主要有：( 1 ) 至多只能给出在概率意义下的解：( 2 ) 算法效率比 较低；( 3 ) 容易丢掉真正的全局最优解；( 4 ) 没有比较好的终止准则，无法保证所找到 的解一定是全局最优解 启发式算法通常是通过模拟生物进化，人工智能，数学与物理科学，神经系统 和统计力学等概念，以直观为基础构造的算法启发式算法主要包括禁忌搜索算法、 模拟退火算法、遗传算法和人工神经网络等。 2 1 2 凹极小问题的算法 如前指出，由于求解一般形式的约束全局优化问题难度很大，所以人们更多的 是关注那些具有特殊结构的约束全局优化问题，特别是凹极小化问题，单调优化问 题，d c ，优化问题以及二次规划问题等( 见文1 4 6 】【4 7 1 【5 2 】【5 7 】【1 0 8 1 【1 1 1 l 【1 1 4 1 ) 由于本论文第三章、第四章所研究的单调优化问题经过等价变换后化为凸极大 化问题( 或凹极小化问题) ，因此在本节我们简要地介绍求凹极小化问题的一些基本 算法所谓凹极小化问题，就是指目标函数，( o ) 是凹函数，可行域d 是一般紧凸集 的全局优化问题 】6 上海大学博士学位论文 2 1 2 1 基本概念和结果 下面先介绍一些有关的定义和结论： 定义2 1 4 有限个半空间的交称为多面体伽l y h e d r o n ) , 有界的多面体称为多胞 形( p o l y t o p e ) 显然，多面体可表示为 如r l a x 6 ， 其中a 是一个m 竹矩阵，b r m 定义2 1 5 设函数，：g r ，其中c 是皿”中的凸集如果对于任意z l z 2 g 和0 a 1 ，有 ，( 妇l + ( 1 一a ) z 2 ) a f ( x 1 ) + ( 1 一a ) ，( $ 2 ) ， 则称，是e 上的一个凸函数如果上述严格不等式成立，刖称，是严格凸函数 如果(