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

• Макаренко Дмитрий Владимирович
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Макаренко Дмитрий Владимирович

Введение

Глава 1. Современные численные методы оптимизации: обзор

литератyры

1.1 Введение

1.2 Стохастический градиентный спуск для распределенных задач

при наличии компрессии

1.3 Задача о локальной минимизации силового поля для трехмерного представления макромолекул

1.3.1 Проблематика задачи

1.3.2 Постановка задачи

1.3.3 Возможные подходы к решению задачи. Особенности применения градиентного метода

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

1.3.5 Методы одномерного поиска

1.3.6 Результаты экспериментов

Глава 2. Методы типа зеркального спуска для относительно

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

2.1 Введение

2.2 Субградиентный метод для вариационных неравенств с относительно сильно монотонными и ограниченными операторами

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

2.4 Адаптивная оценка скорости сходимости одного субградиентного метода для сильно выпуклых задач и вычислительные эксперименты для задачи о наименьшем покрывающем шаре

Глава 3. Рестарты зеркального спуска для относительно

липшицевых задач с условием у-роста

3.1 Введение

Стр.

3.2 Экспериментальное сравнение скорости сходимости для задачи поиска покрывающего шара наименьшего радиуса двух субградиентных методов при различных дополнительных условиях

3.3 Рестарты зеркального спуска для выпуклых относительно липшицевых задач, удовлетворяющих условию относительного

у-роста

3.4 Адаптивный критерий остановки каждого из рестартов

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

Заключение

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

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

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

Введение

Задачи оптимизации применяются в самых разных областях человеческой деятельности от экономики до машинного обучения. Например, методы оптимизации позволяют решать системы уравнений, моделировать экономические процессы, обучать нейросети и анализировать риски в банках. Такое многообразие приложений связано с тем, что задача оптимизации - это поиск лучшего доступного решения, которое удовлетворяет требованиям исследуемой модели. Методы оптимизации предлагают обширный выбор инструментов, которые распределены по характеристикам моделей и предъявляемых к ней ограничений. Общая постановка задачи минимизации имеет вид

min f (x).

xeQ J

Здесь и всюду далее n — это размерность пространства переменных, а Q — выпуклое замкнутое подмножество Rn. Учет размерности задачи в современном мире стал необходимостью, поскольку модели усложняются и количество учитываемых параметров растет экспоненциально. Подобный рост размерности привел к росту популярности численных методов оптимизации градиентного типа. Речь о методах, в которых на итерациях может использоваться информация о значении целевой функции ее градиента. К недостаткам данного типа методов можно отнести необходимость прибегать к информации о функциональных свойствах для исследуемых задач, таких как гладкость, липшицевость и сильная выпуклость. Напомним определения используемых далее функционального свойства. Одним из них является условие Липшица вида

\f (y) - f (x)| ^ M\\y - x||2 Vx,y e Q

при некотором фиксированном M > 0, а норма \ \2 — это евклидова норма. Гладкость целевой функции определяется как условие Липшица для градиента:

\\Vf (x) - Vf (y)\\2 ^ L\\x - y\\2 Ух, y e Q

при некотором фиксированном L > 0. Данное условие влечет неравенство, более часто применяемое на практике,

f (у) ^ f (х) + Vf (x),y - х) + L\\х - y\\2 Ух,у e Q. (1)

Часто полезным будет свойство сильной выпуклости функции [5]:

/ (Лх+(1 - Л)у) ^

Л/(х) + (1 - Л)/(у) - |Л(1 - Л)\\х - у\\2 Чх, у е Я,

где 0 ^ Л ^ 1, для некоторого > 0, называемого константой сильной выпуклости. Для таких функций верно неравенство

/(х) + {V/(х),у - х) + |\\х - у\\2 ^ /(у) Чх, у е Я. (2)

Одна из причин популярности градиентных методов - это низкая затратность и возможность отказаться в оценках скорости сходимости от размерности задачи, что делает их применение эффективным для многих задач. В широком смысле под эффективностью метода оптимизации понимается время, необходимое для получения достаточно хорошего решения. Однако, подобная величина зависит от огромного количества аспектов, не имеющих прямого отношения к алгоритму поиска достаточно хорошего решения. Такими аспектами могут являться мощность вычислительного устройства, доступная точность представления чисел, необходимое количество памяти и т.д. Чтобы разделить технический и теоретический аспекты, под эффективностью численного метода оптимизации на определенном классе задач часто понимают именно эффективность в смысле Бахвалова-Немировского [6] — число обращений по ходу работы метода к оракулу, достаточное для достижения приемлемой точности. Оракулом называется подпрограмма расчета значений целевой функции (градиента, гессиана или некоторой заменяющей их величины) с необходимой точностью. Как правило, данное обращение является наиболее «дорогостоящей» частью шага. В некоторых ситуациях оптимизация работы оракула является необходимостью для приемлемой работы метода, этот аспект будет более подробно обсуждаться на примере в рамках 1й главы в пункте 1.3.5.

