Гасников, А. В. Об эффективности одного метода рандомизации зеркального спуска в задачах онлайн оптимизации [Текст] / А. В. Гасников, Ю, Е. Нестеров, В. Г. Спокойный // Журнал вычислительной математики и математической физики. - 2015. - Т. 55, № 4. - С. 582-598. - Библиогр.: c. 597-598 . - ISSN 0044-4669
Рубрики: Математика Вычислительная математика Кл.слова (ненормированные): антагонистическая матричная игра -- задачи онлайн оптимизации -- метод двойственных усреднений -- метод зеркального спуска -- многорукие бандиты -- рандомизация -- стохастическая оптимизация -- экспоненциальное взвешивание -- эффективность метода рандомизации Аннотация: Предлагается рандомизированная онлайн версия метода зеркального спуска. Отличие от имеющихся версий заключается в способе рандомизации. Рандомизация выводится не на этапе вычисления субградиента функции, как это повсеместно принято, а на этапе проектирования на единичный симплекс. В результате получается покомпонентный субградиентный спуск со случайным выбором компоненты, допускающий онлайн интерпретацию. Это наблюдение, например, позволило единообразно проинтерпретировать результаты о взвешивании экспертных решений и предложить наиболее эффективный способ поиска равновесия в антагонистической матричной игре с разреженной матрицей. Доп.точки доступа: Нестеров Ю. Е.; Спокойный, В. Г. Нет сведений об экземплярах (Источник в БД не найден) |
Гасников, А. В. Об эффективных рандомизированных алгоритмах поиска вектора PageRank [Текст] / А. В. Гасников, Д. Ю. Дмитриев // Журнал вычислительной математики и математической физики. - 2015. - Т. 55, № 3. - С. 355-371. - Библиогр.: c. 370-371 . - ISSN 0044-4669
Рубрики: Математика Вычислительная математика Кл.слова (ненормированные): Markov chain Carlo -- PageRank -- Кнута-Яо алгоритм -- алгоритм Кнута-Яо -- метод зеркального спуска -- поиск вектора PageRank -- поиск ранжирующего вектора -- рандомизация -- рандомизированные алгоритмы -- стохастическая оптимизация Аннотация: В работе рассматриваются два рандомизированных способа поиска вектора PageRank. На основе современных неравенств концентрации меры в работе приводятся новые оценки времени работы такого метода, учитывающие специфику матрицы P. В основе второго способа лежит идея сведения поиска ранжирующего вектора к поиску равновесия в антагонистической матричной игре. Доп.точки доступа: Дмитриев, Д. Ю. Нет сведений об экземплярах (Источник в БД не найден) |
Гасников, А. В. Двойственные методы поиска равновесий в смешанных моделях распределения потоков в больших транспортных сетях [Текст] / А. В. Гасников, Е. В. Гасникова, Ю. Е. Нестеров // Журнал вычислительной математики и математической физики. - 2018. - Т. 58, № 9. - С. 1447-1454. - Библиогр.: с. 1454 (20 назв. ) . - ISSN 0044-4669
Рубрики: Математика Вычислительная математика Кл.слова (ненормированные): грузоперевозки -- задача поиска распределения потоков в транспортной сети -- метод зеркального спуска -- поиск кратчайших путей -- пропускная способность транспортной сети -- прямо-двойственный метод -- равновесное распределение потоков в транспортной сети -- распределение грузовых потоков -- эффективное распараллеливание Аннотация: В работе изучается задача поиска равновесного распределения потоков в транспортной сети, часть ребер которой характеризуется функциями затрат, а часть ребер характеризуется пропускной способностью и постоянными затратами на прохождение в отсутствие затора. Такие модели (получившие название смешанные модели) возникают, например, при описании грузоперевозок РЖД. Частным случаем смешанной модели является семейство моделей равновесного распределения потоков по путям: BMW-модель (модель Бэкмана), модель стабильной динамики. Поиск равновесия в смешанной модели сводится к решению задачи выпуклой оптимизации. В данной статье строится двойственная задача, которая решается методом зеркального спуска (двойственных усреднений). Приводятся два различных способа восстановления решения исходной (прямой) задачи. Показывается, что предложенные подходы допускают эффективное распараллеливание. Результаты о скорости сходимости предложенных численных методов соответствуют известным нижним оракульным оценкам для данного класса задач (с точностью до мультипликативных констант). Доп.точки доступа: Гасникова, Е. В.; Нестеров, Ю. Е. Нет сведений об экземплярах (Источник в БД не найден) |
Прямо-двойственный метод зеркального спуска для условных задач стохастической оптимизации [Текст] / А. С. Баяндина [и др.] // Журнал вычислительной математики и математической физики. - 2018. - Т. 58, № 11. - С. 1794-1803. - Библиогр.: с. 1803 (24 назв. ) . - ISSN 0044-4669
Рубрики: Математика Вычислительная математика Кл.слова (ненормированные): вероятность больших уклонений -- двойственность задач -- задачи выпуклой стохастической оптимизации -- метод зеркального спуска -- рандомизация -- стохастическая выпуклая оптимизация -- условная оптимизация -- условные задачи стохастической оптимизации Аннотация: Изучается возможность распространения метода зеркального спуска для задач выпуклой стохастической оптимизации на выпуклые задачи условной стохастической оптимизации (с функциональными ограничениями вида неравенств). Предлагается конкретный метод, состоящий в том, что осуществляется шаг обычного зеркального спуска, если ограничения не сильно нарушены и осуществляется шаг зеркального спуска по нарушенному ограничению, в случае если оно нарушено достаточно сильно. При специальном выборе параметров метода устанавливается (оптимальная для данного класса задач) оценка скорости его сходимости (с точными оценками вероятностей больших уклонений). Устанавливается (в детерминированном случае) также прямо-двойственность предложенного метода. Другими словами, показывается, что по генерируемой методом последовательности можно восстановить решение двойственной задачи (с той же точностью, с которой решается прямая задача). Обсуждается эффективность метода для задач с огромным числом ограничений. Отметим, что в полученную в работе оценку убывания зазора двойственности не входит неизвестный размер решения двойственной задачи. Доп.точки доступа: Баяндина, А. С.; Гасников, А. В.; Гасникова, Е. В.; Мациевский, C. В. Нет сведений об экземплярах (Источник в БД не найден) |