Distributed and Decentralized Optimization Algorithms via Consensus ALADIN

Resumo Técnico: Algoritmos de Otimização Distribuída e Descentralizada via Consenso ALADIN

Formulação do Problema
Este artigo aborda o desafio da otimização de consenso distribuída e descentralizada, um componente crítico em aplicações como redes elétricas inteligentes, controle ótimo e aprendizado de máquina. O problema central envolve $N$ agentes, cada um possuindo uma função objetivo local $f_i(x_i)$, buscando minimizar a soma dessas funções enquanto garantem que todas as variáveis locais $x_i$ atinjam um consenso com uma variável global $z$ (ou seja, $x_i = z$). Os autores distinguem entre dois cenários:

1. Centralizado: Existe um coordenador central para agregar informações e resolver o subproblema de coordenação.
2. Descentralizado: Não existe um coordenador central; os agentes comunicam-se apenas com vizinhos imediatos sobre um grafo direcionado. Além disso, o cenário descentralizado incorpora comunicação quantizada, onde as mensagens estão sujeitas a largura de banda limitada e níveis de quantização ($\Delta$), introduzindo erros potenciais na troca de informações.

O artigo visa especificamente a extensão do framework ALADIN (Alternating Direction Inexact Newton baseado em Lagrangiano Aumentado) para problemas de consenso. Embora o ALADIN tenha demonstrado sucesso na alocação de recursos distribuída, sua aplicação direta à otimização de consenso enfrenta desafios estruturais, incluindo a falta de uma função objetivo global para a variável de consenso (impedindo a definição direta do Hessiano), a dependência de coordenadores centrais ou grafos não direcionados, e o alto custo de largura de banda na transmissão de informações de segunda ordem.

Metodologia
Os autores propõem o C-ALADIN (Consenso ALADIN), um framework que substitui o programa quadrático (QP) acoplado genérico usado no ALADIN padrão por um QP específico para consenso. A metodologia divide-se em variantes centralizadas e descentralizadas, cada uma oferecendo implementações de primeira e segunda ordem.

1. C-ALADIN Centralizado:

   • Variante de Segunda Ordem (Algoritmo 1): Os agentes resolvem subproblemas locais de Lagrangiano aumentado e transmitem apenas suas variáveis primais atualizadas para um coordenador. O coordenador reconstrói gradientes e aproximações do Hessiano usando atualizações BFGS baseadas nos dados recebidos, evitando a transmissão direta de informações de segunda ordem. Uma solução de forma fechada é derivada para o QP de consenso em grande escala, reduzindo significativamente a complexidade computacional.
   • Variante de Primeira Ordem: Para cenários onde a aproximação do Hessiano é difícil, as matrizes Hessianas são substituídas por matrizes identidade escaladas ($B_i = \rho I$). Isso simplifica as regras de atualização para uma forma semelhante ao Consenso ADMM, mas mantém a estrutura do ALADIN.

2. C-ALADIN Descentralizado com Comunicação Quantizada:

   • Primeira Ordem (Equação 27): Os agentes realizam otimização local e, em seguida, utilizam um protocolo de Consenso Médio Quantizado em Tempo Finito (FQAC) (Algoritmo 2) para estimar a variável global e os gradientes. Este protocolo opera sobre grafos direcionados e utiliza quantizadores assimétricos do tipo "mid-rise".
   • Segunda Ordem (Algoritmos 3 e 4): Duas variantes são propostas para problemas não convexos:
     • Bílevel (Algoritmo 3): Resolve o QP de consenso no loop interno usando o C-ALADIN descentralizado de primeira ordem.
     • Aproximada (Algoritmo 4): Emprega uma agregação inexata das matrizes Hessianas estimando médias de variáveis primais e gradientes via protocolo FQAC, recuperando depois uma aproximação do Hessiano BFGS localmente.

Principais Contribuições
O artigo faz as seguintes contribuições específicas à literatura:

• Framework C-ALADIN: Introduz uma formulação ALADIN adaptada para restrições de consenso, substituindo o acoplamento estilo alocação de recursos por um QP de consenso natural.
• Métodos Eficientes de Segunda Ordem: Desenvolve um C-ALADIN de segunda ordem que evita a transmissão direta do Hessiano, reconstruindo informações no coordenador (centralizado) ou via estimativa local (descentralizado), preservando a convergência local rápida enquanto reduz a sobrecarga de comunicação.
• Descentralização sobre Grafos Direcionados: Propõe variantes totalmente descentralizadas que operam sem um coordenador central e funcionam sobre topologias de comunicação direcionadas.
• Comunicação Quantizada: Integra protocolos de consenso quantizado em tempo finito ao framework ALADIN, permitindo operação sob restrições de largura de banda.
• Garantias de Convergência:
  • Estabelece convergência global para problemas convexos (tanto centralizados quanto descentralizados).
  • Estabelece convergência local para problemas não convexos.
  • Prova que, para o caso descentralizado quantizado, as iterações convergem para uma vizinhança do ótimo determinada pelo nível de quantização $\Delta$.

Resultados
Simulações numéricas foram conduzidas em problemas convexos (mínimos quadrados distribuídos) e não convexos (alocação de sensores).

• Caso Convexo: O C-ALADIN de primeira ordem proposto demonstrou convergência acelerada em comparação ao Consenso ADMM e outros métodos de última geração (por exemplo, Pull-FTERC, AsyAD-ADMM). As versões descentralizadas quantizadas alcançaram um compromisso favorável entre eficiência de comunicação (largura de banda reduzida via quantização) e precisão da solução.
• Caso Não Convexo: As variantes de segunda ordem (Algoritmos 1, 3 e 4) convergiram com sucesso para vizinhanças de pontos estacionários. Em contraste, as variantes de primeira ordem divergiram neste cenário, destacando a necessidade de informações de segunda ordem para consenso não convexo. As variantes descentralizadas de segunda ordem (Algoritmos 3 e 4) mantiveram velocidades de convergência comparáveis ao Algoritmo 1 centralizado, enquanto métodos existentes como o GIANT falharam em convergir na instância não convexa específica testada.
• Impacto da Quantização: Os resultados confirmaram que níveis de quantização menores ($\Delta$) resultam em maior precisão, enquanto níveis maiores reduzem o uso de largura de banda, consistente com os limites de erro teóricos derivados.

Significado e Afirmações
O artigo afirma que o C-ALADIN preenche lacunas críticas na literatura existente ao unificar três desafios anteriormente desconexos: adaptar o ALADIN para restrições de consenso, permitir a descentralização sobre grafos direcionados e suportar comunicação quantizada. Os autores afirmam que seus métodos retêm as propriedades de convergência rápida dos métodos de segunda ordem, enquanto reduzem substancialmente os custos de comunicação e computação em comparação com abordagens descentralizadas existentes.

O trabalho enfatiza que, embora o ALADIN típico pudesse teoricamente resolver esses problemas via reformulação, tal abordagem incorre em complexidade e sobrecarga de implementação significativas. O C-ALADIN oferece uma alternativa estrutural mais natural e eficiente. O artigo conclui que os algoritmos propostos fornecem uma solução robusta para otimização distribuída em grande escala, particularmente em ambientes com largura de banda de comunicação limitada e objetivos não convexos, embora reconheça que a caracterização teórica do efeito do parâmetro de penalidade $\rho$ nas taxas de convergência permanece um problema aberto para pesquisa futura.