Global Optimization With Matlab Products(draft)_mathworks.pdf 55491w

Global Optimization with MATLAB® Products

Manager 이 장 원 차장 Application Engineer 엄준상

© 2011 The MathWorks, Inc.1

Agenda



Introduction to Global Optimization



Survey of Solvers with Examples – – – –

MultiStart Global Search Pattern Search Simulated Annealing

– Genetic Algorithm / Multiobjective Genetic Algorithm 

Peaks

8 6 4 2 0 -2 -4 -6 3

2

2 1

0

0

-1

-2

-3

-2

y

Additional Resources

x

Local minima



Question & Answer

Global minima 2

Optimization – Finding answers to problems automatically Modify Design Parameters

Initial Design Parameters

NO

Model or Prototype

Objectives Achieved?

YES

Optimal Design

OPTIMIZATION PROCESS

Design process can be performed: Manually (trial-and-error or iteratively)

Optimization benefits include: 

Finding better (optimal) designs

Automatically



(using optimization techniques)



Faster design evaluations Useful for trade-off analysis (N dimensions)



Non-intuitive designs may be found

Antenna Design Using Genetic Algorithm http://ic.arc.nasa.gov/projects/esg/research/antenna.htm

3

Example Global Optimization Problems Why does fmincon have a hard time finding the function minimum?

5

5

5

0

0

0

-5

-5

-5

-10

-10 5 10 x Starting at 6

5 10 x Starting at 8

0

10

10

5

5

5

0

0

0

-5

-5

-5

-10 0

5 x

10

Peak VE Value = 0.96144 1

-10 0

10

-10

Why didn’t fminunc find the maximum volumetric efficiency?

Starting at 3 10

0

x sin(x) + x cos(2 x)

Starting at 1 10

5 x

10

0

5 x

0.8

0.8

-10 0

0.9

0.9

5 10 x Starting at 10

10

Why didn’t nonlinear regression find a good fit? c=b1e-b4t+b2e-b5t+b3e-b6t

Manifold Pressure Ratio

x sin(x) + x cos(2 x)

Starting at 0 10

0.7

0.7 0.6

0.6

End

0.5

0.5

0.4

0.4

0.3

Start

0.8

0.3

0.2 0.7

0.2 0.1

0.6

0.1 c

0.5

0 1000

0.4

2000

3000 4000 5000 Revolutions Per Minute, RPM

6000

0.3 0.2 0.1 0

0

20

40

60 t

80

100

120

4

Global Optimization Goal: Want to find the lowest/largest value of the nonlinear function that has many local minima/maxima Problem: Traditional solvers often return one of the local minima (not the global) Solution: A solver that locates globally optimal solutions

Rastrigin’s Function

5

Global Optimization Toolbox – For problems that contain multiple maxima/minima or are non-smooth

Optimization T oolbox Faster/fewer function eval uations Larger problems (higher d imensions) Finds local minima/maxim a

Finds global minima/maxi ma (most of the time) Better on  non-smooth  stochastic  discontinuous  undefined gradients Custom data types (in GA and SA solvers)

Global Optimization Toolbox

  



 

6

MULTISTART

7

What is MultiStart?



Run a local solver from each set of start points



Option to filter starting points based feasibility



s parallel computing

8

GLOBAL SEARCH

11

What is GlobalSearch?



Multistart heuristic algorithm



Calls fmincon from multiple start points to try and find a global minimum



Filters/removes non-promising start points

12

GlobalSearch Overview Schematic Problem 3

Peaks function Three minima Green, z = -0.065 Red, z= -3.05 Blue, z = -6.55

2

1

y

0

-1

-2

-3 -3

-2

-1

0

1

2

3

x 13

GlobalSearch Overview – Stage 0 Run from specified x0 3

2

1

y

0

-1

-2

-3 -3

-2

-1

0

1

2

3

x 14

GlobalSearch Overview – Stage 1 Generate stage 1 start points via Scatter Search 3

2

6

4

1

y

3

0

0 0

-1

-2 -2

-3 -3

0 -2

-1

0

1

0 2

3

x 15

GlobalSearch Overview – Stage 1 Find stage 1 start point with lowest penalty value 3

2

6

4

1

y

3

0

0 0

-1

-2 -2

-3 -3

0 -2

-1

0

1

0 2

3

x 16

GlobalSearch Overview – Stage 1 Run from best stage 1 point 3

2

1

y

0

-1

-2

-3 -3

-2

-1

0

1

2

3

x 17

GlobalSearch Overview – Stage 2 Generate stage 2 start points using Scatter Search 3

2

1

y

0

-1

-2

-3 -3

-2

-1

