On the Turing Model Complexity of Interior Point Methods for Semidefinite Programming
From MaRDI portal
Publication:2821802
DOI10.1137/15M103114XzbMath1346.90661arXiv1507.03549OpenAlexW1639981145MaRDI QIDQ2821802
Frank Vallentin, Etienne de Klerk
Publication date: 23 September 2016
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1507.03549
Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Interior-point methods (90C51)
Related Items
Solving generic nonarchimedean semidefinite programs using stochastic game algorithms, Least distortion Euclidean embeddings of flat tori, A note on the computational complexity of the moment-SOS hierarchy for polynomial optimization, Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks, How Do Exponential Size Solutions Arise in Semidefinite Programming?, An experimental comparison of methods for computing the numerical radius, Minimizing Rational Functions: A Hierarchy of Approximations via Pushforward Measures, On exact Reznick, Hilbert-Artin and Putinar's representations, Stochastic numerical approach for solving second order nonlinear singular functional differential equation, An approximation algorithm for the maximum spectral subgraph problem, Complete positivity and distance-avoiding sets
Cites Work
- A new polynomial-time algorithm for linear programming
- Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
- The ellipsoid method and its consequences in combinatorial optimization
- Geometric algorithms and combinatorial optimization
- An exact duality theory for semidefinite programming and its complexity implications
- Some characterizations and properties of the ``distance to the ill-posedness and the condition measure of a conic linear system
- Effects of Finite-Precision Arithmetic on Interior-Point Methods for Nonlinear Programming
- A Mathematical View of Interior-Point Methods in Convex Optimization
- Latest Developments in the SDPA Family for Solving Large-Scale SDPs
- Approximation Algorithms and Semidefinite Programming
- New Code Upper Bounds From the Terwilliger Algebra and Semidefinite Programming
- High-Accuracy Semidefinite Programming Bounds for Kissing Numbers
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Incorporating Condition Measures into the Complexity Theory of Linear Programming
- Primal-Dual Interior-Point Methods for Semidefinite Programming in Finite Precision
- Upper bounds for packings of spheres of several radii
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