Таким образом, аналитическая сложность оптимизационной задачи для метода на заданном классе характеризуется количеством запросов к оракулу для гарантии нахождения приближенного решения с заранее заданной точностью £ > 0. Что можно более формально описать

\\хм - х*\\2 < £,

где хN — точка выхода алгоритма после N итераций используемого метода, а х* — искомое точное решение задачи. Также часто рассматривают точность с точки

зрения значения функции, а именно

\f (xn) - f (ж*)\ < е-

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

Существует несколько типов оракульных оценок:

- верхняя — количество обращений к оракулу не более данного значения (хуже не будет),

- нижняя — не менее данного числа обращений (лучше не будет),

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

Ранее многие задачи относились к задачам небольшой размерности, но в последнее время размерность задач увеличивается. Задачей небольшой размерности обычно называют задачу, когда возможно N ^ n, где N — количество обращений к оракулу, а n — размерность пространства. На практике к задачам небольшой размерности можно отнести задачи, имеющие размерность в несколько сотен. Неплохую эффективность для таких задач имеют методы секущей гиперплоскости, к которым относятся метод центров тяжести и метод эллипсоидов. Однако их оптимальные оценки N ~ O (n log n) существенно зависят от размерности пространства [7]. Эта зависимость приводит к высоким требованиям по необходимой памяти и необходимости увеличения количества итераций с ростом размерности пространства для сохранения той же точности. Градиентные методы в противоположность им обладают сравнительно скромными требованиями по необходимой памяти, и соответствующие оценки не зависят от размерности задачи. Отметим также, что лучшие верхние оценки на классе гладких выпуклых функций известны для ускоренных методов [8].

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

В таблице 1 R — это ||жо — ж*||2, а х0 — стартовая точка алгоритма. Как видим, оценки в гладком случае существенно лучше, чем в негладком. В слу-

Таблица 1 — Оптимальные оценки количества обращений к субградиенту.

\/(у) - !(х)| ^ ^ М Цу - х 112 ЦЧ/(у) -V/(х)||2 < < Ь\\у - х112

/(х) - выпукла о ()

/(х) - ^-сильно выпукла в || • || 2 - норме о (М) о (^ [ш])

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

Напомним, что для негладких задач в качестве обобщения понятия градиента рассматривают понятие субградиента. Вектор д называют субградиентом в точке х0, если

/(х) ^ /(хо) + {д,х - хо) Ух е Я.

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

Отметим важное и развиваемое в данной работе обобщение оптимальных результатов для субградиентного метода на случай задачи с аналогом условия Липшица относительно некоторой выпуклой прокс-функции (относительная липшицевость). Такая прокс-функция, в отличие от классической постановки, не обязана удовлетворять условию сильной выпуклости относительно нормы [10—12]. Напомним важное понятие дивергенции (расхождения) Брэгмана. Предполагается, что нам доступна некоторая выпуклая (вообще говоря, не сильно

выпуклая) дифференцируемая прокс-функция й, порождающая некоторое расстояние, и соответствующая ей дивергенция (расхождение) Брэгмана [13]

V (у, х) = й(у) — й(х) — (Чй(х) ,у — х).

При помощи дивергенции Брэгмана вводятся такие необходимые понятия, как относительная липишицевость, относительная сильная выпуклость, относительная гладкость и условие относительного у-роста. Например, свойство относительной Ь-гладкости функции / обобщает условие Ь-гладкости / (см. (1)), где квадрат евклидовой нормы в определении заменяется дивергенцией Брэгмана

I(у) < I(х) + {V/(х),у — х) + IV(у,х) Ух,у е Я,

где Я — область определения /.

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

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

т&х{д(х),х* — х) ^ 0,

где х* называют слабым решением вариационного неравенства, Я — выпуклое замкнутое подмножество д : Я —^ Предполагается, что решение х* существует. Такая постановка приводит к существенно более широкому классу задач, чем минимизационные задачи. Класс вариационных неравенств имеет достаточно широкую область применения в различных областях математики, таких как теория игр, моделирование потоков и математическая экономика.

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

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

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

Задачи, решаемые в данной диссертации:

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

2. Экспериментальный анализ методов безградиентного, градиентного и квазинютоновского типов для работы с невыпуклым, вообще говоря, функционалом специальной структуры, а именно практический анализ возможностей эффективной оптимизации для задачи минимизации белка, имеющей различные физические основания, OPLS force field.

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

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

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

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

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

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

3. Впервые получены оценки скорости сходимости рестартованного метода зеркального спуска для относительно липшицевых задач оптимизации с относительным у-ростом при у > 1.

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

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

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

