Accuracy Certificates for Computational Problems With Convex Structure
(Joint work with Arkadi Nemirovski and Shmuel Onn)

Uriel G. Rothblum
The Alexander Goldberg Chair in Management Science
Faculty of Industrial Engineering and Management
The Technion
Haifa 32000, ISRAEL

Wednesday, September 26, 2007
4:30 - 5:30 PM
Terman Engineering Center, Room 453


Abstract:

In this paper we introduce the notion of certificates for approximate solutions of various computational problems with 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 polynomial time in a way that will produce solutions to the above problems along with accuracy certificates.


Bio:

Uriel G. Rothblum took his Ph.D. in Operations Research from Stanford in 1974. He has been a Professor in the Faculty of Industrial Engineering and Management at the Technion since 1984. He has served as Dean of the Faculty (1992-1995) and as Vice President for Academic Affairs of the Technion (1998-2002). His research interests include optimization, game theory, linear models and applied probability, and he has published over 140 papers on these subjects. He is currently the President of the Israeli OR Society and is an Associate Editor of MOR, LAA and the J. Combinatorial Optimization. He was elected an INFORMS Fellow in 2002.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html