0

1

2

3

x 18

GlobalSearch Overview – Stage 2 Analyse each stage 2 point in turn. 3

2

1

y

0

-1

-2

-3 -3

-2

-1

0

1

2

3

x 19

GlobalSearch Overview – Stage 2 Don’t run points that are in basins of existing minimum 3

2

1

y

0

-1

-2

-3 -3

-2

-1

0

1

2

3

x 20

GlobalSearch Overview – Stage 2 Analyse each stage 2 point in turn. 3

2

1

y

0

-1

-2

-3 -3

-2

-1

0

1

2

3

x 21

GlobalSearch Overview – Stage 2 Don’t run points whose penalty value exceeds threshold 3

Current penalty threshold value : 4

6

2

1

y

0

-1

-2

-3 -3

-2

-1

0

1

2

3

x 22

GlobalSearch Overview – Stage 2 Analyse each stage 2 point in turn 3

2

1

y

0

-1

-2

-3 -3

-2

-1

0

1

2

3

x 23

GlobalSearch Overview – Stage 2 Run start point if it satisfies distance & merit criteria 3

Current penalty threshold value : 4

2

1

y

0

-1

-2

-3 -3

-3

-2

-1

0

1

2

3

x 24

GlobalSearch Overview – Stage 2 Expand basin of attraction if minimum already found 3

Current penalty threshold value : 2 2

1

y

0

Basins can overlap

-1

-2

-0.1 -3 -3

-2

-1

0

1

2

3

x 25

SIMULATED ANNEALING

28

What is Simulated Annealing?



A probabilistic metaheuristic approach based upon the physical process of annealing in metallurgy.



Controlled cooling of a metal allows atoms to realign from a random higher energy state to an ordered crystalline (globally) lower energy state



By analogy, simulated annealing replaces a current solution by randomly choosing a nearby solution



A “nearby” solution is determined by the solution temperature 29

Simulated Annealing Overview – Iteration 1 Run from specified x0

3

2

1

y

0

0.9 -1

-2

-3 -3

-2

-1

0

1

2

3

x 30

Simulated Annealing Overview – Iteration 1 Randomly generate a new point according to probability distribution and current temperature 3

Temperature = 1 2

1

y

3

0

0.9 Possible New Points: Standard Normal N(0,1) * Temperature

-1

-2

-3 -3

-2

-1

0

1

2

3

x 31

Simulated Annealing Overview – Iteration 1 If lower, accept the point, if higher, accept based upon acceptance probability 3

Temperature = 1 2

Paccept  1

y

1 1 e

( 30.9 ) / T

 0.11

3

0

0.9 -1

-2

-3 -3

-2

-1

0

1

2

3

x 32

Simulated Annealing Overview – Iteration 1 Randomly generate a new point according to probability distribution and current temperature 3

Temperature = 1 2

1

y

3

0

0.9 -1

0.3 -2

-3 -3

-2

-1

0

1

2

3

x 33

Simulated Annealing Overview – Iteration 1 Randomly generate a new point according to probability distribution and current temperature, accept new point if lower value 3

Temperature = 1 2

1

y

3

0

0.9 -1

0.3 -2

-3 -3

-2

-1

0

1

2

3

x 34

Simulated Annealing Overview – Iteration 2 Lower temperature according to temperature schedule 3

Temperature = 1 2

1

y

3

0

0.9 -1

0.3 -2

-3 -3

-2

-1

0

1

2

3

x 35

Simulated Annealing Overview – Iteration 2 Lower temperature according to temperature schedule and generate new point 3

Temperature = 0.75 2

1

y

3

0

0.9

-1.2 -1

0.3 -2

-3 -3

-2

-1

0

1

2

3

x 36

Simulated Annealing Overview – Iteration N-1 After several iterations, the search radius becomes small and we narrow in on a local solution 3

Temperature = 0.1 2

1

3 -3

y

0

0.9

-1.2 -1

0.3 -2

-3 -3

-2

-1

0

1

2

3

x 37

Simulated Annealing Overview – Iteration N Reset temperature and start the process again (reanneling) 3

Temperature = 1 2

1

3 -3

y

-2

0

-1.2

0.9

-1

0.3 -2

-3 -3

-2

-1

0

1

2

3

x 38

Simulated Annealing Overview – Iteration N Reset temperature and start the process again (reannealing) 3

Temperature = 1 2

1

3 -3

y

-2

0

-1.2

Paccept 

1

0.9

1  e( 2( 3)) / T

 0.27

-1

0.3 -2

-3 -3

-2

-1

0

1

2

3

x 39

Simulated Annealing Overview – Iteration N Reset temperature and start the process again (reannealing) 3

