Heurystyka dla optymalizacji

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 funkcje$g(x) = \min_y f(x,y)$i $h(y) = \min_x f(x,y)$ są wypukłe

Algorytm : iteracja $i^{\text{th}}$ zaczyna się od $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)$

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

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

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

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ów$\sum w(\theta)F(\theta)^2$$\theta\in R^n$$F(\theta) \in R^m$$w(\theta)\in R$


$L_p$