Методы оптимизации для негладких задач в пространствах больших размерностей тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Титов Александр Александрович

• Титов Александр Александрович
• кандидат наук
• 2023

Оглавление диссертации кандидат наук Титов Александр Александрович

Введение

Глава 1. Алгоритмы Зеркального Спуска для задач

оптимизации с нестандартными условиями роста целевого функционала

1.1 Краткий очерк истории развития оптимизации и формальная постановка задачи

1.2 Адаптивные модификации метода зеркального спуска

1.2.1 Метод зеркального спуска для выпуклой липшицевой целевой функций

1.2.2 Метод зеркального спуска для целевой функции с нестандартными условия роста

1.3 Алгоритм зеркального спуска для минимизации квазивыпуклой целевой функции

Глава 2. Онлайн и стохастическая постановка задачи оптимизации для относительно липшицевых функционалов

2.1 Методы зеркального спуска для относительно липшицевых функций, допускающих представление в модельной общности

2.1.1 Понятие относительной гладкости и относительной липшицевости функции

2.1.2 Представление относительно липшицевых функций в модельной общности и аналог метода зеркального спуска

2.2 Аналоги метода зеркального спуска для относительно липшицевых функционалов

2.3 Онлайн постановка задачи оптимизации в случае относительно

липшицевых функционалов в модельной общности

2.3.1 Методы зеркального спуска для классической онлайн

постановки задачи оптимизации

2.3.2 Онлайн постановка задачи оптимизации для

относительно липшицевых функций в модельной общности

2.4 Стохастическая постановка задачи оптимизации в случае относительно липшицевых функционалов

2.5 Процедура рестартов метода зеркального спуска для относительно сильно выпуклых задач оптимизации

Глава 3. Численные методы решения вариационных неравенств

3.1 Адаптивный проксимальный метод для вариационных неравенств

3.2 Аналог метода зеркального спуска для относительно ограниченного оператора

3.3 Ускоренные методы для седловых задач е пониженной гладкостью

3.4 Техника рестартов адаптивного проксимального зеркального метода для сильно монотонных вариационных неравенств

Заключение

Список сокращений и условных обозначений

Список литературы

Список рисунков

Список таблиц

Введение диссертации (часть автореферата) на тему «Методы оптимизации для негладких задач в пространствах больших размерностей»

Введение

Необходимость развития численных методов негладкой выпуклой оптимизации в последние годы обусловлена значительным прогрессом в различных областях науки, в том числе, биологии, экономики, химии, прикладной математики, теоретической физики и многих других. Особенной трудностью, прежде всего, в задачах машинного обучения и анализа данных, является большой объем исходной выборки, важность получения как можно более точного решения и минимизации погрешности, а также сложность в вычислении значения функции или ее производных, которые описывают конкретную математическую модель. Последний аспект является особенно актуальным в связи с невозможностью осуществления точной численной оценки разнообразных характеристик функции во многих прикладных задачах. Таким образом, многие классические алгоритмы оптимизации оказываются неприменимыми, например, в случае, если целевая функция является негладкой. Стоит отметить, что на сегодняшний день подавляющее большинство прикладных задач порождают задачи оптимизации именно негладких функций [79, 61, 18].

Хорошо известно, что как выпуклая [88], так и липшицевая [86] функция, является дифференцируемой на своей области определения почти всюду. Тем не менее, для многих прикладных задач с подобными свойствами целевого функционала, методы оптимизации для гладкого случая являются не применимыми. Нетрудно показать [36], что для функции, градиент которой удовлетворяет условию Липшица (далее — для гладкой функции):

||У/(х) -V/Ы||*< Щх - уЦ (1)

выполнено следующее неравенство:

/(У) - /(х) < (х),у - х) + ]2Уж - уу2 Ух, у е йот/. (2)

Естественной попыткой обобщения неравенства (2) является замена второго слагаемого правой части (2), на расстояние в некотором обобщенном смысле. Мотивацией данного подхода являются как трудности с использованием евкли-дового расстояния во многих прикладных задачах (среди которых можно выде-

лить задачу оптимального проектирования, метод опорных векторов для задачи бинарной классификации, задачу о поиске общей точки N заданных эллипсоидов и т.д.), так и преднамеренная замена ||ж — у||2 на расстояние, более адаптированное к конкретной постановке рассматриваемой задачи. Такая идея была предложена в [58] с заменой нормы разности переменных х,у на расстояние в обобщенном смысле, а именно — на дивергенцию Брэгмана. Важным моментом подобного обобщения является сохранение оптимальной скорости сходимости методов первого порядка [58, 57, 4].

Так, одним из основных результатов в данном направлении была недавно предложенная концепция относительной гладкости [58], позволившая, в частности, применить метод градиентного типа для решения задачи о построении оптимального эллипсоида, покрывающего набор заданных точек. Эта задача играет важнейшую роль в статистике и анализе данных [58, 4]. Далее, в [57] была предложена концепция относительной липшицевости, позволившая по новому взглянуть на многие прикладные задачи, среди которых будет рассмотрен метод опорных векторов для задачи бинарной классификации, а также задача о поиске общей точки п заданных эллипсоидов.

Второй проблемой, возникающей при рассмотрении неравенства (2), является невозможность точного вычисления градиента функции /(х). Недавно в [92, 28, 106] было показано, что различные модификации алгоритма зеркального спуска, применимы в случае использования так называемого ^-субградиента, при этом показано, что накопления величины погрешности в итоговых оценках скорости сходимости не происходит. Однако, во многих прикладных задачах затруднительно не только вычисление градиента с некоторой погрешностью, но и само значение целевой функции. Одним из наиболее важных результатов в данном направлении была предложенная в [21] концепция (6, Ь)-оракула, ухудшающая качество решения задачи оптимизации по функции лишь на 0(д).

В первой части диссертации расширяется класс рассмотренных задач, в том числе для абстрактной модели функции, замещающей первое слагаемое (V/(х), у — х) с некоторой погрешностью, при этом допускается, что сама функция представима в абстрактном виде с помощью так называемой модели, позволяющей работать с задачами композитной оптимизации. Стоит отметить, что при этом сохраняются оптимальные оценки скорости сходимости для предложенных методов.

Вторым фокусом диссертации являются вариационные неравенства и сед-ловые задачи с соответствующими уровнями гладкости операторов. Стоит отметить, что вариационные неравенства играют ключевую роль в решении многих прикладных в области гидродинамики [49], проектирования динамических систем [26, 67] экономики, в частности при моделировании сетевого эффекта [66], поиска общего экономического равновесия [45, 26, 38], равновесия Нэша [83], матричных играх [69] и т. д.

