Please use this identifier to cite or link to this item: https://doi.org/10.1023/B:COAP.0000013059.84424.af
Title: Convergence Analysis of an Infeasible Interior Point Algorithm Based on a Regularized Central Path for Linear Complementarity Problems
Authors: Zhou, G.
Toh, K.-C. 
Zhao, G. 
Keywords: Global convergence
Infeasible interior point method
Infeasible regularized central path
Linear complementarity problem
Polynomiality
Issue Date: Mar-2004
Citation: Zhou, G., Toh, K.-C., Zhao, G. (2004-03). Convergence Analysis of an Infeasible Interior Point Algorithm Based on a Regularized Central Path for Linear Complementarity Problems. Computational Optimization and Applications 27 (3) : 269-283. ScholarBank@NUS Repository. https://doi.org/10.1023/B:COAP.0000013059.84424.af
Abstract: Most existing interior-point methods for a linear complementarity problem (LCP) require the existence of a strictly feasible point to guarantee that the iterates are bounded. Based on a regularized central path, we present an infeasible interior-point algorithm for LCPs without requiring the strict feasibility condition. The iterates generated by the algorithm are bounded when the problem is a P* LCP and has a solution. Moreover, when the problem is a monotone LCP and has a solution, we prove that the convergence rate is globally linear and it achieves ε-feasibility and ε-complementarity in at most O(n 2 ln(1/ε)) iterations with a properly chosen starting point.
Source Title: Computational Optimization and Applications
URI: http://scholarbank.nus.edu.sg/handle/10635/103065
ISSN: 09266003
DOI: 10.1023/B:COAP.0000013059.84424.af
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

1
checked on Aug 17, 2018

WEB OF SCIENCETM
Citations

1
checked on Aug 8, 2018

Page view(s)

36
checked on Aug 17, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.