Труды КНЦ вып. 11 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ) вып. 8/2020 (11)

Л( x, y ) = max q(x, y) - min q(x , y) ysY xeX (2) Очевидно, она неотрицательна в силу (1) и обращается в ноль при ( x v) = (x* V*) . Основным результатом описанных далее алгоритмов зеркального спуска (ЗС) является следующее неравенство: при каждой итерации t > 1,выполняется E Л ( xt, y t) < С yjt + 1 t , (3) где E - математическое ожидание, постоянная C выписывается явно как функция параметров решаемой задачи, t - число итераций, приводящих к оценке ( xt , V ) t t седловой точки. Алгоритм ЗС (неадаптивный) записывается следующим образом. 1. Инициализация: при k=0 задаются параметры алгоритма и начальные С0 = 0, TJn = 0 x0 Vn значения двойственных ^ 0 ' n и прямых 0, 0 переменных. т , , k = 1,2,..., t 2. Итерации: реализуются рекуррентно при переменные Ck Vk - + Yk qx (xk-^Vk-1) - qy (xk-l, Vk -1) (4) x,, Vk gradW /?t(^k ) g ra dU . (% ) qx (-,-) qy (-,-) используя стохастические субградиенты \ 'l y ' . 3. Дополнительное усреднение: получить окончательные оценки на итерации t >1 , а именно xt= 1 x^t ~ 1 X^t ^"^t ^^k=\^ k*^k-1 Vt t ^^k=1УkVk-1 ^ k =1 yk ^ k =1 yk (5) Здесь W (•) „ U $(•) и - выпуклые гладкие функции с липшицевыми градиентами и положительными параметрами @ и $ (подробнее см., например, [4]). Отметим, что стохастические субградиенты qx( , ) , qy( , ) должны удовлетворять дополнительным условиям независимости, несмещенности и ограниченности вторых моментов. Показано, что разумно выбирать y k = 1 последовательности k и Pk = А л / k + 1 $k = $ 0 ^ k + 1 . J Н0 Ѵ 1 0 v • (6) они приводят к верхней границе (3) для описанного выше алгоритма ЗС. Ѳ S Параметры ^ 0 и 0 определены в [4]. Адаптивный алгоритм ЗС отличается от описанного выше неадаптивного алгоритма ЗС рекуррентно формируемыми последовательностями вместо (6), а именно: 1 183