|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
МАТЕМАТИЧЕСКИЕ ОСНОВЫ И ЧИСЛЕННЫЕ МЕТОДЫ МОДЕЛИРОВАНИЯ
Linearly convergent gradient-free methods for minimization of parabolic approximation
[Линейно сходящиеся безградиентные методы для минимизации параболической аппроксимации]
A. I. Bazarovaa, A. N. Beznosikova, A. V. Gasnikovabc a Moscow Institute of Physics and Technology (National Research University), Dolgoprudny, Moscow Region
b Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute), Moscow
c Caucasus Mathematical Center, Adyghe State University, Maikop
Аннотация:
Нахождение глобального минимума невыпуклых функций — одна из ключевых и самых сложных проблем современной оптимизации. В этой работе мы рассматриваем отдельные классы невыпуклых задач, которые имеют четкий и выраженный глобальный минимум.
В первой части статьи мы рассматриваем два класса «хороших» невыпуклых функций, которые могут быть ограничены снизу и сверху параболической функцией. Такой класс задач не исследован широко в литературе, хотя является довольно интересным с прикладной точки зрения. Более того, для таких задач методы первого и более высоких порядков могут быть абсолютно неэффективны при поиске глобального минимума. Это связано с тем, что функция может сильно осциллировать или может быть сильно зашумлена. Поэтому наши новые методы используют информацию только нулевого порядка и основаны на поиске по сетке. Размер и мелкость этой сетки, а значит, и гарантии скорости сходимости и оракульной сложности зависят от «хорошести» задачи. В частности, мы показываем, если функция зажата довольно близкими параболическими функциями, то сложность не зависит от размерности задачи. Мы показываем, что наши новые методы сходятся с линейной скоростью сходимости $\log(1/\epsilon)$ к глобальному минимуму на кубе.
Во второй части статьи мы рассматриваем задачу невыпуклой оптимизации с другого ракурса. Мы предполагаем, что целевая минимизируемая функция есть сумма выпуклой квадратичной задачи и невыпуклой «шумовой» функции, пропорциональной по модулю расстоянию до глобального решения. Рассмотрение функций с такими предположениями о шуме для методов нулевого порядка является новым в литературе. Для такой задачи мы используем классический безградиентный подход с аппроксимацией градиента через конечную разность. Мы показываем, как можно свести анализ сходимости для нашей задачи к стандартному анализу для задач выпуклой оптимизации. В частности, и для таких задач мы добиваемся линейной скорости сходимости.
Экспериментальные результаты подтверждают работоспособность и практическую применимость всех полученных методов.
Ключевые слова:
безградиентная оптимизация, невыпуклая задача, линейная скорость сходимости.
Поступила в редакцию: 09.02.2022 Принята в печать: 13.02.2022
Образец цитирования:
A. I. Bazarova, A. N. Beznosikov, A. V. Gasnikov, “Linearly convergent gradient-free methods for minimization of parabolic approximation”, Компьютерные исследования и моделирование, 14:2 (2022), 239–255
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/crm966 https://www.mathnet.ru/rus/crm/v14/i2/p239
|
Статистика просмотров: |
Страница аннотации: | 99 | PDF полного текста: | 28 | Список литературы: | 21 |
|