Volume 51, Number 2, April-June 2017
|Page(s)||299 - 328|
|Published online||08 February 2017|
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
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.