Extragradient methods with complexity guarantees for hierarchical variational inequalities

Resumo Técnico: Métodos de Extragradiente com Garantias de Complexidade para Desigualdades Variacionais Hierárquicas

Formulação do Problema
O artigo aborda o problema de resolver problemas de equilíbrio hierárquicos dentro de um espaço de Hilbert separável real $Z$. O objetivo central é encontrar uma solução $z^*$ para uma hemi-desigualdade variacional (HVI) definida sobre o conjunto de solução de outra HVI. Formalmente, o problema (P) é encontrar $z^* \in S_2$ tal que:
$$\langle F_1(z^*), z - z^* \rangle + \ell_1(z) - \ell_1(z^*) \geq 0 \quad \forall z \in S_2$$
onde $S_2 = \text{zer}(F_2 + \partial \ell_2)$ é o conjunto de soluções da HVI de nível inferior. Aqui, $F_1, F_2$ são operadores monotônicos, e $\ell_1, \ell_2$ são funções próprias, convexas e semicontínuas inferiores.

Esta formulação unifica várias classes de problemas, incluindo:

• Otimização bilevel simples (onde $\ell_1, \ell_2$ são suaves ou compostas).
• Desigualdades variacionais aninhadas (onde $\ell_1=0$ e $\ell_2$ é uma função indicadora).
• Problemas de Equilíbrio de Nash Generalizados (GNEPs) conjuntamente convexos e hierárquicos.
• Controle ótimo sob restrições de VI.

Metodologia
Os autores propõem um Método de Extragradiente Otimista (Algoritmo 1) baseado na regularização de Tikhonov. Diferente de abordagens anteriores que exigem dupla avaliação de operadores por iteração (ex: extragradiente padrão), este método utiliza uma avaliação de operador "passada" para reduzir o custo computacional para uma única avaliação de operador por iteração.

O algoritmo constrói uma sequência de operadores regularizados $V_k = F_2 + \sigma_k F_1$ e funções regularizadas $G_k = \ell_2 + \sigma_k \ell_1$, onde $(\sigma_k)$ é uma sequência de regularização decrescente convergindo para zero. O esquema de iteração é:

1. Predição: $z_{k+1/2} = \text{prox}_{t_k G_k}(z_k - t_k (F_2(z_{k-1/2}) + \sigma_k F_1(z_{k-1/2})))$
2. Correção: $z_{k+1} = \text{prox}_{t_k G_k}(z_k - t_k (F_2(z_{k+1/2}) + \sigma_k F_1(z_{k+1/2})))$

A análise baseia-se em suposições geométricas específicas:

• Nitidez Fraca (Weak Sharpness): Assume-se que o conjunto de solução de nível inferior $S_2$ satisfaz uma condição de nitidez fraca $(\alpha, \rho)$, vinculando a função de gap à distância do conjunto de solução.
• Condição de Attouch-Czarnecki: Uma condição de somabilidade sobre os tamanhos de passo e parâmetros de regularização é imposta para garantir a limitação das iterações.
• Coerência Hierárquica: Uma condição que garante que o domínio da função de nível superior está contido no domínio de nível inferior.

Principais Contribuições

1. Formulação de Problema Geral: O artigo estende a literatura existente (especificamente [1, 57]) ao lidar com termos compostos convexos gerais $\ell_1, \ell_2$ em espaços de Hilbert potencialmente de dimensão infinita, em vez de se restringir a dimensões finitas com funções indicadoras sobre conjuntos compactos.
2. Eficiência Algorítmica: O método proposto requer apenas uma avaliação dos operadores $F_1, F_2$ por iteração, melhorando em relação aos métodos de extragradiente de dupla chamada usados em trabalhos anteriores.
3. Garantias de Complexidade: Os autores estabelecem taxas de complexidade de iteração no pior caso tanto para o gap de viabilidade (nível inferior) quanto para o gap de otimalidade (problema hierárquico) usando médias ergódicas adequadamente construídas.
4. Remoção da Suposição de Compacidade: Ao contrário de análises de complexidade anteriores que exigiam domínios compactos, este trabalho deriva taxas de convergência sem assumir que os domínios das desigualdades variacionais são compactos, baseando-se em nitidez fraca geométrica e técnicas de análise assintótica.

Principais Resultados
O artigo estabelece taxas de convergência sublineares para a média ergódica $\bar{z}_K$ gerada pelo algoritmo. Assumindo uma sequência de regularização $\sigma_k = O(k^{-\delta})$ com $\delta \in (0,1)$:

• Gap de Viabilidade: A função de gap para o problema de nível inferior converge a uma taxa de $O(k^{-\delta})$.
• Gap de Otimalidade: A função de gap para todo o problema hierárquico converge a uma taxa de $O(k^{-(1-\delta)})$.
• Taxas Melhoradas: Sob a suposição de que o operador de nível superior $F_1$ é fortemente monotônico, o artigo deriva taxas melhoradas, mostrando convergência para uma solução única.
• Convergência Fraca: Sob a condição de nitidez fraca geométrica, mostra-se que a sequência de iterações converge fracamente para uma solução em $S_1$.

Significância e Alegações
Os autores alegam que seus resultados igualam e melhoram o estado da arte em termos de complexidade de iteração e generalidade da formulação do problema. Especificamente, o artigo:

• Estende as garantias de complexidade de otimização bilevel simples e casos específicos de VI para uma ampla classe de problemas de HVI hierárquicos em espaços de dimensão infinita.
• Demonstra que a condição de "nitidez fraca", anteriormente usada primariamente em otimização hierárquica, pode ser efetivamente traduzida para o cenário variacional para estabelecer declarações de complexidade unificadas.
• Fornece um framework metodológico usando técnicas de análise de equações de evolução não autônomas para lidar com domínios não limitados, uma contribuição que os autores sugerem que pode ser útil para outros problemas de equilíbrio hierárquico.

O artigo conclui observando que, embora a análise atual cubra cenários determinísticos, trabalhos futuros poderiam explorar formulações estocásticas e métodos acelerados. Experimentos numéricos em equilíbrios de Nash hierárquicos e problemas min-max restritos (incluindo Equações de Valor Absoluto Generalizadas) são apresentados para validar os achados teóricos.