Losowe opadanie współrzędnych

Randomizowana (blokowa) metoda zestawiania współrzędnych to algorytm optymalizacyjny spopularyzowany przez Nesterova (2010) oraz Richtárika i Takáča (2011). Pierwszą analizę tej metody w odniesieniu do problemu minimalizacji gładkiej funkcji wypukłej przeprowadził Niestierow (2010). W analizie Niestierowa metodę należy zastosować do kwadratowego zaburzenia pierwotnej funkcji o nieznanym współczynniku skalowania. Richtárik i Takáč (2011) podają granice złożoności iteracji, które tego nie wymagają, tzn. metodę stosuje się bezpośrednio do funkcji celu. Co więcej, uogólniają to ustawienie na problem minimalizacji funkcji złożonej, tj. sumy gładkiej wypukłej i (prawdopodobnie niegładkiej) wypukłej funkcji separowanej blokowo:

${\ Displaystyle F (x) = f (x) + \ Psi (x),}$

gdzie ${\ Displaystyle \ Psi (x) = \ suma _ {i = 1} ^ {n} \ Psi _ {i} (x ^ {(i)}),}$ ${\ Displaystyle x \ w R ^ {N}}$ jest rozkładany na bloki zmiennych/współrzędnych ${\ displaystyle n} :$ ${\ Displaystyle x = (x ^ {(1)}, \ kropki, x ^ {(n)})}$ i ${\ Displaystyle \ Psi _ {1}, \ kropki ,\Psi _{n}}$ są (prostymi) funkcjami wypukłymi.

Przykład (rozkład blokowy): Jeśli ${\ Displaystyle x = (x_ {1}, x_ {2}, \ kropki, x_ {5}) \ in R ^ {5}}$ i ${\ displaystyle n = 3}$ można wybrać ${\ Displaystyle x ^ {(1)} = (x_ {1}, x_ {3}), x ^ {(2)} = (x_ {2}, x_ {5})}$ i ${\ displaystyle x ^ {(3)} = x_ {4}$ }

Przykład (regulatory separowane blokowo):

${\ Displaystyle n = N; \ Psi (x) = \ | x \ | _ {1} = \ suma _ {i = 1} ^ {n} | x_ {i} |}$
${\ Displaystyle N = N_ {1} + N_ {2} + \ kropki + N_ {n}; \ Psi (x) = \ suma _ { ja = 1} ^ {n} \ | x ^ {(i)} \|_ {2}}$ , gdzie ${\ Displaystyle x ^ {(i)} \ w R ^ {N_ {i}}}$ i ${\ displaystyle \|\ cdot \|_ {2}}$ to standardowa norma euklidesowa.

Algorytm

Rozważ problem optymalizacji

{\ Displaystyle \ min _ {x \ w R ^ {n}} f (x),}

gdzie jest funkcją $gładką$ i .

Gładkość: Przez gładkość rozumiemy, co następuje: zakładamy, że gradient $\ displaystyle L_ {1}, L_ {2} ,\kropki,L_{n}}$ ciągły pod względem współrzędnych Lipschitza ze stałymi. $L$ . To znaczy, zakładamy, że

{\ Displaystyle |\ nabla _ {i} f (x + on_ {i}) - \ nabla _ {i} f (x) | \ równoważnik L_ {i} | h |,}

dla wszystkich , gdzie oznacza pochodną cząstkową względem $R ^ {n}} i godz ∈ R {\$ ${\ Displaystyle x \$ $in$ Displaystyle do zmiennej $i)}}$ (

Niestierow, Richtarik i Takac wykazali, że następujący algorytm zbiega się do punktu optymalnego:

  Algorytm  Metoda losowego zmniejszania współrzędnych Wejście:  ${\ displaystyle x_ {0} \ w R ^ {n}}$  // punkt początkowy Dane wyjściowe:  ${\ displaystyle x}$  zestaw  x  : = x_0  dla  k  : = 1, . ..  wybierz  współrzędną  ${\ Displaystyle i \ in \ {1,2, \ kropek, n ​​\}}$  , równomiernie losowo aktualizuj  
     ${\ Displaystyle x ^ {(i)} = x ^ {(i)} - {\ Frac {1} {L_ {i}}} \ nabla _{i}f(x)}$  koniec dla

„←” oznacza przypisanie . Na przykład „ największy ← element ” oznacza, że wartość największego elementu zmienia się na wartość elementu .
„ return ” kończy algorytm i wyświetla następującą wartość.

Współczynnik konwergencji

Ponieważ iteracje tego algorytmu są wektorami losowymi, wynik złożoności wyznaczałby granicę liczby iteracji potrzebnych, aby metoda dała przybliżone rozwiązanie z dużym prawdopodobieństwem. Wykazano, że jeśli ${\ Displaystyle k \ geq {\ Frac {2nR_ {L} (x_ {0})} {\epsilon }}\log \left({\frac {f(x_{0})-f^{*}}{\epsilon \rho }}\right)} ,$ gdzie ${\ Displaystyle R_ {L} (x) = \ max _ {y} \max _{x^{*}\in X^{*}}\{\|yx^{*}\|_{L}:f(y)\równoważnik f(x)\}}$ , $f^{*}$ jest rozwiązaniem optymalnym ( ${\ Displaystyle f ^ {*} = \ min _ {x \ w R ^ {n}} \ {f (x) \}} )$ , $)}$ ${ \ displaystyle \ rho \ in$ $0,1$ to poziom ufności i dokładność celu, a następnie ${\ Displaystyle Prob (f (x_ {k}) -f ^ {*}> \ epsilon) \ równoważnik \ rho}$ .

Przykład dotyczący konkretnej funkcji

Poniższy rysunek pokazuje, jak $w$ się podczas iteracji. Problemem jest

{\ Displaystyle f (x) = {\ tfrac {1} {2}} x ^ {T }\left({\begin{array}{cc}1&0,5\\0,5&1\end{array}}\right)x-\left({\begin{array}{cc}1,5&1,5\end{ array}}\right)x,\quad x_{0}=\left({\begin{array}{cc}0&0\end{array}}\right)^{T}}

Rozszerzenie do ustawiania współrzędnych bloku

Blokowanie kierunków współrzędnych na kierunki współrzędnych blokowych

Można naturalnie rozszerzyć ten algorytm nie tylko na współrzędne, ale na bloki współrzędnych. Załóżmy $,$ mamy . ${\ displaystyle e_ {1} = (1,0,0,0,0) ^ {T}, e_{2}=(0,1,0,0,0)^{T},e_{3}=(0,0,1,0,0)^{T},e_{4}=(0, 0,0,1,0)^{T},e_{5}=(0,0,0,0,1)^{T}}$ ta ma 5 kierunków współrzędnych, konkretnie w którym może się poruszać metoda losowego opadania współrzędnych. Można jednak pogrupować niektóre kierunki współrzędnych w bloki i zamiast tych 5 kierunków współrzędnych możemy mieć 3 kierunki współrzędnych bloku (patrz ilustracja).

Zobacz też