  


An Oblivious Ellipsoid Algorithm for Solving a System of (In)Feasible Linear Inequalities
Jourdain Lamperski(jourdainmit.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 interiorpoint 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 ) Citation: Download: [PDF] Entry Submitted: 10/08/2019 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  