EECS Joint Colloquium Distinguished Lecture Series  
Wednesday, September 22, 2004 Professor Stephen P. Boyd Information Systems Laboratory 

Advances in Convex Optimization: Interiorpoint Methods, Cone Programming, and Applications 

Abstract: 

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 worstcase complexity results of linear programming have been extended to nonlinear convex optimization, and interiorpoint methods for nonlinear convex optimization achieve efficiencies approaching that of modern linear programming solvers. Moreover, special purpose implementations for largescale 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, secondorder 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, nonconvex 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.


Biography:  
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 computeraided control system design, and convex programming applications in control, signal processing, and circuits. 