Resumo Técnico: Desigualdades de Intervalo Conjunto para QCQPs Não Convexos

Declaração do Problema

O artigo aborda o desafio de gerar planos de corte eficazes para Programas Quadráticos com Restrições Quadráticas (QCQPs) não convexos, uma classe central de problemas em Programação Linear Inteira Mista (MINLP). Embora relaxações padrão como a Técnica de Reformulação-Linearização (RLT) e relaxações de Programação Semidefinida (SDP) (por exemplo, a relaxação de Shor) forneçam aproximações convexas, elas frequentemente sofrem de um compromisso entre força e esparsidade. Especificificamente, as reformulações de autovalores e as restrições SDP densas tipicamente destroem a esparsidade da formulação QCQP original, levando a cortes computacionalmente caros que são difíceis de integrar em solvers de MINLP. Os autores buscam um framework para derivar desigualdades válidas e fortes que preservem a esparsidade da formulação QCQP subjacente enquanto exploram a geometria não convexa.

Metodologia: Abordagem Projetar-Então-Elevar (Project-Then-Lift)

Os autores propõem uma estratégia de "projetar-então-elevar" inspirada nas desigualdades de Arredondamento de Inteiros Mistos (MIR) usadas em Programação Linear Inteira Mista (MILP). A metodologia procede da seguinte forma:

1. Desigualdades Base e Projeção:
   Partindo de duas desigualdades base válidas para a formulação QCQP estendida (envolvendo variáveis $x$ e a matriz elevada $X$), os autores definem um mapa afim $A_{JR}$ que projeta essas desigualdades em um espaço de imagem bidimensional. Sejam as desigualdades base $\phi_i + \langle \Theta_i, X \rangle + \theta_i^\top x \geq 0$ para $i=1,2$. A projeção mapeia pares $(X, x)$ viáveis para um vetor $y = (y_1, y_2)$, onde $y_i$ corresponde ao lado esquerdo da $i$-ésima desigualdade.

2. Análise de Intervalo Conjunto (Joint Range Analysis):
   O núcleo do método analisa o intervalo conjunto $F(\mathbb{R}^n)$ das duas funções quadráticas $f_1(x)$ e $f_2(x)$ associadas às desigualdades base. O conjunto de pontos projetados viáveis é a interseção deste intervalo conjunto com um cone simplicial $K_{JR}$ definido pelas desigualdades base.

   • Caso Não Convexo: Os autores caracterizam o fecho convexo do intervalo conjunto quando este é não convexo. Eles mostram que, sob condições específicas (dependência linear das partes quadráticas), o intervalo conjunto assume uma forma não convexa explícita, tal como a fronteira ou o exterior de uma bacia parabólica.
   • Caso Convexo: Quando o intervalo conjunto é convexo, eles fornecem uma representação de Programação Semidefinida (SDP).

3. Caracterização do Fecho e Derivação de Desigualdades:
   Os autores derivam uma descrição em forma fechada do fecho convexo do conjunto projetado ($H_{JR} = \text{cl}(\text{conv}(F(\mathbb{R}^n) \cap K_{JR}))$).

   • Para casos não convexos, o fecho é descrito pela interseção do cone simplicial com a bacia parabólica ou seu complemento, resultando frequentemente em cortes "secantes" (cortes de interseção) definidos pelos pontos onde os raios do cone saem do conjunto não convexo.
   • Para casos convexos, o fecho é descrito via funções de suporte, levando a um problema de separação com restrições SDP.

4. Elevação e Preservação de Esparsidade:
   As desigualdades válidas derivadas no espaço de imagem 2D são elevadas de volta para o espaço original $(X, x)$ usando a inversa do mapa afim. Crucialmente, como a projeção é baseada em apenas duas desigualdades base, as desigualdades elevadas resultantes herdam a esparsidade (suporte) dessas desigualdades base. Isso evita os problemas de densidade associados às relaxações SDP completas.

