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

A Interior-point Algorithm with Full-Newton Steps for Monotone Linear Complementarity Problem Based on a Kernel Function

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

In this paper,a new full-Newton step interior-point algorithm is proposed based on a kernel function with linear growth term for monotone linear complementarity problem.This kernel function determines searching directions and the proximity measure between the iterates and the center path.By developing some new technical results,an iteration bound O（nL）that coincides with the currently best known iteration bound is derived for monotone linear complementarity problem.