Одним из наиболее заметных численных методов решения вариационных неравенств был экстраградиентный метод Г. М. Корпелевич, предложенный в 1976 году [51]. Недавно, объединяя подходы, описанные в [69] и [74] был предложен универсальный численный алгоритм [91], который способен производить автоматическую настройку на уровень гладкости задачи (а именно на параметр v, см. (3) далее). В диссертации этот метод распространяется на условие сильной монотонности оператора в предположениях введенных ранее классах гладкости. Также, рассматривается вариант недавно предложенного [1] ускоренного метода решения седловых задач в негладкой постановке. В частности, для седловых задач предлагается обобщение условия Липшица градиента целевой функции (1) на следующее условие Гельдера:

\\Vf(z) -Vf Lv\\z - , (3)

играющее важную роль в решении многих прикладных задач, таких как задача о многоруком бандите (multi armed bandit problem) [55], задача определения вариабельности сердечного ритма (heart rate variability problem) [68] и др.

Целью данной работы является разработка оптимальных численных методов решения многомерных задач негладкой выпуклой оптимизации с функциональными ограничениями. В качестве базы для разработки методов используются известные методы зеркального спуска и их модификации. Для возможности применения предложенных методов на более широком классе функционалов вводится модификация концепции неточной модели целевого функционала и функционального ограничения. Также исследуется применимость методов для функционалов, удовлетворяющих ослабленному варианту условия Липшица, а именно условию относительно липшицевости функции классической задачи оптимизации и относительной гладкости оператора вариационного неравенства. Также цель диссертации включает в себя разработку модификаций методов для

решения вариационных неравенств и седловых задач соответствующих классов гладкости. В частности, планируется впервые предложить технику рестартов адаптивного проксимального метода для сильно монотонных вариационных неравенств, а также ускоренный метод для негладкой (гельдеровой) седловой задачи.

Для достижения поставленной цели были предложены следующие задачи диссертации:

1. Разработать аналог метода зеркального спуска с переключениями для решения задачи минимизации квазивыпуклых нелипшицевых функций с квазивыпуклыми липшицевыми ограничениями типа неравенств; обосновать соответствующие теоретические оценки скорости сходимости.

2. Расширить применимость методов зеркального спуска на класс относительно липшицевых задач, распространить предложенные модификации метода зеркального спуска для минимизации функций, допускающих представление в абстрактной модельной общности, а также исследовать теоретические характеристики предложенных методов в случае онлайн и стохастической постановки задачи оптимизации относительно липшицевых функционалов.

3. Разработать модификацию алгоритма зеркального спуска для вариационных неравенств с монотонным относительно ограниченным оператором.

4. Предложить технику рестартов адаптивного проксимального зеркального метода для сильно монотонных вариационных неравенств с гель-деровым оператором.

5. Разработать ускоренный алгоритм решения сильно выпукло-вогнутых седловых задач с пониженным уровнем гладкости функционала.

Актуальность данного направления прежде всего обусловлена резким развитием смежных дисциплин, требующих решения задач многомерной оптимизации с минимальными погрешностями. Вопрос оптимизации функционалов большой размерности играет ключевую роль в таких отраслях науки как машинное обучение и анализ данных. Онлайн постановка задачи оптимизации используется в работе с финансовыми рынками, социальными сетями, а также в задачах принятия решений. Введенная концепция относительной липшицевости полез-

на при решении задач обучения с подкреплением. Вариационные неравенства, в свою очередь, являются основным инструментом решения задач общей экономики, поиска рыночного равновесия, а также комплементарных задач (задач дополнительности).

Основные положения, выносимые на защиту:

1. Был разработан аналог алгоритма зеркального спуска для задач оптимизации нелипшицевых квазивыпуклых функций, при наличии квазивыпуклых липшицевых ограничений типа неравенств.

2. Был предложен вариант метода зеркального спуска для задач выпуклого программирования на классе относительно липшицевых задач, включая задачи онлайн оптимизации, а также задачи в стохастической постановке; были получены теоретические оценки скорости сходимости алгоритмов зеркального спуска для решения задачи оптимизации с функциями, допускающими представление в абстрактной модельной общности.

3. Была предложена модификация алгоритма зеркального спуска для вариационных неравенств с монотонным относительно ограниченным оператором, а также доказана оценка скорости сходимости, которую можно считать оптимальной.

4. Была предложена модификация техники рестартов адаптивного проксимального зеркального метода для вариационных неравенств с сильно монотонным гельдеровым оператором и доказана оценка скорости сходимости, являющаяся оптимальной при V = 0 и V = 1.

5. Была описана техника ускорения алгоритма решения сильно выпукло-вогнутых седловых задач с пониженным уровнем гладкости.

Научная новизна:

1. Впервые был предложен аналог метода зеркального спуска с переключениями для задач минимизации квазивыпуклого целевого функционала с квазивыпуклыми липшицевыми ограничениями типа неравенств.

2. Впервые была предложена техника рестартов адаптивного проксимального зеркального метода для сильно монотонных вариационных неравенств с гельдеровыми операторами.

3. Впервые был предложен ускоренный метод для седловой задачи с пониженным уровнем гладкости.

Степень достоверности полученных результатов обусловлена публикацией 12 статей, индексируемых базой Scopus и Web of Science. Ниже приведен список публикаций по материалам диссертации.

1. Bayandina, A., Dvurechensky, P., Gasnikov, A., Stonyakin, F., Titov, A. Mirror Descent and Convex Optimization Problems with Non-smooth Inequality Constraints. In: Giselsson, P., Rantzer, A. (eds) Large-Scale and Distributed Optimization. Lecture Notes in Mathematics. - 2018. - T. 2227. - С. 181-213.

2. F. S. Stonyakin, A. A. Titov. One Mirror Descent algorithm for convex constrained optimization problems with non-standard growth properties.// SchoolSeminar on Optimization Problems and their Applications, OPTA-SCL 2018. CEUR-WS 2018, Vol. 2098, P. 372-384.

3. Titov, A.A., Stonyakin, F.S., Gasnikov, A.V., Alkousa, M.S. Mirror Descent and Constrained Online Optimization Problems. In: Evtushenko, Y., Jacimovic, M., Khachay, M., Kochetov, Y., Malkova, V., Posypkin, M. (eds) Optimization and Applications. OPTIMA 2018. Communications in Computer and Information Science. - 2019. - Т. 974, - С. 64-78.

