Solving Optimization Problems with MATLAB

1 1 2018 The MathWorks, Optimization Problems with MATLAB2 Introduction Least-squares minimization Nonlinear Optimization Mixed-integer programming Global optimizationTopics3 Optimization ProblemsMinimize RiskMaximize ProfitsMaximize Fuel Efficiency4 Design ProcessInitial Design VariablesSystemModify Design VariablesOptimal DesignObjectivesmet?NoYes5 Manually (trial-and-error or iteratively)Why use Optimization ?Initial Guess6 Automatically (using optimizationtechniques)Initial GuessWhy use Optimization ?7 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 Introduction Least-squares minimization Nonlinear Optimization Mixed-integer programming Global optimizationTopics9 Curve Fitting DemoGiven some data:Fit a curve of the form:teccty 21)(t = [0.]

2 3 .8 ];y = [.82 .72 .63 .60 .55 .50];10 How to solve? Eccceyecctytt 21211)(As a linear system of equations:22minyEcEcyc Can t solve this exactly (6 eqns, 2 unknowns)An Optimization problem ! Introduction Least-squares minimization Nonlinear Optimization Mixed-integer programming Global optimizationTopics12 Nonlinear Optimizationmin log1+ 1 432+3 1+ 2 13213 Nonlinear Optimization -Modeling Gantry Crane Determine acceleration profile that minimizes payload swings25s4s20s1s20s1:sConstraint2121 fppppftttttt14 Symbolic Math Toolbox Perform exact computations using familiar MATLAB syntax in MATLAB Integration Differentiation Equation Solving Transformations Simplification Unit conversion Variable precision arithmetic Results in typeset math in Live Editor Integrates with MATLAB , Simulink, Simscape15 Introduction Least-squares minimization Nonlinear Optimization Mixed-integer programming Global optimizationTopics16 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.

3 On/off Buy/don t buy Mixed-integer linear programming: Solve Optimization problem while enforcing that certain variables need to be integer17 Continuous and integer variables 1 0,100 2 {1,2,3,4,5}Linear objective and constraintsmin 1 2 2 1+4 2 20 1+ 2=10such thatMixed-Integer Linear Programming18 Optimize Gift Card SpendingProblem: Given gift cards to different stores and a shopping list of desired purchases, decide how to spend the gift cards to use as much of the gift card money as : You cannot overspend the gift card. You can purchase one of any item, and must purchase one of a specific Salesman ProblemProblem How to find the shortest path through a series of points?

4 Solution Calculate distances between all combinations of points Solve an Optimization problem where variables correspond to trips between two points111011000020 Introduction Least-squares minimization Nonlinear Optimization Mixed-integer programming Global optimizationTopics21 Example Global Optimization ProblemsWhy does fminconhave a hard time finding the function minimum?0510-10-50510xStarting at 100510-10-50510xStarting at 80510-10-50510xStarting at 6x sin(x) + x cos(2 x)0510-10-50510xStarting at 30510-10-50510xStarting at 10510-10-50510xStarting at 0x sin(x) + x cos(2 x)22 Initial GuessExample Global Optimization ProblemsWhy didn t fminuncfind the maximum efficiency?

5 23 Example Global Optimization ProblemsWhy didn t nonlinear regression find a good fit? +b2e-b5t+b3e-b6t24 Global OptimizationGoal:Want to find the lowest/largest value of the nonlinear function that has many local minima/maximaProblem:Traditional solvers often return one of the local minima (not the global)Solution:A solver that locates globally optimal solutionsGlobal Minimum at [0 0]Rastrigin s Function25 Global Optimization Solvers Covered Today Multi Start and Global Search Pattern Search Genetic Algorithm Surrogate Optimization Particle Swarm Simulated Annealing26 MultiStart Demo Nonlinear Regressionlsqcurvefit solutionMultiStart solution27 MULTISTART28 What is MultiStart?

6 Run a local solver from each set of start points Option to filter starting points based on feasibility Supports parallel computing29 MultiStart Demo Peaks Function30 GLOBAL SEARCH31 What is GlobalSearch? Multistartheuristic algorithm Calls fminconfrom multiple start points to try and find a global minimum Filters/removes non-promising start points32-3-2-10123-3-2-10123 GlobalSearch Overview Schematic ProblemPeaks function Three minimaGreen, z = , z= , z = Overview Stage 0 Run from specified x0xy34-3-2-10123-3-2-10123 GlobalSearch Overview Stage 13600040-2xy35-3-2-10123-3-2-10123 GlobalSearch Overview Stage 13600040-2xy36-3-2-10123-3-2-10123 GlobalSearch Overview Stage 1xy37-3-2-10123-3-2-10123 GlobalSearch Overview Stage 2xy38-3-2-10123-3-2-10123 GlobalSearch Overview Stage 2xy39-3-2-10123-3-2-10123 GlobalSearch Overview Stage 2xy40-3-2-10123-3-2-10123 GlobalSearch Overview Stage 2xy41-3-2-10123-3-2-10123 GlobalSearch Overview Stage 26 Current penalty threshold value.

7 4xy42-3-2-10123-3-2-10123 GlobalSearch Overview Stage 2xy43-3-2-10123-3-2-10123 GlobalSearch Overview Stage 2 Current penalty threshold value : 4-3xy44-3-2-10123-3-2-10123 GlobalSearch Overview Stage 2 Expand basin of attraction if minimum already foundCurrent penalty threshold value : can overlap45 GlobalSearch Demo Peaks Function46 PATTERN SEARCH(DIRECT SEARCH)47 What is Pattern Search? An approach that uses a pattern of search directions around the existing points Expands/contracts around the current point when a solution is not found Does not rely on gradients: works on smooth and nonsmoothproblems48-3-2-10123-3-2-10123 Pattern Search Overview Iteration 1 Run from specified x0xy349-3-2-10123-3-2-10123 Pattern Search Overview Iteration 1 Apply pattern vector, poll new points for improvementxy3 Mesh size = 1 Pattern vectors = [1,0], [0,1], [-1,0], [0,-1] 0_*_xvectorpatternsizemeshPnew 0]0,1[*1x poll successfulComplete Poll (not default)

8 50-3-2-10123-3-2-10123 Pattern Search Overview Iteration 2xy3 Mesh size = 2 Pattern vectors = [1,0], [0,1], [-1,0], [0,-1] Poll51-3-2-10123-3-2-10123 Pattern Search Overview Iteration 3xy3 Mesh size = 4 Pattern vectors = [1,0], [0,1], [-1,0], [0,-1] Search Overview Iteration 4xy3 Mesh size = 4* = 2 Pattern vectors = [1,0], [0,1], [-1,0], [0,-1] Search Overview Iteration NContinue expansion/contraction until Search Peaks Function55 Pattern Search Climbs Mount Washington56 GENETIC ALGORITHM57 What is a Genetic Algorithm? Uses concepts from evolutionary biology Start with an initial generation of candidate solutions that are tested against the objective function Subsequent generations evolve from the 1stthrough selection, crossoverand mutation58 How Evolution Works Binary Case Selection Retainthe best performing bit strings from one generation to the next.

9 Favor these for reproduction parent1 = [ 1 0 1 0 0 1 1 0 0 0 ] parent2 = [ 1 0 0 1 0 0 1 0 1 0 ] Crossover parent1 = [ 101 0 01 100 0] parent2 = [ 100 1 00 101 0] child= [ 100 0 01 101 0 ] Mutation parent = [ 10 10 0 110 0 0 ] child = [ 0 10 10 10 0 0 1] 59-3-2-10123-3-2-10123 Genetic Algorithm Iteration 1 Evaluate initial populationxy60-3-2-10123-3-2-10123 Genetic Algorithm Iteration 1 Select a few good solutions for reproductionxy61-3-2-10123-3-2-10123 Genetic Algorithm Iteration 2 Generate new population and evaluatexy62-3-2-10123-3-2-10123 Genetic Algorithm Iteration 2xy63-3-2-10123-3-2-10123 Genetic Algorithm Iteration 3xy64-3-2-10123-3-2-10123 Genetic Algorithm Iteration 3xy65-3-2-10123-3-2-10123 Genetic Algorithm Iteration NContinue process until stopping criteria are metxySolution found66 Genetic Algorithm Peaks Function67 Genetic Algorithm Integer ConstraintsMixed

10 Integer xare integersExamples Only certain sizes of components available Can only purchase whole shares of stock)(minxfx68 Application: Circuit Component Selection 6 components to size Only certain sizes available Objective: Match Voltage vs. Temperature curveThermistor Circuit300 330 360 ..180k 200k 220k Thermistors: Resistance varies nonlinearly with temperature? = , 69 SURROGATE OPTIMIZATION70 What is Surrogate Optimization ? An approach that creates and optimizes a surrogate of the function Searches randomly to explore and adaptively to refine Does not rely on gradients: works on smooth and nonsmoothproblems71-3-2-10123-3-2-10123 Surrogate Optimization OverviewConstruction phase evaluate at random points to construct surrogatexyRandom pointsIncumbent72-3-2-10123-3-2-10123 Surrogate Optimization OverviewSearch phase minimize merit function of surrogate and point spreadxyRandom pointsAdaptive pointsIncumbent73-3-2-10123-3-2-10123 Surrogate Optimization OverviewReset Repeat construction and search phasesxyRandom pointsAdaptive pointsIncumbent74-3-2-10123-3-2-10123 Surrogate Optimization OverviewContinue process until stopping criteria are metxyRandom pointsAdaptive pointsSolution foundIncumbent75