Geoscience Reference
In-Depth Information
dCm
2
Cn.dC1/
be the feasible domain of Problem
(
10.13
)
-
(
10.24
)
. Then, with the notation above:
Theorem 10.5
Let
K
R
(a)
min
Q
r
"
as
r
!1
.
(b) Let
y
r
be an optimal solution of the SDP relaxation (
Q
r
). If
rank M
r
.
y
r
/
D
rank M
rr
0
.
y
r
/
D
t
then
min
Q
r
D
and one may extract
t
points
.x
.k/;
u
.k/;v
.k/;
w
.k//
t
kD1
K
, all global minimizers of problem (
OMPF
).
Proof
The convergence of the semidefinite relaxation
Q
r
follows from a result by
Jibetean and de Klerk (
2006
, Theorem 9) that it is ap
pli
ed here to the polynomial
function in (
10.13
) and the closed semi-algebraic set
K
. The second assertion on
the rank condition, for extracting optimal s
olu
tions, follows from applying Lasserre
(
2009
, Theorem 5.7) to the SDP relaxation
Q
r
.
We also observe that one can exploit the block diagonal structure of the
problem (
10.13
)-(
10.21
) since the only monomials that appear in that formulation
are of the form x
Ǜ
u
i
Q
jD1
v
j
ij
for all i
D
1;:::;m. Hence, a result similar to
Theorem12inBlancoetal.(
2013
) about a sparse reformulation also holds for this
problem.
Tab les
10.1
and
10.2
present some computational results obtained applying the
above technique for different planar ordered median problems. Programs were
coded in MATLAB R2010b and executed in a PC with an Intel Core i7 processor
at 2
2:93GHz and 8 GB of RAM. The semidefinite programs were solved
by calling SDPT3 4.0, Kim-Chuan et al. (
2006
). We report the CPU times for
computing solutions as well as the gap,
obj
, with respect to upper bounds obtained
with the battery of functions in
optimset
of MATLAB, which only provide
approximations on the exact solutions (optimality cannot be certified). In order to
compute the accuracy of an obtained solution, we use the following measure for the
error (see Blanco et al.
2013
):
obj
D
j
the optimal value of the SDP
fopt
j
max
f
1; fopt
g
;
(10.25)
where fopt is the approximated optimal value obtained with the functions in
optimset
. The interested reader is referred to Blanco et al. (
2013
, Section 5)
for further details and computational results using the tools in this section applied
to location problems.
