EECS Joint Colloquium Distinguished Lecture Series

Wednesday, September 22, 2004
Hewlett Packard Auditorium, 306 Soda Hall
4:00-5:00 p.m.

Professor Stephen P. Boyd

Information Systems Laboratory
Department of Electrical Engineering
Stanford University


Advances in Convex Optimization: Interior-point Methods, Cone Programming, and Applications




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. 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. Moreover, special purpose implementations for large-scale applications can take advantage of many different types of problem structure. Several new classes of standard convex optimization problems have emerged, including semidefinite programming and linear matrix inequalities, which are well known in control, and also determinant maximization, second-order cone programming, and geometric programming, which are less well known. 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, 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, analysis and design of nonlinear and uncertain systems, and robust optimization.


Stephen Boyd is the Samsung Professor of Engineering and Director of the Information Systems Laboratory, in Stanford's Electrical Engineering Department. He received the A.B. degree in Mathematics from Harvard University in 1980, and the Ph.D. in Electrical Engineering and Computer Science from the University of California, Berkeley, in 1985, and then joined the faculty at Stanford. His interests include computer-aided control system design, and convex programming applications in control, signal processing, and circuits.