（运筹学与控制论专业论文）解决互补问题的一种随机水平值方法.pdf

2 0 0 9 上海大学硕士学位论文 摘要 作为一类新的数学模型，互补问题于1 9 6 4 年在美国r w c o t t l e 的博士学位论 文“n o n l i n e a rp r o g r a m sw i t hp o s i t i v e l yb o u n d e dj a c o b i a n s ”中被提出来它是指 包含的两组决策变量之间满足的一种“互补关系”，c o t t l e 与导师g b d a n t z i g 教 授( 著名的运筹学家、。线性规划之父”) 当时就指出。线性优化和二次优化问题 都是线性互补的特例随着社会的不断发展和数学学科在现实生活的应用逐渐显 现，最优化问题已成为一门应用非常广泛的学科它主要讨论在有限种或是无限 种可行方案中挑选出最优的方案，构造寻求最优解的计算方法，并研究这些方法 的理论性质及实际的数值表现最优化问题广泛见于科学研究、国防、工程、管理 、经济、金融等重要领域，规模越来越大的优化问题也得到了较好的解决，有关该 问题的方法性研究具有非常重要的实际意义 本文中利用常见的n c p 函数将互补问题转化为一般的最优化问题，并考虑用 一种新的全局优化的方法对转化后的最优化问题进行求解： 该方法中我们利用一类重要的n c p 函数- - f i s c h e r - b u r m e i s t e r 函数( 记为f b 函数) 将非线性互补问题转化为一个优化问题，这一选择主要基于f b 函数的良 好性质针对满足l i p s c h i t z 性质的目标函数构造了一种新的随机型水平值逼近方 法算法中我们引进重要抽样的思想和相对熵的概念，其有效结合，使得在每一次 迭代过程中的样本点都得到了很好的更新，无论在算法的收敛性以及数值结果上 都验证了该算法的有效性 本文共分为六章：第一章介绍了互补问题的研究状况及本人的工作情况；第 二章中给出了互补问题的主要模型及其与优化问题的关联性；第三章介绍了有关 方法的相关基本概念；第四章讨论了一种新的实现算法及算法的收敛性；第五章 为本文的结论和展望，事实上，基于本文的方式，亦可考虑互补问题的新的等价形 式，以及利用其它有效的优化方法来求解，并可对所得结果进行比较；最后附上本 方法的实现程序，可以考虑对更多的实际例子进行验证 关键词：非线性互补，线性互补，n c p 函数，全局优化，随机型水平值逼近，算 法收敛性 2 0 0 9 上海大学硕士学位论文 i i a bs t r a c t a san e wk i n do fm a t h e m a t i c sm o d e l ，c o m p l e m e n t a r yp r o b l e mh a sb e e ne a r l yp u t f o r w a r db ya na m e r i c a n r w c o t t l ei nh i sd i s s s e r t a t i o nf o rt h ed e g r e eo fd o c t o ri n1 9 6 4 ， w h o s es u p e r v i s o ri st h ef a m o u sp r o f e s s o r ，g b d a n t z i g ，a n dw h oi sa l s of a m o u sa st h e f a t h e ro fl i n e a rp r o g r a m m i n g a n dm e a n w h i l e ，b o t hc o t t l ea n dd a n t z i gh a sp o i n t e do u t t h a t ：l i n e a ro p t i m i z a t i o na n dq u a d r a t i co p t i m i z a t i o na r eo ft h el i n e a rc o m p l e m e n t a r y p r o b l e m s n o w a d a y s ，o p t i m i z a t i o nh a sb e e nac o m p r e h e n s i v ed i s c i p l i n ew h i c hc o n c e n - t r a t e so nc o n s t r u c t i n ga n df i n d i n ge f f e c t i v eo p t i m i z a t i o nm e t h o d s ，t h e np i c k i n go u tt h e m o s to p t i m a lr e s u l tf r o ma l lt h ef e a s i b l es o l u t i o n s i nf a c t ，a sar e s u l to fi t sa p p l i c a t i o n i n c l u d i n ge n g i n e e r i n g ，m a n a g e m e n t ，n a t i o n a ld e f e n s e ，e c o n o m i c sa n df i a n c i a le t c f i e l d s ， m o r ea n dm o r eh u g eo p t i m i z a t i o np r o b l e m sh a sb e e ne f f e c t i v e l ys o l v e d t h e r e f o r e ，t h e r e s e a r c ho nt h i sa s p e c tp l a y sam o r ea n dm o r ei m p o r t a n ts i g n i f i c a n c ei nt h er e a ls o c i e t y i nt h i st h e s i s ，w eu t i l i z et h ec o m m o nn c pf u n c t i o nt oc o n v e r tt h ec o m p l e m e n t a r i t y p r o b l e m si n t oo p t i m i z a t i o np r o b l e m ，t h e np u tf o r w a r da ne f f e c t i v eo p t i m i z a t i o nm e t h o d s t os o l v et h ec o r r e s p o n d i n gp r o b l e m s ，w h i c hi n c l u da l g o r i t h md e s i g n i n g ，f e a s i b i l i t ya n a l y s i s a n dn u m e r i c a lr e s u l t sc o m p a r i s o n t h em a i ni d e ai s ： w ei n t r o d u c ea ni m p o r t a n tn c pf u n c t i o n - - f i s c h e r b u r m e i s t e r ( n o t e da sf b ) f u n c - t i o nt oc o n v e r tt h en o n l i n e a rc o m p l e m e n t a r yp r o b l e mi n t oag l o b a lo p t i m i z a t i o np r o b - l e m t h e nw ec o n s t r u c tan e ws t o c h a s t i cl e v e l v a l u ea p p r o x i m a t i o nm e t h o di nw h i c hl i p - s c h i t zp r o p e r t yi sn e c e s s a r yf o rt h eo b j e c t i v e i nt h ea l g o r i t h m ，w eu t i l i z ea ni m p r o t a n t s a m p l i n ga n dc r o s s - e n t r o p ym e t h o da n dt h er e l a v a n tr e s u l t sa r eg i v e n t h et h e s i si so r g a n i z e da sf o l l o w s ：s o m er e l a t e db a s i ck n o w l e d g e s ，c o m p l e m e n t a r i t y p r o b l e mm o d e l sa n di t sr e l a t i o n s h i pw i t ho p t i m i z a t i o np r o b l e ma r ei n t r o d u c e di nt h ef i r s t t h r e ec h a p t e r s ；i nt h ef o u r t hc h a p t e r ，w ep u tf o r w a r dt h en e ws t o c h a s t i cm e t h o ds o l v i n g t h ee q u i v a l e n to p t i m i z a t i o np r o b l e mo ft h eo r i g i n a lc pp r o b l e m ；i nt h el a s tt w op a r t sw e g i v es o m eo t h e rd i s c u s s i o n si nt h ef u t u r ea n dt h ep r o c e d u r eo ft h ea l g o r i t h m k e yw o r d s ：c o m p l e m e n t a r yp r o b l e m ，n c pf u n c t i o n ，g l o b a lo p t i m i z a t i o n ，s t o c h a s - t i cl e v a l - v a l u ea p p r o x i m a t i o n ，a l g o r i t h mc o n v e r g e n c e 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作除了文中特 别加以标注和致谢的地方外，论文中不包含其他人已发表和撰写过的研究成果 参与同一工作的其他同志对本研究所做的任何贡献均已在论文中作了说明并表示 了谢意 签名： 本论文使用授权说明 日期： 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有权保留论 文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分 内容 ( 保密的论文解密后应遵守此规定) 签名：导师签名；翌盘。煎日期： 第一章引言 1 1 问题的研究背景 互补问题是运筹学与计算数学的一个交叉研究领域，近些年它在力学、工程、 经济、国防等许多实际部门的广泛应用，使得它成为数学规划中的一个日益热门的 研究课题互补问题最早首先由著名的运筹学家、数学规划的创始人g b d a n t z i g 和他的学生r w c o t t l e 于1 9 6 3 年提出次年，c o t t l e 在他的博士论文中第一次提 出求解互补问题的非线性规划算法 1 0 】互补问题在当时的学术界引起了一阵热 潮c o t t l e 和d a n t z i g 在当时都曾指出：线性规划与二次规划都是线性互补问题的 特例【9 1 2 】而c o t t l e - d a n t z i g 在1 9 6 8 年的文献中更指出：双矩阵对策问题也是线 性互补问题的一特例【1 1 】线性互补问题还包括了最优停止问题和市场均衡问题 等非线性互补问题、混合互补问题和隐互补问题包括了更多的数学问题，如一般 非线性规划的k k t 条件是混合互补问题的一特例 互补问题是指在其中包含的两组决策变量之间满足一种。互补关系”一般地， 该问题可写成如下形式： 令f ：解一舻为由解到形的一映射，相应的互补问题是； 求解不等式组 表示为c p ( f ) z 0 ，f ( x ) 0 x t f ( x ) = 0 1 2互补问题的研究现状 ( 1 - 1 1 ) ( 1 1 2 ) 互补关系反映了实际应用当中广泛存在的一种关系作为一类新的数学模型， 。互补问题”在初期曾被称为“拼合问题”( c o m p o s i t ep r o b l e m ) 、。基本问题” ( f u n d a m e n t a lp r o b l e m ) 或“互补转轴问题”( c o m p l e m e n t a r i t yp i v o tp r o b l e m ) 等互补问题是从线性规划与非线性规划的推广而形成的，所以它的算法研究与 1 2 0 0 9 上海大学硕士学位论文 2 可解性研究一样，受到了研究者的重视关于互补问题的研究一般分为理论和算 法两方面，前者主要研究界的存在性、唯一性、稳定性与灵敏度分析，以及互补问 题与其他数学问题的联系等；后者则主要建立有效的求解方法及相应的算法理论 分析至2 0 世纪8 0 年代中后期，经过二十余年的努力，在理论与算法方面已取得 了比较丰硕的成果关于1 9 9 0 年以前的工作，可见h a r k e r 和p a n g 的综述性文章 【1 8 】以及该时期的优秀专著由于互补问题与最优化、变分不等式、平衡问题等数 学分支的紧密联系，以及在科技与经济方面的广泛应用，互补问题显示着越来越 重要的地位，这也激励了人们对其理论与算法的进一步研究，在近十余年的时间 里，人们不仅改进与丰富了互补问题的理论研究而且还提出多种有效算法对于 互补问题的研究包括有：可解性、解集的拓扑性质、稳定性、误差界以及不同类型 的互补问题的算法研究近年来对于互补问题的研究方法主要有：内点法、非光滑 牛顿法、光滑牛顿法等( 【7 】【1 4 】【2 6 】【2 9 】【驯【3 9 】【4 0 】【4 1 】【5 1 】【5 2 】【5 7 】) ；经典的算法 有：不动点再生理论和投影法及相应的最新改进方法，可见【2 0 】【2 2 】 2 7 】【5 6 】【5 8 1 特别地，近年来越来越多的研究者们考虑到互补问题与最优化问题的紧密的 联系，利用最优化理论或方法解决某些互补问题，其主要思想为；选择合适的n c p 函数将原互补问题转化为一类相应的最优化问题，再寻求有效的方法对转化后的 优化问题进行求解而目前对于全局优化问题的求解方法分为确定性方法和随机 型算法，常见的确定性算法有：积分水平集算法、外逼近算法、内点法、割平面算 法、分支定界算法、填充函数法、隧道函数法等，详见【4 】【1 7 】【3 1 】【3 6 】【4 3 】【5 0 】【6 0 】； 随机型方法有：二阶段算法、随机搜索方法、启发式随机算法等，可见【3 】【5 】【1 3 】 【3 5 【5 0 】 5 3 】 1 3 本文的工作 本文中讨论互补问题c p ( f ) ，根据其中f 的性质选取一类重要的n c p 函数 f b 函数将原问题转化为相应的全局优化问题，再引进了一类新的随机型水平值 逼近方法对该优化问题进行求解该方法的应用主要受启发于r y r u b i n s t e i n 关 于利用相对熵方法解决连续的组合优化问题的文章【4 4 】，这也是相对熵方法最早 被应用于解决优化问题的先例在该方法中，我们充分利用了重点抽样方法和相对 熵算法的有效结合，每次进行下一轮迭代之前都考虑将对应的密度函数族更新， 2 0 0 9 上海大学硕士学位论文 3 并重新确定水平集瓯，从而保证了算法的有效性和渐进收敛性，文中附有本算法 的程序以及实际算例，也充分说明了该方法的有效性和精确性 第二章互补问题与数学规划的联系 2 1 互补问题的模型 根据互补问题中变量所满足的条件不同，以及互补关系的不同形式，互补问题 被区分为若干类型其中包括有：线性互补问题( t h el i n e a rc o m p l e m e n t a r i t yp r o b - l e m ) 、竖直线性互补问题( t h ev e r t i c a ll c p ) ，水平线性互补问题( t h eh o r i z o n t a l l c p ) 、广义线性互补问题( t h ee x t e n d e dl c p ) 、非线性互补问题( t h en o n 5 n e a r c o m p l e m e n t a r i t yp r o b l e m ) 、混合非线性互补问题( t h em i x e dn c p ) 、隐互补问题 ( t h ei m p l i c tc o m p l e m e n t a r i t yp r o b l e m ) ，非线性微分互补问题( t h en o n l i n e a rd i f - f e r e n t i a lc o m p l e m e n t a r i t yp r o b l e m ) 、集值互补问题( t h es e t v a l u e dc o m p l e m e n t a r i t y p r o b l e m ) 等等并且这些问题在实际生活中的应用也是相当广泛的，例如双矩阵 对策和多矩阵对策( 可转化为线性互补问题) 、纯交换的竞争经济的均衡、静态交 通流均衡问题和具有生产和投资的经济均衡( 可转化为一般的非线性互补问题) 、 一般的价格均衡问题( 可转化为求解一混合互补问题) 均可以寻找到其对应的互 补问题的模型 接下来将介绍几种常见的互补问题，首先约定t 以舻表示n 维欧氏空间， 磁表示舻的非负象限，舻中的矢量均为列矢量，x t y 表示矢量z 与y 的内积， ，表示矢量或矩阵的转置 2 1 1 非线性互补问题 令f ：舻_ 印为由r n 到舻的一映射，相应的非线性互补问题是指：求矢 量z 舻，满足 z 0 ，f ( x ) 0 ，z 1f ( x ) = 0 ( 2 1 1 ) 且将该非线性互补问题记为n c p ( f ) 将上述非线性互补问题进行推广可以得到 广义非线性互补问题的一般形式： 令g ，h ：舻一舻是两个映射，广义非线性互补问题表示为：求z r n ，满 4 2 0 0 9 上海大学硕士学位论文 5 足 g ( z ) 0 ，h ( z ) 0 ，g ( z ) t 1 4 ( x ) = 0 且将该问题记为c p ( g ，h ) 由此可见，当g ( z ) = x 时，该问题即转化为了一般 的非线性互补问题 2 1 2 线性互补问题 当映射f 是线性映射时，即f ( z ) = m x + q ，m 舻跏是一n n 实矩阵， q r n 是一n 维矢量，则上述互补问题化为线性互补问题即寻求一矢量。r n ， 满足 z 0 ，m ( x ) + q 0 ，x t ( m x 十q ) = 0 ( 2 1 2 ) 并将其记为l c p ( m ，q ) 若引入矢量y 舻，y = m x + g ，则变量x i 与y i 满足条件x i 0 ，y i 0 ，x i y i = o ，i = 1 ，n 这表明了两组变量 觋) 与 y i 满足互补关系由于线性互补问题 来源于线性规划和二次规划，现考虑二次规划( q p ) ： m i n q ( z ) = ，卅互1 z t 啦 s t a x b ，x 0 ( 2 1 3 ) ( 2 1 4 ) 其中q r n x n 为对称矩阵，a 舻跏，若q = 0 ，则二次规划退化为一个线性规 划设z 是二次规划( q p ) 的局部最优解，根据k a r u s h k u h n t u c k e r 最优性定理， 存在l a g r a n g e 乘子矢量，满足k k t 条件： u = c + q z a t 0 z o z t 札= o ( 2 1 5 ) i = 一b + a x 0 ，y 0 ，y r t ，= 0 若q 是半正定矩阵( 如q = 0 ) ，则q ( x ) 为凸函数，条件( 2 1 5 ) 也是( q p ) 的 全局最优解的充分条件定义： m ：= q a a 0 r ，g ：= 三 lll 一6i 条件( 2 1 5 ) 即转化为一线性互补问题l c p ( m ，q ) ，其中包含的矩阵m 是一个 双对称矩阵，所以任意一个二次规划的k k t 条件等价于一线性互补问题，而且 2 0 0 9 上海大学硕士学位论文 6 lu o ，日( 伽，t ，) o ， 丁日( 伽，口) = o 般躲辫押嘶) _ 0 亿 ， 1 ：芸i 兰；z 0 a 。 厶l 2 0 0 9 上海大学硕士学位论文 7 令n l = 礼+ f ，n 2 = 仇，取伽：= ( z ，p ) ，t ，：= 入，且 g c 伽，t ，：= v ， ) + 查心v 篡于十墨九v 优( z ) 则k - k t 条件( 2 1 7 ) 可化为一混合非线性互补问题 2 2互补问题的优化形式及n c p 函数 非线性互补问题是一类新的数学模型，它包含的两组决策变量之间满足一种 “互补关系”通过了解互补问题与数学规划的联系，若能够有效地利用最优化中 的某些方法来解决互补问题，则能更好地研究互补问题的求解等问题近期的研 究可参见【1 】本节中主要讨论如何将一般的互补问题转化成某些情况下的等价形 式一一最优化问题，其中涉及到一类重要的概念，即n c p 函数及其相关性质 我们考虑经典的非线性互补问题( 记为。n c p ) 求一矢量z i t ，满足 r ( x ) 0 ，z 0 ，x f ( x ) = 0 ， 其中f ：舻_ 舻是由舻到舻上的一个映射该问题具有许多的现实意义，蕴含了 很多数学问题，例如：线性规划问题，非线性规划问题的一阶k a r s h k u h n t u c k e r 条件以及在金融、工程、经济等方面的实际问题 近年来，对于非线性互补问题的研究均考虑通过一些n c p 函数将其转化为无 约束或是有约束的最优化问题来处理 2 1 3 4 】 令孟舻是互补问题n c p ( f ) 的解，即有 雪0 ，f ( 牙) 0 ，牙t e ( 孟) = 0 ，t = 1 ，佗 显然这等价于孟满足 m i n ( 孟i ，只( 牙) ) = 0 ，i = 1 ，n 上一组等式可记为r a i n ( 童，f ( 孟) ) = 0 ，这里m i n ( 孟，f ( 牙) ) 是一矢量，其分量是 m i n ( 黾，e ( 孟) ) = 0i = 1 ，礼，所以互补问题n c p ( f ) 等价于求解方程组 2 0 0 9 上海大学硕士学位论文8 m i n ( 牙，f ( 牙) ) = 0 ，一般地m i n ( a ，b ) 被称为“m i n 函数”下面介绍有关n c p 函数的定义： 定义1 ：若函数妒：r 2 _ r 1 对于任意的( a ，6 ) t r 2 ，有 妒( n ，b ) = 0 骨a 0 ，b 0 ，a b = 0 ( 2 2 1 ) 则该函数矽被称为“n c p 函数” 显然，m i n 函数是一n c p 函数，它被记为蛎n 对于任意一n c p 函数妒， 互补问题n c p ( f ) 可等价地转化为方程组 圣( z ) ：= 妒( 甄，f 1 ( z ) ) 妒( z n ，r ( z ) ) ( 2 2 2 ) 令妒：r 2 一r 1 是一n c p 函数，互补问题n c p ( f ) 的求解可借助于映射圣( z ) ( 见 式( 2 2 2 ) ) 转化为求解以下优化问题的全局最优解： z m 舻i n 懈) i i 2 = 地，只( z ) ) 2 ( 2 2 3 ) 并且此优化问题的最优值为零函数( z ) 1 1 2 被称为n c p ( f ) 的一种“价值函数” 定义2 ：令f ：x2 群一舻为一映射，x 为一闭集，非负函数p ：x 一磷 被称为n c p ( f ) 的一个价值函数，如果点牙是n c p ( f ) 的一个解，当且仅当牙是 以下优化问题的全局最优解： r a i n p ( z )( 2 2 4 ) s t z x 且p ( 牙) = 0 更确切地说，价值函数在x 酽上的全局最小值和原互补问题n c p 的解集是一 致的，因此为了构造一个价值函数，最有效的方法就是利用该n c p 函数的笛卡尔 结构性质 令 坼卜宁吐茹只甸那 亿2 劫 2 0 0 9 上海大学硕士学位论文 9 则式( 2 2 4 ) 成为： r a i n x t f ( x )( 2 2 6 ) s t z 0 ，f ( x ) 0 并且孟f ( 牙) = 0 所以函数x t f ( x ) 也是一种价值函数当f 是线性映射时，优化 问题( 2 2 6 ) 是一个二次规划，值得一提的是价值函数不一定是凸函数，也不一 定是可微的，此特点对研究线性互补问题的解的性质起了重要作用 在转化后的优化问题( 2 2 3 ) 式中惮( z ) 0 2 具有许多良好的性质如连续可微 的等等，可见【2 3 】 4 8 】 下面介绍几种常用的重要n c p 函数及其简单性质： 1 事实上m i n 函数有另一种表达式，它在互补问题的算法的设计中更为有用s 1 妒m i n ( n ，b ) = 去( n + b 一 ( 口一6 ) 2 ) 但同时应注意到，r a i n 函数的不足之处是在a b = 0 上的点均不可微，这使得函 数m i n ( x ，f ( z ) ) 不可微以m i n 函数为基础推广该函数； 妒m i n ( n ，b ) ：= m i n ( a ，a b ) 其中n 0 是一常数，有效地应用到投影方法和非光滑牛顿方法等 2 m a n g a s a r i a n s o l o d o v 函数( m s 函数) 妒m s ( n ，6 ) = n 6 + ( 去) ( ( n q 6 ) 辜一n 2 + ( 6 一q n ) 车一b 2 ) = n 6 + ( 去) ( m a x o ，n q 6 ) 2 一n 2 + m a x o ，6 一n n 】_ 2 “2 ) ， 其中q 1 ，( ，) + ：= ；( 1 ，l4 - ，) 可证明该n c p 函数在r 2 非负且连续可微，见参 考文献【2 1 】最初以该函数作为基础的价值函数是由m a n g a s a r i a n 和s o l o d o v 提 出的，并以他们的名字命名该函数，见【3 4 】 3 f i s c h e r b u r m e i s t e r 函数( f b 函数) ： 2 0 0 9 上海大学硕士学位论文 1 0 该函数的讨论最初是由f i s c h e r 和b u r m e i s t e r 奠定的，他们也由此得到函数的命 名近年来惦b 函数赢得了许多研究者的青睐和广泛的应用，其具有一些较好的 性质成为了一类非常重要的n c p 函数( 可见【6 】【1 6 【3 3 】【4 8 】) 事实上，该函数 函数具有下述良好的性质，即： 定理1 ：c f b ( a ，b ) 是一凸的n c p 函数，且在任一点( n ，6 ) t 0 为可微，妒刍日 在平面上任意点为连续可微 证明：由于妇日( 口，b ) ：= 正珊一( 0 4 - 6 ) ，v ( n ，6 ) t r 2 ， 1 ) 若a 0 ，b 0 ，a b = 0 ，显然有妒f b ( 口，b ) = 0 反之，若惦b ( n ，b ) = 0 ，即有 正丽= a4 - b ，则有a b = 0 如a = 0 ，则b = 痧0 ，同理如b = 0 ，即n 0 即 证得妒f b 是一n c p 函数再根据凸函数的定义，可验证妇b 是一凸函数 2 ) 显然，函数妇口在( n ，b ) 0 是可微的纬b 在( a ，b ) 0 的梯度是 坼小川= 粘二= 二霪列 令v 妒刍b ( o ，0 ) ：= 0 ，易证得v 妒b 在点( 0 ，0 ) 处是连续的，所以妒；b 在r 2 中是连 续可微的 基于n c p 函数f b 函数的上述良好性质，本文中我们利用该函数将非线性 互补问题转化为与其等价的优化问题 因此，原非线性互补问题n c p ( f ) 可以改写成如下的最优化问题： 剌m i n m ) 5 恕地，只( z ) ) 2 ( 2 2 7 ) 前面我们已经强调文中所讨论的目标函数均具有l i p s c h i t z 性质，其中妒( 甄，只( z ) ) 由b f b ( a ，b ) 替代，x = zz i 0 ，e ( z ) o ) 定义3 ：若函数，( z ) ，对妇1 ，x 2 x ，jl 0 ，满足 i f ( x 1 ) 一，( z 2 ) i l l l x l z 2 | l ， 其中”0 表示e u c l i d e a n 范数，则称函数( x ) 在x 上满足l i p s c h i t z 条件 第三章随机方法的预备知识 3 1全局优化的常用方法 最优化问题的一般可表述为： m l n s 芒 ，( z ) z x 其中z = ( z 1 ，z 2 ，扩) x 三舻，f ( x ) 是定义在x 上的实值函数本文中我 们讨论极小值的情形，即 r a i n ，( z ) x e x 如果对于所有的z x ，存在z x ，满足f ( x + ) f ( x ) ，我们称z + 是问题的 全局最小值当x = 舻时，称上述问题为无约束全局最优化问题；当x = z 舻：吼 ) 0 ，i = 1 ，2 ，p ；h j ( z ) = o ，歹= p + 1 ，p + 2 ，m ) cr n 特另i j 地，当z 为连续变量，f ( x ) 为连续函数时，称该问题为连续全局最优化问题 连续全局优化问题在经济、工程等现实领域中的应用日益广泛，而对于全局 优化的求解方法研究却较局部求解方法存在更大的困难，其主要原因在于目标函 数可能具有多个极值及缺少有效的全局优化判断准则现存有效的局部方法，如 牛顿法、拟牛顿法等等往往是无效的尽管也存在不少的全局优化算法在现实计 算中起着重要的作用，但是却总会存在某些缺陷，这是在解决实际问题时需要尤 为值得关注且难以回避的环节 事实上，对于全局最优解问题，通常可以采用如下思想来求解： 一类是通过局部最优点来寻求全局最优点其典型代表有填充函数法和隧道 函数法【5 0 5 a 5 5 6 0 】，这类方法主要是希望通过已经达到的一个局部最优解，继 续搜寻另一局部最优解，不断地进行比较和更新此时，只要最优问题中目标函数 ( x ) 在x 局部最优有限，则通过此类方法一定能在有限次的搜寻之后得到原问题 的最优解，即全局最优但是该方法的困难之处在于很难跳出问题的局部最优， 填充函数法通过构造一类辅助函数，将原问题转化，再对转化后的新问题进行扰 2 0 0 9 上海大学硕士学位论文 动，而这种扰动是不可预测的，因此难以判断所得到的局部最优是否为原问题的 全局最优局部方法的优势在于下降速度比较快，但是所得到的最优点有可能仅 仅为局部的最优点 为了避免局部优化方法的不足之处，研究者们不断地去寻找全局最优方法，全 局最优化的具体方法主要可分为确定型方法和随机型算法：常见的确定性方法有 割平面法、填充函数法、隧道函数法( 见 3 6 】【4 3 】【6 0 】) 等等；此处我们不做讨论，如 需更深入了解，可见相关文献 3 1 】【3 7 】【5 5 】【5 4 】等随机型算法包括有；m o n t ec a r o l 方法( 【3 8 】【4 6 】) 、纯粹随机型算法、现代启发式算法( 模拟退火方法、遗传算法 【1 9 】【2 5 】【4 2 】【5 9 】) 等等由于在现实生活中的许多不确定因素，这种特性较多地出 现在经济和金融领域当中，从而随机型算法的研究逐渐吸引了众多研究者，引导 着随机型方法快速地发展 本文中提出了一种新的随机型水平值逼近算法，在基本的随机型算法中引进 了重点抽样的方法和相对熵的概念( 可见( 1 3 l 【1 5 4 4 4 5 1 ) ，该方法特点在于每一 次新的迭代均对水平值进行更新，并且对取样密度函数进行相应的更新，解决了 传统的水平集方法中投点难，而水平值难以确定的问题，从而保障了算法的高效 性，并且证明了该算法的渐进收敛性 3 2 有关随机的基本理论 1 基本知识： 定义1 ，一个实验或随机试验所有可能结果的集合称为样本空间，通常用 s ，q ，u 来表示变量x 为q 上的实值函数，即x ：q r 称为一随机变量随 机变量一般用大写拉丁字母或小写希腊字母( 如：x ，z ，7 ) 来表示 从上面的定义注意到，随机变量实质上是函数，但不能把它的定义与变量的 定义相混淆如果随机变量x 的取值为有限个的或者是可数无穷尽的值x = x 1 ，x 2 ，z n ，则称x 为离散随机变量；如果x 由全部实数或者由一部分区 间组成，x = x l a z 6 ，一0 0 a b + 。o 则称x 为连续随机变量，连续随 机变量的值是不可数及无穷尽的 定义2 ：函数p r 称为概率函数，如果满足下列三个条件： 1 ) p 7 ( q ) = 1 2 0 0 9 上海大学硕士学位论文 1 3 2 ) 对于任何事件e ， 0 p r ( e ) 1 3 ) 对任何两两交集为空的事件集召， p r ( ue ) = p r ( e ) e b e b 定义3 ：对妇r ，定义f ( x ) = p r ( x z ) ，称之为随机变量x 的分布函 数f ( x ) 若存在一个函数l ( x ) ，对所有的一o o z + o 。，均有 ，口 f ( a ) = f ( t ) d t ，一 成立，则称函数y ( x ) 为函数f ( z ) 的密度函数，且( x ) = f ，( z ) 在区间【a ，b ) 内 的概率为 p r ( a x u ( 码) j v ( o ) d u c l ) , j u ( 2 ) j u ( b 1 ) j u ( b ) j 则停止迭代七= 白；否则令南：= + 1 ，转步骤2 重新开始迭代 2 0 0 9 上海大学硕士学位论文 1 8 3 3 基本算法 一般来说，相对熵算法包含下列迭代思想： i ) 按照某种分布随机地抽取一个样本； 2 ) 更新分布中的参数，一般来说为所选取的概率密度函数中的参数，不断地优化 下一步迭代中产生的随机样本 1 本文中的相对熵算法 求解连续全局优化问题 m i n 妒( z ) z 舻。、 我们采用基于分布密度函数n ( x ，p ，盯2 ) 的相对熵方法： 令g ( x ，u ) = n ( x ，p ，盯2 ) 为n 维坐标正态分布， 忡m 确= 丙采唧( 一壹i = l 簪) ( 3 3 1 ) ( 2 7 r ) n 兀吼 “ 其中均值向量p = ( p l ，p 2 ，) 与方差向量盯= ( a l ，盯2 ，) 中的各个分 量均为相互独立的此时的c e 算法为： 步骤1t 选取样本容量及系数n ( 0 p 1 ) ，令优良样本数n = p n ， 参数口o = ( 硒。，口0 2 ，卢o 。) ，锑= ( 铝。，施，铝。) ，令k ：= 0 ； 步骤2 ；按分布函数( z ，m ，醒) 抽取样本集x 七= x ，砖，义岛) ； 步骤3 ：分别计算妒( 肆) ，i = 1 ，2 ，选取f 个使得函数值妒( 砷) 相 对最小的样本最为我们的优良样本，记为 x ，砖，硝。) 步骤4 ：利用步骤3 中所获得的优良样本集，按照下列方式更新参数( 砒，a 2 ) 。 p 缸 - 1 j ：2 寺2 + 1 j ：= 一应七十1 ，j ) 2 ，歹= 1 ，2 ，n 硌 磷 胪沮”渊 一 一 1 一 1 一 2 0 0 9 上海大学硕士学位论文 1 9 其中 步骤5 ：磨光步骤 卢七+ 1 = a 口知+ 1 + ( 1 一a ) 应南 醒+ 1 = 凤耀+ 1 + ( 1 一仇) 耀 仇= p z ( 1 一