4. Stonyakin, F. S., Alkousa, M. S., Titov, A. A., Piskunova, V. V. On some methods for strongly convex optimization problems with one functional constraint. In: Khachay, M., Kochetov, Y., Pardalos, P. (eds) Mathematical Optimization Theory and Operations Research. MOTOR 2019. Lecture Notes in Computer Science. - 2019. - Т. 11548, - С. 82-96.

5. Gasnikov, A. V., Dvurechensky, P. E., Stonyakin, F. S., Titov, A. A. An adaptive proximal method for variational inequalities //Computational Mathematics and Mathematical Physics. - 2019. - Т. 59. - №. 5. - С. 836-841.

6. Stonyakin, F. S., Alkousa, M., Stepanov, A. N., Titov, A. A. Adaptive mirror descent algorithms for convex and strongly convex optimization problems with functional constraints //Journal of Applied and Industrial Mathematics. - 2019. - Т. 13. - №. 3. - С. 557-574.

7. Стонякин Ф.С., Степанов А.Н., Гасников А.В., Титов А.А. Метод зеркального спуска для условных задач оптимизации с большими значениями норм субградиентов функциональных ограничений // Компьютерные исследования и моделирование, 2020, т. 12, № 2, с. 301-317

8. Titov, A. A., Stonyakin, F. S., Alkousa, M. S., Ablaev, S. S., Gasnikov, A. V. Analogues of switching subgradient schemes for relatively Lipschitz-continuous convex programming problems In: Kochetov, Y., Bykadorov, I., Gruzdeva, T. (eds) Mathematical Optimization Theory and Operations Research. MOTOR 2020. Communications in Computer and Information Science. - 2020. - Т. 1275. - С. 133-149.

9. Titov, A. A., Stonyakin, F. S., Alkousa, M. S., Gasnikov, A. V. Algorithms for solving variational inequalities and saddle point problems with some generalizations of Lipschitz property for operators In: Strekalovsky, A., Kochetov, Y., Gruzdeva, T., Orlov, A. (eds) Mathematical Optimization Theory and Operations Research: Recent Trends. MOTOR 2021. Communications in Computer and Information Science. - 2021. - Т. 1476. - С. 86-101.

10. Savchuk O.S., Titov A.A., Stonyakin F.S., Alkousa M.S. Adaptive firstorder methods for relatively strongly convex optimization problems // Computer Research and Modeling, 2022, vol. 14, no. 2, pp. 445-472.

11. Ablaev, S. S., Titov, A. A., Stonyakin, F. S., Alkousa, M. S., Gasnikov, A. Some Adaptive First-Order Methods for Variational Inequalities with Relatively Strongly Monotone Operators and Generalized Smoothness. In: Olenev, N., Evtushenko, Y., Jacimovic, M., Khachay, M., Malkova, V., Pospelov, I. (eds) Optimization and Applications. OPTIMA 2022. Lecture Notes in Computer Science. - 2022. - Т. 13781. - С. 135-150.

12. Stonyakin, F., Gasnikov, A., Dvurechensky, P., Titov, A., Alkousa, M. Generalized Mirror Prox Algorithm for Monotone Variational Inequalities: Universality and Inexact Oracle //Journal of Optimization Theory and Applications. - 2022. - С. 1-26.

Апробация работы. Основные результаты работы докладывались на: следующих конференциях, воркшопах и симпозиумах:

1. Всероссийская научная конференция МФТИ, 2018, 2019.

2. 23rd International Symposium on Mathematical Programming (ISMP 2018), Bordeaux, France.

3. International Conference Optimization and Applications (OPTIMA), 2019, 2020 Petrovac, Montenegro.

4. Mathematical Optimization Theory and Operations Research (MOTOR), 2019, 2020, 2021. Novosibirsk, Irkutsk, Russia

5. Quasilinear Equations, Inverse Problems and Their Applications (QIPA), 2018, 2019, 2021, Moscow, Russia.

6. Международный симпозиум по применению численных методов оптимизации для решения обратных задач, 2021, Москва, Россия.

7. Moscow Conference on Combinatorics and Applications, 2021, Долгопрудный, Россия.

8. International Conference "Optimization without Borders", 2021, Sochi, Russia.

Объем и структура работы. Диссертация состоит из введения, трех глав, и заключения.

В первой главе диссертации приведена формальная постановка задачи и предложены некоторые модификации метода зеркального спуска задачи минимизации функций с нестандартными условиями роста. В п. 1.1 описывается краткая история развития оптимизации, а также представлена общая постановка задачи оптимизации и базовые определения, используемые в диссертации. В п. 1.2 рассматривается адаптивная модификация метода зеркального спуска для решения задачи оптимизации с функциональным ограничением:

f (х) ^ min (4)

xEdomj

s.t. д(х) < 0. (5)

со скоростью сходимости О (здесь и далее, если не оговорено обратное, под скоростью сходимости будем понимать количество итераций работы алгоритма, достаточное для достижения ^-точности решения расссматриваемой задачи), в предположении, что целевая функция и функциональное ограничение удовлетворяют условию Липшица. Здесь и далее под £ будем понимать точность решения рассматриваемой задачи.

Далее, в случае, если целевая функция f (х) не удовлетворяет условию Липшица, но имеет липшицев градиент, предлагается соответствующая модификация метода зеркального спуска с аналогичной скоростью сходимости. В п. 1.3 рассматривается случай невыпуклых функций, в том числе, как одновременная квазивыпуклость целевой функции и функционального ограничения, так

и случай квазивыпуклости лишь целевого функционала. Скорость сходимости

В пункте 1.3 обосновывается возможность применения введенной ранее модификации метода зеркального спуска для минимизации квазивыпуклой целевой функции (при этом предполагается, что функциональное ограничение при этом, все еще выпукло), а также предлагается метод для решения задачи (1.6-1.7) в случае, если и целевой функционал /(х), и ограничение д(х) являются квазивыпуклыми.

Вторая глава диссертации прежде всего посвящена обобщению условия Липшица (2) в случае замены нормы разности на расстояние в некотором обобщенном смысле, точнее — на дивергенцию Брэгмана (см. п. 2.1). Таким образом, уже в рамках концепции относительной липшицевости функций:

в пункте 2.2 предлагаются различные адаптивные модификации метода зеркального спуска. Важной особенностью предложенных методов является допущение представления функции в некоторой абстрактной общности, являющейся естественным обобщением предложенной концепции (6, Ь)-модели функции [21]. Также рассматриваются обобщения предложенных методов в случае нескольких функциональных ограничений.

