A New Ai–Zhang Type Interior Point Algorithm for Sufficient Linear Complementarity Problems
提出一种结合Ai–Zhang长步内点法与Darvay代数等价变换技术的新算法，在宽邻域中工作并保持最优迭代复杂度，MATLAB实验验证了其在充分与非充分问题上的效率。
Abstract In this paper, we propose a new long-step interior point method for solving sufficient linear complementarity problems. The new algorithm combines two important approaches from the literature: the main ideas of the long-step interior point algorithm introduced by Ai and Zhang and the algebraic equivalent transformation technique proposed by Darvay. Similar to the method of Ai and Zhang, our algorithm also works in a wide neighborhood of the central path and has the best known iteration complexity of short-step variants. However, due to the properties of the applied transforming function in Darvay’s technique, the wide neighborhood definition in the analysis depends on the value of the handicap. We implemented not only the theoretical algorithm but a greedy variant of the new method (working in a neighborhood independent of the handicap) in MATLAB and tested its efficiency on both sufficient and non-sufficient problem instances. In addition to presenting our numerical results, we also make some interesting observations regarding the analysis of Ai–Zhang type methods.