Heuristiken zur Optimierung

Da es Freitag ist, ist es Zeit für eine CW-Frage. Ich suche nach Heuristiken, die bei Optimierungsproblemen weit verbreitet sind. Um den Umfang auf "theoretisch freundlichere" Heuristiken zu beschränken, sind hier die Regeln (einige willkürlich, andere nicht).

• Es sollte eine genau definierte Methode ohne zahlreiche Parameter und mit einer konkreten Laufzeit sein (möglicherweise pro Iteration).
• Es sollten einige bekannte theoretische Ergebnisse vorliegen (Konvergenzrate, etwaige Approximationsgrenzen, stationäre Eigenschaften usw.).
• Es sollte eine breite Anwendbarkeit und mindestens eine Flaggschiff-Anwendung haben, bei der es sich entweder um die Methode der Wahl oder um eine von wenigen handelt.
• Es sollte nicht von der Natur inspiriert sein (obwohl dies wie ein leichtfertiger Einwand erscheint, versuche ich, genetische Algorithmen, die Optimierung von Ameisenkolonien und dergleichen auszuschließen).

Die Antworten sollten idealerweise im folgenden Format vorliegen: Hier ist ein Beispiel.

Name : Wechselnde Optimierung

Ziel : Minimiere eine (im Allgemeinen nicht konvexe) Funktion $f(x,y)$

Bedingungen : Die zugehörigen Funktionen und h (y) = \ min_x f (x, y) sind konvex$g(x) = \min_y f(x,y)$$h(y) = \min_x f(x,y)$

Algorithmus : Die Iteration $i^{\text{th}}$ beginnt mit $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)$

Bekannteste App : bedeutet, iteriertes engstes Paar.$k$

Theorie : Bekannte Ergebnisse auf Mitteln, allgemein ausreichende Bedingungen für die globale Optimalität des Frameworks$k$

ps Sie werden vielleicht feststellen, dass Ihre Antwort als Vorlesung in einem von mir geplanten Algorithmus-Seminar endet :)

Name: iteriertes neu gewichtetes kleinstes Quadrat
Ziel: Minimieren Sie die Funktion der Form , , , Bedingungen: abhängig vom Fall Algorithmus: offensichtlich - Gewichte fixieren, quadratisches Problem lösen, Gewichte neu berechnen Bekannteste App: geometrischer Median, M-Schätzer, Norm, komprimierte Erfassung Theorie: von Fall zu Fall bewiesen$\sum w(\theta)F(\theta)^2$$\theta\in R^n$$F(\theta) \in R^m$$w(\theta)\in R$


$L_p$