Далее, в п. 2.3 рассмотрены алгоритмы минимизации соответствующих уровней гладкости в случае онлайн постановки задачи, то есть задачи минимизации с функциональным ограничением следующего вида:

Предложенные методы также являются оптимальными [42] с точки зрения того, что количество непродуктивных шагов соизмеримо с общим числом итераций алгоритмов N.

П. 2.4 посвящен стохастической постановке задачи оптимизации с сохранением предположений о гладкости целевой функции и функционального огра-

предложенных методов также составляет О .

(6)

^ Ё ?>(х) ^

(7)

бЛ. д(х) < 0

ничения, более того, предложенные методы также имеют оптимальные оценки скорости сходимости О •

В п. 2.5 рассматривается концепция относительной сильной выпуклости целевой функции:

I(х) — /(у) + ¡IV(у, X) < (V/(х) ,х — у) Ух, у е йот/, (8)

а также предлагается процедура рестартов введенного ранее алгоритма зеркального спуска со скоростью сходимости О ^^^, где М — максимальная константа относительной липшицевости (6) целевой функции Mf и функционального ограничения Мд:

М = шax{Mf ,Мд }. (9)

В главе 3 рассматривается задача поиска решения вариационного неравенства:

шах(д(х),х* — х) < 0, (10)

X

а также седловой задачи

