Wysiłek obliczeniowy algorytmów

9

Rozważ ściśle wypukły, nieograniczony problem optymalizacjiO:=minxRnf(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}xoptx0xopt.xϵO

||xxopt||2||x0xopt||2ϵ.

Załóżmy, że istnieją dwa iteracyjne algorytmy A1 i A2 aby znaleźć rozwiązanie ϵ close dla O o następujących właściwościach:

  1. Dla dowolnego ϵ>0, całkowity wysiłek obliczeniowy, tj. Wysiłek wymagany na iterację × całkowitą liczbę iteracji, w celu znalezienia rozwiązania ϵ close jest taki sam dla obu algorytmów.
  2. Wysiłek na iterację dla A1 wynosi O(n), powiedzmy, podczas gdy dla A2 jest O(n2).

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

Suresh
źródło

Odpowiedzi:

14

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.

Brian Borchers
źródło
7

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.A1O(n)O(nk)A2kk=2A2

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

Bill Barth
źródło
Zgadzam się z tobą w kwestii ograniczeń przestrzeni. Zastanawiałem się, czy można uzasadnić sprawę na podstawie złożoności czasu.
Suresh