（运筹学与控制论专业论文）几个求解全局优化的填充函数法.pdf

摘要 最优化问题广泛见于工程、国防、经济、生产管理、交通运输等许多重要领域。 最优化是一门讨论决策问题的最优选择，构造寻求最优解的计算方法并研究这些 方法的理论性质及实际计算表现的学科。在过去的几十年里，由于全局最优化在 许多领域的重要应用，其理论和方法已经得到了很大的发展。这些方法主要包括 确定性方法和随机性方法。其中，填充函数法就是随之出现的一种确定性方法。它 是求解全局最优化问题的实用方法之一。 本论文的主要工作就是讨论并研究了求解一般函数的全局最优解问题的几个 填充函数法。 填充函数法的丰要思想是：如果已经找到了个局部极小点z ，但它不是全 局最小点，我们可以在z 处构造一个填充函数使迭代点列离开z + 所在的谷域， 找到更好的点z ( 即z 处的目标两数值比z + 处的目标函数值更小) 。然后以x 7 为 初始点极小化原问题找到更优的局部极小点。 本论文结构安排如下： 第一章主要介绍了目前的几种伞局最优化问题和算法，以及他们的特点。其 中有：填充函数法、打洞函数法、分支定界法、积分水平集法等。我们对填充函数 法做了着重介绍。在此基础上，分析了各自的优缺点，为进一步的改进和构造新的 填充函数法，提供了一些指导思想和思路。后面六章由六篇独立的文章组成。 在第二章，利用【8 7 】中改进的填充函数的定义，对一般无约束最优化问题提 出了一个新的填充函数。分析并证明了该填充函数的性质，针对该填充函数，建立 了一个新算法，对该算法进行了数值实验。数值结果表明该填充函数法是有效的。 在第三章，利用改进的填充函数的定义，对一般的无约束最优化问题给出了一个 新的单参数填充函数，分析并证明了此填充函数的性质，利用该填充函数，构造了 新的算法，对此算法进行了数值实验，并将此算法与上一章的算法做了比较，结果 表明此填充函数算法是可行的。在第四章，利用改进的填充函数的定义，对一般无 约束最优化问题给出了新的填充函数，并构造了新的算法。在第五章，利用第二章 介绍的填充函数，建立了求解整数规划的新算法。本章首先介绍了些关于离散 i 优化的基本概念，然后给出了新的算法，并给出了用此算法求解几个测试问题的 计算结果。计算结果表明此算法是有效的和可行的。在第六章，我们介绍了一个新 的单参数填充函数，建立了求解整数规划的新算法，并给出了用此算法求解几个 测试问题的计算结果。计算结果表明此算法是实用有效的方法之一。在第七章，绍 了一个新的填充函数，并构造了求解整数规划的新算法。 关键词全局最优化填充函数方法局部极小点全局极小点连续规划离 散规划 a b s t r a c t g l o b a lo p t i m i z a t i o np r o b l e m sa b o u n d si nm a n yi m p o r t a n tf i e l d ss u c ha se n 酉n e e r i n g ，n a t i o n a ld e f e n c e ，f i n a n c e ，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 ，e t c t h eo p t i m i z a t i o ni sad i s c i p l i n ew h i c hd i s c u s s e st h ec h a r a c t e r so fo p t i m a lc h o i c eo nd e c i s i o np r o b l e m sa n dc o n s t r u c t sc o m p u t i n ga p p r o a c h e st of i n dt h e o p t i m a ls o l u t i o n d u r i n gt h ep a s ts e v e r a ld e c a d e s ，g r e a td e v e l o p m e n th a sb e e n o b t a i n e di nt h et h e o r e t i c a la n da l g o r i t h m i ca s p e c t so fg l o b a lo p t i m i z a t i o nd u et o t h ei 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 e s ed e v e l o p e da p p r o a c h e sm a i n l yc o n s i s t o ft w oc a t e g o r i e s ：s t o c h a s t i ca n dd e t e r m i n i s t i cm e t h o d s t h ef i l l e df u n c t i o na l g o - r i t h mi n t r o d u c e db vg ea n dq i n ( 1 9 8 7 ) i so n eo ft h ed e t e r m i n i s t i cm e t h o d s i ti s o n eo ft h ee 伍c i e n tm e t h o d st os o l v et h eg l o b a lo p t i m i z a t i o n t h i sp a p e rm a i n l yd i s c u s s e sa n ds t u d i e s s e v e r a lf i l l e df u n c t i o nm e t h o d st os o l v e t h eg l o b a lo p t i m i z a t i o np r o b l e mo fg e n e r a lf u n c t i o n t h em a i ni d e ao ft h ef i l l e df u n c t i o n ：t h e yh a v ec o m m o nc h a r a c t e r i fal o c a l m i n i m i z e rz ：h a sb e e nf o u n df o rp r i m a lp r o b l e m ，w ec a nm a k eaa u x i l i a r yf u n c t i o n ， s u c ha st u n n e l l i n gf u n c t i o no rf i l l e df u n c t i o n ，s u c ht h a ti t e r a t i v es e q u e n t i a lp o i n t s l c a v et h ev a l l e yi nw h i c hz ：l i e st of i n dab e t t e rp o i n tz i dt h el o w e rv a l l e y ( i e ( z 7 ) 0 ，使得对于所有x l ，x 2 s ，有 l f ( x 2 ) 一，( z ) l l i i x ，一x l l l ， 其中l 称为李普希兹常数。 定理1 1 1 设sc 舻是凸的，在包含s 的一个开集上连续可微，并且在 s 上具有有界的梯度，则，在s 上是李普希兹函数，且李普希兹常数 l s u p l l v f ( x ) l i ：z s 】1 定义1 1 7 sc 形称为闭集，如果s 包含所有收敛点列 戤) cs 的极限 点：sc 舻称为紧集，如果s 是闭的有界集 由函数在紧集上的连续性，可以得到下列著名的魏尔斯特拉斯定理： 定理1 1 2 如果s 是舻中一个非空紧集，f ( x ) 是s 上的连续函数，那么 f ( x ) 在s 上至少有一个全局极小( 极大) 点 定义1 1 8 集合s 形上定义的实值函数，在s 上的点z 处称为下半 连续，如果有f ( x ) = l i r ai n f f ( y ) ；，在s 上的点z 处称为上半连续，如果有 f ( x ) = l i ms u p ，( 可) 容易看出，函数在z 点处既下半连续，又上半连续，则它在z 点处连续。如 果将定理1 1 2 中，的连续替换成下半连续( 上半连续) ，定理仍然成立。 定义1 1 9 在凸集c 上函数，的上方图砸( ，) 表示为：e p ( ，) = ( z ，r ) c r ：r ，( z ) 。 在极小化问题和凸性的研究中，下半连续的表现形式和重要性与下面的结果 有关： 定理1 1 3 设凸集s 是舻中一个非空闭集，是s 上任意一个函数，则下 列条件是等价的： f 在s 上，是下半连续的 2 对于每个o t r ，l ( ，；o t ) = z s ：f ( x ) q 是闲的 舅在形+ 1 中，上方图e p i ( f ) 是闭集。 定义1 1 1 0 定义在舻中的函数，( z ) 称为强制的，如果有* mf ( x ) = + 对于无约束最优化问题，其中s = 胛，若，是强制的，则全局极小点的存在 性问题可以借助定理1 1 2 来讨论。 3 上海大学博士学位论文 定理1 1 4 若，( z ) 是强制的，并且连续，则厂( z ) 在俨中至少有一个全局 极小点 下面给出一些关于局部和全局极小点特征的结果： 定义1 1 1 1 向量d 舻称为点矿s 处的可行方向，如果存在a 0 ，使 得对于每个0 a ，有z + + a d s ( s 是问题的可行域) 令，在点矿的一个邻域内连续可微，并且令d 舻满足d r v f ( z + ) 0 ， 其中表示式d r v f ( x ) 是在z 处沿方向d 的方向导数。对于固定z 和d ，函数 ， + + a d ) 描述了，沿射线 z = z + a d ，a o ) 的情况。因为 ，( z + + a d ) = ，( z ) + a 矿v s ( z + c a d ) ， 这里0 口 0 ，使 得对于每个0 a 页，有，( z + + a d ) ，( 矿) 。也就是，可以沿方向d ，使，局部 地下降。所以我们有如下定理： 定理1 1 5 假设函数，( z ) 在一个包含sc 舻的开集内连续可微。若z s 是， ) 的一个局部极小点( 相对于s ) 则对于每个可行方向d ，都有d r v f ( x + ) 0 ， 定义1 1 1 2 点矿s 称为平稳点，如果对于每一个可行方向d ，都有 d r v f ( x + ) 20 对于一般问题来说，平稳点并不_ 定是极小点，但是对于凸规划问题，我们有 下列定理： 定理1 1 6 若，是一个在包含s 的开集内连续可微的凸函数，并且s 是一 个凸集，则z + s 是一个全局极小点，当且仅当z 是一个平稳点 定理1 1 7 凸函数，：s _ r ( 其中s 形是凸的) 的每一个局部极小点 也是全局极小点 定义1 1 1 3 凸集s 边界上的点z 称为一个极点，如果不存在互异的两点 z l ，x 2 s ，使得z = a z l + ( 1 一a ) x 2 ，0 a ，( z ：) ，存在一条从z 到z ； 的下降路径。 若z ；是f ( x ) 的局部极大点，则- f ( x ) 在局部极小点z ；处的盆谷称为f ( x ) 在局部极大点z ：的峰。 定义1 2 2 设z ：和z ；是函数f ( x ) 的两个不同的极小点。如果，扛：) ，( z ；) ，则称在z ；处的盆谷磁比z ；处的盆谷b ；低，或称b ；比彩高。 一般使用填充函数方法还要求假设1 2 2 或假设1 2 3 。 假设1 2 2 f ( x ) 只有有限个极小值点 假设1 2 3 f ( x ) 只有有限个极小值。 孤立点z ：处盆谷研的半径定义为： r = i n f 忙一z 孙 x c b ；。 如果，( z ) 在z ；处的h e s s i a n 矩阵v 2 ，( z ：) 正定，则r 0 。 填充函数算法由两个阶段步组成一极小化阶段和填充阶段。这两个阶段交替 使用直到找不到更好的局部极小点。在第一阶段里，可以用经典的局部极小化算 法如拟牛顿法拟牛顿方法 3 0 ，5 3 ，5 8 l ，梯度投影法 7 7 ，8 2 】和共轭梯度法【9 6 】等， 寻找目标函数的一个局部极小值点z ：。然后进入第二阶段，主要思想是以当前极 小点z ；为基础定义一个填充函数，并利用它找到z ：，使得 f ( x ) 0 。 他们注意到这个函数存在如下缺点： 函数中的这两个参数相互依赖，而且在算法执行中我们不知道这两个参数如何 适取，使算法的实现产生困难。 由于受到指数项e x p ( 一且三号韭) 的影响，当p 小或忙一z + 0 大时，尸( z ，z + ) 和 v p ( x ，z ，) 变得很小，从而产生假的平稳点。 p ( z ，z ) 只在线上存在极小点，凶此算法实现很困难。 x 为有界闭箱，事实上不是真正无约束全局极小化问题。 为了克服上述缺陷，葛和秦在 1 8 1 给出了七个填充函数： 讯一 萨南e x p ( 一宇) ， g ( z ，x + l ，r ，p ) = 一p 2l o g r + ，( z ) 】一0 z z ：1 1 2 ， 0 ( z ，z ：，r ，p ) = 一p 2l o g r + ，( z ) 】一i i z z 训， q ( x ，z ：，a ) = 一【，( z ) 一，( z ；) 1e x p ( a i i x z ；1 1 2 ) ， q ( x ，x 1 ，a ) = - f ( x ) 一，( z ：) 】e x p ( a i i x z 7 1 1 ) ， v e ( z ，z ：，a ) = 一v f ( x ) 一2 a f ( x ) 一，( z ：) 】( z z ：) ， v 啻( z ，z ：，a ) = - v f ( z ) 一a 【，( z ) 一，( z ；) 1 i ；三 斋 他们指出后四个函数是较好的填充函数。l i u 在文献 s o ( 9 o m ) 中给出一个函数以 克服上述填充函数的缺陷： h ( z ，z ：，口) = 五玎f ；了犏一口i i z z ：0 2 ， 其中a 充分大。显然，这里要求1 + f ( z ) 一，( z ：) 0 。 1 1 上海大学博：学位论义 葛和秦( 1 9 9 0 ) 在文【2 2 】中提出了另一类关于前置点铷的填允函数，其定义 为： 定义1 2 4 j 若矿三( p ) ，则在s t = z x ：f ( x ) ，( z ) 上除了 x o s l 是t ( x ，x + ) 的极小点外，不存在其他平稳点 2 若岛= z x ：y ( x ) 0 ，0 h 0 充分大。 之后l u c i d i 和p i c c i a l l i ( 2 0 0 2 ) 在文【5 2 j 中进行了更为深入的讨论。并给出了 以下填充函数： v ( z ，a ，h ) = 叩( 1 l x x o t l ) 妒( a f ( x ) 一f ( x * 1 ) + 】) 这两个定义中都假定l i m ( x ) = + o o ，f c 2 ，( p ) 的局部极小点的个数为 $ o 。 有限个。这类函数的缺陷是，在算法实现中，总是在s l 上进行极小化求解，有可 能老是找到x o s 。 在各种文章中对填允函数的定义有所不i 可。尤其在文献 2 0 l 的定义中，条件 ( 3 ) 是很难实现的，已有很多文献做了改进。如 8 7 】中对填充酾数的定义进行了改 进，设z ；是f ( x ) 的一个局部极小点： 定义1 2 5 函数p ( z ，z ：) 称为( x ) 在局部极小点z ：处的填充函数，如果满 足： ( 1 ) z ：是p ( x ，z ：) 的一个严格局部极大点，y ( x ) 在点z ：处的盆谷b ；成为 p ( x ，z ：) 的峰的一部分。 ( 2 ) p ( x ，z ：) 在比b ；高的盆谷里没有稳定点。 ( 3 ) 如果存在比研低的盆谷匝，则在z ”和z ：的连线上极小化p ( z ，z ：) 得到极小点一历，其中，( z ；，6 ) 是在z ；的邻域，z ”( z ；，6 ) 1 2 上海大学蹲：l 学位论义 并给出了一个性质较好的函数，如文献【8 7 1 中定义的 p ( z ，z ：，p ，p ) = ，( z ：) 一m i n f ( x ) ，( z ：) 】一p l l x z ：| 1 2 + u m a x 0 ，f ( x ) 一，( z ：) 】) 2 该文章的另一特点是他们对填充函数的迭代搜索方法进行了详细的讨论，得到了计 算方法上的一些结论。进一步他们把改进后的填充函数用于求解非线性整数规划， 建立了一个近似算法，从而为求解非线件整数规划提供了一个途径。参见 5 1 ，8 5 1 等。 近来，我们对填充函数的定义又作了改进： 定义1 2 6 函数p ( x ，z ：) 称为f ( x ) 在局部极小点z ：处的填充函数，如果满 足： ( 1 ) 3 7 ；是p ( z ，x 1 ) 的一个严格局部极大点 ( 2 ) 对任意的z s 1 ，有v p ( x ，z ；) 0 ，这里s l = zf ( x ) 厂( z ：) ，z x z ： 。 ( 3 ) 如果z ：不是全局极小点，那么p ( z ，z ：) 一定在= zif ( x ) 0 和7 满足0 0 为一个t i c , j , 的数。 上海大学博士学位论义 图1 2 2 ：f ( x ) = x s i n x 和乃( z ，z ) ，t 2 ( x ，z + ) ，其中q = 1 0 0 0 ，r = 0 0 0 1 。 2 对任意z s l = z x ：f ( x ) f ( x ) ) ，v t ( z ，z + ) 0 3 若岛= z x ：f ( x ) 0 ，z o 隹x ，且对所有z x ，满足忙一x o l i l 。 针对于函数f ( x 1 = x s