3. Введён аналог острого минимума (у-роста) с использованием дивергенции Брэгмана. Получена оценка скорости сходимости рестартованного метода зеркального спуска для относительно липшицевых задач оптимизации с относительным у-ростом. В ситуации сильно выпуклой прокс-функции предложены адаптивные правила остановки для рестартов исследуемого метода зеркального спуска и получен результат о его скорости сходимости.

Апробация работы. Основные результаты работы докладывались на:

- проектной смене «Современные методы теории информации, оптимизации и управления» в центре «Сириус», 2021,

- QIPA (Quasilinear Equations, Inverse Problems and Their Applications), 2021,

- 64-й всероссийской научной конференции МФТИ, 2021,

- QIPA (Quasilinear Equations, Inverse Problems and Their Applications), 2018,

- 61-й всероссийской научной конференции МФТИ, 2018.

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

Публикации. Основные результаты по теме диссертации изложены в 4 печатных изданиях ,3 — в периодических научных журналах, индексируемых Web of Science или Scopus, 1 — в тезисах докладов.

Объем и структура работы. Диссертация состоит из введения, 3 глав и заключения. Полный объём диссертации составляет 90 страниц, включая 12 рисунков и 2 таблицы. Список литературы содержит 86 наименований.

Глава 1. Современные численные методы оптимизации: обзор литератyры.

1.1 Введение

Многие прикладные задачи обладают сложной внутренней структурой, которая не позволяет эффективно применять к ним теоретические методы без значительной их модификации. С ростом популярности нейронных сетей, повышением сложности экономических моделей, развитием компиляторных оптимизаций все чаще происходит столкновение теоретической постановки с задачей распределения ресурсов, представленной в различных формах. Часто на практике присутствует существенный набор специальных ограничений, дополнительно усложняют работу плохо определенные минимизируемые функционалы (различные loss-функции, к примеру). Многие из важных прикладных задач теряют свойство выпуклости, и тем более гладкость. Частично об этой проблеме говорит рост популярности адаптивных методов, которые подстраиваются к локальным значениям гладкости (см. например [10; 15; 16]). В случае такой общей постановки задачи список методов, которые можно эффективно применять, сильно ограничен. В подобных ситуациях не всегда есть гарантии сходимости, не говоря уже о гарантиях хороших верхних оценок. Значительную роль в подборе метода играет проблема роста размерности, например, при использовании «покомпонентного спуска» каждая итерация пропорциональна размерности пространства, что вносит более значимый вклад в скорость сходимости по сравнению с градиентными аналогами. В связи с чем возникает естественное желание расширить допустимый класс задач для которых возможно эффективно применять хорошо исследованные методы первого порядка.

Также получила широкое распространение методика аппроксимации задачи к некоторому гладкому аналогу целевой выпуклой функции. Эту идею используют известные универсальные методы в таких работах как [17; 18]. Универсальные градиентные методы основаны на квадратичной интерполяции целевой функции для выпуклой оптимизации с гельдеровым градиентом, они используют искусственную погрешность для подстройки константы Гельдера. Универсальность в данном случае подразумевает подстройку метода под гладкость функции. К подобным подходам, когда пытаются выделить некоторые локальные свойства

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

Анализ известных теорем об оптимальных оценках сформулированных для различных методов первого порядка, показывает, что ряд свойств, которые требуются для достижения соответствующей оценки, допускают существенные обобщения, свойственные для достаточно интересных классов задач. Это и привело в частности к появлению ряда работ [11; 19—21], которые переходят к «относительной липшицевости» и постановке задачи в терминах вариационных неравенств. Подобный подход будет развит в последующих главах, здесь мы не будем подробно останавливаться на данном направлении.

Отметим особенности представления оценки при помощи количества обращений к оракулу (подпрограмме), что удобно для сравнения методов, однако если анализировать вопрос с точки зрения имплементации, то возникают несоответствия между фактическим временем работы и оценкой. Алгоритмическая сложность не учитывает ряда особенностей самого метода, как и возможностей вычислительного устройства, на котором будут происходить измерения. Например, в данной оценке никак не учитывается зависимость по данным конкретного алгоритма, то есть ситуация, когда следующая по порядку исполнения команда, зависит от вычисления предыдущей команды. А это напрямую определяет возможности его параллелизации. Подобный тип оценки был более удобен ранее, когда исполняющее устройство позволяло только последовательное исполнение, а основным параметром, влияющим на финальное время работы метода, была тактовая частота, определяющая количество обрабатываемых команд в единицу времени. Современные исполняющие устройства в значительной мере используют возможности параллелизации, потому время работы алгоритма определяется в том числе и профилем его доступа к данным. Причем тип и параметры па-раллелизации будут зависеть как от алгоритма, так и от организации памяти и иных функциональных ограничений устройства. Данная проблематика более подробно затрагиваются в пункте 1.3.3 за счет особенностей целевой функции, которые не позволяют гарантировать хорошие оценок скорости сходимости. Метод покоординатного спуска обладает крайне пессимистичными оценками скорости сходимости, однако он позволяет параллелизовать шаги, производимые в различных измерениях. Попытка воспользоваться данным несоответствием и легла в основу данной главы. Также приводится опыт работы с методами первого порядка на данном функционале в отсутствии гарантий оценок.

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

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

