一个求解P-互补问题的非内点路径跟踪算法

摘要

作为应用数学领域的一个重要分支,互补问题一直受到广大学者的青睐.由于其为数学、经济、工程等众多科学和技术领域中的实际问题提供了简单有效的数学模型,互补问题被认为是应用数学领域内十分重要的问题之一.互补问题的研究从1970年开始至今已经取得了非凡的成就,无论是在理论研究方面还是在算法设计方面,成绩斐然.该文的主要工作属于算法设计领域.提到算法,应用比较多的是求解线性互补问题的Lemke方法,从1970年前后它被提出就受到了众多学者的关注,良好的应用效果成为它引人注目的关键,但是在最坏情形下指数收敛又成为它不可弥补的缺陷.正是为了改正这一不足,众多其他类型的方法应运而生.这里特别要提到的是在求解线性规划问题的Karmarke内点法的基础上发展起来的非内点路径跟踪算法.这一类方法吸收了内点法良好的收敛性质以及非平滑算法的局部收敛性分析的优势,同时打破了内点法对初始点、迭代点必须是内点的限制.鉴于以上这些优势非内点路径跟踪算法吸引了许多学者从事这方面的研究,并取得了不错的成果.需要提出的是,对于解集无界的P<,0>-互补问题的算法研究还不是很多,主要的工作仅见于Chen和Ye[15],Zhao和Li[62,63,64].该文的主要工作是借鉴Zhao和Li[63]的思想为解决解集无界的P<,0>-互补问题提供一条新的非内点路径,并在此基础上建立一个非内点路径跟踪算法,进而分析算法的收敛性质.该文与现有的工作的不同在于(1)我们的非内点路径的建立不是基于Tikhonov正则而是基于对平滑CP-函数的扰动;(2)在我们的算法中μ不再被固定的看作是参数或者变量,而是同时具有这两种

目录

文摘

英文文摘

第一章绪论

§1.1 互补问题

§1.2互补问题的来源

§1.3非内点算法概述

§1.4符号与本文的结构

第二章一条新的非内点路径

§2.1平滑CP-函数和非内点路径

§2.2一个新的假设条件

§2.3新的非内点路径

第三章一个求解P0-互补问题的非内点算法

§3.1路径邻域

§3.2算法与整体收敛性

§3.3算法的收敛速度

第四章数值实验

§4.1路径实验

§4.2算法实验

后记

参考文献

致谢