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)
Warunki : Powiązane funkcjei są wypukłe
Algorytm : iteracja zaczyna się od .
Najbardziej znana aplikacja : oznacza, iterowana najbliższa para.
Teoria : Znane wyniki dla średnich, ogólne wystarczające warunki dla globalnej optymalności ram
ps Może się okazać, że twoja odpowiedź kończy się wykładem na seminarium z algorytmami, które planuję :)
ds.algorithms
reference-request
optimization
heuristics
Suresh Venkat
źródło
źródło
Odpowiedzi:
Nazwa: iterowana przeważona najmniejsza kwadrat∑w(θ)F(θ)2 θ∈Rn F(θ)∈Rm w(θ)∈R
Lp
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ów
źródło