An Oblivious Ellipsoid Algorithm for Solving a System of (In)Feasible Linear Inequalities

DOI10.1287/MOOR.2023.1353arXiv1910.03114OpenAlexW2979398313MaRDI QIDQ6189902FDOQ6189902

Jourdain B. Lamperski, Michael J. Todd, Robert M. Freund

Publication date: 5 March 2024

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Abstract: The ellipsoid algorithm is a fundamental algorithm for computing a solution to the system of $m$ linear inequalities in $n$ variables $(P):A^{op}xleu$ when its set of solutions has positive volume. However, when $(P)$ is infeasible, the ellipsoid algorithm has no mechanism for proving that $(P)$ is infeasible. This is in contrast to the other two fundamental algorithms for tackling $(P)$, namely the simplex method and interior-point methods, each of which can be easily implemented in a way that either produces a solution of $(P)$ or proves that $(P)$ is infeasible by producing a solution to the alternative system $mathrm(itAlt):Alambda=0$, $u^{op}lambda<0$, $lambdage0$. This paper develops an Oblivious Ellipsoid Algorithm (OEA) that either produces a solution of $(P)$ or produces a solution of $mathrm(itAlt)$. Depending on the dimensions and on other natural condition measures, the computational complexity of the basic OEA may be worse than, the same as, or better than that of the standard ellipsoid algorithm. We also present two modified versions of OEA, whose computational complexity is superior to that of OEA when $nllm$. This is achieved in the first modified version by proving infeasibility without actually producing a solution of $mathrm(itAlt)$, and in the second modified version by using more memory.

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

zbMATH Keywords

computational complexitylinear inequalitiesellipsoid algorithmcondition measurescertificates

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60)

This page was built for publication: An Oblivious Ellipsoid Algorithm for Solving a System of (In)Feasible Linear Inequalities

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