Semidefinite programs (SDPs) are some of the most popular and widespread optimization problems to emerge in  the last thirty years. A curious pathology of SDPs is  illustrated by a famous example of Khachiyan: feasible solutions of SDPs may need exponential space to even write down. Understanding such large solutions is a key to  solve one of the most important open problems in optimization theory: can we decide feasibility of SDPs in polynomial time?  

We first address the question: how common are such large solutions in SDPs ?  Although the common consent is that they are rare, we prove that they are surprisingly common: a linear change of variables transforms every strictly feasible SDP into a Khachiyan type SDP in which the leading variables are large.  As to “how large”, that depends on the singularity degree, a ubiquitous parameter of SDPs.  Finally, we give a partial “yes” answer to the question: can we represent exponential size solutions in a compact fashion, in polynomial space? 

Share this Event