Hongbo Sun propõe algoritmo para desigualdades variacionais: 6400 problemas, 1e-5

Hongbo Sun apresentou um algoritmo universal para desigualdades variacionais (VI) que dispensa a monotonicidade do mapeamento. O método funciona com mapeamentos contínuos arbitrários em domínios poliédricos e garante convergência linear global. Para soluções não degeneradas, ela é exata; para as degeneradas, atinge-se qualquer precisão definida de antemão. Em 6400 problemas aleatórios com dimensão de até 1024, o gap ficou abaixo de 1e-5 em todos os casos.

Por que as desigualdades variacionais ainda são consideradas um problema difícil

Uma desigualdade variacional exige encontrar, no conjunto viável, um ponto em que o campo vetorial não ofereça melhora em nenhuma direção viável. Essa formulação abrange problemas de otimização, de complementaridade, problemas de ponto de sela e equilíbrios de jogos. Por isso, as VI aparecem com frequência onde vários participantes otimizam objetivos diferentes ao mesmo tempo: em formulações minimax e em sistemas multiagente.

O problema é que as garantias da maioria dos métodos clássicos dependem de monotonicidade ou de condições próximas. Sem elas, os algoritmos entram em ciclos ou divergem. No resumo do artigo, o desenvolvimento de algoritmos universais com garantias globais de convergência é descrito como um problema antigo e ainda em aberto.

Fibrado em vez de contornar singularidades manualmente

O método se baseia em path-following: a solução é buscada ao acompanhar uma trajetória contínua a partir de um ponto inicial simples. A fraqueza dessa abordagem é conhecida. Em pontos singulares, as garantias se rompem, e a trajetória pode chegar a um beco sem saída.

Sun primeiro transforma a VI geral em uma VI suave sobre um simplex. Em seguida, descreve o conjunto de soluções do sistema KKT com ponto fixo como um fibrado sobre o simplex, chamado de “fixed-point bundle”. A geometria do fibrado separa dois tipos de movimento: pela base e pelas fibras. Com isso, três tarefas que normalmente são resolvidas em separado cabem em um único esquema:

• escolha do ponto inicial;
• movimento ao longo da trajetória;
• contorno de singularidades.

Em um ponto singular, o algoritmo simplesmente se desloca pela fibra até um ponto não degenerado e continua o percurso a partir dali.

O que os experimentos mostraram

A validação foi feita em problemas gerados aleatoriamente. Principais parâmetros:

• número de instâncias: 6400;
• dimensão máxima: 1024;
• precisão alcançada: gap abaixo de 1e-5 em todas as instâncias;
• convergência para soluções não degeneradas: linear global, exata;
• convergência para soluções degeneradas: linear global, com qualquer precisão previamente definida;
• suposições de monotonicidade ou propriedades semelhantes: não são necessárias;
• domínio de definição: poliedros que se reduzem a um simplex;
• código e dados: github.com/shb20tsinghua/FiberBundle_VI;
• continuação: arXiv:2609.16158, em que o arcabouço é estendido a produtos de simplex para o cálculo de equilíbrios de Nash.

Vale destacar o resultado “em todos os casos”. Para um algoritmo sem suposições estruturais, a ausência de falhas em tantos problemas aleatórios importa mais na prática do que a velocidade em exemplos convenientes.

Onde isso pode ser útil e o que verificar

O trabalho não tem aplicação direta em produtos; é uma ferramenta fundamental. Mas a demanda por ela é clara para quem constrói aprendizado multiagente, formulações de jogos e problemas de equilíbrio. Para esse público, a falta de garantias fora do caso monótono continua sendo uma dor constante.

Como o repositório é aberto, o primeiro passo para os profissionais é rodar o método em seus próprios problemas estruturados. Instâncias aleatórias mostram bem a robustez, mas não substituem a verificação em dados reais, nos quais os mapeamentos têm estrutura própria. Também convém checar como o custo de cada passo cresce em dimensões acima de 1024 e como o algoritmo se comporta com exigências de precisão muito altas em soluções degeneradas. O desenvolvimento seguinte já está indicado: a extensão a produtos de simplex abrirá caminho para o cálculo de equilíbrios de Nash em jogos com vários participantes.