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

condition numberslinear programmingperturbationssmoothed analysis

Mathematics Subject Classification ID

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

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.

Review text

A distinctive characteristic of the numerical analysis related computations is that they are affected by errors. To understand these errors the condition number of the input at hand is used, which is a positive number measuring the sensitivity of the output with respect to small perturbations of the input. This paper deals with the condition number of linear programs. More specifically, the paper performs, for the aforementioned class of problems, a smoothed analysis of the condition number introduced by Goffin and later generalised by Cucker and Cheung, stating and proving probability tail bounds for it under adversarial random perturbations.

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

• A new condition number for linear programming
• A primal-dual algorithm for solving polyhedral conic systems with a finite-precision machine
• A Problem in Geometric Probability.
• 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
• 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?)
• 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 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
• Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
• 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 kinematic formula in Riemannian homogeneous spaces
• The Probability That a Numerical Analysis Problem is Difficult
• The probability that a slightly perturbed numerical analysis problem is difficult
• The Relaxation Method for Solving Systems of Linear Inequalities
• The reverse isoperimetric problem for Gaussian measure

Cited in

(8)

• On the expected condition number of linear programming problems
• Sharp recovery bounds for convex demixing, with applications
• Probabilistic analyses of condition numbers
• Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems
• Smoothed analysis of condition numbers and complexity implications for linear programming
• On a problem posed by Steve Smale
• Coverage processes on spheres and condition numbers for linear programming
• 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)