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 (Semi-definite Programming )
Category 2: Convex and Nonsmooth Optimization (Convex Optimization )
Category 3: Nonlinear Optimization (Constrained Nonlinear Optimization )
Entry Submitted: 02/23/2021
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|