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$. 


$x_{i+1} \leftarrow \arg \min_x f(x, y_i)$
$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 :)
Name: iterated reweighted least square

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$

Conditions:  depend on case

Algorithm: obvious - fix weights, solve quadratic problem, recalculate weights

Best known app: geometric median,  M-estimators,$L_p$ norm, compressed sensing

Theory:  proven on-case-to-case basis