How Do Exponential Size Solutions Arise in Semidefinite Programming?
证明了半定规划中指数级规模解其实很常见：线性变量变换可将任何严格可行半定规划转化为Khachiyan型问题，且解的大小取决于对偶问题的奇异度。
.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