Про швидкiсть збiжностi субградiєнтих методiв з кроком Поляка

Анотація

Розглядаються субградiєнтнi методи (метод А та метод В) для знаходження точки мiнiмуму опуклої функцiї, якщо вiдоме її мiнiмальне значення. Обидва методи використовують вiдомий крок Поляка, який залежить вiд скалярного параметра m ≥ 1 i гарантує монотонне зменшення вiдстанi до точки мiнiмуму. Якщо m = 1, то методи А та В застосовнi для довiльної опуклої функцiї. Параметр m > 1 дозволяє врахувати спецiальнi класи опуклих функцiй – опуклi квадратичнi функцiї (m = 2), диференцiйовнi однорiднi функцiї з показником σ (m = σ) та iншi. Для обох методiв доведено теореми про їх збiжнiсть зi швидкiстю O 1/ √ k для довiльної опуклої функцiї та збiжнiсть зi швидкiстю геометричної прогресiї для опуклої функцiї з гострим мiнiмумом. Метод А є субградiєнтним методом з кроком Поляка у вихiдному просторi змiнних. Параметр m = 1 вiдповiдає класичному кроку Поляка для довiльної опуклої функцiї. Параметр m = 2 можна використовувати при мiнiмiзацiї квадратичних функцiй, для яких величина кроку Поляка збiльшується в два рази порiвняно з класичним кроком Поляка при m = 1. Для одновимiрних квадратичних функцiй метод А знаходить точку мiнiмуму за один крок з довiльної стартової точки, що вiдповiдає однiй iтерацiї методу Ньютона. Доведення теорем про швидкiсть збiжностi методу А базується на характеристиках опуклої функцiї в вихiдному просторi змiнних, серед яких ключову роль вiдiграє константа c1, яка обмежує норму субградiєнта. Метод В – субградiєнтний метод з перетворенням простору, де крок Поляка обчислюється у перетвореному лiнiйним оператором просторi змiнних. Метод визначається невиродженою матрицею B. Параметр m = 1 вiдповiдає класичному кроку Поляка для довiльної опуклої функцiї у перетвореному просторi змiнних. Якщо m = 2, то для одновимiрної квадратичної функцiї метод В знаходить точку мiнiмуму за один крок при довiльних матрицi B та стартовiй точцi. Доведення теорем про швидкiсть збiжностi методу B базуються на характеристиках функцiї в перетвореному просторi змiнних, аналогiчних характеристикам функцiй у початковому просторi для методу А.