Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Optimization Seminar

Gabor Pataki

University of North Carolina, Chapel Hill

Bad semidefinite programs: they all look the same

Abstract:

Semidefinite Programming (SDP) is the problem of optimizing a linear objective function of a symmetric matrix variable, with the requirement that the variable also be positive semidefinite. Duality theory is a central concept in SDP, just like it is in linear programming. However, in SDP pathological phenomena occur, such as nonattainment of the optimal values, and positive gaps. This research was motivated by the curious similarity of pathological SDPs that appear in the literature. We give exact characterizations of when a semidefinite system is badly behaved from the standpoint of duality, and show that "all bad semidefinite programs look the same", as they are characterized by the presence of certain excluded matrices. We find certain combinatorial characterizations: we prove that all badly behaved semidefinite systems can be brought to a certain standard form, on which it is trivial to recognize their bad behavior, using only elementary linear algebra, without referring to any theorem. We prove analogous results for well-behaved systems, which are not badly behaved. As a byproduct, we present an algorithm to generate all well behaved systems; in particular, we present a method to generate all linear maps under which the image of the cone of psd matrices is closed.

Host: Jiawang Nie

May 16, 2014

2:00 PM

AP&M 5829

****************************