Accuracy Certificates for Computational Problems with Convex Structure

The goal of this 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 with monotone operators, computing saddle points of convex-concave functions, and solving convex Nash equilibrium problems. We demonstrate how the implementation of the ellipsoid method and other cutting plane algorithms can be augmented with the computation of such certificates without significant increase of the computational effort. Further, we show that (computable) certificates exist for any algorithm that is capable of producing solutions of guaranteed accuracy.