An inexact infeasible arc-search interior-point method for linear optimization problems

Resumo Técnico: Um Método de Ponto Interior de Busca de Arco Inexato e Inviável para Problemas de Otimização Linear

Enunciado do Problema
O artigo aborda a solução de Problemas de Otimização Linear (LOPs) utilizando Métodos de Ponto Interior (IPMs). Especificamente, foca em IPMs de busca de arco inexatos e inviáveis (II-IPMs), que são variantes projetadas para resolver LOPs partindo de um ponto inicial inviável e resolvendo os sistemas de Newton de forma inexata (por exemplo, via solvers iterativos como o Gradiente Conjugado). Embora os solvers inexatos reduzam o custo computacional por iteração para problemas de grande escala, os métodos existentes de busca de linha inviáveis inexatos sofrem de uma desvantagem significativa: o acúmulo de erros de linearização (da aproximação do caminho central) e erros de inexatidão (do solver) ao longo de uma direção de busca reta. Esse acúmulo força o algoritmo a tomar tamanhos de passo muito pequenos, resultando em um limite de complexidade de iteração de pior caso relativamente frouxo de $O(n^2 L)$, onde $n$ é o número de variáveis e $L$ é o comprimento binário dos dados de entrada.

Metodologia
Os autores propõem um novo método denominado II-arc (Método de Ponto Interior de Busca de Arco Inexato e Inviável). A inovação central reside na substituição da busca padrão por linha reta por uma estratégia de busca de arco elíptico.

1. Estrutura de Busca de Arco: Em vez de se mover ao longo de uma linha reta, o método aproxima o caminho central usando um arco elíptico definido por uma expansão de Taylor de segunda ordem. O próximo iterado $(x_{k+1}, y_{k+1}, s_{k+1})$ é computado como:
   $$x(\alpha) = x_k - \dot{x} \sin(\alpha) + \ddot{x}(1 - \cos(\alpha))$$
   (e analogamente para $y$ e $s$), onde $\dot{x}, \ddot{x}$ são as primeira e segunda derivadas do caminho central.
2. Resolução Inexata: O método resolve os sistemas de Newton para a primeira derivada ($\dot{x}, \dot{y}, \dot{s}$) e a segunda derivada ($\ddot{x}, \ddot{y}, \ddot{s}$) de forma inexata. Os autores utilizam a formulação do Sistema de Equações Normais Modificado (MNES) para análise teórica para relaxar os requisitos de resíduo, embora os experimentos numéricos utilizem o Sistema de Equações Normais (NES) padrão com um precondicionador de Jacobi devido à instabilidade numérica observada nas implementações de MNES para problemas de grande escala.
3. Seleção do Tamanho do Passo: O tamanho do passo $\alpha$ é escolhido para satisfazer condições específicas de vizinhança (garantindo que o iterado permaneça dentro de uma região específica do caminho central) e uma condição do tipo Armijo para garantir uma redução suficiente no gap de dualidade.
4. Análise Teórica: Os autores provam que a trajetória curva do arco de busca suprime o erro de linearização de forma mais eficaz do que uma linha reta. Isso permite que o tamanho do passo permaneça maior mesmo quando os sistemas de Newton são resolvidos com inexatidão significativa.

Principais Contribuições

• Primeiro IPM de Busca de Arco Inexato: Tanto quanto os autores sabem, este é o primeiro artigo que discute um IPM inexato dentro da estrutura de busca de arco.
• Limite de Complexidade Melhorado: O artigo estabelece um limite de complexidade de iteração polinomial de $O(n^{1.5} L)$ para o método II-arc proposto. Isso representa uma melhoria teórica sobre o melhor limite conhecido para os métodos existentes de busca de linha inviáveis inexatos ($O(n^2 L)$) por um fator de $n^{0.5}$.
• Mitigação do Acúmulo de Erro: Os autores demonstram que a estratégia de busca de arco mitiga o acúmulo de erros de linearização e de inexatidão, que é o principal gargalo nos métodos de linha inviáveis inexatos existentes.

Resultados Numéricos
Os autores conduziram experimentos numéricos em problemas de grande escala da coleção de benchmarks NETLIB (incluindo DFL001, QAP15, STOCFOR3 e problemas Kennington) usando uma implementação em Python com Gradiente Conjugado Pré-condicionado (CG) como o solver linear.

• Comparação: O método II-arc proposto (especificamente a variante usando o ponto inicial heurístico de Yang, "II-arc-Yang") foi comparado com um método existente de busca de linha inviável inexata ("II-line-Yang").
• Desempenho:
  • Iterações: O II-arc-Yang consistentemente exigiu menos iterações do que o II-line-Yang. Para quase 25% dos problemas de teste, o método de busca de linha exigiu o dobro ou mais de iterações do que o método de busca de arco.
  • Tempo de Computação: O II-arc-Yang reduziu o tempo total de computação para 75% dos problemas. A redução nas iterações compensou o custo adicional de resolver o sistema da segunda derivada.
  • Robustez: O método resolveu com sucesso 17 de 18 problemas de teste, demonstrando estabilidade numérica.
• Pontos Iniciais: O estudo também comparou um ponto inicial constante contra o ponto inicial heurístico de Yang, encontrando que a abordagem heurística (II-arc-Yang) geralmente produziu melhor desempenho em termos de iterações e tempo.

Significância e Alegações
O artigo afirma que o método II-arc proposto oferece um limite de iteração de pior caso comprovadamente mais apertado do que os métodos existentes de busca de linha inviáveis inexatos. A significância deste trabalho reside em unir os benefícios teóricos da busca de arco (melhor aproximação do caminho central) e a necessidade prática de solvers inexatos para problemas de grande escala.

Os autores observam modestamente que, embora a complexidade teórica tenha sido melhorada, o objetivo principal foi propor a estrutura e discutir sua convergência. Eles reconhecem que o desempenho numérico poderia ser ainda mais aprimorado por:

• Implementar o método em linguagens mais rápidas (ex: C++, Julia).
• Investigar solvers de sistemas lineares inexatos e precondicionadores mais avançados.
• Explorar combinações com a estratégia de reinício de Nesterov ou IPMs viáveis.

O artigo conclui que a aproximação de arco elíptico permite tamanhos de passo maiores na presença de inexatidão, levando tanto a uma redução teórica na complexidade de iteração quanto a melhorias práticas na resolução de problemas de otimização linear de grande escala.