基于核函数求解单调线性互补问题的新full-Newton步内点算法

吴　珊　张明望　黄正伟

(1. 三峡大学 理学院， 湖北 宜昌　443002； 2. 三峡大学 经济与管理学院， 湖北 宜昌　443002)



基于核函数求解单调线性互补问题的新full-Newton步内点算法

吴珊1张明望1黄正伟2

(1. 三峡大学 理学院， 湖北 宜昌443002； 2. 三峡大学 经济与管理学院， 湖北 宜昌443002)

摘要：本文对单调线性互补问题设计了一种基于核函数的full-Newton步内点算法．该核函数导出新的搜索方向并定义了迭代点到中心路径的邻近度量．通过应用新的技术引理，证明了该算法的多项式复杂性阶为L)，这与当前求解单调线性互补问题内点算法最好的迭代复杂性阶一致．

关键词：单调线性互补问题；full-Newton步；核函数；多项式复杂性

线性互补问题是运筹学与计算数学相互交叉的一个研究领域，为线性规划、二次规划提供了一个统一的研究框架，在经济学和工程中有着广泛的应用[1]．求解线性互补问题的算法很多，其中原始-对偶内点算法是一类非常重要而有效的算法[2-3]．

受文献[6-12]的启发，本文设计了一种基于具有线性增长项的核函数求解单调线性互补问题的新full-Newton步内点算法，并应用该核函数导出新的搜索方向且定义了迭代点到中心路径的邻近度量．同时，证明了该算法的多项式复杂性阶与当前求解线性互补问题内点算法最好的迭代复杂性阶一致．据我们所知，这是基于具有线性增长项核函数的第一个多项式full-Newton步内点算法．

文中记法：Rn表示n维欧式空间；e表示分量全为1的n维列向量；‖·‖1，‖·‖2和‖·‖∞分别表示向量的1-范数、2-范数和无穷范数；……