WIXLIB

Solving Optimization Problems with MATLAB 2018 The MathWorks, Inc.1

Topics Introduction Least-squares minimization Nonlinear optimization Mixed-integer programming Global optimization2

Optimization ProblemsMaximize Fuel EfficiencyMinimize RiskMaximize Profits3

Design esSystemObjectivesmet?YesOptimalDesign4

Why use Optimization?Manually (trial-and-error or iteratively)InitialGuess5

Why use Optimization?Automatically (using optimization techniques)InitialGuess6

Why use Optimization? Finding better (optimal) designs and decisions Faster design and decision evaluations Automate routine decisions Useful for trade-off analysis Non-intuitive designs may be foundAntenna Design Using Genetic rch/antenna.htm7

Topics Introduction Least-squares minimization Nonlinear optimization Mixed-integer programming Global optimization8

Curve Fitting DemoGiven some data:t [0 .3 .8 1.1 1.6 2.3];y [.82 .72 .63 .60 .55 .50];Fit a curve of the form:y (t ) c1 c2 e t9

How to solve?As a linear system of equations:y (t ) c1 c2e t c1 y 1 e Ec c2 tCan’t solve this exactly(6 eqns, 2 unknowns)y Ec 0.82 1 0.72 1 0.63 1 0.60 1 0.55 1 0.50 1e 0 e 0 .3 e 0 .8 e 1.1 e 1.6 2 .3e min Ec yc c1 c 2 22An optimization problem!10

Topics Introduction Least-squares minimization Nonlinear optimization Mixed-integer programming Global optimization11

Nonlinear Optimization4min log 1 𝑥1 𝑥32 3 𝑥1 𝑥2 𝑥1 3212

Nonlinear Optimization - Modeling Gantry Crane Determine acceleration profile thatminimizes payload swingConstraints : t f t p1 t p 2 1s t p1 20 s 1s t p 2 20 s 4 s t f 25 s13

Symbolic Math Toolbox Perform exact computations using familiarMATLAB syntax in MATLAB––––––– IntegrationDifferentiationEquation solvingTransformationsSimplificationUnit conversionVariable precision arithmeticResults in typeset math in Live EditorIntegrates with MATLAB, Simulink, Simscape14

Topics Introduction Least-squares minimization Nonlinear optimization Mixed-integer programming Global optimization15

Mixed-Integer Programming Many things exist in discrete amounts:– Shares of stock– Number of cars a factory produces– Number of cows on a farm Often have binary decisions:– On/off– Buy/don’t buy Mixed-integer linear programming:– Solve optimization problem while enforcing that certain variables need to be integer16

Mixed-Integer Linear ProgrammingContinuous and integer variables𝑥1 0, 100𝑥2 {1,2,3,4,5}Linear objective and constraintsmin 𝑥1 2𝑥2𝑥such that𝑥1 4𝑥2 20ቊ𝑥1 𝑥2 1017

Optimize Gift Card SpendingProblem: Given gift cards to different stores and a shopping list of desired purchases, decide how tospend the gift cards to use as much of the gift card money as possible.Constraints: You cannot overspend the gift card.You can purchase one of any item, and must purchase one of a specific item.18

Traveling Salesman ProblemProblem How to find the shortest path through a series of points?Solution Calculate distances between all combinations of pointsSolve an optimization problem where variables correspond to trips between two points101000111019

Topics Introduction Least-squares minimization Nonlinear optimization Mixed-integer programming Global optimization20

Example Global Optimization ProblemsWhy does fmincon have a hard time finding thefunction minimum?x sin(x) x cos(2 x)Starting at 0Starting at 3101010555000-5-5-5-10-10-100x sin(x) x cos(2 x)Starting at 1510xStarting at 60510xStarting at 80101010555000-5-5-5-10-1005x10510xStarting at 10-1005x1005x1021

Example Global Optimization ProblemsWhy didn’t fminunc find the maximum efficiency?InitialGuess22

Example Global Optimization ProblemsWhy didn’t nonlinear regression find a good fit?c b1e-b4t b2e-b5t 3

Global OptimizationGoal:Want to find the lowest/largest value ofthe nonlinear function that has many localminima/maximaGlobal Minimum at [0 0]Problem:Traditional solvers often return one of thelocal minima (not the global)Solution:A solver that locates globally optimalsolutionsRastrigin’s Function24

Global Optimization Solvers Covered Today Multi Start and Global Search Pattern Search Genetic Algorithm Surrogate Optimization Particle Swarm Simulated Annealing25

MultiStart Demo – Nonlinear Regressionlsqcurvefit solutionMultiStart solution26

