Robust smoothed analysis of a condition number for linear programming

• 成果类型: Article
• 署名作者: Buergisser, Peter; Amelunxen, Dennis
• 署名单位: University of Paderborn
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-010-0346-x
• 发表日期: 2012
• 页码: 221-251
• 关键词: numerical-analysis problem; conic systems; Complexity theory; probability; algorithms; difficult

摘要

We perform a smoothed analysis of the GCC-condition number C(A) of the linear programming feasibility problem there exists x is an element of Rm+1 Ax < 0. Suppose that <(A)over bar> is any matrix with rows (a) over bar (i) of euclidean norm 1 and, independently for all i, let a(i) be a random perturbation of (a) over bar (i) following the uniform distribution in the spherical disk in S-m of angular radius arcsin sigma and centered at (a) over bar (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 et al. (Math Program Ser A, 2009). Our result is robust in the sense that it easily extends to radially symmetric probability distributions supported on a spherical disk of radius arcsin sigma, whose density may even have a singularity at the center of the perturbation. Our proofs combine ideas from a recent paper of Burgisser et al. (Math Comp 77(263), 2008) with techniques of Dunagan et al.