Ellipsoid Method for Linear Programming made simple

2017/12/13 by Sanjeev Saxena, Saxena, Sanjeev
Mathematics · Computer Science · #Advanced Optimization Algorithms Research #Matrix Theory and Algorithms

paper · pdf · doi:10.48550/arxiv.1712.04637

Abstract

In this paper, ellipsoid method for linear programming is derived using only minimal knowledge of algebra and matrices. Unfortunately, most authors first describe the algorithm, then later prove its correctness, which requires a good knowledge of linear algebra.

Related

• The ellipsoid method redux
• An Oblivious Ellipsoid Algorithm for Solving a System of (In)Feasible Linear Inequalities
• Linear Programming, the Simplex Algorithm and Simple Polytopes
• Still Simpler Way of Introducing Interior-Point method for Linear Programming
• A strongly polynomial-time algorithm for the general linear programming problem