Paper Info
Title
Large-step interior-point algorithm for linear optimization based on a new wide neighbourhood.
Abstract
The interior-point algorithms can be classified in multiple ways. One of these takes into consideration the length of the step. In this way, we can speak about large-step and short-step methods, that work in different neighbourhoods of the central path. The large-step algorithms work in a wide neighbourhood, while the short-step ones determine the new iterates that are in a smaller neighbourhood. In spite of the fact that the large-step algorithms are more efficient in practice, the theoretical complexity of the short-step ones is generally better. Ai and Zhang introduced a large-step interior-point method for linear complementarity problems using a wide neighbourhood of the central path, which has the same complexity as the best short-step methods. We present a new wide neighbourhood of the central path. We prove that the obtained large-step primal–dual interior-point method for linear programming has the same complexity as the best short-step algorithms.
Year
DOI
Venue
2018
10.1007/s10100-018-0524-0
CEJOR
Keywords
Field
DocType
Linear programming, Large-step algorithm, Wide neighbourhood, Polynomial complexity
Complementarity (molecular biology),Economics,Mathematical optimization,Algorithm,Neighbourhood (mathematics),Linear programming,Polynomial complexity,Interior point method,Iterated function,Zhàng,Spite
Journal
Volume
Issue
ISSN
26
3
1435-246X
Citations 
PageRank 
References 
2
0.39
13
Authors
2
Name
Order
Citations
PageRank
Zs. Darvay164.20
Petra-Renáta Takács251.13