/* = штшах / (х,у). (11)

ж у

В п. 3.1 предлагается адаптивный проксимальный метод решения вариационных неравенств с липшицевым оператором, гарантирующий ^-точное решение за не более, чем О (1) итераций, что является оптимальной оценкой.

В пункте 3.2 предлагается аналог метода зеркального спуска для вариационных неравенств с относительно ограниченным

(д(х),у — х)< М\J22V(у,х), (12)

и монотонным оператором:

(д(у) — 9(х),у — х)> 0, (13)

гарантирующий ^-точное решение задачи (10) за О (^2) итераций.

Далее, в п. 3.3 предлагается ускоренный метод решения седловой задачи (11) в предположении, что градиент целевой функции частично удовлетворяет

условию Гельдера, V € [0,1], при этом по одной переменной является гладким (градиент удовлетворяет условию Липшица):

|УЖ/(х,у) - Vxf(х',у)\\2< ьхх\\х - х' 112, IV,/(х,у) - Vxf)\2< \\у - ,

IV/- VI(^,у)\\2< \\ж - х'\\2,

\VУ I (Х,У ) -VУ / (Х,у')\\2< Ьуу\\у - у'\\2.

(14)

(15)

(16) (17)

При этом количество итераций для достижения ^-точного решения составляет

(Д ■ 108.

\ V I1* V

)

(18)

где

Ь = Ь

(

Ь (1 - ^)(2 - и)

2е

2- и

)

2- ^

£ = £

(Ч^)

У

2-V

+ ЬххО 2

и-иЛ

2-й I ,

(19)

где И — диаметр множества определения /(х, ■).

В п. 3.4 впервые предлагается техника рестартов для вариационных неравенств с гельдеровым сильно монотонным оператором:

(9(х) - 9(У),х - у)> ^\\х - yf,

(20)

при этом допускается, что вычисление оператора, удовлетворяющего условию Гельдера с константой Ь1У, допустимо с некоторыми погрешностями. Скорость сходимости алгоритма при этом составляет

о (( 7)

1+- 2^ О 2^2

1о82-

£

1-^

£

) •

(21)

где О можно понимать как некоторые характеристики рассматриваемого пространства, подробнее см. п. 3.4. Стоит отметить, что для V = 0 скорости сходимости предложенного алгоритма и ускоренного метода (18-19) (см. п. 3.3) совпадают, в то время как для V > 0 асимптотическая скорость сходимость ускоренного метода п. 3.3 является лучшей.

Полный объём диссертации составляет 114 страниц с 1 рисунком и 3 таблицами. Список литературы содержит 111 наименований.

1. Алгоритмы Зеркального Спуска для задач оптимизации с нестандартными условиями роста целевого функционала

Первая глава диссертации посвящена некоторым модификациям метода зеркального спуска для решения задачи оптимизации (1.6-1.7) при различных предположениях о классе гладкости целевого функционала и функционального ограничения. В первом пункте главы 1.1 дано краткое описание истории развития оптимизации, представлена общая постановка задачи оптимизации, а также базовые определения, используемые для теоретического обоснования свойств сходимости методов их решения. Также, в п. 1.1 проанализированы различные варианты обобщений евклидового расстояния с обоснованием их актуальности для решения многих прикладных задач. Во п. 1.2 рассматривается адаптивная модификация метода зеркального спуска в предположении, что целевая функция и функциональное ограничение удовлетворяют условию Липшица. Далее, требование липшицевости целевой функции /(х) заменяется на условие липши-цевости ее градиента V/(х) и предлагается модификация метода зеркального спуска для соответствующего класса гладкости функционалов. В п. 1.3 ослабляется требование к выпуклости целевой функции и функционального ограничения. Также в п. 1.3 обосновывается возможность применения введенной ранее модификации метода зеркального спуска для минимизации квазивыпуклой целевой функции (при этом предполагается, что функциональное ограничение при этом, все еще выпукло), а также предлагается метод для решения задачи (1.6-1.7) в случае, если и целевой функционал /(х), и ограничение д(х) являются квазивыпуклыми.

1.1 Краткий очерк истории развития оптимизации и формальная

постановка задачи

История развития оптимизации берет свое начало с 300-ого года до нашей эры, когда, как известно [110], были сформулированы первые частные случаи изопериметрической задачи. Так, примерно в 300 году до н. э. Евклидом бы-

ла рассмотрена задача поиска кратчайшего расстояние между точкой и прямой, в результате чего он пришел к выводу, что именно квадрат имеет наибольшую площадь среди всех прямоугольников с заданной суммарной длиной ребер. Чуть позже, примерно в 200 году до н. э. Зенодор рассматривает по сути первую задачу вариационного исчисления, а именно задачу Дидоны — поиска фигуры наибольшей возможной площади, граница которой имеет заданную длину и издает трактат "Об изопериметрических фигурах" [99]. Намного позже, в 1615 году Иоганн Кеплер определяет оптимальные размеры винной бочки [101] и таким образом распространяет постановку изопериметрической задачи на трехмерное пространство. Чуть позже Кеплер сформулировал задачу, по своей постановке очень похожую на задачу о разборчивой невесте [30], которая сыграла важную роль в развитии оптимизации.

Очевидно, наибольший толчок в развитии оптимизации произошел во второй половине XVII века, когда был создан аппарат математического анализа и, чуть позже, принципы вариационного исчисления. В начале XIX века А. Ле-жандр и К. Гаусс представляют метод наименьших квадратов [90], на сегодняшний день являющийся одним из самых популярных инструментов регрессионного анализа. Чуть позже, в 1815, английские ученые Томас Мальтус, Роберт Торренс, Эдуард Уэст и Давид Рикардо предложили концепцию квазивыпуклости, сыгравшую важную роль в экономики и финансовой теории (о методах минимизации квазивыпуклых функций речь пойдет в п. 1.3). Основным достижением в области оптимизации XIX века была предложенная О. Коши в 1847 году дискретная итеративная схема, немного позже трансформировавшаяся в один из наиболее известных на сегодняшний день численных методов оптимизации — метод градиентного спуска [15]:

Хк+1 = хк — 7 V/(хк). (1.1)

Дальнейшее развитие оптимизации в XX веке было существенно обусловлено прогрессами в области экономики и финансов. Так, например, в 1952 году Г. Марковиц предложил принцип формирования оптимального портфеля в виде задачи квадратичной оптимизации [62], за что в 1990 получил Нобелевскую премию. Стоит отметить, что оптимизация в XX веке активно развивалась параллельно с выпуклым анализом и базировалось по большей части на работах западных ученых, например, [87, 64, 17], в то время как независимой наукой

оптимизация стала существенно благодаря работам многих отечественных ученых, например, [85, 80, 71]. В последние годы основными драйверами развития теории оптимизации играют, прежде всего, машинное обучение и анализ данных. Так, первый метод с переключениями для классической задачи оптимизации с функциональным ограничением (см. (1.6-1.7) далее) был предложен Б. Т. Поляком в 1967 году [107].

Перейдем к формальной постановке задачи оптимизации. Пусть (Е, ||-||) — некоторое нормированное конечномерное векторное пространство, а Е* — пространство непрерывных линейных функционалов, определенных на Е — его сопряженное. Зададим норму сопряженного пространства следующим образом:

\Мк*= \М\*= швх{(у,х), ЦхЦ< 1}, (1.2)

где под (у, х) будем обозначать значение непрерывного линейного функционала у в точке х € Е.

Здесь и далее, если не оговорено обратное, под нормой \\-\\ будет пониматься абстрактная норма, заданная на соответствующем пространстве.

Рассмотрим выпуклое компактное подмножество X С Е, а также две выпуклые субдифференцируемые функции /(х) : X ^ К и д(х) : X ^ К. Напомним, что понятие выпуклости множества X подразумевает выполнение следующего условия:

Ув € [0,1],Ухъх2 € X : 9х\ + (1 - в)х2 € X. (1.3)

Выпуклость функции /(х), определенной на выпуклом множестве X, в свою очередь, означает, что

¡(вхЛ + (1 - 0)Х2) < в/ (Х1 ) + (1 - 9)/(Х2) УХЪХ2 € Х,в € [0, 1]. (1.4)

Одним из наиболее важных понятий, используемых в диссертации, является свойство липшицевости.

Определение 1.1. Будем говорить, что /(х) удовлетворяет условию Липшица с константой М (или, что функция является М-липшицевой), если

для всех х,у Е X выполнено следующее неравенство:

\f (х) - f (у)\< М||Ж - у\\. (1.5)

Рассмотрим классическую постановку задачи оптимизации с функциональным ограничением:

f (х) ^ min, (1.6)

хЕХ

s.t. g(x) < 0. (1.7)

На сегодняшний день существует большое количество способов решения задачи (1.6-1.7), среди которых одним из наиболее известных является метод множителей Лагранжа, гарантирующий необходимое условие решения задачи. Определив функцию Лагранжа следующим образом

Список литературы диссертационного исследования кандидат наук Титов Александр Александрович, 2023 год

Список литературы

[1] Mohammad S Alkousa, Alexander Vladimirovich Gasnikov, Darina Mikhailovna Dvinskikh, Dmitry A Kovalev и Fedor Sergeevich Stonyakin. "Accelerated methods for saddle-point problem". В: Computational Mathematics and Mathematical Physics 60.11 (2020), с. 1787—1809.

[2] Fatima Ardjani, Kaddour Sadouni и Mohamed Benyettou. "Optimization of SVM multiclass by particle swarm (PSO-SVM)". В: 2010 2nd International Workshop on Database Technology and Applications. IEEE. 2010, с. 1—4.

[3] Didier Aussel и Joydeep Dutta. "Generalized Nash equilibrium problem, variational inequality and quasiconvexity". В: Operations research letters 36.4 (2008), с. 461—464.

[4] Heinz H Bauschke, Jerome Bolte и Marc Teboulle. "A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications". В: Mathematics of Operations Research 42.2 (2017), с. 330—348.

[5] A. Bayandina, P. Dvurechensky, A. Gasnikov, F. Stonyakin и A. Titov. "Mirror Descent and Convex Optimization Problems With Non-Smooth Inequality Constraints". В: LCCC Focus Period on Large-Scale and Distributed Optimization (2018), с. 181—213.

[6] A. Beck и M. Teboulle. "Mirror descent and nonlinear projected subgradient methods for convex optimization". В: Operations Research Letters 31.3 (2003), с. 167—175.

[7] Amir Beck и Marc Teboulle. "A fast iterative shrinkage-thresholding algorithm for linear inverse problems". В: SIAM journal on imaging sciences 2.1 (2009), с. 183—202.

[8] A. Ben-Tal, T. Margalit и A. Nemirovski. "The ordered subsets mirror descent optimization method with applications to tomography". В: SIAM Journal on Optimization 12.1 (2001), с. 79—108.

[9] Aaron Ben-Tal и Arkadi Nemirovski. "Lectures on modern convex optimization (Lecture notes)". В: Personal web-page of A. Nemirovski (2015).

[10] Aharon Ben-Tal h Arkadi Nemirovski. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. SIAM, 2001.

[11] Stephen Boyd, Stephen P Boyd h Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.

[12] Marcus Brazil, Ronald L Graham, Doreen A Thomas h Martin Zachariasen. "On the history of the Euclidean Steiner tree problem". B: Archive for history of exact sciences 68.3 (2014), c. 327—354.

[13] Sebastien Bubeck, Nicolo Cesa-Bianchi h gp. "Regret analysis of stochastic and nonstochastic multi-armed bandit problems". B: Foundations and Trends® in Machine Learning 5.1 (2012), c. 1—122.

[14] Sebastien Bubeck h Ronen Eldan. "Multi-scale exploration of convex functions and bandit convex optimization". B: Conference on Learning Theory. PMLR. 2016, c. 583—589.

[15] Augustin Cauchy h gp. "Methode generale pour la resolution des systemes d'equations simultanees". B: Comp. Rend. Sci. Paris 25.1847 (1847), c. 536— 538.

[16] F. Clarke. Optimization and non-smooth analysis. New York: John Wiley h Sons, 1983.

[17] Frank H Clarke. "Generalized gradients and applications". B: Transactions of the American Mathematical Society 205 (1975), c. 247—262.

[18] Frank H Clarke. Method of Dynamic and Nonsmooth Optimization. SIAM, 1989.

[19] Cong D. Dang h Guanghui Lan. "Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimization". B: SIAM J. on Optimization 25.2 (2015), c. 856—881. DOI: 10.1137/130936361.

[20] Gerard Debreu h Tjalling C Koopmans. "Additively decomposed quasiconvex functions". B: Mathematical Programming 24.1 (1982), c. 1—38.

[21] Olivier Devolder, Francois Glineur h Yurii Nesterov. "First-order methods of smooth convex optimization with inexact oracle". B: Mathematical Programming 146.1 (2014), c. 37—75.

[22] Olivier Devolder, Frangois Glineur, Yurii Nesterov h gp. "First-order methods with inexact oracle: the strongly convex case". B: CORE Discussion Papers 2013016 (2013), c. 47.

[23] Kai-Bo Duan h S Sathiya Keerthi. "Which is the best multiclass SVM method? An empirical study". B: International workshop on multiple classifier systems. Springer. 2005, c. 278—285.

[24] John Duchi, Elad Hazan h Yoram Singer. "Adaptive subgradient methods for online learning and stochastic optimization." B: Journal of machine learning research 12.7 (2011).

[25] John C Duchi, Shai Shalev-Shwartz, Yoram Singer h Ambuj Tewari. "Composite Objective Mirror Descent." B: 10 (2010), c. 14—26.

[26] Paul Dupuis h Anna Nagurney. "Dynamical systems and variational inequalities". B: Annals of Operations Research 44.1 (1993), c. 7—42.

[27] Pavel Dvurechensky h Alexander Gasnikov. "Stochastic intermediate gradient method for convex problems with stochastic inexact oracle". B: Journal of Optimization Theory and Applications 171.1 (2016), c. 121—145.

[28] Pavel E Dvurechensky, Alexander V Gasnikov, Evgeni A Nurminski h Fedor S Stonyakin. "Advances in low-memory subgradient optimization". B: Numerical Nonsmooth Optimization. Springer, 2020, c. 19—59.

[29] Francisco Facchinei h Jong-Shi Pang. Finite-dimensional variational inequalities and complementarity problems. Springer, 2003.

[30] Thomas S Ferguson. "Who solved the secretary problem?" B: Statistical science 4.3 (1989), c. 282—289.

[31] Cedric Fevotte, Nancy Bertin h Jean-Louis Durrieu. "Nonnegative matrix factorization with the Itakura-Saito divergence: With application to music analysis". B: Neural computation 21.3 (2009), c. 793—830.

[32] Abraham D Flaxman, Adam Tauman Kalai h H Brendan McMahan. "Online convex optimization in the bandit setting: gradient descent without a gradient". B: arXiv preprint cs/0408007 (2004).

[33] Alexander Gasnikov, Anastasia Lagunovskaya h Larisa Morozova. "On the relationship between imitative logit dynamics in the population game theory and mirror descent method in the online optimization using the example of the Shortest Path Problem". B: arXiv preprint arXiv:1511.02398 (2015).

[34] Alexander V Gasnikov, Ekaterina A Krymova, Anastasia A Lagunovskaya, Ilnura N Usmanova h Fedor A Fedorenko. "Stochastic online optimization. Single-point and multi-point non-linear multi-armed bandits. Convex and strongly-convex case". B: Automation and remote control 78.2 (2017), c. 224— 234.

[35] Alexander Vladimirovich Gasnikov, PE Dvurechensky, Fedor Sergeevich Stonyakin h Aleksandr Aleksandrovich Titov. "An adaptive proximal method for variational inequalities". B: Computational Mathematics and Mathematical Physics 59.5 (2019), c. 836—841.

[36] AV Gasnikov. "Modern numerical optimization methods". B: The method of universal gradient descent. Moscow: MIPT (2018).

[37] F. Giannessi. "On Minty Variational Principle". B: New Trends in Mathematical Programming. Applied Optimization 13 (1997), c. 93—99.

[38] Franco Giannessi h Antonino Maugeri. Variational inequalities and network equilibrium problems. Springer, 1995.

[39] Cristobal Guzman h Arkadi Nemirovski. "On lower complexity bounds for large-scale smooth convex optimization". B: Journal of Complexity 31.1 (2015), c. 1—14.

[40] Nicolas Hadjisavvas, Sandor Komlosi h Siegfried S Schaible. Handbook of generalized convexity and generalized monotonicity. T. 76. Springer Science & Business Media, 2006.

[41] Elad Hazan h gp. "Introduction to online convex optimization". B: Foundations and Trends® in Optimization 2.3-4 (2016), c. 157—325.

[42] Elad Hazan h Satyen Kale. "Beyond the regret minimization barrier: an optimal algorithm for stochastic strongly-convex optimization". B: Proceedings of the 24th Annual Conference on Learning Theory. JMLR Workshop h Conference Proceedings. 2011, c. 421—436.

[43] Elad Hazan, Kfir Levy и Shai Shalev-Shwartz. "Beyond convexity: Stochastic quasi-convex optimization". В: Advances in neural information processing systems 28 (2015).

[44] Zhaolin Hu и L Jeff Hong. "Kullback-Leibler divergence constrained distributionally robust optimization". В: Available at Optimization Online (2013), с. 1695—1724.

[45] Alejandro Jofre, R Terry Rockafellar и Roger JB Wets. "Variational inequalities and economic equilibrium". В: Mathematics of Operations Research 32.1 (2007), с. 32—50.

[46] Lee K Jones и Charles L Byrne. "General entropy criteria for inverse problems, with applications to data compression, pattern classification, and cluster analysis". В: IEEE transactions on Information Theory 36.1 (1990), с. 23—30.

[47] Anatoli Juditsky, Arkadi Nemirovski и др. "First order methods for nonsmooth convex large-scale optimization, i: general purpose methods". В: Optimization for Machine Learning 30.9 (2011), с. 121—148.

[48] Leonid G Khachiyan и Michael J Todd. On the complexity of approximating the maximal inscribed ellipsoid for a polytope. Тех. отч. Cornell University Operations Research и Industrial Engineering, 1990.

[49] David Kinderlehrer и Guido Stampacchia. An introduction to variational inequalities and their applications. SIAM, 2000.

[50] Diederik P Kingma и Jimmy Ba. "Adam: A method for stochastic optimization". В: arXiv preprint arXiv:1412.6980 (2014).

[51] Galina M Korpelevich. "The extragradient method for finding saddle points and other problems". В: Matecon 12 (1976), с. 747—756.

[52] Walid Krichene, Alexandre Bayen и Peter L Bartlett. "Accelerated mirror descent in continuous and discrete time". В: Advances in neural information processing systems 28 (2015).

[53] Solomon Kullback. Information theory and statistics. Courier Corporation, 1997.

[54] Guanghui Lan, Arkadi Nemirovski h Alexander Shapiro. "Validation analysis of mirror descent stochastic approximation method". B: Mathematical programming 134.2 (2012), c. 425—458. DOI: 10.1007/s10107-011-0442-6.

[55] Yusha Liu, Yining Wang h Aarti Singh. "Smooth Bandit Optimization: Generalization to Holder Space". B: International Conference on Artificial Intelligence and Statistics. PMLR. 2021, c. 2206—2214.

[56] Rodolfo Lourenzutti h Renato A Krohling. "The Hellinger distance in multicriteria decision making: an illustration to the TOPSIS and TODIM methods". B: Expert Systems with Applications 41.9 (2014), c. 4414—4421.

[57] Haihao Lu. ""Relative continuity" for non-lipschitz nonsmooth convex optimization using stochastic (or deterministic) mirror descent". B: INFORMS Journal on Optimization 1.4 (2019), c. 288—303.

[58] Haihao Lu, Robert M Freund h Yurii Nesterov. "Relatively smooth convex optimization by first-order methods, and applications". B: SIAM Journal on Optimization 28.1 (2018), c. 333—354.

[59] Mario Lucic, Olivier Bachem h Andreas Krause. "Strong coresets for hard and soft Bregman clustering with applications to exponential family mixtures". B: Artificial intelligence and statistics. PMLR. 2016, c. 1—9.

[60] Robert J Lyon, JM Brooke, Joshua D Knowles h Benjamin W Stappers. "Hellinger distance trees for imbalanced streams". B: 2014 22nd International Conference on Pattern Recognition. IEEE. 2014, c. 1969—1974.

[61] Marko M Makela h Pekka Neittaanmaki. Nonsmooth optimization: analysis and algorithms with applications to optimal control. World Scientific, 1992.

[62] Harry Markowitz. "Selection, Portfolio". B: The Journal of Finance 7.1 (1952), c. 77—91.

[63] Elisa Mastrogiacomo h Emanuela Rosazza Gianin. "Portfolio optimization with quasiconvex risk measures". B: Mathematics of Operations Research 40.4 (2015), c. 1042—1059.

[64] Jean-Jacques Moreau. "Application of convex analysis to the treatment of elastoplastic systems". B: Applications of methods of functional analysis to problems in mechanics. Springer, 1976, c. 56—89.

[65] Pedro Moreno, Purdy Ho h Nuno Vasconcelos. "A Kullback-Leibler divergence based kernel for SVM classification in multimedia applications". B: Advances in neural information processing systems 16 (2003).

[66] Anna Nagurney. Network economics: A variational inequality approach. T. 10. Springer Science & Business Media, 1998.

[67] Anna Nagurney h Ding Zhang. Projected dynamical systems and variational inequalities with applications. T. 2. Springer Science & Business Media, 1995.

[68] Toru Nakamura, Hiroyuki Horio h Yoshihide Chiba. "Local holder exponent analysis of heart rate variability in preterm infants". B: IEEE Transactions on biomedical engineering 53.1 (2005), c. 83—88.

[69] Arkadi Nemirovski. "Prox-method with rate of convergence O (1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems". B: SIAM Journal on Optimization 15.1 (2004), c. 229—251.

[70] Arkadij Semenovic Nemirovskij h David Borisovich Yudin. "Problem complexity and method efficiency in optimization". B: (1983).

[71] AS Nemirovsky. "Interior point polynomial methods in convex programming". B: (1996).

[72] Y. Nesterov. "Subgradient methods for convex functions with nonstandard growth properties". B: (2018). URL: https ://www . mathnet . ru : 8080 / PresentFiles/16179/growthbm_nesterov.pdf.

[73] Yu Nesterov. "Gradient methods for minimizing composite functions". B: Mathematical programming 140.1 (2013), c. 125—161.

[74] Yu Nesterov. "Universal gradient methods for convex optimization problems". B: Mathematical Programming 152.1 (2015), c. 381—404.

[75] Yu E Nesterov. "Effective methods in nonlinear programming". B: Moscow, Radio i Svyaz (1989).

[76] Yurii Nesterov. "Dual extrapolation and its applications to solving variational inequalities and related problems". B: Mathematical Programming 109.2-3 (2007). First appeared in 2003 as CORE discussion paper 2003/68, c. 319— 344.

[77] Yurii Nesterov. Introductory lectures on convex optimization: A basic course. T. 87. Springer Science & Business Media, 2003.

[78] Yurii Nesterov. "Primal-dual subgradient methods for convex problems". B: Mathematical Programming 120.1 (2009), c. 221—259.

[79] Yurii Nesterov. "Relative smoothness: new paradigm in convex optimization". B: Conference report, EUSIPCO-2019, A Coruna, Spain. T. 4. 2019.

[80] Yurii E Nesterov. "A method for solving the convex programming problem with convergence rate O (1/k" 2)". B: Dokl. akad. nauk Sssr. T. 269. 1983, c. 543—547.

[81] Luca Oneto, Sandro Ridella h Davide Anguita. "Tikhonov, Ivanov and Morozov regularization for support vector machine learning". B: Machine Learning 103.1 (2016), c. 103—136.

[82] Francesco Orabona, Koby Crammer h Nicolo Cesa-Bianchi. "A generalized online mirror descent with applications to classification and regression". B: Machine Learning 99.3 (2015), c. 411—435.

[83] Jong-Shi Pang h Masao Fukushima. "Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games". B: Computational Management Science 2.1 (2005), c. 21—56.

[84] John Platt. "Sequential minimal optimization: A fast algorithm for training support vector machines". B: (1998).

[85] Boris T Polyak. "Some methods of speeding up the convergence of iteration methods". B: Ussr computational mathematics and mathematical physics 4.5 (1964), c. 1—17.

[86] Hans Rademacher. "Über partielle und totale differenzierbarkeit von Funktionen mehrerer Variabeln und über die Transformation der Doppelintegrale". B: Mathematische Annalen 79.4 (1919), c. 340—359.

[87] R Tyrrell Rockafellar. Convex analysis. T. 18. Princeton university press, 1970.

[88] Laurent Schwartz. "Analyse mathematique". B: (1967).

[89] Shai Shalev-Shwartz h gp. "Online learning and online convex optimization". B: Foundations and Trends® in Machine Learning 4.2 (2012), c. 107—194.

[90] Harold W Sorenson. "Least-squares estimation: from Gauss to Kalman". B: IEEE spectrum 7.7 (1970), c. 63—68.

[91] Fedor Stonyakin, Alexander Gasnikov, Pavel Dvurechensky, Alexander Titov h Mohammad Alkousa. "Generalized Mirror Prox Algorithm for Monotone Variational Inequalities: Universality and Inexact Oracle". B: Journal of Optimization Theory and Applications (2022), c. 1—26.

[92] Fedor S Stonyakin. "Adaptive Mirror Descent Methods for Convex Programming Problems with delta-subgradients". B: arXiv preprint arXiv:2012.12856 (2020).

[93] Fedor S Stonyakin, Darina Dvinskikh, Pavel Dvurechensky, Alexey Kroshnin, Olesya Kuznetsova, Artem Agafonov, Alexander Gasnikov, Alexander Tyurin, Cesar A Uribe, Dmitry Pasechnyuk h gp. "Gradient methods for problems with inexact model of the objective". B: International Conference on Mathematical Optimization Theory and Operations Research. Springer. 2019, c. 97—114.

[94] Peng Sun h Robert M Freund. "Computation of minimum-volume covering ellipsoids". B: Operations Research 52.5 (2004), c. 690—706.

[95] Tijmen Tieleman, Geoffrey Hinton h gp. "Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude". B: COURSERA: Neural networks for machine learning 4.2 (2012), c. 26—31.

[96] Alexander A Titov, Fedor S Stonyakin, Mohammad S Alkousa, Seydamet S Ablaev h Alexander V Gasnikov. "Analogues of switching subgradient schemes for relatively Lipschitz-continuous convex programming problems". B: International Conference on Mathematical Optimization Theory and Operations Research. Springer. 2020, c. 133—149.

[97] Alexander A Titov, Fedor S Stonyakin, Mohammad S Alkousa h Alexander V Gasnikov. "Algorithms for solving variational inequalities and saddle point problems with some generalizations of Lipschitz property for operators". B: International Conference on Mathematical Optimization Theory and Operations Research. Springer. 2021, c. 86—101.

[98] Alexander A Titov, Fedor S Stonyakin, Alexander V Gasnikov и Mohammad S Alkousa. "Mirror descent and constrained online optimization problems". В: International Conference on Optimization and Applications. Springer. 2018, с. 64—78.

[99] Gerald J Toomer. "The Mathematician Zenodorus". В: Greek, Roman, and Byzantine Studies 13.2 (1972), с. 177—192.

[100] Deming Yuan, Yiguang Hong, Daniel W.C. Ho и Guoping Jiang. "Optimal Distributed Stochastic Mirror Descent for Strongly Convex Optimization". В: arXiv:1610.04702 (2016). URL: https://arxiv.org/pdf/1610.04702.pdf.

[101] Ivan Zelinka, Vaclav Snasael и Ajith Abraham. Handbook of optimization: from classical to modern approach. Т. 38. Springer Science & Business Media, 2012.

[102] Junyu Zhang, Mingyi Hong и Shuzhong Zhang. "On lower iteration complexity bounds for the convex concave saddle point problems". В: Mathematical Programming 194.1 (2022), с. 901—935.

[103] Martin Zinkevich. "Online convex programming and generalized infinitesimal gradient ascent". В: Proceedings of the 20th international conference on machine learning (icml-03). 2003, с. 928—936.

[104] А. С. Немировский и Д. Б. Юдин. "Сложность задач и эффективность методов оптимизации". В: Наука (1979).

[105] Аркадий Семенович Немировский и Юрий Евгеньевич Нестеров. "Оптимальные методы гладкой выпуклой минимизации". В: Журнал вычислительной математики и математической физики 25.3 (1985), с. 356— 369.

[106] Б. Т. Поляк. "Введение в оптимизацию". В: Наука (1983).

[107] Борис Теодорович Поляк. "Один общий метод решения экстремальных задач". В: Доклады Академии наук. Т. 174. 1. Российская академия наук. 1967, с. 33—36.

[108] Ф. С. Стонякин, А. Н. Степанов, А. В. Гасников и А. А. Титов. "Метод зеркального спуска для условных задач оптимизации с большими значениями норм субградиентов функциональных ограничений". В: Компьютерные Исследования и Моделирование 12.2 (2020), с. 301—317.

[109] Федор Сергеевич Стонякин, Мохаммад С Алкуса, Алексей Николаевич Степанов и Максим Александрович Баринов. "Адаптивные алгоритмы зеркального спуска в задачах выпуклого программирования с липшице-выми ограничениями". В: Труды Института математики и механики УрО РАН 24.2 (2018), с. 266—279. DOI: 10.21538/0134-4889-2018-24-2266-279.

[110] Владимир Тихомиров. Рассказы о максимумах и минимумах. Litres, 2022.

[111] Александр Игоревич Тюрин и Александр Владимирович Гасников. "Быстрый градиентный спуск для задач выпуклой минимизации с оракулом, выдающим ( 5, L)-модель функции в запрошенной точке". В: arXiv preprint arXiv:1711.02747 (2017).

Список рисунков

1 Результаты работы Алгоритмов 6, 7, 8, 9 для задачи

Ферма-Торричелли-Штейнера..................... 57

Список таблиц

1 Результаты работы Алгоритма 18 с параметрами

п = 1000, т = 50, N =10 для Примеров 1,2............. 98

2 Результаты работы Алгоритма 18 с параметрами

п = 1000, т = 50, N =10 для Примеров 3,4............. 99

3 Результаты работы Алгоритма 18 с параметрами

п = 1000, т = 50, N =10 для Примера 5............... 99