TY - JOUR
T1 - Exploiting problem structure in Derivative-Free Optimization
AU - Porcelli, Margherita
AU - Toint, Philippe
N1 - Funding Information:
Both authors are indebted to the University of Florence for its support while the present research was being conducted. The first author is member of the Gruppo Nazionale per il Calcolo Scientifico (GNCS) of the Istituto Nazionale di Alta Matematica (INdAM) and this work was partially supported by INdAM-GNCS under Progetti di Ricerca 2019 and 2020. Authors’ addresses: M. Porcelli, Università di Bologna, Dipartimento di Matematica and AM2, Piazza di Porta S. Donato, 5, Bologna 40126, Italy, and ISTI–CNR, Via Moruzzi 1, Pisa, Italy; email: margherita.porcelli@unibo.it; Ph. L. Toint, Namur Center for Complex Systems (NAXYS), University of Namur, 61, rue de Bruxelles, Namur B-5000, Belgium; email: philippe.toint@unamur.be. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2022 Association for Computing Machinery. 0098-3500/2022/02-ART6 $15.00 https://doi.org/10.1145/3474054
Publisher Copyright:
© 2022 Association for Computing Machinery.
PY - 2022/2/26
Y1 - 2022/2/26
N2 - A structured version of derivative-free random pattern search optimization algorithms is introduced which is able to exploit coordinate partiallyseparable structure (typically associated with sparsity) often present inunconstrained and bound-constrained optimization problems. This techniqueimproves performance by orders of magnitude and makes it possible to solvelarge problems that otherwise are totally intractable by other derivative-freemethods. A library of interpolation-based modelling tools is also described,which can be associated to the structured or unstructured versions of theinitial BFO pattern search algorithm. The use of the library further enhancesperformance, especially when associated with structure. The significant gainsin performance associated with these two techniques are illustrated using anew freely-available release of BFO which incorporates them. A interestingconclusion of the results presented is that providing global structuralinformation on a problem can result in significantly less evaluations of theobjective function than attempting to building local Taylor-like models.
AB - A structured version of derivative-free random pattern search optimization algorithms is introduced which is able to exploit coordinate partiallyseparable structure (typically associated with sparsity) often present inunconstrained and bound-constrained optimization problems. This techniqueimproves performance by orders of magnitude and makes it possible to solvelarge problems that otherwise are totally intractable by other derivative-freemethods. A library of interpolation-based modelling tools is also described,which can be associated to the structured or unstructured versions of theinitial BFO pattern search algorithm. The use of the library further enhancesperformance, especially when associated with structure. The significant gainsin performance associated with these two techniques are illustrated using anew freely-available release of BFO which incorporates them. A interestingconclusion of the results presented is that providing global structuralinformation on a problem can result in significantly less evaluations of theobjective function than attempting to building local Taylor-like models.
KW - derivative-free optimization
KW - direct-search methods
KW - structured problems
KW - interpolation models
UR - http://www.scopus.com/inward/record.url?scp=85125179007&partnerID=8YFLogxK
U2 - 10.1145/3474054
DO - 10.1145/3474054
M3 - Article
AN - SCOPUS:85125179007
SN - 0098-3500
VL - 48
JO - ACM Transactions on Mathematical Software
JF - ACM Transactions on Mathematical Software
IS - 1
M1 - 6
ER -