Smoothed Analysis of Renegar’s Condition Number for Linear Programming

John Dunagan, Daniel A. Spielman, Shang‐Hua Teng2002

TL;DR

This paper introduces a "smoothed analysis" for linear programming, showing that even with slight random "noise" added to the problem's data, the condition number (a measure of how sensitive the problem is to small changes) remains small with high probability. This provides a theoretical explanation for why interior-point algorithms, which are known to be slow in the worst-case, often perform very well in practice.

What Problem Does This Paper Address?

Linear programming (LP) is a fundamental optimization problem with wide applications. Interior-point algorithms are a popular class of methods for solving LPs, known for their theoretical polynomial-time worst-case complexity. However, their practical performance often far exceeds these worst-case bounds. This discrepancy suggests that worst-case analysis might not fully capture the behavior of these algorithms on typical inputs. This paper aims to bridge this gap by using "smoothed analysis," a technique that examines algorithm performance under slight random perturbations of the input, to understand the behavior of LP condition numbers and, consequently, interior-point algorithms.

Methods

The core of the paper is the smoothed analysis of Renegar's condition number for linear programs. The authors define a "primal condition number" and a "dual condition number" for various canonical forms of LPs. They then introduce Gaussian perturbations to the input matrices and vectors, with variance $\sigma^2$. The key technical contribution is proving that the expected logarithm of these condition numbers is bounded by $O(\log(nd/\sigma))$ with high probability. This involves extending existing theories of distance to ill-posedness to conic linear programs and leveraging probabilistic tools like Helly's Theorem and bounds on Gaussian random variables. The analysis is structured by first analyzing primal and dual condition numbers separately and then combining them.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Smoothed Analysis Explains Practical Performance: The paper provides a theoretical basis for why interior-point algorithms, despite potentially poor worst-case performance, are efficient in practice. By showing that the condition number (which directly impacts algorithm complexity) is small under slight perturbations, it suggests that typical real-world problems are "well-behaved" in this smoothed sense.
  • Condition Number as "Wiggle Room": The condition number is framed as a measure of "wiggle room" or distance to ill-posedness. A small condition number implies that the problem is far from being ill-posed, meaning small perturbations don't drastically change its feasibility or solution.
  • Generalization of Ill-Posedness: The authors extend the concept of distance to ill-posedness to conic linear programs, which are a more general form of LP, making their analysis applicable to various LP formulations.
  • Probabilistic Tools are Crucial: The proof relies heavily on probabilistic arguments and geometric inequalities, demonstrating the power of these tools in analyzing algorithmic complexity in a smoothed setting.

Key Results

  • The expected logarithm of Renegar's condition number for a linear program, subject to Gaussian perturbations of variance $\sigma^2$, is $O(\log(nd/\sigma))$ with high probability.
  • This leads to a smoothed complexity bound of $O(n^3 \log(nd/\sigma\epsilon))$ for Renegar's interior-point algorithm to find a solution of relative accuracy $\epsilon$.
  • When combined with smoothed analysis of finite termination procedures, this yields an overall smoothed complexity of $O(n^3 \log(nd/\sigma))$ for finding exact solutions.

Limitations and Future Work

  • Model of Perturbation: The paper focuses on Gaussian perturbations. Future work could explore other perturbation models, such as property-preserving or zero-preserving perturbations, to see if similar bounds can be achieved.
  • Non-linear Problems: The authors suggest that condition numbers are relevant for non-linear optimization problems as well, and that their smoothed analysis techniques might be extendable to these areas.
  • Specific LP Forms: While the analysis covers canonical forms, further investigation into specific LP structures and their smoothed condition numbers could be beneficial.

Summary updated

Abstract

For any linear program, we show that a slight random relative perturbation of that linear program has small condition number with high probability. Following [ST01], we call this smoothed analysis of the condition number. Part of our main result is that the expectation of the log of the condition number of any appropriately scaled linear program subject to a Gaussian perturbation of variance σ² is at most O(log nd/σ) with high probability. Since the condition number bounds the running time of many algorithms for convex programming, this may explain their observed fast convergence.
BibTeX
@misc{dunagan2002smoothed,
  author = {John Dunagan and Daniel A. Spielman and Shang‐Hua Teng},
  title = {{Smoothed Analysis of Renegar’s Condition Number for Linear Programming}},
  year = {2002},
}
Figure