Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Convex relaxations for semialgebraic problems and their applications in systems and control.

Semialgebraic problems, i.e., those that can be expressed with a finite number of polynomial inequalities and inequalities, are ubiquitous in many different engineering disciplines. A few concrete examples are given by the analysis and synthesis of control systems, graph theoretic problems, and issues of network survivability and reliability. In general, this class of problems have bad complexity properties, and exact algorithms to solve them are usually computationally infeasible. As a consequence, considerable research efforts have been directed towards the efficient computation of approximate solutions (or bounds) for this class of problems. In this talk, we present a new convex optimization framework for semialgebraic problems. The key element is the interaction of concepts from real algebra and convex optimization, in particular a semidefinite programming formulation for the sums of squares decomposition for multivariable polynomials. These results are used to construct a hierarchy of progressively stronger convex tests, to prove that a given semialgebraic set is empty. The search for such certificates can be efficiently carried out, in polynomial time. The developed techniques unify and generalize many well-known existing results. We describe the application of the results to problems in systems and control theory, and continuous and combinatorial optimization. These include Lyapunov stability of nonlinear systems described by polynomial vector fields, stronger sufficient conditions for matrix copositivity, and enhanced semidefinite relaxations for quadratic programming. The ideas and algorithms will be illustrated with examples from a broad range of application domains.
Type of Seminar:
Minisymposium on Analysis and Control of Dynamical Systems
Dr. Pablo A. Parrilo
Control and Dynamical Systems California Institute of Technology Mail Stop 107-81 Pasadena, CA 91125-8100
Dec 19, 2000   14:15

ETH Zentrum, Building VAW, Room B1, Gloriastrasse 37-39, 8006 Zurich
Contact Person:

Prof. M. Morari
No downloadable files available.
Biographical Sketch:
Pablo A. Parrilo was born in Buenos Aires, Argentina. He received the Electronics Engineering degree from the University of Buenos Aires in 1994, and the PhD in Control and Dynamical Systems from the California Institute of Technology in June 2000. He is currently a Postdoctoral Scholar and Lecturer at Caltech, where he is teaching an introductory graduate course on Robust Control. His research interests include robust control and identification, robustness analysis, networked systems, convex optimization and computational algebra.