Heuristiken zur Optimierung

9

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 konvexG(x)=Mindestyf(x,y)h(y)=Mindestxf(x,y)

Algorithmus : Die Iteration ichth beginnt mit xich,yich .

  1. xich+1argMindestxf(x,yich)
  2. yich+1argMindestyf(xich+1,y)

Bekannteste App : bedeutet, iteriertes engstes Paar.k

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

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

Suresh Venkat
quelle
"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)." Also kein simuliertes Tempern, statistische Mechanik usw.?
Joe Fitzsimons
Ich habe eigentlich kein Problem mit simuliertem Tempern, und als ich dies schrieb, habe ich versucht, einen Weg zu finden, um SA zu behalten und GAs auszuschließen :).
Suresh Venkat

Antworten:

2

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 bewiesenw(θ)F.(θ)2θR.nF.(θ)R.mw(θ)R.


L.p

mirror2image
quelle