Budapesti Corvinus Egyetem ×
Handicap version
Back to main page

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

2022-09-26 15:33:12

Gábor Pataki, professor at University of North Carolina, will give an online seminar on operations research.

Kapcsolódó hírek

Kapcsolódó események

Corvinus Épület

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 

Copied to clipboard
GEN.:2022.11.29. - 05:32:16