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?
Article
View How do exponential size solutions arise in semidefinite programming?