О двойственном методе градиентного спуска для задачи о распределении ресурсов в многоагентных системах

Рассматривается последовательность блочно-сепарабельных задач выпуклого программирования, описывающих распределение ресурсов в многоагентных системах. Построено несколько итерационных алгоритмов назначения цен на ресурсы. При различных предположениях о функциях полезности и ресурсных ограничениях получены оценки для среднего отклонения целевой функции от оптимального значения (сожаления) и величины невязки в ограничениях. Среднее здесь понимается как математическое ожидание для независимых одинаково распределённых данных, и как временно́е среднее в задаче онлайн оптимизации. Анализ задачи проводится на основе методов онлайн оптимизации и теории двойственности. Рассмотренные алгоритмы основаны на информации о разности между суммарным спросом и предложением, которая порождается реакциями агентов на цены и соответствует невязке в ограничениях.