Condition-Based Complexity of Convex Optimization in Conic Linear Form via the Ellipsoid Algorithm

DOI10.1137/S105262349732829XzbMath0953.90044MaRDI QIDQ4702342

Jorge R. Vera, Robert M. Freund

Publication date: 24 November 1999

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

zbMATH Keywords

error analysisconditioningellipsoid methodcomplexity of convex optimization

Mathematics Subject Classification ID

Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05)

Related Items (30)

Extreme points of well-posed polytopes ⋮ On two measures of problem instance complexity and their correlation with the performance of SeDuMi on second-order cone problems ⋮ A primal-dual symmetric relaxation for homogeneous conic systems ⋮ Solidity indices for convex cones ⋮ Strong duality and minimal representations for cone optimization ⋮ Inradius and circumradius of various convex cones arising in applications ⋮ Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization ⋮ Smoothed analysis of condition numbers and complexity implications for linear programming ⋮ Sampling rates for \(\ell^1\)-synthesis ⋮ Generating and measuring instances of hard semidefinite programs ⋮ Centers of sets with symmetry or cyclicity properties ⋮ A condition-based algorithm for solving polyhedral feasibility problems ⋮ Geometric measures of convex sets and bounds on problem sensitivity and robustness for conic linear optimization ⋮ Some preconditioners for systems of linear inequalities ⋮ On two-stage convex chance constrained problems ⋮ Computing the radius of pointedness of a convex cone ⋮ Normality and modulability indices. I: Convex cones in normed spaces ⋮ Probabilistic analysis of condition numbers for linear programming ⋮ On the block-structured distance to non-surjectivity of sublinear mappings ⋮ Conic systems and sublinear mappings: equivalent approaches. ⋮ On properties of different notions of centers for convex cones ⋮ Distance to ill-posedness and the consistency value of linear semi-infinite inequality systems ⋮ The condition number of a function relative to a set ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Lipschitz and Hölder continuity results for some functions of cones ⋮ A geometric analysis of Renegar's condition number, and its interplay with conic curvature ⋮ On strata of degenerate polyhedral cones. I: Condition and distance to strata ⋮ The Condition Number of Riemannian Approximation Problems ⋮ Probabilistic analysis of the Grassmann condition number

This page was built for publication: Condition-Based Complexity of Convex Optimization in Conic Linear Form via the Ellipsoid Algorithm