Применение ​методов​​ глобальной оптимизации ​для поиска равновесия по Нэшу в квадратичной игре n лиц

Рассматривается некооперативная игра n лиц с функциями потерь, квадратичными по собственной переменной игрока и билинейными по парам переменных различных игроков. Ограничения игроков считаются линейными. С помощью подхода Никайдо-Исода задача поиска равновесия по Нэшу в данной игре сводится к задаче оптимизации функции оптимального значения, т.е. к задаче неявной оптимизации. При этом целевая функция оказывается невыпуклой. Предлагается алгоритм для решения полученной задачи, основанный на построении нелинейных опорных функций и оценок оптимального значения сверху и снизу. Данный алгоритм в результате работы либо находит глобальное решение задачи, либо устанавливает факт отсутствия равновесных ситуаций в игре. В оставшейся части доклада вводится стандартное предположение о строгой выпуклости функций потерь игроков по собственным переменным, благодаря чему "внутренняя" задача минимизации, определяющая функцию оптимального значения, имеет строго выпуклую целевую функцию. Замена "внутренней" задачи двойственной по Лагранжу позволяет свести исходную постановку к задаче d.c. оптимизации. Предлагается способ линеаризации вогнутого слагаемого в d.c. разложении и соответствующий метод локального поиска, представляющий из себя серию выпуклых экстремальных задач с явными целевыми функциями. В докладе приводятся результаты численного эксперимента.