混合互补问题的光滑化算法研究

VIP免费

3.0 牛悦 2024-11-11 5 4 355.34KB 32 页 15积分

侵权投诉

摘要

互补问题作为运筹学中一个热门的研究课题, 近几十年来, 数学研究工作者

们提出了很多求解互补问题的方法.一般来说,互补问题一方面可以通过等价转化

为光滑的或者非光滑的优化问题求解, 继而利用优化理论进行求解; 另一方面可

将其转化为等价的光滑的或者非光滑的方程组求解. 此类方法目前已经有效解决

了许多互补问题. 基于光滑函数的算法在互补问题中都取得了很好的数值计算效

果, 本文分别针对非线性互补问题和混合互补问题给出了相应的光滑化算法. 全

文共分三章.

第一章:介绍了互补问题的历史起源、研究现状和一些基本原理、定义, 简单

介绍了各类光滑化函数, 并给出了互补问题的算法概况.

第二章:对于混合互补问题, 在假定函数是 0

函数的的条件下, 给出了一类基

于双曲余弦光滑函数的自适应信赖域法. 在假定的条件下证明了算法的收敛性.

第三章:对于混合互补问题, 给出了一类基于 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 互补问题历史起源和研究现状

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



是一个 nn 实矩阵, n

Rq是一个 n维矢量. 线性互补问题记为

),( qMLCP .

2、非线性互补问题

非线性互补问题是:寻找一个向量 n

R满足如下关系:

0, () 0, ()=0

xFx xFx (1.1.2)

其中 nn RRF :是连续可微的非线性映射. 当()Fx是线性函数时, 则互补问

题(1.1.2)退化为线性互补问题(1.1.1), 否则称为非线性互补问题, 记为 ()NCP F .

3、混合互补问题

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

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

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

摘要互补问题作为运筹学中一个热门的研究课题,近几十年来,数学研究工作者们提出了很多求解互补问题的方法.一般来说,互补问题一方面可以通过等价转化为光滑的或者非光滑的优化问题求解,继而利用优化理论进行求解;另一方面可将其转化为等价的光滑的或者非光滑的方程组求解.此类方法目前已经有效解决了许多互补问题.基于光滑函数的算法在互补问题中都取得了很好的数值计算效果,本文分别针对非线性互补问题和混合互补问题给出了相应的光滑化算法.全文共分三章.第一章:介绍了互补问题的历史起源、研究现状和一些基本原理、定义,简单介绍了各类光滑化函数,并给出了互补问题的算法概况.第二章:对于混合互补问题,在假定函数是0P函数的...

展开>> 收起<<

混合互补问题的光滑化算法研究.pdf

共32页,预览4页

还剩页未读，继续阅读

混合互补问题的光滑化算法研究

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: