Robust smoothed analysis of a condition number for linear programming

DOI10.1007/S10107-010-0346-XMaRDI QIDQ662310zbMATH OpenOpenAlexFDO

Authors Peter Bürgisser, Dennis Amelunxen

Publication date 22 February 2012

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

Full work available at URL https://arxiv.org/abs/0803.0925

zbMATH Keywords

linear programmingperturbationscondition numberssmoothed analysis

Mathematics Subject Classification ID

Linear programming (90C05) Geometric probability and stochastic geometry (60D05) Sensitivity, stability, parametric optimization (90C31) Random convex sets and integral geometry (aspects of convex geometry) (52A22)

Abstract: We perform a smoothed analysis of the GCC-condition number C(A) of the linear programming feasibility problem exists xinR^{m+1} Ax < 0. Suppose that �ar{A} is any matrix with rows �ar{a_i} of euclidean norm 1 and, independently for all i, let a_i be a random perturbation of �ar{a_i} following the uniform distribution in the spherical disk in S^m of angular radius arcsinsigma and centered at �ar{a_i}. We prove that E(ln C(A)) = O(mn / sigma). A similar result was shown for Renegar's condition number and Gaussian perturbations by Dunagan, Spielman, and Teng [arXiv:cs.DS/0302011]. Our result is robust in the sense that it easily extends to radially symmetric probability distributions supported on a spherical disk of radius arcsinsigma, whose density may even have a singularity at the center of the perturbation. Our proofs combine ideas from a recent paper of B"urgisser, Cucker, and Lotz (Math. Comp. 77, No. 263, 2008) with techniques of Dunagan et al.

Recommendations

• Smoothed analysis of condition numbers and complexity implications for linear programming
• Probabilistic analysis of condition numbers for linear programming
• On the expected condition number of linear programming problems
• Smoothed analysis of termination of linear programming algorithms
• Smoothed analysis of condition numbers

Cites work

• scientific article; zbMATH DE number 3686285 (Why is no real title available?)
• scientific article; zbMATH DE number 1069617 (Why is no real title available?)
• scientific article; zbMATH DE number 3436238 (Why is no real title available?)
• scientific article; zbMATH DE number 1962932 (Why is no real title available?)
• scientific article; zbMATH DE number 873911 (Why is no real title available?)
• A Problem in Geometric Probability.
• A new condition number for linear programming
• A primal-dual algorithm for solving polyhedral conic systems with a finite-precision machine
• Adversarial smoothed analysis
• Conditioning of random conic systems under a general family of input distributions
• Coverage processes on spheres and condition numbers for linear programming
• Incorporating Condition Measures into the Complexity Theory of Linear Programming
• Linear programming, complexity theory and elementary functional analysis
• On the expected condition number of linear programming problems
• Probabilistic analysis of condition numbers for linear programming
• Smooth approximation of convex bodies
• Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
• Smoothed analysis of algorithms
• Smoothed analysis of complex conic condition numbers
• Smoothed analysis of condition numbers
• Smoothed analysis of condition numbers and complexity implications for linear programming
• Smoothed analysis of termination of linear programming algorithms
• Some perturbation theory for linear programming
• Steiner’s formulae on a general 𝑆ⁿ⁺¹
• Tail Decay and Moment Estimates of a Condition Number for Random Linear Conic Systems
• The Probability That a Numerical Analysis Problem is Difficult
• The Relaxation Method for Solving Systems of Linear Inequalities
• The kinematic formula in Riemannian homogeneous spaces
• The probability that a slightly perturbed numerical analysis problem is difficult
• The reverse isoperimetric problem for Gaussian measure

Cited in

(8)

• Smoothed analysis of condition numbers and complexity implications for linear programming
• Sharp recovery bounds for convex demixing, with applications
• Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems
• On a problem posed by Steve Smale
• Coverage processes on spheres and condition numbers for linear programming
• Probabilistic analyses of condition numbers
• On the expected condition number of linear programming problems
• Adversarial smoothed analysis

This page was built for publication: Robust smoothed analysis of a condition number for linear programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q662310)