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”