Derivative-Free Optimization and Applications

Research grant POCI/MAT/59442/2004 funded by FCT.

May 2005 - December 2007

Doctoral Members: A. Ismael F. Vaz and Luís Nunes Vicente (PI)
Graduate Students: Ana Luísa Custódio
Consultants: Andrew R. Conn and Katya Scheinberg - João M. Fernandes

Optimization problems defined by functions for which derivatives are unavailable or available at a prohibitive cost are appearing more and more frequently in computational science and engineering. Increasing complexity in mathematical modeling, higher sophistication of scientific computing, and abundance of legacy codes are some of the reasons why derivative-free optimization is currently an area of great demand. Difficulties and challenges arise from multiple sources: expensive function evaluation, black-box/legacy codes, noise and uncertainty, unknown a priori function domains, and hidden constraints.

In many physical applications, the true models or functions being optimized are extremely expensive to evaluate but, based e.g. on simplified physics or mesh coarsening, there are often surrogate models available, less accurate but cheaper to evaluate. In these circumstances, one would expect to design an optimization framework capable of extracting as much information as possible from the surrogate model while parsimoniously using the fine, true model to accurately guide the course of the optimization process.

We have identified five applications involving complex simulations and/or physical experimentations, resulting from joint research with engineering colleagues (see below): nanotechnology, air pollution, molecular geometry, mechanical system with contact.

On a different but related level, this project involves the development, analysis, and implementation of new algorithms for derivative-free optimization, by bringing together different geometrical concepts (like positive generators and poisedness [2,3]) and different sampling strategies (like directional sampling and surrogate modeling [7]). The goal is to exchange ideas from different methodologies (for instance, using simplex gradients to poll more efficiently in pattern search [5,6], or using heuristics to improve the search phase of pattern search towards global optimization [8]).

A book on the topic is currently being finished: Introduction to Derivative-Free Optimization, A. R. Conn, K. Scheinberg, and L. N. Vicente, MPS-SIAM Series on Optimization, SIAM, Philadelphia, to appear in 2008.


[1] P. Alberto, F. Nogueira, H. Rocha, and L.N. Vicente, Pattern search methods for user-provided points: Application to molecular geometry problems, SIAM Journal on Optimization, 14 (2004) 1216-1236. PDF

[2] A.R. Conn, K. Scheinberg, and L.N. Vicente, Geometry of interpolation sets in derivative free optimization, Mathematical Programming, 111 (2008) 141-172. PDF

[3] A. R. Conn, K. Scheinberg, and L. N. Vicente, Geometry of sample sets in derivative-free optimization: Polynomial regression and underdetermined interpolation, IMA Journal of Numerical Analysis, 28 (2008) 721-748. PDF

[4] A. R. Conn, K. Scheinberg, and L. N. Vicente, Global convergence of general derivative-free trust-region algorithms to first and second order critical points, SIAM Journal on Optimization, 20 (2009) 387-415. PDF

[5] A. L. Custódio, J. E. Dennis Jr., and L. N. Vicente, Using simplex gradients of nonsmooth functions in direct search methods, IMA Journal of Numerical Analysis, 28 (2008) 770-784. PDF

[6] A.L. Custódio and L.N. Vicente, Using sampling and simplex derivatives in pattern search methods, SIAM Journal on Optimization, 18 (2007) 537-555. PDF

[7] M. Hintermüller and L.N. Vicente, Space mapping for optimal control of partial differential equations, SIAM Journal on Optimization, 15 (2005) 1002-1025. PDF

[8] A. I. F. Vaz and L.N. Vicente, A particle swarm pattern search method for bound constrained global optimization, Journal of Global Optimization, 39 (2007) 197-219. PDF


[1] PSwarm: A global optimization solver for bound constrained problems (without derivatives) - available.

[2] SID-PSM: A pattern search method guided by simplex derivatives for use in derivative-free optimization (MATLAB) - available under request.