Текущий выпуск Номер 7, 2024 Том 16

Все выпуски

[ Switch to English ]

Субградиентные методы для слабо выпуклых задач с острым минимумом в случае неточной информации о функции или субградиенте

Стонякин Ф.С., Лyшко Е.А., Третьяк И.Д., Аблаев С.С.
 pdf (296K)

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

Ключевые слова: субградиентный метод, адаптивный метод, шаг Поляка, слабо выпуклые функции, острый минимум, неточный субградиент
Цитата: Стонякин Ф.С., Лyшко Е.А., Третьяк И.Д., Аблаев С.С. Субградиентные методы для слабо выпуклых задач с острым минимумом в случае неточной информации о функции или субградиенте // Компьютерные исследования и моделирование, 2024, т. 16, № 7, с. 1765-1778
Citation in English: Stonyakin F.S., Lushko Е.A., Trеtiak I.D., Ablaev S.S. Subgradient methods for weakly convex problems with a sharp minimum in the case of inexact information about the function or subgradient // Computer Research and Modeling, 2024, vol. 16, no. 7, pp. 1765-1778
DOI: 10.20537/2076-7633-2024-16-7-1765-1778
URL: http://crm.ics.org.ru/journal/article/3567/
Creative Commons License Статья доступна по лицензии Creative Commons Attribution-NoDerivs 3.0 Unported License.

Журнал индексируется в Scopus

Полнотекстовая версия журнала доступна также на сайте научной электронной библиотеки eLIBRARY.RU

Журнал входит в систему  Российского индекса научного цитирования.

Журнал включен в базу данных Russian Science Citation Index (RSCI) на платформе Web of Science

Международная Междисциплинарная Конференция "Математика. Компьютер. Образование"

Международная Междисциплинарная Конференция МАТЕМАТИКА. КОМПЬЮТЕР. ОБРАЗОВАНИЕ.

Copyright © 2009–2025 Институт компьютерных исследований