Smoothed analysis of condition numbers and complexity implications for linear programming

• 成果类型: Article
• 署名作者: Dunagan, John; Spielman, Daniel A.; Teng, Shang-Hua
• 署名单位: Yale University; Microsoft; Boston University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-009-0278-5
• 发表日期: 2011
• 页码: 315-350
• 关键词: interior-point methods; algorithm; termination; geometry

摘要

nn We perform a smoothed analysis of Renegar's condition number for linear programming by analyzing the distribution of the distance to ill-posedness of a linear program subject to a slight Gaussian perturbation. In particular, we show that for every n-by-d matrix (A) over bar, n-vector (b) over bar, and d-vector (c) over bar satisfying parallel to(A) over bar, (b) over bar, (c) over bar parallel to(F) <= 1and every sigma <= 1, E-A,E-b,E-c[log C(A,b,c)] = O(log(nd/sigma)), where A, b and c are Gaussian perturbations of (A) over bar, (b) over bar and (c) over bar of variance sigma(2) and C( A, b, c) is the condition number of the linear program defined by (A, b, c). From this bound, we obtain a smoothed analysis of interior point algorithms. By combining this with the smoothed analysis of finite termination of Spielman and Teng (Math. Prog. Ser. B, 2003), we show that the smoothed complexity of interior point algorithms for linear programming is O(n(3) log(nd/sigma)).