A condensing approach for linear-quadratic optimization with geometric constraints

1. O Problema Abordado

O artigo foca em problemas de otimização de dimensão finita da forma:
$$\min_{x} f(x) := \frac{1}{2}\langle x, Qx \rangle + \langle q, x \rangle$$
sujeito a:
$$Ax \in C$$

Onde:

• $x \in \mathbb{R}^n$ são as variáveis de decisão.
• $f(x)$ é uma função quadrática convexa (definida por uma matriz simétrica $Q$ e vetor $q$).
• $A \in \mathbb{R}^{m \times n}$ é uma matriz linear.
• $C \subset \mathbb{R}^m$ é um conjunto fechado, não vazio, que pode ser não convexo.

Contexto e Motivação:
Problemas com custos quadráticos e restrições poliedrais são comuns em controle e processamento de sinais. No entanto, aplicações modernas exigem a modelagem de condições lógicas, restrições de cardinalidade e dinâmicas não suaves (como contato mecânico ou comutação). O conjunto $C$ pode representar conjuntos de complementaridade, restrições de "ou-ou" (either-or), ou restrições que desaparecem (vanishing). A dificuldade principal é que, embora $C$ possa ser não convexo, é prático computar projeções sobre ele (oráculo de projeção). Métodos padrão de Programação Não Linear (NLP) frequentemente falham nesses casos devido à violação de qualificações de restrição em pontos viáveis interessantes.

---

2. Metodologia Proposta

A abordagem combina o Método do Lagrangiano Aumentado (AL) com uma técnica de condensação que explora a estrutura linear-quadrática do problema.

2.1. Estrutura Lagrangiana Aumentada

O problema original é reformulado introduzindo uma variável auxiliar $z$, resultando em:
$$\min_{x, z} f(x) + I_C(z) \quad \text{sujeito a} \quad Ax - z = 0$$
Onde $I_C$ é a função indicadora do conjunto $C$. O método utiliza um esquema de Lagrangiano Aumentado com salvaguardas (safeguarded), onde as subproblemas são resolvidos até estacionariedade aproximada. A função Lagrangiana inclui termos de penalidade quadrática para a restrição de igualdade e um termo de regularização proximal (Tikhonov) para estabilidade numérica.

2.2. Técnica de Condensação (O Núcleo da Contribuição)

A inovação principal reside na exploração da estrutura do subproblema do Lagrangiano Aumentado.

• Observação Chave: Para um $z \in C$ fixo, o subproblema em relação a $x$ torna-se um problema de minimização quadrática não restrita (ou com restrições lineares de igualdade "seguras").
• Mapeamento Único: Devido à convexidade estrita da função objetivo em relação a $x$, existe um minimizador único $x^*(z)$. Isso define um mapeamento linear $X_k: C \to \mathbb{R}^n$.
• Função Marginal: Substituindo $x$ por $X_k(z)$, o problema original de dimensão $n+m$ é reduzido a um problema de dimensão $m$ apenas na variável $z$:
  $$\min_{z \in C} M_k(z) := \min_{x} L_{\sigma_k}(x, z, \hat{x}_k, \hat{y}_k)$$
• Vantagens:
  1. Redução de Dimensão: O problema reduzido tem $m$ variáveis em vez de $n+m$.
  2. Melhor Condicionamento: O problema condensado é numericamente mais estável.
  3. Custo Computacional: O gradiente da função marginal $M_k(z)$ é barato de calcular e Lipschitz contínuo globalmente.
  4. Restrições de Igualdade "Seguras": O método permite tratar restrições de igualdade lineares (como dinâmicas de controle) como restrições de nível inferior (hard constraints) no subproblema, sem relaxá-las no Lagrangiano Aumentado, preservando a esparsidade e simetria do sistema linear resultante.

2.3. Algoritmo e Convergência

O algoritmo (ALG 3.1) itera entre:

