Локальный поиск в квадратичной игре двух лиц

Рассматривается бескоалиционная игра двух лиц в нормальной форме с квадратичными функциями потерь игроков. Предполагается, что функция потерь каждого игрока является строго выпуклой квадратичной функцией собственной переменной. Зависимость потерь от переменной другого участника линейна и определяется соответствующим билинейным слагаемым. Задача поиска равновесия по Нэшу в рассматриваемой игре сводится к эквивалентной минимаксной задаче с помощью подхода Никайдо–Исода. Поскольку для данной игры не удаётся аналитически решить «внутреннюю» задачу максимизации, то полученная минимаксная задача представляется как задача минимизации невыпуклой неявно заданной функции на множестве ситуаций игры. «Внутренняя» задача максимизации, являющаяся выпуклой, заменяется двойственной по Лагранжу задачей, благодаря чему целевая функция исходной задачи оптимизации представляется в виде разности двух выпуклых функций (осуществляется d.c.-разложение), при этом функция, определяющая вогнутую часть разложения, по-прежнему задана неявно. В работе предлагается естественный способ линеаризации вогнутого слагаемого и, на основе этого, применение итеративного метода локального поиска для d.c.-функций. В данном методе очередная точка выбирается как решение выпуклой задачи оптимизации, в которой целевая функция получается из исходной целевой функции путём линеаризации вогнутого слагаемого в d.c.-разложении. В силу невыпуклости рассматриваемой нами задачи, предлагается использовать локальный поиск в сочетании с мультистартом. Известно, что минимальное значение целевой функции равно нулю и множество точек, где оно достигается, совпадает с множеством равновесий в исходной игре, благодаря чему можно легко проверить, является ли полученная локальным спуском стационарная точка равновесием по Нэшу. Приводятся результаты численного тестирования локального поиска для d.c.-функций и его сравнение с рядом существующих методов поиска равновесия на случайно сгенерированных задачах.