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.

Astrophysics. 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 [8], which has been appropriately interfaced with the stellar evolutionary code.
• Nanotechnology. 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 [1]. 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.

[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

Software:

[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.