Immunity to Increasing Condition Numbers of Linear Superiorization versus Linear Programming

Resumo Técnico: Imunidade ao Aumento dos Números de Condição de Programação Linear Superiorização Versus Programação Linear

Definição do Problema
O artigo aborda o desempenho comparativo de algoritmos de Programação Linear (LP) e da metodologia de Linear Superiorização (LinSup) quando aplicados a problemas de programação linear caracterizados por números de condição crescentes. Enquanto a LP clássica visa encontrar um ponto ótimo (minimizando a função objetivo sujeita a restrições), a LinSup visa encontrar um ponto viável com uma função objetivo "superior" (reduzida, embora não necessariamente mínima). O problema central investigado é a sensibilidade de ambas as abordagens à mal-postura (ill-posedness), especificamente como o aumento dos números de condição da matriz de restrição afeta o tempo de execução, a obtenção de viabilidade e a redução da função objetivo desses algoritmos.

Metodologia
Os autores conduziram um estudo experimental controlado comparando a LinSup contra solvers de LP estabelecidos.

• Geração de Problemas: Os pesquisadores construíram problemas de programação linear da forma $\min \langle c, x \rangle$ sujeito a $Ax \le b$ e $\ell \le x \le u$. Para garantir a similaridade estrutural entre diferentes números de condição, eles utilizaram Decomposição de Valor Singular (SVD). Eles geraram matrizes semi-ortogonais aleatórias $U$ e $V$ e construíram matrizes diagonais $\Sigma_\kappa$ com valores singulares distribuídos para alcançar números de condição $\kappa$ específicos (variando de bem condicionados a altamente mal condicionados). Os tamanhos das matrizes variaram de $80 \times 100$ a $4000 \times 5000$.
• Algoritmos Testados:
  • LinSup: Implementada usando o método de projeção Agmon-Motzkin-Schönberg (AMS) como o algoritmo base de busca de viabilidade. Perturbações foram introduzidas usando o gradiente negativo normalizado da função objetivo. O algoritmo empregou perturbações limitadas e projeções cíclicas com cronogramas de tamanho de passo específicos e mecanismos de reinicialização.
  • Solvers de LP: O estudo comparou a LinSup contra scipy.simplex, scipy.revised simplex, scipy.interior-point e gurobi.primal simplex.
• Protocolo Experimental: Para garantir uma comparação justa, os autores impuseram um critério de parada unificado baseado em um limiar de inviabilidade fixo ($\varepsilon = 10^{-8}$).
  • A LinSup foi executada até atingir este limiar.
  • Os solvers de LP foram executados sob o mesmo limiar. Se um solver de LP falhasse em atingir o limiar dentro do tempo $T_{sup}$ (o tempo que a LinSup levou para terminar), ele era interrompido em $T_{sup}$, e seu iterado atual era registrado.
  • Métricas registradas incluíram tempo de execução, valores da função objetivo e violações máximas de restrição (inviabilidade) no término e ao longo das iterações.

Principais Contribuições e Resultados
O estudo fornece evidências empíricas sobre a robustez da LinSup em comparação com solvers de LP clássicos sob variações de dificuldade do problema:

1. Desempenho em Dimensões Crescentes ( $\kappa$ Fixo):

   • Para dimensões pequenas, solvers baseados em simplex foram mais rápidos.
   • À medida que as dimensões do problema aumentavam (até $4000 \times 5000$), o tempo de execução das implementações de simplex (incluindo Gurobi) aumentou significativamente. Em dimensões elevadas, a LinSup terminou mais rápido que os solvers de simplex.
   • Notavelmente, nas maiores dimensões testadas, a LinSup atingiu o limiar de viabilidade antes mesmo dos algoritmos de simplex atingirem a viabilidade.

2. Imunidade ao Aumento dos Números de Condição (Dimensões Fixas):

   • Métodos Simplex: À medida que o número de condição aumentava, as implementações de simplex da scipy exibiram uma degradação severa. Elas frequentemente terminavam precocemente com valores de objetivo subótimos, efetivamente "rendendo-se" devido à dificuldade do problema.
   • Método de Pontos Interiores: Embora este método parecesse encontrar baixos valores de objetivo rapidamente, ele teve dificuldades em atingir o nível de viabilidade exigido para números de condição elevados, resultando em altos valores de inviabilidade (até $10^1$).
   • LinSup: O método de superiorização demonstrou uma estabilidade notável. Seu tempo de execução permaneceu relativamente consistente, independentemente do número de condição, e ela consistentemente alcançou o limiar de viabilidade alvo ($\varepsilon = 10^{-8}$) em todos os números de condição testados.
   • Função Objetivo: A LinSup consistentemente produziu valores de função objetivo melhores (menores) no ponto de término em comparação com os métodos simplex em cenários mal condicionados.

3. Análise de Proximidade-Alvo:

   • Gráficos de inviabilidade versus valor da função objetivo (curvas de proximidade-alvo) confirmaram que a LinSup manteve um caminho constante em direção à viabilidade enquanto reduzia o objetivo. Em contraste, o método de pontos interiores mostrou um descompasso entre encontrar um baixo valor de objetivo e satisfazer as restrições em configurações mal condicionadas.

Significância e Alegações
O artigo afirma que a Programação Linear Superiorização oferece uma vantagem distinta sobre os solvers de LP clássicos ao lidar com sistemas lineares mal condicionados, particularmente em cenários de grande escala.

• Robustez: Os autores concluem que a LinSup é menos afetada por altos números de condição do que os solvers de LP testados. Eles atribuem isso à natureza do algoritmo: a LinSup realiza projeções individuais em hiperplanos em vez de resolver o sistema completo simultaneamente, e a "resiliência de perturbação limitada" do algoritmo base pode ajudar a absorver erros computacionais que seriam amplificados pela má condição.
• Utilidade Prática: O estudo sugere que, para aplicações onde encontrar um ponto viável com um valor de objetivo reduzido é suficiente (uma abordagem de "satisfação" em vez de otimalidade estrita), a LinSup é uma ferramenta mais confiável e eficiente para problemas mal postos.
• Escopo Modesto: Os autores declaram explicitamente que seus resultados baseiam-se em configurações experimentais e tamanhos de problemas específicos. Eles expressam confiança de que as tendências observadas se manterão para instâncias maiores, mas não afirmam que a LinSup substitui os solvers de LP para todas as tarefas de otimização. Eles observam que a LinSup não é um solver de LP e não visa a otimalidade restrita, mas sim um ponto viável "superior".
• Trabalho Futuro: O artigo sugere que a robustez observada da LinSup em configurações lineares justifica investigação em configurações não lineares, particularmente onde os métodos de pontos interiores são conhecidos por ter dificuldades com a má condição (ex: radioterapia modulada por intensidade).