Ellipsoid algorithm, or why convex programming is "simple" * скачать в хорошем качестве

Ellipsoid algorithm, or why convex programming is "simple" *

Anatoli Iouditski (Université de Grenoble-Alpes) Ellipsoid algorithm, or why convex programming is "simple". IThe advent of the Ellipsoid algorithm by Nemirovski and Yudin in 1976 have several major academic and computational implications. First, it allowed to prove efficient solvability of generic Convex Programming problems satisfying mild computability and boundedness assumptions (it was is the “working horse” in the famous result (Khachiyan et al,’78) on polynomial time solvability of Linear Programming. On the other side, it may be used to solve to high accuracy convex problems of pretty general type. In this lecture we study the algorithm and discuss its application to the proof of the Khachiyan theorem. The lecture is intended for the audience with basic knowledge of analysis and geometry.