P(κ)线性互补问题宽邻域原始-对偶内点算法研究

摘要

1984年，N．Karmarkar提出了线性规划的一种新的多项式算法，该算法不仅比椭球算法具有更优越的计算复杂性，而且在实际计算中也可以与单纯形法相媲美，尤其对大规模问题更显其高效性．与单纯形算法沿着可行区域的边界寻优不同，Karmarkar算法是建立在单纯形结构之上的，它是从初始内点出发，沿着最速下降方向，从可行区域内部逐渐走向最优解．因此Karmarkar算法又被称为内点算法．自从Karmarkar划时代的论文发表以来，内点算法一直是数学规划领域一个非常活跃的研究方向． 互补问题的理论和算法在经济学，对策论和数学规划领域有着广泛的应用，关于互补问题的研究一直是非线性科学和计算科学的热点问题，求解互补问题的算法的研究也取得了很多成果。1991年,Kojima等人将已有的线性规划结论都推广到更一般的阵线性互补问题上，此后，线性规划内点算法能否推广到阵线性互补问题上成了衡量这种算法好坏的标准之一．因此，对阵线性互补问题算法的研究具有重要意义． 本论文重点研究阵线性互补问题和阵水平线性互补问题两种重要的非单调线性互补问题，针对上述两种互补问题，提出了几种宽邻域内点算法，详细分析了所给算法的迭代复杂性．全文各部分内容安排如下： 第一章为绪论。首先给出了互补问题的基本理论，然后介绍了内点算法的产生与研究现状。 第二章对阵线性互补问题提出了一种基于宽邻域的势函数约减算法，在较一般的情况下证明了算法的多项式复杂性． 第三章给出阵线性互补问题的一种基于邻近度量函数最小值的预估－校正算法，并在较一般的情况下证明了该算法是多项式时间算法． 第四章给出了求解 阵水平线性互补问题的一种基于一类self-regular邻近度量函数的预估－校正算法，并证明了算法具有目前最好的迭代复杂性． 第五章则是对本文工作的总结和对未来的展望。