DerivativeFree Optimization and Applications
  
Problem Description
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 derivativefree optimization is currently an area of great demand. Difficulties and challenges arise from multiple sources: expensive function evaluation, blackbox/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.
Modelling & Computational Challenges
Astrophysics. Describing a single star by means of theoretical stellar models is a nontrivial 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 adhoc approximations such as the unicity of the mixing length parameter and the metaltohelium 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 derivativefree global optimization code [8], which has been appropriately interfaced with the stellar evolutionary code.
Nanotechnology. One of the derivativefree 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 (derivativefree) 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 derivativefree 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 userprovided 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.

Research at LCM
We have identified five applications involving complex simulations and/or physical experimentations, resulting from joint research with engineering colleagues (see above): astrophysics, 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 derivativefree 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]).
Our goal is also to promote a numerical comparison of different classes of derivativefree algorithms (which remains relatively open), providing a template for various methods and a benchmarking test set that represents well the sort of difficulties that arise in derivativefree optimization.
A book on the topic is currently being finished: Introduction to DerivativeFree Optimization, A. R. Conn, K. Scheinberg, and L. N. Vicente, MPSSIAM Series on Optimization, SIAM, Philadelphia, to appear in 2008.
Papers & Reports
 [1] P. Alberto, F. Nogueira, H. Rocha, and L. N. Vicente, Pattern search methods for userprovided points: Application to molecular geometry problems, SIAM Journal on Optimization, 14 (2004) 12161236
 [2] A. R. Conn, K. Scheinberg, and L. N. Vicente, Geometry of interpolation sets in derivative free optimization, to appear in Mathematical Programming
 [3] A. R. Conn, K. Scheinberg, and L. N. Vicente, Geometry of sample sets in derivative free optimization: Polynomial regression and underdetermined interpolation, to appear in IMA Journal of Numerical Analysis
 [4] A. R. Conn, K. Scheinberg, and L. N. Vicente, Global convergence of general derivativefree trustregion algorithms to first and second order critical points, Preprint 0649 of the Department of Mathematics, University of Coimbra
 [5] A. L. Custódio, J. E. Dennis Jr., and L. N. Vicente, Using simplex gradients of nonsmooth functions in direct search methods, appear in IMA Journal of Numerical Analysis
 [6] A. L. Custódio and L. N. Vicente, Using sampling and simplex derivatives in pattern search methods, SIAM Journal on Optimization, 18 (2007) 537555
 [7] M. Hintermüller and L. N. Vicente, Space mapping for optimal control of partial differential equations, SIAM Journal on Optimization, 15 (2005) 10021025
 [8] A. Ismael F. Vaz and L. N. Vicente, A particle swarm pattern search method for bound constrained global optimization, to appear in Journal of Global Optimization
Software
 [1] PSwarm: A global optimization solver for linearly constrained problems (without derivatives) (C, including Parallel MPI, and Matlab)  available.
 [2] SIDPSM: A pattern search method guided by simplex derivatives for use in derivativefree optimization (Matlab)  available under request.
Project Team
 A. Ismael F. Vaz, Department of Production and Systems, University of Minho
 Luís Nunes Vicente, LCM/CMUC
 Ana Luísa Custódio, New University of Lisbon
 A.R. Conn and K. Scheinberg, IBM T.J. Watson Research Center
 J. M. Fernandes, Department of Mathematics & Astronomical Observatory, FCTUC
 A. Cavaleiro, N. Carvalho, and N. Parreira, Department of Mechanical Engineering, FCTUC
 E. Ferreira, Department of Biological Engineering, University of Minho
 P. Alberto and F. Nogueira, Department of Physics, FCTUC
 A. Pinto da Costa, Department of Civil Engineering, IST
Project Reference
FCT Research Project  POCI/MAT/59442/2004