Speaker: John Dunagan, MIT Dept of Mathematics

Title: Perturbations to Linear Programs

Abstract:

Consider an arbitrary linear program Ax < b with m constraints in d
dimensions. Let each element of the constraint matrix be subject to a
small random Gaussian perturbation of variance sigma^2. We show that a
simple classical algorithm for solving linear programs, the perceptron 
algorithm[1954], succeeds in finding a feasible point (if one exists) in 
O~(m^2 d^3 /(sigma^2 delta)) iterations with probability at
least 1-delta. This is joint work with Avrim Blum to appear in SODA '02.

We proceed to analyze Renegar's condition number for linear programs
under the same perturbation model. Condition numbers measure the
ill-posedness of a problem; they are ubiquitous in numerical analysis
and scientific computing. Numerous interior point methods have recently
been analyzed using Renegar's condition number. We show that the
condition number is O~(m^2 d^2 /(sigma^2 delta)) with
probability at least 1-delta. This is joint work with Dan Spielman (MIT) 
and Shang-Hua Teng (UIUC -> BU) submitted to the SIAM Conference
on Optimization.

Both of these results can be viewed in the smoothed complexity model
introduced by Spielman and Teng. Smoothed analysis interpolates between
worst-case and average-case analysis by measuring the running time on an
arbitrary instance under a random perturbation. A large perturbation yields
traditional average-case analysis; as the perturbation becomes vanishingly
small, we obtain traditional worst-case analysis. In this framework, our
results are that the perceptron algorithm and condition number have
polynomial smoothed complexity with high probability.