互补系统的非光滑方法

VIP免费

3.0 牛悦 2024-11-19 4 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 系统思想的起源与发展

系统科学(Systems science)作为一个大门类的学科，形成于 20 世纪中叶

]101[ −。与系统科学密切相关的科学的系统思想源远流长，经历了孕育、形成与发展

的漫长过程。系统科学中的系统思想是关于事物整体性观念、相互联系观念、演

化发展观念的统一。系统概念来源于古代人类社会丰富的实践经验，在与自然系

统的交往中，人类的生产活动不断丰富。从流传至今的《诗经》、《黄帝内经》等

巨著到都江堰大型水利工程以及农历节气等古代农事、医药、天文成就，在不同

程度上闪耀着古代朴素系统科学的光辉。同时古代中国与古希腊的哲学思想也反

映了朴素的系统概念，古代中国与古希腊的唯物主义思想家都从物质本原出发，

把自然界当成统一体对待。古希腊的赫拉克利特、我国春秋时期的老子为古代东、

西方朴素唯物主义哲学思想的代表，都强调对自然界整体性、统一性的认识，包

含了系统科学思想的萌芽。

15 世纪下半叶，随着力学、天文学、物理学、化学、生物学等科目从统一混

沌的自然哲学中分离出来，近代科学开始了日新月异的发展。近代自然科学发展

了研究自然界的独特分析方法，利用实验、解剖与观察对自然界的细节进行分门

别类的研究。19 世纪上半叶，自然科学取得了能量转化、细胞与进化论三个伟大

的发现，有力推动了人类对自然过程相互联系的认识。对此恩格斯评论到：“由于

这三大发现和自然科学的其他巨大进步，我们现在不仅能够指出自然界中各个领

域内的过程之间的联系，而且总的说来也能指出各个领域之间的联系了，这样，

我们就能够依靠经验自然科学本身所提供的事实，以近乎系统的形式描绘出一幅

自然界联系的清晰图画。描绘这样一幅总的图画，在以前是所谓自然哲学的任务。

而自然哲学只能这样来描绘：用观念的、幻想的联系来代替尚未知道的现实的联

系，用想象来补充缺少的事实，用纯粹的臆想来填补现实的空白，它在这样做的

时候提出了一些天才的思想，预测到一些后来的发现，但是也发表了十分荒唐的

见解，这在当时是不可能不这样的。今天，当人们对自然研究的结果只要辨证地

即从它们自身联系进行考察，就可以制成一个在我们这个时代是令人满意的“自

然体系”的时候，当这种联系的辨证性质，甚至违背自然研究者的意志使他们受

过形而上学训练的头脑不得不承认的时候，自然哲学就最终被排除了”。19 世纪的

自然科学为唯物主义自然观建立了坚实的基础，为马克思主义哲学提供了丰富的

材料。马克思、恩格斯的辨证唯物主义认为，物质世界是由无数相互联系、相互

依赖、相互制约、相互作用的事物和过程所形成的统一整体。辨证唯物主义体现

的物质世界普遍联系与整体性的思想就是系统思想，19 世纪，系统思想进一步从

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

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

展开>> 收起<<

互补系统的非光滑方法.pdf

共104页,预览10页

还剩页未读，继续阅读

互补系统的非光滑方法

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: