On the Turing model complexity of interior point methods for semidefinite programming
From MaRDI portal
Publication:2821802
DOI10.1137/15M103114XzbMATH Open1346.90661arXiv1507.03549OpenAlexW1639981145MaRDI QIDQ2821802FDOQ2821802
Authors: E. de Klerk, Frank Vallentin 
Publication date: 23 September 2016
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Abstract: It is known that one can solve semidefinite programs to within fixed accuracy in polynomial time using the ellipsoid method (under some assumptions). In this paper it is shown that the same holds true when one uses the short-step, primal interior point method. The main idea of the proof is to employ Diophantine approximation at each iteration to bound the intermediate bit-sizes of iterates.
Full work available at URL: https://arxiv.org/abs/1507.03549
Recommendations
- On the Complexity of a Practical Interior-Point Method
- scientific article; zbMATH DE number 409894
- An Interior-Point Method for Semidefinite Programming
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- Interior-point algorithms for semi-infinite programming
- On a general class of interior-point algorithms for semidefinite programming with polynomial complexity and superlinear convergence
- On homogeneous interrior-point algorithms for semidefinite programming
- New complexity analysis of a full Nesterov-Todd step interior-point method for semidefinite optimization
- Improved complexity analysis of full Nesterov-Todd step interior-point methods for semidefinite optimization
- Interior-point algorithms for semidefinite programming based on a nonlinear formulation
Analysis of algorithms and problem complexity (68Q25) Interior-point methods (90C51) Semidefinite programming (90C22)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A new polynomial-time algorithm for linear programming
- Geometric algorithms and combinatorial optimization
- The ellipsoid method and its consequences in combinatorial optimization
- An exact duality theory for semidefinite programming and its complexity implications
- A mathematical view of interior-point methods in convex optimization
- Incorporating Condition Measures into the Complexity Theory of Linear Programming
- Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
- Some characterizations and properties of the ``distance to the ill-posedness and the condition measure of a conic linear system
- Title not available (Why is that?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- New Code Upper Bounds From the Terwilliger Algebra and Semidefinite Programming
- Approximation algorithms and semidefinite programming.
- Upper bounds for packings of spheres of several radii
- Title not available (Why is that?)
- High-Accuracy Semidefinite Programming Bounds for Kissing Numbers
- Primal-Dual Interior-Point Methods for Semidefinite Programming in Finite Precision
- Effects of finite-precision arithmetic on interior-point methods for nonlinear programming
- Latest Developments in the SDPA Family for Solving Large-Scale SDPs
- Title not available (Why is that?)
Cited In (11)
- Complete positivity and distance-avoiding sets
- On semidefinite programming characterizations of the numerical radius and its dual norm
- Least distortion Euclidean embeddings of flat tori
- On exact Reznick, Hilbert-Artin and Putinar's representations
- Minimizing rational functions: a hierarchy of approximations via pushforward measures
- An approximation algorithm for the maximum spectral subgraph problem
- A note on the computational complexity of the moment-SOS hierarchy for polynomial optimization
- How Do Exponential Size Solutions Arise in Semidefinite Programming?
- An experimental comparison of methods for computing the numerical radius
- Stochastic numerical approach for solving second order nonlinear singular functional differential equation
- Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks
This page was built for publication: On the Turing model complexity of interior point methods for semidefinite programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2821802)
