Variable aggregation for nonlinear optimization problems

Resumo Técnico: Agregação de Variáveis para Problemas de Otimização Não Linear

1. Problema e Contexto

A agregação de variáveis (substituir uma variável definida por uma restrição de igualdade pela sua expressão algébrica) é uma técnica de pré-processamento (pre-solve) bem estabelecida em programação linear e inteira mista. No entanto, seu impacto em Programação Não Linear (NLP) é menos explorado e documentado.

Embora algumas linguagens de modelagem (como AMPL, AIMMS e Pyomo) e solvers comerciais implementem formas básicas de agregação, não há consenso sobre quais estratégias são mais eficazes. O desafio central é equilibrar a redução do número de variáveis (o que pode acelerar a fatoração da matriz KKT) com o risco de aumentar a densidade e a complexidade não linear das restrições restantes (o que pode tornar a avaliação do Hessian mais custosa e prejudicar a convergência).

O objetivo deste trabalho é formalizar a agregação de variáveis como um algoritmo de pré-processamento para NLPs, desenvolver novas estratégias e analisar empiricamente seu impacto na estrutura do problema, tempo de resolução e confiabilidade de convergência.

2. Metodologia

Os autores formalizam a agregação como a eliminação de um subconjunto de variáveis $v$ e restrições de igualdade $\tilde{g}(u, v) = 0$, desde que a matriz Jacobiana $\nabla_v \tilde{g}$ seja não singular. Eles propõem que, se as restrições tiverem uma estrutura triangular estrita inferior, a eliminação pode ser feita explicitamente sem necessidade de métodos iterativos implícitos.

Para identificar quais variáveis e restrições podem ser agregadas, o trabalho compara seis métodos distintos, divididos em duas categorias principais:

A. Estratégias de Agregação Aproximada Máxima (Aggressivas):
Buscam eliminar o maior número possível de variáveis, independentemente da estrutura resultante.

1. Greedy (GR): Um algoritmo ganancioso que itera sobre as restrições e seleciona variáveis que aparecem linearmente e não foram usadas anteriormente, garantindo a triangularidade inferior.
2. Linear Matching (LM): Um algoritmo baseado em grafos bipartidos.
   • Calcula um matching máximo no grafo de incidência linear.
   • Decompõe o subgrafo induzido em forma triangular de blocos.
   • Aplica o método Greedy dentro de cada bloco diagonal para extrair o maior subconjunto triangular inferior possível.
   • É provado que este método é NP-completo para encontrar o máximo exato, mas o heurístico proposto fornece limites inferiores e superiores para o número de eliminações.

B. Estratégias de Preservação de Estrutura (Conservadoras):
Buscam agregar variáveis sem aumentar a densidade (número de não-nulos) ou a complexidade não linear das restrições restantes. Todas utilizam restrições com no máximo duas variáveis.
3. Linear Degree-1 (LD1): Elimina variáveis fixas (restrições do tipo $y = c$).
4. Equal Coefficient Degree-2 (ECD2): Elimina variáveis usando restrições lineares do tipo $y = x + c$ (coeficientes com mesma magnitude), preservando os valores do Jacobiano.
5. Linear Degree-2 (LD2): Elimina variáveis usando apenas restrições lineares com duas variáveis ($y = ax + b$), preservando a linearidade.
6. Degree-2 (D2): Elimina variáveis usando restrições com até duas variáveis (podendo ser não lineares, como $y = x^2$), mas garantindo que o número de variáveis por restrição não aumente.

Experimentação:
Os métodos foram testados em quatro problemas de otimização não linear de diferentes domínios:

• Otimização dinâmica de uma coluna de destilação (DIST).
• Operação ótima de um reator de leito móvel (MB).
• Otimização dinâmica de uma rede de gasodutos (PIPE).
• Fluxo de potência ótimo em corrente alternada (ACOPF).

Os testes foram realizados com o solver IPOPT (método de pontos interiores), variando parâmetros para avaliar a confiabilidade de convergência em 121 combinações de parâmetros por problema.

