  


How do exponential size solutions arise in semidefinite programming?
Gabor Pataki (gaborunc.edu) Abstract: Semidefinite programs (SDPs) are some of the most popular and broadly applicable optimization problems to emerge in the last thirty years. A curious pathology of SDPs, illustrated by a classical example of Khachiyan, is that their solutions may need exponential space to even write down. Exponential size solutions are the main obstacle to solve a long standing open problem: can we decide feasibility of SDPs in polynomial time? The consensus seems to be that large size solutions in SDPs are rare. Here we prove that they are actually quite 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 of a dual problem. Further, we present some SDPs in which large solutions appear naturally, without any change of variables. We also partially answer the question: how do we represent such large solutions in polynomial space? Keywords: semidefinite programming; exponential size solutions; Khachiyan's example; singularity degree Category 1: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Category 2: Convex and Nonsmooth Optimization (Convex Optimization ) Category 3: Nonlinear Optimization (Constrained Nonlinear Optimization ) Citation: Download: [PDF] Entry Submitted: 02/23/2021 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  