Статьи автора

АДАПТИВНЫЙ АЛГОРИТМ ФРАНК–ВУЛЬФА ДЛЯ ЗАДАЧ МИНИМИЗАЦИИ ВЫПУКЛЫХ ОТНОСИТЕЛЬНО ГЛАДКИХ ФУНКЦИЙ

Номер выпуска 3 от 01.03.2025

В работе предложен новый вариант адаптивного алгоритма Франк–Вульфа для относительно гладких выпуклых задач минимизации. Предлагается использовать дивергенцию, отличную от половины квадрата евклидовой нормы в формуле для регулировки длины шага. Доказаны оценки скорости сходимости такого метода для задач минимизации относительно гладких выпуклых функций с “trianglе scaling propеrty”. Также доказана оценка со скоростью геометрической прогрессии при условии относительной сильной выпуклости функции. Выполнены вычислительные эксперименты для обратной задачи Пуассона (Poisson inverse problem) и для метода опорных векторов (SVM). Найдены условия, в которых наблюдается явное преимущество предложенного алгоритма над классическим методом, а также над ускоренными методами градиентного типа с относительной гладкостью и свойством “trianglе scaling propеrty”. Библ. 15. Фиг. 2.

122 0

АДАПТИВНЫЕ ПРЯМО-ДВОЙСТВЕННЫЕ МЕТОДЫ С НЕТОЧНЫМ ОРАКУЛОМ ДЛЯ ОТНОСИТЕЛЬНО ГЛАДКИХ ОПТИМИЗАЦИОННЫХ ЗАДАЧ И ИХ ПРИЛОЖЕНИЯ К ЗАДАЧАМ ВОССТАНОВЛЕНИЯ МАЛОРАНГОВЫХ МАТРИЦ

Номер выпуска 7 от 23.04.2025

Статья посвящена адаптивным прямо-двойственным методам первого порядка для относительно гладких задач оптимизации с ограничениями-неравенствами, а также их приложениям к задачам восстановления малоранговых матриц. Показано, что для некоторого класса относительно гладких задач восстановления малоранговых матриц можно применять треугольное шкалированное свойство с коэффициентом шкалирования γ = 2, что открыло возможность применения для таких задач ускоренных методов и методов типа Франк–Вульфа и результатов об их вычислительных гарантиях. Предложен адаптивный вариант метода подобных треугольников для гладких задач относительно дивергенции Брегмана с треугольным шкалированным свойством с коэффициентом шкалирования γ = 2. Также предложены неускоренный и ускоренный прямо-двойственные адаптивные методы с неточным оракулом для относительно гладких задач. Ускоренный прямо-двойственный метод также есть аналог метода подобных треугольников и использует треугольное шкалированное свойство дивергенции Брегмана с коэффициентом шкалирования γ = 2. Ключевая особенность исследования в статье методов — возможность использования на итерациях неточной информации и учета неточности решения вспомогательных подзадач на итерациях методов. Это естественно ввиду усложнения таких подзадач в силу использования дивергенции (расхождения) Брегмана вместо квадрата евклидовой нормы. В частности, это привело к варианту метода Франк–Вульфа для выделенного класса относительно гладких задач. Для всех предложенных методов получены теоретические результаты о качестве выдаваемого решения.

11 0