Heuristics for Optimization

Since it's Friday, it's time for a CW question. I'm looking for heuristics that have wide use in optimization problems. To limit the scope to more 'theory-friendly' heuristics, here are the rules (some arbitrary, some not)

• It should be a well defined method without numerous parameters, and with a concrete running time (maybe per iteration)
• It should have some known theoretical results associated with it (rate of convergence, approximation bounds if any, stationary properties, and so on)
• It should have wide applicability and at least one flagship application where it's either the method of choice or one of a few.
• it should not be inspired by nature (while this seems like a frivolous objection, I'm trying to exclude genetic algorithms, ant colony optimization and the like).

Answers should ideally be in the following format: here's an example.

Name: Alternating optimizaton

Goal: Minimize a (generally nonconvex) function $f(x,y)$

Conditions: The associated functions $g(x) = \min_y f(x,y)$ and $h(y) = \min_x f(x,y)$ are convex

Algorithm: $i^{\text{th}}$ iteration starts with $x_i, y_i$.

1. $x_{i+1} \leftarrow \arg \min_x f(x, y_i)$
2. $y_{i+1} \leftarrow \arg\min_y f(x_{i+1}, y)$

Best known app: $k$-means, iterated closest pair.

Theory: Known results on $k$-means, general sufficient conditions for global optimality of framework

p.s You might find that your answer ends up as a lecture in an algorithms seminar I'm planning :)

• "it should not be inspired by nature (while this seems like a frivolous objection, I'm trying to exclude genetic algorithms, ant colony optimization and the like)." So no simulated annealing, statistical mechanics, etc. ? – Joe Fitzsimons May 1 '11 at 14:09
• I actually have no problem with simulated annealing, and when I wrote this, I was trying to find a way to keep SA and exclude GAs :). – Suresh Venkat May 2 '11 at 2:10

Goal: minimize function of the form $\sum w(\theta)F(\theta)^2$, $\theta\in R^n$, $F(\theta) \in R^m$, $w(\theta)\in R$
Best known app: geometric median, M-estimators,$L_p$ norm, compressed sensing