How Do Exponential Size Solutions Arise in Semidefinite Programming?
From MaRDI portal
Publication:6195320
DOI10.1137/21m1434945arXiv2103.00041OpenAlexW3134417020MaRDI QIDQ6195320
Publication date: 13 March 2024
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2103.00041
semidefinite programmingreformulationssingularity degreeexponential size solutionsKhachiyan's example
Semidefinite programming (90C22) Inequalities and extremum problems involving convexity in convex geometry (52A40) Duality theory (optimization) (49N15)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Facial reduction algorithms for conic optimization problems
- The generalized trust region subproblem
- A new polynomial-time algorithm for linear programming
- Positive definite Hankel matrix completions and Hamburger moment completions
- A polynomial-time algorithm, based on Newton's method, for linear programming
- Regularizing the abstract convex program
- Quadratic programming with one negative eigenvalue is NP-hard
- On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
- On the complexity of semidefinite programs
- Semidefinite programming relaxations for semialgebraic problems
- NP-hardness of deciding convexity of quartic polynomials and related problems
- On the complexity of testing attainment of the optimal value in nonlinear optimization
- Amenable cones: error bounds without constraint qualifications
- Feasibility testing for systems of real quadratic equations
- Quadratic programming is in NP
- Global Optimization with Polynomials and the Problem of Moments
- A Mathematical View of Interior-Point Methods in Convex Optimization
- A Note on Polynomial Solvability of the CDT Problem
- Solving Generalized CDT Problems via Two-Parameter Eigenvalues
- On the Turing Model Complexity of Interior Point Methods for Semidefinite Programming
- Class of global minimum bounds of polynomial functions
- Error Bounds for Linear Matrix Inequalities
- SOS Is Not Obviously Automatizable, Even Approximately
- Indefinite Trust Region Subproblems and Nonsymmetric Eigenvalue Perturbations
- Characterizing Bad Semidefinite Programs: Normal Forms and Short Proofs
- Exact Duality in Semidefinite Programming Based on Elementary Reformulations
- A STRUCTURAL GEOMETRICAL ANALYSIS OF WEAKLY INFEASIBLE SDPS
- Complexity, exactness, and rationality in polynomial optimization
