Geoscience Reference
In-Depth Information
Par
f
1
;f
2
;f
3
with respect to the three objective functions f
1
;f
2
;f
3
. For a cell C
2
gen
X
Now it remains to consider the Pareto-optimality of the set
C
we define
the collapsing and the remaining part of C with respect to Q-criteria optimality by
col
Q
.C/
WD
˚
x
2
C
W
x
…
Par
f
1
;:::;f
Q
X
rem
Q
.C/
WD
˚
x
2
C
W
x
2
Par
f
1
;:::;f
Q
:
X
Summing up the preceding results we get a complete geometric characteriza-
tion of the set of Pareto solutions for the three criteria case. For each cell C,
col
Q
.C/
P
[
rem
Q
.C/
D
C and,asshownbyNickeletal.(
2005b
), determining both
sets can be done with the gradients of the objective functions with a complexity of
O.Qlog Q/.
Theorem 9.6
The set of Pareto solutions satisfies:
X
Par
f
1
;f
2
;f
3
D
X
Par
f
1
;f
2
;f
3
[
encl
X
Par
f
1
;f
2
;f
3
gen
gen
Par
f
1
;f
2
;f
3
;x
2
col
3
.C/
g
:
gen
2
W9
C
2
nf
x
2
C
;C
X
R
X
Par
f
1
;f
2
;f
3
. Then we have, by Theorem
9.5
,thaty
2
Proof
Let y
2
Par
f
1
;f
2
;f
3
[
encl
X
Par
f
1
;f
2
;f
3
: Moreover for C
2
gen
gen
X
C
with y
2
C
we have y
2
rem
3
.C/,i.e.,y
…
col
3
.C/. This implies
y
2
X
Par
f
1
;f
2
;f
3
[
encl
X
Par
f
1
;f
2
;f
3
gen
gen
Par
f
1
;f
2
;f
3
;x
2
col
3
.C/
g
:
gen
2
W9
C
2
nf
x
2
R
C
;C
X
We distinguish the following cases :
Case 1: y
2
encl
X
Par
f
1
;f
2
;f
3
.Theny
2
X
Par
f
1
;f
2
;f
3
by Theo-
gen
rem
9.5
.
Case 2 : y
2
Par
f
1
;f
2
;f
3
.
Case 2.1 :
9
C
2
gen
X
Par
f
1
;f
2
;f
3
with y
2
C
)
y
…
col
3
.C/
)
y
2
rem
3
.C/
)
y
2
gen
C
;C
X
X
Par
f
1
;f
2
;f
3
.
Par
f
1
;f
2
;f
3
with y
2
C
)
L
.f
p
;f
p
.y//
\
L
.f
q
;f
q
.y//
Df
y
g
for some p;q
2f
1;2;3
g
;p<q
)
T
qD1
L
.f
q
;f
q
.y//
D
y
g)
y
2
gen
Case 2.2 :
69
C
2
C
;C
X
X
sPar
f
1
;f
2
;f
3
X
Par
f
1
;f
2
;f
3
:
In the case of median functions the gradients
r
f
q
.x/; q
2f
1;2;3
g
; (in
those points where they are well-defined) can be computed in O.M log.G
max
//
time (analogous to the evaluation of the function). Therefore, we can test in
O.M log.G
max
// time if a cell C
2
Par
f
1
;f
2
;f
3
collapses. We
gen
C
;C
X
