Все выпуски

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

Non-smooth optimization often arises in many applied problems. The issues of developing efficient computational procedures for such problems in high-dimensional spaces are very topical. First-order methods (subgradient methods) are well applicable here, but in fairly general situations they lead to low speed guarantees for large-scale problems. One of the approaches to this type of problem can be to identify a subclass of non-smooth problems that allow relatively optimistic results on the rate of convergence. For example, one of the options for additional assumptions can be the condition of a sharp minimum, proposed in the late 1960s by B. T. Polyak. In the case of the availability of information about the minimal value of the function for Lipschitz-continuous problems with a sharp minimum, it turned out to be possible to propose a subgradient method with a Polyak step-size, which guarantees a linear rate of convergence in the argument. This approach made it possible to cover a number of important applied problems (for example, the problem of projecting onto a convex compact set). However, both the condition of the availability of the minimal value of the function and the condition of a sharp minimum itself look rather restrictive. In this regard, in this paper, we propose a generalized condition for a sharp minimum, somewhat similar to the inexact oracle proposed recently by Devolder – Glineur – Nesterov. The proposed approach makes it possible to extend the class of applicability of subgradient methods with the Polyak step-size, to the situation of inexact information about the value of the minimum, as well as the unknown Lipschitz constant of the objective function. Moreover, the use of local analogs of the global characteristics of the objective function makes it possible to apply the results of this type to wider classes of problems. We show the possibility of applying the proposed approach to strongly convex nonsmooth problems, also, we make an experimental comparison with the known optimal subgradient method for such a class of problems. Moreover, there were obtained some results connected to the applicability of the proposed technique to some types of problems with convexity relaxations: the recently proposed notion of weak $\beta$-quasi-convexity and ordinary quasiconvexity. Also in the paper, we study a generalization of the described technique to the situation with the assumption that the $\delta$-subgradient of the objective function is available instead of the usual subgradient. For one of the considered methods, conditions are found under which, in practice, it is possible to escape the projection of the considered iterative sequence onto the feasible set of the problem.

В первой части работы получена оценка скорости сходимости ранее известного ускоренного метода первого порядка 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.

In the first part of the paper we present convergence analysis of AGMsDR method on a new class of functions — in general non-convex with $M$-Lipschitz-continuous gradients that satisfy Polyak – Lojasiewicz condition. Method does not need the value of $\mu^{PL}>0$ in the condition and converges linearly with a scale factor $\left(1 - \frac{\mu^{PL}}{M}\right)$. It was previously proved that method converges as $O\left(\frac1{k^2}\right)$ if a function is convex and has $M$-Lipschitz-continuous gradient and converges linearly with a~scale factor $\left(1 - \sqrt{\frac{\mu^{SC}}{M}}\right)$ if the value of strong convexity parameter $\mu^{SC}>0$ is known. The novelty is that one can save linear convergence if $\frac{\mu^{PL}}{\mu^{SC}}$ is not known, but without square root in the scale factor.

The second part presents modification of AGMsDR method for solving problems that allow alternating minimization (Alternating AGMsDR). The similar results are proved.

As the result, we present adaptive accelerated methods that converge as $O\left(\min\left\lbrace\frac{M}{k^2},\,\left(1-{\frac{\mu^{PL}}{M}}\right)^{(k-1)}\right\rbrace\right)$ on a class of convex functions with $M$-Lipschitz-continuous gradient that satisfy Polyak – Lojasiewicz condition. Algorithms do not need values of $M$ and $\mu^{PL}$. If Polyak – Lojasiewicz condition does not hold, the convergence is $O\left(\frac1{k^2}\right)$, but no tuning needed.

We also consider the adaptive catalyst envelope of non-accelerated gradient methods. The envelope allows acceleration up to $O\left(\frac1{k^2}\right)$. We present numerical comparison of non-accelerated adaptive gradient descent which is accelerated using adaptive catalyst envelope with AGMsDR, Alternating AGMsDR, APDAGD (Adaptive Primal-Dual Accelerated Gradient Descent) and Sinkhorn's algorithm on the problem dual to the optimal transport problem.

Conducted experiments show faster convergence of alternating AGMsDR in comparison with described catalyst approach and AGMsDR, despite the same asymptotic rate $O\left(\frac1{k^2}\right)$. Such behavior can be explained by linear convergence of AGMsDR method and was tested on quadratic functions. Alternating AGMsDR demonstrated better performance in comparison with AGMsDR.

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

The problem of developing efficient numerical methods for non-convex (including non-smooth) problems is relevant due to their widespread use of such problems in applications. This paper is devoted to subgradient methods for minimizing Lipschitz $\mu$-weakly convex functions, which are not necessarily smooth. It is well known that subgradient methods have low convergence rates in high-dimensional spaces even for convex functions. However, if we consider a subclass of functions that satisfies sharp minimum condition and also use the Polyak step, we can guarantee a linear convergence rate of the subgradient method. In some cases, the values of the function or it’s subgradient may be available to the numerical method with some error. The accuracy of the solution provided by the numerical method depends on the magnitude of this error. In this paper, we investigate the behavior of the subgradient method with a Polyak step when inaccurate information about the objective function value or subgradient is used in iterations. We prove that with a specific choice of starting point, the subgradient method with some analogue of the Polyak step-size converges at a geometric progression rate on a class of $\mu$-weakly convex functions with a sharp minimum, provided that there is additive inaccuracy in the subgradient values. In the case when both the value of the function and the value of its subgradient at the current point are known with error, convergence to some neighborhood of the set of exact solutions is shown and the quality estimates of the output solution by the subgradient method with the corresponding analogue of the Polyak step are obtained. The article also proposes a subgradient method with a clipped step, and an assessment of the quality of the solution obtained by this method for the class of $\mu$-weakly convex functions with a sharp minimum is presented. Numerical experiments were conducted for the problem of low-rank matrix recovery. They showed that the efficiency of the studied algorithms may not depend on the accuracy of localization of the initial approximation within the required region, and the inaccuracy in the values of the function and subgradient may affect the number of iterations required to achieve an acceptable quality of the solution, but has almost no effect on the quality of the solution itself.