Рассуждая об имплементации методов оптимизации, стоит также принимать в расчет ограничения, возникающие из-за машинного представления чисел (см. например [22; 23]). Во многих случаях недостаточная точность может приводить к так называемым градиентным взрывам или исчезновению значения, что соответствует слишком большому для представления числу и слишком малому для отделения его от 0. Эти эффекты широко обсуждаются при реализации библиотек, осуществляющих автоматическое дифференцирование. Данные аспекты находят отражение в концепции неточного оракула, что в конечном итоге отражается на теоретических оценках. Также существуют подходы, направленные на обнаружение ошибки и ее исправление при следующих итерациях, аналогичные ранее продемонстрированному подходу. Тут важно отметить, что машинная точность необходимая для работы метода является существенным ограничением для его использования во многих приложениях. Чем выше требуемая точность, тем больше необходимо памяти для хранения результатов работы, тем более сложное представление чисел необходимо поддерживать. Практическим примером подобной проблематики является процесс переноса обучения нейронной сети с

г=1

серверных мощностей на устройство со значительным ограничением памяти, такое как мобильный телефон. [24; 25]

Для описания интересующих нас методов рассмотрим общую задачу безусловной выпуклой оптимизации [17], которая является «классической»

min f (x). (1.1)

xeR™ w

Через x0 обозначим точку старта, через x* - искомое точное решение задачи (1.1). Если решение задачи (1.1) не единственно, то под x* будем понимать такое решение задачи (1.1), которое наиболее близко к x0 в смысле Евклидового расстояния. Определим R = ||x° — x*||2. Будем также считать, что Amax (V2f (x)) ^ L, Amin iy2f (x)) ^ ^ ^ 0. Введем также число обусловленности х = L/ц,. Если n достаточно большое, то самым простым численным методом решения задачи (1.1) будет градиентный спуск [26], [27]:

xk+1 = xk — LVf (xk) . (1.2)

Известна следующая теоретическая оценка для метода (1.2)

