Optimization Online


Accuracy Certificates for Computational Problems with Convex Structure

Arkadi Nemirovski (nemirovs***at***isye.gatech.edu)
Shmuel Onn (onn***at***ie.technion.ac.il)
Uriel Rothblum (rothblum***at***ie.technion.ac.il)

Abstract: 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 corresponding to 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 guaranteed to produce solutions of guaranteed accuracy.

Keywords: convexity, certificates, computation in

Category 1: Convex and Nonsmooth Optimization

Citation: Faculty of Industrial Engineering and Management, Technion - Israel Institute of Technology, April 2007

Download: [PDF]

Entry Submitted: 04/06/2007
Entry Accepted: 04/06/2007
Entry Last Modified: 11/29/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society