Правила остановки для адаптивного варианта метода Франка – Вульфа в условиях относительно неточной информации о градиенте

В данной работе предложен и исследован критерий остановки для вариантов метода Франк - Вульфа в ситуации использования градиента с относительной погрешностью. Предложенное правило остановки базируется на анализе в случае относительной погрешности зазора двойственности, который выполняет роль критерия близости значения функции к оптимальному решению, аналогичную норме градиента для задач без ограничений. Зазор двойственности позволяет судить о качестве текущего решения не только с точки зрения значения целевой функции, но и с учётом свойств допустимого множества, что особенно важно для задач с ограничениями. Актуальность рассматриваемой тематики обусловлена тем, что в реальных задачах оптимизации, особенно для задач с большими данными и в машинном обучении, часто невозможно получить на каждой итерации точную информацию о градиенте целевой функции: вычисления могут быть основаны на неполных данных, квантизированы, усреднены по мини-батчам или содержать вычислительные ошибки. В таких условиях влияние относительной погрешности, пропорциональной норме точного градиента, становится важным фактором, определяющим сходимость и качество численных методов. В работе подробно анализируются случаи выбора шага минимизации по одномерной квадратичной модели как при постоянной, так и при адаптивно подбираемой константе Липшица градиента. Для обеих ситуаций получены оценки числа итераций, достаточного для гарантии достижения заданной точности решения задачи. При этом отметим, что использование соответствующего аналога шага, зависящего от константы Липшица градиента позволило, в частности, для c-градиентно доминируемых функций получить результат о близкой к линейной скорости сходимости в условиях относительной погрешности и внутренней точки минимума допустимого множества. Проведенные численные эксперименты для функции линейной регрессии и функции ошибки логистической регрессии подтверждают теоретические выводы, демонстрируя устойчивость критерия остановки и эффективность адаптивного выбора шага даже при различных вариантах относительной неточности оракула. Особое внимание уделено сопоставлению реального числа итераций с теоретическими оценками, что позволяет выявить преимущество предложенного правила остановки для задач с относительной погрешностью.