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

Expand
  • 1. School of Mathematics and Statistics, Henan University of Science and Technology, Luoyang 471023, Henan, China

Received date: 2015-02-14

  Online published: 2016-03-15

Abstract

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.

Cite this article

LIU Changhe, SHANG Youlin, LI Jinrui . Path-following interior point algorithms based on wide neighborhoods and a new class of directions[J]. Operations Research Transactions, 2016 , 20(1) : 43 -53 . DOI: 10.15960/j.cnki.issn.1007-6093.2016.01.004

References

[1] 韩继业, 修乃华, 戚厚铎. 非线性互补理论与算法 [M]. 上海: 上海科学技术出版社, 2006.
[2] Nocedal J, Wright S J. Numerical Optimization [M]. New York: Springer, 1999.
[3] Megiddo N. Pathways to the optimal set in linear programming [C]//Progress in Mathematical Programming: Interior Point and Related Methods. New York: Springer, 1989, 131-158.
[4] Kojima M, Mizuno S, Yoshise A. A primal-dual interior point algorithm for linear programming [C]//Progress in Mathematical Programming: Interior Point and Related Methods. New York: Springer, 1989, 29-47.
[5] Monteiro R D C, Adler I. Interior path following primal-dual algorithms, Part I: Linear programming [J]. Math Program, 1989, 44: 27-41.
[6] Kojima M, Mizuno S, Yoshise A. A polynomial-time algorithm for a class of linear complementarity problems [J]. Math Program, 1989, 44: 1-26.
[7] Mizuno S, Todd M J, Ye Y. On adaptive step primal-dual interior-point algorithms for linear programming [J]. Math Oper Res, 1993, 18: 964-981.
[8] Hung P, Ye Y. An asymptotical O(nL)-iteration path-following linear programming algorithm that use wide neighborhoods [J]. SIAM J Optim, 1996, 6: 570-586.
[9] Ai W, Zhang S. An O(nL) iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone LCP [J]. SIAM J Optim, 2005, 16: 400-417.
[10] Li Y, Terlaky T. A new class of large neighborhood path-following interior point algorithms for semidefinite optimization with O(nlogTrX^0S^0)arepsilon) iteration complexity [J]. SIAM J Optim, 2010, 20: 2853-2875.
[11] Wright S J. Primal-Dual Interior-Point Methods [M]. Philadelphia: SIAM, 1997.
[12] 刘长河, 刘红卫, 尚有林. 对称锥规划的邻域跟踪算法 [J]. 中国科学: 数学, 2013, 43: 691-702.
Outlines

/