Complexity of convex optimization using geometry-based measures and a reference point

DOI10.1007/s10107-003-0435-1zbMath1098.90095OpenAlexW2128341540MaRDI QIDQ1434069

Robert M. Freund

Publication date: 1 July 2004

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

complexityconvex optimizationinterior-point methodbarrier method

Mathematics Subject Classification ID

Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Interior-point methods (90C51)

Related Items (11)

On two measures of problem instance complexity and their correlation with the performance of SeDuMi on second-order cone problems ⋮ Behavioral measures and their correlation with IPM iteration counts on semi-definite programming problems ⋮ A primal-dual symmetric relaxation for homogeneous conic systems ⋮ Smoothed analysis of condition numbers and complexity implications for linear programming ⋮ Largest dual ellipsoids inscribed in dual cones ⋮ Preprocessing and Regularization for Degenerate Semidefinite Programs ⋮ New characterizations of Hoffman constants for systems of linear constraints ⋮ On the Implementation and Usage of SDPT3 – A Matlab Software Package for Semidefinite-Quadratic-Linear Programming, Version 4.0 ⋮ The condition number of a function relative to a set ⋮ A Data-Independent Distance to Infeasibility for Linear Conic Systems ⋮ A geometric analysis of Renegar's condition number, and its interplay with conic curvature

This page was built for publication: Complexity of convex optimization using geometry-based measures and a reference point