|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
МАТЕМАТИЧЕСКИЕ ОСНОВЫ И ЧИСЛЕННЫЕ МЕТОДЫ МОДЕЛИРОВАНИЯ
Субградиентные методы для задач негладкой оптимизации с некоторой релаксацией условия острого минимума
С. С. Аблаевab, Д. В. Макаренкоa, Ф. С. Стонякинab, М. С. Алкусаac, И. В. Баранb a Московский физико-технический институт,
Россия, 141701, Московская обл., г. Долгопрудный, Институтский пер., 9
b Крымский федеральный университет им. В. И. Вернадского,
Россия, 295007, Республика Крым, г. Симферополь, проспект академика Вернадского, 4
c Национальный исследовательский университет «Высшая школа экономики»,
Россия, 101000, г. Москва, ул. Мясницкая, д. 20
Аннотация:
Задачи негладкой оптимизации нередко возникают во многих приложениях. Вопросы разработки эффективных вычислительных процедур для негладких задач в пространствах больших размерностей весьма актуальны. В таких случаях разумно применять методы первого порядка (субградиентные методы), однако в достаточно общих ситуациях они приводят к невысоким скоростным гарантиям. Одним из подходов к этой проблеме может являться выделение подкласса негладких задач, допускающих относительно оптимистичные результаты о скорости сходимости в пространствах больших размерностей. К примеру, одним из вариантов дополнительных предположений может послужить условие острого минимума, предложенное в конце 1960-х годов Б. Т. Поляком. В случае доступности информации о минимальном значении функции для липшицевых задач с острым минимумом известен субградиентный метод с шагом Б. Т. Поляка, который гарантирует линейную скорость сходимости по аргументу. Такой подход позволил покрыть ряд важных прикладных задач (например, задача проектирования точки на выпуклый компакт или задача отыскания общей точки системы выпуклых множеств). Однако как условие доступности минимального значения функции, так и само условие острого минимума выглядят довольно ограничительными. В этой связи в настоящей работе предлагается обобщенное условие острого минимума, аналогичное известному понятию неточного оракула. Предложенный подход позволяет расширить класс применимости субградиентных методов с шагом Б. Т. Поляка на ситуации неточной информации о значении минимума, а также неизвестной константы Липшица целевой функции. Более того, использование в теоретической оценке качества выдаваемого методом решения локальных аналогов глобальных характеристик целевой функции позволяет применять результаты такого типа и к более широким классам задач. Показана возможность применения предложенного подхода к сильно выпуклым негладким задачам и выполнено экспериментальное сравнение с известным оптимальным субградиентным методом на таком классе задач. Более того, получены результаты о применимости предложенной методики для некоторых типов задач с релаксациями выпуклости: недавно предложенное понятие слабой $\beta$-квазивыпуклости и обычной квазивыпуклости. Исследовано обобщение описанной методики на ситуацию с предположением о доступности на итерациях $\delta$-субградиента целевой функции вместо обычного субградиента. Для одного из рассмотренных методов найдены условия, при которых на практике можно отказаться от проектирования итеративной последовательности на допустимое множество поставленной задачи.
Ключевые слова:
субградиентный метод, острый минимум, квазивыпуклая функция, слабо $\beta$-квазивыпуклая функция, липшицева функция, $\delta$-субградиент.
Поступила в редакцию: 12.02.2022 Исправленный вариант: 30.03.2022 Принята в печать: 05.04.2022
Образец цитирования:
С. С. Аблаев, Д. В. Макаренко, Ф. С. Стонякин, М. С. Алкуса, И. В. Баран, “Субградиентные методы для задач негладкой оптимизации с некоторой релаксацией условия острого минимума”, Компьютерные исследования и моделирование, 14:2 (2022), 473–495
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/crm978 https://www.mathnet.ru/rus/crm/v14/i2/p473
|
Статистика просмотров: |
Страница аннотации: | 179 | PDF полного текста: | 61 | Список литературы: | 42 |
|