Heuristics for Optimization

Question

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 :)

Answer 1

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