Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Convex Optimization and Applications


Speaker: Steve Boyd, Stanford University
Location: 2112 MSB
Start time: Fri, Mar 10 2006, 2:10PM

In this talk I will give an overview of some major developments in convex optimization that have emerged over the last ten years or so, and briefly describe several typical applications. The basic idea is that convex problems are fundamentally tractable, in theory and in practice. The polynomial worst-case complexity results of linear programming have been extended to nonlinear convex optimization, and interior-point methods for nonlinear convex optimization achieve efficiencies approaching that of modern linear programming solvers. Several new classes of standard convex optimization problems have emerged, including semidefinite programming, determinant maximization, second-order cone programming, and geometric programming. Like linear and quadratic programming, we have a fairly complete duality theory, and very effective numerical methods for these problem classes. There has been a steadily expanding list of new applications of convex optimization, in areas such as circuit design, signal processing, statistics, communications, control, and other fields. Convex optimization is also emerging as an important tool for hard, non-convex problems. Convex relaxations of hard problems provide a general approach for handling hard optimization problems, with applications in combinatorial optimization and robust optimization. Joint work with Lieven Vandenberghe