（运筹学与控制论专业论文）非线性互补问题的水平值估计算法.pdf

摘要 本学位论文研究非线性互补问题的水平值估计算法非线性互补问题的数学模 型是生活生产实际中许多平衡问题的数学表达形式，具有很广泛的应用，因此也受 到运筹学及其它领域个方面专家的高度重视，一直是非线性规划研究的一个重要的 研究方向 非线性互补问题的算法研究非常活跃，成果极其丰富将互补问题转化成约束 非线性优化问题来求解，是互补问题的提出者d e n t z i n g 和c o t t l e 最早的求解思想 实现这种算法思想的关键在于寻找一个好的全局优化算法，能最大范围地收敛到全 局最小点随着全局优化算法研究的深入，具有这种大范围收敛性的可实现算法已 经出现，水平值估计算法就是其中之一 本文的主要目的是将约束全局优化的水平值估计算法应用到求解非线性互补问 题，我们从理论上证明了算法的收敛性，数值实验也说明了算法的有效性本文共 分五章，按如下形式来组织第一章简要介绍非线性互补问题，包括它的广泛的应 用，求解的各种算法，特别是转化为约束全局优化问题的思想及算法第二章，我 们介绍了求解约束全局优化问题的水平值估计算法，包括算法设计基础、算法收敛 性、实现算法及其收敛性 文章的第三章，我们将约束全局优化的水平值估计算法应用于求解非线性互补 问题，描述了算法及其主要思想、步骤，证明了算法的收敛性第四章，我们用_ 些数值例子说明了算法的有效性在第五章，我们对今后的研究进行了展望 关键词：非线性互补问题；约束全局优化；水平值估计算法；大范围收敛性；应用 i i a b s t r a c t t h i st h e s i si sm a i n l yc o n t r i b u t e dt os t u d yal e v e l v a l u ee s t i m a t i o nm e t h o d | 0 rs o l v i n gn o n l 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 s 。t h em a t h e m a t i c a lm o d e lo ft h e n o n l 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 s ( h e r e a f t e rn c p ) a r et h ee x p r e s s i o no fal o to ft h e e q u i l i b r i u mp r o b l e m si np r a c t i c e ，a n di th a sb r o a da p p l i c a t i o n s ，s oi t i sm u c ha c c o u n t e d b ys p e c i a l i s t sf r o mv a r i o u sf i e l d s ，a n di t i sa ni m p o r t a n tr e s e a r c hd i r e c t i o no ft h en o n l i n e a r p r o g r a m m i n g t h er e s e a r c ho nt h ea l g o r i t h mf o rf i n d i n gt h es o l u t i o n so fn c p ，i sv e r ya c t i v e ，a n d t h er e s e a r c hr e s u l t sa r ep r o f u s e t h ei d e af o rf i n d i n gt h es o l u t i o n so fn c p , w h i c hc o n v e r t s i ti n t oan o n l i n e a ro p t i m i z a t i o np r o b l e m ( n p ) ，i sp r o p o s e db yd e n t z i n ga n dc o o t i e ，w h o a r et h eo r i g i n a t o r so fn c p w h i c hi sc r u c i a lt oi m p l e m e n tt h i si d e a ，i ss e e k i n gag o o d a l g o r i t h mf o rf i n d i n gt h eg l o b a ls o l u t i o n so ft h en o n l i n e a ro p t i m i z a t i o np r o b l e m s ，t h i s a l g o r i t h mi sr e q u i r e dc o n v e r g e n t i n gi ne x t e n s i v e n e s st ot h eg l o b a ls o l u t i o n s w eh a v et h e a l g o r i t h m sw i t ht h i sc o n v e r g e n c e ，a l o n gw i t ht h ed e e p l yr e s e a r c ho ft h eg l o b a lo p t i m i z a t i o n m e t h o d ，t h el e v e l - v a l u ee s t i m z a t i o nm e t h o di so n eo ft h e m t h em a i ng o a lo ft h i st h e s i si sa p p l i n gt h el e v e l - v a h ee s t i m z a t i o nm e t h o dt os o l v e n c p ，w ep r o v et h ec o n v e r g e n c eo ft h i sa l g o r i t h mw i t ha p p l i c a t i o nf o rn c pi nt h e o r y ，a n d i l l u s t r a t ei t se f f e c t i v i t yb yn u m e r i c a le x p e r i m e n t s t h i sa r t i c l ei sd i v i d e di n t of i v ec h a p t e r s i nt h ec h a p t e r1 w eg i v eab r i e fi n t r o d u c t i o n o nn c p ，i n c l u d ei t sb r o a d l ya p p l i c a t i o n sa n dv a r i o u sa l g o r i t h m sf o rs o l v i n gi t e s p e c i a l l y t h ei d e at h a tc o n v e r t si ti n t on pa n ds o l v ei tb uu s i n gt h ei n t e g r a ll e v e l s e tm e t h o d i nt h ec h a p t e r2 ，w ei n t r o d u c et h el e v e l - v a l u ee s t i m a t i o nm e t h o df o rs o l v i n gt h eg l o b a l o p t i m i z a t i o nw i t hc o n s t r a i n s ，i n c l u d et h e f o u n d a t i o no ft h ea l g o r i t h m ，a n di t sc o n v e r g e n c e ， t h ei m p l e m e n t a t i o na n dt h ec o n v e r g e n c eo ft h ei m p l e m e n t a t i o n i nt h ec h a p t e r3 ，w ea p p l i e st h el e v e l - v a l u ee s t i m a t i o nm e t h o df o rs o l v i n gn c p ， d e s c r i b et h ea l g o r i t h ma n di t sm a i ni d e aa n dm a i ns t e p s ，a n dp r o v ei t se o n v e g e n c e i nt h e c h a p t e r4 ，w eg i v es o m en u m e r i c a lr e s u l t st oi l l u s t r a t et h ee f f e c t i v i t yo ft h em e t h o d a t t h el a s t ，i nc h a p t e r5 ，w eg i v ec o n c l u s i o n sa n ds o m ep r o s p e c t so nt h i st o p i c k e y w o r d s ：n o n l 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 s ；g l o b a lo p t i m i z a t i o nw i t hc o n s t r a i n s ；l e v e l - v a l u ee s t i m a t i o nm e t h o d ；c o n v e r g e n ti ne x t e n s i v e n e s s ；a p p l i c a t i o n 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作除了 文中特别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写 过的研究成果参与同一工作的其他同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意 签名：日期：型鸯羔蟹 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有 权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可以公布 论文的全部或部分内容 ( 保密的论文在解密后应遵守此规定) 躲一塑嘲髀槲卅期：之塑型 非线性互补问题的水平值估计算法 第一章引言 “互补问题”作为一类新的数学模型，是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 ”中 提窦寒的，它避解决生活与生产实舔酶平衡阚题最有力的数学工具之一。菲 线性互补问题是一类重要的互补问题，一般地有如下表泳形式 茹0 ，f ( x ) 芝0 ，x t f ( x ) = 0( 1 王) 其中f ：r n 叶冗“为咒n 到自身的映射我们记非线性互补问题( 1 1 ) 为 n c p ( f ) 。 本章我们先对菲线性互补问题在生产实践与优化理论方面的应用做一个 简要介绍，然后对问题的各类解法的研究成果进行简要的回顾 1 1 生产实践中的爿# 线性互补问题。 经济与社会生活中的许多实际阍题可以用n c p ( f ) 模型来表示菲线性 互补模型是解决生活与生产实践中平衡问题最有力的数学工具之一 倒l 。纯交换的竞争经济的均衡问题： 设有耗种不同的商黼和m 个商入，他 f 购销这些商品。令珏订表示商入 i 对商品j 的初始拥有权，u = ( u f ，j = 1 ，2 ，n ) r ”，令函数d i j ( p ) 表示 商入l 对商品j 的需求懋，p = 锄，歹= 王，。，n ) 是商品的流通价格矢量。令 m h i ( p ) = 【d 玎( p ) 一u 幻】， ( p ) = ( o ) ，j = 1 ，2 ，n ) 7 ( 1 2 ) f = l 假设 nm ， = 鳓) 一雠t 鼻= 0 j = l i = l 成搬则所谓均衡问题就是寻求一组价格p j ，j f = l ，竹，满足功0 ，h j ( p ) 0 ，j = l ，2 ，牲。此问题可以转化为非线性互补问题令( p ) = - h ( p ) ，求矢 2 0 0 8 年上海大学硕士学位论文 量p r “，满足 p 0 ，) 0 ，p t h ( p ) = 0 ( 1 4 ) 例2 具有生产和投资的经济均衡： 设有m 种商品和n 种经济活动令p = p i ) r ”表示商品的价格矢 量，p t 是商品i 的价格，b = ( 6 t ) r ”表示投资矢量，b i 表示对商品i 的 初始投资d 0 ) = ( d t ) ) r “表示市场的需求函数，d ) 是在价格p 下 市场对商品i 的需求量耖i i ( y j ) r “为活动水平矢量，是活动j 的水 平，这是一个未知量 c = ( c j ) r ”表示活动的单位运行费用矢量，c j 是 活动歹的单位运行费用a = 【a i j l r ”“表示投入产出系数矩阵，a t ， 0 表示产出，a t ， 0 时，o i ( 0 + ( 0 ) 0 满足该条件的口( t ) 可以构造出许多种，由不同的口( t ) 可以再生出许多不同 的光滑方程组，然后用n e w t o n 型方法求解这些方程组，即可得到原非线性 互补问题的解为了保证求解方程组时n e w t o n 型方法具有所谓。大范围收 敛性”，w a s t s o n 建立了同伦算法( 取o ( t ) = t 3 ) ，s u b r a m a n i a n 提出了带阻尼 因子的g a u s s n e w t o n 算法( 取o ( t ) = t l t l ) 光滑方程法有很多优越性，例如具有局部超线性收敛性，有的具有大范 围收敛性，但是它们有一个共同的缺点，就是转化以后的方程组都是非线性 较高程度的非线性方程组，这样导致了理论与计算的复杂化 2 ) 非光滑方程法 为了克服光滑方程法的缺点，研究者们提出了非光滑方程法 p a n g 取口( t ) = 一0 5 t 得到下面的n c p 函数 妒1 ( o ，b ) = m i n a ，扫) ，( 1 1 3 ) 非线性互补问题的水平值估计算法 将j 摹线性互补闻蹶转化为下暖的菲光滑方程组 h a r k e r 稳x i a o 考虑了另一种荐生菲巍浮方程组 ( 1 。王4 ) h i ( x ) = f ( m a x 0 ，髫) ) + r a i n 0 ，z ) = 0 ( 1 1 5 ) 焉f e i c h e r 萼l 入了一个结擒简单又奇持鲢n c p 舔数 得鲥爵生菲光滑方程组 日3 ( z ) = 0 ( 1 1 7 ) 恐霉) 具有很好鹩性覆，弓l 起了人们泛的兴趣 c h e n c h e n k a n z o w 摄如n c p 函数 妒a ( a ，婶= a - 镪( 8 ，妨+ ( 1 一a ) 8 + 沁，a ( 0 ，1 ) ，( 1 。1 8 ) 其中o + = m a x 0 ，n ) ，得到系列漂亮的理论与数值结果 3 ) 可微的无约束优化法 这类方法就燕把互补简题转纯为一个与之等价酶可微无终束优化麓题， 然后用某种大范围或n e w t o n 型方法求解 m a a g a s a r i a n 积s o l o d o v 首先给出可微的n c p 函数 妒m s ( n ，6 ) = n 6 + 壶( m 燃 o , a - a b 一a 2 + m a x 0 ，6 一。6 ) 一b 2 ) ，( 1 1 9 ) 并取辩璧酶1 蔻数生成可徽的努丞数 咖m 8 ( z ) = 妒m s ( f t ( z ) ) 。 ( 1 2 0 ) 继而许多作者做了大量的工作，例如，m o r e 给出可行的信赖域算法；w a n g - m o n t e i r o - p a n g 提出了降势内点法，等等。 4 ) g l p 投影法 o | | ” 坍 p n 圮 嚣 茹 n nm ；m 慧 譬 2 0 0 8 年上海大学硕士学位论文 这种方法基于g o l d s t e i n l e v i t i n p o l y a k 求解凸规划的梯度投影法思想求 解互补问题基本迭代格式为 z ”：= p 一9 f ( z ) 】+ ， ( 1 2 1 ) 这里q 0 为步长迭代( 1 2 1 ) 的收敛性需要强单调性的假设为此，k o - r p e l e v i c h 提出外梯度法，令 z ”8 叫：= z a f c x o f ( z ) 】+ ) 】+ ( 1 2 2 ) 外梯度法的收敛性仅要求f ( z ) 单调且解集x 圣 何炳生教授对投影收缩算法进行了长期深入的研究，揭示了已有的算法 中的寻查方向都是基于三个基本不等式的不同组合s o l o d o v 和t s e n g 在某 种情况下推广了h e 的投影收缩算法，给出了g l p 的一般迭代格式 z ”。叫：= z 一7 p 一1 丁1 a ( z ) 一丁0 ( 【z q f ( z ) 】+ ) ) ，( 1 2 3 ) 其中r 0 是步长，t o ：= i a f , q o 使死强单调，p 是选定的正定 矩阵 5 ) 内点法 这种方法把互补问题转化为一个与之等价的非负约束方程组，然后用 n e w t o n 型方法求解这种方法曾经取得极大的成功，一度成为研究的主流 令y = f ( z ) ，将互补问题( 1 1 ) 转化为 h ( z , y ) ：iy f ( z l ：o ，8 z o ，! o ( 1 2 4 ) l zoy j 这里zo y = ( x l y l ，2 n y 。) 7 给定点( 一，y ) r 辑，内点法的一般迭代格 式为 ( z 川，y + 1 ) = ( z ，y ) + a ( 磁，砖) ， ( 1 2 5 ) v h ( z ，y k ) d k = 一直( 矿，耖) ，d = ( d i ，砖) ( 1 2 6 ) 这里事( x h ，y k ) 是由h ( x k , y 鼍) 经过一个微小扰动得到，其目的是调节迭代 的收敛速度；入k 为步长，它的取法使得新的点( 扩+ l ，y + 1 ) r 辑，且效益 函数有一定量的下降 内点法的优势在于： 非线性互补问题的水平值估计算法 ( 1 ) 大范围收敛性若f ( x ) 单调，可行集q = ( z ，y ) l y = f ( z ) ，z 0 ，y 之 o ) 存在内点，那么由内点法产生的迭代点列 ( z 2 ，耖。) ) 满足( 矿) t y 2 - 40 且 q 线性 ( 2 ) 局部超线性收敛若f ( x ) 单调且可行集q 存在内点若( z ，y ) 是 ( z ，y ) ) 的一个极限点且具有某种i f _ 贝i j 性，则 ( z ，耖) ) 超线性收敛于 ( z ，可) ( 3 ) 多项式时间复杂性若f ( x ) = m x4 - q 单调且可行集存在内点，那 么对可行内点法，最好的复杂性界为o ( v n l ) ；对不可行内点法，最好的复 杂性界为o ( n l ) 6 ) 磨光方程与非内点法 用一个光滑函数日( z ，a ) 近似代替非光滑方程法中的( z ) ，其中日( z ，n ) 为磨光方程，q 为磨光参数，h ( x ，0 ) = 日( z ) ，转而求解方程 日( z ，o t ) = 0 ，( 1 2 7 ) 这就是磨光方程法如果在迭代过程中能把o t 调整到0 ，称为连续磨光方程； 进一步，如果连续不断压缩n 到0 ，就是非内点法 1 3 2 非线性互补问题的全局优化算法 随着全局优化理论与方法研究的不断深入，新的高效率的全局优化算法 被发明，克服算法收敛到非全局最优解已经成为可能，从而求解非线性互补 问题的这一最原始的途径再一次被激活，回到算法研究的前沿 郑权【1 3 】应用他所提出的求解全局优化问题的积分水平集算法 1 4 ，1 5 ， 1 6 ，1 7 ，1 8 1 来求解非线性互补问题，取得了成功其基本思想是将互补问题 ( 1 1 ) 转化为下列约束全局优化问题 c 。g l o b m 。i j nx t f ( z ) ( 1 2 8 ) 其中s = z r n ：z 0 ，f ( z ) o ) 假设问题( 1 1 ) 有唯一解，那么显然优化问题( 1 2 8 ) 有唯一全局最优解， 且其全局最优值为c = 0 用非连续精确罚函数将问题( 1 2 8 ) 进一步转化为无约束问题，定义罚函 数为 以州，= 协藉0 s q 2 9 ， 2 0 0 8 年上海大学硕士学位论文 其中j 0 为给定的正数，且 t l d ( z ) = 1 m i n ( x i ，o ) i + i r a i n ( f i ( x ) ，o ) i 】 ( 1 3 0 ) i = l 用积分水平集算法来求问题( 1 2 8 ) 的解，具体的算法如下： 积分水平集算法求解( 1 2 8 ) 步1 给定c o m i n 。s9 ( z ) ，e 0 给定a o 0 充分大，卢 1 0 h o ：= f z ：g ( z ) + a o p $ ( z ，6 ) c o ，k ：= 0 步2 计算罚均值 c = 志厶。【如) 恤州州) 脚 ( 1 _ 3 1 ) 其中三“= z ：g ( x ) + a k p 。( z ，6 ) ：o k 步3 计算罚方差 一上u ( h k ) 厶。的) 抱加固一砰础 ( 1 3 2 ) 如果 e ，令口i + l = a k 卢；k ：= k + 1 ，转步2 ；否则，转步4 步4 c 仁c k + 1 ；日h k + 1 终止 这种算法的本质就是将非线性互补问题转化为对其适当的价值函数进行 全局优化计算从这个角度来看，好的全局优化算法是通过这种途径求解非 线性互补问题的关键 1 4 本文的工作与文章结构 水平值估计算法是一个较好的求解全局优化同题的算法求解全局优化 问题水平值估计算法的基本思想最初见于文献【1 9 】，文献【2 0 】与【2 1 】对水平 值估计算法进行了进一步的研究与完善，使之成为可实现的有效的且具有较 好收敛性的全局优化算法本文的主要工作针对非线性互补问题的等价形式 ( 1 2 8 ) ，将全局优化的水平值估计算法应用于求解非线性互补问题 在本文的第二章，我们主要介绍求解约束全局优化的问题的水平值估计 算法，以及其基于数论中一致分布佳点集求积分的实现算法，这种实现算法 具有确定的收敛性 非线性互补同题的水平值估计算法 本文第三章，我们将水平值估计算法应用于求解一般的非线性互补问 题，提出了求解非线性互补问题的水平值估计算法，并从理论上证明了算法 的收敛性 在第四章，我们用若干数值的例子，从而进一步从实践上验证了算法的 有效性 第五章，对其它形式的互补问题及非线性互补问题的其它等价形式如何 用水平值估计算法求解进行了讨论，提出了今后研究工作的进行了展望 2 0 0 8 年上海大学硕士学位论文 第二章约束全局优化的水平值估计算法 约束全局优化的水平值估计算法首先由邬冬华等【2 0 1 提出，并提出了基 于数论中一致分布佳点集计算积分的实现算法，证明了实现算法的收敛性 彭拯等【2 1 】将文献【2 0 】的结果从箱约束推广到一般函数约束的情况，并由非 精确牛顿法收敛性准则证明了实现算法的收敛性本章我们先介绍函数约束 全局优化的水平值估计算法的基本理论与概念算法；然后介绍利用数论方法 计算积分的基本算法；最后介绍全局优化水平值估计算法基于数论求积分的 实现算法 2 1 约束全局优化的水平值估计算法一概念算法 本节考虑一般函数约束的全局最优化问题 c 2 赌m ) ( 2 1 ) 其中sc 冗n ，s = z i z r “：g i ( x ) 0 ，i = 1 ，2 ，t ) 圣，是一个紧集， ，：r ”- r 连续，c 为( z ) 在s 上的全局最小值 郑权【1 6 ，17 】首先给出了问题( 2 1 ) 的一个基于积分水平集算法的非连 续精确罚算法，这个算法实质上可以看成一个水平值逼近算法，即用一个下 降的水平值序列 c k ) 逼近问题的全局最优解c 。算法的基本思想为：先定 义非连续精确罚函数f c x ，a ) = ，( z ) 十a p c z ) ，并证明在一定条件下辅助问题 m i n f ( x ，a ) = y ( x ) + a p ( z ) 的解就是问题( 2 1 ) 的解；然后，构造水平集段。= z l z 尺“：f c z ，a k ) sc ) ， 在日。丰满( r o b u s t ) 的假设下，令 o k + 1 = 志厶脚胁，2 丽丽丘州e 毗) d “ 从而得到2 个收敛序列 c t ) 和 凰。) ，并证明序列 铅) 收敛到c 。，且 匝。) 收敛到日= 。s ：f ( x ) = z + ) ，其中日为最优解集算法的终止条件为 非线性互补问题的水平值估计算法 水平集上罚函数的方差 眯m ) = 志：r o c , - f 训) 2 舡一+ 。 ( 2 2 ) 田蔚文，邬冬华等【2 2 1 对该算法进行了改进本节定义并研究了约束水 平集上的方差函数，利用求解方差方程的根，构造一个求解问题( 2 1 ) 的带 有非连续精确罚函数的水平值估计算法 2 1 1 约束水平集上的方差函数及其性质 令h c = x i x r “：，( ? ) c ) ，并设厶( z ) 为示性函数，即 j c z ，= ：x 2e g a a 定义函数 ，”( c ) = 丘s n 日。) ( z ) ( c ，( z ) ) 2 d p ， ( 2 3 ) m ( c ) = 厂，( s n ( z ) ( c 一，( 2 ) ) 舡， ( 2 4 ) 称u ( c ) 为约束水平集上的方差函数，m ( c ) 为均差函数下面讨论 ( c ) ，m ( c ) 所具有的一些性质 引理2 1 1 对于v c r ，有 v ( c ) 0 ，m ( c ) 芝0 ( 2 5 ) 证明：由定义，当snh e 西，且z snh e ，则有 ( s n h 。) ( z ) = 1 ，c f ( x ) 0 而当z r “一s n 趣或s n h , = 圣时，由此有i c s n m ) ( z ) = 0 于是可知： ”( c ) 0 ，m ( c ) 0 引理2 1 2 对于v c l ，c 2 r ，c l c 2 ，有 v ( c 1 ) v ( c 2 ) ，m ( c 1 ) m ( c 2 ) ( 2 6 ) 证明：先证v ( c 1 ) v ( c 2 ) 2 0 0 8 年上海大学硕士学位论文 因为c 1 c 2 ，由定义知：噩：鼠。，所以s n 皿。s n 致， v ( c 1 ) 一v ( c 2 ) = 厶s n 矾1 ) ( 州c 1 一( 圳2 舡一厶舯舻) ( c 2 一，( 瑚2 舡 = ( s n 日。：) ( z ) ( c 1 一，( z ) ) 2 一( c 2 一，( z ) ) 2 d u + s n ( 耳。一肌：) ) ) ( c 1 一，( z ) ) 2 劫 = i c s n h 。：) ( z ) 【( c 1 一c 2 ) ( c l + c 2 2 ，( z ) ) 】d p + i ( s n l h 。一h 。2 ) ) ( z ) ( c l 一，( z ) ) 2 d p = a 1 + a ， 显然a 2 0 对于a 1 ，我们有： 1 ) 若snh c 。西，sn 凰：西，则存在z s n 月岛，有，( z ) 5c 2 0 ，且i ( s n h 。) ( 。) = 1 ，于是a i o ；若s nh e 。 西，sn 也。= 圣，贝0 自然有a 1 = 0 所以v ( c 1 ) 一v ( c 2 ) 0 2 ) t 若s n g c 。= 圣，显然有s n 皿。= 圣，则有v ( c 1 ) 一v ( c 2 ) = 0 再证r e ( c 1 ) r e ( c 2 ) 由于 m ( c 1 ) 一m ( c 2 ) ， = i ( s n h 。) ( z ) ( c l 一，( z ) ) 舡一i ( s n h , ：) ( z ) ( c 2 一，( 训舡 rf = i ( s n h 0 2 ) ( c 1 一c 2 ) d p + i ( s n ( h 。1 一片。2 ) ) ( z ) ( c l 一( x ) ) d u ， = p ( s n g c 2 ) ( c l c 2 ) + i ( s n ( h o 。一1 t , ：) ) b ) ( c l 一，( z ) ) 如 所以运用与上面相似的讨论可知：m ( c 1 ) m ( c 2 ) ( 2 5 ) 和( 2 6 ) 说明函数u ( c ) 与m ( c ) 在( 一0 0 ，+ o o ) 上为非负，单调不减 定理2 1 1 设c = m i n z s ，( z ) ，则 i ) v ( c ) = 0 等价于c c 。； i i ) m ( c ) = o 等价于csc + 证明：i ) 先证v ( c ) = 0 号c c 当i ( s n 皿1 ( z ) 三o 时，即r “，z sn 凰，所以必有sn 矾= 币于 是比s ，有， ) c ，可知c c 。= m i n 。s ，( z ) ； 非线性互补问题的水平值估计算法 当 ( s n h 。) ( z ) 不恒为0 时，即sn 凰妒反设c c ，由f ( z ) 的 连续性知，存在z + s ，使得，( z ) = c 0 ，任何z ( u ( z ，盯) n ( s n 日。) ) ，有f ( x ) 0 与v ( c ) = 0 矛盾! 从而可证c c 由此得v ( c ) = 0 号c c 再证：c c + jv ( c ) = 0 当c 0 时，注意到( 王己c 1 s ) ( 上+ 。n s ) l i m v ( c + a ：c ) - v ( c ) c - 0 z ) c = l i r a 。去【抽朋心) ( c + c m ) ) 2 咖 一，( 。n s ) ( z ) ( c 一，( z ) ) 2 d p 】 = 一l i m 。圭【如。擒n s - h n s ) ( 州c + c m ) ) 2 舡 + 几玫n s ) ( z ) 【( c + c m ) ) 2 一( c m ) ) 2 】训 当z ( 丑c + a cns 一眉cns ) 时，有c 。 d ( z ) = ( 。) 2 0 ) ( z ) 仇( z ) 设琊= 圳z r “：f ( x ，o ) c ) 并定义 t j p ( c ) = 厶日 ) ( z ) ( c f ( z ，口) ) 2 d 弘， ( 2 1 1 ) ( 2 1 2 ) 2 0 0 8 年上海大学硕士学位论文 m p ( c ) 微f 丘日? ) ( z ) ( c f ( 茁，穗) ) c 砸 ( 2 1 3 ) ， 我们可以证明如下的 宠理2 。1 3 l i mv p ( c ) = v ( c ) ( 2 1 4 ) 8 证明；注意到对子任意绘定的a 0 ，有霹翟( h cns ) ，对手v c 0 ，考 虑 l v v ( c ) 一秽( e ” = l 心( 搿) ( c f ( 郴) ) 2 和 一 7 曩n s ) ( 。) ( c 一，( z ) ) 2 舡l = ih 硼吨嗍( z ) ( c f 。) ) 2 舡 + 7 & 壤q s ( 茹) ( ( e 一罗( 譬，8 ) ) 2 一( e 一歹( ) ) 2 ) d i i l l 曼l i ( h r - h e n s ) ( z ) ( c f ( x ，。) ) 2 札l + | 7 & 臻n s ( 一印( 茹) ) 陋一2 f ( x ) 一肇) 审l ， =a 1 + a 2 毙考察龟，避舅毛主毛qs 对，敞秘s 霉) = 0 ，蠢当z 段f ls 时，壶定 义p ( 髫) = 0 ，所以a 2 = 0 对于a l ，洼意到( 王翠一致ns ) 时，e f ( x ，站) o ，p ( 露) 0 ， ( 因舞器 鑫，鑫茹) o ) ，8 1 0 ，所以对每一给寇鳃e ，存在疹= 三二盖l 乎，取 口= m a = ( 1 0 ，口) ，当a 口。时，l c f ( z ，b ) i = i c l ( x ) 一a p ( x ) l 0 及n 1 0 充分大， 令七：= 0 第二步：令 h 品= ( x i f ( x ，a ) o k ， ( 2 1 8 ) 计算 ( c 女) = 五日邑) o ) ( c k f ，口) ) 2 d p ， ( 2 1 9 ) m a c k ) = h ) ( z ) ( c i j f l ( 础) ) 中 ( 2 2 0 ) 如果( c t ) 扩，由定理1 1 , - , 1 。3 知，v p ( c ) 是凸爨数，旦囊c 矿 时，( c ) 0 褥由( 2 2 1 ) 知 所以 v p ( c k ) + ( 锻) ( 斑+ l 一强) = 0 u p ( c k + 1 ) 芝v p ( c k ) + t ( 觑) ( c 女+ l c 女) = 0 于是c k + 1 c 由归纳法知：c 后矿，诋：0 ，1 ，2 ，故f “) 收敛设舌是 c k ) 的极限，则芒之c + ，另外，对( 2 2 1 ) 两边取极限 一器 褥v p ( e ) = 0 ，从薅垂s 。所以蚕= ，鄂 1 i m 睨= c 女 o o 巍l i m k 缘= c 时，关于l i m k 叶磁= 敝n s = 嚣酶证嚷可以参 见文献文献【2 3 】p 4 5 5 0 证毕 2 2 数论方法计算积分 在全局优化的水平值估计算法中，我们需要计算高维数值积分，这本身 又是一个困难的 蠢题。一般邃，人们采用m o n t e - c a r l o 方法，在这薰我髓弱 用数论中的华正方法，即利用一致分布佳点枭来计算数值积分下面对这 一方法及其理论做一简单介绍 设d 是一个单位闭箱，不失一般缝，设d = g 。，g 。一羚，圭卜蓉扩) 鸯 g 。曲勺任意分割。 22 l l 王 i l = = 毋毋 卉 ( ； 土l 1 2 l 略 嚣 z 霉 遗霹 瑶 i i = = o 0 0 仃 l ，b ，女。，( 2 l = ，( z 1 。1 ， 一f ( z l 神z 1 + 1 一i ( x l ，z z - ， + i ( x l 一z 1 + 1 ， + + f 一1 ) m 1 l ( z i + ( 1 ) m m l z z a s t 2 t ，。，( z ；- 一，( z i l + 1 ，z 挚 1 t t _ l i l + i ，z 字 ，z 孑 + l + ( 1 ) n “f ( 。, r i i l + l ，z 1s h 妃s 扎 ，窀警， ，z 蛩一神罂， z ：2个“m 一荔 _ 乏机，： ，1 i + 1 十i b + 1 ，* 1 2 1 七1 如 ksn z 字+ 1 ，z + 1 ) 1 9 。- 它 l ， ，