An $$\ell _{2}$$ ℓ 2 -neighborhood infeasible interior-point algorithm for linear complementarity problems

M. Pirhaji, M. Zangiabadi and H. Mansouri ()
Additional contact information
M. Pirhaji: Shahrekord University
M. Zangiabadi: Shahrekord University
H. Mansouri: Shahrekord University

4OR, 2017, vol. 15, issue 2, No 1, 131 pages

Abstract: Abstract In this paper, we propose an infeasible interior-point algorithm for linear complementarity problems. In every iteration, the algorithm constructs an ellipse and searches an $$\varepsilon $$ ε -approximate solution of the problem along the ellipsoidal approximation of the central path. The theoretical iteration-complexity of the algorithm is derived and the algorithm is proved to be polynomial with the complexity bound $$O\left(n\log \varepsilon ^{-1}\right)$$ O n log ε - 1 which coincides with the best known iteration bound for infeasible interior-point methods.

Keywords: Linear complementarity problem; Ellipsoidal approximation; Interior-point methods; Polynomial complexity; 90C33; 90C51 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10288-016-0325-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:aqjoor:v:15:y:2017:i:2:d:10.1007_s10288-016-0325-z

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-016-0325-z

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().