Koordináta süllyedés

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. április 16-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A koordináta süllyedés egy olyan optimalizáló algoritmus , amely szekvenciálisan minimalizálja a függvényt koordinátairányok mentén. Az algoritmus minden iterációnál meghatároz egy koordinátaváltozót vagy koordinátablokkot egy koordinátakiválasztási szabály segítségével, majd pontosan vagy megközelítőleg minimalizálja a megfelelő koordináta-hipersíkot, miközben más koordinátákat vagy koordinátablokkokat rögzít. Az aktuális iterációnál a koordinátairány mentén lineáris keresés végezhető a megfelelő lépésméret megtalálásához. A koordináta leszármazás alkalmazható differenciálható esetben és olyan kontextus esetén is, amikor a származékokat nem számítják ki.

Leírás

A koordináta süllyedés azon az elgondoláson alapul, hogy sok változó függvényének minimalizálása történhet úgy, hogy egyszerre csak egy irányban minimalizáljuk, például egyetlen változó optimalizálási feladatot (vagy legalábbis egy egyszerűbb feladatot) megoldunk egy hurokban [1] . A ciklikus koordináta süllyedés legegyszerűbb esetben az algoritmus iterációnként egyet hajt végre a koordináta irányain, és egyszerre minimalizálja a célfüggvényt minden koordinátán. Vagyis a kezdeti értékekből kiindulva

,

iteráció határozza meg az optimalizálási problémák iteratív megoldásával egy változóból

[2]

minden vektorváltozóhoz 1 - től .

Így az algoritmus a függvény lokális minimumának kezdeti közelítésével indul, és iteratív módon kap egy vektorsorozatot .

Ha minden iterációnál lineáris keresést végzünk , azt kapjuk

Kimutatható, hogy ennek a sorozatnak a legmeredekebb ereszkedési módszeréhez hasonló konvergenciatulajdonságai vannak. A célfüggvény javulásának hiánya a következő lineáris keresési ciklus után a koordináta irányok mentén azt jelzi, hogy egy stacionárius pontot értünk el.

Az algoritmus működését az alábbiakban mutatjuk be.

Differenciálható eset

Az F függvény folytonos differenciálhatósága esetén a koordináta süllyedési algoritmus a következőképpen foglalható össze : [1] :

A lépést sokféleképpen meg lehet választani, például egy minimalizálási feladat megoldásával (vagyis az F kivételével fix változókkal minimalizálva ), vagy hagyományos lineáris kereséssel [1] .

Korlátozások

A koordináta süllyedésnek két problémája van. Az egyik a több változó nem sima függvényének jelenléte. Az ábrán látható, hogy a koordináta süllyedési iterációk nem stacionárius pontba futhatnak, ha a függvény szintgörbéi nem simák. Tegyük fel, hogy az algoritmus a (-2, -2) pontban kötött ki . Ezután a tengelyekkel párhuzamos két irány van, amelyek mentén meg kell tenni a következő lépést. Piros nyilakkal vannak ábrázolva. E két irányban minden lépés azonban a függvény értékének növekedéséhez vezet (feltételezzük, hogy a minimalizálási probléma megoldódik), így az algoritmus egyetlen lépést sem tesz meg, bár két lépés együttesen a algoritmus közelebb kerül az optimumhoz. Bár ez a példa azt mutatja, hogy a koordináta süllyedés nem feltétlenül vezet optimális megoldáshoz, normális körülmények között lehetséges formális konvergencia kimutatása [3] .

Egy másik probléma a párhuzamosítás nehézsége. Mivel a koordináta-süllyedés természete az irányok közötti hurok, és minden koordinátairány mentén minimalizálja a függvényt, a koordináta-süllyedés nem nyilvánvaló jelölt párhuzamosításra. A legújabb kutatások kimutatták, hogy a párhuzamosítás néhány speciális trükkel használható koordináta-leszálláshoz [4] [5] [6] .

Alkalmazások

A koordináta ereszkedési algoritmusok egyszerűségük miatt népszerűek, de ugyanez a tulajdonság arra ösztönzi a kutatókat, hogy figyelmen kívül hagyják őket az érdekesebb (összetettebb) módszerek javára [1] . A koordináta süllyedés optimalizálás korai alkalmazásai a számítógépes tomográfia területén voltak [7] , ahol a módszer gyors konvergenciát mutatott [8] , és többrétegű helikális komputertomográfiai képek rekonstruálására használták [9] . A ciklikus koordináta süllyedés algoritmusát a fehérjeszerkezet előrejelzésében alkalmazták [10] . Ezen túlmenően, a gépi tanulás nagyszabású problémáinak megjelenésével egyre nőtt az érdeklődés a koordináta süllyedésének alkalmazása iránt , ahol a koordináta-leszállás versenyképesnek bizonyult más módszerekkel szemben, ha olyan problémákra alkalmazzák, mint például a lineáris támogató vektor gépi tanulás . 11] (lásd LIBLINEAR ) és nemnegatív mátrixbővítés [12] . A módszerek vonzóak olyan problémák esetén, ahol a gradiens számítás nem kivitelezhető, talán azért, mert a szükséges adatok számítógépes hálózatokon vannak elosztva [13] .

Lásd még

Jegyzetek

  1. ↑ 1 2 3 4 Wright, 2015 , p. 3–34.
  2. ↑ Archivált másolat . Letöltve: 2022. február 6. Az eredetiből archiválva : 2022. február 6..
  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. ↑ Neszterov, 2012 , p. 341–362.

Irodalom