Geoscience Reference
In-Depth Information
Proof
Since f is linear over X
WD f
x
0
W
0
x
1
:::
x
n
g
, there exists
D
.
1
;:::;
n
/ such that for any x
2
X
f.x/
Dh
;x
i
. Now, let us consider
any y
62
X
. There exists a permutation
2
.1:::n/such that y
2
X
.By
the symmetry property it holds f.y/
D
f.y
/.Moreover,fory
we have f.y
/
D
h
;y
i
: Hence, we get that for any x
2
P
n
R
f.x/
Dh
;x
ord
i
:
Finally, the converse is trivially true.
There are particular instances of the vector that make their analysis interesting.
One of them is the convex case, i.e.,
1
:::
n
, where we can obtain a
characterization without the explicit knowledge of a linearity region.
Theorem 10.2
Given
D
.
1
;:::;
n
/
with
1
2
:::
n
; and
D
.
.1/
;:::;
.n/
/
with
2
n
is
P
.1:::n/
, a symmetric function
f
defined over
R
the support function of the set
S
D
conv
f
W
2
P
.1:::n/
g
if and only if
f
is
the convex ordered median function
X
n
f
.x/
D
i
x
.i/
:
(10.3)
iD1
Proof
Let us assume that f is symmetric and the support function of S
. Then,
X
n
f.x/
D
sup
s2S
h
s;x
iD
sup
2
P
h
;x
iD
sup
2
P
h
;x
iD
i
x
.i/
:
.1:::n/
.1:::n/
iD1
Conversely, it suffices to apply Theorem 368 in Hardy et al. (
1952
)to(
10.3
).
Convexity is an important property within the scope of continuous optimization.
Thus, it is crucial to know the conditions that ensure this property. Nevertheless, in
the context of discrete optimization convexity cannot even be defined. Nevertheless,
in this case submodularity plays a similar role. (The interested reader is referred to
the chapter of the Handbook Discrete Optimization by McCormick (
2005
).) In the
following, we also prove a submodularity property of the convex ordered median
function, Puerto and Tamir (
2005
).
Let x
D
.x
i
/, y
D
.y
i
/, be vectors in
n
.Definethe
meet
of x;y to be the vector
x
V
y
D
.min
f
x
i
;y
i
g
/,andthe
join
of x;y by x
W
y
D
.max
f
x
i
;y
i
g
/. The meet
and join operations define a lattice on
R
n
.
R
Theorem 10.3 (Submodularity Theorem)
Given
D
.
1
;:::;
n
/
, satisfying
0
1
2
:::
n
,
f
.x/
is submodular over the lattice defined by the
above meet and join operations, i.e.,
f
.x
_
y/
C
f
.x
^
y/
f
.x/
C
f
.y/;
8
x;y
2
n
:
R
