线性权互补问题的全牛顿步可行内点算法

作     者：张睿婕 

作者单位：桂林电子科技大学 

学位级别：硕士

导师姓名：迟晓妮

授予年度：2020年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

主      题：线性权互补问题 全牛顿步 可行内点算法 核函数 迭代复杂度 

摘      要：权互补问题是一类重要的新优化问题,当权向量为零时该问题退化为互补问题.科学和工程领域一大类均衡问题可以建模为权互补模型求解,甚至在某些情况下优于建模为互补模型求解.故研究权互补问题的理论和算法具有十分重要的实际意义.相对于互补问题而言,非零权向量使得权互补问题的理论和算法研究更为繁杂.目前,关于权互补问题的研究尚不多见.本文给出求解线性权互补问题的全牛顿步可行内点算法.具体如下:1.设计修正全牛顿步可行内点算法,求解非负象限上的权互补问题.算法采用修正全牛顿步避免线性搜索,简化了迭代过程.分析了算法的严格可行性和多项式时间迭代复杂度.数值算例表明了该算法对于求解线性权互补问题是有效的.2.提出基于核函数的全牛顿步可行内点算法,求解线性权互补问题.运用局部核函数等价变换中心路径.该算法每步迭代只用求解一个线性方程组,节省了计算时间与内存.每次迭代选取适当参数,分析了该算法的严格可行性,证明了算法具有多项式时间复杂度.数值算例结果表明算法的有效性.3.基于一个连续可微函数,给出求解非负象限上权互补问题的一种新全牛顿步可行内点算法.该算法定义了迭代点到中心路径的邻近测度,且每步迭代不需要线搜索.通过选择适当参数,分析了算法的严格可行性,证明了算法迭代复杂度与线性优化目前最好的多项式时间复杂度相同.分析算法求解线性权互补问题的数值实验结果,表明算法的有效性及不同参数值对于算法迭代的影响.