Temperature = 1 2

1

3 -3

y

-2

0

-1.2

0.9

-1

0.3 -2

-3 -3

-2

-1

0

1

2

3

x 40

Simulated Annealing Overview – Iteration N+1 Reduce temperature and continue… 3

Temperature = 0.75 2

1

3 -3

y

-2

0

-1.2 -1

0.3

0.9 -3

-2

-3 -3

-2

-1

0

1

2

3

x 41

Simulated Annealing Overview – Iteration N+1 Reduce temperature and continue… 3

Temperature = 0.75 2

1

3 -3

y

-2

0

-1.2 -1

0.3

0.9 -3

-2

-3 -3

-2

-1

0

1

2

3

x 42

Simulated Annealing Overview – Iteration … Reduce temperature and continue… 3

Temperature = 0.75 2

1

3 -3

y

-2

0

-1.2 -1

0.3

0.9 -3 -6.5

-2

-3 -3

-2

-1

0

1

2

3

x 43

PATTERN SEARCH (DIRECT SEARCH)

47

What is a Pattern Search? 

An approach that uses a pattern of search directions around the existing points, the mesh



Polls the mesh for a better solution and moves to that point



Expands/contracts the mesh around the current point when a solution is not found



Does not rely on gradient information

48

Pattern Search Overview – Iteration 1 Run from specified x0 3

2

1

3

y

0

-1

-2

-3 -3

-2

-1

0

1

2

3

x 49

Pattern Search Overview – Iteration 1 Apply pattern vector, poll new points for improvement 3

Mesh size = 1 Pattern vectors = [1,0], [0,1], [-1,0], [-1,-1] 2

4.6 Pnew  mesh _ size * pattern _ vector  x0

First poll successful 1

3

2.8

y

1.6  1*[1,0]  x0

0

0.4 Complete Poll (not default)

-1

-2

-3 -3

-2

-1

0

1

2

3

x 50

Pattern Search Overview – Iteration 2 Increase mesh size and repeat… 3

Mesh size = 2 Pattern vectors = [1,0], [0,1], [-1,0], [-1,-1] 2

4.6

1

3

2.8

y

1.6

0

0.4

-2.8

0.3

-1

-2

-4 Complete Poll -3 -3

-2

-1

0

1

2

3

x 51

Pattern Search Overview – Iteration 3 Mesh expansion: increase mesh size and repeat… 3

Mesh size = 4 Pattern vectors = [1,0], [0,1], [-1,0], [-1,-1] 2

4.6

1

3

2.8

y

1.6

0

0.4

-2.8

0.3

-1

-2

-4 -3 -3

-2

-1

0

1

2

3

x 52

Pattern Search Overview – Iteration 4 Refine mesh: decrease mesh size and repeat… 3

Mesh size = 4*0.5 = 2 Pattern vectors = [1,0], [0,1], [-1,0], [-1,-1] 2

4.6

1

3

2.8

y

1.6

0

0.4

-2.8

0.3

-1

-2

-4 -3 -3

-2

-1

0

1

2

3

x 53

Pattern Search Overview – Iteration N Continue expansion/contraction until convergence… 3

4.6

2

1

3

2.8

y

1.6

0

0.4

-2.8

0.3

-1

-6.5 -2

-4 -3 -3

-2

-1

0

1

2

3

x 54

GENETIC ALGORITHM

57

What is a Genetic Algorithm? 

Genetic Algorithms use concepts from evolutionary biology to find exact or approximate solutions to optimization problems



Start with an initial generation of candidate solutions that are tested against the objective function



Subsequent generations evolve from the 1st through selection, crossover and mutation



The individual that best minimizes the given objective is returned as the ideal solution

58

How Evolution Works – Binary Case 

Selection – Retain the best performing bit strings from one generation to the next. Favor these for reproduction – parent1 = [ 1 0 1 0 0 1 1 0 0 0 ] – parent2



Crossover – parent1 – parent2 – child



= [1 0 0 1 0 0 1 0 1 0]

= [1 0 1 0 0 1 1 0 0 0] = [1 0 0 1 0 0 1 0 1 0] = [1 0 0 0 0 1 1 0 1 0]

Mutation – parent – child

= [1 0 1 0 0 1 1 0 0 0] = [0 1 0 1 0 1 0 0 0 1] 59

Genetic Algorithm – Iteration 1 Evaluate initial population 3

2

1

y

0

-1

-2

-3 -3

-2

-1

0

1

2

3

x 60

Genetic Algorithm – Iteration 1 Select a few good solutions for reproduction 3

2

1

y

0

-1

-2

-3 -3

-2

-1

