Запропоновано декілька адаптивних алгоритмічних методів, які можна застосувати до завдань негладкою опуклою оптимізації. Перший з них заснований на введенні спеціальної штучної неточності, і для його реалізації запропоновано відповідний аналог концепції абстрактної неточною моделі цільової функції. Для цієї концепції запропоновані аналоги градиентного методу, а також швидкого градиентного методу з адаптивною налаштуванням деяких параметрів неточною моделі, і отримана оцінка якості знайденого рішення. Показано, що для негладких задач можливо модифікувати запропоновані методи так, щоб гарантовано виконувалася збіжність по функції зі швидкістю, близькою до оптимальної. Введена аналогічна концепція неточною моделі для оператора поля варіаційного нерівності, а також для седловой завдання і приведена оцінка швидкості збіжності відповідного адаптивного варіанту проксимального дзеркального методу. Запропоновано аналоги субградієнтного схем з перемиканнями для задач опуклою оптимізації з обмеженнями. При цьому розглянуті припущення, пов'язані з нещодавно запропонованим умовою відносної ліпшіцевості. Це дозволило виписати оцінку якості рішення з відносною точністю для завдання мінімізації однорідного опуклого функціоналу при досить загальних припущеннях.

Анотація наукової статті з математики, автор наукової роботи - Стонякін Ф. З.


Adaptive gradient methods for some classes of nonsmooth optimization problems

We propose several adaptive algorithmic methods for problems of non-smooth convex optimization. The first method is based on a special artificial inexactness. For its implementation the corresponding analogue of the concept of an abstract inexact model of the objective functional is proposed. For this concept, analogues of gradient and fast gradient methods with adaptive tuning of some parameters of this model are proposed and an assessment of the quality of the solution is obtained. It is shown that it is possible for nonsmooth problems to modify the proposed method to guarantee the convergence in the function with a close to optimal rate. A similar concept of an inexact model is introduced for variational inequalities and saddle point problems. Estimate of the convergence rate of the corresponding adaptive version of the proximal mirror method is presented. Analogues of switching subgradient schemes are proposed for convex programming problems. In this case, assumptions close to the recently proposed condition of the relative Lipschitz continuity are considered, which allows us to obtain an estimate of the quality of the solution with relative accuracy for the problem of minimizing a homogeneous convex functional using fairly general assumptions.


