EECS Joint Colloquium Distinguished Lecture Series

Monday, April 05, 2004
306 Soda Hall, Hewlett-Packard Auditorium
4:00 - 5:00 p.m.

Dr. Pablo Parrilo

Assistant Professor of Analysis and Control Systems at the Automatic Control Laboratory,
Swiss Federal Institute of Technology (ETH Zürich)


Sum of squares programs: what are they good for, and how to solve them




Sum of squares (SOS) programs are a particular class of convex optimization problems, that combine in a very appealing way notions from algebraic and numeric computation. They are based on the sum of squares decomposition for multivariate polynomials, and have found many applications in engineering and applied mathematics, mainly through semidefinite elaxations of polynomial optimization problems.

In this talk we will discuss the SOS formulation and its applications, as well as the techniques available for exploiting their special algebraic structure towards an efficient numerical solution. Additionally, we identify properties of systems of polynomial equations and inequalities that can be successfully exploited for numerical efficiency. Our results apply, among others, to sparse polynomials, the ideal structure present in systems with explicit equality constraints, and structural symmetries, as well as combinations thereof. The results will be motivated and illustrated through applications of sum of squares techniques from different areas, such as quantum information and systems and control theory.


Pablo A. Parrilo has been Assistant Professor of Analysis and Control Systems at the Automatic Control Laboratory of the Swiss Federal Institute of Technology (ETH Zürich) since October 2001. Prof. Parrilo was born in Buenos Aires, Argentina. He received the Electronics Engineering degree from the University of Buenos Aires in 1994, and obtained a PhD in Control and Dynamical Systems from the California Institute of Technology in June 2000. After receiving his degree, he stayed at Caltech as postdoctoral scholar and lecturer, until September 2001. He has held short-term visiting appointments at UC Santa Barbara, Lund Institute of Technology, and UC Berkeley. His current research interests include control and identification of uncertain complex systems, robustness analysis and synthesis, and the application of tools from convex optimization and computational algebra to practically relevant problems in engineering, economics, and physics.