Общие численные методы

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

О. С. Савчук^ab, Ф. С. Стонякин^abc, А. А. Выгузов^ac, М. С. Алкуса^c, А. В. Гасников<sup>ac

a</sup> Московский физико-технический институт (национальный исследовательский университет), Московская облаcть, г. Долгопрудный
^b Крымский федеральный университет имени В. И. Вернадского, Симферополь, Россия
^c Университет Иннополис, Иннополис, Россия

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

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

УДК: 519.85

Поступила в редакцию: 18.04.2025
Принята в печать: 23.04.2025

DOI: 10.31857/S0044466925070077

 Англоязычная версия: Computational Mathematics and Mathematical Physics, 2025, 65:7, 1605–1627

Реферативные базы данных:

•