0

1

2

3

x 61

Genetic Algorithm – Iteration 2 Generate new population and evaluate 3

2

1

y

0

-1

-2

-3 -3

-2

-1

0

1

2

3

x 62

Genetic Algorithm – Iteration 2 Select a few good solutions for reproduction 3

2

1

y

0

-1

-2

-3 -3

-2

-1

0

1

2

3

x 63

Genetic Algorithm – Iteration 3 Generate new population and evaluate 3

2

1

y

0

-1

-2

-3 -3

-2

-1

0

1

2

3

x 64

Genetic Algorithm – Iteration 3 Select a few good solutions for reproduction 3

2

1

y

0

-1

-2

-3 -3

-2

-1

0

1

2

3

x 65

Genetic Algorithm – Iteration N Continue process until stopping criteria are met 3

2

1

y

0

Solution found

-1

-2

-3 -3

-2

-1

0

1

2

3

x 66

Comparison of Solver (Default) Performance rf([x,y])

6 FuncValue Min StartPt

4

y

2

0

-2

-4

-6 -6

-4

-2

0 x rf([x,y])

2

4

6

0 x

20

40

60

60 FuncValue Min StartPt

40

y

20

0

-20

-40

-60 -60

-40

-20

rf([x,y]) FuncValue Min StartPt

60

40

y

20

0

-20

-40 -40

-20

0

20 x

40

60

69

70

Additional Resources

Webinars  Speeding Up Optimization with Parallel Computing (August 2010) On-demand Webinars  Genetic Algorithm in Financial Applications  Tips & Tricks: Getting Started with Optimization  Introduction to Optimization

71

Information

North America – Phone: 508-647-7000 – E-mail: [email protected]

Outside North America – your local MathWorks office or reseller: www.mathworks.com/

72

Questions?

73

MATLAB Provides the Foundation for Optimization

The leading environment for technical computing – – – –

Customizable Numeric computation Data analysis and visualization The de facto industry-standard, high-level programming language for algorithm development – Toolboxes for statistics, optimization, symbolic math, signal and image processing, and other areas – Foundation of the MathWorks product family

74

Optimization Toolbox Solve standard and large-scale optimization problems

Graphical interface and command line functions for:     

Linear and nonlinear programming Quadratic programming Nonlinear least squares and nonlinear equations Multi-objective optimization Binary integer programming

Additional Capabilities:  Parallel computing in selected solvers  Customizable algorithm options  Choose between standard and largescale algorithms  Output diagnostics

75

Global Optimization Toolbox Solve multiple maxima, multiple minima, and nonsmooth optimization problems

Graphical interface and command line functions for:   

 

Global Search solver Multistart solver Genetic algorithm solver – Single objective – Multiobjective with Pareto front Direct search solver Simulated annealing solver

Useful for problems not easily addressed with Optimization Toolbox:      

Discontinuous Highly nonlinear Stochastic Discrete or custom data types Undefined derivatives Multiple maxima/minima 76

Anatomy of an Optimization Problem

General Form Accepted by MATLAB Solvers Objective Function

Typically a linear or nonlinear function

min f ( x) x

Decision variables

Subject to Constraints (i.e. such that)

Ax  b,

c( x)  0

Aeq x  beq , ceq ( x)  0 Linear constraints l • inequalities • equalities • bounds

 xu

Nonlinear constraints • inequalities • equalities

77

MATLAB Optimization Products and Example Applications MATLAB Solving Equations

Statistics Toolbox Curve Fitting Toolbox

Real roots finding (1D):

Optimization Toolbox

Genetic Algorithm and Direct Search Toolbox

Real roots finding (N-D):

Noisy, discontinuous root finding (N-D)

Nonlinear Systems F(X) = 0

Noisy, discontinuous systems: F(X) = 0

Model Fitting (least squares) Constrained curve fitting

Noisy, Discontinuous parameter estimation

x 3-2 x-5 100 50

 f(x) = 0

0

 Root finding

-50

 Systems of equations

-100

-6

-4

-2

0 x

2

4

6

Linear Systems: F(x) = 0 Ax-b = 0 (i.e. Ax=b) >> x = A \ b

Curve/Modeling Fitting

Basic (linear) curve fitting 0.9 0.8

 curve fitting  parameter estimation

(model fitting)

Trade-Off Studies  Maximization

Advanced (nonlinear) curve fitting

Parameter Estimation

0.7 0.6 0.5

0

0.5

1

1.5

2

2.5

Unconstrained nonlinear minimization

Constrained nonlinear minimization

Noisy, Discontinuous, illdefined mimization

 Minimization  Goal seeking  Multiobjective

78