Heurystyka dla optymalizacji

9

Ponieważ jest piątek, czas na pytanie CW. Szukam heurystyki, która ma szerokie zastosowanie w problemach związanych z optymalizacją. Aby ograniczyć zakres do bardziej „przyjaznej teorii” heurystyki, oto zasady (niektóre arbitralne, niektóre nie)

  • Powinna to być dobrze zdefiniowana metoda bez wielu parametrów i z konkretnym czasem pracy (może na iterację)
  • Powinny mieć związane z tym pewne znane wyniki teoretyczne (szybkość zbieżności, granice aproksymacji, jeśli takie istnieją, właściwości stacjonarne itd.)
  • Powinien mieć szerokie zastosowanie i co najmniej jedną flagową aplikację, jeśli jest to albo metoda z wyboru, albo jedna z niewielu.
  • nie powinna być inspirowana naturą (choć wydaje się to frywolnym sprzeciwem, staram się wykluczyć algorytmy genetyczne, optymalizację kolonii mrówek i tym podobne).

Odpowiedzi najlepiej powinny mieć następujący format: oto przykład.

Nazwa : naprzemienna optymalizacja

Cel : zminimalizowanie funkcji (generalnie nie wypukłej)f(x,y)

Warunki : Powiązane funkcjeg(x)=minyf(x,y)i h(y)=minxf(x,y) są wypukłe

Algorytm : iteracja ith zaczyna się od xi,yi .

  1. xi+1argminxf(x,yi)
  2. yi+1argminyf(xi+1,y)

Najbardziej znana aplikacja : k oznacza, iterowana najbliższa para.

Teoria : Znane wyniki dla średnich, ogólne wystarczające warunki dla globalnej optymalności ramk

ps Może się okazać, że twoja odpowiedź kończy się wykładem na seminarium z algorytmami, które planuję :)

Suresh Venkat
źródło
„nie powinna być inspirowana naturą (choć wydaje się to frywolnym sprzeciwem, staram się wykluczyć algorytmy genetyczne, optymalizację kolonii mrówek itp.”). Więc nie ma symulowanego wyżarzania, mechaniki statystycznej itp.?
Joe Fitzsimons
Właściwie nie mam problemu z symulowanym wyżarzaniem, a kiedy to napisałem, starałem się znaleźć sposób na zachowanie SA i wykluczenie GA :).
Suresh Venkat

Odpowiedzi:

2

Nazwa: iterowana przeważona najmniejsza kwadrat
Cel: zminimalizować funkcję formularza , , , Warunki: zależą od przypadku Algorytm: oczywisty - ustalanie ciężarów, rozwiązywanie problemu kwadratowego, przeliczanie ciężarów Najbardziej znana aplikacja: mediana geometryczna, M-estymatory, norma , wykrywanie skompresowane Teoria: sprawdzona na podstawie indywidualnych przypadkóww(θ)F(θ)2θRnF(θ)Rmw(θ)R


Lp

mirror2image
źródło