混合互补问题的光滑化算法研究
VIP免费
摘 要
互补问题作为运筹学中一个热门的研究课题, 近几十年来, 数学研究工作者
们提出了很多求解互补问题的方法.一般来说,互补问题一方面可以通过等价转化
为光滑的或者非光滑的优化问题求解, 继而利用优化理论进行求解; 另一方面可
将其转化为等价的光滑的或者非光滑的方程组求解. 此类方法目前已经有效解决
了许多互补问题. 基于光滑函数的算法在互补问题中都取得了很好的数值计算效
果, 本文分别针对非线性互补问题和混合互补问题给出了相应的光滑化算法. 全
文共分三章.
第一章:介绍了互补问题的历史起源、研究现状和一些基本原理、定义, 简单
介绍了各类光滑化函数, 并给出了互补问题的算法概况.
第二章:对于混合互补问题, 在假定函数是 0
P
函数的的条件下, 给出了一类基
于双曲余弦光滑函数的自适应信赖域法. 在假定的条件下证明了算法的收敛性.
第三章:对于混合互补问题, 给出了一类基于 Lifting 光滑逼近函数的光滑牛顿
法, 在假定函数是连续可微的条件下, 证明了算法的全局收敛性和超线性收敛性;
继而将这种方法应用于非线性互补问题中, 最后通过数值试验结果显示了该算法
对非线性互补问题及混合互补问题的有效性.
关键词:光滑函数 混合互补问题 全局收敛性 自适应信赖域算法
数值试验
ABSTRACT
Complementary problem is a hot research topics of operations research. In recent
decades, mathematical scholars proposed many useful solving methods. One method for
solving complementarity problems is transforming the problems to a smooth or
nonsmooth optimization problem and then using the methods of solving optimization
problems to solve it; Another commonly used method is transforming the problems into
a smooth or nonsmooth equations. On the basis of these methods and some proper
algorithms, many complementarity problems have been solved effectively. The
algorithms based on smooth function have good numerical calculation when they are
used to solving complementarity problems, so, in this paper, we give the smoothing
algorithms for mixed complementarity problems and the nonlinear complementarity
problems. This paper includes three chapters.
Chapter 1: The historical origins of complementary problems and some basic
principles of complementarity problems are introduced. Some recent developments on
the smoothing function and algorithms for complementarity problems are discussed.
Chapter 2: We propose an adaptive trust region algorithm for the mixed
complementarity problems based on a cosh-based smoothing function smoothing
function. Under suitable assumptions, the global convergence property of algorithm is
proved.
Chapter 3: We propose a class of Newton method for mixed complementarity
problems based on a new smoothing function. We obtain the convergence of the
proposed algorithm under certian conditions. Some preliminary numerical and
numerical test results are given.
Key Words: Smoothing Function, Mixed Complementarity Problem,
Global Convergence, Self-adaptive Trust Region
Algorithm, Numerical Test.
目 录
中文摘要
ABSTRACT
第一章 绪 论 ......................................................... 1
1.1 互补问题及其算法研究进展 ..................................... 1
1.1.1 互补问题历史起源和研究现状 ................................. 1
1.1.2 互补问题的算法概况 ......................................... 2
1.1.3 互补问题的 NCP 函数和等价形式 ............................... 4
1.1.4 互补问题的基本概念及基本定理 ............................... 5
1.2 本文的主要研究内容 ........................................... 6
第二章 混合互补问题的自适应信赖域算法 ............................... 8
2.1 引言 ......................................................... 8
2.2 光滑化函数及相关性质 ......................................... 8
2.3 算法模型及其收敛性分析 ...................................... 12
2.3.1 信赖域算法的介绍 .......................................... 12
2.3.2 自适应信赖域算法 .......................................... 13
2.3.3 算法的全局收敛性 .......................................... 14
2.4 小结 ........................................................ 17
第三章 混合互补问题的 Lifting 价值函数及其算法 ......................... 18
3.1 引言 ........................................................ 18
3.2 预备知识 .................................................... 19
3.3 算法模型及收敛性分析 ........................................ 20
3.3.1 算法模型 ................................................... 20
3.3.2 算法的收敛性分析 ........................................... 21
3.4 非线性互补问题中的应用 ...................................... 22
3.4.1 算法模型 ................................................... 22
3.4.2 算法的收敛性分析 ........................................... 23
3.5 数值试验 .................................................... 24
附录 全文通用记号 .................................................. 26
参考文献 ............................................................ 27
在读期间公开发表的论文 .............................................. 30
致 谢 .............................................................. 31
第一章 绪 论
1
第一章 绪 论
本章叙述了互补问题的历史起源和研究现状, 阐述了互补问题的几种等价转
化形式以及算法概况, 给出了一些基本定义. 在本章第三节中, 列举了本文的主要
研究内容.
1.1 互补问题及其算法研究进展
1.1.1 互补问题历史起源和研究现状
1964 年Cottle R W 在其博士学位论文"Nonlinear Programs with Positively
Bounded Jacobians"中提出了"互补问题"这一数学模型. 互补问题在初期曾被称为"
基本问题"、"拼合问题"、或"互补转轴问题"等. Cottle 在1964 年的文[1]中和
Dantzig-Cottle 1967 年的文[2]指出:线性规划与二次规划是线性互补问题的特例.
而Cottle-Dantzig 1968 年的文[3]中提出双矩阵对策问题也是线性互补问题的一个
特例. 线性互补问题还包括了市场均衡问题和最优停止问题等. 非线性互补问题、
混合互补问题和隐互补问题则包括了更多的数学问题, 如一般非线性规划的 KKT
条件是混合互补问题的一个特例.
互补问题是指它包含的两组决策变量之间满足一种"互补关系". 在具体应用
时, 根据互补问题中的变量所满足的条件的不同和互补形式的不同, 可以将互补
问题划分成多种不同的形式. 下面, 我们着重介绍几种常见的互补问题，其定义可
参见文献[4,5].
1、线性互补问题
线性互补问题是:寻求 n
Rx , 满足
0, 0xMxq
, 0)( qMxxT
(1.1.1)
其中 nn
R
M
是一个 nn 实矩阵, n
Rq是一个 n维矢量. 线性互补问题记为
),( qMLCP .
2、非线性互补问题
非线性互补问题是:寻找一个向量 n
x
R满足如下关系:
0, () 0, ()=0
T
xFx xFx (1.1.2)
其中 nn RRF :是连续可微的非线性映射. 当()Fx是线性函数时, 则互补问
题(1.1.2)退化为线性互补问题(1.1.1), 否则称为非线性互补问题, 记为 ()NCP F .
3、混合互补问题
摘要：
展开>>
收起<<
摘要互补问题作为运筹学中一个热门的研究课题,近几十年来,数学研究工作者们提出了很多求解互补问题的方法.一般来说,互补问题一方面可以通过等价转化为光滑的或者非光滑的优化问题求解,继而利用优化理论进行求解;另一方面可将其转化为等价的光滑的或者非光滑的方程组求解.此类方法目前已经有效解决了许多互补问题.基于光滑函数的算法在互补问题中都取得了很好的数值计算效果,本文分别针对非线性互补问题和混合互补问题给出了相应的光滑化算法.全文共分三章.第一章:介绍了互补问题的历史起源、研究现状和一些基本原理、定义,简单介绍了各类光滑化函数,并给出了互补问题的算法概况.第二章:对于混合互补问题,在假定函数是0P函数的...
相关推荐
-
建筑工程投标文件范本-(格式)VIP免费
2024-11-22 17 -
幕墙工程施工组织设计方案VIP免费
2025-01-09 6 -
建筑商品砼生产项目创业计划书VIP免费
2025-01-09 10 -
建筑工程商业计划书模板VIP免费
2025-01-09 8 -
工程项目施工计划书VIP免费
2025-01-09 6 -
《专业型文档》建筑企业计划书VIP免费
2025-01-09 8 -
xx水库灌区管道工程水工图纸C1VIP免费
2025-01-09 13 -
邮政区域仓储配送中心VIP免费
2025-01-09 8 -
疾病预防控制中心招标文件VIP免费
2025-01-09 14 -
体育健身中心施工招标文件VIP免费
2025-01-09 11
作者：牛悦
分类：高等教育资料
价格：15积分
属性：32 页
大小：355.34KB
格式：PDF
时间：2024-11-11
