Benchmarking Optimization Algorithms with Quality Profiles and Test Set Profiles

Resumo Técnico: Avaliação de Algoritmos de Otimização com Perfis de Qualidade e Perfis de Conjunto de Teste

Definição do Problema
O benchmarking de algoritmos de otimização apresenta um desafio significativo, particularmente ao comparar solvers que podem convergir para diferentes pontos de solução em um conjunto de teste. Ferramentas de benchmarking existentes, como perfis de desempenho (Dolan e Moré) e perfis de dados (Moré e Wild), focam primordialmente na eficiência (esforço computacional) e na confiabilidade (taxas de sucesso). Embora os perfis de desempenho sejam o padrão para medir o esforço de convergência (ex: tempo de CPU, iterações), eles frequentemente excluem problemas onde os solvers convergem para soluções distintas para garantir uma comparação justa do fardo computacional. Consequentemente, há uma carência de ferramentas especificamente projetadas para avaliar e comparar a qualidade (precisão) dos valores da função objetivo finais obtidos por diferentes solvers, especialmente em cenários onde métodos exatos e heurísticas são comparados, ou onde os solvers convergem para mínimos locais distintos. Além disso, a literatura tem dedicado pouca atenção à avaliação quantitativa da adequação e consistência do próprio conjunto de teste em relação aos solvers que estão sendo submetidos ao benchmarking.

Metodologia
Os autores propõem duas ferramentas gráficas inovadoras: Perfis de Qualidade e Perfis de Conjunto de Teste.

1. Perfis de Qualidade:

   • Definição: Para um conjunto de solvers $S$ e problemas de teste $P$, um perfil de qualidade $Q_s(\tau)$ representa a proporção de problemas onde um solver $s$ alcança uma solução dentro de um limite de precisão específico $\tau$. A precisão é medida em relação a um valor de referência $f_L^{(p)}$ (tipicamente a melhor solução encontrada por qualquer solver no conjunto) e um ponto inicial $x_0^{(p)}$.
   • Inequação Central: O perfil é construído com base na inequação:
     $$f_s^{(p)}(x^*) - f_L^{(p)} \leq \tau [f^{(p)}(x_0^{(p)}) - f_L^{(p)}]$$
     onde $\tau \in [0, 1]$.
   • Fraco vs. Forte: Perfis "fracos" utilizam o ponto inicial $x_0^{(p)}$ na normalização, enquanto perfis "fortes" utilizam a pior solução encontrada pelos solvers.
   • Melhorias de Visualização: Para lidar com a dificuldade de distinguir trilhas densamente agrupadas, os autores introduzem parâmetros de escala $r_1$ e $r_2$. Estes permitem a compressão ou expansão não linear dos eixos das abscissas (precisão) e das ordenadas (porcentagem de problemas), respectivamente. Isso facilita o zoom em intervalos de precisão específicos (ex: alta precisão próximo a $\tau=0$) sem descartar dados.
   • Propriedades: Os perfis são provados serem invariantes sob transformações afins consistentes da função objetivo e são não decrescentes. Diferente dos perfis de desempenho, eles não requerem identificação de parâmetros a priori que possa introduzir viés, embora dependam de um orçamento computacional fixo (critério de parada) por solver.

2. Perfis de Conjunto de Teste:

   • Propósito: Avaliar a robustez das conclusões do benchmarking e a consistência do conjunto de teste $P$.
   • Metodologia: Esta ferramenta aplica uma técnica de bootstrapping. Ela reamostra repetidamente o conjunto de teste $P$ (com reposição) para gerar múltiplos subconjuntos $\hat{P}$. Perfis de qualidade são computados para cada subconjunto.
   • Saída: A variância $\sigma_s^2(\tau)$ dos valores do perfil de qualidade através dos ciclos de bootstrap é plotada contra $\tau$. Uma baixa variância indica que o ranking e o desempenho do solver são robustos a mudanças na composição do conjunto de teste, enquanto uma alta variância sugere que as conclusões do benchmarking são sensíveis aos problemas específicos escolhidos.

Principais Contribuições

