Mathematisches Institutskolloquium
-
Institut für Mathematik der HU
Rudower Chaussee 26,
12489 Berlin
Optimization in Theory and Practice
Stephen Wright (Computer Sciences Department, University of Wisconsin-Madison)
Abstract: Algorithms for continuous optimization problems have a rich history of design and innovation over the past several decades, in which mathematical analysis of their convergence and complexity properties plays a central role. Besides their theoretical properties, optimization algorithms are interesting also for their practical usefulness as computational tools for solving real-word problems. There are often gaps between the practical performance of an algorithm and what can be proved about it. These two facets of the field — the theoretical and the practical — interact in fascinating ways, each driving innovation in the other. This work focuses on the development of algorithms in two areas — linear programming and unconstrained minimization of smooth functions — outlining major algorithm classes in each area along with their theoretical properties and practical performance, and highlighting how advances in theory and practice have influenced each other in these areas. In discussing theory, we focus mainly on non-asymptotic complexity, which are upper bounds on the amount of computation required by a given algorithm to find an approximate solution of problems in a given class.