Engineering Analysis ENG 3420 Fall 2009 Dan C Marinescu Office HEC 439 B Office hours Tu Th 11 00 12 00 Lecture 11 Last time Newton Raphson The secant method Today Optimization Golden ratio makes one dimensional optimization efficient Parabolic interpolation locate the optimum of a single variable function fminbnd function determine the minimum of a one dimensional function fminsearch function determine the minimum of a multidimensional function Next Time Linear algebra Lecture 11 2 Optimization Critical for solving engineering and scientific problems One dimensional versus multi dimensional optimization Global versus local optima A maximization problem can be solved with a minimizing algorithm Optimization is a hard problem when the search space for the optimal solution is very large Heuristics such as simulated annealing genetic algorithms neural networks Algorithms Golden ratio makes one dimensional optimization efficient Parabolic interpolation locate the optimum of a single variable function fminbnd function determine the minimum of a one dimensional function fminsearch function determine the minimum of a multidimensional function How to develop contours and surface plots to visualize twodimensional functions 3 Optimization Find the most effective solution to a problem subject to a certain criteria Find the maxima and or minima of a function of one or more variables One versus multi dimensional optimization One dimensional problems involve functions that depend on a single dependent variable for example f x Multidimensional problems involve functions that depend on two or more dependent variables for example f x y Global versus local optimization Global optimum the very best solution Local optimum solution better than its immediate neighbors Cases that include local optima are called multimodal Generally we wish to find the global optimum One versus Multi dimensional Optimization One dimensional problems involve functions that depend on a single dependent variable for example f x Multidimensional problems involve functions that depend on two or more dependent variables for example f x y Euclid s golden number Given a segment of length y1 y2 the golden number is determined from the condition y1 y2 2 y1 y y2 1 2 1 0 y2 y2 The solution of the last equation is 1 5 1 680133 2 8 Golden Section Search Algorithm for finding a minimum on an interval xl xu with a single minimum unimodal interval uses the golden ratio 1 6180 to determine location of two interior points x1 and x2 d 1 x u x l x1 x l d x 2 x u d One of the interior points can be re used in the next iteration f x1 f x2 x2 will be the new lower limit and x1 the new x2 f x2 f x 1 x1 will be the new upper limit and x2 the new x1 f x1 f x2 x2 is the new lower limit and x1 the new x2 f x2 f x1 x1 is the new upper limit and x2 the new x1 Golden section versus bisection 11 Parabolic interpolation Parabolic interpolation requires three points to estimate optimum location The location of the maximum minimum of a parabola defined as the interpolation of three points x1 x2 and x3 is 2 2 1 x 2 x1 f x 2 f x 3 x 2 x 3 f x 2 f x1 x 4 x 2 2 x 2 x1 f x 2 f x 3 x 2 x 3 f x 2 f x1 The new point x4 and the two surrounding it either x1 and x2 or x2 and x3 are used for the next iteration of the algorithm fminbnd built in function fminbnd combines the golden section search and the parabolic interpolation Example xmin fval fminbnd function x1 x2 Options may be passed through a fourth argument using optimset similar to fzero fminsearch built in function fminsearch determine the minimum of a multidimensional function xmin fval fminsearch function x0 xmin a row vector containing the location of the minimum x0 an initial guess must contain as many entries as the function expects The function must be written in terms of a single variable where different dimensions are represented by different indices of that variable Example minimize f x y 2 x y 2x2 2xy y2 Step 1 rewrite as f x1 x2 2 x1 x2 2 x1 2 2x1x2 x2 2 Step 2 define the function f using Matlab syntax f x 2 x 1 x 2 2 x 1 2 2 x 1 x 2 x 2 2 Step 3 invoke fminsearch x fval fminsearch f 0 5 0 5 x0 has two entries f is expecting it to contain two values the minimum value is 0 7500 at a location of 1 000 1 5000 Heuristics for global optimization Global optimization is a very hard problem when the search space for the solution is very large Heurisitic adjective for experience based techniques that help in problem solving learning and discovery A heuristic method is particularly used to rapidly come to a solution that is hoped to be close to the best possible answer or optimal solution Heuristics noun meaning rules of thumb educated guesses intuitive judgments or simply common sense Heuristics for global optimization Simulated annealing Genetic algorithms Neural networks 17 Simulated annealing SA Inspired from metallurgy Annealing is a technique involving heating and controlled cooling of a material to increase the size of its crystals and reduce their defects The heat causes the atoms to become unstuck from their initial positions a local minimum of the internal energy and wander randomly through states of higher energy the slow cooling gives them more chances of finding configurations with lower internal energy than the initial one Each step of the SA algorithm Replaces the current solution by a random nearby solution chosen with a probability that depends on the difference between the corresponding function values and on a global parameter T called the temperature that is gradually decreased during the process The dependency is such that the current solution changes almost randomly when T is large but increasingly downhill as T goes to zero The allowance for uphill moves saves the method from becoming stuck at local minima which are the bane of greedier methods 18 Genetic algorithms Global search heuristics to find exact or approximate solutions to optimization and search problems Genetic algorithms are a particular class of evolutionary algorithms EA that use evolutionary biology concepts such as inheritance mutation selection and crossover The evolution usually starts from a population of randomly generated individuals and happens in generations In each generation the fitness of every individual in the population is evaluated multiple individuals are stochastically selected from the current population based on their fitness and modified recombined and possibly randomly mutated to form a new