Область наук:

  • Математика

  • Рік видавництва: 2020


    Журнал: Праці Московського фізико-технічного інституту


    Наукова стаття на тему 'АДАПТИВНІ градієнтних методів ДЛЯ ДЕЯКИХ КЛАСІВ ЗАВДАНЬ негладку ОПТИМІЗАЦІЇ'

    Текст наукової роботи на тему «АДАПТИВНІ градієнтних методів ДЛЯ ДЕЯКИХ КЛАСІВ ЗАВДАНЬ негладку ОПТИМІЗАЦІЇ»

    ?УДК 519.85

    Ф. С. Стонякін

    Кримський федеральний університет ім. В. І. Вернадського Московський фізико-технічний інститут (національний дослідницький університет)

    Адаптивні градієнтні методи для деяких класів задач негладкою оптимізації

    Запропоновано декілька адаптивних алгоритмічних методів, які можна застосувати до завдань негладкою опуклою оптимізації. Перший з них заснований на введенні спеціальної штучної неточності, і для його реалізації запропоновано відповідний аналог концепції абстрактної неточною моделі цільової функції. Для цієї концепції запропоновані аналоги градієнтного методу, а також швидкого градиентного методу з адаптивною налаштуванням деяких параметрів неточною моделі, і отримана оцінка якості знайденого рішення. Показано, що для негладких задач можливо модифікувати запропоновані методи так, щоб гарантовано виконувалася збіжність по функції зі швидкістю, близькою до оптимальної. Введена аналогічна концепція неточною моделі для оператора поля варіаційного нерівності, а також для седловой завдання і приведена оцінка швидкості збіжності відповідного адаптивного варіанту проксимального дзеркального методу. Запропоновано аналоги субградієнтного схем з перемиканнями для задач опуклою оптимізації з обмеженнями. При цьому розглянуті припущення, пов'язані з нещодавно запропонованим умовою відносної ліпшіцевості. Це дозволило виписати оцінку якості рішення з відносною точністю для завдання мінімізації однорідного опуклого функціоналу при досить загальних припущеннях.

    Ключові слова: градієнтний метод, швидкий градієнтний метод, адаптивний метод, Ліпшиця градієнт, негладка оптимізація, дзеркальний спуск, відносна ліпшіцевость, відносна точність.

    F. S. Stony akin

    V. I. Vernadsky Crimean Federal University Moscow Institute of Physics and Technology

    Adaptive gradient methods for some classes of nonsmooth

    optimization problems

    We propose several adaptive algorithmic methods for problems of non-smooth convex optimization. The first method is based on a special artificial inexactness. For its implementation the corresponding analogue of the concept of an abstract inexact model of the objective functional is proposed. For this concept, analogues of gradient and fast gradient methods with adaptive tuning of some parameters of this model are proposed and an assessment of the quality of the solution is obtained. It is shown that it is possible for nonsmooth problems to modify the proposed method to guarantee the convergence in the function with a close to optimal rate. A similar concept of an inexact model is introduced for variational inequalities and saddle point problems. Estimate of the convergence rate of the corresponding adaptive version of the proximal mirror method is presented. Analogues of switching subgradient schemes are proposed for convex programming problems. In this case, assumptions close to the recently proposed condition of the relative Lipschitz continuity are considered, which allows us to obtain an estimate of the quality of the solution with relative accuracy for the problem of minimizing a homogeneous convex functional using fairly general assumptions.

    © Стонякін Ф. С., 2020

    (С) Федеральне державне автономне освітня установа вищої освіти

    «Московський фізико-технічний інститут (національний дослідницький університет)», 2020

    Key words: gradient method, fast gradient method, adaptive method, Lipschitz continuous gradient, nonsmooth optimization, mirror descent, relative Lipschitz continuity, relative accuracy.

    Вступ

    У багатьох прикладних задачах виникає необхідність відповідних алгоритмічних методів для задач негладкою опуклою оптимізації. Однак оцінки ефективності таких процедур в разі великої розмірності змінних вельми песимістичні. Так, наприклад, е-точне рішення по функції завдання опуклою негладкою оптимізації можливо досягти за 0 (е-2) звернень до підпрограми знаходження (суб) градієнта, і в загальному випадку така оцінка не улучшаема [1]. Для гладких завдань оцінки ефективності вище, що призводить до природної ідеї для негладких задач обґрунтувати можливість використання якого-небудь наближення оптимізаційної моделі до гладкому нагоди. Цю ідею, зокрема, реалізують так звані універсальні методи, дослідження яких було покладено початок в роботі [2]. Універсальні градієнтні методи засновані на побудові для задач опуклою оптимізації з гёльдеровим (суб) градієнтом цільового функціоналу аналога стандартної квадратичної інтерполяції з штучно введеної похибкою. Універсальність методу при цьому розуміється як можливість адаптивної настройки при роботі методу на оптимальний в деякому сенсі рівень гладкості завдання і величину, відповідну константі Гельдера ьі (суб) градієнта цільового функціонала. Виявляється, що можливість такого налаштування може дозволити експериментально для деяких завдань поліпшити швидкість збіжності в порівнянні з оптимальними теоретичними оцінками [2].

    Штучну неточність для негладких задач можна вводити по-різному [3,4]. При цьому природно виникає проблема опису впливу похибок завдання цільового функціоналу і градієнта на оцінки швидкості збіжності методів. Для градієнтних методів відомий підхід до цієї проблеми, заснований на недавно запропонованої концепції неточного оракула [1,6]. Відомо, що для неускоренного градієнтних методів в оцінках швидкості збіжності не відбувається накопичення величин, пов'язаних з похибками. Однак при цьому для оптимального за відсутності похибок на класі гладких опуклих задач швидкого градиентного методу в підсумковій оцінці швидкості збіжності величини похибок можуть накопичуватися. Концепція неточного оракула була узагальнена в [2,8], де були введені поняття (5, Ь) -моделі і (5, Ь, ^) - моделі цільової функції для задач оптимізації. Суть даних узагальнень в заміні (V / (х), у - х) деякої абстрактної опуклою по першій змінної функцією ф (у, х), що дозволяє розглядати ширший клас завдань [8].

    Різним методам градиентного типу присвячені все нові сучасні роботи [2,3,8-10]. Зокрема, нещодавно в [9] введені умови відносної гладкості оптимизируемого функціоналу, які передбачають заміну умови ліпшіцевості градієнта на ослаблений варіант:

    / (У) < / (Х) + (Vf (х), у - х) + IV (у, х), (1)

    де V (у, х) - широко використовуваний в оптимізації аналог відстані між точками х і у, який називають дивергенцией Брегмана. Зазвичай дивергенція Брегмана вводиться на базі допоміжної 1-сильно опуклою функції й (породжує відстані), що диференціюється в усіх точках опуклого замкнутого безлічі Q:

    V (у, х) = ї (у) - й (х) - (Vй (х), у - х) Ух, у е Я, (2)

    Де (•, •) - скалярний добуток в Мга. Зокрема, для стандартної евклідової норми || • Ц2 і відстані в Мга можна вважати, що V (у, х) = ї (у - х) = | \\ у - х \\ 2, для довільних х, у е Я- Однак часто виникає необхідність використовувати і неевклидова

    норми. Більш того, розглянуте в [3,9] умова відносної гладкості передбачає лише опуклість (але не сильну опуклість) породжує функції д ,. Як показано в [3], концепція відносної гладкості дозволяє застосувати варіант градиентного методу для деяких завдань, які раніше вирішувалися лише за допомогою методів внутрішньої точки. Зокрема, мова йде про відому завданню побудови оптимального еліпсоїда, що покриває заданий набір точок. Це завдання, зокрема, представляє інтерес для статистики та аналізу даних. Відзначимо в цьому зв'язку також запропонований недавно в [12] підхід до завдань негладкою оптимізації, пов'язаний з релаксацією умови Ліпшиця, яка передбачає заміну обмеженості норми субградіента «V / (ж) У * ^ Mf так званої відносної ліпшіцевостью:

    «V / ми.« Е Я.У = * |

    При цьому породжує функція й не обов'язково сильно опукла. В роботі [12] запропоновано детермінований і стохастичний алгоритми дзеркального спуску для задачі мінімізації опуклого щодо ліпшіцева цільового функціоналу. Відзначимо також, що в [13] показана оптимальність дзеркального спуску для задач математичного програмування з квазівипуклимі диференційовними гёльдеровимі цільовими функціоналами і опуклими ліпшіцевимі функціоналами обмежень.

    Пропонована стаття присвячена в основному розвитку згаданих вище ідей. У першому розділі запропонована модифікація концепції (6,?) - моделі цільової функції зі змінною неточністю, яка дозволяє врахувати можливість неточного завдання не тільки значення цільової функції, а й самої моделі. Зокрема, для стандартної моделі ф (у, х) = (V / (х), у - х) описується ситуація похибки завдання цільового функціоналу /, а також похибки завдання (суб) градієнта V /.

    У перших трьох розділах роботи ми виділяємо (в модельній спільності за аналогією з [2]) клас задач, для яких (V / - обурений значення (суб) градієнта V /) вірно наступне нерівність з параметрами 61,62,7, А ^ 0 :

    / (Х) + (VI (х), у - х) - 62 - 7 «У - я || < / (У) <

    (3)

    < / (Х) + (V / (х), У - х) + ^ «у - ж || 2 + А" у - ж || +? 1 ЧХ, у е д.

    Сенс такого узагальнення полягає в тому, що можливі різні значення параметрів 7 і А в (3) і вплив величин 61 ж А на підсумкове якість рішення може бути зменшено. випадок ^ > 0 докладніше розглянутий в [4], а в цій роботі ми вважаємо 7 = 0. Це припущення цілком природно, якщо розглядати А як штучну

    А

    / (Х) + (V / (х), у - х) < f (у) < / (Х) + (V / (х), у - х) + ^ Іу - я || 2 + А "у - Ж || (4)

    цілком можна розглядати як оцінку стрибків субдіфференціалов / уздовж всіляких векторних відрізків [х; у] [3]. Нескладно зрозуміти, що якщо / в (4) задовольняє умові Ліпшиця з константою М > 0, то А ^ 2М. Відзначимо, що можлива ситуація, коли А істотно менше М [3]. Схожі на (4) умови розглядалися в [6,14] для випадку, коли / представимо у вигляді суми гладкого і негладкого цільового функціоналу. У даній роботі розглянуто більш широкий клас цільових функціоналів, які не обов'язково представимо у вигляді суми гладкого і негладкого доданків. У підсумку запропонована загальна концепція неточною моделі цільової функції, яка могла б описати всі зазначені вище ситуації. Далі в розділі 4 введена аналогічна концепція неточною моделі для оператора поля варіаційного нерівності, а також для седловой завдання. Виписано оцінки швидкості збіжності відповідного адаптивного варіанту проксимального дзеркального методу. В останньому розділі статті розглянуті аналоги субградієнтного схем з перемиканнями для задач опуклою оптимізації з обмеженнями. при

    цьому розглянуті припущення, близькі до недавно запропонованого умові відносної ліпшіцевості [12], що дозволило отримати оцінку якості рішення з відносною точністю для завдання мінімізації однорідного опуклого функціоналу при досить загальних припущеннях.

    Робота складається з вступу, п'яти основних розділів і укладення.

    У розділі 1 узагальнено раніше запропоноване поняття (8,?) - моделі цільової функції [2] в запитаної точці і введена концепція (8, А,?) - моделі функції (визначення 1). Введена також більш загальна концепція (8, А, Ь, ^) - моделі цільової функції, яку можна, зокрема, застосувати на класі гладких сильно опуклих функціоналів. Запропоновано аналог градиентного методу (алгоритм 1) градиентного типу з адаптивною налаштуванням параметрів неточності цієї моделі.

    У розділі 2 запропонований варіант швидкого градиентного методу (алгоритм 2) для задач опуклою мінімізації з адаптивним вибором кроку і адаптивної налаштуванням на величини параметрів (8, А,?) - моделі і отримана оцінка якості знайденого рішення.

    Розділ 3 присвячений спеціального класу задач опуклою негладкою оптимізації, до яких може бути застосована концепція визначення 1 (8 = 0 А > 0). Показано, що для таких завдань можливе модифікувати алгоритм 2 так, щоб гарантовано досягалося е-точне рішення задачі мінімізації / за

    звернень до (суб) градієнту цільового функціоналу. По суті, отриманий деякий аналог результату ([6], п. 4.7.2), проте оптимізується функціонал вже не обов'язково має вигляд суми гладкого і негладкого доданка і розглянута модельна спільність. Відзначимо, що при цьому для адаптивного прискореного методу оцінка може збільшитися на деякий логарифмический множник виду 0 (^ 2 (е-3)), для адаптивного неускоренного - на множник виду 0 (log2 (? - 1)). Відзначимо також, що параметр А можна розуміти і як величину, яка відповідає неточно заданому (суб) градієнту.

    Далі в розділі 4 показано, як можна вводити аналог концепції (8, А,?) - моделі оптимізується функціоналу, але вже для варіаційних нерівностей і сідлових завдань.

    Нарешті, в останньому розділі 5 обговорюються альтернативні підходи до алгоритмическим схемами для задач негладкою оптимізації з ліпшіцевимі опуклими функціональними обмеженнями. Запропоновано адаптивний метод із заміною звичайного умови Ліпшиця на деякі його аналоги. Розглянуто умова, близьке до відносної ліпшіцевості [12], яка не передбачає 1-сильній опуклості дивергенції Брегмана. Це дозволило запропонувати метод, який гарантує досягнення якості наближеного рішення з фіксованою відносною точністю для завдання мінімізації опуклого однорідного цільового функціоналу / в разі, коли субдиференціал / в нульовій точці може не містити 0 як внутрішню точку.

    Усюди далі через || • || позначається норма в просторі Мга, а терез || • || * Норма в неоднозначному просторі.

    1. Концепція (8, А, Ь) -моделі функції в запитаної точці і оцінка швидкості збіжності для градієнтного методу

    Введемо анонсований вище аналог поняття (5, А,?) - моделі цільової функції, кото-

    А

    кові гладкими цільовими функціоналами [3].

    Визначення 1. Будемо говорити, що / допускає (5, А, Ь) -модель ф в точці х е Я, якщо для деякої опуклою по першій змінної функції ф (у, х), такий, що при в сяком х ф (х , х) = 0, буде вірно нерівність

    / (Х) + ф (у, х) - 81 < Д (х) + ф (у, х) < / (У) < (Х) + ф (у, х) + 82 + А Цу - ж || + IV (у, х) (5)

    для довільних х, у е Я при фіксованих д,? 1,82 ^ 0 і /<5 (х) е [/ (х) - 5, / (ж)] Ух е Я-

    Усюди далі будемо вважати, що 5 = = 52, а також? § (х) е [? '(Х) - 5, f (ж)]. Відзначимо, що запропонована концепція є модифікація введеного в [4] поняття (5, А,?) - моделі цільового функціоналу в запитуваної точці.

    Зауваження 1. Для неускоренного методу можливо замінити ліве нерівність в (5) на ослаблений варіант

    / (Х *) > / (Х) + ф (х *, х) - 5, (6)

    де х * - найближче до х вирішення завдання мінімізації / с точки зору дивергенції Брегмана V (х *, х). Нерівність (6) буде, зокрема, вірно для завдання мінімізації квазівипуклой цільової функції при досить малій величині похибки градієнта.

    Можна також ввести і аналог концепції (5, Ь, ^) - оракула в оптимізації зі змінною неточністю. при у > 0 ця концепція дозволяє обгрунтувати швидкість збіжності пропонованого нами методу, близьку до лінійної.

    Визначення 2. Будемо вважати, що / допускає (5, А, Ь, у) -модель ф (у, х), якщо для довільних х, у е Я вірно

    / (У) < / Г (х) + Ф (у, х) + АЦУ - ж || + 5 + IV (у, х), (7)

    а також

    f (х) - 5 + ф (х *, х) + уу (х *, х) ^ / г (х) + ф (х *, х) + уу (х *, х) ^} (х *) , (8)

    де х * - найближче до х вирішення завдання мінімізації / с точки зору дивергенції Брегмана V (х *, х). Нерівність (8) буде, зокрема, вірно для завдання мінімізації сильно квазівипуклой цільової функції [10] при досить малій величині похибки градієнта.

    Приклад 1. Як приклад по аналогії з прикладом 1 з [4] відзначимо завдання сильно опуклою композитної оптимізації / (х) = д (х) + до (х) ^ шт, де д - гладка опукла функція, а до - опукла НЕ обов'язково гладка функція простої структури. якщо при

    це для градієнта Vg задано його наближення Vд: покласти

    ф (у, х) = (Vд (х), у - х) + до (у) - до (х)

    V д (х) - Vg (x)

    і в разі завзято опуклості д або до буде вірно (7).

    ^ А, то можна

    Для завдання мінімізації функціонала, що допускає (5, А, Ь, ^) - модель в довільній запитаної точці, запропонуємо такий метод.

    Алгоритм 1 Адаптивний градієнтний метод для функцій, що допускають (5, A, L, ц) -модель в запитаної точці.

    Require: х0? Q - початкова точка, V (х *, х °) ^ R2, параметри Lo, Ao, So > 0: 2ц. < Lo < 2L, Ao < 2A, 5o < 25. 1: Lk + x: = Lk / 2, Ak + i: = 5k + i: = 2: xk + l: = axgmin ^ (x, xk) + Lk + lV (x, xk)}.

    repeat

    xEq

    3

    4

    5

    6

    7

    8 9

    Ensure: yk + l: = arg min f (xi + l).

    i = o, ..., k

    if fs (xk + l) < fs (xk) + ф (xk + l, xk) + Lk + lV (xk + l, xk) + 5k + l + Ak + l \\ xk + l - xk || then

    k: = k + 1 і виконання п. 1. else

    Lk + l: = 2Lk + l 5k + l: = 2 | 5k + l; Ak + l: = 2 | Ak + l і виконання п. 2. end if until k > N

    до

    Усюди далі домовимося вважати, що Л а1 = 1 для деякої числової последова-

    1 = до + 1

    ності а1. справедлива наступна

    Теорема 1. Нехай має (5, А, Ь, ц) -модель в кожній точці х € Тоді, після до ітерацій справедливо нерівність

    f (yk + l) - f И < 1

    k k

    S ^ п 1 - ?

    __

    i = o Li + 1 L

    k 7 k 5 + Si + l + A + l \ xi + l - xi

    * I iiii - & "+? П i -i

    o o = + l

    Відзначимо, що допоміжна завдання п. 2 лістингу алгоритму 1 вирішується не більше

    2А Ап

    З, 2L 25 2A1 2к + maW log2 -, log2 -, log2 д | (9)

    раз.

    Доведення. Введемо позначення: 5к + 1: = 5к + 1 + Ак + 1 || хк + 1 - хк ||. Шелі до ітерацій алгоритму 1 отримуємо

    0 ^ ф (х, хк) - ф (хк + 1, хк) + Ьк + 1У (х, хк) - Ьк + 1 V (х, хк + 1) - Ьк + 1У (хк + 1, хк), звідки

    Ьк + 1У (х, хк + 1) < ф (х, хк) - ф (хк + \ хк) + Ьк + 1 V (х, хк) - Ьк + 1У (хк + 1, хк). (10) Відповідно до нерівності (7):

    -Ьк + 1У (хк + \ хк) < 5к + 1 -? З (хк + 1) +? З (хк) + ф (хк + 1, хк).

    Застосовуючи тепер (10), отримуємо

    Ьк + 1У (х, хк + 1) < ^ + 1 - / (хк + 1) + (хк) + ф (х, хк) + Ьк + 1У (х, хк) + 5. (11)

    Нехай х = ж *. Тоді, враховуючи (8), маємо fs (xkJ + ф (x *, xk) ^ f (х *) - ^ V (x *, xk). Застосуємо це не]; Далі,

    це нерівність до (11): Lk + lV (х *, xk + l) ^ S + 5k + l + f (х *) - f (xk + l) + (Lk + l - y) V (x *, xk).

    V (x *, xk + l) < f (x *) - f ^ + 5 + 5k + l + (l -JL.) V (x *, xk) <

    V Lk + l J

    Jk + l ^ k + l

    X

    < (ХШ) + (/ (х.) -? (Х *) \ + Ц' »+

    V Ьк + 1 / у 'Ьк + 1

    Lk + 1 Ьк

    Л - "Ц + Л - Л - А) у (х.<хк-1) <

    Ьк \ Ьк + 1 / \ Ьк + 1 / V Ьк /

    <± п (1 - {- У ± п О-Ь ^) + п (! - 7 ^ у (х'-х0)-

    ?= 0? +1 .7 = "+ ^ 3 '? = 0? +1 ^ 7? = 0 4? + 1У

    З урахуванням ук + 1 = агдттг = про ~ к / (ХГ + 1) і У (х *, хк + 1) ^ 0 маємо / (ук + 1) - / (х *) ^

    1§ к / \ к ^ .р * к /

    I ТТ / 1 V 0л, ^ ^ + ^? + 1 ТТ Л V

    , ,-I п (1 - у (х., Х0) + Е П I1 -).

    ? 1 + Т п (1 -? -) V «4 - = 0? +1 |» = '+' 4

    ?= 0 1 + 1 j = i + 1y J '

    Оцінка (9) обгрунтовується аналогічно п. 2 доведення теореми 2.1 з [4].

    Зауваження 2. Оцінка (9) показує, що в середньому трудомісткість ітерації запропонованого адаптивного алгоритму перевищує трудомісткість неадаптивного методу не більше ніж в постійне число раз. Відзначимо також, що при к = 0,1,2, ... Ьк + 1 ^ 2СЬ, С = тах 11, Щ, Ц}.

    Слідство 1. При V = 0 отримана оцінка, якості рішення приймає, вид

    Л ^ 1) -! И < + (Е ^ У 'Е * +, + А х? П +, ^ (12)

    - ^ \ г = 0? +1 /? = 0? +1

    +1

    ^ Ь1 +

    = 0

    < -2СЬУ (х., Х) + (? У-1? + Ai »" х '+' х ' "+ Л \<= 0 Ь '+ Ч? 0 »' +1

    2. Оцінка швидкості збіжності для варіанту швидкого градиентного методу, що використовує концепцію (8, А, »-моделі цільової функції в запитаної точці

    Виявляється, що концепція (8, А, »-моделі оптимизируемого функціоналу дозволяє отримати аналог теореми 1 для адаптивного варіанту швидкого градиентного методу Ю. Є. Нестерова (БГМ) [15]. Сенс використання цього методу в тому, що при відсутності похибок він дає оптимальні оцінки швидкості збіжності на класі задач опуклою оптимізації з ліпшіцевим градієнтом. Ми вирушаємо від [2], де запропоновано адаптивний швидкий градієнтний метод з оракулом, який використовує (8, "-модель цільової функ-

    А = 0

    1-сильна опуклість путті-функції й (х) відносно норми.

    Зауваження 3. Аналогічно зауваженням 2 для будь-якого до ^ 0 при деякому З ^ 1 виконано Ьк ^ 2СЬ. При до = 0 це вірно з того, що "0 ^ 2» Для до ^ 1 це випливає з того, що ми вийдемо з внутрішнього циклу, де підбирається Ьк, раніше, ніж Ьк побільшає 2СЬ. Вихід з циклу гарантується тим, що згідно з припущенням існує (8, А, »-модель для / (х) в будь-якій точці х ?

    За схемою міркувань [2] можна перевірити наступний результат.

    Алгоритм 2 Швидкий градієнтний метод з оракулом, який використовує (5, Д,?) - модель в запитаної точці.

    Require: х °? Q - початкова точка, V (х *, х °) ^ R2, параметри Lo > 0, Д0 > 0,? Про > 0 (L0 < 2L, До < 2Д, 50 < 25). 1: 0-крок: у0: = х0, і0: = х0, Li: = k0, Д1: = ~ 20, Si: = f-, ат: = 0, А0: = ат 2: for к = 1 ,. .. do

    3: Знаходимо найбільший корінь ak + i: Ак + ak + i = Lk + iak + i ',

    Ак + i: = Ак + ak + i, Ук + i: = ak + lUA + АКХ, fk + i (х) = V (х, ик) + ак + ЖХ, ук + 1);

    Ак + 1

    k + i / \ k + i ak + iuk + i + Акхк і +: = argmm ^ Qifk + i ^), х +: = ---;

    4: if U (хк + i) < h (yk + i) + Ф (хк + А-, yk + i) + \ ^ k + i - yk + i || 2 + Дк + Лхk + i - yk + i || + 5k + i then

    Lk + 2: = Lk2 + \ Дк + 2: = і ^ k + 2: = і перейти до наступного кроку else

    Lk + i: = 2Lk + i, Дк + i: = 2Дk + l і 5k + i: = 25k + i і повторити поточний крок end if end for

    Теорема 2. Нехай V (х *, х °) ^ В ?, де х0 - початкова точка, ах * найближча точка мінімуму до точки х0 в сенсі дивергенції Брегмана. Для запропонованого алгоритму, 2 після до ітерацій виконано наступне нерівність:

    В2 1 к-1

    !(Хк) -! (Х *) < -- + ^ ^ (Аг + 1 || х * + 1 - уг + 11 | + 5 + + 5) Аг + 1.

    г = 0

    Відзначимо, що допоміжна завдання, пункту 3 лістингу алгоритму 2 вирішується не більше

    (2Ь 25 2А1

    2к + шах -, '^ 2 д Г (13)

    раз.

    Отриману оцінку можна дещо конкретизувати з використанням наступного допоміжного твердження, яке також перевіряється за схемою міркувань [2] (по суті, воно вже доведено в [2] при С = 1).

    Лемма 1. Нехай для послідовності ак виконано

    до

    ат = 0, Ак = ^ 2 -к = Ькак,

    г = 0

    де для фіксованого З ^ 1 вірно Ьк ^ 2СЬ при всякому до > 0 згідно з зауваженням 3 вище. Тоді, для, будь-якого до ^ 1 вірно наступне нерівність:

    -до * > ^ • ( »)

    Тому з теореми 2 випливає

    Наслідок 2. Нехай V (х *, х0) ^ В2, де х0 - початкова точка, ах * найближча точка х0

    виконано наступне нерівність:

    8С г В2 1 к-1

    ?(Хк) -? (Х *) < (До + Г ^ + А ~ до ^ (Д + 1 ЦХТ - Уг + 111 + 8 + 1 + 8) 4 + 1-

    3. Про застосування запропонованої концепції неточною моделі

    функції до негладким завданням за рахунок введення штучних неточностей

    Відзначимо, що на величину А в (12) можна дивитися і як на характеристику негладку функціоналу /. Точніше кажучи, А можна розуміти, наприклад, як верхню оцінку

    раторних відрізків [х; у] з області визначення /. Виявляється, в разі відомої величини А < можливо дещо модифікувати алгоритм 1, забезпечивши зменшення Аг + 1 || ХГ + 1 -ХГ \\ в (12) до будь-якої заданої величини. Це дозволить показати оптимальність даного методу в теорії нижніх оракульних оцінок [1] ​​з точністю до логарифмічного множника. Зауважимо, що в даному пункті ми всюди вимагаємо 1-сильну опуклість путті-функції у визначенні 1. Також позначимо всюди далі через / * = / (х *) - шукане

    пускає (5, А, »-модель ф.

    Нехай на (до + 1) -й ітерації алгоритму 1 (к = 0,1, ..., І - 1) вірно нерівність Ь ^ Ь ^ + 1 ^ 2Ь (як показано в п. 2 доведення теореми 2.1 з [4 ], цього можна завжди домогтися виконанням не більше ніж постійного числа операцій п. 2 лістингу алгоритму 1). Для кожної ітерації алгоритму 1 (к = 0,1, ... - 1) запропонуємо таку процедуру:

    Повторюємо операції п. 2 р раз, збільшуючи Ьк + 1 в два рази при незмінній Ак + 1 ^ 2А.

    Процедуру (15) зупинимо в разі виконання одного з нерівностей:

    А

    fc + i

    xk + 1 - x

    < -2

    або

    f (xk + 1) < f (xk) + ф (хк + 1, хк) + 2P-1L

    xk + i xk

    (15)

    (16) (17)

    Відзначимо, що тут ми вважаємо функціонал / точно заданим, тобто = / (5 = 0) і ф (у, х) = (V / {х), у - х), де V / - деякий субградіент f. В роботі [4] доведено, що р можна вибрати так, щоб 22Р ^ 1 + ^ г ^ -, і отриманий наступний результат.

    Теорема 3. Нехай ^ = 0. Тоді для виходу ук + 1 модифікованого алгоритму 1 з урахуванням додаткової процедури (15) нерівність / (ук + 1) - / * ^ е буде гарантовано виконано не більш ніж після

    4LR2 64A2R2

    - + -про-

    log2 1 +

    16А2 Y

    L

    -

    (18)

    Нехай тепер у > 0. Якщо покласти 5i + i = 5 = 0 для будь-якого r = 0, до і Аг + 1 || ХГ + 1 - ХГ || ^ §, то відповідно до теореми 1

    f (yk + 1) - fix *) < 2CL (l - 2 ^ L) k + 1 V (x *, x0) + 2-.

    А

    ° (1 'og2;)

    2

    кроків градиентного методу (пункту 2 лістингу алгоритму 1). Дійсно, якщо покласти 5 = 5 = 0 (тобто = /) і V (х *, х0) ^ В2, то для досягнення якості рішення

    ?(Ук + 1) -? (Х *) ^ е

    необхідно виконати не більше

    2СЬ, 4СЬВ2 -1п-

    ц е

    1

    ітерацій алгоритму 1. З огляду на оцінки (22) з урахуванням процедури (15) на кожному кроці підсумкове число звернень до (суб) градієнту цільового функціоналу для алгоритму 1 можна оцінити як

    (20, Ь 32С А2 \ (40>ЬВ2 64СВ2 '1 + - 1п [- +-

    V ц

    це) \ е

    ) 1оЕ2 ^ 1 +

    16А2 \ еЬ)

    1.

    Покажемо, що дасть застосування схожою схеми для швидкого градиентного методу на класі опуклих функціоналів /, для яких при деяких Ь > 0 і А > 0 вірно

    Ь

    ?(У) < ?(Х) + ф (у, х) ^ 11 у-х \\ 2 + А || у-х \\ Ух, у ея-

    (19)

    Зокрема, для завдань опуклою негладкою оптимізації ф (у, х) = (V / (х), у - х) для деякого субградіента V /.

    Розглянемо варіант швидкого градиентного методу (алгоритм 2), який використовує (, А, Ь)

    тивний варіант цього методу з постійним кроком Ьк + 1 = 2Р Ь для деякого ре Мі 5 = ^ для деяких е > 0 та фіксованого постійної 7 > 0. Будемо при цьому вважати = / (тобто функціонал / заданий точно). В такому випадку на (до + 1) -й ітерації (к = 0, 1, 2,...)

    ?(Хк + 1) < ?(Хк) + ф (хк + 1, хк) + ^ Цхк + 1 - хк112 +

    2

    і після N ітерацій (це можна перевірити аналогічно [2])

    ?(Х1У) - г <

    8 | 2р | ЬВ2 eN

    +

    (^ + 1) 2 27 '

    А | | хк + 1 - ук + 1Ц < ^,

    | | хк + 1 - ук + 11 | 2 ^ АЦхк + 1 - ук + 11 |

    (20)

    (21)

    якщо

    то

    А | | хк + 1 - ук + 1Ц > -, (2Р - 1) Ь .. до + 1 до + 1 .. (2Р - 1) Ье

    2 11 х -ук ^ > 47А •

    Тоді друга нерівність альтернативи (21) завідомо виконається при

    47А2

    2Р > 1 +

    Ь

    Тому покладемо

    =

    Ч1 + 4-7Т)

    (22) (23)

    Тепер покажемо, яким можна вибрати кількість ітерацій N щоб гарантовано (46) забезпечувало) - / * ^ е. Для цього будемо вимагати виконання нерівностей

    2Р + 3ЬК2 е їжак е

    - ^ - і - ^ -

    (Ж + 1) 2 2 2 '

    звідки 7 ^ N і (Ж + 1) 2 ^ 2Р +. Для спрощення викладок посилимо останню вимогу: N2 >

    2 Р + 4ЬК2

    , звідки

    2 16ЬК2 (47А2 Ч 16ЬК2 64ЖА2К2 Ж2 > - 1 + -! - ^ - + - 2-.

    ? \ Ь? )? ? 2

    Це означає, що Ж можна вибирати як, де N2 - більший корінь рівняння

    ДТ2 64А2К2 16ЬК2 п Ж2 - Ж - = 0,

    32А2К2 [32А2В2 \ 2 16ЬК2

    Ж2 = + 1 ^ - ^) +

    2

    /

    Далі, в силу нерівності у / а + Ь > + (А, Ь > 0) маємо

    ж ^ N2 - ^ - +-.

    2

    (Й)

    ітерацій швидкого градиентного методу, тобто обгрунтований деякий аналог результату про слайдингом [14], але вже цільова функція не обов'язково є сума гладкого і негладкого доданків.

    При цьому можливо використовувати метод з адаптивною налаштуванням констант Ь, а також Ак + 1 ^ А. Тоді оцінка числа ітерацій може змінитися в постійне число раз. Також при цьому за рахунок р додаткових процедур адаптивного підбору Ь ^ + 1 (за умови Ь ^ Ь ^ + 1 ^ 2Ь для всякого к = 0,1, ... - 1) на кожній ітерації методу додасться множник (23):

    р ^

    (4Ж А2 \ 1 ((128 + 64 ^ 2) А4К2 ЖА2 ^ 2 \

    Теорема 4. Для виходу хм модифікованого алгоритму 2 з урахуванням додаткової процедури (15) при А ^ + 1 = А на (до + 1) -й ітерації (к = 0,1, ..., Ж - 1) нерівність? ( Хі) - / * ^ е буде гарантовано виконано не більш ніж після

    (32 + 16л / 2) А2К2 2КУ [21, ((128 + 64л / 2) А4 К2 8КА2Л / 2 \

    + - | §2 (1 + - + -I

    ?2 -ф?

    Ь? 3 'у /'ё3)

    (24)

    Зауваження 4. Якщо не припускати, що на (до + 1) -й ітерації (к = 0,1, ..., N - 1) модифікованих алгоритмів 1 і 2 виконано нерівність Ь ^ Ь ^ + 1 ^ 2Ь і передбачити

    Ь А

    збільшитися не більше ніж в

    * 2Ь 2 ^ "

    , А0 /

    раз. Відзначимо також, що логарифмічні множники в (18) і (24) можна опустити, якщо розглядати неадаптівние варіанти методів 1 і 2 з фіксованим параметром Ьк + 1 = 2РЬ при відповідному натуральному р.

    4. Адаптивна настройка на величину похибок для варіаційних нерівностей і сідлових завдань

    Метод з адаптивною налаштуванням похибок можна запропонувати і для варіаційних нерівностей [16], а також сідлових завдань. В даному пункті ми покажемо, як це можна зробити в модельній спільності. Ми вирушаємо від [17], де введена концепція неточною моделі для варіаційних нерівностей і сідлових завдань, але з постійною неточністю і без адаптивної настройки до величинам похибок.

    Нагадаємо постановку задачі рішення варіаційного нерівності, а також необхідні поняття і результати. Для оператора З: Я ^ Мга, заданого на опуклому компакті Я з Мга під сильним, варіаційним, нерівністю розуміємо нерівність виду

    (С (х *), х * х) < 0. (25)

    Відзначимо, що в (25) потрібно знайти х * е Я (ет0 х * якого

    тах (С (х *), х * - х) ^ 0. (26)

    Для монотонного оператора поля С можна розглядати слабкі варіаційні нерівності

    (С (х), х * х) < 0. (27)

    х * е Я х е Я

    Запропоновано аналог концепції неточною моделі цільової функції в оптимізації для варіаційних нерівностей і сідлових завдань. Для зручності будемо розглядати задачу

    х * е Я

    ф (х, х *) ^ 0 Ух ея (28)

    для деякого опуклого компакта Я С КГА, а також функціоналу ф: Я х Я ^ Якщо

    ф

    ф (х, у) + ф (у, х) < 0 Ух, у ея, (29)

    то всяке рішення (28) буде також і рішенням двоїстої задачі рівноваги

    ф (х *, х) < 0 Ух ея. (30)

    х *

    ф

    Приклад 2. Якщо для деякого оператора З: В ^ Мга покласти

    ф (х, у) = (С (у), х-у) Ух, у ея, (31)

    то (28) і (30) будуть рівносильні відповідно стандартним сильному і слабкому вариа-

    З

    тах |

    Приклад 3. Для деякого оператора G: Q ^ Мга і опуклого функціоналу h: Q ^ Мга простої структури вибір функціоналу

    ф (х, у) = (G (y), x -у) + h (x) - h (y) (32)

    призводить до змішаного вариационном, у нерівності

    (G (y), y-х) + h (y) - h (x) < 0, (33)

    G

    (G (x), y-х) + h (y) - h (x) < 0. (34)

    Концепцію (o, А, »-моделі для виділеного вище класу задач можливо ввести в такий спосіб.

    Визначення 3. Будемо говорити, що функціонал ф допускає (5, А, »-модель ф $ (х, у) при деяких фіксованих значеннях параметрів L, 5, А > 0 в довільній точці у відносно дивергенції Брегмана V (у, х), якщо для довільних x, y, z ЕQ вірні:

    (I) ф (х, у) < ф5 (x, y) + S-,

    (Ii) ф $ (х, у) опуклий функціонал по першій змінної і ф $ (х, х) = 0;

    фе (х, у) + фб (у, х) < S; (35)

    (Iv) (узагальнена відносна гладкість)

    ф&(Х, у) < ф&(Х, z) + ф&(Z, у) + LV (х, z) + LV (z, у) + 5 + А \\ у - z \\. (36)

    Природно виникає ідея узагальнити цей метод на абстрактні завдання (28) і (30) в припущеннях їх розв'язання, а також (i) - (iv). При цьому будемо враховувати похибку 5 в (36), а також похибка 5 рішення допоміжних завдань на ітераціях відповідно до одного з досить відомих в алгоритмічної оптимізації підходів:

    х: = arg m, in, yeQ<f (у), якщо (V ((x), x - у) ^ 6. (37)

    По суті, передбачається, що допоміжні завдання мінімізації вирішуються з деякою o

    , А, L

    аналог проксимального дзеркального методу A.C. Немирівського з адаптивним вибором кроку. Опишемо (N + 1) -ю ітерацію цього методу (N = 0,1, 2, ...), вибравши початкове наближення х0 = arg minX? Qd (x), зафіксувавши точність е > 0, а також деякі константи L0 ^ 2L, o0 ^ 20 і А0 ^ 2А.

    Алгоритм 3 Адаптивний метод для концепції (5, А,?) - моделі для ВН.

    1. N: = N + 1 Ln + 1: =, W: = ^, AN + 1: =

    2. Рахуємо:

    yN + l: = argminsX? Q [ф ^ (x, xN) + LN + 1V (x, xN)},

    xN + 1: = arg minsxeQ [ф ^ (x, yN + 1) + LN + 1V (x, xN)} ​​доти, поки не буде виконано:

    ф& (XN + 1, xN) (yN + 1, xN) + ф& (XN + 1, yN + 1) + + Ln + 1V (yN + 1, xN) + Ln + 1V (yN + 1, xN + 1) + An + 1 || yN + 1 -xN + 1 II + ON +1.

    (38)

    3. Якщо (38) не виконано, то Ln + 1 | = 2Ln + i, $ n + i | = 25n + u Д «+ i | = 2An + 1 і повторюємо п. 2.

    4. Інакше перехід до п. 1.

    5. Критерій зупинки методу:

    n -1 maxV (х, х0)

    У - > ^ -. (39)

    Для стислості будемо всюди далі позначати

    N-1 + 1

    SN J- | (40)

    fo Jk + 1

    справедлива наступна

    х е Я

    виконано нерівність

    _ Ф ^ <?+2 "+ + д - ^, (41)

    ^ Ьк + 1 8м Ьк + 1

    а також

    , ^ ~ 1 У-$ до + 1 + Ак + 1 Цук + 1 -хк + 1Ц, ч

    ф (у, х) < г + 25 + 25 + -? - ^ (42)

    ^ Ьк + 1

    при

    1 N-1 vk + i

    ^ Е Ь- <43>

    Sn Jk + 1

    Зауваження 5. Для звичайних слабких варіаційних нерівностей (27) нерівність (42) можна замінити на

    ~, 1 1N-1 5k + 1 + ^ k + 1 \\ yk + 1 -Xk + 1 \

    max {G (x), у - x) ^ e + 25 + 25 + - у ^ -z-u-11. (44)

    xeQ sn Jk + 1

    Аналогічно теоремі 3 можна сформулювати результат про те, що при j = 5 = 5 = 0

    процедурою типу (15) можна домогтися виконання max (G (x), у - х) ^ е за

    xeQ

    4LR2 64Д2

    -+

    2

    , / 16Д2 \

    звернення до оракула для З.

    (, А, Ь)

    що постановка седловой завдання передбачає, що для опуклого з футболу та увігнутого по V функціоналу? (І, V): М ™ 1 + ™ 2 ^ М (і Е Q1 З М "1 і V Е Q2 З М" 2) потрібно знайти (і *, V *) таку, що

    ?(І *, V) ^? (І *, V *) ^? (І, V *) (45)

    для довільних і Е Ql і V Е Q2| Ми вважаємо Ql і Q2 опуклими компактами в просторах М "1 і М" 2 і тому Q = Ql х Q2 З М ™ 1 + ™ 2 також є опуклий компакт. Для будь-якого х = (і, у) Е ^ ^^^^^ ^^ агать, що || х || = УТМ] 2 ^ !! ^]] 2, де || | І || | || 2 - норми в просторах М "1 і М" 2). Домовимося позначати х = (їх, їх), у = (ІУ, иу) Е Q.

    і

    до варіаційного нерівності з оператором

    cw = | (46>

    Запропонуємо деяку варіацію концепції (5, Д, L) -мoдeлі для варіаційних нерівностей, але вже на більш вузькому класі сідлових завдань.

    Визначення 4. Будемо говорити, що для деякої постійної 5 > 0 функція ф&(X, у) (ф: Мга1 + ГА2 х R "-ix" -2 ^ R) є (o, Д, L) -мoдeль для седловой завдання (45), якщо для деякого функціоналу фз при проізвольпих x, y, z Е Q виконані припущення (i) - (iv) визначення 3, а також справедливо нерівність:

    f (uy, vx) - f (ux, vy) ^ ФЗ (x, y) + S Ух, у eQ. (47)

    З теореми 5 випливає

    Теорема 6. Якщо для седловой завдання (45) існує (o, Д, L) -M, ode ^, ь фз (х, у), то після зупинки алгоритму 3 отримаємо точку

    1 ^ ук + 1

    У = (uy, Щ): = (і v): = L-, (48)

    N k = 0 k + l

    для, якої вірна оцінка, величини-якості рішення седловой, завдання:

    f (~) | f (^ ^ + 2 J - +. + 1 N- Ok + 1 + Дк + 1 \\ yk + l -xk + l \\

    max f (u, v) - mm f (u, v) ^ e + 2d + o + -7- > --LJ-11. (49)

    veQ2 ueQi On k == 0 Lk + i

    5. Адаптивні алгоритми дзеркального спуску для негладких задач опуклою оптимізації з функціональними обмеженнями

    В даному розділі ми розглянемо деякі методи для задачі мінімізації опуклою негладкою функції f (x) ^ min з ліпшіцевим опуклим функціональним обмеженням g (x) ^ 0. Далі будемо вважати, що х * - одне з рішень такого завдання. Ми будемо розглядати для виділеного класу задач методи, аналогічні схемам з перемиканнями, які сходять до піонерським роботам [18,19]. Нещодавно в [20] були запропоновані методи дзеркального спуску такого типу для умовних задач з адаптивним вибором кроку і адаптивними критеріями зупинки. Більш того, виявилося [13,21], що для зазначених процедур

    оптимальну на класі опуклих ліпшіцевих цільових функціоналів оцінку швидкості збіжності 0 (е-2) можна поширити і на клас квазівипуклих гёльдерових цільових функціоналів. Розглянуто і додатки до задачі оптимізації комп'ютерної мережі для логарифмічного цільового функціоналу [21]. За підсумками проведених експериментів з'ясувалося, що, як правило, швидше за всіх з розглянутих схем [13, 20, 21] працює наступний метод.

    Алгоритм 4 Адаптивний дзеркальний спуск

    Require: е > 0, О0: d (x *) ^ 0% 1: х0 = argminxeQ d (x) I = 0 k ^ 0 repeat

    if g (xk) ^ еЦУд (xk) || * then hk ^

    2

    3

    4

    5

    6

    7

    8 9

    10

    11 12

    13

    14

    || V / (xk) || *

    xk + 1 ^ Mirrxk (hkVf (xk)) // "продуктивні кроки 'k

    else

    hk ^ || Vfl (Xk)

    i *

    xk + 1 ^ Mirrxk (hkVg (xk)) // "непродуктивні кроки end if k ^ k + 1 until

    2a

    Де I j | - кількість непродуктивних кроків (ми позначимо через | / | кількість продуктивних кроків, тобто | I | + | JI = N). Ensure: х = hkXk.

    kei kel

    Позначимо через e > 0 фіксовану точність, хо - початкове наближення таке, що для деякого © про > 0 вірно нерівність V (х *, х °) ^ © 0- Нехай

    Ь (х) - д (у) < Мд || х -уЦУх, у eQ. (51)

    Тоді справедливий наступний результат про оцінку якості знайденого рішення запропонованого методу (в [21] є повний доказ в разі евклідової Проксі-структури, для довільної Проксі-структури це обгрунтування аналогічно).

    Теорема 7. Після зупинки запропонованого алгоритму 4 справедливі, нерівності

    f (x) -? (х *) ^ е і g (х) ^ ЕМД.

    На базі теореми 7 в припущенні ліпшіцевості цільового функціоналу

    | f (х) -? Ш ^ Mf Цх -уЦ (52)

    можна оцінити кількість ітерацій, необхідних для виконання критерію зупинки (1). Ясно, що V kel f (хк) || * ^ Mf, і тому

    i J i + g ц ^^ > i J i + Mf > ^ + ^ ТщЬп-

    Це означає, що при

    2&1 max {1, M2f}

    N >

    ?2

    критерій зупинки (1) свідомо виконаний, тобто шукана точність досягається за О (ітерацій.

    За аналогією з ([20], теорема 3.2) можна перевірити наступний результат, що означає прямо-подвійність алгоритму 4 в разі обмеженого безлічі Q.

    Теорема 8. Нехай Q обмежена і max d (x) < 60. Тоді якщо застосувати алгоритм 4 до

    xeQ

    завданню

    <PW = mi, n 1 f (x) + У2 hgi (x) >

    xeQ I fi J

    ^ Max, xeQ I "v I ^ i '^ 0, i = i, ..., m

    \ I = i)

    то після зупинки для знайденої пари (xk, \ k) буде вірно:

    f (xk) -<р (.Xk) < e, g (xk) ^ Mgе.

    Схожий на алгоритм 4 метод можна запропонувати і для задач з наступними релаксації відомого нерівності Коші-Буняковського для субградіентов Vf (х) і Vg (х):

    {Vf (х), х - у) ^ w \\ Vf (х) \\ * V-V (У, х) VyeQ (53)

    2

    і всякого х G Q такого, що V (х *, х) ^ де х * - найближчим рішення до початкової точки хо з точки зору дивергенції V, w > 0 - деяка фіксована постійна; а також

    {V g (х), х - у) <Mg sj2V (у, х) Ух, у gQ (54)

    Mg > 0

    12

    Ясно, що при V (у, х) ^ 1 \\ У - х \\ нерівність (53) вірно для w = 1. Нерівність (54),

    алгоритм 5.

    Тоді з (53) і (54) маємо

    hk (Vf х), хk - х * \ <---2 + V (х *, х, г) - V (х * ^^ 1) Ук G I,

    k \ / OWVf (Tk) || 2 V V

    2 \\ Vf) \\ *

    e2 < hkg ^) ^ hk (Vg (хk), хk - х * ^ ^ + V (х *, хк) - V (х * ^^ 1) Ук G J. Після підсумовування зазначених нерівностей отримуємо

    ? hk (/ ^) - f (.х *)) < ^? hk -? - \ J \ + V (х *, х0). kei kei

    Теорема 9. Після виконання, критерію зупинки (55) справедлива оцінка:

    / (? С) -? (Х *) < ш2е і д (х) < ЕМД (56)

    або V (х *, хк) < ^ Для деякого до.

    Зауваження 6. Замість умови (53) можна розглянути і нерівність {V / (х), х - у) ^ М ^ у / 2V (у, х), яке вірно в разі відносної ліпшіцевості / [12]. Для цього необхідно вибирати в алгоритмі 5 продуктивні кроки Ік = а також критерій зупинки

    2V (х *, х) = 2&0 < Mr +? 'V \ |

    про

    Алгоритм 5 Адаптивний дзеркальний спуск

    Require: е > 0, в0: d (x *) ^ в0

    1 2

    3

    4

    5

    6

    7

    8 9

    10 11 12

    13

    14

    x0 = argminxeQ d (x) I = 0 k ^ 0 repeat

    if g (xk) ^ eMg then

    hf 4 __ ^ _

    Uk ^ || Vf (xk) || *

    xk + l ^ Mirrxk (hkVf (xk)) k

    else

    hg i__ihk ^ Mg

    xk + 1 ^ Mirrxk (hkVg (xk)) end if k ^ k + 1 until

    "Продукт, івние кроки '

    "Непродуктивні кроки '

    2в2

    <

    ?

    kei

    ш

    \\ Vf (xk) ||

    + \ J \,

    (55)

    Де ijl - кількість непродуктивних кроків (ми позначимо через | / | кількість продуктивних кроків, тобто | / | + lJ | = N).

    Ensure: ж

    ? h

    kei

    f

    k kei

    Y1 h {xk

    Після виконання цього критерію буде вірно нерівність

    f (%) - f (x *) ^ е і ^ е мд|

    (57)

    2

    1

    Отриманий результат дозволяє застосувати запропоновану алгоритмічну схему для негладких задач опуклою однорідної оптимізації з відносною точністю. Така постановка перегукується з роботам Ю.Е.Нестерова (див. Розділ 6 дисертації [25]). Як показано Ю.Е.Нестеровим, підхід до оцінки якості виконання завдання з точки зору саме відносної точності цілком виправданий для різних прикладних задач (лінійне програмування, проектування механічних конструкцій, завдання оптимальної еліпсоїдальної апроксимації опуклого безлічі і ін.), Якщо бажана відносна точність не дуже мала. Відомо, що досить широкий клас задач оптимізації з відносною точністю можна зводити до мінімізації опуклою однорідної функції. Отже, розглядається на опуклому замкненому безлічі Q З Шп завдання мінімізації опуклою однорідної функції виду

    f (x) ^ min (58)

    x? Q

    з опуклими функціоналами обмеженнями

    gp (x) ^ 0, р = 1, т. (59)

    Стандартно будемо позначати g (x): = maxi ^ p ^ m {gp {x)}.

    З використанням розглянутих варіантів концепції відносної ліпшіцевості покажемо, як можна виписати оцінки збіжності для дзеркальних спусків з перемикання-0

    Розглянуто наступний ослаблений варіант цього умови

    (0) Cdf (0) QB% (0), (60)

    де К * - пов'язаний конус до деякого полунормірованному конусу До З КГА до закону скорочення і конус-напівнорма || | \\ до (відміну від звичайної напівнорма в тому, що 11 | ^^ = а || х || до лише для a ^ 0). Тут під сопрле / СеММ&ш конусом К * розуміється набір функціоналів виду фе = max {0, l (x)} для лінійних функціоналів I: До ^ R: l (x) ^ Ci N ^ ll ^ ПРИ деякому Се > 0 Ух? К. Ясно [22,23], що К * буде опуклим конусом з операціями додавання

    ф / Л ®фе2: = Ф: ф (х) = max {0, l \ (x) + i2 (x)}

    і множення на скаляр Л ^ 0 ФХЕ (х) = ЛФЕ (х) = Л max {0, l (x)} Ух? К. На К * можна ввести норму ЦфеЦк * = sup \ ^ \\ K ^ max {0, l (x)} = sup \ ^ \\ K ^ 1 (х) і куля радіуса г В? * (0) = {фе? К * \\ 1феЦк * < г}

    З аналога теореми про опорному функціонал в н0рМІр0ванних конуса р2] отримуємо,

    що

    \\ х \\ к = max 1 (х). (61)

    -Феев ** (0)

    Для полунормірованного конуса при Цх || к = 0 досить вибрати I = 0, і (61) буде вірно. Наведемо деякий приклад пари (К, К *).

    Приклад 4. Нехай К = {(х, у) \ х, у? R} і \\ (х, у) \\ к = л / х2 + у2 + у. Можна перевірити, що в такому випадку К * = {фе \ I ((х, у)) = Лх + цу: ц + ^ < або Л = ц = 0}, а

    0, якщо Л = ц = 0;

    до * = \ ц Л2 Л2

    - + -, якщо ц +--< при ц > 0.

    2 2ц Ц

    Тоді Вк (0) має вигляд кола на площині (Л, ц) радіуса 1 з центром в точці Л = 0, ц = 1. Не зменшуючи спільності міркувань, будемо вважати К = і вк (0), а також X *? До для

    точного рішення х * розглянутої задачі мінімізації f на Q.

    Згідно зі схемою міркувань ([25], глава 6) для виведення оцінок швидкості збіжності методів з відносною точністю необхідно знати оцінку R величини відстані від

    х0 х *

    операція віднімання і тому в якості аналога норми різниці можна використовувати метрику йк (х0, х *), де

    (Х, у) = sup \ фе (х) -фе (у) \ Ух, у? Q. \\ до * <л

    Деякі умови, при яких нормований конус допускає існування метрики такого типу, досліджені автором роботи в [22-24].

    Отримано аналог теореми 6.1.1 [25] для зазначеного вище припущення (х °, х *? К).

    Теорема 10. 1) Ух? До 7 ° \\ х \\ до ^ 1 (х) ^ Більш того,

    а / (х0) < Ред \\ х ° \\ до < ?(Х *) < Дх °) < Ред \\ х0 \\ до.

    2) Для будь-якого точного рішення х *? До справедливо нерівність

    2 + 2

    йк (х °, х *) < \\ х ° \\ до + \\ х * \\ до < - г < -?(Х °).

    7 ° 7 °

    Для застосування до поставленого завдання наведеного вище методу дзеркального спуску (алгоритм 5) із запропонованими варіантами умов відносної ліпшіцевості досить вибрати Проксі-структуру так, щоб

    V (х *, х °) < ш (1к (х *, х °), (62)

    для деякої постійної сС > 0. Цього можна домогтися, наприклад, такими способами:

    1. Якщо х ° = 0, то при d (x) = \\ Хук можна покласти V (х *, 0) = \\ х * \\ к = dK (х *, 0).

    2. Якщо х0 = arg minX ^ Qd (x), то для деякого субградіента Vd (x °) вірно нерівність (yd (x °), x * - х °) ^ 0 і тоді V (х *, х °) ^ d (х *) - d (x0). Якщо вибрати d (х) = \\ х \\ до, то відповідно до теореми про опорному функціонал в полунормірованних конусах

    V (х *, х0) = \\ х * \\ до - || х ° || к = max [0,? (Х *)} - || х0 || до ^ ^ max {0,1 (х *)} - max {0,? (х0)} ^ d к (х *, х0),

    тобто (62) виконано при зі = 1. Вважаємо далі зі = 1 (інше значення цієї постійної може привести лише до зміни в підсумкових оцінках констант).

    циала df (0) для деякої константи Mf > 0 буде вірно \\ Vf (х) \\ + ^ Mf. Тому критерій зупинки модифікованого алгоритму 5 відповідно до зауваженням 6 свідомо буде виконаний після 2O0 max | l, M | j е-2 ітерацій. Будемо вважати, що

    Oq = d к (х0, х *) ^ V (х *, х0) і для деякого N (число ітерацій) виберемо е = - =. f (x) - f (x *) ^ і д (х) ^ - =. Тепер згідно з зауваженням 6 маємо

    В2 2 f (x *) ff (2 \ МД Q0

    ^^ ^ ', тобто fix) ^ fix *) 1 + - = і а (х) ^ -.

    Vn V 7oVN) ^ JN

    Тому для досягнення відносної точності 5 > 0 по функції свідомо досить

    N > 4

    кроків модифікованого алгоритму 5 з постійними продуктивними кроками згідно з зауваженням 6. Відзначимо, що критерій зупинки при цьому свідомо виконаний при N ^ -? гш,

    те "

    оскільки

    2в2 тах ^ 1, М2 ^ 2N тах ^ 1, М2 ^ 8тах ^ 1, М2 ^

    про

    ^ ^ = © 0 ^ ^ '

    звідки випливає наступна

    зауваження 6 і при цьому М1 > 0 така, що IV / (ж) У * ^ М ^ Тоді, після N ^ ^ 2 ітерацій модифікованого алгоритму 5 з постійними продукт, ієни, м, і, кроками згідно з зауваженням 6 гарантовано буде вірно нерівність

    М © 2

    / (Ж) (х *) (1 + 5) ід (Х) < .

    висновок

    У цій статті запропоновані деякі адаптивні методи градієнтного типу, які застосовні до завдань негладкою оптимізації.

    У перших трьох розділах розглянуті підходи, засновані на введенні штучних похибок. Похибки можуть бути як природними (завдання цільової функції і градієнта), так і штучними (зведення негладкою завдання до гладкою з деякою неточністю). При цьому одна з основних відмінних рис пропонованих підходів - наявність в оптимізаційної моделі цільового функціоналу змінної величини, що відповідає похибки (суб) градієнта або ступеня негладких завдання.

    Отримано оцінки швидкості збіжності для адаптивного неускоренного градиентного методу з адаптивною налаштуванням на рівень гладкості завдання, а також величини похибок. Розглянуто також варіант швидкого градиентного методу Ю.Є. Нестерова для відповідної концепції неточною моделі оптимізується функціоналу. Доведено, що для неускоренного методу не накопичуються всі типи похибок моделі. Для прискореного методу обгрунтована можливість зменшення впливу змінної похибки на оцінку якості рішення до будь-якої прийнятної величини при накопиченні величин, відповідних постійним значенням величин похибок використовуваної концепції моделі оптимізується функціоналу. При цьому адаптивність методу може на практиці покращувати якість знайденого рішення в порівнянні з отриманими теоретичними оцінками. Однак в отриманих оцінках якості рішення реалізована адаптивна настройка не всіх параметрів неточною моделі. Повна адаптивна настройка на величини похибок можлива для штучних неточностей, пов'язаних з розглядом негладких задач.

    Обґрунтовано можливість застосування неускоренного процедур для щодо гладких цільових функціоналів. В такому випадку отриману оцінку швидкості збіжності 0 (е-1) можна вважати оптимальною навіть при відсутності похибок [26]. Показано, як можна ввести аналогічну концепцію неточною моделі для варіаційних нерівностей і сідлових завдань і запропонувати аналог екстраградіентного методу з адаптивною налаштуванням на величину детермінованого (як постійного, так і змінного) шуму.

    В останньому шостому розділі роботи розглянуті адаптивні алгоритмічні схеми з перемиканнями для негладких задач опуклою оптимізації з ліпшіцевимі обмеженнями, які досить ефективно працюють для деяких завдань з цільовими функціоналами нижчого рівня гладкості. Зокрема, мова може йти про завдання з диференційовними гёльдеровимі цільовими функціоналами [21] або з відносно ліпшіцевимі цільовими функціоналами [12] і функціоналами обмежень. Введені релаксації умови Ліпшиця, зокрема, дозволяють отримувати оцінки швидкості збіжності з відносною точністю для однорідних цільових функціоналів при досить загальних припущеннях. Однак на відміну від результатів перших розділів роботи по методам градиентного типу не вдалося запропонувати методи з адаптивною налаштуванням на вели-

    замість звичайних субградіентов, а також обурених з точністю 5 > 0 значень функціоналів. У підсумкових оцінках при цьому не відбувається накопичення величин, відповідних

    ливаются величини, відповідні погрішностей, що виникають при вирішенні допоміжних завдань на ітераціях алгоритму 5. Зазначена методика може бути застосована до завдань з будь-якою кількістю функціоналів обмежень. У цьому плані цікавим завданням може бути порівняння розробленої методики з підходом до негладким завданням опуклого програмування з одним функціоналом обмеження, який заснований на переході до одновимірної двоїстої задачі. При цьому знаходження відповідного значення двоїстого множника може виконуватися методом дихотомії [28] при допустимої похибки значення похідної, пов'язаної з неточністю рішення допоміжних підзадач. Для задач з двома обмеженнями можна застосовувати методику [29] з критерієм зупинки, схожим на критерій зупинки алгоритму 1 з [28] та відповідним невластивому значенням обуреного градієнта двоїстої задачі. Експериментально показано, що такі підходи можуть призводити до лінійної швидкості збіжності навіть для негладких задач. Якщо ж цільової функціонал гладкий і сильно опуклий, а функціонали обмежень гладкі й опуклі, то лінійну швидкість збіжності можна обґрунтувати за схемою міркувань [28].

    Автор дякує П.Є. Дворічанського і A.B. Гаснікова за вказівку деяких літературних посилань і корисні обговорення.

    Робота виконана за підтримки гранту РФФД мовляв-а-вед (розділи 1 і 2), гранту РИФ

    18-71-00048 (розділи 3 і 4, теореми 7 і 8), а також гранту Президента РФ МК-15.2020.1

    (Теореми 10 і 11).

    література

    1. Немирівський А. С., Юдін Д.Б. Складність завдань і ефективність методів оптимізації. Москва: Наука, 1979. 384 с.

    2. Nesterov Yu. Universal gradient methods for convex optimization problems // Math. Program. Ser. A. 2015. V. 152, N 1-2. P. 381-404.

    3. Стонякін Ф. С. Аналог квадратичної інтерполяції для спеціального класу негладких функціоналів і одне його додаток до адаптивного методу дзеркального спуску // Динамічні системи. 2019. Т. 9 (37), № 1. С. 3-16.

    4. Стонякін Ф. С. Адаптація до похибки для деяких методів градієнтного типу // Праці ІММ УрО РАН. 2019. Т. 25, № 4. С. 210-225.

    5. Devolder О., Glineur F., Nesterov Yu. First-order methods of smooth convex optimization with inexact oracle // Math. Program. 2014. V. 146, N 1-2. n P. 37-75.

    6. Devolder O. Exactness, Inexactness and Stochasticitv in First-Order Methods for Large-Scale Convex Optimization // PhD thesis, 2013. 309 p.

    7. Tyurin A.I., Gasnikov A. V. Fast gradient descent method for convex optimization problems with an oracle that generates a (5, L) -model of a function in a requested point // Computational Mathematics and Mathematical Physics. 2019. V.59, N 7. P. 1137-1150.

    8. Stonyakin FS, Dvinskikh D., Dvurechensky P., Kroshnin A., Kuznetsova O., Agafonov A., Gasnikov A., Tyurin A., IJribe CA, Pasechnyuk D., Artamonov S. Gradient Methods for Problems with Inexact Model of the Objective // ​​In: Khachav M., Kochetov Y., Pardalos P. (eds) Mathematical Optimization Theory and Operations Research. MOTOR 2019. Lecture Notes in Computer Science. 2019. V. 11548. P. 97-114.

    9. Bauschke H.H., Bolte J., Teboulle M. A Descent Lemma Beyond Lipschitz Gradient Continuity: First-Order Methods Revisited and Applications // Mathematics of Operations Research. 2017. V. 42, N 2. P. 330-348.

    10. Necoara I., Nesterov Y. Glineur F. Linear convergence of first order methods for non-stronglv convex optimization // Math. Program. 2019. V. 175. P. 69-107.

    11. Lu H., Freund R.M., Nesterov Y. Relatively smooth convex optimization by Firstorder methods, and applications // SIAM Journal on Optimization. 2018. V. 28, N 1. P. 333-354.

    12. Lu H. «Relative-Continuitv» for Non-Lipschitz Non-Smooth Convex Optimization using Stochastic (or Deterministic) Mirror Descent // Arxiv preprint. 2018. 22 p. Available at: https://arxiv.org/abs/1710.04718v3.

    13. Stonyakin F., Stepanov A., Titov A., Gasnikov A. Mirror Descent for Constrained Optimization Problems with Large Subgradient Values ​​// Copmuter Research and Modelling. 2020. V. 12, N 2. 23 p. Available at: https://arxiv.org/abs/1908.00218v4.

    14. ban G. Gradient sliding for composite optimization // Math. Program. 2016. V. 159, N 1-2. P. 201-235.

    15. Нестеров Ю.Є. Метод мінімізації опуклих функцій зі швидкістю збіжності 0 (1 / к2) // Доповіді АН СРСР. 1983. Т. 269, № 3. С. 543-547.

    16. Stonyakin F., Vorontsova Е., Alkousa М. New Version of Mirror Prox for Variational Inequalities with Adaptation to Inexactness // Communications on Computer and Information Sciences. 2020. V. 1145. P. 427-442.

    17. Стонякін Ф.С. Про адаптивному проксимальному методі для деякого класу варіаційних нерівностей і суміжних завдань // Праці ІММ УрО РАН. 2019. Т. 25, № 2. С.185-197.

    18. Поляк Б. Т. Один загальний метод рішення екстремальних задач // Докл. АН СРСР. 1967. Т. 174, № 1. С. 33-36.

    19. Шор Н.З. Застосування узагальненого градієнтного спуску в блоковому програмуванні // Кібернетика. 1967. № 3. С. 53-55.

    20. Bayandina A., Dvurechensky P., Gasnikov A., Stony akin F., Titov A. Mirror descent and convex optimization problems with non-smooth inequality constraints // Large-Scale and Distributed Optimization. Lecture Notes in Math. 2018. V. 2227. P. 181-213.

    21. Ivanova A., Stonyakin F., Pasechnyuk D., Vorontsova E., Gasnikov A. Adaptive Mirror Descent for the Network Utility Maximization Problem // Arxiv preprint. 2019. 7 p. Available at: https://arxiv.org/abs/1911.07354v2.

    22. Stonyakin F.S. An analogue of the Hahn-Banach theorem for functional on abstract convex cones 11 Eurasian Math. J. 2016. V.7, N 3. P. 89-99.

    23. Стонякін Ф. С. Сублінейний аналог теореми Банаха-Мазура в відокремлюваних опуклих конусах з нормою // Матем. нотатки. 2018. Т. 104, № 1. С. 118-130.

    24. Stonyakin F.S. Hahn-Banach type theorems on functional separation for convex ordered normed cones 11 Eurasian Math. J. 2019. V. 10, N 1. P. 59-79.

    25. Нестеров Ю.Є. Алгоритмічна опукла оптимізація / Дисс. ... докт. фіз.-мат. наук. Москва: МФТІ, 2013. 367 с.

    26. Dragomir R.-A., Taylor A., ​​dAspremont A., Bolte J. Optimal Complexity and Certification of Bregman First-Order Methods. Arxiv preprint. 2019. 32 p. Available at: https://arxiv.org/abs/1911.08510.

    27. Dvurechensky P., Gasnikov A., Nurminsky E. and Stonyakin F. Advances in Low-Memory Subgradient Optimization. A.M. Bagirov et al. (Eds.), Numerical Nonsmooth Optimization, Springer Nature Switzerland AG. 2020. 36 p. Available at: htt ps: // arxiv .org / abs / 1902.01572vl.

    28. Stonyakin F.S., Alkousa M.S., Titov A.A., Piskunova V. V. On Some Methods for Strongly Convex Optimization Problems with One Functional Constraint. M. Khachav et al. (Eds.). Mathematical Optimization Theory and Operations Research. MOTOR 2019. Lecture Notes in Computer Science. 2019. V. 11548. P. 82-96.

    29. Пасечнюк Д.А., Стонякін Ф.С. Про один метод мінімізації опуклою ліпшіцевой функції двох змінних на квадраті // Комп'ютерні дослідження і моделювання. 2019. Т. 11, № 3. С. 379-395.

    References

    1. Nemirovsky A.S., Yudin D.B. Problem Complexity and Method Efficiency in Optimization. Moskow: Nauka, 1979. 384 p. (In Russian).

    2. Nesterov Yu. Universal gradient methods for convex optimization problems. Math. Program. Ser. A. 2015. V. 152, N 1-2. P. 381-404.

    3. Stonyakin F.S. An analog of quadratic interpolation for a special class of nonsmooth functional and one of its applications to the adaptive method of mirror descent. Dynamical systems. 2019. V. 9 (37), N 1. P. 3-16. (In Russian).

    4. Stonyakin F.S. Adaptation to inexactness for some gradient-type optimization methods. Proceedings of the Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences. 2019. V. 25, N 4. P. 210-225. (In Russian).

    5. Devolder O., Glineur F., Nesterov Yu. First-order methods of smooth convex optimization with inexact oracle. Math. Program. 2014. V. 146, N 1-2. P. 37-75.

    6. Devolder O. Exactness, Inexactness and Stochasticitv in First-Order Methods for Large-Scale Convex Optimization. PhD thesis, 2013. 309 p.

    7. Tyurin A.I., Gasnikov A. V. Fast gradient descent method for convex optimization problems with an oracle that generates a (6, L) -model of a function in a requested point. Computational Mathematics and Mathematical Physics. 2019. V. 59, N 7. P. 11371150.

    8. Stonyakin FS, Dvinskikh D., Dvurechensky P., Kroshnin A., Kuznetsova O., Agafonov A., Gasnikov A., Tyurin A., Uribe CA, Pasechnyuk D., Artamonov S. Gradient Methods for Problems with Inexact Model of the Objective. Khachav M., Kochetov Y., Pardalos P. (eds) Mathematical Optimization Theory and Operations Research. MOTOR 2019. Lecture Notes in Computer Science. 2019. V. 11548. P. 97-114.

    9. Bauschke H.H., Bolte J., Teboulle M. A Descent Lemma Beyond Lipschitz Gradient Continuity: First-Order Methods Revisited and Applications. Mathematics of Operations Research. 2017. V. 42, N 2. P. 330-348.

    10. Necoara I., Nesterov Y. Glineur F. Linear convergence of first order methods for non-stronglv convex optimization. Math. Program. 2019. V. 175. P. 69-107.

    11. Lu H., Freund R.M., Nesterov Y. Relatively smooth convex optimization by Firstorder methods, and applications. SIAM Journal on Optimization. 2018. V. 28, N 1. P. 333-354.

    12. LuH. «Relative-Continuity» for Non-Lipschitz Non-Smooth Convex Optimization using Stochastic (or Deterministic) Mirror Descent. Arxiv preprint. 2018. 22 p. Available at: https: / / arxiv.org/abs / 1710.04718v3.

    13. Stonyakin F., Stepanov A., Titov A., Gasnikov A. Mirror Descent for Constrained Optimization Problems with Large Subgradient Values. Cop muter Research and Modelling. 2020. V. 12, N 2. 23 p. Available at: https://arxiv.org/abs/1908.00218v4.

    14. Lan G. Gradient sliding for composite optimization. Math. Program. 2016. V. 159, N 1-2. P. 201-235.

    15. Nesterov Yu.E. A minimization method for convex functions with a convergence rate 0 (1 / k2). Dokl. Akad. Nauk SSSR. 1983. V. 269, N 3. P. 543-547. (In Russian).

    16. Stonyakin F., Vorontsova E., Alkousa M. New Version of Mirror Prox for Variational Inequalities with Adaptation to Inexactness. Communications on Computer and Information Sciences. 2020. V. 1145. P. 427-442.

    17. Stonyakin F.S. On the adaptive proximal method for a class of variational inequalities and related problems. Proceedings of the Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences. 2019. V. 25, N 2. P. 185-197. (In Russian).

    18. Polyak B. T. One general method for solving extreme problems. Dokl. Akad. Nauk SSSR. 1967. V.174, N 1. P. 33-36. (In Russian).

    19. Shor N.Z. Application of generalized gradient descent in block programming. Cybernetics. 1967. № 3. P. 53-55. (In Russian).

    20. Bayandina A., Dvurechensky P., Gasnikov A., Stonyakin F., Titov A. Mirror descent and convex optimization problems with non-smooth inequality constraints. Large-Scale and Distributed Optimization. Lecture Notes in Math. 2018. V. 2227. P. 181-213.

    21. Ivanova A., Stonyakin F., Pasechnyuk D., Vorontsova E., Gasnikov A. Adaptive Mirror Descent for the Network Utility Maximization Problem. Arxiv preprint. 2019. 7 p. Available at: https://arxiv.org/abs/1911.07354v2.

    22. Stonyakin F.S. An analogue of the Hahn-Banach theorem for functional on abstract convex cones. Eurasian Math. J. 2016. V.7, N 3. P. 89-99.

    23. Stonyakin F.S. A sublinear analogue of the Banach-Mazur theorem in separable convex cones with norm. Math. Notes. 2018. V. 104, N 1. P. 118-130.

    24. Stonyakin F.S. Hahn-Banach type theorems on functional separation for convex ordered normed cones. Eurasian Math. J. 2019. V.10, N 1. P. 59-79.

    25. Nesterov Yu.E. Algorithmic convex optimization. Doctoral thesis. Moscow, MIPT, 2013. 367 p. (In Russian).

    26. Dragomir R.-A., Taylor A., ​​dAspremont A., Bolte J. Optimal Complexity and Certification of Bregman First-Order Methods. Arxiv preprint. 2019. 32 p. Available at: https://arxiv.org/abs/1911.08510.

    27. Dvurechensky P., Gasnikov A., Nurminsky E. and Stonyakin F. Advances in Low-Memory Subgradient Optimization. In: A. M. Bagirov et al. (Eds.), Numerical Nonsmooth Optimization, Springer Nature Switzerland AG. 2020. 36 p. Available at: https: / / arxiv.org/abs / 1902.01572vl.

    28. Stonyakin F.S., Alkousa M.S., Titov A.A., Piskunova V. V. On Some Methods for Strongly Convex Optimization Problems with One Functional Constraint. M. Khachav et al. (Eds.). Mathematical Optimization Theory and Operations Research. MOTOR 2019. Lecture Notes in Computer Science. 2019. V. 11548. P. 82-96.

    29. Pasechnyuk D.A., Stonyakin F.S. One method for minimization a convex Lipschitz-continuous function of two variables on a fixed square. Computer Research and Modeling. 2019. V. 11, N 3. P. 379-395. (In Russian).

    Надійшла до редакції 26.12.2019


    Ключові слова: градієнтні методи /ШВИДКИЙ градієнтні методи /АДАПТИВНИЙ МЕТОД /Ліпшиця ГРАДІЄНТ /негладку ОПТИМІЗАЦІЯ /ДЗЕРКАЛЬНИЙ УЗВІЗ /Відносна ЛІПШІЦЕВОСТЬ /Відносна ТОЧНІСТЬ /GRADIENT METHOD /FAST GRADIENT METHOD /ADAPTIVE METHOD /LIPSCHITZ CONTINUOUS GRADIENT /NONSMOOTH OPTIMIZATION /MIRROR DESCENT /RELATIVE LIPSCHITZ CONTINUITY /RELATIVE ACCURACY

    Завантажити оригінал статті:

    Завантажити