Accuracy certificates for computational problems with convex structure

Arkadi Nemirovski, Shmuel Onn and Uriel G. Rothblum

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 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 essential increase of the

computational effort. Further, we show that (computable)

certificates exist whenever an algorithm is {capable} to produce

solutions of guaranteed accuracy.