Coordonarea coborârii

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 16 aprilie 2022; verificarea necesită 1 editare .

Coborârea coordonatelor este un algoritm de optimizare care minimizează secvențial o funcție de-a lungul direcțiilor de coordonate. La fiecare iterație, algoritmul determină o variabilă de coordonate sau un bloc de coordonate prin intermediul unei reguli de selecție a coordonatelor, apoi minimizează exact sau aproximativ peste hiperplanul de coordonate corespunzător în timp ce fixează alte coordonate sau blocuri de coordonate. La iterația curentă, o căutare liniară de-a lungul direcției de coordonate poate fi efectuată pentru a găsi o dimensiune adecvată a pasului. Coborarea coordonatelor poate fi aplicată atât în ​​cazul diferențiabil, cât și în cazul contextului când derivatele nu sunt calculate.

Descriere

Coborarea coordonatelor se bazează pe ideea că minimizarea unei funcții a mai multor variabile se poate face prin minimizarea de-a lungul unei direcții la un moment dat, de exemplu prin rezolvarea unei singure probleme de optimizare a variabilei (sau cel puțin a unei probleme mai simple) într-o buclă [1] . În cel mai simplu caz de coborare ciclică a coordonatelor , algoritmul iterează peste direcțiile coordonatelor câte una pe iterație, minimizând funcția obiectiv peste fiecare coordonată la un moment dat. Adică pornind de la valorile inițiale

,

iterația determină din prin rezolvarea iterativă a problemelor de optimizare dintr-o variabilă

[2]

pentru fiecare variabilă vectorială de la 1 la .

Astfel, algoritmul începe cu o aproximare inițială a minimului local al funcției și obține o succesiune de vectori în mod iterativ.

Când se efectuează o căutare liniară la fiecare iterație, obținem

Se poate arăta că această secvență are proprietăți de convergență similare metodei de coborâre abruptă. Lipsa de îmbunătățire a funcției obiectiv după următorul ciclu de căutări liniare de-a lungul direcțiilor de coordonate indică faptul că a fost atins un punct staționar.

Funcționarea algoritmului este prezentată mai jos.

Caz diferențiabil

În cazul diferențierii continue a funcției F , algoritmul de coborare a coordonatelor poate fi rezumat ca [1] :

Pasul poate fi ales în mai multe moduri, de exemplu, prin rezolvarea unei probleme de minimizare (adică prin minimizarea F cu variabile fixe cu excepția lui ), sau prin căutare liniară tradițională [1] .

Restricții

Coborârea coordonată are două probleme. Una dintre ele este prezența unei funcții neregulate a mai multor variabile. Figura arată că iterațiile de coborâre de coordonate pot rula într-un punct non-staționar dacă curbele de nivel ale funcției nu sunt netede. Să presupunem că algoritmul a ajuns în punctul (-2, -2) . Apoi există două direcții paralele cu axele de-a lungul cărora ar trebui făcut următorul pas. Sunt afișate cu săgeți roșii. Cu toate acestea, orice pas în aceste două direcții va duce la o creștere a valorii funcției (se presupune că problema de minimizare este rezolvată), astfel încât algoritmul nu va face un singur pas, deși doi pași împreună ar aduce algoritm mai aproape de optim. Deși acest exemplu arată că coborârea coordonatelor nu conduce neapărat la o soluție optimă, este posibil să se arate convergența formală în condiții normale [3] .

O altă problemă este dificultatea paralelizării. Deoarece natura coborârii coordonatelor este de a bucla peste direcții și de a minimiza o funcție de-a lungul fiecărei direcții de coordonate, coborârea de coordonate nu este un candidat evident pentru paralelizare. Cercetări recente au arătat că paralelizarea poate fi folosită pentru coborârea coordonată cu unele trucuri speciale [4] [5] [6] .

Aplicații

Algoritmii de coborare în coordonate sunt populari pentru simplitatea lor, dar aceeași proprietate încurajează cercetătorii să-i ignore în favoarea unor metode mai interesante (mai complexe) [1] . Aplicațiile timpurii ale optimizării coborârii coordonate au fost în domeniul tomografiei computerizate [7] , unde metoda a arătat o convergență rapidă [8] și a fost folosită pentru a reconstrui imagini de tomografie computerizată elicoidal multistrat [9] . Algoritmul de coborare a coordonatelor ciclice a fost aplicat în predicția structurii proteinei [10] . Mai mult, a existat un interes din ce în ce mai mare pentru aplicarea coborârii coordonate odată cu apariția problemelor la scară largă în învățarea automată , în care coborârea coordonatelor s-a dovedit a fi competitivă cu alte metode atunci când este aplicată la probleme precum învățarea automată a vectorului de suport liniar . 11] (vezi LIBLINEAR ) și extinderea matricei nenegative [12] . Metodele sunt atractive pentru problemele în care calculul gradientului nu este fezabil, poate pentru că datele necesare sunt distribuite prin rețele de calculatoare [13] .

Vezi și

Note

  1. ↑ 1 2 3 4 Wright, 2015 , p. 3–34.
  2. ↑ Copie arhivată . Preluat la 6 februarie 2022. Arhivat din original la 6 februarie 2022.
  3. ↑ Spall, 2012 , p. 187–208.
  4. ↑ Zheng, Saquib, Sauer, Bouman, 2000 , p. 1745–1759
  5. ↑ Fessler, Ficaro, Clinthorne, Lange, 1997 , p. 166–175.
  6. ↑ Wang, Sabne, Kisner, 2016 , p. 2:1–2:12.
  7. ↑ Sauer, Bouman, 1993 , p. 534–548.
  8. ↑ Yu, Thibault, Bouman, Sauer, 2011 , p. 161–175.
  9. ↑ Thibault, Sauer, Bouman, Hsieh, 2007 , p. 4526–4544.
  10. ↑ Canutescu, Dunbrack, 2003 , p. 963–72.
  11. ↑ Hsieh, Chang, Lin, Keerthi, 2008 , p. 408.
  12. ↑ Hsieh, Dhillon, 2011 , p. 1064.
  13. ↑ Nesterov, 2012 , p. 341–362.

Literatură