Aleksandr Touzov

How do exponential size solutions arise in semidefinite programming?

  • Gabor Pataki
  • Aleksandr Touzov
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Semi-definite Programming

    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 … Read more

    An echelon form of weakly infeasible semidefinite programs and bad projections of the psd cone

  • Gabor Pataki
  • Aleksandr Touzov
    • Categories Convex Optimization, Semi-definite Programming

    A weakly infeasible semidefinite program (SDP) has no feasible solution, but it has nearly feasible solutions that approximate the constraint set to arbitrary precision. These SDPs are ill-posed and numerically often unsolvable. They are also closely related to “bad” linear projections that map the cone of positive semidefinite matrices to a nonclosed set. We describe … Read more