互补系统的非光滑方法

VIP免费
3.0 牛悦 2024-11-19 9 4 665.1KB 104 页 15积分
侵权投诉
摘 要
本文主要对具有十分重要的理论与现实应用意义的互补系统问题进行研究。
互补系统问题是一类重要的优化问题，在实际问题的求解中主要用于求解出现在
工程技术、经济领域与交通领域的均衡问题，如 Nash 均衡问题、交通均衡问题等
各种相关问题。理论方面，主要在求解非线性规划的约束优化问题、KKT 最优性
条件等方面有重要的应用。
本文主要分七部分对互补系统问题的非光滑方法进行研究，以下为主要的研
究工作介绍。
1．对与求解互补系统问题相关并且在求解变分问题、均衡问题与工程问题
中有重要应用的非光滑方程系统以及极大值方程系统的算法进行了研究，给出了
参数牛顿法与几种修正的 Levenberg-Marquardt 算法。在较为温和的条件下证明
了算法的收敛性，并且给出了与以往算法比较的数值实验。通过数值实验表明了
算法的有效性。
2．给出求解非线性互补系统问题的两种非单调 Levenberg-Marquardt 算法，
在较为温和的条件下证明了算法的全局收敛性。
3．对垂直互补系统问题给出了参数牛顿法与修正的 Levenberg-Marquardt
算法，在较为温和的条件下分别给出了参数牛顿法的局部超线性收敛结果与数值
实验以及修正的 Levenberg-Marquardt 算法的全局收敛性结果与数值实验。
4．对广义非线性互补系统问题进行了研究，基于互补函数把非线性互补系
统问题转化为非光滑方程系统，给出了近似牛顿法与超线性收敛的参数牛顿法以
及全局收敛的修正 Levenberg-Marquardt 算法，并且分别给出相应的超线性收敛
与全局收敛性定理与数值实验。
5．利用一族新的价值函数对非光滑互补系统问题进行了研究，在互补函数
连续但不要求 Lipschitz 连续条件下，给出了非光滑互补系统问题的免梯度算法，
并且证明了免梯度算法的全局收敛性结果。
关键词：非线性互补 非光滑方程 极大值函数 非光滑互补 非单调
Levenberg-Marquardt 算法 全局收敛
ABSTRACT
This dissertation mainly study complementarity problem, which is very useful in
theory analysis and practice. Complementarity problem is also a very useful
optimization problem, which can be used in the study of constrained optimization,
Karush-Kuhn-Tucker systems of nonlinear programming problems and many problems
in mechanics and engineering, equilibrium problems in economic and transportation,
such as Nash equilibrium, equilibrium traffic assignment and etc.
This dissertation study the nonsmooth algorithms for complementarity problem
with seven parts. Summarizing the entire dissertation, the paper’s primary research job
is as follows.
1. For solving complementarity problems, we firstly study the algorithms of
nonsmooth systems of equations and finitely many maximum functions systems, which
also have been proposed in the study of variational problem, equilibrium problem and
engineering mechanics. A parameterized Newton method and some kinds of modified
Levenberg-Marquardt method have been presented for nonsmooth systems of
equations and finitely many maximum functions systems. Under mild assumptions, the
present methods are shown to be convergence. Some numerical results comparing the
proposed methods with classical reformulations indicate that the methods work quit
well in practice.
2. We present the convergence of two nonmonotone Levenberg-Marquardt algorithms
for nonlinear complementarity problem. Under mild assumptions, the nonmonotone
Levenberg- Marquardt algorithms are shown to be globally convergent.
3. A kind of parameterized Newton method and modified Levenberg-Marquardt
algorithm are given for a kind of vertical complementarity problem. Under mild
assumptions, locally superlinear convergence results are also proved for parameterized
Newton method. And global convergence results are given for modified Levenberg
Marquardt algorithm. Numerical tests are also listed.
4. We deal with a general nonlinear complementarity problem. Based on a nonlinear
complementarity function, it is transformed into a system of nonsmooth equations.
Then approximate Newton methods, parameterized Newton method and modified
Levenberg-Marquardt algorithm are developed and their superlinear convergence and
global convergence are proved. Numerical tests are also listed.
5. A family of new merit functions are used to deal with nonsmooth complementarity
problem where the underlying function is assumed to be a continuous but not
necessarily locally Lipschitzian map. A derivative free descent algorithm for sloving
the nonsmooth continuous complementarity problem is proposed. In addition, we
prove the global convergence of the derivative free descent algorithm.
Key words: Nonlinear complementarity Nonsmooth equations
Maximum functions Nonsmooth complementarity Nonmonotone
Levenberg-Marquardt algorithm Global convergence
目 录
中文摘要
ABSTRACT
第一章 绪 论 .....................................................1
§1.1 系统思想的起源与发展 .....................................1
§1.1.1 系统科学在我国的发展 ..................................3
§1.2 系统科学的技术科学层次 ...................................4
§1.3 运筹学问题 ...............................................4
§1.4 互补系统问题的来源与发展 .................................6
§1.4.1 互补系统问题的解法 ...................................7
§1.4.2 特殊互补系统问题的求解方法 ..........................12
§1.4.3 非光滑方程系统研究意义 ..............................12
§1.4.4 非光滑方程系统的求解方法 ............................14
§1.5 互补系统问题的应用 ......................................15
§1.6 互补系统问题近期的国内外研究现状 ........................16
§1.7 本文主要工作与论文结构 ..................................17
§1.8 本章小结 ................................................22
第二章 非光滑方程系统的求解方法 .................................23
§2.1 极大值方程系统的参数牛顿法 ..............................23
§2.1.1 引言 ................................................23
§2.1.2 预备知识 ............................................24
§2.1.3 参数牛顿法 ..........................................25
§2.1.4 数值实验 ............................................26
§2.2 非光滑方程的修正 Levenberg-Marquardt 算法及其局部收敛性 ..28
§2.2.1 引言 ................................................28
§2.2.2 预备知识 ............................................28
§2.2.3 修正 Levenberg-Marquardt 算法与收敛性 ................29
§2.2.4 数值实验 ............................................31
§2.3 非光滑方程的修正 Levenberg-Marquardt 算法及其全局收敛性 ..35
§2.3.1 引言 ................................................35
§2.3.2 预备知识 ............................................37
§2.3.3 修正的 Levenberg-Marquardt 算法及其全局收敛性 ........37
§2.3.4 数值实验 ............................................43
§2.4 本章小结 ................................................48
第三章 非线性互补系统问题的非单调 Levenberg-Marquardt 算法 .......49
§3.1 问题介绍 ................................................49
§3.2 基础知识 ................................................50
§3.3 非单调 Levenberg-Marquardt 算法及其收敛性 ................51
§3.4 算法讨论 ................................................58
§3.5 本章小结 ................................................59
第四章 求解垂直互补系统问题的非光滑方法 .........................61
§4.1 介绍 ....................................................61
§4.2 预备知识 ................................................62
§4.3 近似牛顿法的超线性收敛性与数值实验 ......................63
§4.4 修正的 Levenberg-Marquardt 算法以及数值实验 ..............66
§4.5 本章小结 ................................................68
第五章 广义互补系统问题的非光滑方法 .............................69
§5.1 问题介绍与预备知识 ......................................69
§5.2 近似牛顿法 ..............................................71
§5.3 参数牛顿法与数值实验 ....................................73
§5.4 修正的 Levenberg-Marquardt 算法以及数值实验 ..............76
§5.5 F-B 函数转化法 ...........................................77
§5.6 本章小结 ................................................78
第六章 非光滑互补系统问题的价值函数与免梯度算法的全局收敛性 .....79
§6.1 介绍 ....................................................79
§6.2 预备知识 ................................................80
§6.3 价值函数的最优性 ........................................81
§6.4 收敛的免梯度算法 ........................................83
§6.5 本章小结 ................................................86
第七章 总结与展望 ...............................................87
§7.1 全文工作总结 ............................................87
§7.2 论文的主要研究内容和研究成果 ............................87
§7.3 进一步研究展望 ..........................................87
参考文献 ........................................................89
第一章 绪论
1
第一章 绪论
§1.1 系统思想的起源与发展
系统科学(Systems science)作为一个大门类的学科，形成于 20 世纪中叶
]101[ −。与系统科学密切相关的科学的系统思想源远流长，经历了孕育、形成与发展
的漫长过程。系统科学中的系统思想是关于事物整体性观念、相互联系观念、演
化发展观念的统一。系统概念来源于古代人类社会丰富的实践经验，在与自然系
统的交往中，人类的生产活动不断丰富。从流传至今的《诗经》、《黄帝内经》等
巨著到都江堰大型水利工程以及农历节气等古代农事、医药、天文成就，在不同
程度上闪耀着古代朴素系统科学的光辉。同时古代中国与古希腊的哲学思想也反
映了朴素的系统概念，古代中国与古希腊的唯物主义思想家都从物质本原出发，
把自然界当成统一体对待。古希腊的赫拉克利特、我国春秋时期的老子为古代东、
西方朴素唯物主义哲学思想的代表，都强调对自然界整体性、统一性的认识，包
含了系统科学思想的萌芽。
15 世纪下半叶，随着力学、天文学、物理学、化学、生物学等科目从统一混
沌的自然哲学中分离出来，近代科学开始了日新月异的发展。近代自然科学发展
了研究自然界的独特分析方法，利用实验、解剖与观察对自然界的细节进行分门
别类的研究。19 世纪上半叶，自然科学取得了能量转化、细胞与进化论三个伟大
的发现，有力推动了人类对自然过程相互联系的认识。对此恩格斯评论到：“由于
这三大发现和自然科学的其他巨大进步，我们现在不仅能够指出自然界中各个领
域内的过程之间的联系，而且总的说来也能指出各个领域之间的联系了，这样，
我们就能够依靠经验自然科学本身所提供的事实，以近乎系统的形式描绘出一幅
自然界联系的清晰图画。描绘这样一幅总的图画，在以前是所谓自然哲学的任务。
而自然哲学只能这样来描绘：用观念的、幻想的联系来代替尚未知道的现实的联
系，用想象来补充缺少的事实，用纯粹的臆想来填补现实的空白，它在这样做的
时候提出了一些天才的思想，预测到一些后来的发现，但是也发表了十分荒唐的
见解，这在当时是不可能不这样的。今天，当人们对自然研究的结果只要辨证地
即从它们自身联系进行考察，就可以制成一个在我们这个时代是令人满意的“自
然体系”的时候，当这种联系的辨证性质，甚至违背自然研究者的意志使他们受
过形而上学训练的头脑不得不承认的时候，自然哲学就最终被排除了”。19 世纪的
自然科学为唯物主义自然观建立了坚实的基础，为马克思主义哲学提供了丰富的
材料。马克思、恩格斯的辨证唯物主义认为，物质世界是由无数相互联系、相互
依赖、相互制约、相互作用的事物和过程所形成的统一整体。辨证唯物主义体现
的物质世界普遍联系与整体性的思想就是系统思想，19 世纪，系统思想进一步从
互补系统的非光滑方法
2
经验上升为哲学，从辨证发展到定性论述。
随着现代科学、技术、文化的发展，科学的定量的系统思想形成了。现代科
学技术在 20 世纪中期对系统思想方法作出了两大贡献，第一使系统思想定量化，
成为一套具有数学理论、能够定量处理系统各组成部分相互联系的科学方法。第
二为定量化系统思想的实际应用提供了强大计算能力的计算机。同时，科学的定
量化的系统思想形成也来源于社会实践的需要。当代社会活动的大型化、复杂化，
使系统思想方法不仅要定性，而且重要的是要定量。以第二次世界大战为标志点，
定量化的系统方法开始广泛的应用到分析大型的工程、经济、社会复杂系统问题。
从取得数学表述形式与计算开始，系统思想方法从一种哲学思维发展成为专门的
科学。总之，系统思想是进行分析与综合的辨证思维工具，它从辨证唯物主义得
到哲学表达形式，从运筹学等定量学科得到定量的表述形式，从系统工程得到了
实践的内容。
系统科学作为现代科学技术体系中的一个大部门，是综合、横断的新兴科学
技术部门，其形成与发展与科学技术息息相关 ]1611[ −。系统科学是从事物的整体与
部分、全局与局部以及层次结构关系这个角度来研究客观世界，客观世界包括自
然的和人造的，而人也是客观世界的一部分。
人类对客观世界的认识与改造遵循从整体到局部，再到整体的模式。能反映
事物整体与部分、全局与局部以及层次关系的基本概念为系统。系统是由一些相
互关联、相互影响、相互作用的组成部分所构成并具有某种功能的整体。系统科
学是以系统为研究与应用对象的科学与技术。科学家明确地把系统作为研究对象
是以贝塔郎菲提出“一般系统论”概念为标志。20 世纪 40 年代出现的系统论、运
筹学、控制论、信息论是系统科学理论，系统工程、系统分析、管理科学是系统
科学的工程应用。同时物理学、数学、理论生物学、系统生态学等其他技术的发
展与新突破进一步揭示了系统的一些性质与规律。例如：由于生产规模的扩大，
生产技术的复杂以及科学研究涉及部门与专业越来越多，出现了大规模的生产系
统、技术系统与科学系统。这些系统的出现要求人们要从整体和相互联系的角度
考虑问题，要求制定处理大规模复杂系统问题的科学方法。1957 年美国的古德和
麦考尔合作出版了第一本以“系统工程”命名的书籍，二战以后美国的兰德公司
在处理解决大型社会经济系统问题时，提出了“系统分析”，针对大型经营管理技
术以泰勒为代表的科学管理发展为“管理科学”。70 年代末，钱学森给出了系统科
学体系结构：处在应用技术层次上为系统工程、在技术科学层次为运筹学、控制
论与信息论等学科、在基础科学层次上为系统学 ]41[ −。70 年代的艾根在进化论与自
组织理论的基础上，提出了“超循环”理论，阐述了自然界演化的自组织原理。
第一章 绪论
3
另外，托姆对突变现象与理论作出了一系列系统深刻的论述。
20 世纪 80 年代以来，对系统科学发展起较大推动的为非线性科学与复杂性科
学研究的兴起 ]9[ 。非线性科学的研究进一步推动了人类对世界本质的认识，客观
世界的一切事物都是相互作用体与相互作用过程，非线性是数学概念，是相互作
用的数学表达。一个系统不仅是各个部分的总和，叠加原理的失效，就是数学上
的非线性。非线性科学研究的成果极大丰富和深化了系统科学和系统工程定量化
的发展，进一步推动了复杂性研究的兴起 ]199[ −。上世纪 40 年代末，系统科学的先
驱者贝塔朗菲已经提出研究复杂性问题。信息论创始人之一的韦弗同样把有组织
复杂性作为系统科学的研究对象。关于复杂性传统的理解是简单与复杂相对的，
一个事物在未被认识以前为复杂的，一旦认识了解就成了简单的。但随着现代科
学技术的发展，人们发现复杂性是客观存在的，真正的复杂性即使人们认识了特
有的规定性，仍然是复杂的。复杂性具有多样性、高度非线性化、非光滑、多个
体等特征。近期复杂性科学研究的兴起是以圣菲研究所的建立为标志，研究所以
三位诺贝尔奖获得者为首，组织了一批不同科学研究领域的科学家。他们的研究
宗旨为开展跨学科、跨领域的复杂性科学研究，认为事物的复杂性是从简单性发
展来的，是在适应环境的过程中产生。他们把经济、生态、计算机网络等称为复
杂适应系统，同时认为存在某些一般性的规律控制复杂适应系统的行为。非线性、
远离平衡、混沌、分形、模糊性都是复杂性的表现，把复杂性当作复杂性处理，
才是复杂系统理论所要求的简化。对复杂性科学的研究反映了现代科学技术发展
的综合趋势，是不同科学领域的共识。
§1.1.1 系统科学在我国的发展
系统科学在我国的研究工作是从早期推广运筹学开始，运筹学从 1955 年开始
在我国科学界掀起了应用与理论研究的热潮 ]9,5[ 。1956 年在中国科学院力学研究所
成立了我国第一个运筹学研究组，1960 年的年底中国科学院力学研究所与中国科
学院数学研究所的两个运筹学研究室合并为数学研究所的运筹学研究室。在华罗
庚、钱学森、许国志等老一辈科学家的努力下，在我国的科学界不断掀起“统筹
法”、“图上作业法”、“中国邮路问题”、“系统工程”等应用热潮。1980 年 11 月在
北京召开的中国系统工程学会成立大会，为以系统工程为代表的中国系统科学研
究奠定了新的基础。随着系统工程在社会、经济、科学技术等各方面的应用研究
不断深入，系统理论的基础研究也不断发展。从 1986 年开始的“系统学讨论班”
活动由钱学森院士亲自指导，为系统科学在我国的发展作出不可磨灭的贡献。讨
论班总结提出了系统研究方法，明确了系统学是研究系统结构与功能的一般规律
的科学，形成了系统学的提纲与内容。20 世纪 80 年代中期，在钱学森院士的指导
互补系统的非光滑方法
4
参与下我国系统学研究界提出了“复杂巨系统”概念。1990 年发表的论文 “一个
科学新领域——开放的复杂巨系统及其方法论” ]2[ ，表明我国的系统科学研究在
国际研究前沿有了自己独特的见解 ]85[ −。钱学森院士对复杂性问题的评述为：“凡
是不能用还原论方法处理的或不宜用还原论方法处理的问题，需要用或宜用新的
科学方法处理的问题，都是复杂性问题，复杂巨系统就是这类问题 ]5[ ”。对我国学
者的研究工作，协同学创始人哈肯曾说：“系统科学的概念是由中国学者较早提出
的，我认为这是很有意义的概括，并在理解和解释现代科学，推动其发展方面是
十分重要的”。
§1.2 系统科学的技术科学层次
技术科学层次的系统科学主要包括信息论、控制论、运筹学，技术科学研究
的问题来源于工程实践。钱学森院士认为：“技术科学的目的是把工程实际中所用
的许多设计原则加以整理与总结，使之成为理论，因而也就是把工程实际的各个
不同领域的共同性显示出来，而且也有力地说明一些基本概念的重大作用 ]101[ −”。
在系统学原理指导下对通信工程、控制工程、经营管理活动的实践经验加以理论
总结，用系统观点与方法阐述相关的概念，制定一般的理论框架，就是技术层次
的系统科学。在技术科学层次，系统科学关心的是系统的功能、效益、用途。在
技术科学层次的系统理论中包含了大量的可控制、可行解、最优策略等反映能动
性的概念，但任何系统的管理、运筹决策等都在限制条件下进行。因此，技术层
次的系统科学理论都是在一定限制条件下发挥能动性的科学理论。
在人们实践过程的运筹决策、管理中，人类的常理是要把办的事情办成、办
好、力争办的最好，这种常理就是最优性原理。为达到最优化目的、根据最优化
理论制定的各种解决不同具体问题的方法就是最优化方法。面对今天开放的复杂
巨系统，最优化理论与方法应该结合实际，坚持按照从定性到定量综合集成的方
法论思想处理问题。对较为简单的系统在完全理性和信息完备的假设之上，寻求
系统“最优解”。对比较复杂的系统在完全理性和信息完备的假设之上，寻求系统
“可行解”、“满意解”。
§1.3 运筹学问题
技术科学层次的系统科学主要包括信息论、控制论、运筹学，但在系统科学
的三门技术科学中，运筹学与自然科学的技术科学区别最明显 ]111[ −。自然科学中的
技术科学研究对象为物质运动与能量转换，抛开了人的活动。运筹学则是研究人
们基于一定物质客观条件的办事过程，抛开了物质运动与能量转移。研究成果看，
自然科学中的技术科学解答的是问题的答案，运筹学提供给人们的是策略、最优
化方法。另外，自然科学中的技术科学体现着物理学的痕迹，运筹学则出现了很
第一章 绪论
5
多如：策略、合作、对策等反映人类活动的描述性词汇。
运筹学问题主要是指在人类生活实践中出现的，要通过定性谋划与定量计算
而制定出策略、方案的问题，是能用数学语言描述的事理问题。钱学森院士对运
筹学问题的介定为：“我们的运筹学不包括系统工程的内容，而只包括了系统工程
的特殊数学理论 ]101[ −”。
一切运筹学问题都是由目标、约束条件、决策方案构成的系统，实际的运筹
学问题种类繁多，不同的典型问题发展成不同的分支。但不同分支的任务都是正
确的对运筹学问题进行充分分析，以系统观点为指导，寻求解决问题的算法，在
满足不同的约束条件下给出最优策略或最优解。以下介绍几类运筹学问题 ]20,18,15[ 。
（1）规划论. 为运筹学的一个重要分支，主要是建立模型后，求模型的最优
解，研究解的特性，是典型的运筹数学范畴。主要的研究为各种模型的算法设计
与分析，在提供好算法的基础上，利用数学手段来论证事理规律，建立关于事理
的理论。主要模型有线性规划模型、非线性规划模型、整数规划模型、目标规划
模型、动态规划模型等。在满足一定的约束条件下给出最优算法，在现代工业、
农业、经济管理、交通均衡、军事等各个领域都有广泛深刻的影响。
（2）图论与网络优化. 广泛应用于自然科学、工程技术和生产管理等领域，
各种通讯和计算机网络的优化设计、交通网络的合理分布以及大型工程项目的计
划管理等都需要运用图论与网络分析的方法解决。图论在化学、物理、遗传学、
控制论、信息论、人工智能、经济学、系统工程、社会人文科学等领域都有大量
的应用。最小支撑树、最短路、最大流、中国邮递员问题、旅行商问题等都是图
论与网络优化的重要组成部分。
（3）排队论. 研究公共服务系统运行与优化的数学理论与方法，通过对随机
服务现象的统计研究，找出反映随机现象的平均特性，研究提高服务系统的工作
效率。
（4）决策论. 主要应用于科学经营管理高中层决策，为科学的解决带有不确
定性和风险性决策问题所发展的系统分析方法，目的是提高科学决策水平，减少
决策失误的风险。
（5）库存论. 研究经营生产中各种物资应该在何时间以多少来补充库存，目
的是使库存与采购的总费用最小，在提高系统工作效率与降低产品成本上有重要
应用。
（6）对策论. 是一种研究在竞争环境下决策者行为的数学方法，在社会政治、
经济、军事活动与日常生活的竞争、斗争的场合都可应用。竞争各方为达到各自
的利益和目标，必须考虑对方可能的策略，然后选取对自己有利的策略，确定合
摘要：

摘要本文主要对具有十分重要的理论与现实应用意义的互补系统问题进行研究。互补系统问题是一类重要的优化问题，在实际问题的求解中主要用于求解出现在工程技术、经济领域与交通领域的均衡问题，如Nash均衡问题、交通均衡问题等各种相关问题。理论方面，主要在求解非线性规划的约束优化问题、KKT最优性条件等方面有重要的应用。本文主要分七部分对互补系统问题的非光滑方法进行研究，以下为主要的研究工作介绍。1．对与求解互补系统问题相关并且在求解变分问题、均衡问题与工程问题中有重要应用的非光滑方程系统以及极大值方程系统的算法进行了研究，给出了参数牛顿法与几种修正的Levenberg-Marquardt算法。在较为温和...

展开>> 收起<<
互补系统的非光滑方法.pdf

共104页,预览10页

还剩页未读， 继续阅读

相关推荐

更多
立即下载
作者：牛悦 分类：高等教育资料 价格：15积分 属性：104 页 大小：665.1KB 格式：PDF 时间：2024-11-19

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

推荐作者

热门标签

/ 104
评分 收藏
分享
立即下载 VIP免费下载
客服
关注