SDP approximations for copositive and completely positive matrices (or, Pólya meets De Finetti)

Pablo A. Parrilo
Electrical Engineering and Computer Science, MIT

Abstract: The recognition and verification of matrix copositivity is a well-known computationally hard problem, with many applications in continuous and combinatorial optimization. In this talk we discuss a hierarchy of approximations for a real matrix to be copositive, based on semidefinite programming (SDP). These conditions are obtained through the use of a sum of squares decomposition for multivariable forms. The completeness of the hierarchies is shown to be equivalent to classical results for homogeneous forms and exchangeable random variables due to Pólya and De Finetti, respectively. We will discuss their relationship, the application of the results to some well-known families of copositive forms, as well as a "quantum" version of the problem.

Bio Sketch: Pablo A. Parrilo is Associate Professor in the Department of Electrical Engineering and Computer Science at MIT, and a member of the Laboratory for Information and Decision Systems (LIDS). His current research interests include control and identification of uncertain complex systems, robustness analysis and synthesis, and the development and application of computational tools based on convex optimization and algorithmic algebra to practically relevant problems in engineering, economics, and physics.

From October 2001 through September 2004, Pablo was Assistant Professor of Analysis and Control Systems at the Automatic Control Laboratory of the Swiss Federal Institute of Technology (ETH Zurich). He received an Electronics Engineering degree from the University of Buenos Aires in 1994, a PhD in Control and Dynamical Systems from the California Institute of Technology in 2000, and held short-term visiting appointments at UC Santa Barbara, Lund Institute of Technology, and UC Berkeley.