Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system

DOI10.1007/S101070000165zbMath0989.65061MaRDI QIDQ1587936

Robert M. Freund, Marina A. Epelman

Publication date: 28 February 2001

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

zbMATH Keywords

algorithmcomputational complexitycondition numberiterative methodconditioninginterior point methodnormed linear spacesellipsoid methodpartially ordered spaceconic linear systems

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10) Numerical computation of matrix norms, conditioning, scaling (65F35) Linear operators on ordered spaces (47B60) Numerical solutions to equations with linear operators (65J10) Equations and inequalities involving linear operators, with vector unknowns (47A50) Complexity and performance of numerical algorithms (65Y20)

Related Items (32)

Examples with decreasing largest inscribed ball for deterministic rescaling algorithms ⋮ Linearly convergent away-step conditional gradient for non-strongly convex functions ⋮ On Chubanov’s Method for Solving a Homogeneous Inequality System ⋮ Rescaled Coordinate Descent Methods for Linear Programming ⋮ Distance to ill-posedness in linear optimization via the Fenchel-Legendre conjugate ⋮ A primal-dual symmetric relaxation for homogeneous conic systems ⋮ Theorems of the alternative for conic integer programming ⋮ Solving conic systems via projection and rescaling ⋮ Smoothed analysis of condition numbers and complexity implications for linear programming ⋮ Stability in linear optimization and related topics. A personal tour ⋮ Generalized self-concordant analysis of Frank-Wolfe algorithms ⋮ First-order methods for convex optimization ⋮ Hopfield neural networks in large-scale linear optimization problems ⋮ Rescaling Algorithms for Linear Conic Feasibility ⋮ A condition-based algorithm for solving polyhedral feasibility problems ⋮ Some preconditioners for systems of linear inequalities ⋮ An improved version of Chubanov's method for solving a homogeneous feasibility problem ⋮ Normality and modulability indices. I: Convex cones in normed spaces ⋮ Conic programming: infeasibility certificates and projective geometry ⋮ On the block-structured distance to non-surjectivity of sublinear mappings ⋮ Conic systems and sublinear mappings: equivalent approaches. ⋮ Distance to ill-posedness and the consistency value of linear semi-infinite inequality systems ⋮ On the von Neumann and Frank--Wolfe Algorithms with Away Steps ⋮ The condition number of a function relative to a set ⋮ A Data-Independent Distance to Infeasibility for Linear Conic Systems ⋮ Randomized Gradient Boosting Machine ⋮ Polytope Conditioning and Linear Convergence of the Frank–Wolfe Algorithm ⋮ On strata of degenerate polyhedral cones. I: Condition and distance to strata ⋮ The Condition Number of Riemannian Approximation Problems ⋮ A characterization theorem and an algorithm for a convex hull problem ⋮ First-order methods for the convex hull membership problem ⋮ Projection and Rescaling Algorithm for Finding Maximum Support Solutions to Polyhedral Conic Systems

This page was built for publication: Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system