9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ "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. ? $\endgroup$ – Joe Fitzsimons May 1 '11 at 14:09
  • $\begingroup$ 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 :). $\endgroup$ – Suresh Venkat May 2 '11 at 2:10
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.