线性互补问题基于核函数的内点算法

摘要

全文共分五章，在第一章主要概述了互补问题的各种形式及求解互补问题的几种主要算法，尤其对本文研究的算法-原始-对偶内点算法，做了比较详细的介绍，给出了用原始-对偶内点算法求解线性规划问题的具体过程和算法复杂性分析。第二章介绍了核函数的基本概念及其在算法中的作用，对已有的核函数做了简单的概括，并提出本文所研究的核函数的形式，研究和概括了此种形式下这类核函数需具有的性质。第三章介绍了单调线性互补问题的-些理论基础，研究了求解单调线性互补问题的基于一般核函数的路径跟踪内点算法，分析了算法的复杂性，得出了算法的一个统一迭代界.对于不同的核函数，提供了一种计算其算法理论迭代界的方法，并对核函数的形式和性质做了进一步的推广。在论文的第四章中，就一些具体的核函数，得出了大步和小步校正算法的理论迭代界，并选取具体核函数，用本文设计的算法，对具体算例进行了计算，得出了数值结果.最后，在第五章对全文的研究工作做了总结，并对将来的研究工作做了展望.

目录

文摘

英文文摘

声明

第一章 引言

§1.1互补问题

§1.1.1互补问题的类型

§1.1.2互补问题的解法

§1.2内点算法

§1.2.1内点算法的背景和类型

§1.2.2原始-对偶内点算法

§1.3本文的研究背景和主要工作

§1.4注记

第二章 一般核函数的形式和性质

§2.1核函数的定义及其作用

§2.2已有的核函数及其研究

§2.3一般核函数的形式和性质

§2.3.1ψb(t)的性质

§2.3.2ψ(t)的性质

第三章 解单调线性互补问题的基于一般核函数的内点算法

§3.1单调线性互补问题

§3.2单调线性互补问题的基于一般核函数的内点算法

§3.2.1中心路径

§3.2.2搜索方向

§3.2.3算法

§3.3复杂性分析

§3.3.1ψ(υ)的性质

§3.3.2ψ(υ)在内迭代中的减小过程

§3.3.3算法的理论迭代界及其计算方法

§3.4核函数推广及相应的算法复杂性

第四章 数值结果

§4.1几种核函数的理论迭代界

§4.2算例和数值

§4.2.1算例和数值一

§4.2.2算例和数值二

第五章 结论与展望

参考文献

作者攻读硕士期间完成的论文

致谢