RUTCOR Colloquia -
Uri Rothblum,
Speaker
1:30 PM, Room 139, RUTCOR Building
ACCURACY CERTIFICATES FOR
COMPUTATIONAL PROBLEMS WITH CONVEX STRUCTURES
Arkadi Nemirovski,
Shmuel Onn and Uriel G. Rothblum
In this paper we introduce the
notion of certificates for approximate
solutions of various computational problems
in convex structure,
including the minimization of a convex
function over a solid, the solution of
variational inequalities, the determination of
a Nash equilibrium and
the identification of saddle points of
convex-concave functions. We show
that these certificates can be used to
efficiently convince an external
person that a solution at hand satisfies
desired properties to prescribed
accuracy.
We also show how the Ellipsoid method can be implemented in a
way that will produce solutions to the
above problem along with accuracy certificates.