Global and local information in structured derivative free optimization with BFO

Margherita Porcelli, Philippe Toint

Research output: Working paper

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 to the structured or unstructured versions of the
initial BFO 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 BFO which incorporates them. A interesting
conclusion of the 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.
Original languageEnglish
PublisherArxiv
Number of pages27
Volume2001.04801
Publication statusPublished - 15 Jan 2020

Fingerprint

Derivatives
Constrained optimization
Interpolation

Keywords

  • derivative-free optimization
  • direct-search methods
  • structured problems
  • interpolation models

Cite this

@techreport{c81783278ee942f2bbe9d491898f67c2,
title = "Global and local information in structured derivative free optimization with BFO",
abstract = "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.",
keywords = "derivative-free optimization, direct-search methods, structured problems, interpolation models",
author = "Margherita Porcelli and Philippe Toint",
year = "2020",
month = "1",
day = "15",
language = "English",
volume = "2001.04801",
publisher = "Arxiv",
type = "WorkingPaper",
institution = "Arxiv",

}

Global and local information in structured derivative free optimization with BFO. / Porcelli, Margherita; Toint, Philippe.

Arxiv, 2020.

Research output: Working paper

TY - UNPB

T1 - Global and local information in structured derivative free optimization with BFO

AU - Porcelli, Margherita

AU - Toint, Philippe

PY - 2020/1/15

Y1 - 2020/1/15

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 - Working paper

VL - 2001.04801

BT - Global and local information in structured derivative free optimization with BFO

PB - Arxiv

ER -