Advanced Convex Optimization : Lecture 6 : Complexity of Subgradient Methods

In this talk spanning about 36 minutes we discuss an issue which lies at the heart of modern convex optimization algorithms. The question is how fast can we reach approximate optimality or epsilon-optimality to sound technically correct. This essentially means how many iterations are required to get to approximate optimality. For a particular class of algorithms helpful for polyhedral convex functions we show how to design step-lengths which will lead us to approximate optimality in polynomial time.