Текущий выпуск Номер 6, 2020 Том 12
Результаты поиска по 'выпуклый функционал':
Найдено статей: 4
  1. Алкуса М.С.
    О некоторых стохастических методах зеркального спуска для условных задач онлайн-оптимизации
    Компьютерные исследования и моделирование, 2019, т. 11, № 2, с. 205-217

    Задача выпуклой онлайн-оптимизации естественно возникают в случаях, когда имеет место обновления статистической информации. Для задач негладкой оптимизации хорошо известен метод зеркального спуска. Зеркальный спуск — это расширение субградиентного метода для решения негладких выпуклых задач оптимизации на случай неевкидова расстояния. Работа посвящена стохастическим аналогам недавно предложенных методов зеркального спуска для задач выпуклой онлайн-оптимизации с выпуклыми липшицевыми (вообще говоря, негладкими) функциональными ограничениями. Это означает, что вместо (суб)градиента целевого функционала и функционального ограничения мы используем их стохастические (суб)градиенты. Точнее говоря, допустим, что на замкнутом подмножестве $n$-мерного векторного пространства задано $N$ выпуклых липшицевых негладких функционалов. Рассматривается задача минимизации среднего арифметического этих функционалов с выпуклым липшицевым ограничением. Предложены два метода для решения этой задачи с использованием стохастических (суб)градиентов: адаптивный (не требует знания констант Липшица ни для целевого функционала, ни для ограничения), а также неадаптивный (требует знания константы Липшица для целевого функционала и ограничения). Отметим, что разрешено вычислять стохастический (суб)градиент каждого целевого функционала только один раз. В случае неотрицательного регрета мы находим, что количество непродуктивных шагов равно $O$($N$), что указывает на оптимальность предложенных методов. Мы рассматриваем произвольную прокс-структуру, что существенно для задач принятия решений. Приведены результаты численных экспериментов, позволяющие сравнить работу адаптивного и неадаптивного методов для некоторых примеров. Показано, что адаптивный метод может позволить существенно улучшить количество найденного решения.

    Просмотров за год: 42.
  2. Пасечнюк Д.А., Стонякин Ф.С.
    Об одном методе минимизации выпуклой липшицевой функции двух переменных на квадрате
    Компьютерные исследования и моделирование, 2019, т. 11, № 3, с. 379-395

    В статье получены оценки скорости сходимости по функции для недавно предложенного Ю.Е. Нестеровым метода минимизации выпуклой липшицевой функции двух переменных на квадрате с фиксированной стороной. Идея метода — деление квадрата на меньшие части и постепенное их удаление так, чтобы в оставшейся достаточно малой части все значения целевой функции были достаточно близки к оптимальному. При этом метод заключается вр ешении вспомогательных задач одномерной минимизации вдоль разделяющих отрезков и не предполагает вычисления точного значения градиента целевого функционала. Основной результат работы о необходимом количестве итераций для достижений заданной точности доказан вкла ссе гладких выпуклых функций, имеющих липшицев градиент. При этом отмечено, что свойство липшицевости градиента достаточно потребовать не на всем квадрате, а лишь на некоторых отрезках. Показано, что метод может работать при наличии погрешностей решения вспомогательных одномерных задач, а также при вычислении направлений градиентов. Также описана ситуация, когда возможно пренебречь временными затратами (или уменьшить их) на решение вспомогательных одномерных задач. Для некоторых примеровэк спериментально продемонстрировано, что метод может эффективно работать и на некоторых классах негладких функций. При этом построен пример простой негладкой функции, для которой при неудачном выборе субградиента даже в случае точного решения вспомогательных одномерных задач может не наблюдаться сходимость метода. Проведено сравнение работы метода Ю.Е. Нестерова, метода эллипсоидов и градиентного спуска для некоторых гладких выпуклых функций. Эксперименты показали, что метод Ю.Е. Нестерова может достигать желаемой точности решения задачи за меньшее (в сравнении с другими рассмотренными методами) время. В частности, замечено, что при увеличении точности искомого решения время работы метода Ю.Е. Нестерова может расти медленнее, чем время работы метода эллипсоидов.

    Просмотров за год: 34.
  3. Стонякин Ф.С., Степанов А.Н., Гасников А.В., Титов А.А.
    Метод зеркального спуска для условных задач оптимизации с большими значениями норм субградиентов функциональных ограничений
    Компьютерные исследования и моделирование, 2020, т. 12, № 2, с. 301-317

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

  4. Гасников А.В., Кубентаева М.Б.
    Поиск стохастических равновесий в транспортных сетях с помощью универсального прямо-двойственного градиентного метода
    Компьютерные исследования и моделирование, 2018, т. 10, № 3, с. 335-345

    В статье рассматривается одна из задач транспортного моделирования — поиск равновесного распределения транспортных потоков в сети. Для описания временных издержек и распределения потоков в сети, представляемой с помощью графа, используется классическая модель Бэкмана. При этом поведение агентов не является полностью рациональным, что описывается посредством введения марковской логит-динамики: в каждый момент времени водительвыбирает маршрут случайно согласно распределению Гиббса с учетом текущих временных затрат на ребрах графа. Таким образом, задача сводится к поиску стационарного распределения для данной динамики, которое является стохастическим равновесием Нэша – Вардропа в соответствующей популяционной игре загрузки транспортной сети. Так как данная игра является потенциальной, эта задача эквивалентна минимизации некоторого функционала от распределения потоков, причем стохастичностьпро является в появлении энтропийной регуляризации. Для полученной задачи оптимизации построена двойственная задача. Для ее решения применен универсальный прямо-двойственный градиентный метод. Его особенность заключается в адаптивной настройке на локальную гладкость задачи, что особенно важно при сложной структуре целевой функции и невозможности априорно оценитьг ладкость с приемлемой точностью. Такая ситуация имеет место в рассматриваемой задаче, так как свойства функции сильно зависят от транспортного графа, на который мы не накладываем сильных ограничений. В статье приводится описание алгоритма, в том числе подробно рассмотрено применение численного дифференцирования для вычисления значения и градиента целевой функции. В работе представлены теоретическая оценка времени работы алгоритма и результаты численных экспериментов на примере небольшого американского города.

    Просмотров за год: 28.

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

Журнал входит в Перечень российских рецензируемых научных журналов, в которых должны быть опубликованы основные научные результаты диссертаций на соискание ученых степеней доктора и кандидата наук ВАК, группы специальностей: 01.01.00, 01.02.00.
 

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

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

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

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