Question? Leave a message!




Introduction to Engineering Optimization

Introduction to Engineering Optimization 14
Outline Motivation Example Problem Classi cation Modeling Lecture 1: Introduction to Engineering Optimization Kevin Carlberg Stanford University July 27, 2009 Kevin Carlberg Lecture 1: Introduction to Engineering OptimizationOutline Motivation Example Problem Classi cation Modeling Goals An introduction to mathematical optimization, which is quite useful for many applications spanning a large number of elds Design (automotive, aerospace, biomechanical) Control Signal processing Communications Circuit design Cool and useful applications of the tools learned so far: can we use nite element modeling to design an aircraft or to detect internal damage in a structure Kevin Carlberg Lecture 1: Introduction to Engineering OptimizationOutline Motivation Example Problem Classi cation Modeling References J. Nocedal and S. J. Wright. Numerical Optimization, Springer, 1999. S. Boyd and L. Vadenberghe. Convex Optimization, Cambridge University Press, 2004. P.E. Gill, W. Murray, and M.H. Wright, Practical Optimization, London, Academic Press, 1981. I. Kroo, J. Alonso, D. Rajnarayan, Lecture Notes from AA 222: Introduction to Multidisciplinary Design Optimization, http://adg.stanford.edu/aa222/. Kevin Carlberg Lecture 1: Introduction to Engineering OptimizationOutline Motivation Example Problem Classi cation Modeling Course information Instructor: Kevin Carlberg (carlbergstanford.edu) Lectures: There will be ve lectures covering 1 Introduction to Engineering Optimization 2 Unconstrained Optimization 3 Constrained Optimization 4 Optimization with PDE constraints Assignments: There will be a few minor homework and inclass assignments Kevin Carlberg Lecture 1: Introduction to Engineering OptimizationOutline Motivation Example Problem Classi cation Modeling 1 Motivation 2 Example 3 Problem Classi cation Convex v. nonconvex Continuous v. discrete Constrained v. unconstrained Singleobjective v. multiobjective 4 Modeling Kevin Carlberg Lecture 1: Introduction to Engineering OptimizationOutline Motivation Example Problem Classi cation Modeling Why optimization Mathematical optimization: make something the best it can possibly be. maximize objective by choosing variables subject to constraints Are you optimizing right now objective: learning; variables: actions; constraints: physical limitations Perhaps more realistically, objective: comfort Kevin Carlberg Lecture 1: Introduction to Engineering OptimizationOutline Motivation Example Problem Classi cation Modeling Applications Physics. Nature chooses the state that minimizes an energy functional (variational principle). Transportation problems. Minimize cost by choosing routes to transport goods between warehouses and outlets. Portfolio optimization. Minimize risk by choosing allocation of capital among some assets. Data tting. Choose a model that best ts observed data. Kevin Carlberg Lecture 1: Introduction to Engineering OptimizationOutline Motivation Example Problem Classi cation Modeling Applications with PDE constraints Design optimization Model predictive control Figure from R. Findeisen and F. Allgower, \An Introduction to differ, there is no guarantee that the closedloop system will be stable. It is indeed easy to construct examples for which the closedloop becomes unstable if a (small) finite horizon is chosen. Hence, when using finite horizons in standard NMPC, the stage cost cannot be chosen simply based on the desired physical objectives. Nonlinear Model Predictive Control," 21st Benelux Meeting on Systems and Control, 2002. The overallbasic structure ofa NMPC controlloop isdepicted in Figure 3. As canbe seen, it is necessary to estimate NMPC controller u y dynamic Plant optimizer cost function xˆ + system model state estimator constraints Figure 3: Basic NMPC control loop. Structural damage the system states from the dete output measurements. ction Summarizing the basic NMPC scheme works as follows: 1. obtain measurements/estimates of the states of the system Kevin Carlberg Lecture 1: Introduction to Engineering Optimization 2. compute an optimal input signal byminimizing a givencostfunction overa certainpredictionhorizon in the future using amodelofthesystem 3. implementthe firstpartof theoptimal inputsignal until new measurements/estimates of the state are avail able 4. continue with 1. From the remarks given so far and from the basic NMPC setup, one can extract the following key characteristics of NMPC: NMPC allowsthe use of a nonlinear model for prediction. NMPC allowsthe explicit consideration of state and input constraints. InNMPC a specified performance criteria is minimized online. InNMPC the predicted behavior is in general differentfrom the closed loop behavior. Theonline solution of an openloop optimal control problem is necessary for the application of NMPC. To perform the prediction the system states must be measured or estimated. In the remaining sections various aspects of NMPC regarding these properties will be discussed. The next section focuses on system theoretical aspects of NMPC. Especially the questions on closedloop stability, robustness and the output feedback problem are considered. 2 SystemTheoreticalAspectsofNMPC In this section different system theoretical aspects of NMPC are considered. Besides the question of nominalstability ofthe closedloop, which canbe considered assomehowmature today,remarks on robustNMPC strategiesas well as the outputfeedback problem are given. 5Outline Motivation Example Problem Classi cation Modeling Brachistochrone Problem History One of the rst problems posed in the calculus of variations. Galileo considered the problem in 1638, but his answer was incorrect. Johann Bernoulli posed the problem in 1696 to a group of elite mathematicians: I, Johann Bernoulli... hope to gain the gratitude of the whole scienti c community by placing before the nest mathematicians of our time a problem which will test their methods and the strength of their intellect. If someone communicates to me the solution of the proposed problem, I shall publicly declare him worthy of praise. Newton solved the problem the very next day, but proclaimed \I do not love to be dunned pestered and teased by foreigners about mathematical things." Kevin Carlberg Lecture 1: Introduction to Engineering OptimizationOutline Motivation Example Problem Classi cation Modeling Brachistochrone Problem (homework) Problem: Find the frictionless path that minimizes the time for a particle to slide from rest under the in uence of gravity between two points A and B separated by vertical height h and horizontal length b. 1 2 Conservation of energy: mv + mgh = C 2 R x B Beltrami Identity: for I (y) = f (y(x))dx, the stationary x A   point solution y characterized by I (y ) = 0 satis es 0 f f y = C . 0 y Kevin Carlberg Lecture 1: Introduction to Engineering OptimizationOutline Motivation Example Problem Classi cation Modeling Numerical Solution Although the analytic solution is available, an approximate solution can be computed using numerical optimization techniques. Figure: Evolution of the solution using a gradientbased algorithm Kevin Carlberg Lecture 1: Introduction to Engineering OptimizationOutline Motivation Example Problem Classi cation Modeling Numerical Solution (for di erent h) Kevin Carlberg Lecture 1: Introduction to Engineering OptimizationOutline Convex v. nonconvex Motivation Continuous v. discrete Example Constrained v. unconstrained Problem Classi cation Singleobjective v. multiobjective Modeling Mathematical Optimization Mathematical optimization: the minimization of a function subject to constraints on the variables. \Standard form": minimize f (x) n x2R subject to c (x) = 0; i = 1;:::; n e i d (x) 0; j = 1;:::; n j i n Variables: x2R n Objective function: f :R R n Equality constraint functions: c :R R i n Inequality constraint functions: d :R R j n Feasible set:D =fx2R j c (x) = 0; d (x) 0g i j Di erent optimization algorithms are appropriate for di erent problem types Kevin Carlberg Lecture 1: Introduction to Engineering OptimizationOutline Convex v. nonconvex Motivation Continuous v. discrete Example Constrained v. unconstrained Problem Classi cation Singleobjective v. multiobjective Modeling Convex v. nonconvex f(x) Convex problems: Convex objective and constraint functions: g( x + y) g(x) + g(y) x convex nonconvex f(x) f(x) x x D D LP (linear programming): linear objective and constraints. Common in management, nance, economics. QP (quadratic programming): quadratic objective, linear constraints. Often arise as algorithm subproblems. NLP (nonlinear programming): the objective or some constraints are general nonlinear functions. Common in the physical sciences. Kevin Carlberg Lecture 1: Introduction to Engineering OptimizationOutline Convex v. nonconvex Motivation Continuous v. discrete Example Constrained v. unconstrained Problem Classi cation Singleobjective v. multiobjective Modeling Convex v. nonconvex signi cance Convex: a unique optimum (local solution=global solution) NLP: A global optimum is desired, but can be dicult to nd f(x) x Figure: Local and global solutions for a nonlinear objective function. Local optimization algorithms can be used to nd the global optimum (from di erent starting points) for NLPs Kevin Carlberg Lecture 1: Introduction to Engineering OptimizationOutline Convex v. nonconvex Motivation Continuous v. discrete Example Constrained v. unconstrained Problem Classi cation Singleobjective v. multiobjective Modeling Continuous v. discrete optimization Discrete: The feasible set is nite Always nonconvex Many problems are NPhard Subtypes: combinatorial optimization, integer programming Example: How many warehouses should we build Continuous: The feasible set is uncountably in nite Continuous problems are often much easier to solve because derivative information can be exploited Example: How thick should airplane wing skin be Discrete problems are often reformulated as a sequence of continuous problems (e.g. branch and bound methods) Kevin Carlberg Lecture 1: Introduction to Engineering OptimizationOutline Convex v. nonconvex Motivation Continuous v. discrete Example Constrained v. unconstrained Problem Classi cation Singleobjective v. multiobjective Modeling Constrained v. unconstrained Unconstrained problems (n = n = 0) are usually easier to e i solve Constrained problems are thus often reformulated as a sequence of unconstrained problems (e.g. penalty methods) Kevin Carlberg Lecture 1: Introduction to Engineering OptimizationOutline Convex v. nonconvex Motivation Continuous v. discrete Example Constrained v. unconstrained Problem Classi cation Singleobjective v. multiobjective Modeling Singleobjective v. Multiobjective optimization We may want to optimize two competing objectives f and f 1 2 (e.g. manufacturing cost and performance) Pareto frontier: set of candidate solutions among which no solution is better than any other solution in both objectives f 2 f 1 These problems are often solved using evolutionary algorithms Kevin Carlberg Lecture 1: Introduction to Engineering OptimizationOutline Motivation Example Problem Classi cation Modeling Modeling Modeling: the process of identifying the objective, variables, and constraints for a given problem Algorithm Parameter Modeling selection selection No Makes sense Solution Yes Finished The more abstract the problem, the more dicult modeling becomes Kevin Carlberg Lecture 1: Introduction to Engineering OptimizationOutline Motivation Example Problem Classi cation Modeling Example (Homework) You live in a house with two other housemates and two vacancies. You are trying to choose two of your twenty mutual friends (who all want to live there) to ll the vacancies. Model the problem as a mathematical optimization problem, and categorize the problem as constrained/unconstrained, continuous/discrete, convex/NLP, and single/multiobjective Kevin Carlberg Lecture 1: Introduction to Engineering OptimizationOutline Motivation Example Problem Classi cation Modeling Rest of the week Unconstrained optimization Constrained optimization PDEconstrained optimization Kevin Carlberg Lecture 1: Introduction to Engineering Optimization