How Do Exponential Size Solutions Arise in Semidefinite Programming?

.A striking pathology of semidefinite programs (SDPs) is illustrated by a classical example of Khachiyan: feasible solutions in SDPs may need exponential space even to write down. Such exponential size solutions are the main obstacle to solving a long standing, fundamental open problem: can we decide feasibility of SDPs in polynomial time? The consensus seems that SDPs with large size solutions are rare. However, 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 coming from sum-of-squares proofs, 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?Keywordssemidefinite programmingexponential size solutionsKhachiyan's examplereformulationssingularity degreeMSC codes90C2249N1552A40