New complexity analysis of the primal-dual method for semidefinite optimization based on the Nesterov-Todd direction

DOI10.1023/A:1017514422146zbMath1009.90081OpenAlexW2269291726MaRDI QIDQ5949888

Cornelis Roos, Tamás Terlaky, Jiming Peng

Publication date: 5 December 2001

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1017514422146

zbMATH Keywords

semidefinite optimizationpolynomial complexityprimal-dual interior point methods

Mathematics Subject Classification ID

Semidefinite programming (90C22) Abstract computational complexity for mathematical programming problems (90C60) Interior-point methods (90C51)

Related Items

A FULL NT-STEP INFEASIBLE INTERIOR-POINT ALGORITHM FOR SEMIDEFINITE OPTIMIZATION BASED ON A SELF-REGULAR PROXIMITY, Simplified infeasible interior-point algorithm for SDO using full Nesterov-Todd step, A full-NT-step infeasible interior-point algorithm for SDP based on kernel functions, Complexity analysis of infeasible interior-point method for semidefinite optimization based on a new trigonometric kernel function, An infeasible interior point method for the monotone SDLCP based on a transformation of the central path

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming
• Symmetric primal-dual path-following algorithms for semidefinite programming
• Semidefinite programming in combinatorial optimization
• Semidefinite programming
• Probabilistic Analysis of an Infeasible-Interior-Point Algorithm for Linear Programming
• Interior-Point Methods for the Monotone Semidefinite Linear Complementarity Problem in Symmetric Matrices
• Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
• On the Nesterov--Todd Direction in Semidefinite Programming
• Self-Scaled Barriers and Interior-Point Methods for Convex Programming
• Primal--Dual Path-Following Algorithms for Semidefinite Programming
• Primal-Dual Interior-Point Methods for Self-Scaled Cones
• On Extending Some Primal--Dual Interior-Point Algorithms From Linear Programming to Semidefinite Programming
• Existence and Uniqueness of Search Directions in Interior-Point Algorithms for the SDP and the Monotone SDLCP
• Semidefinite Programming
• An Interior-Point Method for Semidefinite Programming
• New complexity analysis of the primal-dual Newton method for linear optimization