On the Turing model complexity of interior point methods for semidefinite programming
From MaRDI portal
Publication:2821802
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.
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
Cites work
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 3516928 (Why is no real title available?)
- scientific article; zbMATH DE number 3637614 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 1534296 (Why is no real title available?)
- scientific article; zbMATH DE number 964349 (Why is no real title available?)
- A mathematical view of interior-point methods in convex optimization
- A new polynomial-time algorithm for linear programming
- An exact duality theory for semidefinite programming and its complexity implications
- Approximation algorithms and semidefinite programming.
- Effects of finite-precision arithmetic on interior-point methods for nonlinear programming
- Geometric algorithms and combinatorial optimization
- 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
- Latest Developments in the SDPA Family for Solving Large-Scale SDPs
- New Code Upper Bounds From the Terwilliger Algebra and Semidefinite Programming
- Primal-Dual Interior-Point Methods for Semidefinite Programming in Finite Precision
- Reduction of symmetric semidefinite programs using the regular -representation
- Some characterizations and properties of the ``distance to the ill-posedness and the condition measure of a conic linear system
- The ellipsoid method and its consequences in combinatorial optimization
- Upper bounds for packings of spheres of several radii
Cited in
(11)- Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks
- 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
- An approximation algorithm for the maximum spectral subgraph problem
- Minimizing rational functions: a hierarchy of approximations via pushforward measures
- 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
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)