MULTISTART27

What is MultiStart? Run a local solver from each setof start points Option to filter starting pointsbased on feasibility Supports parallel computing28

MultiStart Demo – Peaks Function29

GLOBAL SEARCH30

What is GlobalSearch? Multistart heuristic algorithm Calls fmincon from multiplestart points to try and find aglobal minimum Filters/removes non-promisingstart points31

GlobalSearch OverviewSchematic Problem3Peaks functionThree minimaGreen, z -0.065Red, z -3.05Blue, z -6.5521y0-1-2-3-3-2-10123x32

GlobalSearch Overview – Stage 0Run from specified x0321y0-1-2-3-3-2-10123x33

GlobalSearch Overview – Stage 132641y3000-1-2-2-3-30-2-101023x34

GlobalSearch Overview – Stage 132641y3000-1-2-2-3-30-2-101023x35

GlobalSearch Overview – Stage 1321y0-1-2-3-3-2-10123x36

GlobalSearch Overview – Stage 2321y0-1-2-3-3-2-10123x37

GlobalSearch Overview – Stage 2321y0-1-2-3-3-2-10123x38

GlobalSearch Overview – Stage 2321y0-1-2-3-3-2-10123x39

GlobalSearch Overview – Stage 2321y0-1-2-3-3-2-10123x40

GlobalSearch Overview – Stage 23Current penaltythreshold value : 4621y0-1-2-3-3-2-10123x41

GlobalSearch Overview – Stage 2321y0-1-2-3-3-2-10123x42

GlobalSearch Overview – Stage 23Current penaltythreshold value : 421y0-1-2-3-3-3-2-10123x43

GlobalSearch Overview – Stage 2Expand basin of attraction if minimum already found3Current penalty threshold value : 221y0Basins can overlap-1-2-0.1-3-3-2-10123x44

GlobalSearch Demo – Peaks Function45

PATTERN SEARCH(DIRECT SEARCH)46

What is Pattern Search? An approach that uses a patternof search directions around theexisting points Expands/contracts around thecurrent point when a solution isnot found Does not rely on gradients: workson smooth and nonsmoothproblems47

Pattern Search Overview – Iteration 1Run from specified x03213y0-1-2-3-3-2-10123x48

Pattern Search Overview – Iteration 1Apply pattern vector, poll new points for improvement3Mesh size 1Pattern vectors [1,0], [0,1], [-1,0], [0,-1]24.6Pnew mesh size * pattern vector x0First poll successful132.8y1.6 1*[1,0] x000.4Complete Poll (not default)-1-2-3-3-2-10123x49

Pattern Search Overview – Iteration 23Mesh size 2Pattern vectors [1,0], [0,1], [-1,0], [0,-1]24.6132.8y1.600.4-2.80.3-1-2-4Complete Poll-3-3-2-10123x50

Pattern Search Overview – Iteration 33Mesh size 4Pattern vectors [1,0], [0,1], [-1,0], 1

Pattern Search Overview – Iteration 43Mesh size 4*0.5 2Pattern vectors [1,0], [0,1], [-1,0], 2

Pattern Search Overview – Iteration NContinue expansion/contraction until convergence 34.62132.8y1.600.4-2.80.3-1-6.5-2-4-3-3-2-10123x53

Pattern Search – Peaks Function54

Pattern Search Climbs Mount Washington55

GENETIC ALGORITHM56

What is a Genetic Algorithm? Uses concepts from evolutionarybiology Start with an initial generation ofcandidate solutions that are testedagainst the objective function Subsequent generations evolvefrom the 1st through selection,crossover and mutation57

How Evolution Works – Binary Case Selection– Retain the best performing bit strings from one generation to the next. Favor these forreproduction– parent1 [ 1 0 1 0 0 1 1 0 0 0 ]– parent2 [ 1 0 0 1 0 0 1 0 1 0 ] Crossover– parent1– parent2– child [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]58

Genetic Algorithm – Iteration 1Evaluate initial population321y0-1-2-3-3-2-10123x59

Genetic Algorithm – Iteration 1Select a few good solutions for reproduction321y0-1-2-3-3-2-10123x60

Genetic Algorithm – Iteration 2Generate new population and evaluate321y0-1-2-3-3-2-10123x61

Genetic Algorithm – Iteration 2321y0-1-2-3-3-2-10123x62

Genetic Algorithm – Iteration 3321y0-1-2-3-3-2-10123x63

Genetic Algorithm – Iteration 3321y0-1-2-3-3-2-10123x64

Genetic Algorithm – Iteration NContinue process until stopping criteria are met321y0Solution found-1-2-3-3-2-10123x65

