Wysiłek obliczeniowy algorytmów

Rozważ ściśle wypukły, nieograniczony problem optymalizacji$\mathcal{O} := \min_{x \in \mathbb{R}^n} f(x).$Niech oznacza jego unikalne minima, a x_0 będzie początkowym przybliżeniem do x_ \ text {opt}. Wywołamy wektor x an \ epsilon - zamknij rozwiązanie \ mathcal {O} if \ begin {equation} \ frac {|| x - x _ {\ text {opt}} || _2} {|| x_0 - x_ \ text {opt} || _2} \ leq \ epsilon. \ end {równanie}$x_\text{opt}$$x_0$$x_\text{opt}.$$x$$\epsilon-$$\mathcal{O}$

Załóżmy, że istnieją dwa iteracyjne algorytmy $\mathcal{A}_1$ i $\mathcal{A}_2$ aby znaleźć rozwiązanie $\epsilon-$ close dla $\mathcal{O}$ o następujących właściwościach:

1. Dla dowolnego $\epsilon > 0,$ całkowity wysiłek obliczeniowy, tj. Wysiłek wymagany na iterację $\times$ całkowitą liczbę iteracji, w celu znalezienia rozwiązania $\epsilon-$ close jest taki sam dla obu algorytmów.
2. Wysiłek na iterację dla $\mathcal{A}_1$ wynosi $O(n),$ powiedzmy, podczas gdy dla $\mathcal{A}_2$ jest $O(n^2).$

Czy są sytuacje, w których jeden wolałby jeden algorytm od drugiego? Dlaczego?

Zazwyczaj bardzo trudno jest, jeśli nie niemożliwe, zaimplementować równoległą wersję iteracyjnego algorytmu, który działa równolegle w różnych iteracjach. Zakończenie jednej iteracji jest naturalnym punktem sekwencji. Jeśli jeden algorytm wymaga mniejszej liczby iteracji, ale więcej pracy na iterację, bardziej prawdopodobne jest, że ten algorytm można skutecznie zaimplementować równolegle.

Przykładem tego jest programowanie liniowe, w którym metoda pierwotnej podwójnej bariery (punktu wewnętrznego) zwykle wykorzystuje tylko kilkadziesiąt iteracji nawet w przypadku bardzo dużych problemów, ale praca na iterację jest dość długa. Dla porównania różne wersje metody simpleks zwykle wymagają znacznie więcej iteracji, ale praca na iterację jest mniejsza. W praktyce równoległe implementacje metod punktów wewnętrznych wykazały znacznie lepszą wydajność równoległą niż równoległe implementacje metody simpleks.

Mogę wymyślić kilka możliwości:

Jeśli oba algorytmy monotonicznie zmniejszają błąd przy każdej iteracji, może być wskazane, aby niektóre miały więcej, tańszych iteracji, ponieważ daje to więcej możliwości wyboru, kiedy przestać iterować.

Jeśli to praca i czas, ale pamięć , możesz preferować jeśli jest duże. może być nawet wystarczająco duże, abyś wybrał ponieważ użycie pamięci jest bardziej prawdopodobne, że cię tutaj ograniczy.$\mathcal{A}_1$$O(n)$$O(n^k)$$\mathcal{A}_2$$k$$k=2$$\mathcal{A}_2$

Prawdopodobnie dotyczy to tego, czy mówimy o optymalizacji, czy innej klasie problemu iteracyjnego.