<p>Name: iterated reweighted least square
<br>
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$
<br>
Conditions:  depend on case
<br>
Algorithm: obvious - fix weights, solve quadratic problem, recalculate weights
<br>
Best known app: geometric median,  M-estimators,$L_p$ norm, compressed sensing
<br>
Theory:  proven on-case-to-case basis</p>

CC BY-SA 3.0
2011-05-01T04:24:28.583Z
2011-05-01T05:42:14.357Z
2011-05-01T05:42:14.357Z
mirror2image
<p>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)</p>

<ul>
<li>It should be a well defined method without numerous parameters, and with a concrete running time (maybe per iteration)</li>
<li>It should have some known theoretical results associated with it (rate of convergence, approximation bounds if any, stationary properties, and so on)</li>
<li>It should have wide applicability and at least one flagship application where it's either the method of choice or one of a few.</li>
<li>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). </li>
</ul>

<p>Answers should ideally be in the following format: here's an example. </p>

<p><strong>Name</strong>: Alternating optimizaton</p>

<p><strong>Goal</strong>: Minimize a (generally nonconvex) function $f(x,y)$</p>

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

<p><strong>Algorithm</strong>: $i^{\text{th}}$ iteration starts with $x_i, y_i$. </p>

<ol>
<li>$x_{i+1} \leftarrow \arg \min_x f(x, y_i)$</li>
<li>$y_{i+1} \leftarrow \arg\min_y f(x_{i+1}, y)$</li>
</ol>

<p><strong>Best known app</strong>: $k$-means, iterated closest pair. </p>

<p><strong>Theory</strong>: Known results on $k$-means, <a href="http://geomblog.blogspot.com/2008/01/important-heuristics-alternating.html" rel="nofollow">general sufficient conditions for global optimality of framework</a></p>

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

CC BY-SA 3.0
2011-05-01T14:09:37.707Z
"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
CC BY-SA 3.0
2011-05-02T02:10:10.870Z
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
<ds.algorithms><reference-request><optimization><heuristics>
Heuristics for Optimization
Suresh Venkat
# Heuristics for Optimization

(Asked by: username_0 on 2011-04-30)

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](http://geomblog.blogspot.com/2008/01/important-heuristics-alternating.html)

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

**Tags:** ds.algorithms, reference-request, optimization, heuristics

> **Comments:**
> **username_1**: "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. ?  
> **username_0**: 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 :).  

---

## 1 answers

### Answer by username_2 on 2011-05-01. Score: 2

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


---

