Mix-CALADIN: A Distributed Algorithm for Consensus Mixed-Integer Optimization

1. Problema Abordado

O artigo foca em problemas de otimização distribuída com consenso e variáveis inteiras mistas (MIP), com ênfase específica em variáveis booleanas (0 ou 1).

• Contexto: A otimização MIP é crucial em aplicações como design de redes de transporte, seleção de sensores e micro-redes elétricas. No entanto, à medida que a escala e complexidade aumentam, a resolução centralizada torna-se impraticável devido a demandas de memória e tempo computacional.
• Desafio Principal: A maioria dos algoritmos distribuídos existentes para MIPs depende de solucionadores de programação inteira mista locais (centralizados ou distribuídos) para resolver subproblemas, o que limita a escalabilidade e a aplicabilidade em tempo real. Além disso, muitos métodos heurísticos existentes carecem de garantias teóricas de convergência, especialmente para problemas não convexos.
• Objetivo: Desenvolver um algoritmo distribuído que resolva problemas MIP (convexos e não convexos) sem depender de solucionadores MIP locais, mantendo garantias rigorosas de convergência.

2. Metodologia: Mix-CALADIN

Os autores propõem o Mix-CALADIN, uma extensão do framework Consensus Augmented Lagrangian Alternating Direction Inexact Newton (CALADIN). O algoritmo opera em duas etapas distintas:

Etapa I: Relaxação Contínua e Inicialização

• Abordagem: As restrições de variáveis inteiras (booleanas) são relaxadas, permitindo que as variáveis assumam valores contínuos.
• Execução: Aplica-se o algoritmo CALADIN padrão para resolver o problema relaxado.
• Resultado: Esta etapa fornece um limitante inferior teórico para o problema original e gera um ponto inicial de alta qualidade ($\tilde{z}^*$) para a segunda etapa.
• Convergência: Herda as propriedades de convergência do CALADIN original: convergência linear global para problemas convexos e convergência linear local para problemas não convexos.

Etapa II: Refinamento para Soluções Booleanas

• Estrutura: Um framework de otimização de dois níveis (inner e outer loop) que utiliza o ponto inicial da Etapa I.
• Nível Interno (Inner Loop):
  • Os agentes calculam gradientes locais.
  • Um coordenador resolve um problema de Programação Quadrática (QP) com restrições de caixa ($0 \leq z_d \leq 1$).
  • Adiciona-se um termo de penalidade convexa aproximada, $\alpha(1 - 2z_d^{[k]})^\top z_d$, ao objetivo para guiar as variáveis contínuas em direção aos valores booleanos (0 ou 1).
• Nível Externo (Outer Loop):
  • Monitora a violação da restrição booleana (medida por $(1-z_d)^\top z_d$).
  • Se a violação for maior que uma tolerância, o parâmetro de penalidade $\alpha$ é aumentado exponencialmente ($\alpha \leftarrow \beta \alpha$) e o nível interno é reiniciado.
  • O processo termina quando a solução satisfaz as restrições booleanas dentro da tolerância.
• Diferencial: Diferente de métodos que arredondam variáveis diretamente (heurísticos), o Mix-CALADIN usa uma aproximação convexa suave e um esquema de penalidade progressiva para garantir estabilidade numérica e convergência.

3. Principais Contribuições

1. Novo Algoritmo Distribuído: Primeiro trabalho a empregar o Consensus ALADIN para resolver problemas distribuídos de otimização inteira mista sem utilizar solucionadores MIP locais.
2. Garantias de Convergência Rigorosas:
   • Estabelece convergência global linear para problemas convexos e local linear para não convexos na Etapa I.
   • Prova a convergência da Etapa II sob a suposição de que as funções objetivo são Lipschitz contínuas, desde que o parâmetro de penalidade seja suficientemente grande.
3. Abordagem em Duas Etapas: Combina a eficiência da relaxação contínua com um mecanismo de refinamento iterativo para forçar a integridade das variáveis, evitando a instabilidade numérica comum em métodos de arredondamento direto.
4. Implementação Leve: Inclui esquemas de regularização para garantir que as matrizes Hessianas sejam definidas positivas, mesmo em problemas não convexos.

4. Resultados Numéricos

Os autores validaram o algoritmo em MATLAB com dois casos de estudo:

• Caso 1 (Não Convexo): Problema de localização de sensores com restrições mistas booleanas. O algoritmo demonstrou capacidade de lidar com paisagens de otimização complexas.
• Caso 2 (Convexo): Comparação com o método ADMM baseado em projeção (Takapoui et al., 2020).
  • Desempenho: O Mix-CALADIN convergiu para soluções de melhor qualidade do que o ADMM baseado em projeção.
  • Convergência: As curvas de erro mostraram taxas de convergência linear consistentes com a teoria.
  • Comportamento da Função de Energia: As simulações mostraram o padrão esperado de "degraus" na função de energia, onde o aumento de $\alpha$ eleva temporariamente o custo, seguido pela redução pelo loop interno, até a satisfação das restrições.

5. Significado e Impacto

O Mix-CALADIN preenche uma lacuna crítica na literatura de otimização distribuída:

• Independência de Solucionadores: Elimina a necessidade de caixas-pretas (solucionadores MIP comerciais) nos nós locais, permitindo a implementação em redes de dispositivos com recursos limitados.
• Teoria vs. Prática: Oferece garantias teóricas de convergência (frequentemente ausentes em métodos heurísticos para MIP distribuído) para uma classe ampla de problemas, incluindo não convexos.
• Aplicabilidade: É particularmente relevante para sistemas de controle em rede, redes de sensores e micro-redes inteligentes onde a privacidade de dados e a descentralização são essenciais, e onde a presença de variáveis de decisão discretas (como liga/desliga) é comum.

Em suma, o artigo apresenta uma solução robusta e teoricamente fundamentada para um problema complexo, superando as limitações de escalabilidade e garantias de métodos anteriores.