5. Desigualdades de Intervalo Misto-Conjunto Secante:
   Estendendo o conceito de MIR, os autores introduzem "desigualdades de intervalo misto-conjunto secantes". Estas envolvem a extração de termos "mistos" (combinações lineares fracionárias ou variáveis contínuas) das desigualdades base para formar um par central que satisfaz as condições parabólicas não convexas. Isso permite que o método lide com estruturas mais complexas, de forma semelhante a como o MIR lida com termos fracionários em MILP.

Contribuições Principais

• Fechos Convexos em Forma Fechada: O artigo fornece uma caracterização completa em forma fechada para a interseção de um cone simplicial e um intervalo conjunto não convexo de duas funções quadráticas. Isso inclui descrições geométricas explícitas para várias configurações (ex: ápice dentro/fora da bacia parabólica, raios de recessão).
• Novas Famílias de Cortes: Os autores introduzem desigualdades de intervalo conjunto e desigualdades de intervalo misto-conjunto secantes. Estas são válidas para a formulação QCQP estendida e são derivadas via cortes de interseção no espaço projetado 2D.
• Preservação de Esparsidade: Ao contrário dos cortes baseados em SDP padrão, as desigualdades propostas são esparsas. O suporte de cada desigualdade elevada é estritamente controlado pelo suporte das duas desigualdades base utilizadas para gerá-la.
• Representação SDP para Casos Convexos: Para intervalos conjuntos convexos, os autores fornecem uma representação semidefinida que oferece uma rota esparsa para linearizar a relaxação SDP de Shor.
• Classificação Algorítmica: Um algoritmo é apresentado para classificar o intervalo conjunto como convexo ou não convexo e para determinar sua forma geométrica específica (ex: fronteira parabólica, região sólida ou plano pontuado).

Resultados

O artigo relata experimentos geométricos preliminares comparando a força das desigualdades de intervalo conjunto propostas contra a relaxação RLT de primeiro nível padrão.

• Métrica: A força é medida pela razão entre a área da interseção entre a relaxação RLT projetada e o fecho do intervalo conjunto versus a área da relaxação RLT projetada sozinha. Uma razão menor indica um corte mais forte (maior redução de área).
• Achados:
  • Em casos "não clipados" (unclipped), onde o intervalo conjunto está inteiramente contido no cone, os cortes não fornecem redução adicional (razão = 1).
  • Em casos não triviais de não convexidade (ex: "Chord-Truncated Bowl" e "Ray-Truncated Bowl"), o fecho do intervalo conjunto reduz significativamente a área projetada. A média geométrica deslocada da razão de área variou aproximadamente de 0,108 a 0,490 em diferentes dimensões e configurações.
  • Os casos de intervalo conjunto convexo (Caso 7) também demonstraram redução substancial de área (razões entre 0,219 e 0,403).
  • Os resultados sugerem que a abordagem proposta pode aumentar substancialmente o aperto da relaxação projetada construída via RLT.

Significância e Alegações

Os autores alegam que este trabalho preenche a lacuna entre a força geométrica dos cortes de interseção e a necessidade computacional de esparsidade em solvers de MINLP.

• Separação de Geometria e Dimensão: A principal significância é o desacoplamento do passo geométrico difícil (lidar com a não convexidade) da dimensão ambiente. A geometria complexa é resolvida em um espaço de baixa dimensão (2D) onde existem soluções em forma fechada, enquanto o corte final permanece esparso no espaço original de alta dimensão.
• Exploração da Não Convexidade: O framework expõe e explora explicitamente intervalos conjuntos não convexos, que são inacessíveis a abordagens que dependem apenas de "convexidade oculta" (como o S-lemma) ou relaxações convexas padrão.
• Generalização do MIR: A abordagem generaliza o paradigma bem-sucedido de projetar-então-elevar do MIR para o domínio não linear do QCQP, oferecendo um mecanismo para gerar cortes fortes sem exigir restrições de matriz densas.
• Direções Futuras: Os autores observam modestamente que um estudo sistemático dentro de um solver MINLP completo está além do escopo atual. Eles identificam a automação da seleção de pares de desigualdades base eficazes como uma direção primária para pesquisas futuras, sugerindo que heurísticas similares às usadas para separação de MIR poderiam ser adaptadas para "alinhar" coeficientes quadráticos a fim de induzir a necessária geometria não convexa.