How do exponential size solutions arise in Semidefinite Programming? – Online szeminárium

Az előadás az Online Magyar Operációkutatási Szemináriumsorozat következő állomása lesz, melyet a Corvinus Institute for Advanced Studies alatt működő Corvinus Centre for Operations Research (CIAS-CCOR) szervez 2022. október 5-én. 

Az előadás absztraktja: 

“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.” 

Az online csatlakozás lehetőségéről a marianna.eisenberg-nagy@uni-corvinus.hu email címen lehet érdeklődni.