Все выпуски

В статье получены оценки скорости сходимости по функции для недавно предложенного Ю.Е. Нестеровым метода минимизации выпуклой липшицевой функции двух переменных на квадрате с фиксированной стороной. Идея метода — деление квадрата на меньшие части и постепенное их удаление так, чтобы в оставшейся достаточно малой части все значения целевой функции были достаточно близки к оптимальному. При этом метод заключается вр ешении вспомогательных задач одномерной минимизации вдоль разделяющих отрезков и не предполагает вычисления точного значения градиента целевого функционала. Основной результат работы о необходимом количестве итераций для достижений заданной точности доказан вкла ссе гладких выпуклых функций, имеющих липшицев градиент. При этом отмечено, что свойство липшицевости градиента достаточно потребовать не на всем квадрате, а лишь на некоторых отрезках. Показано, что метод может работать при наличии погрешностей решения вспомогательных одномерных задач, а также при вычислении направлений градиентов. Также описана ситуация, когда возможно пренебречь временными затратами (или уменьшить их) на решение вспомогательных одномерных задач. Для некоторых примеровэк спериментально продемонстрировано, что метод может эффективно работать и на некоторых классах негладких функций. При этом построен пример простой негладкой функции, для которой при неудачном выборе субградиента даже в случае точного решения вспомогательных одномерных задач может не наблюдаться сходимость метода. Проведено сравнение работы метода Ю.Е. Нестерова, метода эллипсоидов и градиентного спуска для некоторых гладких выпуклых функций. Эксперименты показали, что метод Ю.Е. Нестерова может достигать желаемой точности решения задачи за меньшее (в сравнении с другими рассмотренными методами) время. В частности, замечено, что при увеличении точности искомого решения время работы метода Ю.Е. Нестерова может расти медленнее, чем время работы метода эллипсоидов.

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

Работа посвящена исследованию субградиентных методов с различными вариациями шага Б.Т. Поляка на классах задач минимизации слабо выпуклых и относительно слабо выпуклых функций, обладающих соответствующим аналогом острого минимума. Оказывается, что при некоторых предположениях о начальной точке такой подход может давать возможность обосновать сходимость сyбградиентного метода со скоростью геометрической прогрессии. Для субградиентного метода с шагом Б.Т. Поляка доказана уточненная оценка скорости сходимости для задач минимизации слабо выпуклых функций с острым минимумом. Особенность этой оценки — дополнительный учет сокращения расстояния от текущей точки метода до множества решений по мере роста количества итераций. Представлены результаты численных экспериментов для задачи восстановления фазы (которая слабо выпyкла и имеет острый минимyм), демонстрирующие эффективность предложенного подхода к оценке скорости сходимости по сравнению с известным ранее результатом. Далее, предложена вариация субградиентного метода с переключениями по продуктивным и непродуктивным шагам для слабо выпуклых задач с ограничениями-неравенствами и получен некоторый аналог результата о сходимости со скоростью геометрической прогрессии. Для субградиентного метода с соответствующей вариацией шага Б.Т. Поляка на классе относительно липшицевых и относительно слабо выпуклых функций с относительным аналогом острого минимума получены условия, которые гарантируют сходимость такого субградиентного метода со скоростью геометрической прогрессии. Наконец, получен теоретический результат, описывающий влияние погрешности доступной сyбградиентномy методу информации о (сyб)градиенте и целевой функции на оценку качества выдаваемого приближенного решения. Доказано, что при достаточно малой погрешности $\delta > 0$ можно гарантировать достижение точности решения, сопоставимой c $\delta$.

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

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

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

