Extragradient methods with complexity guarantees for hierarchical variational inequalities

Resumen Técnico: Métodos de Extragradiente con Garantías de Complejidad para Desigualdades Variacionales Jerárquicas

Formulación del Problema
El artículo aborda el problema de resolver problemas de equilibrio jerárquico dentro de un espacio de Hilbert separable real $Z$. El objetivo central es encontrar una solución $z^*$ a una desigualdad hemi-variacional (HVI) definida sobre el conjunto de soluciones de otra HVI. Formalmente, el problema (P) consiste en 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$$
donde $S_2 = \text{zer}(F_2 + \partial \ell_2)$ es el conjunto de soluciones de la HVI de nivel inferior. Aquí, $F_1, F_2$ son operadores monotónicos, y $\ell_1, \ell_2$ son funciones propias, convexas y semicontinuas inferiores.

Esta formulación unifica varias clases de problemas, incluyendo:

• Optimización bilevel simple (donde $\ell_1, \ell_2$ son suaves o compuestas).
• Desigualdades variacionales anidadas (donde $\ell_1=0$ y $\ell_2$ es una función indicadora).
• Problemas de equilibrio de Nash generalizados (GNEPs) jerárquicos y conjuntamente convexos.
• Control óptimo bajo restricciones de VI.

Metodología
Los autores proponen un Método de Extragradiente Optimista (Algoritmo 1) basado en la regularización de Tikhonov. A diferencia de enfoques previos que requieren evaluaciones dobles del operador por iteración (por ejemplo, el extragradiente estándar), este método utiliza una evaluación "pasada" del operador para reducir el costo computacional a una sola evaluación del operador por iteración.

El algoritmo construye una secuencia de operadores regularizados $V_k = F_2 + \sigma_k F_1$ y funciones regularizadas $G_k = \ell_2 + \sigma_k \ell_1$, donde $(\sigma_k)$ es una secuencia de regularización decreciente que converge a cero. El esquema de iteración es:

1. Predicción: $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. Corrección: $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})))$

El análisis se basa en supuestos geométricos específicos:

• Agudeza Débil (Weak Sharpness): Se asume que el conjunto de soluciones de nivel inferior $S_2$ satisface una condición de agudeza débil $(\alpha, \rho)$, vinculando la función de brecha con la distancia al conjunto de soluciones.
• Condición de Attouch-Czarnecki: Se impone una condición de sumabilidad sobre los tamaños de paso y los parámetros de regularización para asegurar la acotación de las iteraciones.
• Coherencia Jerárquica: Una condición que asegura que el dominio de la función de nivel superior está contenido dentro del dominio de nivel inferior.

Contribuciones Clave

1. Formulación General del Problema: El artículo extiende la literatura existente (específicamente [1, 57]) al manejar términos compuestos convexos generales $\ell_1, \ell_2$ en espacios de Hilbert potencialmente de dimensión infinita, en lugar de restringirse a dimensiones finitas con funciones indicadoras sobre conjuntos compactos.
2. Eficiencia Algorítmica: El método propuesto requiere solo una evaluación de los operadores $F_1, F_2$ por iteración, mejorando respecto a los métodos de extragradiente de doble llamada utilizados en trabajos previos.
3. Garantías de Complejidad: Los autores establecen tasas de complejidad de iteración en el peor de los casos tanto para la brecha de factibilidad (nivel inferior) como para la brecha de optimalidad (problema jerárquico) utilizando promedios ergódicos adecuadamente construidos.
4. Eliminación de la Suposición de Compacidad: A diferencia de otros análisis de complejidad que requerían dominios compactos, este trabajo deriva tasas de convergencia sin asumir que los dominios de las desigualdades variacionales sean compactos, apoyándose en la agudeza débil geométrica y técnicas de análisis asintótico.

Resultos Principales
El artículo establece tasas de convergencia sublineales para el promedio ergódico $\bar{z}_K$ generado por el algoritmo. Asumiendo una secuencia de regularización $\sigma_k = O(k^{-\delta})$ con $\delta \in (0,1)$:

• Brecha de Factibilidad: La función de brecha para el problema de nivel inferior converge a una tasa de $O(k^{-\delta})$.
• Brecha de Optimalidad: La función de brecha para todo el problema jerárquico converge a una tasa de $O(k^{-(1-\delta)})$.
• Tasas Mejoradas: Bajo la suposición de que el operador de nivel superior $F_1$ es fuertemente monotónico, el artículo deriva tasas mejoradas, mostrando la convergencia hacia una solución única.
• Convergencia Débil: Bajo la condición de agudeza débil, se demuestra que la secuencia de iteraciones converge débilmente a una solución en $S_1$.

Significancia y Reivindicaciones
Los autores afirman que sus resultados igualan y mejoran el estado del arte en términos de complejidad de iteración y la generalidad de la formulación del problema. Específicamente, el artículo:

• Extiende las garantías de complejidad desde la optimización bilevel simple y casos específicos de VI hacia una amplia clase de problemas de HVI jerárquicos en espacios de dimensión infinita.
• Demuestra que la condición de "agudeza débil", utilizada previamente de forma primordial en la optimización jerárquica, puede traducirse efectivamente al entorno de las desigualdades variacionales para establecer declaraciones de complejidad unificadas.
• Proporciona un marco metodológico utilizando técnicas de análisis de ecuaciones evolutivas no autónomas para manejar dominios no acotados, una contribución que los autores sugieren puede ser útil para otros problemas de equilibrio jerárquico.

El artículo concluye señalando que, si bien el análisis actual cubre entornos deterministas, el trabajo futuro podría explorar formulaciones estocásticas y métodos acelerados. Se presentan experimentos numéricos sobre equilibrios de Nash jerárquicos y problemas min-max con restricciones (incluyendo Ecuaciones de Valor Absoluto Generalizadas) para validar los hallazgos teóricos.