Spectral conjugate gradient projection methods for large-scale monotone equations without Lipschitz continuity

Resumo Técnico: Métodos de Projeção de Gradiente Conjugado Espectral para Equações Monótonas de Grande Escala

Enunciado do Problema
O artigo aborda o problema de encontrar um vetor $x \in \Gamma$ tal que $G(x) = 0$, onde $G: \mathbb{R}^n \to \mathbb{R}^n$ é um mapeamento monótono contínuo e $\Gamma \subset \mathbb{R}^n$ é um conjunto não vazio, fechado e convexo. Esta formulação abrange problemas de desigualdade variacional, problemas de complementaridade, cálculos de equilíbrio químico, sensoriamento comprimido e regressão logística regularizada. Embora métodos do tipo Newton ofereçam convergência local rápida para $G$ diferenciável, são impraticáveis para problemas de grande escala devido aos requisitos de armazenamento de $O(n^2)$ e à necessidade de calcular jacobianos. Métodos de gradiente conjugado (CG) são preferidos em configurações de grande escala, pois exigem apenas avaliações de função e armazenamento de $O(n)$. No entanto, estender métodos CG para configurações com restrições geralmente depende de técnicas de projeção, e os métodos existentes frequentemente exigem continuidade Lipschitziana de $G$ ou sofrem com taxas de convergência subótimas.

Metodologia
Os autores propõem dois métodos de projeção livres de derivadas que integram um parâmetro espectral adaptativo $\lambda_k$ em estruturas de gradiente conjugado estabelecidas. Ambos os métodos utilizam a técnica de projeção de Solodov–Svaiter, que envolve calcular uma direção de descida, realizar uma busca linear para gerar um ponto trial, construir um hiperplano separador baseado na monotonicidade de $G$ e projetar a iteração atual sobre este hiperplano.

1. GMOPCGM (Método de Gradiente Conjugado de Perry Ótimo Generalizado Modificado):
   Este método generaliza o Método de Gradiente Conjugado de Perry Ótimo Modificado (MOPCGM) de Sabi'u et al. A direção de busca é derivada de uma matriz de Perry ótima modificada, onde o parâmetro de escala é substituído por um parâmetro espectral adaptativo $\lambda_k$. O parâmetro $\lambda_k$ é limitado dentro de $[\alpha_{\min}, \alpha_{\max}]$ e é atualizado usando razões espectrais do tipo Barzilai–Borwein baseadas na curvatura local ($s_{k-1}$ e $v_{k-1}$). A direção de busca resultante satisfaz uma condição de descida suficiente independente da busca linear.

2. GCGPM (Método de Projeção de Gradiente Conjugado Generalizado):
   Este método generaliza o CGPM de Zheng et al., que é baseado no parâmetro de Hager–Zhang. Os autores introduzem um parâmetro espectral Dai–Liao $\lambda_k$ na fórmula de atualização. Similarmente ao GMOPCGM, o parâmetro espectral adapta-se à geometria local do problema. A direção de busca é construída para garantir descida suficiente.

Principais Contribuições

• Derivação de Novas Direções de Busca: O artigo deriva duas novas direções de busca que generalizam as estruturas existentes MOPCGM e CGPM por meio de um parâmetro espectral $\lambda_k$.
• Independência da Descida Suficiente: É provado que ambos os métodos propostos satisfazem uma condição de descida suficiente ($G_k^T p_k \leq -c \|G_k\|^2$) que vale independentemente da estratégia de busca linear.
• Convergência Global sob Suposições Mais Fracas:
  • Para o GMOPCGM, a convergência global é estabelecida sob as Suposições A1 (conjunto solução não vazio) e A2 (monotonicidade) apenas. Crucialmente, este resultado não exige a continuidade Lipschitziana de $G$.
  • Para o GCGPM, a convergência global é provada sob as suposições padrão A1–A3, que incluem a continuidade Lipschitziana.
• Eficácia Prática: Os métodos são testados em 18 problemas de referência com dimensões de até 120.000, bem como em aplicações em sensoriamento comprimido e regressão logística regularizada.

Resultados Numéricos
Os autores conduziram extensos experimentos numéricos comparando o GMOPCGM e o GCGPM contra três métodos existentes: MOPCGM, CGPM e STTDFPM.

• Problemas de Referência: Em 5.400 execuções (18 problemas, 6 dimensões, 10 pontos iniciais), o GCGPM alcançou a maior taxa de convergência (96,9%) e o menor número mediano de iterações (10) e avaliações de função (52). O GMOPCGM convergiu em 93,0% das instâncias com uma mediana de 28 iterações, uma melhoria significativa em relação ao seu predecessor MOPCGM (160 iterações).
• Sensoriamento Comprimido: Em tarefas de recuperação de sinal com regularização $\ell_1$, ambos os métodos propostos convergiram em todas as 240 instâncias de teste. O GCGPM e o GMOPCGM exigiram significativamente menos iterações e tempo de CPU em comparação com o MOPCGM, que falhou em 20 instâncias. Todos os métodos alcançaram erro quadrático médio (MSE) comparável na recuperação do sinal.
• Regressão Logística Regularizada: Em conjuntos de dados de classificação binária do mundo real, ambos os métodos propostos convergiram em todas as 60 instâncias. O GMOPCGM reduziu o número mediano de iterações de 2.447 (MOPCGM) para 313, demonstrando o benefício da generalização espectral para equações monótonas não lineares. O GCGPM foi o mais eficiente, exigindo 184 iterações medianas.

Significância e Alegações
O artigo afirma que a integração de parâmetros espectrais adaptativos em estruturas de projeção de gradiente conjugado oferece uma abordagem robusta para resolver equações monótonas de grande escala. A principal significância teórica reside na prova de convergência para o GMOPCGM, que remove a exigência de continuidade Lipschitziana — um gargalo comum na análise de métodos livres de derivadas para equações monótonas. Na prática, os resultados demonstram que a generalização espectral melhora consistentemente o desempenho sobre os métodos base em termos de velocidade de convergência e custo computacional, tornando os algoritmos propostos adequados para aplicações de alta dimensão em processamento de sinais e aprendizado de máquina. Os autores observam que trabalhos futuros poderiam estender a análise de convergência do GCGPM para o cenário pseudomonótono e explorar técnicas de aceleração inercial.