f (xN) — f (x*) ^ ^f min { N'(—NX) } . (1.3)

На практике значение параметра L, которое нужно методу (1.2) для работы, как правило, не известно. К тому же, на самом деле, методу (1.2) и не и требуется знание глобального значения этого параметра. Достаточно знать значение этого параметра на траектории метода. Возможным решением проблемы незнания L является переход к методу наискорейшего спуска [27]:

hk e argmin f (xk — hVf (xk)) ,

h>° (1.4)

xk+1 = xk — hkVf (xk) .

Переход к наискорейшему спуску принципиально не меняет оценку скорости сходимости (1.3), но может обладать иным поведением на практике.

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

xk+1 e x° + Lin {Vf (x°) ..,Vf (xk) }?

(1.5)

Ответ на этот вопрос отрицательный (см. например [6]). У градиентных (наискорейших) спусков существуют различные ускоренные варианты. Поясним это на примере задачи квадратичной оптимизации.

Одной из характерных задач выпуклой оптимизации является задача минимизации положительно определенной квадратичной формы (эквивалент решения линейной системы уравнений, см. например [7]):

min f (x) = min - (Ax,x) — (b,x).

x£R"J y J xeR« 2X ' x '

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

xk+1 = xk - акVf (xk) + ßk • (xk - xk-1) , (1.6)

где

(ak,ßk) = argmin f (xk - aVf {xk) + ß • (xk - xk-1)) .

a, ß

Метод (1.6) обладает следующей оптимальным оценкой

.f(xN) - f (x.) <

^ min /-LR—_, 2LR2 Л/Х-ТГ , (V-n+1 - A1\2 ДЛ C-7)

[2(2N + 1)2 \y/x +V \An-N +1 + Aj

где N < n, 0 < ^ = Amin (A) = А, < A2 < ... < An = Amax (A) = L. Второй аргумент в минимуме (1.7) при больших значениях N оценивается сверху 2LR2 exp (-2N/y/x). При N = n метод гарантированно находит точное решение, что следует из последней оценки в минимуме (1.7). Сформулированный результат является фундаментальным фактом выпуклой оптимизации и вычислительной линейной алгебры одновременно, и базируется на наличии рекуррентных формул для многочленов Чебышёва [28], [6].

Список литературы диссертационного исследования кандидат наук Макаренко Дмитрий Владимирович, 2022 год

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

5. Б. Т. Поляк. Теоремы существования и сходимость минимизирующих последовательностей для задач на экстремум при наличии ограничений [Текст]. Т. 166 / Б. Т. Поляк. — 1966. — С. 287—290. — URL: http://mi.mathnet.ru/ dan32017.

6. Немировский, А. С. Сложность задач и эффективность методов оптимизации [Текст] / А. С. Немировский, Д. Б. Юдин. —Наука, 1979.

7. S., B. Convex optimization: algorithms and complexity [Text] / B. S. // Foundations and Trends in Machine Learning. — 2015. — Vol. 6, no. 3/4. — P. 231—357.

8. Нестеров, Ю. Е. Метод минимизации выпуклых функций со скоростью сходимости O(1/k2) [Текст] / Ю. Е. Нестеров // Докл. АН СССР. Т. 269. — 1983.-С. 543-547.

9. Julien, S. A simpler approach to obtaining an O(1/t) convergence rate for the projected stochastic subgradient method [Text] / S. Julien, M. Schmidt, F. Bach. — 2012. - URL: https://arxiv.org/pdf/1212.2002.pdf.

10. Antonakopoulos, K. Adaptive first-order methods revisited: Convex optimization without Lipschitz requirements [Text] / K. Antonakopoulos, P. Mertikopoulos. — 2021. - URL: https://arxiv.org/pdf/2107.08011.pdf.

11. Lu, H. Relative-Continuity for Non-Lipschitz Non-Smooth Convex Optimization using Stochastic (or Deterministic) Mirror Descent [Text] / H. Lu // INFORMS Journal on Optimization. — 2018. — Vol. 1, no. 4. — P. 288—303.

12. Regret Bounds without Lipschitz Continuity: Online Learning with Relative-Lipschitz Losses [Text] / Y. Zhou [et al.] // 34th Conference on Neural Information Processing Systems (NeurlPS 2020). — 2020. — P. 232—246.

13. Bauschke, H. A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications [Text] / H. Bauschke, J. Bolte, M. Teboulle // Mathematics of Operations Research. — 2017. — Vol. 42, no. 2. — P. 330—348.

14. Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization [Текст] / H. Hendrikx [и др.] // ICML 2020 - Thirty-seventh International Conference on Machine Learning. — Vienna / Virtual, Austria, 07.2020. — (Proceedings of Machine Learning Research). — URL: https : //hal.archives-ouvertes.fr/hal-02974232.

15. O'Donoghue, B. Adaptive restart for accelerated gradient schemes [Text] / B. O'Donoghue, E. Candes // Foundations of computational mathematics. — 2015. — Vol. 15, no. 3. — P. 715—732.

16. An adaptive proximal method for variational inequalities [Text] / A. Gasnikov [et al.] // Computational Mathematics and Mathematical Physics. — 2018. — Vol. 59, no. 5.—P. 836—841.

17. Gasnikov, A. Universal gradient descent [Текст] / A. Gasnikov. — 2017. — arXiv: 1711.00394.

18. A universal modification of the linear coupling method [Text] / S. Guminov [et al.] // Optimization Methods and Software. — 2019. — Vol. 34, no. 3. — P. 560—577.

19. Dragomir, R. Bregman Gradient Methods for Relatively-Smooth Optimization Doctoral dissertation [Text] /R. Dragomir. —2021. —URL: https://hal.inria.fr/tel-03389344/document.

20. Lu, H. Relatively Smooth Convex Optimization by First-Order Methods, and Applications [Text] / H. Lu, R. Freund, Y. Nesterov // SIAM Journal on Optimization. — 2018. — Vol. 28, no. 1. — P. 333—354.

21. Gradient-Type Adaptive Methods for Relatively Lipschitz Convex Optimization Problems [Text] / F. Stonyakin [et al.]. — 2021. — URL: https://arxiv.org/pdf/ 2107.05765.pdf.

22. Understanding and optimizing asynchronous low-precision stochastic gradient descent [Текст] / C. De Sa [и др.] //2017 ACM/IEEE 44th Annual International Symposium on Computer Architecture (ISCA). — 2017. — С. 561—574.

23. Li, Z. Dimension-Free Bounds for Low-Precision Training [Текст] / Z. Li, C. M. De Sa // Advances in Neural Information Processing Systems. Т. 32 / под ред. H. Wallach [и др.]. — Curran Associates, Inc., 2019. — URL: https: //proceedings.neurips.cc/paper/2019/file/d4cd91e80f36f8f3103617ded9128560-Paper.pdf.

24. Progressive Learning of Low-Precision Networks for Image Classification [Текст] / Z. Zhou [и др.] // IEEE Transactions on Multimedia. — 2021. — Т.23.-С. 871-882.

25. High-Accuracy Low-Precision Training [Текст] / C. De Sa [и др.]. — 2018. — Март. — URL: https://arxiv.org/abs/1803.03383.

26. Nesterov, Y. Introductory lectures on convex optimization: A basic course [Text] / Y Nesterov. — Springer Science & Business Media, 2013.

27. Поляк, Б. Т. Введение в оптимизацию [Текст] / Б. Т. Поляк. — 1983.

28. Nocedal, J. Numerical optimization [Text] / J. Nocedal, S. J. Wright. — Springer, 2006.

29. Su, W. A differential equation for modeling Nesterov's accelerated gradient method: Theory and insights [Text] / W. Su, S. Boyd, E. Candes // Advances in Neural Information Processing Systems. — 2014. — P. 2510—2518.

30. Stich, S. U. Local SGD Converges Fast and Communicates Little [Текст] / S. U. Stich // ArXiv. — 2019. — Т. abs/1805.09767.

31. Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification and Local Computations [Текст] / D. Basu [и др.] // Advances in Neural Information Processing Systems. Т. 32 / под ред. H. Wallach [и др.]. — Curran Associates, Inc., 2019. — URL: https : / / proceedings . neurips . cc / paper / 2019 / file / d202ed5bcfa858c15a9f383c3e386ab2-Paper.pdf.

32. QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding [Текст] / D. Alistarh [и др.] // Proceedings of the 31st International Conference on Neural Information Processing Systems. — Long Beach, California, USA: Curran Associates Inc., 2017. - С. 1707-1718. - (NIPS'17).

33. Stich, S. U.The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication [Текст] / S. U. Stich, S. P. Karimireddy // CoRR. — 2019. — Т. abs/1909.05350. — arXiv: 1909 . 05350. — URL: http://arxiv.org/abs/1909.05350.

34. Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization [Текст] / H. Hendrikx [и др.] // Proceedings of the 37th International Conference on Machine Learning. — JMLR.org, 2020. — (ICML'20).

35. Levinthal, C. How to fold graciously [Text] / C. Levinthal. — University of Illinois Press Urbana, 1969. — P. 22—24.

36. Canutescu, A. A. Cyclic coordinate descent: A robotics algorithm for protein loop closure [Text] / A. A. Canutescu, R. L. Dunbrack // Protein science. — 2003. — Vol. 12, no. 5.—P. 963—972.

37. A kinematic view of loop closure [Text] / E. A. Coutsias [et al.] // Journal of computational chemistry. — 2004. — Vol. 25, no. 4. — P. 510—528.

38. Ponder, J. W. Force fields for protein simulations [Text] / J. W. Ponder, D. A. Case // Advances in protein chemistry. — 2003. — Vol. 66. — P. 27—85.

39. A Second Generation Force Field for the Simulation of Proteins, Nucleic Acids, and Organic Molecules [Text] / W. D. Cornell [et al.] // Journal of the American Chemical Society. — 1995. — Vol. 117, no. 19. —P. 5179—5197.

40. CHARMM36m: an improved force field for folded and intrinsically disordered proteins [Text] / J. Huang [et al.] // Nature Methods. — 2017. — Vol. 14.

41. Jorgensen, W. L. Development and Testing of the OPLS All-Atom Force Field on Conformational Energetics and Properties of Organic Liquids [Text] / W. L. Jorgensen, D. S. Maxwell, J. Tirado-Rives // Journal of the American Chemical Society. - 1996. - Vol. 118, no. 45. -P. 11225-11236.

42. Sweere, A. J. M. Accuracy Test of the OPLS-AA Force Field for Calculating Free Energies of Mixing and Comparison with PAC-MAC [Text] / A. J. M. Sweere, J. G. E. M. Fraaije // Journal of Chemical Theory and Computation. — 2017. — Vol. 13, no. 5.-P. 1911-1923.

43. Semianalytical treatment of solvation for molecular mechanics and dynamics [Text] / W. C. Still [et al.] // Journal of the American Chemical Society. — 1990. — Vol. 112, no. 16. - P. 6127-6129.

44. Wales, D. J. Global optimization by basin-hopping and the lowest energy structures of Lennard-Jones clusters containing up to 110 atoms [Text] / D. J. Wales, J. P. Doye // The Journal of Physical Chemistry A. — 1997. — Vol. 101, no. 28. — P. 5111-5116.

45. Посыпкин, М. А. Методы и распределенная программная инфраструктура для численного решения задачи поиска молекулярных кластеров с минимальной энергией [Текст] / М. А. Посыпкин // Вестник нижегородского университета им. НИ Лобачевского. — 2010. — № 1.

46. Ghadimi, S. Generalized uniformly optimal methods for nonlinear programming [Text] / S. Ghadimi, G. Lan, H. Zhang. — 2015. — arXiv: 1508.07384.

47. Nesterov, Y. Random gradient-free minimization of convex functions [Text] / Y. Nesterov, V. Spokoiny // Foundations of Computational Mathematics. — 2017. — Vol. 17, no. 2. — P. 527—566.

48. Zhigljavsky, A. Stochastic global optimization [Text] / A. Zhigljavsky, A. Zilin-skas. — Springer Science & Business Media, 2007.

49. Zhigljavsky, A. A. Theory of global random search [Text] / A. A. Zhigljavsky. — Springer Science & Business Media, 2012.

50. Computational geometry [Text] / M. De Berg [et al.] // Computational geometry. — Springer, 2000. — P. 1—17.

51. Coordinate descent converges faster with the Gauss-Southwell rule than random selection [Text] / J. Nutini [et al.] // International Conference on Machine Learning.-2015.-P. 1632-1641.

52. Conn, A. R. Introduction to derivative-free optimization [Text] / A. R. Conn, K. Scheinberg, L. N. Vicente. — Siam, 2009.

53. Ghadimi, S. Stochastic first-and zeroth-order methods for nonconvex stochastic programming [Text] / S. Ghadimi, G. Lan // SIAM Journal on Optimization. — 2013. - Vol. 23, no. 4. - P. 2341-2368.

54. Wright, S. J. Coordinate descent algorithms [Text] / S. J. Wright // Mathematical Programming. — 2015. — Vol. 151, no. 1. — P. 3—34.

55. Lower Bounds for Finding Stationary Points II: First-Order Methods [Text] / Y. Carmon [et al.]. — 2017. — arXiv: 1711.00841.

56. Lower Bounds for Finding Stationary Points I [Text] / Y. Carmon [et al.]. — 2017.-arXiv: 1710.11606.

57. First-order Methods Almost Always Avoid Saddle Points [Text] / J. D. Lee [et al.]. — 2017. — arXiv: 1710.07406.

58. Gradient descent only converges to minimizers [Text] / J. D. Lee [et al.] // Conference on Learning Theory. — 2016. — P. 1246—1257.

59. Гудфеллоу, Я. Глубокое обучение [Текст] / Я. Гудфеллоу, Б. Иошуа, А. Кур-вилль. — Litres, 2017.

60. Accelerated Primal-Dual Gradient Descent with Linesearch for Convex, Nonconvex, and Nonsmooth Optimization Problems [Текст] / S. Guminov [и др.] // Doklady Mathematics. Т. 99. — Springer. 2019. — С. 125—128.

61. Protein and ligand preparation: parameters, protocols, and influence on virtual screening enrichments [Text] / G. M. Sastry [et al.] // Journal of computer-aided molecular design. — 2013. — Vol. 27, no. 3. — P. 221—234.

62. Baes, M. Estimate sequence methods: extensions and approximations [Text] / M. Baes // Institute for Operations Research, ETH, Zürich, Switzerland. — 2009.

63. Nesterov, Y. Implementable tensor methods in unconstrained convex optimization [Text] : tech. rep. / Y. Nesterov ; Université catholique de Louvain, Center for Operations Research ; Econometrics (CORE). — 2018.

64. Bayandina, A. Gradient-free two-points optimal method for non smooth stochastic convex optimization problem with additional small noise [Text] / A. Bayandina, A. Gasnikov, A. Lagunovskaya. — 2017. — arXiv: 1701.03821.

65. Dvurechensky, P. An Accelerated Method for Derivative-Free Smooth Stochastic Convex Optimization [Text] / P. Dvurechensky, A. Gasnikov, E. Gorbunov. — 2018.-arXiv: 1802.09022.

66. Протасов, В. Ю. К вопросу об алгоритмах приближенного вычисления минимума выпуклой функции по ее значениям [Текст] / В. Ю. Протасов // Математические заметки. — 1996. — Т. 59, № 1. — С. 95—102.

67. Lee, Y. T. A faster cutting plane method and its implications for combinatorial and convex optimization [Text] / Y. T. Lee, A. Sidford, S. C.-w. Wong // Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on. — IEEE. 2015.-P. 1049-1065.

68. Arjevani, Y. Oracle complexity of second-order methods for smooth convex optimization [Text] / Y. Arjevani, O. Shamir, R. Shiff. — 2017. — arXiv: 1705.07260.

69. The global rate of convergence for optimal tensor methods in smooth convex optimization [Text] / A. Gasnikov [et al.]. — 2018. — arXiv: 1809.00382.

70. Monteiro, R. D. An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods [Text] / R. D. Mon-teiro, B. F. Svaiter // SIAM Journal on Optimization. — 2013. — Vol. 23, no. 2. — P. 1092-1125.

71. Andrei, N. 40 Conjugate Gradient Algorithms for Unconstrianed Optimization. A Survey on Their Definition [Text] / N. Andrei // ICI Technical Report. — 2008. — No. 13.-P. 1-13.-(Visited on 11/19/2015).

72. Nocedal, J. Numerical Optimization [Text] / J. Nocedal, S. J. Wright. — 2nd ed. — New York : Springer, 2006. — 664 p. — (Springer series in operations research).

73. Numerical Recipes. The Art of Scientific Computing [Text] / W. Press [et al.]. — Third edit. — Cambridge University Press, 2007. — 1256 p.

74. Janin, J.Welcome to CAPRI: a critical assessment of predicted interactions [Text] / J. Janin // Proteins: Structure, Function, and Bioinformatics. — 2002. — Vol. 47, no. 3. — P. 257—257.

75. Updates to the integrated protein-protein interaction benchmarks: docking benchmark version 5 and affinity benchmark version 2 [Text] / T. Vreven [et al.] // Journal of molecular biology. — 2015. — Vol. 427, no. 19. — P. 3031—3041.

76. Optimal Complexity and Certification of Bregman First-Order Methods [Text] / R. A. Dragomir [et al.]. — 2021. — URL: https://doi.org/10.1007/s10107-021-01618-1.

77. Inexact relative smoothness and strong convexity for optimization and variational inequalities by inexact model [Text] /F. Stonyakin [etal.] // Optimization Methods and Software. — 2021.

78. Algorithms for solving variational inequalities and saddle point problems with some generalizations of Lipschitz property for operators [Text] / A. Titov [et al.] // Communications in Computer and Information Science. — 2021. — Vol. 1476. — P. 86-101.

79. Макаренко, Д. В. Библиотека для анализа субградиентых методов [Текст] / Д. В. Макаренко. — URL: https : / / github . com/Devjiu/ subgrad (дата обр. 02.10.2022).

80. Поляк, Б. Минимизация негладких функционалов [Текст] / Б. Поляк // Журнал вычислительной математики и вычислительной физики. — 1969. — Т. 9, №3.-С. 509-521.

81. Roulet, V. Sharpness, Restart and Acceleration [Текст] / V. Roulet, A. d'Aspremont // Advances in Neural Information Processing Systems. Т. 30 / под ред. I. Guyon [и др.]. — Curran Associates, Inc., 2017. — URL: https : / / proceedings. neurips. cc/paper/2017/file/2ca65f58e35d9ad45bf7f3ae5cfd08f1 -Paper.pdf.

82. Shapiro, A. On Complexity of Stochastic Programming Problems [Текст] / A. Shapiro, A. Nemirovski. — 2005. — URL: https://doi.org/10.1007/0-387-26771-9_4.

83. Shapiro, A. / A. Shapiro, D. Dentcheva, A. Ruszczynski. — MOS-SIAM Series on Optimization, 2021. — С. 494. — URL: https : / / doi. org / 10 . 1137 /1 . 9781611973433.

84. Peña, D. H. G. F. A unified framework for Bregman proximal methods: subgradient, gradient, and accelerated gradient schemes [Текст] /D. H. G. F. Peña// Working paper, Tepper School of Business, Carnegie Mellon University. — 2018. — URL: https://optimization-online.org/2018/12/6996/.

85. Ben-Tal, A. Lectures on Modern Convex Optimization [Текст] / A. Ben-Tal, A. Nemirovski. — Society for Industrial, Applied Mathematics, 2001. — eprint: https://epubs.siam.org/doi/pdf/10.1137/1.9780898718829. — URL: https: //epubs.siam.org/doi/abs/10.1137/L9780898718829.

86. Mirror Descent and Convex Optimization Problems with Non-smooth Inequality Constraints [Текст] / A. Bayandina [и др.] // Large-Scale and Distributed Optimization / под ред. P. Giselsson, A. Rantzer. — Cham : Springer International Publishing, 2018. — С. 181—213. — URL: https://doi.org/10.1007/978-3-319-97478-1 8.

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

1.1 Компрессионный шум для различных методов...............22

1.2 Отсутствие выпуклости для задачи минимизации OPLS force field ... 29

1.3 Структура типичного белка ..................................................31

1.4 Сходимость безградиентного метода (шевеление случайного атома) . . 34

1.5 Сравнение скорости сходимости безградиентного метода (шевеление случайного атома) с градиентным спуском ................................34

1.6 Убывание энергии на итерациях градиентного спуска с правилом выбора шага по методу парабол и ускоренного градиентного спуска . . 37

2.1 Невязка по функции и оценки для задачи минимизации (2.36) для Q радиуса 6.................................... 58

2.2 Работа уточненной оценки (2.34) для задачи минимизации (2.36) для шара Q = Rn.................................. 59

2.3 Поведение невязки функции в отсутствии усреднения для задачи

(2.36) для шара Q = Rn...........................59

3.1 Результаты решения задачи минимизации (2.36), учитывающей сильную выпуклость, где n = 1 000, r = 5 и шар Q радиуса 4......64

3.2 Результаты решения задачи минимизации (3.7), учитывающей

условие острого минимума, где n = 1 000, r = 0.7525, а = 0.6......65

3.3 Результаты решения задачи минимизации (2.36), учитывающей сильную выпуклость, где n = 1 000, r = 0.7525.............. 66

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

1 Оптимальные оценки количества обращений к субградиенту....... 7

2 Сравнение характеристик методов.....................35