An O(root nL) iteration Mehrotra-type predictor-corrector algorithm for monotone linear complementarity problem

作者：Liu, Changhe^*; Shang, Youlin; Liu, Hongwei

来源：Optimization Letters, 2016, 10(3): 619-634.

DOI：10.1007/s11590-015-0889-0

• Linear complementarity problem
• Interior-point methods
• Wide neighborhood
• Mehrotra-type predictor-corrector algorithm
• Polynomial complexity

In this paper we propose a new class of Mehrotra-type predictor-corrector algorithm for the monotone linear complementarity problems (LCPs). At each iteration, the method computes a corrector direction in addition to the Ai-Zhang direction (SIAM J Optim 16: 400-417, 2005), in an attempt to improve performance. Starting with a feasible point (x(0), s(0)) in the wide neighborhood N(tau, beta), the algorithm enjoys the low iteration bound of O(root nL), where n is the dimension of the problem and L = log (x(0))(T) s(0)/epsilon with epsilon the required precision. We also prove that the new algorithm can be specified into an easy implementable variant for solving the monotone LCPs, in such a way that the iteration bound is still O(root nL). Some preliminary numerical results are provided as well.

• 出版日期2016-3
• 单位河南大学; 西安电子科技大学