单调线性互补问题基于核函数的满-Newton步不可行内点算法

A full-newton step infeasible interior-point algorithm for monotone linear complementarity problems based on a kernel function

针对单调线性互补问题设计了一种基于核函数的满-Newton步不可行内点算法,算法的主迭代由一个可行步和几个中心步构成。通过建立和应用一些新的分析工具,证明了算法的多项式复杂性为O(nlogmax{(x0)Ts0,‖r0‖/n}),这与当前单调线性互补问题的不可行内点算法最好的迭代界一致。

A full-newton step infeasible interior-point algorithm for monotone linear complementarity problems based on a kernel function was presented. The main iteration of the algorithm consists of a feasibility step and several centrality steps. By using some new analysis tools, the polynomial complexity bound for the algorithm was obtained, namely,O（nlog max｜（x0）TS0,｜｜r0｜｜｜/n）,which is consistent with the currently best iteration bound for infeasible interior-point methods of monotone linear complementarity.