1 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Multidisciplinary System Design Optimization (MSDO) Multiobjective Optimization (I) Lecture 16 31 March 2004 by Prof. Olivier de Weck 2 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Where in Framework ? Discipline A Discipline B Discipline C I n p u t O u t p u t Tradespace Exploration (DOE) Optimization Algorithms Numerical Techniques (direct and penalty methods) Heuristic Techniques (SA,GA, Tabu Search) 1 2 n x x x ao ?? ?? ?? ?? ?? ?? # Coupling 1 2 z J J J ao ?? ?? ?? ?? ?? ?? # Approximation Methods Coupling Sensitivity Analysis Multiobjective Optimization Isoperformance Objective Vector 3 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Lecture Content ? Why multiobjective optimization? Example – twin peaks optimization History of multiobjective optimization Weighted Sum Approach (Convex Combination) Dominance and Pareto-Optimality Pareto Front Computation - NBI 4 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Multiobjective Optimization Problem Multiobjective Optimization Problem Formal Definition () ,, 1, ..., ) min , s.t. , 0 , =0 ( iLB i iUB inxxx = ≤ ≤≤ -[S J [ S K [ S Design problem may be formulated as a problem of Nonlinear Programming (NLP). When Multiple objectives (criteria) are present we have a MONLP () () [] 1 2 1 1 1 1 where () () () () = ao ?? = ao = ?? ao = ?? " "" " " T z T in T m T m JJ x xx gg hh -[ [ [ J[ [ K[ [ 5 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Multiple Objectives 1 2 3 cost [$] - range [km] weight [kg] - data rate [bps] - ROI [%] i z J J J J J aoao ???? ?? ?? == ???? ?? ?? ???? ?? ???? - # # The objective can be a vector J of z system responses or characteristics we are trying to maximize or minimize Often the objective is a scalar function, but for real systems often we attempt multi-objective optimization: [- [ 6 Objectives are usually conflicting. 6 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Why multiobjective optimization ? While multidisciplinary design can be associated with the traditional disciplines such as aerodynamics, propulsion, structures, and controls there are also the lifecycle areas of manufacturability, supportability, and cost which require consideration. After all, it is the balanced design with equal or weighted treatment of performance, cost, manufacturability and supportability which has to be the ultimate goal of multidisciplinary system design optimization. Design attempts to satisfy multiple, possibly conflicting objectives at once. 7 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Example F/A-18 Aircraft Design Decisions Objectives Aspect Ratio Dihedral Angle Vertical Tail Area Engine Thrust Skin Thickness # of Engines Fuselage Splices Suspension Points Location of Mission Computer Access Door Locations Speed Range Payload Capability Radar Cross Section Stall Speed Stowed Volume Acquisition cost Cost/Flight hour MTBF Engine swap time Assembly hours Avionics growth Potential 8 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Multiobjective Examples Production Planning max {total net revenue} max {min net revenue in any time period} min {backorders} min {overtime} min {finished goods inventory} Aircraft Design max {range} max {passenger volume} max {payload mass} min {specific fuel consumption} max {cruise speed} min {lifecycle cost} 1 2 z J J J ao ?? ?? = ?? ?? ?? - # Design Optimization Operations Research 9 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Multiobjective vs. Multidisciplinary Multiobjective Optimization – Optimizing conflicting objectives – e.g., Cost, Mass, Deformation – Issues: Form Objective Function that represents designer preference! Methods used to date are largely primitive. Multidisciplinary Design Optimization – Optimization involves several disciplines – e.g. Structures, Control, Aero, Manufacturing – Issues: Human and computational infrastructure, cultural, administrative, communication, software, computing time, methods All optimization is (or should be) multiobjective – Minimizing mass alone, as is often done, is problematic 10 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Multidisciplinary vs. Multiobjective single discipline multiple disciplines single objective multiple obj . single discipline multiple disciplines Minimize displacement s.t. mass and loading constraint F δ l m cantilever beam support bracket Minimize stamping costs (mfg) subject to loading and geometry constraint F D $ airfoil α (x,y) Maximize C L /C D and maximize wing fuel volume for specified α, v o V fuel v o Minimize SFC and maximize cruise speed s.t. fixed range and payload commercial aircraft Image taken from NASA's website. http://www.nasa.gov. 11 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Example: Double Peaks Optimization Objective: max J= [ J 1 J 2 ] T (demo) () () 22 12 22 12 22 12 2 (1) 11 35 1 12 (2) 12 31 10 5 30.52 xx xx xx Jxe x xxe exx ?? + ?? ?+ ? =? §· ??? ¨? ?1 + () 22 21 22 22 21 2 1 2 (1) 22 (2 )35 2 21 31 10 3 5 xx xx x x Jxe x xxe e ?+ ???? =+ §· ??+? ? ¨? ?1 12 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Double peaks optimization Optimum for J 1 alone: Optimum for J 2 alone: x 1 * = 0.0532 1.5973 J 1 * = 8.9280 J 2 (x 1 *)= -4.8202 x 2 * = -1.5808 0.0095 J 1 (x 2 *)= -6.4858 J 2 * = 8.1118 Each point x1* and x2* optimizes objectives J 1 and J 2 individually. Unfortunately, at these points the other objective exhibits a low objective function value. There is no single point that simultaneously optimizes both objectives J 1 and J 2 ! 13 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Tradeoff between J 1 and J 2 Want to do well with respect to both J 1 and J 2 Define new objective function: J tot =J 1 + J 2 Optimize J tot Result: X tot* = 0.8731 0.5664 J(x tot *) = 3.0173 J1 3.1267 J2 J tot * = 6.1439 = max(J 1 ) max(J 2 ) tradeoff solution max(J 1 +J 2 ) 14 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics History (1) – Multicriteria Decision Making Life is about making decisions. Most people attempt to make the “best” decision within a specified set of possible decisions. Historically, “best” was defined differently in different fields: – Life Sciences: The best referred to the decision that minimized or maximized a single criterion. – Economics: The best referred to the decision that simultaneously optimized several criteria. In 1881, King’s College (London) and later Oxford Economics Professor F.Y. Edgeworth is the first to define an optimum for multicriteria economic decision making. He does so for the multiutility problem within the context of two consumers, P and π: – “It is required to find a point (x,y,) such that in whatever direction we take an infinitely small step, P and π do not increase together but that, while one increases, the other decreases.” – Reference: Edgeworth, F.Y., Mathematical Psychics, P. Keagan, London, England, 1881. 15 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics History (2) – Vilfredo Pareto Born in Paris in 1848 to a French Mother and Genovese Father Graduates from the University of Turin in 1870 with a degree in Civil Engineering – Thesis Title: “The Fundamental Principles of Equilibrium in Solid Bodies” While working in Florence as a Civil Engineer from 1870- 1893, Pareto takes up the study of philosophy and politics and is one of the first to analyze economic problems with mathematical tools. In 1893, Pareto becomes the Chair of Political Economy at the University of Lausanne in Switzerland, where he creates his two most famous theories: – Circulation of the Elites – The Pareto Optimum “The optimum allocation of the resources of a society is not attained so long as it is possible to make at least one individual better off in his own estimation while keeping others as well off as before in their own estimation.” Reference: Pareto, V., Manuale di Economia Politica, Societa Editrice Libraria, Milano, Italy, 1906. Translated into English by A.S. Schwier as Manual of Political Economy, Macmillan, New York, 1971. 16 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics History (3) – Extension to Engineering After the translation of Pareto’s Manual of Political Economy into English, Prof. Wolfram Stadler of San Francisco State University begins to apply the notion of Pareto Optimality to the fields of engineering and science in the middle 1970’s. The applications of multi-objective optimization in engineering design grew over the following decades. References: – Stadler, W., “A Survey of Multicriteria Optimization, or the Vector Maximum Problem,” Journal of Optimization Theory and Applications, Vol. 29, pp. 1-52, 1979. – Stadler, W. “Applications of Multicriteria Optimization in Engineering and the Sciences (A Survey),” Multiple Criteria Decision Making – Past Decade and Future Trends, ed. M. Zeleny, JAI Press, Greenwich, Connecticut, 1984. – Ralph E. Steuer, “Multicriteria Optimization - Theory, Computation and Application”, 1985 17 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Notation and Classification Ref: Ralph E. Steuer, “Multicriteria Optimization - Theory, Computation and Application”, 1985 Traditionally - single objective constrained optimization: () max . . f st S = ∈ -[ [ () objective function feasible region fJ S [ 6 6 If f(x) linear & constraints linear & single objective = LP If f(x) linear & constraints linear & multiple obj. = MOLP If f(x) and/or constraints nonlinear & single obj.= NLP If f(x) and/or constraints nonlinear & multiple obj.= MONLP 18 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Mapping Sets Linear Nonlinear Decision Space (Design Space) Criterion Space (Objective Space) x 1 x 2 x 1 x 2 J 1 J 2 S Z c 1 c 2 x 1 x 4 x 3 x 2 J 1 J 3 J 4 J 2 J 1 J 2 Z’ J 1 J 4 J 2 x 1 MOLP MONLP x 2 x 3 x 4 S’ S’’ J 3 Z’’ Z’’’ Set of images of all points in set S 19 ? Massachusetts Institute ofTechnology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Map: Double Peaks – many-to-one X tot* J(x tot* ) A function f which may (but does not necessarily) associate a given member of the range of f with more than one member of the domain of f. “Range” “Domain” A Domain Range Bfa Many-To-One 20 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Formal Solution of a MOO Problem Trivial Case: There is a point that simultaneously optimizes all objectives * xS∈ , where 1 i Jiz≤≤ Such a point almost never exists - i.e. there is no point that will simultaneously optimizes all objectives at once Two fundamental approaches: (){ } () 12 max , , , . . 1 i z z ii UJJ J st J f S =≤≤ ∈ [ [ ! Scalarization Approaches Pareto Approaches 12 12 and for at least one ii ii JJ i JJ i ≥? > Preferences included upfront Preferences included a posteriori 21 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Notation SOLP { } max T J S=∈F[ [ S feasible region in decision space if S is determined by linear constraints { } ,0, nm S =∈ = ≥ ∈[$[E[E\MOLP { } {} 1 1 max max . . T zT z J J st S = =∈ F[ F[ [ ## Multiobjective linear program Single objective linear program 22 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Notation (II) C z x n Criterion matrix 12 z cc c ao = ?? & " Gradient vector of z objectives 12 n T ii i n x xx ∈ ao = ?? L L [ [ " point in decision space [] 12 z T z JJ J ∈ = - - " (Criterion) Objective vector 23 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics SOLP versus MOLP x 1 x 2 S c 1 x 1* x 2* c 2 constraints Optimal solution if only J 1 considered Optimal solution if only J 2 considered What is the optimal solution of a MOLP? { } {} 1 2 max max .. S J J st = = ∈   F[ F[ [ 24 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Weighted-Sum Approach x 1 x 2 S c 1 x 1 x 2 c 2 constraints Each objective i is multiplied by a strictly positive scalar λ i 1 0, 1 k z ii i λλ = -? Λ= ∈ > = ?? ˉ? |  x 3* Solve the composite or WSLP: { } max S∈ 7 &[[ c 3 12 λλ=  FFF Strictly convex combination of objectives criterion cone 25 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Weighted Sum: Double Peaks () 12 1 where [0,1] tot JJ Jλλ λ=+? ∈ Demo: At each setting of λ we solve a new single objective optimization problem – the underlying function changes at each increment of λ ?λ=0.05 26 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Weighted Sum Approach (II) λ=1 λ=0 Weighted sum finds interesting, solutions but misses many solutions of interest. 27 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Weighted Sum (WS) Approach 1 z i MOi i i JJ sf λ = = | Max(J 1 /sf 1 ) Min(J 2 /sf 2 ) miss this concave region Pareto front convert back to SOP LP in J-space easy to implement scaling important ! weighting determines which point along PF is found misses concave PF λ 2 >λ 1 λ 1 >λ 2 J-hyperplane J* i J* i+1 PF=Pareto Front(ier) weight scale factor 28 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics What are the weights λ ? : z U →\Decision Maker has a utility function U=f(J), J=J(x) Then: 1 z xxi i i U UJ J = §· ? ?= ? ¨? ? ?1 | Chain rule Gradient of U at x S∈ where i i xi i n J x J J x ? ao ?? ? ?? ?=?? ?? ? ?? ?? ? ? ? # For LP’s 1 z i i w = | L F 1 z x i i U U J = §· ? ?= ¨? ? ?1 | L F Direction of Gradient at x 1 i i UJ w UJ ?? = ?? 1 i i z j j w w λ = = | Weights determine direction of gradient vector of U normalize 29 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Group Exercise: Weights (5 min) We are trying to build the “optimal” automobile There are six consumer groups: -G1: “25 year old single” (Cannes, France) -G2: “family w/3 kids” (St. Louis, MO) -G3: “electrician/entrepreneur” (Boston, MA) -G4: “traveling salesman” (Montana, MT) -G5: “old lady” (Rome, Italy) -G6: “taxi driver” (Hong Kong, China) Objective Vector: J1: Turning Radius [m] J2: Acceleration [0-60mph] J3: Cargo Space [m 3 ] J4: Fuel Efficiency [mpg] J5: Styling [Rating 0-10] J6: Range [km] J7: Crash Rating [poor-excellent] J8: Passenger Space [m 3 ] J9: Mean Time to Failure [km] Assignment: Determine λ i , i =1…9 9 1 1000 i i λ = = | WB=wheelbase, ED=engine displacement x=[WB ED…] T () f=-[ 30 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics What are the scale factors sf i ? Scaling is critical in multiobjective optimization Scale each objective by sf i : Common practice is to scale by sf i = J i * Alternatively, scale to initial guess J(x o )=[1..1] T Multiobjective optimization then takes place in a non-dimensional, unit-less space Recover original objective function values by reverse scaling iii JJsf= Example: J 1 =range [sm] J 2 =fuel efficiency [mpg] sf 1 =573.5 [sm] sf 2 =36 [mpg] “best in GM class” Saab 9-5 Suzuki “Swift” 31 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Properties of optimal solution () () * optimal if for and for S ≥ ∈≠ [ -[ -[ [[[ This is why multiobjective optimization is also sometimes referred to as vector optimization x* must be an efficient solution S∈[ is efficient if and only if (iff) its objective vector (criteria) J(x) is non-dominated A point is efficient if it is not possible to move feasibly from it to increase an objective without decreasing at least one of the others S∈[ (maximization) 32 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Dominance (assuming maximization) Let be two objective (criterion) vectors. Then J 1 dominates J 2 (weakly) iff More precisely: z ∈  --1 2 i z J J J J ao ?? ?? = ?? ?? ?? ?? # and ≥≠   -- -- 12 12 and for at least one ii ii JJ i JJ i≥? > Also J 1 strongly dominates J 2 iff More precisely: >  -- 12 ii JJ i>? 33 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Dominance - Exercise max{range} min{cost} max{passengers} max{speed} [km] [$/km] [-] [km/h] 7587 6695 3788 8108 5652 6777 5812 7432 321 211 308 278 223 355 401 208 112 345 450 88 212 90 185 208 950 820 750 999 812 901 788 790 #1 #2 #3 #4 #5 #6 #7 #8 Multiobjective Aircraft Design Which designs are non-dominated ? (5 min) 34 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Set Theory Non-dominated Designs: #1, #2, #3, #4 and #8 Dominated Designs: #5, #6, #7 Set Theory: D ND DND∩=? S∈[ J Z ,DZNDZ?? DNDZ∪= J* () ND∈ -[ A solution must be feasible A solution is either dominated or non-dominated but cannot be both at the same time All dominated and non-dominated solutions must be feasible All feasible solutions are either non-dominated or dominated Pareto-optimal solutions are non-dominated Z∈-- 35 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Procedure (I) Algorithm for extracting non-dominated solutions: Pairwise comparison 7587 > 6695 321 > 211 112 < 345 950 > 820 Score #1 Score #2#1 #2 1 0 0 1 0 1 1 0 2 vs 2 Neither #1 nor #2 dominate each other 7587 > 6777 321 < 355 112 > 90 950 > 901 Score #1 Score #6#1 #6 1 0 1 0 1 0 1 0 4 vs 0 Solution #1 dominates solution #6 In order to be dominated a solution must have a”score” of 0 in pairwise comparison 36 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Procedure (II) for ind1=1:(n-1) for ind2=(ind1+1):n Ja=Jall(:,ind1).*sign(minmax); Jb=Jall(:,ind2).*sign(minmax); scorea=0;scoreb=0; for indz=1:z if Ja(indz)>Jb(indz) scorea=scorea+1; elseif Ja(indz)<Jb(indz) scoreb=scoreb+1; else % both solutions are equal end end if scoreb==0&scorea~=0 dmatrix(ind1,ind2)=1; %a dominates b elseif scorea==0&scoreb~=0 dmatrix(ind2,ind1)=1; %b dominates a else % no domination in this pair end end end Pairwise comparison Populate Domination Matrix paretosort.m 37 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Domination Matrix 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 0 0 0 0 0 1 Solution 2 dominates Solution 5 0 0 0 0 1 1 2 0 Shows which solution dominates which other solution (horizontal rows) and (vertical columns) Solution 7 is dominated by Solutions 2 and 8 Row Σ j-th row indicates how many solutions j-th solution dominates Column Σ k-th column indicates by how many solutions the k-th solution is dominated Non-dominated solutions have a zero in the column Σ ! 38 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Dominance versus Efficiency Whereas the idea of dominance refers to vectors in criterion space J, the idea of efficiency refers to points in decision space x. Mapping: () { } , z ZfS=∈ = ∈--[[MOLP MONLP { } , z ZS=∈ = ∈--&[[dominance (objective space) efficiency (decision space) Z= reachable range in objective space 39 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Efficiency () () () () A point is efficient iff there does not exist another such that and . Otherwise is inefficient. S S ∈ ∈≥ ≠ [ [-[-[ -[ -[ [ A point x is efficient if its criterion (objective) vector is not dominated by the criterion vector of some other point in S. Efficient set ND Can use this criterion as a Pareto Filter if the design space has been explored (e.g. DoE). 40 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Double Peaks: Non-dominated Set Filtered the Full Factorial Set: 3721 Non-dominated set approximates Pareto frontier: 79 points (2.1%) 41 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Pareto-Optimal vs ND max (J 1 ) min(J 2 ) True Pareto Front Approximated Pareto Front D ND PO All pareto optimal points are non-dominated Not all non-dominated points are pareto-optimal √ √ √ √ It’s easier to show dominatedness than non-dominatedness !!! Obtain different points for different weights 42 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Direct Pareto Front Calculation SOO: find x* MOO: find PF PF J 1 J 2 PF J 1 J 2 bad good - It must have the ability to capture all Pareto points - Scaling mismatch between objective manageable - An even distribution of the input parameters (weights) should result in an even distribution of solutions A good method is Normal-Boundary-Intersection (NBI) 43 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Normal Boundary Intersection (I) Goal: Generate Pareto points that are well-distributed 1 J 2 J 1 0 1 Reachable Range NU * 1 J * 2 J - S [ 0 u - Utopia Point 1. Carry out single objective optimization: () * 1,2,..., ii J Jiz=?= L [ 2. Find utopia point () ii i i JJ J l ? = L [ () () () 12 T z JJ J ao = ?? X  ] -[[ [" 5. Normalize 3. Find Nadir Point 12 T NN N z JJ J ao = ?? 1 - " () () () min T N iii i JJJ J=   ] [[ [" 4. Nadir-Utopia Distance [ ] 12 T z ll l== 1X /--" 1, 2,...,iz= 44 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Normal Boundary Intersection (2) Carry out a series of optimizations Restricted design space: U – Utopia Line between anchor points, NU – normal to Utopia line Feasible region restricted to one part of Range Find Pareto point for each NU setting Move NU from to in even increments Yields remarkably even distribution of Pareto points Applies for z>2, U-line becomes a Utopia-hyperplane * 1 J * 2 J Reference: Das I. and Dennis J, “Normal-Boundary Intersection: A New Method for Generating Pareto Optimal Points in Multicriteria Optimization Problems”, SIAM Journal on Optimization, Vol. 8, No.3, 1998, pp. 631-657 45 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Lecture Summary A multiobjective problem has more than one optimal solution All points on Pareto Front are non-dominated Methods: Weighted Sum Approach (Caution: Scaling !) Pareto-Filter Approach Normal Boundary Intersection (NBI) More methods in the next lecture The key difference between multiobjective optimization methods can be found in how and when designer preferences are brought into the process. …. More in next lecture 46 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Remember …. Pareto Optimal means ….. “Take from Peter to pay Paul”