Derivative-Free Optimization and Applications
Research grant POCI/MAT/59442/2004 funded by
May 2005 - December 2007
Doctoral Members: A. Ismael F. Vaz and
Luís Nunes Vicente (PI)
Ana Luísa Custódio
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 ). 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 ).
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.
Describing a single star by means of theoretical stellar models is a
non-trivial problem due to the simulations involved and the large
number of unknowns compared to the observations. Currently, stellar
age and mass are estimated using interpolation in grids of stellar
models and/or assuming ad-hoc approximations such as the unicity of
the mixing length parameter and the metal-to-helium enrichment,
normally scaled by the solar values.
We are developing a new approach to model the FGK main sequence of stars of
Population I, by directly minimizing the fitting of the evolutionary
simulations to the observations, as a combined function of the mass,
age, helium and metals abundance, mixing length parameter, and
overshooting. The optimization of the fitting permits to extract
these six parameters simultaneously, and it is achieved by applying a
derivative-free global optimization code , which has been appropriately
interfaced with the stellar evolutionary code.
One of the derivative-free applications involves the optimization of material properties in the development of new functional coatings for decorative and microoptoelectronics applications. The optimization problems are unconstrained but might involve more than one objective. Evaluation of the functions results from nanotechnology experimentation.
The coatings are based on transition metals oxynitrides and are deposited by physical vapour deposition techniques. The idea is to combine the excellent mechanical properties of the nitrides with specific optical characteristics (colours) of the oxides. By tuning the deposition conditions, one can obtain coatings with compositions varying from oxides to nitrides, thus exploring the vast spectrum of their optical and mechanical properties. The tuning is now carried out by varying the oxides and nitrides decompositions. Application of (derivative-free) optimization is expected to guide this tuning process more efficiently (and less costly) and to lead to new material compositions.
Air Pollution. Another application of derivative-free optimization involves function evaluation by numerical simulation. The existence of several models for air pollution allows the possibility of computing the maximum air pollution concentration in a given region. The existent models, available both for fixed and mobile sources, allow also the planning of the sampling stations positions (maximizers). The refined models provide a more detailed treatment of physical and chemical processes, but have higher computational costs and the available software is usually written in a computer language where derivatives are not available or are expensive to compute.
Molecular Geometry. A fourth application is in optimization of molecular geometries based on heavy molecular dynamics. A class of new parallel pattern search methods has been developed, tailored to geometrical transformations as user-provided points . Now, we plan to investigate the use of surrogate models in the search step of the methods. We will continue to use parallel computing but will move to carbon clusters.
Mechanical System with Contact. A fifth application in which we are already involved, deals with the simulation of a mechanical system with potential contact by friction. The problem has only a few optimization variables but function evaluation (the minimal normal displacement) requires the integration of a modified ODE system with potential nondifferentiabilities. This problem has constraints, where derivatives are known.
 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.
 A.R. Conn, K. Scheinberg, and L.N. Vicente,
Geometry of interpolation sets in derivative free optimization,
Mathematical Programming, 111 (2008) 141-172.
 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.
 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.
 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.
 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.
 M. Hintermüller and L.N. Vicente, Space mapping for optimal
control of partial differential equations, SIAM Journal on Optimization, 15 (2005) 1002-1025.
 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.
PSwarm: A global optimization
solver for bound constrained problems (without derivatives) -
 SID-PSM: A pattern search method guided by simplex derivatives for use in derivative-free optimization (MATLAB) - available under request.