Article ID: | iaor20102609 |
Volume: | 35 |
Issue: | 1 |
Start Page Number: | 52 |
End Page Number: | 78 |
Publication Date: | Feb 2010 |
Journal: | Mathematics of Operations Research |
Authors: | Nemirovski Arkadi, Onn Shmuel, Rothblum Uriel G |
Keywords: | numerical analysis |
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.