Optimized choice of parameters in interior-point methods for linear programming

Luiz-Rafael Santos (), Fernando Villas-Bôas (), Aurelio R. L. Oliveira () and Clovis Perin ()
Additional contact information
Luiz-Rafael Santos: Federal University of Santa Catarina
Fernando Villas-Bôas: IMECC, University of Campinas
Aurelio R. L. Oliveira: IMECC, University of Campinas
Clovis Perin: IMECC, University of Campinas

Computational Optimization and Applications, 2019, vol. 73, issue 2, No 7, 535-574

Abstract: Abstract In this work, we propose a predictor–corrector interior point method for linear programming in a primal–dual context, where the next iterate is chosen by the minimization of a polynomial merit function of three variables: the first is the steplength, the second defines the central path and the third models the weight of a corrector direction. The merit function minimization is performed by restricting it to constraints defined by a neighborhood of the central path that allows wide steps. In this framework, we combine different directions, such as the predictor, the corrector and the centering directions, with the aim of producing a better one. The proposed method generalizes most of predictor–corrector interior point methods, depending on the choice of the variables described above. Convergence analysis of the method is carried out, considering an initial point that has a good practical performance, which results in Q-linear convergence of the iterates with polynomial complexity. Numerical experiments using the Netlib test set are made, which show that this approach is competitive when compared to well established solvers, such as PCx.

Keywords: Linear programming; Infeasible interior point methods; Optimized choice of parameters; 49M15; 65K05; 90C05; 90C51 (search for similar items in EconPapers)
Date: 2019
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/s10589-019-00079-9 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:coopap:v:73:y:2019:i:2:d:10.1007_s10589-019-00079-9

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-019-00079-9

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

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