1 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Approximation Methods Lecture 19 16 April 2004 Karen Willcox Multidisciplinary SystemMultidisciplinary System Design Optimization (MSDO) 2 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Today’s Topics ? Design variable linking ? Reduced-Basis Methods ? Response Surface Approximations ? Kriging ? Variable-Fidelity Models 3 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Why Approximation Methods? We have seen throughout the course the constant trade-off between computational cost and fidelity. Level of MSDO Fidelity Level trade studies limited optimization/iteration full MDO empirical models intermediate fidelity (e.g. vortex lattice, beam theory) high fidelity (e.g. CFD,FEM) i n c r e a s i n g d i f f i c u l t y from Giesing, 1998 can we do better? can the results be believed? how to implement? Approximation methods provide a way to get high-fidelity model information throughout the optimization without the computational expense. 4 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Approximation Methods ? Recall that the analysis or simcode must be invoked each time the optimizer selects a new design vector to try ? Typically, hundreds (thousands) of design vectors will be analyzed throughout an optimization run ? Can use Approximation Models (Surrogate Models) for objective functions and constraints ? If approximate models are inexpensive to evaluate, can analyze many more design vector options without worrying about computational resources ? Concept first introduced in structural optimization by Barthelemy and Haftka, 1993 5 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Approximation Methods Overview Design variable linking Reduced-basis methods ? reduce the number of design variables in the optimization code ? simcode analysis full order Response surface methods Kriging ? same number of design variables ? simcode analysis simplified Variable-fidelity methods ? combine high-fidelity and approximation models 6 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Design Variable Linking ? Not all design variables may be independent ? For example, symmetry may exist in the problem Define: C = + ?? ?? ?? ? ? ?? ?? = + ?? ? ? ?? ?? ?? ? ? ?? ?? ?? yTx y r ×1 n ×1 r ×n r ×1 optimizer uses y, but provides x to simcode for analysis y T x y C 7 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Reduced-Basis Methods Consider r feasible design vectors: x 1 , x 2 , ..., x r We could consider the desired design to be a linear combination of these basis vectors: 1 * ι α = = + ∑ r i C i x x x scalar coefficient basis vector added for generality 8 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Reduced-Basis Methods We can now optimize J(x) by finding the optimal values for the coefficients α i . dimension n dimension r ? do one full-order evaluation of resulting answer ? approach is efficient if r << n ? will give the true optimum only if x* lies in the span of {x i } ? basis vectors could be – previous designs – solutions over a particular range (DoE) – derived in some other way (POD) 9 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Reduced-Basis Example Example using a reduced-basis approach (van der Plaats Fig 7-2): airfoil design for a unique application. ? many airfoil shapes with known performance are available ? design variables are (x,y) coordinates at chordwise locations (n~100) ? use four basis airfoil shapes (low-speed airfoils) which contain the n geometry points ? plus two basis shapes which allow trailing edge thickness to vary ? r=6 (r<<n) ? optimize for high speed, maximum lift with a constraint on drag 10 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Reduced-Basis Example 11 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Proper Orthogonal Decomposition 1 * ι α? = = ∑ r i i x ?The r basis vectors ? i are orthogonal ? They are computed from M empirical solutions {x 1 , x 2 ,... x M } ? They are optimal in the sense that they minimize the error between the original and the projected data 2 2 (, ) max ? ? ? x Also known as principal components analysis, Kahunen Loève decomposition, singular value decomposition 12 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Proper Orthogonal Decomposition These optimal basis functions can be calculated by: 1. Evaluating the correlation matrix: 2. Solving the M×M eigenvalue problem: 3. Constructing the basis vectors: Ti j ij R = xx i i i R λ=v v 1 M i i j j i v? = = ∑ x Use components of the jth eigenvector to calculate the jth POD basis vector. The jth eigenvalue tells us how important is the jth basis vector. Vanderplaats, G. N. Numerical Optimization Techniques for Engineering Design. Vanderplaats R&D, 1999. Figure 7-2. Vanderplaats, G. N. Numerical Optimization Techniques for Engineering Design. Vanderplaats R&D, 1999. Figure 7-3. 13 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Approximation Methods Overview Design variable linking Reduced-basis methods ? reduce the number of design variables in the optimization code ? simcode analysis full order Response surface methods Kriging ? same number of design variables ? simcode analysis simplified Variable-fidelity methods ? combine high-fidelity and approximation models 14 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Response Surface Methodology ? Keep the same number of design variables, but simplify the simcode analysis ? Create approximating functions to objective and constraints ? Optimize using the approximations ? Update approximations using current optimal solution guess and repeat ? Response surfaces are smooth even if design space is noisy ? Polynomial-based modeling technique ? Provide compact, explicit functional relationship between response and design variables ? Least squares is computationally inexpensive and easy to implement 15 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Local Approximations Most common are Taylor series expansions: δ δ δ? ?= + ? + + ? ? " 0 0 1 ( ) () () () 2 T T J J J 0 x x x x x H x x 0 δ =?xxx ? Could use the first two terms ? linear approximation ? Solve, reanalyze and repeat = sequential linear programming ? Could also include quadratic term: δ δ δ? ?= + ? + + ? ? " 0 0 1 ( ) () () () 2 T T J J J 0 x x x x x H x x update requires: 1 function evaluation n function evaluations n(n+1)/2 function evaluations 16 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Local Approximations ? It is expensive to update the gradient vector and Hessian matrix ? One approach: – perform several approximation cycles updating only the constant term – then update the linear term and repeat – finally, update the Hessian only when no other progress can be made ? If the design space is highly nonlinear, there is no guarantee that this approach will work 17 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Response Surface Methodology ? Another approach: use what information is available to create the approximation ? Use this approximation to make a small move in the design variables ? Analyze the result precisely ? new function evaluation ? Use the new function evaluation to improve the approximation to the design space ? Fit a response surface ? Can use a quadratic or higher order surface ? Might choose to use only some of the function evaluations (e.g. those in a local neighborhood) 18 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics RSM ?= ? 0 . . define ( ) ( )eg J J Jx x ( ) T T 1 2 1 2 2 2 2 11 1 22 2 12 1 2 13 1 3 1 1 23 2 3 1, 1 ... 1 ... 2 ... ... n n nn n n n n n n n J J J J J x x x x x x H x H x H x H x x H x x H x x H x x H x x δ δ δ δ δ δ δ δ δ δ δ δ δ δ δ δδ δ δ ? ? ?=? + ? ? ? = + + + ? ? ? + + + + + + + + + + + x x H x quadratic approximation: (all derivatives and entries of H are evaluated at x 0 ) (?) 19 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics RSM Assume we have evaluated the baseline plus q designs: → 0 1 0 1 , ,..., , ,... q q JJ Jxx x We could write q equations of the form (?) using There is a total of N=n+n(n+1)/2 unknowns: ? ? ? ? ? ? 11 12 1 2 , ,..., , , ,..., nn n J J J HH H x x x ( ) ( ) ( ) 1 0 1 0 2 0 2 0 0 0 , , , , , , q q J J J J J J? ? ? ? ? ?x x x x x x" 20 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics RSM ? q equations, N unknowns ?If q<N, only some coefficients can be calculated ?If q>N, use weighted least squares ? Weight designs closer to current x q more heavily ? In general, use q≥n+1 initial designs so an initial linear approximation can be provided ? If have baseline plus n designs, can fit a linear approximation in each direction (i.e. a hyperplane) ? If have more solutions, can fit a quadratic or higher order surface 21 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics RSM ? In other words, fit objective function with a polynomial ? e.g. quadratic approximation: ? Update model by including a new function evaluation then doing least squares fit to compute the new coefficients 2 , () ii ii i iji j i i i j i J b x c x c x x < = + + + ∑ ∑ ∑0 x a 22 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics RSM Estimation problem: ≈JXc T 1 2 M J J J? ?= ? ? J " 1 1 1 1 1 2 1 1 2 1 1 2 1 1 1 1 1 M M M M x x x x x x x x x ? ? ? ? ? ? ? ? ? ? ? ? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? X " " # # 0 1 1p c c c ? ? ? ? ? ? ? = ? ? ? ? ? ? ? ? c J=vector containing M responses c=vector containing p coefficients x=M×p matrix containing M design vector inputs as rows. Columns depend on approximation. Least squares solution: ( ) 1 T T ? =c X X X J 23 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Kriging ? RSM tends to create a global model of the design space (especially if all points weighted equally in the LS) ? May be of limited accuracy when multiple extrema exist (especially quadratic polynomial models) ? Kriging : combine global model of design space with a model for local deviations which interpolates sample points ? Developed in fields of spatial statistics and geostatistics ? Original statistical techniques developed by mining engineer D.G. Krige ? Interpolation-based modeling technique ? Computationally more expensive and not as simple to implement as RSM 24 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Kriging Unknown function to be modeled expressed as: () () ()J f Z= +x x x ? known function ? “global” model for design space ? e.g. use RSM to fit f(x) using M observations ? Gaussian random function ? zero mean ? variance σ 2 ? “localized” deviation from global model cov ( ), ( ) ( , ) i j i j Z Z Rσ 2 ? ? ? ?= ? ? ? ? x x R x x covariance matrix of Z(x) correlation matrix correlation function 25 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Approximation Methods Overview Design variable linking Reduced-basis methods ? reduce the number of design variables in the optimization code ? simcode analysis full order Response surface methods Kriging ? same number of design variables ? simcode analysis simplified Variable-fidelity methods ? combine high-fidelity and approximation models 26 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Variable Fidelity Models Initialization High-fidelity model Approximation model Optimizer x J(x), g(x) optimization on a simplified model recourse to detailed model From: Fig. 1, Alexandrov et al. ? Use information from high-fidelity model to check approximate designs ? Optimize using approximate model ? Recalibrate using high-fidelity model 27 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Variable Fidelity Models Questions: ? What do we do when the design derived from the low- fidelity optimization does not provide an improvement in the true objective? ? How can we use information about the predictive capability of the approximation model to decide when to go back to the high-fidelity model? ? How do we decide when to update the approximate model? 28 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Variable Fidelity Models When optimization with approximation model is unsuccessful, there are two possible approaches: 1. Improve the fidelity of the approximate model 2. Do “less” optimization One option: use a trust region approach current iterate x k trust region design space 29 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Trust Region Approach Classic approach: ? Regulate the length of the steps taken by the iterative optimization algorithm ? Regulate based on quality of current approximation model e.g. Quadratic Taylor series model: 1 ( ) ( ) ( ) ( ) 2 T k k k k k T k J q J J? ?+ ≈ + = + ? + ? ? x s x s x x s s B s where s is the prospective step in the design variables, ?x, and B k is a model of the Hessian matrix at x k . 30 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Trust Region Approach ? Restrict the step size to a region in which we trust the quadratic model to approximate J well ? Done by adding a constraint on the step ? trust region subproblem min ( ) s.t. k k k q δ + ≤ x s s ? In practice, variables are scaled to improve performance (step size can vary in different directions) ? Then decide whether to accept the step: 1 if ( ) ( ) otherwise k k k k k J J + ? + + < = ? ? x s x s x x x 31 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Trust Region Update ? Trust radius, δ k , is updated adaptively ? Update depends on predictive quality of quadratic model: ? if model did a good job of predicting J, or if there was more improvement than predicted, then increase δ k ? if model did a bad job of predicting J (J increased or decrease was much lower than predicted), then decrease δ k ? if model did an acceptable job of predicting J, then do not change δ k 32 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Trust Region Update ? Numerically, compare actual and predicted decrease: () ( ) () ( ) k k k k J J r J q ? + = ? + x x s x x s ? Define constants r 1 , r 2 (r 1 <r 2 ) and apply the rules: ?if r< r 1 , decrease the trust radius ?if r>r 2 , increase the trust radius ? Typical values are r 1 =0.1, r 2 =0.75 ? Note that prediction of ascent/descent is more important than prediction of actual value 33 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Classic Trust Region Algorithm For k=0,1,... until convergence do { Find an approximate solution s k to the subproblem: 0 0 Choose and 0 n δ∈ >x \ min ( ) s.t. k k k q δ + ≤ x s s Compare the actual and predicted decrease: () ( ) () ( ) k k k k J J r J q ? + = ? + x x s x x s Update x k and δ k } From Fig. 2, Alexandrov et al. 34 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics β-Correlation Method ? Basic idea is to take low-fidelity approximate model, J a , and correct it by scaling ? Define the scale factor: () () a J J β = x x Given the current design x k , build a first order model of β about x k : () ) )( ) k k k k β β β=( +?( ?x x x x x Optimize with approximate model and use local model of β to scale result : () () k a J Jβ≈x x 35 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Variable Complexity Model ? iSight uses a Variable Complexity Model (VCM) ? Use two simcodes for the same physical process: (1) more accurate, longer running (exact) J(x) (2) less accurate, shorter running (approx.) J a (x) ? Compute a multiplicative or additive correction factor, σ : 0 0 ) ) () ) a a J J J J σ σ ( = ( = ( x x x x 0 0 ) ) () ) a a J J J J σ σ =( ? ( =+ ( x x x x or 36 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics VCM Optimization Simcode J(x) Optimization Approx. J a (x) Optimization Approx. J a (x) Simcode J(x) Conventional optimization with simcode Conventional optimization with approximate model Optimize with approximate model, update with simcode: 1. Run both models, calculate σ 0 2. Optimize using approximate model and σ 0 3. Update correction factor using simcode and repeat 37 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Lecture Summary ? Approximation methods are one way to capture high-fidelity responses without the computational cost ? Design variable linking if physical problem allows ? Reduced-basis methods use low-order representation of the design vector ? use previous designs, DoE or POD ? Response surface methodology ? use polynomial models ? weighted least squares ? Kriging ? interpolation models ? global + local behavior ? Variable-fidelity models ? Trust region approach ? β-correlation 38 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics References Barthelemy, J-F. M. and Haftka, R.T., “Approximation concepts for optimum structural design – a review”, Structural Optimization, 5:129-144, 1993. Giunta, A.A. and Watson, L.T.,”A comparison of approximation modeling techniques: polynomial versus interpolating models”, AIAA Paper 98-4758, 1998. LeGresley, P.A. and Alonso, J.J., “Airfoil design optimization using reduced order models based on proper orthogonal decomposition”, AIAA Paper 2000-2545. Alexandrov, N., Dennis, J.E., Lewis, R.M. and Torczon, V., “A trust region framework for managing the use of approximation models in optimization”, NASA CR-201745, ICASE Report No. 97-50, October 1997. Practical Optimization, P.E. Gill, W. Murray and M.H. Wright, Academic Press, 1986. Numerical Optimization Techniques for Engineering Design, G.N. Vanderplaats, Vanderplaats R&D, 1999.