Genetic Algorithm – Peaks Function66

Genetic Algorithm – Integer ConstraintsMixed Integer Optimizationmin f ( x)xs.t. some x are integersExamples Only certain sizes of componentsavailable Can only purchase whole shares of stock67

Application: Circuit Component Selection300 Ω 6 components to sizeThermistor Circuit330 Ω360 Ω? Only certain sizes available180k Ω200k Ω220k Ω Objective:– Match Voltage vs. TemperaturecurveThermistors:Resistance variesnonlinearly withtemperature𝑅𝑇𝐻 𝑅𝑇𝐻,𝑁𝑜𝑚𝑒𝑇 𝑇𝛽 𝑇 𝑇 𝑁𝑜𝑚𝑁𝑜𝑚68

SURROGATE OPTIMIZATION69

What is Surrogate Optimization? An approach that creates andoptimizes a surrogate of thefunction Searches randomly to exploreand adaptively to refine Does not rely on gradients: workson smooth and nonsmoothproblems70

Surrogate Optimization OverviewConstruction phase – evaluate at random points to construct surrogate32IncumbentRandom points1y0-1-2-3-3-2-10123x71

Surrogate Optimization OverviewSearch phase – minimize merit function of surrogate and point spread32IncumbentRandom pointsAdaptive points1y0-1-2-3-3-2-10123x72

Surrogate Optimization OverviewReset – Repeat construction and search phases32IncumbentRandom pointsAdaptive points1y0-1-2-3-3-2-10123x73

Surrogate Optimization OverviewContinue process until stopping criteria are met32IncumbentRandom pointsAdaptive points1y0Solution found-1-2-3-3-2-10123x74

Surrogateopt Demo – Peaks Function75

PARTICLE SWARM76

What is Particle Swarm Optimization? A collection of particles movethroughout the region Particles have velocity and areaffected by the other particles inthe swarm Does not rely on gradients: workson smooth and nonsmoothproblems77

Particle Swarm Overview – Iteration 1Initialize particle locations and velocities, evaluate all locations321y0-1-2-3-3-2-10123x78

Particle Swarm Overview – Iteration NUpdate velocities for each particle32Best Locationfor this Particle1y0PreviousVelocity-1Best Location forNeighbor Particles-2-3-3-2-10123x79

Particle Swarm Overview – Iteration NUpdate velocities for each particle321y0NewVelocity-1-2-3-3-2-10123x80

Particle Swarm Overview – Iteration NMove particles based on new velocities321y0-1-2-3-3-2-10123x81

Particle Swarm Overview – Iteration NContinue swarming until convergence321y0-1-2-3-3-2-10123x82

Particle Swarm – Peaks Function83

SIMULATED ANNEALING84

What is Simulated Annealing? A probabilistic metaheuristicapproach based upon the physicalprocess of annealing inmetallurgy. Controlled cooling of a metalallows atoms to realign from arandom higher energy state to anordered crystalline (globally) lowerenergy state85

Simulated Annealing Overview – Iteration 1Run from specified x0321y00.9-1-2-3-3-2-10123x86

Simulated Annealing Overview – Iteration 13Temperature 121y300.9Possible New Points:Standard Normal N(0,1) * Temperature-1-2-3-3-2-10123x87

Simulated Annealing Overview – Iteration 13Temperature 12Paccept 1y11 e( 3 0.9 ) / T 0.11300.9-1-2-3-3-2-10123x88

Simulated Annealing Overview – Iteration 13Temperature 121y300.9-10.3-2-3-3-2-10123x89

Simulated Annealing Overview – Iteration 13Temperature 121y300.9-10.3-2-3-3-2-10123x90

Simulated Annealing Overview – Iteration 23Temperature 121y300.9-10.3-2-3-3-2-10123x91

Simulated Annealing Overview – Iteration 23Temperature 0.7521y300.9-1.2-10.3-2-3-3-2-10123x92

Simulated Annealing Overview – Iteration N-13Temperature 0.1213-3y00.9-1.2-10.3-2-3-3-2-10123x93

Simulated Annealing Overview – Iteration NReannealing3Temperature 1213-3y-20-1.20.9-10.3-2-3-3-2-10123x94

Simulated Annealing Overview – Iteration NReannealing3Temperature 1213-3y-20-1.2Paccept 10.91 e( 2 ( 3)) / T 0.27-10.3-2-3-3-2-10123x95

Simulated Annealing Overview – Iteration NReannealing3Temperature 1213-3y-20-1.20.9-10.3-2-3-3-2-10123x96