A polynomial interior-point algorithm with improved iteration bounds for linear optimization
- Resource Type
- Original Paper
- Authors
- Liu, Liying; Hua, Tao
- Source
- Japan Journal of Industrial and Applied Mathematics. 41(2):739-756
- Subject
- Linear programming
Interior-point methods
Kernel function
Polynomial complexity
90C05
90C33
90C51
- Language
- English
- ISSN
- 0916-7005
1868-937X
In this paper, we present a polynomial primal-dual interior-point algorithm for linear optimization based on a modified logarithmic barrier kernel function. Iteration bounds for the large-update interior-point method and the small-update interior-point method are derived. It is shown that the large-update interior-point method has the same polynomial complexity as the small-update interior-point method, which is the best known iteration bounds. Our result closes a long-existing gap in the theoretical complexity bounds for large-update interior-point method and small-update interior-point method.