Mehrotra-type predictor-corrector algorithms for sufficient linear complementarity problem

被引：10

作者：

Liu, Hongwei ^{[1
]}

Liu, Xinze ^{[1
,2
]}

Liu, Changhe ^{[1
,3
]}

机构：

[1] Xidian Univ, Dept Math, Xian, Peoples R China

[2] Lincang Teachers Coll, Dept Math & Sci, Lincang, Peoples R China

[3] Henan Univ Sci & Technol, Dept Appl Math, Luoyang, Peoples R China

来源：

APPLIED NUMERICAL MATHEMATICS | 2012年 / 62卷 / 12期

基金：

中国国家自然科学基金;

关键词：

Linear complementarity problem; Interior-point method; Mehrotra-type algorithm; Predictor-corrector algorithm; Polynomial complexity; INTERIOR-POINT ALGORITHMS; L)-ITERATION ALGORITHM; CONVERGENCE; POLYNOMIALITY;

D O I：

10.1016/j.apnum.2012.05.009

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Two Mehrotra-type predictor-corrector algorithms are proposed for solving sufficient linear complementarity problems. Both algorithms are independent on the handicap chi of the problems. The first version of the Mehrotra-type algorithm is a generalization of the safeguard based Mehrotra-type algorithm for linear programming, that was proposed by Salahi et al. [M. Salahi, J. Peng, T. Terlaky, On Mehrotra-type predictor-corrector algorithms, SIAM J. Optim. 18 (2007) 1377-1397]. We also present a new variant of Mehrotra-type predictor-corrector algorithm using a new adaptive updating strategy of the centering parameter. We show that both algorithms enjoy O(n(1 + chi)log((x(0))(T)s(0)/epsilon)) iteration complexity. Some numerical results are reported as well. (C) 2012 IMACS. Published by Elsevier B.V. All rights reserved.

引用

页码：1685 / 1700

页数：16

共 27 条

[1] Convergence of interior point algorithms for the monotone linear complementarity problem [J].