Mathematics – Optimization and Control
Scientific paper
2008-03-06
Mathematics
Optimization and Control
34 pages. Version 3: only cosmetic changes
Scientific paper
We perform a smoothed analysis of the GCC-condition number C(A) of the linear programming feasibility problem \exists x\in\R^{m+1} Ax < 0. Suppose that \bar{A} is any matrix with rows \bar{a_i} of euclidean norm 1 and, independently for all i, let a_i be a random perturbation of \bar{a_i} following the uniform distribution in the spherical disk in S^m of angular radius \arcsin\sigma and centered at \bar{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 \arcsin\sigma, 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.
Amelunxen Dennis
Bürgisser Peter
No associations
LandOfFree
Robust Smoothed Analysis of a Condition Number for Linear Programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Robust Smoothed Analysis of a Condition Number for Linear Programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Robust Smoothed Analysis of a Condition Number for Linear Programming will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-14360