Optimization Online


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

Jourdain Lamperski(jourdain***at***mit.edu)
Robert Freund(rfreund***at***mit.edu)
Michael Todd(mjt7***at***cornell.edu)

Abstract: The ellipsoid algorithm is a fundamental algorithm for computing a solution to the system of m linear inequalities in n variables (P) 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 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 (Alt). This paper develops an Oblivious Ellipsoid Algorithm (OEA) that either produces a solution of (P) or produces a solution of (Alt), and whose operations complexity dependence on the dimensions in the regime m>>n is of the same order as a standard ellipsoid method (O(m^4)) when (P) is infeasible (but worse complexity when (P) is feasible). However, we show that a simplified version of OEA, which still proves infeasibility, but does not produce a solution of (Alt), achieves O(m^3n) complexity, which is superior to the O(m^4) complexity of a standard ellipsoid algorithm applied to solve (Alt).

Keywords: Ellipsoid Algorithm, Certificates, Condition Measures, Computational Complexity, Linear Inequalities

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 3: Convex and Nonsmooth Optimization (Nonsmooth Optimization )


Download: [PDF]

Entry Submitted: 10/08/2019
Entry Accepted: 10/08/2019
Entry Last Modified: 10/08/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society