Primal-dual entropy-based interior-point algorithms for linear optimization

DOI10.1051/RO/2016020zbMATH Open1365.90166arXiv1410.8226OpenAlexW2963833760MaRDI QIDQ5269350FDOQ5269350

Shen Luo, Levent Tunçel, Mehdi Karimi

Publication date: 15 June 2017

Published in: RAIRO - Operations Research (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1410.8226

zbMATH Keywords

interior-point methodscentral pathsearch directionhomogeneous and self-dual embeddingprimal-dual entropy

Mathematics Subject Classification ID

Linear programming (90C05) Interior-point methods (90C51) Measures of information, entropy (94A17) Approximation by arbitrary nonlinear expressions; widths and entropy (41A46)

Cited In (4)

• Interior-point algorithm for symmetric cone horizontal linear complementarity problems based on a new class of algebraically equivalent transformations
• New predictor-corrector algorithm for symmetric cone horizontal linear complementarity problems
• Predictor-corrector interior-point algorithm for \(P_*(\kappa)\)-linear complementarity problems based on a new type of algebraic equivalent transformation technique
• Entropic approach to interior point solution of linear programs

This page was built for publication: Primal-dual entropy-based interior-point algorithms for linear optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5269350)