3. Contribuições Principais

1. Formalização Teórica: Estabelecimento de uma condição suficiente verificável para que um subconjunto de variáveis e restrições admita uma agregação explícita válida (baseada na triangularidade estrita inferior do Jacobiano).
2. Novo Algoritmo: Desenvolvimento do algoritmo de Linear Matching (LM), uma heurística aproximada para maximizar a agregação, com garantias teóricas sobre seus limites de desempenho.
3. Análise de Compensação (Trade-off): Demonstração de que estratégias agressivas (como LM e GR) reduzem significativamente o número de variáveis, mas podem criar matrizes Hessianas mais densas e complexas, tornando-se um gargalo computacional.
4. Melhoria de Confiabilidade: Evidência empírica de que a agregação de variáveis, em geral, melhora a confiabilidade de convergência de solvers de pontos interiores, mesmo que nem sempre reduza o tempo total de resolução.

4. Resultados Principais

• Estrutura do Problema:

  • As estratégias de agregação máxima (LM e GR) eliminaram entre 70% e 90% das variáveis em alguns modelos, enquanto as estratégias de preservação de estrutura eliminaram menos de 60%.
  • Estratégias agressivas aumentaram significativamente a densidade (número de não-nulos) e a não-linearidade das restrições restantes.
  • Estratégias de preservação de estrutura mantiveram a densidade e a complexidade não linear aproximadamente constantes.

• Tempo de Resolução (Runtime):

  • Não há uma regra universal: a agregação pode acelerar ou desacelerar a solução.
  • Em problemas como Pipeline e Distillation, a agregação reduziu o tempo de solução devido à menor fatoração da matriz KKT.
  • No problema OPF (Fluxo de Potência), a agregação aumentou o tempo de solução devido ao aumento no número de restrições de desigualdade e iterações necessárias.
  • Gargalo do Hessian: Para estratégias agressivas (especialmente LM), a avaliação do Hessian tornou-se o gargalo principal (chegando a 75% do tempo total em alguns casos), superando a fatoração da matriz KKT.

• Confiabilidade de Convergência:

  • Resultado Crítico: Todas as estratégias de agregação testadas melhoraram a taxa de convergência em comparação com o modelo original em todos os problemas testados.
  • Estratégias mais agressivas (D2, GR, LM) tenderam a ter taxas de convergência superiores (até 100% no caso da destilação com D2) em comparação com o modelo original (que falhou em cerca de 15-30% dos casos de parâmetros).
  • A hipótese é que a formulação reduzida mantém os iterados mais próximos do conjunto viável do problema original, resultando em matrizes Jacobianas e KKT melhor condicionadas.

5. Significado e Conclusões

O trabalho demonstra que a agregação de variáveis é uma ferramenta poderosa para aumentar a robustez de solvers de otimização não linear, permitindo que eles resolvam instâncias que antes falhariam.

• Recomendação Prática: Os autores recomendam a implementação de métodos de agregação como opções de pré-processamento em ambientes de modelagem.
• Estratégia Ideal: A estratégia Degree-2 (D2) é destacada como a melhor opção geral. Ela oferece um equilíbrio ideal: elimina um número significativo de variáveis (melhorando a confiabilidade) sem aumentar excessivamente a densidade ou a complexidade não linear (evitando o gargalo do Hessian).
• Futuro: O estudo sugere que a interação entre estratégias de agregação e métodos de convergência global (como busca linear e regiões de confiança) merece análise teórica mais profunda. Além disso, a criação de conjuntos de testes padronizados para avaliar a confiabilidade de solvers não lineares é um passo necessário para avançar o campo.

Em suma, a agregação de variáveis não é apenas uma redução de tamanho, mas uma reformulação estrutural que pode transformar um problema difícil de resolver em um problema estável e confiável, desde que a estratégia escolhida equilibre a redução de variáveis com a preservação da estrutura algébrica.