Hongbo Sun предложил алгоритм для вариационных неравенств: 6400 задач, 1e-5

Hongbo Sun представил универсальный алгоритм для вариационных неравенств (VI), которому не нужна монотонность отображения. Метод работает с произвольными непрерывными отображениями на многогранных областях и гарантирует глобальную линейную сходимость. Для невырожденных решений она точная, для вырожденных достигается любая заранее заданная точность. На 6400 случайных задачах с размерностью до 1024 разрыв опускался ниже 1e-5 в каждом случае.

Почему вариационные неравенства до сих пор считаются тяжёлой задачей

Вариационное неравенство требует найти в допустимом множестве точку, в которой поле направлений не даёт улучшения ни в одну допустимую сторону. Под эту формулу подпадают задачи оптимизации, дополнительности, седловые задачи и игровые равновесия. Именно поэтому VI регулярно всплывают там, где несколько участников оптимизируют разные цели одновременно: в минимаксных постановках и многоагентных системах.

Проблема в том, что гарантии у большинства классических методов держатся на монотонности или близких условиях. Без них алгоритмы начинают циклить или расходятся. В аннотации сама автор называет разработку универсальных алгоритмов с глобальными гарантиями сходимости давней нерешённой задачей.

Расслоение вместо ручного обхода особенностей

Метод построен на path-following: решение ищут, отслеживая непрерывную траекторию от простой стартовой точки. Слабое место такого подхода известно. В особых точках гарантии ломаются, и траектория может упереться в тупик.

Sun сначала преобразует общее VI в гладкое VI на симплексе. Затем множество решений системы KKT с неподвижной точкой описывается как расслоение над симплексом, названное «fixed-point bundle». Геометрия расслоения разделяет два вида движения: по базе и по слоям. Благодаря этому в одну схему укладываются три вещи, которые обычно решают отдельно:

• выбор стартовой точки;
• само движение по траектории;
• обход особенностей.

В особой точке алгоритм просто перемещается по слою в невырожденную точку и продолжает путь оттуда.

Что показали эксперименты

Проверка проводилась на случайно сгенерированных задачах. Ключевые параметры:

• число экземпляров: 6400;
• максимальная размерность: 1024;
• достигнутая точность: разрыв ниже 1e-5 на всех экземплярах;
• сходимость для невырожденных решений: глобальная линейная, точная;
• сходимость для вырожденных решений: глобальная линейная до любой заданной точности;
• допущения о монотонности или подобных свойствах: не требуются;
• область определения: многогранники, которые сводятся к симплексу;
• код и данные: github.com/shb20tsinghua/FiberBundle_VI;
• продолжение: arXiv:2609.16158, где рамка расширена на произведения симплексов для вычисления равновесий Нэша.

Стоит отметить показатель «в каждом случае». Для алгоритма без структурных допущений отсутствие отказов на таком числе случайных задач практически важнее, чем скорость на удобных примерах.

Где это пригодится и что проверять

Прямого продуктового применения у работы нет, это фундаментальный инструмент. Но спрос на него понятен тем, кто строит многоагентное обучение, игровые постановки и задачи равновесия. Для них отсутствие гарантий вне монотонного случая остаётся постоянной болью.

Репозиторий открыт, поэтому первое, что стоит сделать практикам, это прогнать метод на собственных структурированных задачах. Случайные экземпляры хорошо показывают устойчивость, но не заменяют проверку на реальных данных, где у отображений есть своя структура. Отдельно стоит проверить, как растёт стоимость шага при размерностях выше 1024 и как ведёт себя алгоритм при очень высоких требованиях к точности на вырожденных решениях. Дальнейшее развитие уже обозначено: расширение на произведения симплексов откроет путь к вычислению равновесий Нэша в играх с несколькими участниками.