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 minimiz-ing 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 aug-mented with the computation of such certificates without essential increase of the computational effort. Further, we show that (computable) certificates exist whenever an algorithm is capable to produce solutions of guaranteed accuracy