基于一类新方向的宽邻域路径跟踪内点算法

基于一类带有参数theta的新方向, 提出了求解单调线性互补问题的宽邻 域路径跟踪内点算法, 且当theta=1时即为经典牛顿方向. 当取theta为与问题规模 n无关的常数时, 算法具有O(nL)迭代复杂性, 其中L是输入数据的长度, 这与经典宽邻 域算法的复杂性相同; 当取theta=\sqrt{n/\beta\tau}时, 算法具有O(\sqrt{n}L)迭代复杂性, 这里的\beta, \tau是邻域参数, 这与窄邻域算法的复杂性相同. 这是首次研究包括经典宽邻域路径跟踪算法的一类内点算法, 给出了统一的算法框架和收敛性分析方法.

Path-following interior point algorithms based on wide neighborhoods and a new class of directions

This paper presents a class of path-following interior point algorithms for the monotone linear complementarity problems based on wide neighborhoods and the new directions with a parameter \theta. When the parameter \theta=1, the new direction is exactly the classical Newton direction. The algorithms have O(nL) iteration complexity when the parameter \theta is independent of the dimension n, which coincides with the best known iteration complexity for the classical wide neighborhood algorithms. When \theta=\sqrt{n/\beta\tau}, the algorithm has O(\sqrt{n}L) iteration complexity, the best iteration complexity obtained so far by any interior point method for solving linear complementarity problems, where \beta and \tau are neighborhood parameters. To our knowledge this is the first time that a class of interior point algorithms including the classical wide neighborhood path-following algorithm is proposed and analyzed.