On Approximate Computation of Critical Points

Resumo Técnico: Sobre a Computação Aproximada de Pontos Críticos

Enunciado do Problema
O artigo aborda a complexidade computacional de encontrar pontos críticos (pontos estacionários onde o gradiente se anula) para funções não convexas, focando especificamente na tratabilidade da computação aproximada. Embora seja bem estabelecido que encontrar pontos críticos exatos para polinômios cúbicos é NP-difícil, uma crença prevalecente na comunidade de otimização sugere que encontrar pontos críticos aproximados — pontos onde a norma do gradiente é pequena ($\|\nabla f(x)\| \le \epsilon$) ou pontos próximos de um ponto crítico verdadeiro ($\|x - x^*\| \le \epsilon$) — deve ser computacionalmente tratável. Os autores desafiam essa intuição, investigando se mesmo aproximações grosseiras de pontos críticos podem ser computadas em tempo polinomial para classes simples de funções não convexas, como polinômios de baixo grau.

Metodologia
Os autores empregam o modelo de computação de Turing padrão, onde a entrada consiste nos coeficientes de uma classe de funções paramétricas (principalmente polinômios de grau fixo). A metodologia central envolve reduções de tempo polinomial do problema de Clique (um problema conhecido como NP-completo) para o problema de encontrar pontos críticos aproximados.

Ferramentas técnicas principais incluem:

1. Construção Polinomial: Os autores constroem polinômios cúbicos e quárticos específicos (e produtos de polinômios com exponenciais) cujos pontos críticos correspondem a cliques em um determinado grafo. Uma construção central é um polinômio quártico $g_{G,C,k}(x)$ projetado de tal forma que suas raízes correspondam exatamente a vetores indicadores de $k$-cliques em um grafo $G$.
2. Dificuldade de Aproximação: Para provar a dificuldade da aproximação, os autores devem demonstrar que, se um algoritmo retorna um ponto que é "próximo" de ser um ponto crítico (em termos de norma do gradiente ou distância euclidiana), ele efetivamente resolve o problema de decisão subjacente que é NP-difícil.
3. Limites Analíticos: As provas dependem fortemente do estabelecimento do comportamento dos polinômios construídos. Isso inclui:
   • Estabelecer que os polinômios são coercivos e atingem mínimos.
   • Usar as Condições Necessárias de Primeira e Segunda Ordem (FONC/SONC) para limitar a localização dos minimizadores.
   • Aplicar argumentos de continuidade de Lipschitz para relacionar o valor do polinômio em um ponto próximo a um ponto crítico ao valor no ponto crítico verdadeiro.
   • Utilizar limites sobre as raízes de polinômios univariados (limite de Fujiwara) para restringir a magnitude das variáveis.

Principais Contribuições e Resultados

O artigo estabelece que computar pontos críticos aproximados é intratável (a menos que P=NP) sob diversas definições distintas de "aproximação" e sob várias suposições estruturais:

1. Pontos Críticos $\epsilon$-Aproximados (Norma do Gradiente):

   • Teorema 3: Os autores provam que, a menos que P=NP, nenhum algoritmo de tempo polinomial pode computar um ponto crítico $2^n$-aproximado (onde $\|\nabla p(x)\| \le 2^n$) para um polinômio cúbico em $n$ variáveis. Isso se mantém mesmo se o algoritmo for permitido retornar um ponto arbitrário quando nenhum ponto crítico existe.
   • Corolário 8: Este resultado se estende a algoritmos de tempo pseudo-polinomial para encontrar pontos críticos $n^d$-aproximados.
   • Implicação para Pontos Críticos Únicos: A dificuldade persiste mesmo se o polinômio tiver a promessa de possuir um ponto crítico único. Encontrar um ponto crítico $2^n$-aproximado neste cenário refutaria a conjectura do Clique Plantado e implicaria NP=RP.

2. Suposições Estruturais (Limitação Inferior e Unicidade):

   • Proposição 9: Decidir se a exponencial de um polinômio cúbico (que é sempre limitado inferiormente) possui um ponto crítico é NP-difícil.
   • Proposição 10: Mesmo para funções limitadas inferiormente garantidas de possuir um ponto crítico e sem pontos críticos espúrios (ou seja, cada ponto crítico é um mínimo global), encontrar um ponto crítico é difícil. Isso implica que a ausência de mínimos locais espúrios não garante a tratabilidade.
   • Teorema 11: Para polinômios quárticos limitados inferiormente, encontrar um ponto crítico $2^n$-aproximado dentro de uma bola de raio $2^n$ é NP-difícil, mesmo se o algoritmo for permitido comportar-se arbitrariamente quando não existe um ponto crítico no hipercubo unitário.

3. Pontos Críticos $\epsilon$-Próximos (Distância à Solução):

   • Definição: Um ponto crítico $\epsilon$-próximo é um ponto dentro da distância $\epsilon$ de um ponto crítico verdadeiro.
   • Teorema 13: A menos que P=NP, nenhum algoritmo de tempo polinomial pode computar um ponto crítico $\frac{1}{12000 n^{3.5}}$-próximo para um polinômio cúbico.
   • Teorema 15: Este resultado de dificuldade se estende a funções limitadas inferiormente (produtos de polinômios quárticos e exponenciais), mostrando que encontrar um ponto crítico $\frac{1}{1000 n^7}$-próximo também é intratável.

Significância e Alegações
A principal significância do artigo reside em derrubar a crença comum de que a computação de pontos críticos aproximados é uma tarefa tratável em otimização não convexa. Os autores argumentam que a dificuldade da otimização não convexa não decorre apenas da presença de mínimos locais espúrios ou pontos de sela, mas é intrínseca à tarefa de localizar qualquer ponto estacionário, mesmo que aproximadamente.

• Contraste com Modelos de Oráculo: Os autores distinguem seus resultados de trabalhos anteriores em modelos baseados em oráculo (ex: Carmon et al., Hollender e Zampetakis), que fornecem limites inferiores na complexidade de consulta. Este artigo opera no modelo de Turing, descartando qualquer algoritmo de tempo polinomial, incluindo aqueles baseados em relaxações convexas ou outras abordagens não baseadas em oráculo.
• Implicações para Algoritmos: Os resultados sugerem que algoritmos padrão como o Descida de Gradiente ou o Método de Newton (e suas extensões de ordem superior) não podem garantir encontrar mesmo aproximações grosseiras de pontos críticos em tempo polinomial para polinômios cúbicos gerais. Especificamente, o artigo nota que a extensão mais natural do método de Newton (resolver para pontos críticos de expansões de Taylor de grau 3) carece de complexidade por iteração tratável, a menos que P=NP.
• Direções Futuras: Os autores concluem modestamente que seus resultados motivam a busca por classes específicas de funções paramétricas e suposições estruturais (verificáveis em tempo polinomial) sob as quais a computação de pontos críticos aproximados se torna tratável. Eles observam que, embora a convexidade permita a tratabilidade, verificar a convexidade para polinômios de grau 4 ou superior é, por si só, difícil, deixando uma lacuna no entendimento de quais propriedades estruturais permitem a aproximação eficiente.