The lecture is organized by Corvinus Centre for Operations Research (CIAS-CCOR) in part of the “Online Hungarian Operations Research Seminars”.
“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 email@example.com.