TY - JOUR
T1 - Exploting problem structure in Derivative-Free Optimization
AU - Porcelli, Margherita
AU - Toint, Philippe
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
M3 - Article
VL - 48
JO - ACM Transactions on Mathematical Software
JF - ACM Transactions on Mathematical Software
SN - 0098-3500
IS - 1
M1 - 6
ER -