Geometric Conditions for Lossless Convexification in Linear Optimal Control with Discrete-Valued Inputs

Resumo Técnico: Condições Geométricas para Convexificação sem Perda em Controle Ótimo Linear com Entradas Discretas

1. Problema Abordado

O artigo foca no desafio de resolver Problemas de Controle Ótimo (OCP) para sistemas lineares que possuem entradas de valor discreto (ex: atuadores do tipo liga/desliga ou com níveis finitos de magnitude).

• Desafio Principal: A natureza de valores discretos transforma o problema de otimização em um Programa de Inteiros Misto (MIP). MIPs são computacionalmente intratáveis para aplicações em tempo real e críticas para a segurança (como controle de veículos autônomos ou espaçonaves), pois carecem de garantias gerais de convergência e exibem crescimento exponencial no tempo de execução.
• Contexto Específico: O problema é formulado na forma Lagrangeana, onde o objetivo é minimizar o esforço de controle (norma $L_1$), o que é crucial para aplicações espaciais de economia de combustível (ex: manobras de rendezvous com propulsores a gás frio).
• Limitações de Métodos Existentes: Métodos baseados em aprendizado de máquina não garantem optimalidade, e métodos de homotopia introduzem aproximações que podem ser custosas e não garantem a solução exata.

2. Metodologia

Os autores propõem uma convexificação sem perda (lossless convexification) que reformula o problema MIP não-convexo como um Programa Convexo (CP) equivalente, garantindo que a solução do problema relaxado seja idêntica à solução do problema original.

A metodologia segue os seguintes passos:

1. Transformação Epígrafe (Lagrange para Mayer):

   • O problema original na forma Lagrangeana (minimização de integral de custo) é transformado em um problema na forma Mayer (minimização do estado final).
   • Introduz-se uma variável de estado de custo $x_c(t)$ e uma variável de entrada de folga $\mu(t)$, definindo um conjunto de entrada aumentado $\tilde{U}_e$.
   • O novo conjunto de entrada é a interseção do casco convexo das entradas discretas com o epígrafo da função de custo.

2. Condições Geométricas e Normalidade:

   • O trabalho demonstra que, sob certas condições geométricas no conjunto de entrada (especificamente que os vértices do conjunto relaxado $\tilde{U}_e$ correspondam aos elementos do conjunto original discreto $U$), a relaxação convexa é exata.
   • Preservação da Normalidade: Um dos pontos centrais é provar que a normalidade forte do sistema original $(A, B)$ é preservada na transformação para o sistema aumentado $(\hat{A}, \hat{B})$.
   • Teorema de Relaxação: Se o sistema é fortemente normal, a solução ótima do problema convexo relaxado ocorre necessariamente nos pontos extremos (vértices) do conjunto de entrada relaxado. Como os vértices de $\tilde{U}_e$ são, por construção, os pontos discretos originais, a solução do problema convexo retorna automaticamente uma entrada discreta.

3. Algoritmo:

   • O problema é discretizado e resolvido como um Programa Convexo (usando solvers como ECOS via CVXPY), evitando a necessidade de solvers de inteiros mistos.

3. Principais Contribuições

• Extensão da Convexificação sem Perda: O artigo estende resultados anteriores (que focavam na forma Mayer) para problemas na forma Lagrangeana, provando que a transformação via epígrafe preserva a normalidade do sistema.
• Condições Geométricas Explícitas: Estabelece condições claras sobre o conjunto de entrada e a função de custo (função poliedral convexa) que garantem que a relaxação convexa não introduza "perda" de optimalidade.
• Viabilidade em Tempo Real: Demonstra que é possível calcular controles ótimos com restrições discretas em tempo real, eliminando a necessidade de otimização de inteiros mistos.
• Validação Teórica e Numérica: Fornece provas rigorosas de que a solução do problema convexo relaxado é a solução exata do problema original com entradas discretas.

4. Resultados Numéricos

Os autores validaram a abordagem em uma simulação de rendezvous (encontro) de satélites em órbita baixa (LEO):

• Cenário: Um satélite "chaser" com propulsores a gás frio (conjunto de entrada $U = \{-u_{max}, 0, u_{max}\}^3$) deve encontrar um satélite "chief" em órbita elíptica.
• Desempenho Computacional:
  • Em simulações de Monte Carlo (1000 condições iniciais), o tempo médio de solução foi de 0,083 segundos (mediana de 0,069s).
  • Todos os tempos de solução ficaram abaixo de 1 segundo, atendendo aos requisitos de atualização de guia de navegação do projeto SPLICE da NASA (que visa 1 segundo).
• Qualidade da Solução:
  • A distância média da solução para o conjunto discreto ($\bar{d}(u)$) foi extremamente baixa (~0,0038), indicando que a solução do problema convexo é efetivamente discreta.
  • As trajetórias de controle mostraram-se "escalonadas" (piecewise constant), aderindo estritamente aos valores discretos permitidos.
• Robustez: A qualidade da solução (aderência ao conjunto discreto) melhorou exponencialmente com o aumento da resolução da grade, enquanto o tempo de solução cresceu linearmente.

5. Significado e Impacto

• Aplicações Críticas: A técnica permite a implementação em tempo real de estratégias de controle ótimo de combustível para espaçonaves e sistemas robóticos que utilizam atuadores discretos, algo que antes era computacionalmente proibitivo.
• Eficiência: Substitui solvers complexos e lentos de MIP por solvers convexos rápidos e confiáveis.
• Futuro: O trabalho abre caminho para a aplicação de Model Predictive Control (MPC) em sistemas com restrições de entrada discretas e a inclusão de restrições de estado mantendo a convexificação sem perda.

Em resumo, o artigo fornece uma ferramenta teórica e prática robusta para resolver problemas de controle ótimo com restrições discretas de forma eficiente, garantindo que a solução computacional seja matematicamente equivalente à solução ótima do problema original não-convexo.