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

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 … Read more

Accuracy Certificates for Computational Problems with Convex Structure

The goal of the current paper is to introduce the notion of certificates which verify the accuracy of solutions of computational problems with convex structure; such problems include minimizing convex functions, variational inequalities corresponding to monotone operators, computing saddle points of convex-concave functions and solving convex Nash equilibrium problems. We demonstrate how the implementation of … Read more