单调线性互补问题基于新的核函数的大步校正内点算法

摘要

提出了单调线性互补问题基于新的核函数的大步校正内点算法.这个核函数是强凸的,而且它既不是自正则函数也不是经典的对数函数.基于这个核函数,可以定义新的迭代方向和邻近度量.利用这个新的核函数的一些性质,得到新算法的迭代复杂性为O(√n(logn)2 log (n/ε)),这减少了大步校正原始-对偶内点算法的实际计算效果与理论复杂性之间的差距.%A large-update primal-dual interior-point method for monotonic linear complementarity problems based on a new kernel function is presented. The kernel function is strongly convex; and it is neither self-regular function nor the usual logarithmic function. Based on the new kernel function, new search direction and proximity measure are proposed. And using some appealing properties of the new function, the paper showsthat the new large-update method enjoys O(√n( logn)2 log (n/ε)) iteration, which reduce the gap between the practical behavior of the methods and the theoretical performance results.