Benchmarking Optimization Algorithms with Quality Profiles and Test Set Profiles

Technische Samenvatting: Benchmarking van Optimalisatie-algoritmen met Kwaliteitsprofielen en Testsetprofielen

Probleemstelling
Het benchmarken van optimalisatie-algoritmen vormt een aanzienlijke uitdaging, met name bij het vergelijken van solvers die kunnen convergeren naar verschillende oplossingspunten op een testset. Bestaande benchmarking-tools, zoals prestatieprofielen (Dolan en Moré) en dataprofielen (Moré en Wild), richten zich primair op efficiëntie (computationele inspanning) en betrouwbaarheid (succesratio's). Hoewel prestatieprofielen de standaard zijn voor het meten van convergentie-inspanning (bijv. CPU-tijd, iteraties), sluiten zij vaak problemen uit waarbij solvers naar verschillende oplossingen convergeren om een eerlijke vergelijking van de computationele last te waarborgen. Bijgevolg is er een gebrek aan tools die specifiek zijn ontworpen om de kwaliteit (nauwkeurigheid) van de verkregen uiteindelijke doelfunctiewaarden van verschillende solvers te beoordelen en te vergelijken, vooral in scenario's waar exacte methoden en heuristieken worden vergeleken, of waar solvers naar afzonderlijke lokale minima convergeren. Bovendien heeft de literatuur beperkte aandacht besteed aan het kwantitatief beoordelen van de geschiktheid en consistentie van de testset zelf met betrekking tot de gebenchmarkte solvers.

Methodologie
De auteurs stellen twee nieuwe grafische tools voor: Kwaliteitsprofielen en Testsetprofielen.

1. Kwaliteitsprofielen:

   • Definitie: Voor een verzameling solvers $S$ en testproblemen $P$ vertegenwoordigt een kwaliteitsprofiel $Q_s(\tau)$ het aandeel problemen waarbij een solver $s$ een oplossing bereikt binnen een specifieke nauwkeurigheidsdrempel $\tau$. De nauwkeurigheid wordt gemeten ten opzichte van een referentiewaarde $f_L^{(p)}$ (doorgaans de beste oplossing gevonden door een willekeurige solver in de verzameling) en een startpunt $x_0^{(p)}$.
   • Kernongelijkheid: Het profiel wordt geconstrueerd op basis van de ongelijkheid:
     $$f_s^{(p)}(x^*) - f_L^{(p)} \leq \tau [f^{(p)}(x_0^{(p)}) - f_L^{(p)}]$$
     waarbij $\tau \in [0, 1]$.
   • Zwak vs. Sterk: "Zwakke" profielen gebruiken het startpunt $x_0^{(p)}$ in de normalisatie, terwijl "sterke" profielen de slechtste oplossing gevonden door de solvers gebruiken.
   • Visualisatieverbeteringen: Om de moeilijkheid van het onderscheiden van dicht opeengepakte trajecten aan te pakken, introduceren de auteurs schalingparameters $r_1$ en $r_2$. Deze maken niet-lineaire compressie of expansie van de abscissa (precisie) en ordinate (percentage problemen) assen mogelijk. Dit vergemakkelijkt het inzoomen op specifieke nauwkeurigheidsbereiken (bijv. hoge precisie nabij $\tau=0$) zonder gegevens weg te gooien.
   • Eigenschappen: De profielen zijn bewezen invariant onder consistente affine transformaties van de doelfunctie en zijn niet-dalend. In tegen tegenstelling tot prestatieprofielen vereisen ze geen a priori parameteridentificatie die bias zou kunnen introduceren, hoewel ze vertrouwen op een vastgesteld computationeel budget (stopcriterium) per solver.

2. Testsetprofielen:

   • Doel: Om de robuustheid van de benchmarking-conclusies en de consistentie van de testset $P$ te beoordelen.
   • Methodologie: Deze tool past een bootstrapping-techniek toe. Er worden herhaaldelijk subsets $\hat{P}$ getrokken uit de testset $P$ (met teruglegging) om meerdere subsets te genereren. Voor elke subset worden kwaliteitsprofielen berekend.
   • Output: De variantie $\sigma_s^2(\tau)$ van de kwaliteitsprofielwaarden over de bootstrap-cycli wordt uitgezet tegen $\tau$. Een lage variantie geeft aan dat de rangschikking en prestaties van de solver robuust zijn voor veranderingen in de samenstelling van de testset, terwijl een hoge variantie suggereert dat de benchmarking-conclusies gevoelig zijn voor de specifieke gekozen problemen.

Belangrijkste Bijdragen

• Nieuwe Benchmarking-tool: De introductie van Kwaliteitsprofielen biedt een deterministisch procedure om solvers te vergelijken op basis van oplossingsnauwkeurigheid in plaats van computationele inspanning. Dit maakt de inclusie van problemen mogelijk waarbij solvers naar verschillende oplossingen convergeren, wat bij traditionele prestatieprofielvergelijkingen vaak wordt uitgesloten.
• Complementair Karakter: De auteurs positioneren Kwaliteitsprofielen niet als een vervanging voor prestatie- of dataprofielen, maar als een complementair instrument. Ze vullen een gat in de literatuur door een gecondenseerde grafische weergave van de oplossingskwaliteit te bieden, wat bijzonder nuttig is bij het vergelijken van exacte methoden met heuristieken.
• Testset Diagnostiek: De introductie van Testsetprofielen biedt een kwantitatieve, post-hoc methode om de betrouwbaarheid en het onderscheidend vermogen van een testset te evalueren, waarmee een dimensie van benchmarking wordt geadresseerd die vaak over het hoofd wordt gezien.
• Flexibiliteit in Visualisatie: Het gebruik van schalingparameters ($r_1, r_2$) en semilogaritmische schalen maakt gedetailleerde analyse van solverprestaties over verschillende ordes van grootte in nauwkeurigheid mogelijk, een kenmerk dat niet eenvoudig uitbreidbaar is naar standaard prestatie- of dataprofielen.

Resultaten
Het artikel presenteert uitgebreide numerieke experimenten om de tools te valideren:

• Gladde Optimalisatie:
  • In een vergelijking van vier grootschalige onbeperkte solvers (L-BFGS, CG+, TRON, CG DESCENT) op 166 CUTEst-problemen, toonden Kwaliteitsprofielen aan dat TRON de anderen overtrof in de laag-tot-medium nauwkeurigheidsintervallen, terwijl CG+ een iets betere robuustheid vertoonde (minder fouten). De schalingparameters ($r_1 > 1$) bleken essentieel om solvers te onderscheiden in hoog-nauwkeurige regio's waar de trajecten anders ononderscheidbaar waren.
  • Een tweede experiment vergeleek Truncated Newton-methoden met verschillende strategieën voor negatieve kromming-richtingen. Kwaliteitsprofielen benadrukten effectief dat de TN-NC3-strategie (selectie van de eerste negatieve eigenwaarde) de meest effectieve was, wat de theoretische verwachtingen bevestigde en de capaciteit van de tool demonstreerde om specifieke algoritmische kenmerken te peilen.
• Afgeleide-vrije Optimalisatie:
  • De auteurs pasten Kwaliteitsprofielen toe op zeven afgeleide-vrije solvers (waaronder NEWUOA, Nelder-Mead en pattern search methoden) op 145 problemen.
  • De resultaten toonden de complementariteit met Dataprofielen aan: terwijl Dataprofielen prestaties tonen versus computationeel budget voor een vaste nauwkeurigheid, tonen Kwaliteitsprofielen prestaties versus nauwkeurigheid voor een vastgesteld computationeel budget.
  • De experimenten bevestigden dat model-gebaseerde methoden (NEWUOA) over het algemeen een hogere nauwkeurigheid opleveren dan pattern-search methoden, zelfs met bescheiden budgetten, en dat de schalingparameters cruciaal zijn voor het visualiseren van deze verschillen.
• Testset Analyse:
  • Met behulp van synthetische data en variërende cardinaliteit van de testset ($|P|$), toonden Testsetprofielen aan dat kleinere testsets leiden tot een hogere variantie in de solver-rangschikking, wat de gevoeligheid van benchmarking voor de samenstelling van de testset bevestigt.

Betekenis en Claims
De auteurs beweren dat Kwaliteitsprofielen en Testsetprofielen het benchmarkingproces verbeteren door een completer beeld van solvergedrag te geven. Specifiek:

• Ze maken vergelijking mogelijk tussen algoritmen die naar verschillende oplossingen convergeren, een scenario waarin traditionele prestatieprofielen vaak inadequaat zijn of gegevens vereisen uit te sluiten.
• Ze bieden een manier om de "andere kant" van solver-robuustheid te beoordelen: de geschiktheid van de testset zelf.
• De aanpak is constructief in plaats van axiomatisch; het claimt geen paradoxen in rangschikking op te lossen (zoals besproken door Liu et al.), maar biedt een praktisch, op data gebaseerd instrument om een specifieke dimensie van prestatie (oplossingskwaliteit) te meten.
• De tools zijn bijzonder waardevol in afgeleide-vrije en black-box optimalisatie, waar vaste budgetten van functie-evaluaties gebruikelijk zijn en de kwaliteit van de oplossing de primaire metriek van belang is.

Het artikel concludeert dat deze tools beschouwd moeten worden als onderdeel van een breder benchmarking-ecosysteem, die instance-space analyse, solide experimenteel ontwerp en paradox-vrije vergelijkingregels aanvullen, in plaats van bestaande methodologieën te vervangen.