MASSACHUSETTS INSTITUTE OF TECHNOLOGY
OPERATIONS RESEARCH CENTER
FALL 2004 SEMINAR SERIES

DATE

Thursday, November 4, 2004

LOCATION: Room E40-298           TIME: 4:15pm

Reception immediately following in the
Philip M. Morse Reading Room, E40-106

SPEAKER

Professor Pablo A. Parrilo
Associate Professor of EECS
Massachusetts Institute of Technology

TITLE

SDP Approximations for Copositive and Completely Positive Matrices
(or, Pólya meets De Finetti)

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.