Parabolic second-order tangent sets of semialgebraic sets and applications to polynomial optimization

Resumo Técnico: Conjuntos Tangentes Parabólicos de Segunda Ordem de Conjuntos Semialgebraicos e Aplicações à Otimização Polinomial

Enunciado do Problemas
Os cones tangentes de primeira ordem, embora fundamentais na análise variacional e na otimização com restrições, falham em capturar a curvatura, a ativação de segunda ordem das restrições ou comportamentos de viabilidade por ramos. Essas características são críticas em problemas de otimização polinomial degenerados, onde modelos padrão de primeira ordem são insuficientes. O artigo aborda a necessidade de um arcabouço rigoroso e algebricamente verificável para a análise local de segunda ordem de conjuntos semialgebraicos. Especificamente, investiga o conjunto tangente parabólico de segunda ordem, que caracteriza as correções de segunda ordem $w$ em expansões viáveis da forma $x(t) = \bar{x} + tu + \frac{1}{2}t^2w + o(t^2)$, e busca determinar quando este objeto geométrico coincide com um modelo algébrico derivado dos gradientes e Hessianos das restrições que definem o conjunto.

Metodologia
O artigo opera na categoria de conjuntos semialgebraicos fechados básicos $S = \{x \in \mathbb{R}^n : g_i(x) = 0, h_j(x) \leq 0\}$. A metodologia procede através dos seguintes passos:

1. Definições: Os autores definem três variantes do conjunto tangente de segunda ordem em um ponto $\bar{x}$ na direção $u$:

   • O conjunto tangente parabólico externo ($T^{2,out}_S$), definido via limites sequenciais.
   • O conjunto tangente parabólico interno ($T^{2,in}_S$), definido via quantificação universal sobre sequências.
   • O conjunto tangente gerado por arcos ($T^{2,arc}_S$), definido via a existência de arcos semialgebraicos.
   • O conjunto linearizado algébrico de segunda ordem ($L^2_S$), definido pelas igualdades e desigualdades nas restrições sobre $w$ derivadas das expansões de Taylor das restrições ativas.

2. Condições de Regularidade: O núcleo da metodologia introduz a regularidade parabólica algébrica. Esta condição exige duas propriedades em $(\bar{x}, u)$:

   • Estabilidade de Rank Direcional: O rank da matriz do gradiente da família ativa de segunda ordem permanece constante ao longo de arcos viáveis aproximando-se de $\bar{x}$ na direção $u$.
   • Realizabilidade de Arco Parabólico: Toda correção de segunda ordem formalmente admissível $w \in L^2_S(\bar{x}; u)$ é realizada por um arco semialgebraico real.

3. Estratificação: Para conjuntos singulares, o artigo utiliza estratificações semialgebraicas $C^2$ finitas. Ele decompõe o conjunto tangente de um conjunto singular na união dos conjuntos tangentes dos fechamentos dos estratos selecionados (ramos) que se aproximam do ponto com a dada direção.

Principais Contribuições e Resultados

• Caracterização Algébrica: O artigo estabelece que, sob a condição de regularidade parabólica algébrica, os conjuntos tangentes parabólicos externo, interno e gerado por arcos coincidem com o conjunto linearizado algébrico de segunda ordem:
  $$T^{2,out}_S(\bar{x}; u) = T^{2,in}_S(\bar{x}; u) = T^{2,arc}_S(\bar{x}; u) = L^2_S(\bar{x}; u).$$
  Este resultado transforma um objeto geométrico abstrato em um sistema finito de equações/desigualdades lineares e quadráticas envolvendo gradientes e Hessianos.

• Fórmulas Explícitas: Os autores derivam fórmulas exatas para classes específicas de conjuntos:

  • Hipersuperfícies Suaves: O conjunto tangente é definido por uma única equação linear envolvendo o Hessiano do polinômio definidor.
  • Interseções Completas Regulares: O conjunto tangente é o núcleo de um mapa envolvendo o Jacobiano e a segunda derivada do mapeamento.
  • Sistemas de Desigualdade Suaves: Sob independência linear de gradientes, o conjunto tangente é o conjunto poliédrico definido pelas restrições ativas.
  • Conjuntos Estratificados: Uma fórmula é fornecida onde o conjunto tangente de um conjunto singular é a união dos conjuntos tangentes dos fechamentos dos estratos relevantes.

• Aplicações em Otimização:

  • Condições Necessárias de Segunda Ordem: Se $\bar{x}$ é um minimizador local, então para toda direção crítica $u$ e todo $w \in T^2_S(\bar{x}; u)$, a forma quadrática $Q_f(\bar{x}; u, w) = \nabla f(\bar{x})w + u^T \nabla^2 f(\bar{x})u$ deve ser não negativa. Sob regularidade parabólica algébrica, este teste reduz-se a verificar $w \in L^2_S(\bar{x}; u)$.
  • Crescimento Quadrático: O artigo fornece condições suficientes para crescimento quadrático (isto é, $f(x) \geq f(\bar{x}) + c\|x-\bar{x}\|^2$). Se $Q_f$ é estritamente positiva no conjunto linearizado algébrico para todas as direções críticas unitárias, o crescimento quadrático ocorre.
  • Multiplicadores de Lagrange: Os resultados produzem critérios envolvendo multiplicadores de Lagrange onde o termo de segunda ordem da função objetivo é comparado contra o Hessiano do Lagrangiano, ajustado pela curvatura das restrições de desigualdade ativas.

Significância e Alegações
O artigo alega tornar as construções de segunda ordem algebricamente verificáveis para conjuntos viáveis semialgebraicos. Sua significância reside em unir a análise variacional (que frequentemente lida com objetos limitantes) e a geometria algébrica real (que oferece estruturas finitas e computáveis).

Os autores enfatizam que sua abordagem detecta características que os cones tangentes de primeira ordem perdem:

• Curvatura: Distinguir entre ramos viáveis planos e curvos.
• Planicidade: Identificar casos em que as restrições são "planas" (ex: $y \geq x^4$) de modo que as condições de segunda ordem são necessárias para a minimalidade local, mas insuficientes para o crescimento quadrático.
• Dependência de Ramo: Lidar com conjuntos singulares (como cúspides ou tacnodes) onde diferentes ramos podem ter comportamentos de segunda ordem distintos, exigindo análise por ramos em vez de uma única equação linearizada.
• Falha de Escalonamento Parabólico: Destacar casos (como a cúspide $y^2 = x^3$) onde o escalonamento parabólico padrão $t^2$ é insuficiente para capturar a primeira correção não trivial, necessitando de análise de ordem superior ou de ordem fracionária.

O trabalho é apresentado como um complemento local aos métodos algébicos globais (como a hierarquia de momentos-SOS de Lasserre ou abordagens de ideais de gradiente), fornecendo testes de otimalidade local precisos que são computáveis via álgebra polinomial. O artigo conclui modestamente, observando que, embora resolva o caso de segunda ordem sob regularidade, questões relativas a análogos de ordem superior ou de ordem fracionária (ex: expoentes de Puiseux) para ramos singulares (ex: cúspides) e a conexão com certificados globais permanecem abertas.