Combinatorics Seminar 2015

Speaker: Vladimir Yuryevich Protasov (Протасов Владимир Юрьевич), Moscow State University

Date: Wed, Nov 25, 2015

Time: 12:30 - 13:30

Venue: Middle Meeting Room

Title: Fifty years of the “Russian method’’


Assume we are given a convex function of many variables on some convex domain. We do not have a formula for that function and everything we can do is to compute its values at arbitrary points. Is it possible to compute the minimum of that function reasonably fast with a good precision? This is a typical statement of the problem of convex minimization in the "oracle’’ or "black box’’ concept. Half a century ago, in 1965, A. Yu. Levin and D. Newman independently suggested an idea of the cutting plane algorithm. In 1977 N.Z. Shor, A.S. Nemirovskii and D.B. Yudin made this algorithm applicable in practice by introducing the ellipsoid method, which became famous in 1979, when L.G. Khachiyan invoked it to prove polynomial solvability of linear programming problems. We discuss the evolution of the cutting plane idea for the last years and formulate several problems.

Slides: View slides