Fetching the paper…
Reading the bibliography…
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.
A polynomial algorithm in linear programming
Leonid Genrikhovich Khachiyan · 1979
Earlier work this paper cites.
Regularizing the abstract convex program
Jonathan M. Borwein and Henry Wolkowicz · 1981
Earlier work this paper cites.
A new polynomial-time algorithm for linear programming
N Karmarkar · 1984
Earlier work this paper cites.
Class of global minimum bounds of polynomial functions
Naum Z Shor · 1987
Earlier work this paper cites.
A polynomial-time algorithm, based on newton’s method, for linear programming
James Renegar · 1988
Earlier work this paper cites.
A primal-dual interior point algorithm for linear programming
Masakazu Kojima, Shinji Mizuno, and Akiko Yoshise · 1989
Earlier work this paper cites.
Quadratic programming is in NP
Stephen A Vavasis · 1990
Earlier work this paper cites.
Proving polynomial-time for sphere-constrained quadratic programming
Stephen A Vavasis and Richard Zippel · 1990
Earlier work this paper cites.
Quadratic programming with one negative eigenvalue is NP-hard
Panos M Pardalos and Stephen A Vavasis · 1991
Earlier work this paper cites.
On the computational complexity and geometry of the first-order theory of the reals. part i: Introduction. preliminaries. the geometry of semi-algebraic sets. the decision problem for the existential theory of the reals
James Renegar · 1992
Earlier work this paper cites.
Feasibility testing for systems of real quadratic equations
Alexander I Barvinok · 1993
Earlier work this paper cites.
Interior-point polynomial algorithms in convex programming
Yurii Nesterov and Arkadii Nemirovskii · 1994
Earlier work this paper cites.
Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations
Ronald J Stern and Henry Wolkowicz · 1995
Earlier work this paper cites.
Duality results for conic convex programming
Zhi-Quan Luo, Jos Sturm, and Shuzhong Zhang · 1997
Earlier work this paper cites.
On the complexity of semidefinite programs
Lorant Porkolab and Leonid Khachiyan · 1997
Cited alongside, same era.
Theory of linear and integer programming
Alexander Schrijver · 1998
Cited alongside, same era.
Squared functional systems and optimization problems
Yurii Nesterov · 2000
Cited alongside, same era.
A simple derivation of a facial reduction algorithm and extended dual systems
Gábor Pataki · 2000
Cited alongside, same era.
Error bounds for linear matrix inequalities
Jos Sturm · 2000
Cited alongside, same era.
Global optimization with polynomials and the problem of moments
Jean B Lasserre · 2001
Cited alongside, same era.
Exact duality in semidefinite programming based on elementary reformulations
Minghui Liu and Gábor Pataki · 2015
Later among the works it cites.
A note on polynomial solvability of the CDT problem
Daniel Bienstock · 2016
Later among the works it cites.
Positive definite Hankel matrix completions and Hamburger moment completions
Hayoung Choi and Farhad Jafari · 2016
Later among the works it cites.
On the turing model complexity of interior point methods for semidefinite programming
Etienne de Klerk and Frank Vallentin · 2016
Later among the works it cites.
A structural geometrical analysis of weakly infeasible sdps
Bruno F. Lourenço, Masakazu Muramatsu, and Takashi Tsuchiya · 2016
Later among the works it cites.
Solving generalized CDT problems via two-parameter eigenvalues
Shinsaku Sakaue, Yuji Nakatsukasa, Akiko Takeda, and Satoru Iwata · 2016
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
James Renegar · 2001
Cited alongside, same era.
Semidefinite programming relaxations for semialgebraic problems
Pablo A Parrilo · 2003
Cited alongside, same era.
Geometric algorithms and combinatorial optimization
Martin Grötschel, László Lovász, and Alexander Schrijver · 2012
Cited alongside, same era.
NP-hardness of deciding convexity of quartic polynomials and related problems
Amir Ali Ahmadi, Alex Olshevsky, Pablo A Parrilo, and John N Tsitsiklis · 2013
Cited alongside, same era.
Strong duality in conic linear programming: facial reduction and extended duals
Gábor Pataki · 2013
Cited alongside, same era.
Facial reduction algorithms for conic optimization problems
Hayato Waki and Masakazu Muramatsu · 2013
Cited alongside, same era.
Later among the works it cites.
The many faces of degeneracy in conic optimization
Dmitriy Drusvyatskiy and Henry Wolkowicz · 2017
Later among the works it cites.
Amenable cones: error bounds without constraint qualifications
Bruno F Lourenço · 2017
Later among the works it cites.
SOS is not obviously automatizable, even approximately
Ryan O’Donnell · 2017
Later among the works it cites.
On the bit complexity of sum-of-squares proofs
Prasad Raghavendra and Benjamin Weitz · 2017
Later among the works it cites.
On the complexity of testing attainment of the optimal value in nonlinear optimization
Amir Ali Ahmadi and Jeffrey Zhang · 2019
Later among the works it cites.
Characterizing bad semidefinite programs: normal forms and short proofs
Gábor Pataki · 2019
Later among the works it cites.
Complexity, exactness, and rationality in polynomial optimization
Daniel Bienstock, Alberto Del Pia, and Robert Hildebrand · 2020
Later among the works it cites.