Search
Budapesti Corvinus Egyetem ×
Akadálymentesített nézet
Vissza a főoldalra

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

2022-09-26 15:31:43

Online operációkutatási szemináriumot tart Pataki Gábor, az University of North Carolina professzora.

Kapcsolódó hírek

Kapcsolódó események

Corvinus Épület

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. 

Vágólapra másolva
X
GEN.:2022.11.29. - 05:06:56