Программирование
Журнал публикует статьи по всем проблемам, связанным с теоретическим и практическим программированием: операционные системы, технологии программирования, языки программирования и компиляторы, параллельное программирование, верификация и тестирование программ, машинная графика, компьютерная алгебра и т.п.
Журнал предназначен для исследователей, практиков и студентов.
Журнал рецензируется, включен в список ВАК для опубликования работ соискателей ученых степеней.
Журнал основан в 1975 году.
Свидетельство о регистрации СМИ: № 0110181 от 04.02.1993
Текущий выпуск
№ 6 (2023)
АНАЛИЗ ДАННЫХ
ВВЕДЕНИЕ
АДАПТИВНЫЕ МЕТОДЫ ДЛЯ ВАРИАЦИОННЫХ НЕРАВЕНСТВ С ОТНОСИТЕЛЬНО ГЛАДКИМИ И ОТНОСИТЕЛЬНО СИЛЬНО МОНОТОННЫМИ ОПЕРАТОРАМИ
Аннотация
Статья посвящена некоторым адаптивным методам для вариационных неравенств с относительно гладкими и относительно сильно монотонными операторами. Отталкиваясь от недавно предложенного проксимального варианта экстраградиентного метода для такого класса задач, мы детально исследуем метод с адаптивно подбираемыми значениями параметров. Доказана оценка скорости сходимости этого метода. Результат обобщен на класс вариационных неравенств с относительно сильно монотонными \(\delta \)-обобщенно гладкими операторами вариационного неравенства. Для задачи гребневой регрессии и вариационного неравенства, связанного с параллелепипедно-симплексными играми, выполнены численные эксперименты, демонстрирующие эффективность предложенной методики адаптивного подбора параметров в ходе реализации алгоритма.
Адаптивный вариант алгоритма Франк–Вульфа для задач выпуклой оптимизации
Аннотация
В данной работе исследовался вариант метода Франк–Вульфа для задач выпуклой оптимизации с адаптивным подбором параметра шага, соответствующего информации о гладкости целевой функции (константа Липшица градиента). Получены теоретические оценки качества выдаваемого методом приближенного решения с использованием адаптивно подобранных параметров Lk. На классе задач на выпуклом допустимом множестве с выпуклой целевой функцией гарантируемая скорость сходимости предложенного метода сублинейна. Рассмотрено сужение этого класса задач (целевая функция с условием градиентного доминирования) и получена оценка скорости сходимости с использованием адаптивно подбираемых параметров Lk. Важной особенностью полученного результата является проработка ситуации, при которой можно гарантировать после завершения итерации уменьшение невязки функции не менее чем в 2 раза. В то же время использование адаптивно подобранных параметров в теоретических оценках позволяет применять метод как для гладких, так и для негладких задач при условии выполнения критерия выхода из итерации. Для гладких задач можно доказать, что теоретические оценки метода гарантированно оптимальны с точностью до умножения на постоянный множитель. Выполнены вычислительные эксперименты, и проведено сравнение с двумя другими алгоритмами, в ходе чего была продемонстрирована эффективность алгоритма для ряда как гладких, так и негладких задач.
ДЕЦЕНТРАЛИЗОВАННЫЙ МЕТОД УСЛОВНОГО ГРАДИЕНТА НА ПЕРЕМЕННЫХ ВО ВРЕМЕНИ ГРАФАХ
Аннотация
В данной работе рассматривается обобщение децентрализованного алгоритма Франк-Вульфа на переменные во времени сети, исследуются свойства сходимости алгоритма и проводятся соответственные численные эксперименты. Меняющаяся сеть моделируется как детерминированная или стохастическая последовательность графов.
ОБ УСКОРЕННЫХ ПОКОМПОНЕНТНЫХ МЕТОДАХ ПОИСКА РАВНОВЕСИЙ В ДВУХСТАДИЙНОЙ МОДЕЛИ РАВНОВЕСНОГО РАСПРЕДЕЛЕНИЯ ТРАНСПОРТНЫХ ПОТОКОВ
Аннотация
Поиск равновесия в двухстадийной модели транспортных потоков сводится к решению специальной негладкой задачи выпуклой оптимизации с двумя группами разных переменных. Для численного решения данной задачи в статье предложено использовать ускоренный блочно-покомпонентный метод Нестерова–Стиха со специальным выбором вероятностей блоков на каждой итерации (одного из двух). Теоретические оценки сложности такого подхода могут заметно улучшать оценки используемых ранее подходов. Однако в общем случае не гарантируют более быстрой сходимости. В статье проведены численные эксперименты с предложенными алгоритмами.
Устойчивая алгебраическая связность
Аннотация
Алгебраическая связность графа определяется как второе собственное число лапласиана. Данная величина является одной из численных характеристик, показывающих насколько граф связен. Однако данная метрика не учитывает возможных изменений для графа. При этом, стоит заметить, что удаление даже одной вершины или ребра может сделать граф несвязным. Данная работа посвящена разработке метрик на основе алгебраической связности, которые принимают во внимание возможность таких модификаций и дают представление об устойчивости сети. Кроме этого, мы приводим обобщения некоторых известных методов оптимизации для наших версий робастной алгебраической связности. Также данная работа содержит некоторые численные эксперименты, демонстрирующие эффективность предложенных подходов.
БЕЗГРАДИЕНТНЫЕ АЛГОРИТМЫ ДЛЯ РЕШЕНИЯ СТОХАСТИЧЕСКИХ СЕДЛОВЫХ ЗАДАЧ ОПТИМИЗАЦИИ С УСЛОВИЕМ ПОЛЯКА–ЛОЯСИЕВИЧА
Аннотация
Данная работа фокусируется на решения подкласса стохастической невыпукло-невогнутой задачи оптимизации черного ящика с седловой точкой, которая удовлетворяет условию Поляка–Лоясиевича. Для решения такой задачи мы предоставляем первый, насколько нам известно, безградиентный алгоритм, подход к созданию которого основывается на применении градиентной аппроксимации (ядерной аппроксимации) к алгоритму стохастического градиентного спуска подъема со смещенным оракулом. Мы представляем теоретические оценки, гарантирующие глобальную линейную скорость сходимости к желаемой точности. Теоретические результаты мы проверяем на модельном примере, сравнивая с алгоритмом, использующую Гауссовскую аппроксимацию.