Accuracy certificates for computational problems with convex structure

Accuracy certificates for computational problems with convex structure

0.00 Avg rating0 Votes
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: , ,
Keywords: numerical analysis
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.