Geoscience Reference
In-Depth Information
10.3.2
Generalized Continuous Ordered Median Location
Problems
This section extends the analysis presented above, in Sect. 10.3.1 , to the case of non-
polyhedral norms and any dimension d. In doing that we shall cast that problem
within the more general paradigm of polynomial programming. This approach
allows us to apply powerful tools borrowed from the theory of global optimization to
solve our original problem, see Blanco et al. ( 2013 ). This section contains advanced
material which is self-contained. For this reason those non specialized readers not
interested in global optimization techniques may decide to skip it without losing
continuity with the remaining sections of this chapter.
We are given a set A Df a 1 ;:::;a n g
d endowed with an ` -norm (here `
R
stands for the norm k x k D P iD1 j x i j 1=
d ); and a feasible domain
,forallx 2
R
d ,assumedtobeaclosedsemi-
algebraic set, i.e. a set defined by a finite number of polynomial inequalities, where
each g j .x/ 2
d W g j .x/ 0; j D 1;:::;` g
K WD f x 2
R
R
Œx the ring of real polynomials in
.x 1 ;:::;x d /. Since we are interested in solving location problems we shall assume
without loss of generality that we wish to solve the problem in a bounded domain so
that K is compact. The goal is to find a point x 2 K minimizing some globalizing
function of the distances to the set A. Here, we consider that the globalizing function
is rather general and that it is given as an ordered weighted average of polynomials
(the reader may observe that the same approach also extends to rational functions,
Blanco et al. 2013 ).
Some well-known examples, that are formulated in the above terms, are the
following (see, e.g., Blanquero and Carrizosa 2009 ; Drezner 2007 ;Espejoetal.
2009 ; López-de-los-Mozos et al. 2008 or Nickel and Puerto 2005 ):f. u 1 ;:::; u n / D
R
Œx is a polynomial, being
R
P i<j j u i u j j , is the absolute deviation or envy criterion, f. u 1 ;:::; u n / D
P iD1 . u i 1=n P jD1 u j / 2 , is the variance function, f. u 1 ;:::; u n / D P jD1 w j = u j ,
where w j are scalar weights, is the obnoxious facility criterion and f. u 1 ;:::; u n / D
P jD1 b j =.1 C h j j u j j /, with b j and h j appropriate weights, is the Huff competitive
location objective function.
The main feature and what distinguishes location problems from other general
purpose optimization problems, is that the dependence of the decision variables
is given through the norms to the demand points in A,i.e. k x a i k .Inthis
section, we consider a generalized version of the ordered continuous single facility
location problems over closed semi-algebraic feasible sets, i.e., the Ordered Median
of Polynomial Functions problem:
X
m
j f .j/ .x/ W x 2 K g ;
WD minimize f
( OMPF )
jD1
Search WWH ::




Custom Search