Optimization Online


How do exponential size solutions arise in semidefinite programming?

Gabor Pataki (gabor***at***unc.edu)
Aleksandr Touzov (touzov***at***live.unc.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 )


Download: [PDF]

Entry Submitted: 02/23/2021
Entry Accepted: 02/23/2021
Entry Last Modified: 06/30/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society