How do exponential size solutions arise in Semidefinite Programming? – Online seminar

The lecture is organized by Corvinus Centre for Operations Research (CIAS-CCOR) in part of the “Online Hungarian Operations Research Seminars”. 

Abstract: 

“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 ?  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?  

Joint work with Alex Touzov.” 

For information on how to join online, please contact marianna.eisenberg-nagy@uni-corvinus.hu.