ICCOPT 2013 Talk, Room 1.3, Wednesday, July 31, 14:30-16:00

 Speaker: Clovis Gonzaga, Federal University of Santa Catarina, Brazil
 Title: On the complexity of steepest descent algorithms for minimizing quadratic functions


 Abstract:
Scientific Program

We discuss the performance of the steepest descent algorithm for minimizing a quadratic function with Hessian eigenvalues between a>0 and A. Steepest descent methods differ exclusively on the choice of step length at each iteration. We examine patterns in the distribution of these step lengths, showing that a large number of short steps are needed, and how these relate to the much smaller number of large steps. We develop a scheme for choosing the step lengths and try to prove the following result: the number of iterations needed to reduce the distance to an optimal solution by a fixed amount depends on the square root of A/a, in contrast with the linear dependence predicted by Kantorovich's analysis.


 Talk in: Session Wed.B.13 Complexity of convex/nonsmooth/nonlinear optimization methods
 Cluster: Convex and nonsmooth optimization


 Go to: Wed.B
 Go to: unframed Scientific Program

 Go to: ICCOPT 2013 Main Webpage