单调线性互补问题的全牛顿步内点算法

A Full-Newton Step Interior-Point Algorithm for Monotone Linear Complementarity Problems

针对单调线性互补问题,构造了新的核函数.通过构造的核函数来确定搜索方向和逼近度量,接着给出了求解单调线性互补问题的全牛顿步内点算法,最后给出了算法的复杂性界.所构造核函数使得算法分析简单,采用全牛顿步避免了线性搜索.

For solving monotone linear complementarity problems,a new kernel function is introduced, with which a new search direction and proximity measure are determined. Then a full-Netwon step interior-point algorithm is presented. Finally, the complexity bound of the algorithm is proved. The simple kernel function makes the algorithm analysis simple and no line-searches are needed with the full-Newton steps taken.