A structured version of derivative-free random pattern search optimization algorithms is introduced, which is able to exploit coordinate partially separable structure (typically associated with sparsity) often present in unconstrained and bound-constrained optimization problems. This technique improves performance by orders of magnitude and makes it possible to solve large problems that otherwise are totally intractable by other derivative-free methods. A library of interpolation-based modelling tools is also described, which can be associated with the structured or unstructured versions of the initial pattern search algorithm. The use of the library further enhances performance, especially when associated with structure. The significant gains in performance associated with these two techniques are illustrated using a new freely-available release of the Brute Force Optimizer (BFO) package firstly introduced in [Porcelli and Toint 2017], which incorporates them. An interesting conclusion of the numerical results presented is that providing global structural information on a problem can result in significantly less evaluations of the objective function than attempting to building local Taylor-like models.

Exploiting Problem Structure in Derivative Free Optimization / Porcelli M.; Toint P. L.. - In: ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE. - ISSN 0098-3500. - ELETTRONICO. - 48:(2022), pp. 6.1-6.25. [10.1145/3474054]

Exploiting Problem Structure in Derivative Free Optimization

Porcelli M.;
2022

Abstract

A structured version of derivative-free random pattern search optimization algorithms is introduced, which is able to exploit coordinate partially separable structure (typically associated with sparsity) often present in unconstrained and bound-constrained optimization problems. This technique improves performance by orders of magnitude and makes it possible to solve large problems that otherwise are totally intractable by other derivative-free methods. A library of interpolation-based modelling tools is also described, which can be associated with the structured or unstructured versions of the initial pattern search algorithm. The use of the library further enhances performance, especially when associated with structure. The significant gains in performance associated with these two techniques are illustrated using a new freely-available release of the Brute Force Optimizer (BFO) package firstly introduced in [Porcelli and Toint 2017], which incorporates them. An interesting conclusion of the numerical results presented is that providing global structural information on a problem can result in significantly less evaluations of the objective function than attempting to building local Taylor-like models.
2022
48
1
25
Porcelli M.; Toint P. L.
File in questo prodotto:
File Dimensione Formato  
pt3_accepted_TOMS_2Aug21_IRIS.pdf

Accesso chiuso

Licenza: Tutti i diritti riservati
Dimensione 1.78 MB
Formato Adobe PDF
1.78 MB Adobe PDF   Richiedi una copia
3474054.pdf

Accesso chiuso

Licenza: Tutti i diritti riservati
Dimensione 633.06 kB
Formato Adobe PDF
633.06 kB Adobe PDF   Richiedi una copia

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/1351284
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact