Компьютерные исследования и моделирование
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Компьютерные исследования и моделирование:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Компьютерные исследования и моделирование, 2022, том 14, выпуск 2, страницы 239–255
DOI: https://doi.org/10.20537/2076-7633-2022-14-2-239-255
(Mi crm966)
 

Эта публикация цитируется в 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)$ к глобальному минимуму на кубе.
Во второй части статьи мы рассматриваем задачу невыпуклой оптимизации с другого ракурса. Мы предполагаем, что целевая минимизируемая функция есть сумма выпуклой квадратичной задачи и невыпуклой «шумовой» функции, пропорциональной по модулю расстоянию до глобального решения. Рассмотрение функций с такими предположениями о шуме для методов нулевого порядка является новым в литературе. Для такой задачи мы используем классический безградиентный подход с аппроксимацией градиента через конечную разность. Мы показываем, как можно свести анализ сходимости для нашей задачи к стандартному анализу для задач выпуклой оптимизации. В частности, и для таких задач мы добиваемся линейной скорости сходимости.
Экспериментальные результаты подтверждают работоспособность и практическую применимость всех полученных методов.
Ключевые слова: безградиентная оптимизация, невыпуклая задача, линейная скорость сходимости.
Финансовая поддержка Номер гранта
Российский научный фонд 21-71-30005
Исследование выполнено за счет гранта Российского научного фонда (проект № 21-71-30005).
Поступила в редакцию: 09.02.2022
Принята в печать: 13.02.2022
Тип публикации: Статья
УДК: 519.8
Язык публикации: английский
Образец цитирования: A. I. Bazarova, A. N. Beznosikov, A. V. Gasnikov, “Linearly convergent gradient-free methods for minimization of parabolic approximation”, Компьютерные исследования и моделирование, 14:2 (2022), 239–255
Цитирование в формате AMSBIB
\RBibitem{BazBezGas22}
\by A.~I.~Bazarova, A.~N.~Beznosikov, A.~V.~Gasnikov
\paper Linearly convergent gradient-free methods for minimization of parabolic approximation
\jour Компьютерные исследования и моделирование
\yr 2022
\vol 14
\issue 2
\pages 239--255
\mathnet{http://mi.mathnet.ru/crm966}
\crossref{https://doi.org/10.20537/2076-7633-2022-14-2-239-255}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/crm966
  • https://www.mathnet.ru/rus/crm/v14/i2/p239
  • Эта публикация цитируется в следующих 1 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Компьютерные исследования и моделирование
    Статистика просмотров:
    Страница аннотации:99
    PDF полного текста:28
    Список литературы:21
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024