1. Resolver o subproblema condensado $(CAL_k)$ para obter $z_k$.
2. Recuperar $x_k = X_k(z_k)$.
3. Atualizar multiplicadores e parâmetros de penalidade.

O método herda garantias teóricas de convergência do framework do Lagrangiano Aumentado: pontos limite viáveis são pontos KKT (sob qualificações de restrição), e pontos limite inviáveis são pontos estacionários para o problema de viabilidade (minimização da violação de restrição).

---

3. Contribuições Principais

1. Abordagem Híbrida: Integra a robustez teórica do Lagrangiano Aumentado para restrições geométricas não convexas com a eficiência computacional de métodos que exploram estrutura linear-quadrática.
2. Condensação Eficiente: Desenvolveu uma técnica que elimina a variável $x$ analiticamente no subproblema, reduzindo drasticamente o tamanho e o mau condicionamento do problema a ser resolvido pelo solver interno.
3. Generalidade e Flexibilidade: O método lida com conjuntos $C$ não convexos complexos (complementaridade, lógica, etc.) acessando-os apenas através de um oráculo de projeção, sem necessidade de regularizações específicas para cada tipo de restrição.
4. Tratamento de Restrições de Igualdade: Introduz uma forma de tratar restrições de igualdade lineares (como equações de estado) como restrições "duras" no subproblema, acelerando a convergência sem comprometer a estabilidade.
5. Validação Empírica: Demonstra que a abordagem é superior a métodos genéricos e comparável a solvers especializados para problemas específicos.

---

4. Resultados Numéricos

Os autores testaram o método em três benchmarks distintos, comparando configurações de solvers (nmpg vs. panoc+) e formulações (estendida vs. condensada com restrições suaves vs. duras).

• Problema de Valor Inicial (Sistemas com Comutação):
  • Um sistema dinâmico com descontinuidade reformulado como sistema de complementaridade linear.
  • Resultado: A formulação condensada superou consistentemente a formulação estendida. O tratamento "duro" das restrições de igualdade forneceu os melhores tempos de execução. O solver panoc+ (com extrapolação quasi-Newton) geralmente superou o nmpg.
• Problema de Obstáculo (Discretizado):
  • Controle ótimo de um problema de obstáculo com solução degenerada.
  • Resultado: O método permitiu aumentar a discretização de $N=64$ para $N=256$ mantendo tempos de execução razoáveis e reduzindo o número de iterações internas de milhões para milhares, comparado a trabalhos anteriores.
• Controle de Rastreamento AFTI-16 (Aeronave):
  • Controle de uma aeronave com restrições geométricas no controle (condição "ou-ou": apenas um atuador ativo por vez).
  • Resultado: A abordagem condensada com restrições duras mostrou a maior vantagem. O solver encontrou sequências de controle de alta qualidade rapidamente, mesmo com o conjunto admissível não convexo, demonstrando robustez em simulações de controle em malha fechada.

Conclusão dos Resultados: A condensação reduz significativamente o tempo de execução e melhora a robustez. A escolha do solver interno (panoc+) também impactou positivamente o desempenho, mas a formulação condensada foi o fator determinante para a eficiência.

---

5. Significado e Impacto

Este trabalho é significativo porque oferece uma solução prática e teoricamente fundamentada para uma classe de problemas de otimização que são onipresentes em engenharia de controle e tomada de decisão, mas que são difíceis de resolver com técnicas padrão de Programação Não Linear devido à não convexidade e falhas de qualificação de restrição.

Ao combinar a flexibilidade do Lagrangiano Aumentado (que lida bem com não convexidade via projeção) com a eficiência de métodos de condensação (que exploram a estrutura quadrática), o autor propõe um algoritmo escalável. Isso permite resolver problemas de controle ótimo com restrições lógicas e de complementaridade em escalas maiores do que era anteriormente viável, sem a necessidade de desenvolver solvers específicos para cada tipo de restrição não convexa. A técnica é particularmente valiosa para aplicações em tempo real ou em sistemas de grande escala onde o condicionamento numérico e a velocidade de convergência são críticos.