Multidisciplinary System Design Optimization MSDO Optimization Method Selection Recitation 5 Andrew March 1 Massachusetts Institute of Technology Prof de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics Today s Topics Review optimization algorithms Algorithm Selection Questions 2 Massachusetts Institute of Technology Prof de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics Analytical Methods Gradient Based Steepest descent Conjugate Gradient Newton s Method Quasi Newton Direct Search Compass search Nelder Mead Simplex Note The gradient methods have a constrained equivalent Steepest Descent CG Use projection Newton Quasi Newton SQP Direct search typically uses barrier or penalty methods Gradient Methods Compute descent direction dk Compute step length k Take step x k 1 x k k d k Repeat until kdk Steepest Descent Compute descent direction d k f x k Compute step length k Exactly k arg min f x k d k Inexactly any k such that for a c1 c2 in 0 c1 c2 1 T f x k k d k f x k c1 k f x k d k f x k k d k d k c2 f x k d k T Take step x k 1 x k k d k Repeat until kdk T Conjugate Gradient Compute descent direction d k f x k k d k 1 T T f x k f x k or f x k f x k f x k 1 k f x k 1 f x k 1 k T f x k 1 f x k 1 T Compute step length k Exactly k arg min f x k d k Inexactly any k such that for a c1 c2 in 0 c1 c2 1 T f x k k d k f x k c1 k f x k d k f x k k d k d k c2 f x k d k T Take step x k 1 x k k d k Repeat until kdk T Newton s Method Compute descent direction d k H 1 x k f x k Compute step length k Try k 1 decrease If not Exactly k arg min f x k d k Inexactly any k such that for a c1 c2 in 0 c1 c2 1 f x k k d k f x k c1 k f x k d k T f x k k d k d k c2 f x k d k T Trust region k d k k Take step x k 1 x k k d k Repeat until kdk T Quasi Newton Compute descent direction d k B 1 x k f x k B x k H x k B x k f 0 Compute step length k Try k 1 decrease If not Exactly k arg min f x k d k Inexactly any k such that for a c1 c2 in 0 c1 c2 1 f x k k d k f x k c1 k f x k d k T f x k k d k d k c2 f x k d k T Take step x k 1 x k k d k Repeat until kdk T Direct Search Compass Search k xk kei Evaluate f x k k ei i If f x k k ei f x k xk kej xk xk kej Move to minimum of f x k k ei i Else 1 k 1 k 2 xk kei Direct Search Nelder Mead Generate n 1 points in n x1 xn 1 Iterate f x x l arg min x f x x h arg max x x centroid x1 K x n 1 Reflect 0 x r 1 x x h if f x l f x r and f x r f x h x h x r return if f x r f x l Expand 1 x e x r 1 x if f x e f x l x h x e return else x h x r return if f x r f x h Contract 0 1 x c x h 1 x if f x c min f x h f x r x h x c return else x i x i x l 2 i i i J A Nelder and R A Mead A simplex method for function minimization Computer Journal Vol 7 pp 308 313 1965 Heuristic Methods Simulated Annealing Genetic Algorithms Particle Swarm Optimization next lecture Tabu Search next lecture Efficient Global Optimization Simulated Annealing Terminology X or R or Design Vector i e Design Architecture Configuration E System Energy i e Objective Function Value T System Temperature Difference in System Energy Between Two Design Vectors The Simulated Annealing Algorithm 1 Choose a random Xi select the initial system temperature and specify the cooling i e annealing schedule 2 Evaluate E Xi using a simulation model 3 Perturb Xi to obtain a neighboring Design Vector Xi 1 4 Evaluate E Xi 1 using a simulation model 5 If E Xi 1 E Xi Xi 1 is the new current solution 6 If E Xi 1 E Xi then accept Xi 1 as the new current solution with a probability e T where E Xi 1 E Xi 7 Reduce the system temperature according to the cooling schedule 8 Terminate the algorithm Genetic Algorithm Initialize Population initialization next generation Select individual for mating selection Mate individuals and produce children crossover Mutate children mutation Insert children into population insertion n Are stopping criteria satisfied y Finish 13 Ref Goldberg 1989 Massachusetts Institute of Technology Prof de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics Particle Swarm Birds go in a somewhat random direction but also somewhat follow a swarm Keep checking for better locations Generally continuous parameters only but there are discrete formulations Tabu Search Keep a list of places you ve visited Don t return keep finding new places Efficient Global Optimization Started by Jones 1998 Based on probability theory Assumes f x T x N x 2 x T x true behavior regression 2 N x x error from true behavior is normally distributed with mean x and variance 2 x Estimate function values with a Kriging model radial basis functions Predicts mean and variance Probabilistic way to find optima Evaluate function at maximum expected improvement location s and update model What s good algorithm Objective Contours Steepest descent Conjugate gradient Newton s Method Quasi Newton SQP Compass Search Nelder Mead Simplex SA GA Tabu PSO EGO What s good algorithm f x 100 x2 x 1 x 2 2 1 2 1 Steepest descent Conjugate gradient Newton s Method Quasi Newton SQP Compass Search Nelder Mead Simplex SA GA Tabu PSO EGO What s good algorithm Objective Function a Find quick improvement b Find global optima Steepest descent Conjugate gradient Newton s Method Quasi Newton SQP Compass Search Nelder Mead Simplex SA GA Tabu PSO EGO What s good algorithm x1 1 2 3 4 x2 min f x1 x2 Steepest descent Conjugate gradient Newton s Method Quasi Newton SQP Compass Search …