Solving Optimization Problems With MATLAB

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) ntRandom 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

Simulated Annealing Overview – Iteration N 13Temperature 0.75213-3y-20-1.2-10.30.9-3-2-3-3-2-10123x97

Simulated Annealing Overview – Iteration N 13Temperature 0.75213-3y-20-1.2-10.30.9-3-2-3-3-2-10123x98

Simulated Annealing Overview – Iteration 3Temperature 0.75213-3y-20-1.2-10.30.9-3-6.5-2-3-3-2-10123x99

Simulated Annealing – Peaks Function100

Global Optimization Toolbox Solvers GlobalSearch, MultiStart– Well suited for smooth objective and constraints– Relies on gradient calculations– Return the location of local and global minima ga, simulannealbnd, particleswarm– Many function evaluations to sample the search space– Work on both smooth and nonsmooth problems patternsearch, surrogateopt– Fewer function evaluations than ga, simulannealbnd, particlewarm– Work on both smooth and nonsmooth problems101

Optimization Toolbox Solvers fmincon, fminbnd, fminunc, fgoalattain, fminimax– Nonlinear constraints and objectives– Gradient-based methods for smooth objectives and constraints quadprog, linprog– Linear constraints and quadratic or linear objective, respectively intlinprog– Linear constraints and objective and integer variables lsqlin, lsqnonneg– Constrained linear least squares lsqnonlin, lsqcurvefit– Nonlinear least squares fsolve– Nonlinear equations102

Speeding-up with Parallel Computing Global Optimization Toolbox– patternsearch, surrogateopt, ga,gamultiobj, particleswarm: Pointsevaluated in parallel at each iteration– MultiStart: Start points evaluated in parallel Optimization Toolbox– fmincon, fminunc, fminimax,fgoalattain, fsolve, lsqcurvefit,lsqnonlin: Parallel evaluation of objective functionfor finite differences Parallel Computing can also be used in theObjective Function– parfor103

Parallel Computing Toolbox for the DesktopDesktop ComputerLocal Speed up parallel applications Take advantage of GPUs Prototype code for your clusterSimulink, Blocksets,and Other ToolboxesMATLAB104

Scale Up to Clusters and CloudsDesktop ComputerComputer ClusterLocalCluster Simulink, Blocksets,and Other ToolboxesSchedulerMATLAB105

Learn More about Optimization with MATLABRecorded webinar: Linear and MixedInteger Linear Programming in MATLABMATLAB Digest: Using SymbolicGradients for OptimizationRecorded webinar: Optimization inMATLAB for Financial ApplicationsRecorded webinar: Optimization inMATLAB: An Introduction to QuadraticProgrammingCash Flow Matching Example3000MATLAB Digest: ImprovingOptimization Performance with ParallelComputingOptimization Toolbox Web demo:Finding an Optimal Path using MATLABand Optimization Toolbox# Purchased2500200015001000500012345Bonds106

Key Takeaways Solve a wide variety of optimization problems in MATLAB– Linear and Nonlinear– Continuous and mixed-integer– Smooth and Nonsmooth Find better solutions to multiple minima and non-smooth problems using globaloptimization Use symbolic math for setting up problems and automatically calculating gradients Using parallel computing to speed up optimization problems107