Abstract:

In contrast to conventional continuous optimization algorithms whose iterates are computed and analyzed deterministically, randomized methods rely on stochastic processes and random number/vector generation as part of the algorithm. Whereas randomization in algorithms has been a part of research in discrete optimization for the last 20 years, randomization has played at most a minor role in the analysis of algorithms in continuous convex optimization, at least until recently. In this talk we will discuss two recently developed randomization-based algorithms for convex optimization with very good complexity bounds: a method by Belloni/Freund that uses random walks to transform a poorly behaved conic system problem to a well-behaved problem, and a method by Belloni that provides certificates of boundedness or unboundedness for a convex set given only by a membership oracle.