| 【中文题名】 | 非单调线性互补问题内点算法的研究 |
| 【英文题名】 | The Research of an Interior Point Algorithm for a Class of Nonmonotonic Linear Complementarity Problem |
| 【学科专业】 | 应用数学 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-8-16 |
| 【中关键词】 | 互补问题,内点算法,P_*,（κ）矩阵,多项式复杂性, |
| 【英关键词】 | complementarity problem,interior point algorithm,P_*（κ）-matrix,polynomial-time complexity, |
| 【分类导航】 | 数理科学和化学>数学>运筹学>规划论（数学规划）>线性规划> |
| 【论文摘要】 |
在1947年,Danzig提出了线性规划的概念及其著名的算法--单纯型算法,该算法具有很好的计算性能,但从复杂性理论上来讲并不理想;1978年,同样针对线性规划问题,Khachiyan提出了第一个线性规划的多项式算法--椭球算法,但是此算法的实际计算性能并不如单纯单纯形法,这就引起了许多学者试图去寻找新的具有较好计算性能的线性规划的多项式算法;1984年,Karmarkar对线性规划问题提出了一种势函数投影变换算法,从此一类新算法--内点算法被提出了,并使得这类新算法的研究成为近二十几年的热点问题.Karmarkar算法不仅比椭球算法具有更优越的计算复杂性,而且在实际计算中也可以与单纯型法媲美,尤其对大规划问题更显高效性.
本文主要研究了互补问题的内点算法.互补问题是一类非常重要的优化问题,它广泛应用在经济分析、交通平衡策略等社会经济模型中.因此,对互补问题的研究具有重要意义.本论文着重研究了非单调线性互补问题的几种内点算法,并详细分析了所给算法的收敛性.最后通过数值实验证明了我们所提出的算法是有效的.
全文共分五章.第一章首先介绍了互补问题的相关基本知识及最优化的发展历史和内点算法... |
| 【论文题纲】 |
|
内容摘要 |
4-5 |
|
Abstract |
5-8 |
|
引言 |
8-10 |
|
1 绪论 |
10-14 |
|
1.1 互补问题的基本概念 |
10-11 |
|
1.2 内点算法的产生 |
11-12 |
|
1.3 内点算法的研究现状 |
12-14 |
|
2 求解P(κ) 阵线性互补问题的高阶内点算法 |
14-29 |
|
2.1 窄邻域高阶内点算法 |
14-21 |
|
2.2 宽邻域高阶内点算法 |
21-28 |
|
2.3 小结 |
28-29 |
|
3 基于代数变换求解P_0 阵线性互补问题的不可行内点算法 |
29-35 |
|
3.1 算法的描述 |
29-31 |
|
3.2 算法的全局收敛性 |
31-34 |
|
3.3 小结 |
34-35 |
|
4 数值实验 |
35-37 |
|
5 全文总结与展望 |
37-38 |
|
参考文献 |
38-42 |
|
后记 |
42-43 |
|
附录：攻读硕士学位期间发表的论文 |
43 |
|
| 【DOI】 | LunWen.ID:2.2008.14840 |
