（运筹学与控制论专业论文）基于信息分析的网络平衡研究.pdf

摘要 网络平衡配流问题研究一定需求在网络结构上的n a s h 平衡状态分布规律；信 息分析方法，特别是基于信息量分析和最大信息量获取意义下的网络状态分析方 法越来越受到人们的重视。本文对系统最优和用户平衡原则下的网络流性质进行 分析，并用信息分析的方法研究网络平衡的优化、变分不等式和平衡规划模型与 应用；利用基于最小鉴别信息原理的极大熵方法求解极大极小问题、变分不等式 问题和平衡规划问题；将平衡规划模型建立和信息分析方法用于混合网络n a s h 平 衡问题和i t s 领域。 本文在前人极大熵方法研究成果的基础上，将k u l l b a c k 相对熵用于参变极 值问题的信息凝聚方法中，用最小鉴别信息原理的极大熵方法求解极大极小问 题，通过凝聚分布的数字特征给出了参变极值问题的信息凝聚解表示，推广了 极大极小问题的极大熵方法。 第一章概述部分，简述网络平衡和信息分析方法及其研究现状，介绍本论 文的选题背景和研究内容。 第二章在论述k u l l b a c k 相对熵意义下的信息分析方法和网络平衡概念与 性质的基础上，充分考虑先验信息的作用，将最小鉴别原理应用于信息更新； 突破原束从个体出行路径考虑网络平衡的框架，从网络宏观状态分析，提出了 标准用户平衡问题和平衡规划模型。 第i 章利用初始先验分布和k u l l b a c k 相对熵概念，将参变极值问题的求解 过程视为对最优解信息的凝聚过程，首次给出了利用分布数字特征作为参变极 值问题晟优解的一种积分极限表达式，讨论了其一致收敛性的要求，给出了一 致收敛的一个充分条件。通过g a p 函数，将不等式组及变分不等式的求解化为 近似可微优化问题，提出该问题近似解的可微优化方法及解集合的示性函数； 将参变极值的极大熵方法应用于n l p ，得出了全局最优解和最优值的一种显表 示。 第四章将交通规划、交通管理与控制研究及实践最为关注的交通网络配流 问题视为特殊的参变极值问题，给出了网络平衡问题的一种新解释和相应平衡 规划模型：首次给出了混合网络平衡的平衡规划模型及其实现算法，将信息凝 聚方法用于混合网络n a s h 平衡问题的求解，得到了混合网络平衡规划及其信 息凝聚解的联立表示。作为特例，从一般混合网络配流的平衡规划模型导出了 对称型双向影响的网络配流最优化模型。 第五章研究基于网络平衡的交通需求信息更新问题。在交通网络平衡配流 研究中，及时更新和预测o d 信息是一个重要的理论和实际问题。i n o u e ，1 9 7 7 ， c a s c e t t a ，1 9 8 4 ，b e l l ，1 9 9 l 等从路网流量信息入手，进行o d 矩阵估计研究，给 出线性配流模式，但翻i 能保证o d 矩阵估计结果的可靠性。本文依k u l l b a c k 最小鉴别信息原理和最大熵原理提出了o d 矩阵估计的方法，使网络流的观测 量与预测量、o d 先验信息与预测信息一致，在此基础上建立了用户平衡的 o d 信息更新模型。 最后作者总结了全文，并对下一步的研究工作做了展望。 关键词：网络平衡配流；系统最优；n a s h 平衡：用户平衡；变分不等式；平 衡规划；网络容量；交通分配；全局最优解：极大熵方法；k u l l b a c k 信息 a b s t r a c t n e t w o r kf l o we q u i l i b r i u ma s s i g n m e n tp r o b l e mc o n c e r n sw i t ht h ed i s t r i b u t i o no f t h ed e m a n do nt h en e t w o r k t h ei n f o r m a t i o n m e t h o d ，e s p e c i a l l yt h em a x i m u me n t r o p y m e t h o db a s e do nt h ec o n c e p to fk u l l b a c ki n f o r m a t i o nf o rt h ee q u i l i b r i u mh a sr e c e i v e d m o r ea n dm o r ea t t e n t i o nr e c e n t l y t h ea n a l y s i sf o rn e t w o r kn a s he q u i l i b r i u mm o d e l b a s e do nt h em a x i m u me n t r o p ym e t h o da c c o r d i n gt ot h e c o n c e p t o fk u l l b a c k i n f o r m a t i o ni si n t r o d u c e da n dt h e ya r ea p p l i e dt os o l v i n gn l a x - m i np r o b l e m ，v 1 pa n d e q u i l i b r i u mp r o g r a m m i n g w ed e v e l o p e dt h e c o n c e p t o fs h a n n o ne n t r o p yf u n c t i o n b ye m p l o y i n gp r i o r d i s t r i b u t i o ni n f o r m a t i o na n dk u l l b a c ke n t r o p yc o n c e p t st oo b t a i nt h em a x i m u me n t r o p y f u n c t i o no ft h em a x m i np r o b l e mb yi n t r o d u c i n gt h ee x p e c t a t i o no ft h ed i s t r i b u t i o nt o e x p r e s st h es o l u t i o n t h ei n t r o d u c t i o no ft h i sd i s s e r t a t i o ni sg i v e ni nc h a p t e r1 ，w h i c hb r i e f l yg i v e s t h ep r e s e n ts t a t ea n db a c k g r o u n do fn e t w o r kf l o we q u i l i b r i u ma s s i g n m e n tp r o b l e m a n dt h ei n f o r m a t i o nm e t h o d ，a n dt h em a i nr e s u l t si nt h ed i s s e r t a t i o n t h er e l a t i o nb e t w e e ns y s t e mo p t i m a la n du s e re q u i l i b r i u mp a t t e r n si sf u r t h e r d i s c u s s e d ，u s e re q u i l i b r i u mi s t h e s y s t e mo p t i m a ls t a t et a k i n g t h er e a ln e t w o r k c o s t sa st h e m a r g i n a lc o s t s ，a n dt h e r e a l i z a t i o no fs op a t t e r na r ep r e s e n t e di n c h a p t e r2 t h em a x i m u me n t r o p yf u n c t i o na p p r o a c ht om a x m i np r o b l e m si si n t r o d u c e d a n di ti sf u r t h e r d e v e l o p e d t os o l v et r a d i t i o n a l i n e q u a l i t i e s ，v i p a sw e l la s e q u i l i b r i u mp r o g r a m m i n g a ne n t r o p y f u n c t i o nf o ri n e q u a l i t i e sm a dak u l l b a c k e n t r o p ye x p r e s s i o nf o rt h eg a pf u n c t i o no f t h ev a r i a t i o n a li n e q u a l i t yp r o b l e m ( v i p ) a r ep r e s e n t e d t h es o l u t i o no f i n e q u a l i t i e sc a nb ea p p r o a c h e db yo b t a i n i n g t h el o c a l m i n i m u ms o l u t i o no fad i f f e r e n t i a b l ec o n v e xf u n c t i o no p t i m i z a t i o np r o b l e m w e d e v e l o p e dt h ec o n c e p to f s h a n n o ne n t r o p yf u n c t i o nb ye m p l o y i n gp r i o rd i s t r i b u t i o n i n f o r m a t i o na n dk u l l b a c k e n t r o p yc o n c e p t s t oo b t a i nt h em a x i m u me n t r o p y f u n c t i o no ft h em a x m i n p r o b l e m a n dt h e g a p f u n c t i o nf o r v i p , e q u i l i b r i u m p r o g r a m m i n gp r o b l e m a n dt h en l pa r et h e s p e c i a lp a r a m e t r i co p t i m i z a t i o n i l l p r o b l e m si nc h a p t e r3 i nc h a p t e r4 ，t h em i x e dn e t w o r ke q u i l i b r i u mm o d e li sd e r i v e dd i r e c t l yf r o m t h ee q u i l i b r i u mp r o g r a m m i n ga n de pm o d e l sf o rc o m b i n e dw a r d r o pp r i n c i p l e s u n d e rd i f f e r e n ti n f o r m a t i o nc o n d i t i o n sa r e a n a l y z e d t h e k u l l b a c k e n t r o p y e x p r e s s i o nf o rt h eg a p f u n c t i o no ft h ev a r i a t i o n a li n e q u a l i t yp r o b l e m ( v i p ) i sp r e s e n t e d a n di ti su s e dt os o l v et h et r a f f i ca s s i g n m e n tp r o b l e m ( t a p ) i nc h a p t e r5 ，a na p p l i c a t i o no f u p d a t i n go 1 3i n f o r m a t i o n i sp r e s e n t e d b yc o m b i n g t l ec o n c e p t so fn e t w o r ku s e re q u i l i b r i u ma n dk u l l b a c kr e l a t i v ei n f o r m a t i o n f i n a l l y ，t h ea u t h o rs u m su pt h er e s e a r c hr e s u l t si n t h e s i sa n dg i v e sp r o s p e c t s o ft h ef u r t h e rr e s e a r c hi nt h ef i e l d s k e y w o r d s ：n e t w o r kf l o wa s s i g n m e n t ；s y s t e mo p t i m u m ；n a s he q u i l i b r i u m ；u s e r e q u i l i b r i u m ；v a r i a t i o n a li n e q u a l i t y ；e q u i l i b r i u mp r o g r a m m i n g ；m a x i m u m f l o w ； b i l e v e lp r o g r a m m i n g ；o p t i m i z a t i o n ；v i p ；e n t r o p yf u n c t i o n ；k u l l b a c ki n f o r m a t i o n i v 第1 章概论 本章简述网络平衡和信息分析方法、相应的基本研究现状以及论文的选题背 景和研究内容。 网络平衡配流问题研究一定需求在网络结构上的n a s h 平衡状态分布规律；平 衡规划较最优化和变分不等式方法更适合网络配流问题；用户平衡是系统以实际 网络费用作为边际费用时的系统最优状态；信息分析方法，特别是基于信息量分 析和晟大信息量获取意义下的网络状态分析方法越来越受到人们的重视；信息凝 聚方法求解参数极值问题、极大熵方法求解变分不等式问题以及平衡规划的极大 熵方法等是最优化极大熵方法的推广；平衡规划模型及其极大熵方法在混合网络 n a s h 平衡中得到有效应用。 1 1 引言 。 网络分析和信息分析是系统工程的主要内容和方法，一篇关于数学规划在工 业和管理中的应用综述性文献指出，由于网络模型的背景普遍性、形象直观性、 计算有效性以及模型转换方面的灵活性，网络模型超过了7 0 的应用份额【6 8 。 信息分析方法，特别是极大熵方法在系统状态分析以及优化问题中的应用，为网 络n a s h 平衡状态的求解提供了一种新视角。这一方法，将问题分析、求解过程转 化为信息分析和信息量获取最大化的过程，或者说是最快消去不确定性的过程。 在网络模型中，网络平衡又占主要位置，作为自然界和人类社会三大基础的物质、 能源和信息大都以网络流的形式在通讯、电力、交通和管道等网络上进行着传输 转换和分配形成各种网络流。在社会经济系统中也存在着各种网络流形式，如贸 易网络流、金融网络流及人才网络流等。研究网络平衡配流问题及其极大熵方法 有重要的理论意义和实际应用价值。 网络平衡配流问题的实际背景之一源于交通分配问题( t a p ) ，交通分配问题关 心交通需求在道路网络上的时空分布规律，它是交通规划设计和交通管理控制的 基础和依掘。用户平衡分配模式较接近于现实交通环境，它对应着个体出行寻求 各自最小费用时的网络流分配状态。早期用户平衡配流的实现大多采用直观启发 式方法，如迭代全有一全无分配法( i t e r a t e da 1 1 o r - n o t h i n g ) 干1 增量分配法( i n c r e m e n t a l 大连理工大学博士学位论文 a s s i g n m e n t ) 。这种从问题直接到方法的处理过程的特点简单直观，但由于这种没 有模型分析过程直接基于问题的启发式算法一般刁i 是严格意义下的用户平衡配流 实现算法，使得难以对交通网络配流问题进行深入数量分析。五十年代中期， b e c k m a n n 等给出了用户平衡网络配流的最优化等价模型，使得精确意义下的用户 平衡配流模型分析和收敛算法设计成为可能。七十年代末至八十年代初，s m i t h 和d e f e r m o s 等就一般非对称型网络费用的用户平衡配流问题建立了变分不等式 模型f 8 i 】。 由于最优化和变分不等式模型缺少网络平衡配流过程的直观经济含义且难以 标定，人们又用网络对策( n e t w o r kg a m e s ) 研究平衡配流问题，c h a r n e s 和c o o p e r 以o d 对为局中人，将网络用户平衡配流描述为一非合作1 2 人对策n a s h 平衡系 统 6 9 1 ；r o s e n t h a l 用对策论研究了用户平衡配流问题的离散情形，以每个用户作 为局中人，以各自的可行路径集合作为相应的策略空间，证明了离散情形的用户 平衡配流问题等价于网络上的一个非合作纯策略n a s h 对策；由于用户平衡配流连 续模型中网络使用者是无限可分的，不宜将出行者个体作为局中人。另外，以众 多对策人和各自的可行路径集合作为策略空间的对策模型虽然描述起来直观，其 计算实现却困难的多。d e v a r a j a n ( 1 9 8 1 ) 将结果推广到连续情形的网络用户平衡配 流问题【1 3 】，g a r c i a 和z a n g w i l l 就网络用户平衡配流问题给出了同样的对策论模 型l1 3 1 ；f i s k 、h a u r i e 和m a r c o t t e 讨论了更加一般的网络流平衡问题的对策论模 型 1 6 】。 对策论与数学规划的理论和方法在经济、工程及预测等方面有着广泛的应用， 将二者的特，氧结合起来形成的对策规戈1 ( g a m ep r o g r a m m i n g ) 有其理论、方法和应 用上的优势。平衡规划( e q u i l i b r i u mp r o g r a m m i n g ) 和双水平规划( b i - l e v e l p r o g r a m m i n g ) 就是最重要的两种对策规划【9 1 】。事实上，平衡规划是一种特殊的参 变极值问题。 静态网络平衡配流问题的特点与对策规划的特点相符合，利用平衡规划模型 和方法描述多点间最小费用流和混合网络配流问题有其它模型和方法不具备的优 点。网络上用户平衡环境下两点间的最大流问题或一般网络上多点闯的最大滚问 题可以通过一个具有特殊结构的双水平规划来描述。网络配流在算法实现上可以 将有效的非线性规划算法同网络结构和平衡配流特点结合起来。 信息分析方法，特别是极大熵方法在优化问题中为网络n a s h 平衡问题的求解 提供了一条新途径。 2 第l 章概论 优化问题广泛出现在信号处理、系统识别、函数逼近、滤波设计、自动控制 等科学技术领域。如何运用定量分析计算来提高预算的精确度一直是优化研究的 目标。最优化方法是实现上述目标的一个有效途径。通常，我们将所处的环境看 作一个系统，通过系统仿真、系统模拟及运用优化的手段，最终达到预测目的。 在工程与管理科学中，许多问题的数学模型都直接或间接地涉及到最大值函 数，如极大极小问题、平衡规划问题及其它一般参变极值问题。由于此类函数本 身往往是不可微的，这就使得求解可微优化问题的优秀算法不能直接用来求解这 类问题，因此，构造可微函数去逼近最大值函数，用可微优化问题的解去近似原 问题的解。极大熵方法是其重要的一种方法。 由于极大极小问题、变分不等式问题和一般平衡规划问题属于参变极值问题， 不等价于一个连续型可微数学规划问题，许多求解可微优化问题的有效方法不能 直接用来求解这类问题，探讨参变极值问题的极大熵方法有着理论和实际的应用 价值。 1 2 网络平衡及信息分析方法研究的历史和现状 网络配流问题是离散的路径问题的连续化和推广。研究某种需求自网络上的 始点( o ) 流向终点( d ) 时在网络上的分布规律。般网络平衡往往需要用变分不等 式、平衡规划、极大极小等参变极值问题来描述，极大熵方法是将此类问题转化 为一可微优化问题的逼近来求解的一种有效方法。 1 2 1 网络平衡 最初的网络配流问题源于网络上两点间最短路径、最小费用流和最大流等问 题的研究 2 2 1 。一方面，在图论和网络分析的理论研究中，需要将独立于网络流 形态的两点间的最短路径、最小费用和最大流问题和结论推广为依赖于网络上流 量的多点问的最短路径、最小费用和最大流模型；另一方面，由于网络配流问题 有许多实际背景和应用，网络配流问题的一般研究也是实际网络规划设计和评价 分析的需要。网络n a s h 平衡在理论和实践中都是重要的网络配流模式。 1 9 5 2 年，w a r d r o p 在他的文章“s o m e t h e o r e t i c a la s p e c t so f r o , a d t r a f f i cr e s e a r c h ” 【9 2 】中提出的用户平衡( u e ) 原则和系统最优( s o ) 原则促进了网络配流的建模和方 法研究的进程，目前用户平衡原则和系统最优原则是网络配流采用的最普遍的行 为原则，被称为w a r d r o p 原则，条件，尽管在经济学中作为社会原则和市场原则在 大连理工大学博士学位论文 本世纪二十年代就被经济学家提了出来 7 2 】。 1 9 5 6 年，b e c k m a n n 等出版了“s t u d i e si nt h ee c o n o m i c so ft r a n s p o r t a t i o n ”一 书，给出了t a p 的数学模型分年斥，证明了当网络阻抗函数是分离情形时，w a r d r o p 条件对应着线性网络约束的凸非线性规划问题的解 2 】。人们开始用数学规划的方 法分析网络平衡配流问题，后来人们称这等价交换为b e c k m a n n 魔术变换 3 8 1 。 同年，f r a n k 和w o l f e 关于凸二次优化问题的迭代组合凸算法文章的发表为网络平 衡配流精确算法的实现提供了可能。 考虑网络出行需求分布与网络配流的相互影响，对应着弹性需求下的网络配 流问题，b e c k m m m 变换适合般的弹性需求情形，这时固定需求情形可作为一特 例给出，文献 3 8 给出了解的存在性和唯一性结果并证明了其最优性条件满足 w a r d r o pu e 原则。d a f e r m o s 和s p a r r o w ( 1 9 6 9 ) 迸一步深入研究了u e 的最优化模型， l e b l a n c ( 1 9 7 5 ) 将最短路径算法应用于f r m a k w b l f e 算法，给出了u e 优化模型的有 效解法【4 5 1 。s m i t h ( 1 9 7 9 ) l l ld a f e r m o s ( 1 9 8 0 ，1 9 8 2 ) 研究了一般非对称型网络费用下 的用户平衡配流问题 1 1 ，1 2 ，此时网络平衡配流问题需要用变分不等式( v i ) 模型来 刻划r n a g u r n e y ，l9 9 3 ) 。 在静态用户平衡配流模型中，有许多扩展模式。f l o r i a n ( 1 9 7 8 ) 和b o y c e ( 1 9 8 0 ) 将网络配流同出行分布和出行生成结合起来考虑，d a g m l z o 和s h e f t i ( 1 9 7 7 ) 给出了 随机用户平衡( s u e ) 模型 8 1 】，s u e 较u e 模型更适合网络实际。 1 9 9 4 年，p a t r i k s s i o n 针对非对称型网络费用难以标定的情形，提出了约束分 配模型 7 1 】。约束分配方法是从实际出发，通过引入一系列约束来模拟对可能出 现的网络流格局的限制，如容量限制约束，针对某些边要求配流再现实际观测流， 描述网络流量的交互作用等等。理论上证明了约束分配问题的解可以等价地通过 求解一个对称型用户平衡模型获得，这一结果导出了约束模型和非对称模型间的 一种解释关系。 s m i t h 、d a f e i m o s 、a a s h t i a n t 和m a g n a n t i 等对静态非对称型网络配流问题的 深入研究，给出了从数学意义上可以相互转换的不动点、变分不等式和非线性互 补模型【1 1 ，8 0 。得到了平衡解的存在性和唯一性结果。但由于计算实现上的困难， 特别是标定一般非对称型网络费用函数的实际困难，这类方法在实际中还未被采 用【1 1 。 平衡规划是对策论与数学规划的交叉领域。1 9 5 1 年，年仅二十一岁的n a s h 在“n o n - c o o p e r a t i v eg a m e s ”的短文中提出了重要的n a s h 平衡概念，证明了n 人 第1 章概论 对策中鞍点的存在性。1 9 5 3 年数理经济学家利用n a s h 对策思想和方法证明了社 会平衡和经济平衡的存在性；1 9 8 1 年，z a n g w i l l 等用跟踪分析方法研究了平衡规 划解的存在条件，并给出了平衡规划的应用背景和实例【1 1 3 ；平衡规划和变分不 等式的深刻联系由l i o n s 和s t a n r p a c c h i a 于1 9 6 7 年建立【4 7 】。n a s h 平衡是一个重 要概念，许多社会、经济平衡都对应着n a s h 平衡，如市场平衡、贸易平衡和交通 网络平衡等。可以说，平衡规划结合了对策论中的经济行为特点和数学规划的结 构性特点，同时还具有变分不等式适用范围广等长处，所有这些使得平衡规划具 有深刻的理论背景并在社会经济和系统工程领域中有着广泛的应用。正由于这些， n a s h 二十一岁时这方面的开创性： 作和贡献获得了1 9 9 5 年诺贝尔经济学奖。 v i n c e n t 和g r a n t h a m ( 1 9 8 1 ) 用连续静态对策的模型和非线性规划最优性条件分析方 法平行地给出了平衡规划的最优性条件 9 0 】，b r a n ( 1 9 9 6 ) 将双水平最优控制思想 建立在智能交通系统( i t s ) 模型中。 网络配流逆问题来源之一是交通网络分析中的o d 矩阵反推问题，所谓o d 矩阵反推是指在一定条件下，给定网络流分配结果，求交通需求信息。近些年来， 有许多研究者关心从路网观测的流量信息估计o l d 出行矩阵这一问题，常用的方 法有极大熵方法、极大似然法、最d , - - 乘法和b a y e s i a n 估计等。本论文中基于 k u l l b a c k 最小鉴别信息方法的o d 信息估计方法体现了信息分析方法应用的广泛 性。 网络配流逆问题的应用研究的另一背景是均衡交通网络最优配时问题，在网 络上关于网络流的信号控制系统中，控制策略是决定系统控制效率的主要因素。 传统的配时方法是在给定网络流形态下，确定与相应流向流量匹配的信号比。事 实上，信号比与网络流的分配形态密切相关。a l l s o p ( 1 9 7 4 ) 建议在信号配时中将交 通信号控制与出行者路径选择行为之间的影响考虑进来，以期获得最优信号配时 方案，从而开辟了均衡网络交通信号最优配时( e q u i i i b r i u mn e t w o r kt r a f f i cs i g n a l s e t t i n g s ) j 塞_ - - 研究领域。除了信号规划外，由于i t s 研究的深入，信号系统的信息 量分析与应用是i t s 的一个重要方面。如路口信号系统的信息量分析已经从定性 走向定量，简单红绿两色路口灯空系统一个周期至多提供给网络平衡用户一比特 的信息量，而数字化显示和模拟时间显示的电子路口将提供更多的比特信息。因 此，智能交通信息系统是本论文的选题实际背景和具体应用领域之一。 不等式组是类广泛的模型，函数方程是其特例，求解不等式组、刻划不等 式组解集是理论分析与数值计算中最基本和带有普遍意义的问题。变分不等式一 大连理工大学博士学位论文 方面是一般不等式组问题的推广，当指标集世有限时对应着一种特殊的不等式组， 一般情况时足为无限的凸集合，因此是一不可列维的不等式组：另方面，变分 不等式又是优化问题的推广，当连续映射f ( 抑为可微凸函数的梯度时，变分不等 式等价于数学规划问题。不等式组与变分不等式之间的关系也反映了方程与优 化之间的关系，前者是后者的推广。c a r e y1 9 7 7 年给出了数学规划的可积性模型 及其在经济平衡中的应用；f u k u s h i m a1 9 9 7 年通过引进正则化方法给出了变分彳i 等式的一种可微最优化等价表示；作者等1 9 9 9 年讨论了h a r t m a n - s t a m p a c c h i a 变 分不等式的双层平衡等价表示，给出了变分不等式与系统平衡之间的深刻联系 f 2 4 1 。 1 2 2 极大熵方法 极大熵方法是1 9 8 7 年以来形成的求解某些优化问题的一种有效方法，为分析 与数值求解一些优化问题提供了一种新的途径 8 6 1 。文献【3 6 】又将该方法推广到连 续型有界集上的极大极小问题中。利用先验分布信息和k u l l b a c k 熵概念，将参变 极值问题的熵函数方法由只考虑函数值意义下的近似问题和s h a n n o n 熵函数概念 推广到考虑最优解意义的逼近问题和k u l l b a c k 意义下的熵函数，鉴于不等式组及 变分不等式同函数方程及最优化问题之间的关系，利用极大熵方法探讨不等式组 与变分不等式的求解及解集表示有重要的分析与应用意义。 近年来，对于一些特殊优化问题的极大熵方法研究取得了一些重要结果。在 理论研究和实际应用中，经常遇到求解极大极小问题，由于该类问题的非光滑性， 加之对极值函数一般写不出显表示式，用传统的优化方法处理这类问题时显得困 难而低效。极大熵方法是自1 9 8 7 年来形成的求解该类问题的一种有效方法，并己 取得了一些很好的结果，如文献 8 6 ，5 7 5 9 ，8 8 ，8 9 ，3 6 ，1 1 5 ，】。考虑如下优化问题： ( p ) m i nf ( z ) 2 m 。a ；x 。f a x ) ( 1 2 - 1 ) s _ t g ，( x ) 0 ，j = 1 , 2 ，n 首先通过最大值函数将( p ) 转化为单约束问题： m i nf ( x ) = m a x ：( x ) ( p 1 ) s t - m l g a s x ，g ，( x ) o ，= l ，2 ，” ( 1 2 2 ) 再用极大熵函数构造与( p 1 ) 等价的问题 第1 章概论 ( p 2 ) r a i nf p ( 上) = 亡l n e x p p f , ( x ) l ( 1 2 3 ) p百 “g - ( 班i 1i n 再e x p 胁小肛。 最后利用罚函数等方法求解可微优化问题( p 2 ) 8 8 ，8 9 ，1 0 9 ，u o ，用( p 2 ) 的锯去近似【p ) 的解，从数值实验角度来看这种方法有诸多优点。 极大熵方法在近几年中的主要成果有： ( 1 ) 极大极小问题：( 包括无约束极大极小问题与带约束的极大极小问题) 文献 5 7 】利用j a y n e s 熵原理给出了极大极小问题目标函数对应的极大熵函数，并证明 了当参数趋于无穷大时，熵函数的解是所求问题的解 5 8 ，8 8 ，9 4 。 ( 2 ) 一般约束优化问题：约束优化问题的极大熵函数法最早由文献【4 9 】给出。 这种方法要求约束区域非空，因而仅适用于不等式约束问题。一般约束优化问题 极大熵函数由文献 8 7 】给出。此方法将 m i n 厂( 工) s 1 g ，( x ) 0 ，f - 1 , 2 ，k ，( z ) = 0 ，i = 1 , 2 ，k 用下述问题来近似， m i n f ( 曲 5 f g 。( x ) 0 h 。 ) e ( q ) 其中g p = 万ti n 喜e x p p g 心) 】 ”加万1in艺expqh2j=l( 砒嘶) = ；1 n m一，= iyy ( 3 ) 多i f l 标优化问题：文献【8 4 】、 3 7 对形如 m i n f ( x ) = ( ( x ) ，、厂2 ( x ) ，厶( x ) ) 5 r x x = x r l g j ( x ) 0 ，= 1 ，。一，| 其中，( z ) = m 。a ；弘( x ) ，i = i ，卅，对目标函数的成员函数：( x ) 用熵函数 ，( x ，p ) 2 万11 n 否。x p 【p 厶( x ) 】代替，并给出收敛性分析。 文献【9 6 】对常规的多目标函数也构造了以最大值函数作为评价函数的极大熵 函数法。 ( 4 ) 半无限优化问题：半无限优化问题是工程设计领域常见的一种求解有较 大连理工大学博士学位论文 大难度的问题。对f 述半无限优化问题： r a i n ，( x )( 12 4 ) s t 矽，( x ，f ，) 0 ，f ，q 。i = l ，l 利用j a y n e s 熵原理建立极大熵方法，即 m i n f ( x ) ( 1 2 5 ) s ，o ( x ，p ) 兰0 其中 如川2 i 1i n 喜志f ! e 坤 p 0 如一肭， v ( n ) 表示紧集n 。的测度，该文证明了若x + 是( 1 2 5 ) 的解，则当p o o 时，其极限 点x 是问题( 1 2 4 ) 的最优解 2 7 。 文献 3 6 】利用j a y n e s 熵原理给出了最大值函数的一个近似函数： 古m 荟j 懿p p f ( x , t 瑚 研究了该函数的性质及算法实现；文献【9 5 分析了算法的收敛性与稳定性。 此外，极大熵方法在线性规划、模糊优化、大系统优化等问题中也有着广泛 的应用【2 8 。 极大熵函数法结构简单，方法易实现且计算速度快，但当参数充分大时，熵 函数便趋于病态使得算法无法进行下去。文献【5 0 ，1 1 0 】分别给出了一种稳定、有效 的带有新参数的熵函数方法。 近年来极大熵方法被引用于求解非线性互补i h qn 题 1 1 8 ，变分不等式w 瞄刀可 以看作是非线性互补问题和混合互补问题的更进一步的扩展。 即给定函数f ：r ”斗r ”，0 k r “，求x k 满足( 1 2 6 ) 式： f ( x ) 7 ( y 一工+ ) 0 ，对v y k ( 1 2 6 ) 当k = 扛1x o 时，( 1 2 6 ) 式退化为非线性互补问题。另外当集合k 为矩形 k ：= u 2 ( z ，“，) ( 其中：一m ， “， o o ，i = 1 ，2 ， ) 时，( 1 2 6 ) 式称为箱形约束变 分不等式( b v l ) ，即混合互补问题a 上述互补问题是变量和函数之间的互补关系，而广义互补问题 4 0 ，4 7 i h 究的 是两个函数之间的互补关系，即给定函数p ：r ”叶r ”g ：r “斗尺“，求x e r ”，满 足： p ( x ) 0 ，g ( 工) 0 ，p ( x ) 7 1 9 ( j ) = 0 ( 1 2 7 ) 第1 章概论 由于在定的条件下，混合线性互补问题、水平线性互补问题以及垂直线性 互补问题都等价于线性互补问题【9 3 ，1 ，而线性互补问题又是非线l 生互补问题的 一个特殊情况。 互补问题广泛地出现在运筹学中。线性规划、二次规划及非线性规划中均有 其互补问题形式。线性规划问题是求x r ”，满足 m i nc 1x j r a x = b ，x 0( 1 2 8 ) 其最优性条件为： f a x = b a 7 y + j c = 0 ( 1 2 9 ) iz 0 ，5 o ，x 7 j = 0 显然，( 1 2 9 ) 式是一混合线性互补问题( m l c p ) 。 考虑二次规划 r a i n 三j 7 0 x + c t x 2 s t a x = b x 0( 1 2 1 0 ) 其最优性条件为： fj = 一a 7 y + c a x = b( 1 2 ) lx o ，j 0 ，x r j = 0 ， ( 1 21 1 ) 式也是一混合线性互补问题。 考虑带不等式约束条件的非线性规划 m i n f ( x 1 ( 1 2 ，1 2 ) s ，g ( x ) s 0 ， 其中厂：r ”寸r ，g ：置”r ”为凸函数且n m ，其l a r g a n g e 函数为： 上( x ，“) = 厂( x ) + “7 9 ( x ) ， ( 1 2 1 3 ) 且其最优性条件 f v f ( x ) 一v g ( x ) 7 “= 0 l “0 , - g ( x ) o ，7 9 ( x ) = 0 ， 是一个混合互补问题。 对于一般的非线性规划问题 9 大连理工大学博士学位论吏 r a i n ，( j )( 1 、2 1 4 ) s t ( x ) = 0 g ( x ) 0 ， 其中，f ：r ”峙r ，g ：r ”哼r ”，h ：月”专r 。为凸函数且肝所，月，其l a g r a n g e 函 数为： l ( x ，“，v ) = f ( x ) 一“1a ( x ) + v 。g ( x ) ，( 1 。2 1 5 ) 令 f ( x ，u ，v ) = 【v ，l ( x ，“，v ) 一v 。z ( x ，“，v ) 一v ，l ( x ，u ，v ) 7 ，( 1 2 1 6 ) x ：= x r “i g ( 芏) 0 ，a ( x ) = o ，u ：= “r ” ；v ：= v r 。lz o ， 由于f ：r ”寸r ，g ：r ”- r ”，h ：r ”斗r7 为凸函，则非线性规划( 1 2 1 4 ) 式满足一 阶约束规范，从而下面的鞍点条件成立： ( z + ，“，v ) ( 工，“，v ) sl ( x ，“，v ) ， 其中：( x ， ，v ) k ：= x ux v 。从 7 5 知，非线性规划问题( 1 2 1 4 ) 式可以转化为一变 分不等式叫k n 问题。 鞍点问题中的一个重要情形就是扩展的线性一二次规划问题0 8 1 。设x ，y 均为 多胞形，令k ：= x y 则扩展的线性一二次规划问题为： l ( x ，y ) = 去x 7 a + p t x - - x t r y + q 7 y 一去y 7 q y ，( 1 2 1 7 ) z二 互补问题在交通平衡问题中有直接的应用。在所有分析交通堵塞问题 1 9 ，7 8 】 中，都需要定义一个由节点集合n 和弧线集合a 定义的运输网络。交通堵塞问题 模型就是用来预测网络在稳定状态下的交通流量。设沿给定弧线a t a 的费用是总 流量向量厂的非线性函数c a ( ，) ，其中，的分量五，b a 。令c ( ) 是由c a ( ，) ，n e 4 构成的向量。通常假设司机们为了使得他们的运输费用最小，而在运输网络中选 择运输路径时是完全不协调的。通常将集合n 分为始点集合0 和终点集合d ，o o 点对的集合w c 0 d 是给定的。设w s 妒为由起点0 到终点d 的运输流量需求。 般有两种方法建立给定交通网络的交通堵塞模型。一是以考虑起点到终点 ( o d ) 的所有路径为基础的；二是将每一个起点或终点视为不同的区域，将模型表 述为多区域形式。两类模型均为在w a r d r o p 平衡的意义上建立的，而w a r d r o p 平 衡被认为是n a s h 平衡 1 9 】的一个特殊情形。这里只将介绍第一种模型，第二种模 型经过适当的处理，也可以表述为一个互补问题。 给定w w ，令p 。为连接从0 1 3 的点对w 的所有路径的集合，并令p 为网络 p 。的集合；设乞表示路径p t 尸的流量：令流量善的函数( 善) 表示相应路径上的 l o 第1 章概论 流量费用。定义弧线路径关联矩阵，矩阵元素取为： 。fl 若线路p p 经过弧线d a 。” 10 其它 显然，和善之问满足关系f = 舌。当假设每条路径p 的花费( 善) 等于所有p 通过的弧线的花费，称该模型为加法型模型；最后，定义点对w ew 间的最小运费 的变量f 。在用路径描述的模型中，用函数d 。( r ) 表示点对w 间的运输需求，若每 一个d 。( r ) 都取为常数时，称该模型为固定需求模型，更一般的模型通常被称为弹 性需求模型。 w a r d r o p 平衡准则可以表述为：每一个司机在每一对起点终点间选取花费最 小的路径。按照该准则，被选定的路径的花费是相等的，而大于最小花费的路径 将没有流量。数学上，该准则可以简单地描述为：v w w ，p 只， 告p o ，0 ( 善) 一f 。o ，且亭p ( 7 0 ( 善) 一z w ) = 0 ( 1 2 ，1 8 ) 若乞屯( f ) ，v w 成立，则满足上述要求当要求零剩余量时，平衡条 件可以表述为