Primal-dual entropy-based interior-point algorithms for linear optimization
1 Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada.
2 Toronto, Ontario, Canada.
Received: 28 October 2014
Accepted: 22 January 2016
We propose a family of search directions based on primal-dual entropy in the context of interior-point methods for linear optimization. We show that by using entropy-based search directions in the predictor step of a predictor-corrector algorithm together with a homogeneous self-dual embedding, we can achieve the current best iteration complexity bound for linear optimization. Then, we focus on some wide neighborhood algorithms and show that in our family of entropy-based search directions, we can find the best search direction and step size combination by performing a plane search at each iteration. For this purpose, we propose a heuristic plane search algorithm as well as an exact one. Finally, we perform computational experiments to study the performance of entropy-based search directions in wide neighborhoods of the central path, with and without utilizing the plane search algorithms.
Mathematics Subject Classification: 90C05 / 90C51 / 41A46 / 94A17
Key words: Interior-point methods / primal-dual entropy / central path / homogeneous and self-dual embedding / search direction
Research of this author was supported in part by OGS scholarships from the government of Ontario, a Discovery Grant from NSERC, and by ONR Research Grant N00014-12-1-0049.
© EDP Sciences, ROADEF, SMAI 2017