Multifidelity Optimization Using Asynchronous Parallel
Pattern Search and Space Mapping Techniques
Genetha Gray*, Joe Castro , Patty Hough*, and Tony Giunta
*Computational Sciences & Mathematics Research, Sandia National Labs, Livermore, CA
Computational Sciences and Validation & Uncertainty Quantification Processes, Sandia National Labs, Albuquerque, NM
Purpose of Multifidelity Optimization
In many optimization applications, the objective
function f(x) is expensive to calculate and derivatives
may be inaccurate if they exist at all.
Many of these applications have a high fidelity (or
true) model and a low fidelity (or surrogate) model
which simplifies the high fidelity model in some
way.
An MFO approach optimizes an inexpensive, low
fidelity model while making periodic corrections
using the expensive, high fidelity model.
The relationship between the models can be exploited
in an algorithm by applying space mapping
techniques.
MFO Scheme
Outer Loop Optimizer: Asynchronous
Parallel Pattern Search (APPSPACK)
Direct search method
Takes advantage of parallel platform to reduce
computational time
Does not assume time needed to evaluate objective
function is constant
Global convergence to a
stationary point under
mild conditions
Does not
assume
homogeneous
processors
The Inner Loop as an Oracle
)
x
H
(
,f
xH
Space Mapping
Via
Least Squares
Calculation
High Fidelity Mode
Optimization
via
APPSPACK
xH trial
Outer Loop
Low Fidelity Model
Optimization
xH
Inner Loop
MFO ALGORITHM
1. Start Outer Loop (APPSPACK)
Evaluate N high fidelity response points
Produce table of data with xH and fH(xH)
2. Start Inner Loop
Take data from APPSPACK table
Run LS optimization algorithm
At each iteration, evaluate N low-fidelity responses
At completion obtain , , for our space mapping of (xH) +
Optimize low fidelity model within space mapped high
fidelity space. In other words, minimize fL((xH) + ) with
respect to xH to obtain xH*
3. Return xH* to APPPSPACK to determine if a new best
point has been found.
If the inner loop is viewed as an oracle, the only
significant algorithmic change to APPS is the
addition of the oracle.
Analytically, there are no restrictions on how an
oracle can choose points.
Oracle points are used in addition to the points
defined by the search pattern
The convergence of APPSPACK is not adversely
affected.
A convergence proof for the APPS algorithm
exists so no new convergence proof for our MFO
scheme is needed.
Future work may include investigating any
improvement to the convergence of APPS.
A Simple Example
Polynomial Example
2
Space Mapping Representation
RHFM ( x0 , x1 ) x0 0.5 x1 0.83
*
HFM
R
2
2
RLFM ( x0 , x1 ) x0 x1
*
LFM
R
RHFM ( 0.5,0.83)
2
x0 0 x1 1
2
f H ( x0 , x1 ) (0.8 x0 0.5) 2 (0.5 x1 0.83) 2
2
RLFM (0.0,0.0)
When the number of response points is 8, there are two
calls to the inner loop
0 0.5 , 1 0.83
Hi-Fi Model
Result:
Gamma ~ O(1), Starting Point = (-2.0,-2.0)
2
0
2
1
2
f L ( x0 , x1 ) x x ( x0 0 ) ( x1 1 )
2
f H ( x0 , x1 ) ( x0 0.5) ( x1 0.83)
# responses
(x0,x1)
(-0.5,0.83)
(-0.8,-1.2) 1 (-0.76,2.0)
2
2
1
2
Objective
Value
0.0
# Hi-Fi
Calculations
Speed
Up
Ratio
2
(-0.50, 0.83)
8.86e-17
21
2.76
4
(-0.50, 0.83)
5.13e-15
25
2.32
6
(-0.52, 0.84)
3.34e-4
43
1.35
8
(-0.48, 0.81)
1.03e-3
35
1.65
Apps only
(-0.50, 0.85)
4.00e-4
58
-
Log Plot of
Results
The numbered white boxes show
approximately where the inner loop
was called.
The point in red brackets is the
APPSPACK best point before the
inner loop call.
The point in green was obtained by
the inner loop.
(-0.56,1.6) 2 (-0.61,1.25)
Ongoing and Future Work
Study spaces defined using different constraints.
Implement a generic oracle in APPSPACK.
Include a space mapping that does not require domain
spaces to be defined by the same numbers of parameters.
Apply our multifidelity optimization schemes to some
real world problems:
Earth penetrator analysis
Groundwater problems including well field design &
hydraulic capture
Circuit system design
References
Consider a simple example with constant space mapping terms:
Study space mapping sensitivities to various inputs
Number of high fidelity responses used in the mapping
Scaling of the mapping parameters (size of the offset between the low and high fidelity models)
Starting point
Compare the optimum obtained and the number of high fidelity runs required to reach this
optimum
View of High Fidelity
Design Space
Sandia National Laboratories is a multiprogram laboratory operated by Sandia Corporation, a Lockheed Martin Company, for the United States Department of Energy under contract DE-AC04-94AL85000.
Bakr, Bandler, Madsen, and Sondergard, An Introduction to Space
Mapping Technique, Optimization & Engineering, 2:369-384, 2001.
Gray and Kolda, APPSPACK 4.0: Asynchronous Parallel Pattern Search
for Derivative-Free Optimization, Technical Report SAND2004-6391,
Sandia National Laboratories, Livermore, CA, Aug 2004. (Submitted to
ACM TOMS.) http://software.sandia.gov/appspack/version4.0/
Kolda, Revisiting Asynchronous Parallel Pattern Search for Nonlinear
Optimization, Technical Report SAND2004-8055, Sandia National
Laboratories, Livermore, CA, Feb 2004. (In revision for SIAM J. Opt.)
Kolda, Lewis, and Torczon, Optimization by Direct Search: New
Perspectives on Some Classical and Modern Methods, SIAM Review,
45(3):385-482, 2003.
