On two measures of problem instance complexity and their correlation with the performance of SeDuMi on second-order cone problems

DOI10.1007/s10589-005-3911-0zbMath1116.90120OpenAlexW2071359252MaRDI QIDQ853555

Zhi Cai, Robert M. Freund

Publication date: 17 November 2006

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

Full work available at URL: http://hdl.handle.net/1721.1/5540

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Complexity and performance of numerical algorithms (65Y20)

Related Items

Behavioral measures and their correlation with IPM iteration counts on semi-definite programming problems ⋮ On the behavior of the homogeneous self-dual model for conic convex optimization

Uses Software

• SeDuMi

Cites Work

• Unnamed Item
• Some perturbation theory for linear programming
• Complexity of convex optimization using geometry-based measures and a reference point
• Two properties of condition numbers for convex programs via implicitly defined barrier functions
• Linear programming, complexity theory and elementary functional analysis
• Some characterizations and properties of the ``distance to the ill-posedness and the condition measure of a conic linear system
• On the behavior of the homogeneous self-dual model for conic convex optimization
• An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
• Computational Experience and the Explanatory Value of Condition Measures for Linear Optimization
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Condition-Based Complexity of Convex Optimization in Conic Linear Form via the Ellipsoid Algorithm
• Understanding the Geometry of Infeasible Perturbations of a Conic Linear System
• On the Complexity of Computing Estimates of Condition Measures of a Conic Linear System