Задачи негладкой оптимизации нередко возникают во многих приложениях. Вопросы разработки эффективных вычислительных процедур для негладких задач в пространствах больших размерностей весьма актуальны. В таких случаях разумно применятьмет оды первого порядка (субградиентные методы), однако в достаточно общих ситуациях они приводят к невысоким скоростным гарантиям. Одним из подходов к этой проблеме может являться выделение подкласса негладких задач, допускающих относительно оптимистичные результаты о скорости сходимости в пространствах больших размерностей. К примеру, одним из вариантов дополнительных предположений может послужитьуслови е острого минимума, предложенное в конце 1960-х годов Б. Т. Поляком. В случае доступности информации о минимальном значении функции для липшицевых задач с острым минимумом известен субградиентный метод с шагом Б. Т. Поляка, который гарантирует линейную скорость сходимости по аргументу. Такой подход позволил покрыть ряд важных прикладных задач (например, задача проектирования точки на выпуклый компакт или задача отыскания общей точки системы выпуклых множеств). Однако как условие доступности минимального значения функции, так и само условие острого минимума выглядят довольно ограничительными. В этой связи в настоящей работе предлагается обобщенное условие острого минимума, аналогичное известному понятию неточного оракула. Предложенный подход позволяет расширить класс применимости субградиентных методов с шагом Б. Т. Поляка на ситуации неточной информации о значении минимума, а также неизвестной константы Липшица целевой функции. Более того, использование в теоретической оценке качества выдаваемого методом решения локальных аналогов глобальных характеристик целевой функции позволяет применять результаты такого типа и к более широким классам задач. Показана возможностьпр именения предложенного подхода к сильно выпуклым негладким задачам и выполнено экспериментальное сравнение с известным оптимальным субградиентным методом на таком классе задач. Более того, получены результаты о применимости предложенной методики для некоторых типов задач с релаксациями выпуклости: недавно предложенное понятие слабой $\beta$-квазивыпуклости и обычной квазивыпуклости. Исследовано обобщение описанной методики на ситуацию с предположением о доступности на итерациях $\delta$-субградиента целевой функции вместо обычного субградиента. Для одного из рассмотренных методов найдены условия, при которых на практике можно отказаться от проектирования итеративной последовательности на допустимое множество поставленной задачи.

В первой части работы получена оценка скорости сходимости ранее известного ускоренного метода первого порядка AGMsDR на классе задач минимизации, вообще говоря, невыпуклых функций с $M$-липшицевым градиентом и удовлетворяющих условию Поляка – Лоясиевича. При реализации метода не требуется знать параметр $\mu^{PL}>0$ из условия Поляка – Лоясиевича, при этом метод демонстрирует линейную скорость сходимости (сходимость со скоростью геометрической прогрессии со знаменателем $\left.\left(1 - \frac{\mu^{PL}}{M}\right)\right)$. Ранее для метода была доказана сходимость со скоростью $O\left(\frac1{k^2}\right)$ на классе выпуклых задач с $M$-липшицевым градиентом. А также сходимость со скоростью геометрической прогрессии, знаменатель которой $\left(1 - \sqrt{\frac{\mu^{SC}}{M}}\right)$, но только если алгоритму известно значение параметра сильной выпуклости $\mu^{SC}>0$. Новизна результата заключается в том, что удается отказаться от использования методом значения параметра $\mu^{SC}>0$ и при этом сохранить линейную скорость сходимости, но уже без корня в знаменателе прогрессии.

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

Таким образом, представлены адаптивные ускоренные методы с оценкой сходимости $O\left(\min\left\lbrace\frac{M}{k^2},\,\left(1-{\frac{\mu^{PL}}{M}}\right)^{(k-1)}\right\rbrace\right)$ на классе выпуклых функций с $M$-липшицевым градиентом, которые удовлетворяют условию Поляка – Лоясиевича. При этом для работы метода не требуются значения параметров $M$ и $\mu^{PL}$. Если же условие Поляка – Лоясиевича не выполняется, то можно утверждать, что скорость сходимости равна $O\left(\frac1{k^2}\right)$, но при этом методы не требуют никаких изменений.

Также рассматривается адаптивная каталист-оболочка неускоренного градиентного метода, которая позволяет доказать оценку скорости сходимости $O\left(\frac1{k^2}\right)$. Проведено экспериментальное сравнение неускоренного градиентного метода с адаптивным выбором шага, ускоренного с помощью адаптивной каталист-оболочки с методами AGMsDR, Alternating AGMsDR, APDAGD (Adaptive Primal-Dual Accelerated Gradient Descent) и алгоритмом Синхорна для задачи, двойственной к задаче оптимального транспорта.

Проведенные вычислительные эксперименты показали более быструю работу метода Alternating AGMsDR по сравнению как с неускоренным градиентным методом, ускоренным с помощью адаптивной каталист-оболочки, так и с методом AGMsDR, несмотря на асимптотически одинаковые гарантии скорости сходимости $O\left(\frac1{k^2}\right)$. Это может быть объяснено результатом о линейной скорости сходимости метода Alternating AGMsDR на классе задач, удовлетворяющих условию Поляка – Лоясиевича. Гипотеза была проверена на квадратичных задачах. Метод Alternating AGMsDR показал более быструю сходимость по сравнению с методом AGMsDR.