• Nova Ferramenta de Benchmarking: A introdução dos Perfis de Qualidade fornece um procedimento determinístico para comparar solvers com base na precisão da solução, em vez do esforço computacional. Isso permite a inclusão de problemas onde os solvers convergem para soluções diferentes, os quais são tipicamente excluídos das comparações de perfis de desempenho.
• Natureza Complementar: Os autores posicionam os Perfis de Qualidade não como um substituto para perfis de desempenho ou de dados, mas como uma ferramenta complementar. Eles preenchem uma lacuna na literatura ao oferecer uma representação gráfica condensada da qualidade da solução, sendo particularmente útil ao comparar métodos exatos com heurísticas.
• Diagnóstico de Conjunto de Teste: A introdução dos Perfis de Conjunto de Teste oferece um método quantitativo post-hoc para avaliar a confiabilidade e o poder discriminativo de um conjunto de teste, abordando uma dimensão do benchmarking frequentemente negligenciada.
• Flexibilidade na Visualização: O uso de parâmetros de escala ($r_1, r_2$) e escalas semilogarítmicas permite uma análise detalhada do desempenho do solver através de diferentes ordens de magnitude de precisão, uma característica que não é facilmente extensível aos perfis de desempenho ou de dados padrão.

Resultos
O artigo apresenta experimentos numéricos extensos para validar as ferramentas:

• Otimização Suave:
  • Em uma comparação de quatro solvers de larga escala sem restrições (L-BFGS, CG+, TRON, CG DESCENT) em 166 problemas CUTEst, os Perfis de Qualidade revelaram que o TRON superou os outros em intervalos de baixa a média precisão, enquanto o CG+ mostrou uma robustez ligeiramente superior (menos falhas). Os parâmetros de escala ($r_1 > 1$) mostraram-se essenciais para distinguir os solvers em regiões de alta precisão, onde as trilhas seriam de outra forma indistinguíveis.
  • Um segundo experimento comparou métodos Newton Truncados com diferentes estratégias de direção de curvatura negativa. Os Perfis de Qualidade destacaram efetivamente que a estratégia TN-NC3 (selecionando o primeiro autovalor negativo) era a mais eficaz, confirmando expectativas teóricas e demonstrando a capacidade da ferramenta de mensurar características algorítmicas específicas.
• Otimização Livre de Derivadas:
  • Os autores aplicaram Perfis de Qualidade a sete solvers livres de derivadas (incluindo NEWUOA, Nelder-Mead e métodos de busca de padrão) em 145 problemas.
  • Os resultados demonstraram a complementaridade com os Perfis de Dados: enquanto os Perfis de Dados mostram o desempenho vs. orçamento computacional para uma precisão fixa, os Perfis de Qualidade mostram o desempenho vs. precisão para orçamentos computacionais fixos.
  • Os experimentos confirmaram que métodos baseados em modelos (NEWUOA) geralmente produzem maior precisão do que métodos de busca de padrão, mesmo com orçamentos modestos, e que os parâmetros de escala são cruciais para visualizar essas diferenças.
• Análise de Conjunto de Teste:
  • Usando dados sintéticos e variando a cardinalidade do conjunto de teste ($|P|$), os Perfis de Conjunto de Teste mostraram que conjuntos de teste menores levam a uma maior variância nos rankings dos solvers, confirmando a sensibilidade do benchmarking à composição do conjunto de teste.

Significância e Alegações
Os autores alegam que os Perfis de Qualidade e os Perfis de Conjunto de Teste aprimoram o processo de benchmarking ao fornecer uma imagem mais completa do comportamento do solver. Especificamente:

• Eles permitem a comparação de algoritmos que convergem para soluções diferentes, um cenário onde os perfis de desempenho tradicionais são frequentemente inadequados ou exigem a exclusão de dados.
• Oferecem uma maneira de avaliar o "outro lado" da robustez do solver: a adequação do próprio conjunto de teste.
• A abordagem é construtiva em vez de axiomática; não pretende resolver todos os paradoxos de ranking (como os discutidos por Liu et al.), mas fornece uma ferramenta prática e baseada em dados para medir uma dimensão específica do desempenho (qualidade da solução).
• As ferramentas são particularmente valiosas em otimização livre de derivadas e black-box, onde orçamentos fixos de avaliações de função são comuns e a qualidade da solução é a métrica de interesse primário.

O artigo conclui que estas ferramentas devem ser vistas como parte de um ecossistema de benchmarking mais amplo, complementando a análise de espaço-instância, o design experimental sólido e as regras de comparação livres de paradoxos, em vez de substituir as metodologias existentes.