Convex vs. Non-Convex Global Optimization (Deterministic) Convex Underestimator Multi-start Simulated Annealing Genetic Algorithms10.34, Numerical Methods Applied to Chemical Engineering Professor William H. Green Lecture #29: Global Optimization. Multiple Minima. Convex vs. Non-Convex Convex – only one minimum Non-convex – multiple relative minima minx f(x) Global Optimization (Deterministic) x f(x) Figure 1. A function with relative minima. Convex Underestimator xopt By looking at 2nd derivatives, find parabola that is lower than other minimum. 2 3 Figure 2. Convex underestimator. Choose a f(x), upper bound. Divide domain. Underestimate the lower bound with a parabola. Find minimum of parabola. Bound again. If new upper bound is lower than lower bound in other region, can stop considering that section. Cite as: William Green, Jr., course materials for 10.34 Numerical Methods Applied to Chemical Engineering, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY].To converge – lower bound rises at a certain rate; upper bound decreases at a certain rate. Going several zones deep, creates many divisions: 2Ndivisions(1-D) Proteins: 100 dimensional space or more: 100N or more Current papers: can solve 4-5 dimensions Method guarantees global optimum (if you care about the global optimum) If you have 20 variables, use heuristics that often find the global optimum, but there is no guarantee. Multi-start x28 8 8 8 8 8mesh of start points weighted Monte Carlo Figure 3. Begin in multiple locations and then run minimization. In low dimension, draw map. One method, do different starts. Run a local minimization on each, then compare values. With enough points, can make a space. Can use mesh. Can use Monte Carlo – random guess. If there are 100 points and 6 variables, 1006 calculations. Simulated Annealing Can use f(x) ↔ when there are lots of global minimum kTFigure 4. The molecule is heated and then cooled slowly so that conformational changes taking place will lead to a local minimum. This process is repeated many times until several closely related, low energy, conformations are obtained. f(x, z) mixed integer hybrid Genetic Algorithms Î discretize everything “DNA” (z1, z2, z3, …) 10.34, Numerical Methods Applied to Chemical Engineering Lecture 29 Prof. William Green Page 2 of 3 Cite as: William Green, Jr., course materials for 10.34 Numerical Methods Applied to Chemical Engineering, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY].10.34, Numerical Methods Applied to Chemical Engineering Lecture 29 Prof. William Green Page 3 of 3 Cite as: William Green, Jr., course materials for 10.34 Numerical Methods Applied to Chemical Engineering, Fall 2006. MIT OpenCourseWare (http://ocw.mit.edu), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY]. mutate zn Æ zn’ reproduction (exchange of DNA fragments) replication death give everything probabilities to make it mirror evolution Non-determinate methods Î do not exactly know when you are
View Full Document
Unlocking...