A Geometric Approach to Global Optimization.
In this paper we consider the problem of optimizing a piecewise-linear objective function over a non-convex domain. In particular we do not allow the solution to lie in the interior of a prespecified region R. We discuss the geometrical properties of this problems and present algorithms based on combinatorial arguments. In addition we show how we can construct quite complicated shaped sets R while maintaining the combinatorial properties.
Introduction
The solution of piecewise linear programs has always played a special role in
optimization.
In general, piecewise-linearities are often employed to give a more realistic description
of costs than can be achieved by linear terms alone. Also in worst case
analysis piecewise linearity arises naturally.
Furthermore, piecewise-linear programs may be used for approximating convex
objective functions by piecewise linear functions. Such an approximation method
including error bound analysis was proposed by [BHR91].
In addition, piecewise linear programs arise in specific branches of operations
research, like for example location theory, where - given a number of existing
facilities - a new facility has to be located so that some objectives are optimized.
The objectives are often in the form of piecewise linear functions due to the fact
that typically the sum (or the maximum) of weighted distances from the existing
facilities to the new facility is chosen as a criterion. Moreover, these distances are
often derived from norms with a polyhedral unit ball. See [LMW88], [FLFMW92],
and [Nic95] for various piecewise linear models in location theory.
For an overview about methods for solving piecewise linear programs the reader
is referred to [Fou85], [Fou88], [Fou92], and references therein.
As a conclusion it is quite natural also to look at global optimization problems
with piecewise-linearities. In particular, we are interested in the problem of optimizing
a piecewise-linear objective function over a non-convex domain. These
includes problems with reverse convex constraints. For more details and an introduction
to global optimization the reader is referred to [HT96] and references
therein.
Now we will formally introducing the model we consider in this paper.
1.1 The model
Consider the following piecewise linear optimization problem in
and the f are K
different affine linear functions. This is a well-known convex problem and can
efficiently be solved by linear programming methods.
We can also easily introduce a feasibility region A, where A is a polyhedral set
with
A := fx 2
Also (OL) with the additional restriction that x 2 A can be formulated as linear
program and therefore be solved efficiently.
min z
If, however, the feasible region A cannot be described by linear inequalities, or is
not convex, we are in the area of global optimization. In particular we consider
in this paper A := cl(IR n n R), with R ' IR n . By cl(S) we denote the closure of
a set S. Now the minimization problem (ROL) reads
min
f(x) or min
where int(R) denotes the interior of R. With the help of geometric properties of
this problem we will be able to give algorithms to solve (ROL) for a large class
of possible sets R.
The remainder of the paper is organized as follows: First we state geometrical
properties of level curves and level sets. These results are used to derive a combinatorial
description of the solution set in IR n for (ROL) and convex sets R.
Section 4 shows how these results can be extended in the plane for more general
sets R while maintaining the combinatorial character of the solution. The paper
ends with some conclusions and an outview to further research.
2 The concept of cells and level sets
For any set R ' IR n let ext(R) denote the extreme points of R and @R the
boundary of R. Furthermore, let Kg. Then f(x) can be written
as
is an affine linear function and the f k are pairwise different. To denote the solution
sets we introduce
R := min
and
R g:
By defining cells
else
we get a subdivision of IR n into not more than K nonempty cells. The set of all
cells is denoted C. Some properties of C are summarized in the following lemma.
Lemma 1 For the cells C i , i 2 K the following holds:
1. For i 2 K we have that either C i is a polyhedral set with dimension n or
2. ig.
3. S
4.
Proof:
ad 1.) From the definition of C i it follows that C i is either empty or a polyhedral
set which is full-dimensional, because in that case int(C i ) 6= ;.
ad 2.) Let x 2 int(C i ) and suppose there exists k 6= i such that f i
As x is in the interior of C i there exists a ball U := U(x) around x such
that U(x) ' int(C i ). As f i 6= f k the hyperplane H
separates U into two parts U
H such that for all y
H . This is a contradiction since U ' C i .
ad 3.) Take an x 2 IR n . We then have an index i such that f g.
If i is unique, x 2 int(C i ) and we are done. If i is not unique we define
I := fi
Then there exists a ball U := U(x) around x such that
Now define for all k; l; k 6= l; k; l 2 I: g kl := fy
G as the union of all g kl . As the g kl are hyperplanes, U n G 6= ;. Take
G. Then there exists a unique j 2 I such that
meaning that the cell C j 6= ;. As also f j (x) - f k (x) for all k 2 K we can
conclude that x 2 C j .
ad 4.) This statement follows directly from 2. q.e.d.
As the lemma shows, we need only to investigate cells C and we can neglect
the empty ones. In the following we therefore will assume that all cells are
non-empty. The concept of cells has frequently been used in optimization (see
[RS72], [Ede87], [HN95], [Nic95] and references therein). From this literature the
following result is well-known, but restated here for the specific context of this
paper.
Theorem 1 X   is either a whole cell or an r-dimensional facet of a cell, r 2
Proof: We can solve (OL) by inspecting all cells. For any cell C i the optimization
problem is a linear program of which the feasible set is the polyhedral set C i .
Therefore the result follows from the well known properties of linear programming
theory. q.e.d.
The following corollary says, that, for finding one optimal solution it is enough
to look at the extreme points of the cells.
Corollary 1 There always exists a point x 2 X   with x is the extreme point of
a cell C i for an index i 2 K.
We define C @ as the set of all facets of all cells C 2 C.
Additionally, we define construction lines
for all j. The set of all construction lines, denoted by H,
constitutes an arrangement of hyperplanes which define a set of cells CH similar
to the ones introduced by [Ede87]. Note that CH is a subpartition of C, i.e.
denote the set of points x 2 IR n belonging
to a facet of a cell or a construction line, respectively).
The name "lines" refers to the 2-dimensional case where we in fact have 1-
dimensional construction lines. In the n-dimensional case the construction lines
are (n \Gamma 1)-dimensional sets.
Example 1 We are given
In

Figure

1 the
two cell partitions C and CH are shown. We can easily compute X
checking the extreme points of all cells C 2 C.

Figure

1: Illustration for Example 1. The bold part shows C @ . The normal and the bold lines
together constitute H.
One more definition is necessary for that paper. For t 2 IR define the level set
L- (t) and the level curve L= (t) as
Note that for any convex function f , L- (t) is a closed, convex set, which is
nonempty for all t - t   .
Lemma 2 For t ? t   we have that @L-
Proof: For t - t   the result is obvious. For t ? t   we know that any convex
function f with minimal value t   is strict convex on the set fx 2
of all non-minimal solutions. That proves the lemma. q.e.d.
Using level curves and level sets we can reformulate (OL) and (ROL).
Theorem 2
a) t   is the optimal objective value of (OL)
R is the optimal objective value of (ROL)
c) In a) and b) L= (t) can be replaced by L- (t)
d) x is an optimal solution of (ROL) with
R if and only if there exists a
IR, such that
and
The proof follows easily from the definition of level curves, level sets, and Lemma 2.
Lemma 3 . The level curves L= (t) are piecewise linear on C. More specific,
has one of the following shapes:
1. empty
2. the whole cell C i , in this case we have that
3. an r-dimensional facet of C
4. the intersection between C i and a hyperplane H with
it follows that t ? t
Note that only in Case 2 and Case 4 we can say something about the optimality
of t.
Proof:
Case 1: f i const 8x 2 IR n . Then H can either be empty (yielding the
first case) or yielding that L= t.
In the latter case we also have that for all x 2 C i t. Since
f is a convex function, it only can be constant on a full-dimensional set if
it is minimal on that set. Therefore that we can conclude and the
whole cell C i is optimal.
Case 2: f i (x) is not a constant function. Then H is a hyperplane in IR n and
ffl If we have that H " C i ' @C i then H is a supporting hyperplane for
since C i is a polyhedral set it follows that H " C i is a facet of
, we can conclude that int(C i
;. In this case let C
i be the two parts of the cell C i which
are separated by the hyperplane H. That means, one of C
i is
completely contained in L- (t). Let C
t   . Consequently, C
which is a
contradiction, because C
Note that as C i is convex we have that
Proof: As L= there are three possibilities according to Lemma 3.
ffl If L= consequently,
ffl If
ffl If there exists a hyperplane H with C i
then suppose L=
which is a contradiction to Theorem 1. q.e.d.
The following theorem is a consequence of the convexity of f (see also [HT96]
and [HN94]).
Theorem 3 If X   ' int(R) then we have X
Proof: Let x 2 X   and assume that there exists y 2 IR n such that y 2 X
Then y 62 R, yielding that f(x) ! f(y) and therefore we know for all - 2 (0; 1]
that
This also holds if we choose - such that -x which proves the
theorem. q.e.d.
3 Solution for convex forbidden sets in IR n
In this section we look at forbidden sets R which are convex. As we will show in
the following theorem, for these sets there always exists an optimal solution for
the restricted problem, which is in the intersection of the boundary of R with the
the boundary of a cell C 2 C:
Theorem 4 Let R be a convex set, R ' IR n and X   ' int(R). Then there exists
x
R and c 2 C @ with
x
Furthermore only intersections with dim(c " have to be investigated.
Proof: Let x
R such that x 62 C @ . Let
we know that t ? t   , and consequently (see Lemma
is a hyperplane with L= Now we look at the following two
cases.
Case 1: Note that since x 62 C @ we know that x 2
Therefore we can conclude that H
a hyperplane, and x 2 @R " H i . According to Corollary 2 there exists
@R such that z 2 X
Case 2:
That means cannot be optimal for the restricted problem since
Theorem 3 tells us that X
Now suppose we have dim(c " This implies that c
coincides locally with @R and among c the objective function is linear. Assume
that there is no c every level curve
touching c " @R has to be linear throughout c " @R and therefore L= 6' R,
contradicting the optimality condition. It follows that for a x
be optimal there must exist a c
and the result follows by
replacing c by c 0 . q.e.d.
Theorem 5 Let R ' IR n be a convex polyhedron, and X   ' int(R). The set
of facets of R is denoted by F . Then there exists always an optimal solution
x
R in the finite set of points
Cand
Proof: From Theorem 4 we know that for an optimal x   we have x
for some H 2 H. Choose a facet F 2 F such that x   2
choose an index i such that also x   2 @C i holds. Now we have x   2
Therefore
means f is linear in F " Now we
can conclude from the theory of linear programming that there always exists an
optimal vertex v of the polyhedron F "
know that v 2 H " @R and additionally
The next theorem gives a characterization of the optimal solution for all convex
restricted sets. Note that in IR 2 this result is equivalent to Theorem 4.
Theorem 6 Let R ' IR n be convex , and X   ' int(R). Then there exists always
an optimal solution x
R such that x
R is a zero-dimensional intersection
between the boundary @R and a sufficient number of construction lines H 2 H.
Proof: From Theorem 4 we know that there always exists an optimal solution
x
R such that x
only consists of one single point, we are done. If not, we consider the
following problem (ROL1) on the
Note that the optimal solutions of (ROL1) are optimal for (ROL). As the restriction
of f to the linear subspace H 1 remains piecewise linear and convex, R "
is a convex set and
are the new construction lines we can apply Theorem 4 again. We conclude that
there always exists an optimal solution x
R to (ROL1) (and therefore to (ROL))
such that x \Lambda1
according to the definition of H 1 . Then we know that
We repeat this argument until we have a number z of hyperplanes H
H such that the set
only consists of one single point, which then is an optimal solution to (ROL).
q.e.d.
The following corollary shows how Theorems 4 and 6 can be used to derive
an efficient algorithm for solving (ROL) in the plane. We use the fact that
since H is easier to compute.
Corollary 3 Let be a convex set such that X   ' int(R).
Then there exists always an optimal solution x
R in the finite set of points
In the algorithm we first compute the set Cand and then look for the best candidate

Algorithm for solving (ROL) in the plane.
R
1. Compute
2. Compute
3. For all
4. Determine t )g.
5. Output: X
The complexity of the above algorithm is dominated by the complexity of Step
3 which is Int O(K 2 ) (where Int is the complexity of computing an intersection
point between a line and the boundary of the forbidden set R) and the complexity
of Step 4 being O(K 3 ). Overall we have a complexity of O(K 3
Example 2 We use the same objective function f as in Example 1. In addition
we are given a convex set R = [\Gamma10; 14] \Theta [2; 20]. By checking the set of candidates
Cand we get X
objective value 38(see

Figure

2). In Figure 3 the
reduced candidate set based on Theorem 4 is shown.
R

Figure

2: Illustration for Example 2. The bold points show the set of candidates H " @R.
When applying Theorems 4 and 5 for higher dimensions to derive efficient algorithms
a pure enumeration of the set of Candidates is not appropriate. Therefore
combined enumeration and search procedures are suggested. Instead of solv-
ing
R

Figure

3: Illustration for Example 2. The bold points show the set of candidates @C " @R.
for all facets F 2 F it is also possible to restrict the search procedure to linear
subspaces of lower dimensions and solve for all
and all facets F 2 F
Which of those alternative solution approaches is more appropriate is dependent
on the input data.
4 Extensions in the plane
In this section we consider more realistic forbidden sets. At first we examine
what happens, if the forbidden set is not connected, and then extend the results
to so-called bumpy sets.
The algorithm of the previous section can easily be modified to accommodate
the case where R is the union of pairwise disjoint, convex sets R 1
In this situation we first solve the unrestricted problem (OL). Then the following
result is an immediate consequence of Theorem 3.
Theorem 7 Let
and R i are convex sets for L. Then there exists an optimal solution x
R
such that either x
R 62 int(R) or there exists some l with X
R ' @R l .
Proof: If X   ' int(R) Then the convexity of X   and the assumptions on the sets
imply that there exists some l such that X   ' R l . Hence we can
replace R by R l and use Theorem 3 to conclude that X
R ' @R l . q.e.d.
Our results can be extended to other cases of nonconvex restricting sets R. If
we review the proof of Theorem 4 it becomes apparent that we can apply a
combinatorial algorithm as in the case of convex sets whenever we have only a
finite set of points on @R which can lie in the (relative) interior of linear pieces
of a level curve. Therefore we introduce the concept of bumpy sets, which was
first mentioned in [HN95] in the area of location theory.
with its set of roots Roots(R) is any set
which can be constructed by a finite application of the following rules:
1. Any convex set R is a bumpy set. In this case
2. If R 0 is a bumpy set then R
is a one-dimensional, connected, proper curve segment
(i.e. there exists a bijective mapping OE : [0;
In this case R 0 is called the base of R and R 1 the bump. The two disjoint
endpoints of s are the new roots of R, i.e.
Note that dependent on the construction of the bumpy set, the same bumpy set
can have a different set of roots, i.e. Roots(R) is not uniquely defined. For the
following algorithm, however, any set of roots leads to an optimal solution. For
the running time, the smallest set of roots is preferable.
In

Figure

4 and Figure 5 some examples of bumpy sets are shown, and the
following lemmas describe some classes of bumpy sets. Some more applications
of bumpy sets will be shown at the end of this section.

Figure

4: An example for a bumpy set. The dots mark the set of roots.
Lemma 4 Let R be a strict convex set and R 0 a translate of R, such that int(R "
set.
Proof: Choose R as base and R 0 as bump.
ffl R is convex and therefore a bumpy set,
line segment as @R " @R 0
consists of only two points (see, e.g. [Kle97]). q.e.d.
is a bumpy set.
Proof: If R is convex it trivially is a bumpy set. If not we define the convex set
R 0 as the base of the bump. Let be the connected components of
As R is not convex, we know that R 0
consists of L connected, one-dimensional, proper curve segments. That means we

Figure

5: Another example for a bumpy set. The dots mark the set of roots.
can iteratively add all bumps BL to R 0 , as we know that conv(B l ) '
As mentioned, we now will extend the algorithm of the previous section to the
case, where R is a bumpy set. In the following we therefore prove that to find an
optimal solution to (ROL), it again is enough to evaluate a finite candidate set.
In order to do this one more result about the structure of bumpy sets is needed.
Lemma 6 Let R be a bumpy set and s be a line segment. If s ' R and int(s)
touches @R at a unique point x then x 2 Roots(R).
Proof: Induction over the number of bumps.
For a convex set R and a line segment s ' R we know that the interior of s
cannot touch @R from inside at a unique point.
Now take any bumpy set R with base R 0 and bump R 1 . Let s be a line segment
with its interior touching @R from inside at a unique point, i.e., s ' R and
fxg. Now we distinguish three cases:
ffl If x 62 @R 1 , we know that x 2 Roots(R 0 due to the induction
hypothesis.
by definition x 2 @R is one of the (new) roots of R.
and therefore we
again have a linear piece touching a convex set from inside at a unique
point, which is a contradiction.
q.e.d.
The following theorem shows that in order to solve (ROL) with R is a bumpy
set it suffices to examine the candidate set of the last section, i.e. the zero-dimensional
intersections between the boundary of R and the construction lines
additionally, the roots of the bumpy set R.
Theorem 8 Let R ' IR 2 be a bumpy set such that X   ' int(R). Then there
always exists an optimal solution x
R in the finite set of points
Cand
Proof: With Theorem 2 we know that t
R is the optimal value of (ROL) if and
only if L- (t
We also know that L= (t
is the
set of optimal solutions. Now take any x
There exists an open set U 2 IR 2 such that we have a unique point
x
fx
As the level curve L= (t
R ) consists of linear pieces (see Lemma 3) we either
have
ffl that x
R is the endpoint of such a linear piece, in this case x
for some H 2 H (see Theorem 4) or
R is in the interior of such a linear piece, then, according to Lemma 6,
x
R is part of a linear piece s ' L= (t
we know that the endpoints x of s are also in @R and clearly f(x 1
R . At both endpoints, on the other hand, other construction lines
intersect (as the level curves are piecewise linear on the cells,
see Lemma 3), such that we have x
Algorithm for solving (ROL) in the plane with R is a bumpy set.
R
1. Compute
2. Compute
3a. For all
3b.
4. Determine t )g.
5. Output: X
Example 3 We use the same objective function f and forbidden region R as in
Example 2. In addition we are given a convex set R 2] as a bump.
By checking the extended set of candidates Cand we get the new candidates (1; 2) ,
loose the two former candidates ( 16; 2) and (2; 2). By
computing the objective function for the candidates we get X
with objective value 40(see

Figure

6).
Finally we give two examples for the application of bumpy sets. The first application
shows that we can solve the restricted problem (ROL) for any simple
polygon. These simple polygons can then be used for approximating more complex
sets R (see [BHR91], [Rot92] and [KN96] for more details).
Lemma 7 Any simple polygon is a bumpy set.
Proof: Induction over the number of vertices n of the polygon. For
a convex triangle which trivially is a bumpy set. Now take any polygon R with
more than 3 vertices. Consider a triangulation of R into (such a
triangulation always exists, see e.g. [Kle97], [O'R93]) and take any triangle R 1
of that triangulation such that R 1 has two edges on the boundary of R. Define
R 1 as bump and R 0 := R n R 1 as base. Then the triangulation of R 0 consists of
triangles, such that the number of vertices of R 0 is
is a bumpy set, R 1 is convex and
proper line segment, since it is the third edge of the triangle R 1 . q.e.d.
If R is a polygon then the set of roots in the above construction is contained in
the set of vertices of the polygon, i.e.
vertex of Rg;
R
R

Figure

Illustration for Example 3. The bold points show the set of candidates H " @R plus
the roots of the bump.
such that the set of candidates in Step 3b of the algorithm would be
Cand vertex of Rg:
This can be sharpened, as the following lemma shows.
Lemma 8 Let R be a polygon and let X   ' int(R). Then there exists always an
optimal solution x
R in the finite set of points
Cand
Proof: This lemma can be shown by a special bumpy set construction using only
reflexive vertices as roots. Another possibility is to prove the result along the
lines of Theorem 8. q.e.d.
Another application is the following. Suppose we want to have m solutions
\Lambdam to the problem (OL), but have the restriction that these solutions
are not too similar,i.e.
for a given number r 2 IR and a convex distance measure d. This concept has
been used by [BW96] in the context of location theory. Then we can proceed as
follows: First we find the best solution x \Lambda1 to our problem. Then we forbid all
solutions which are too similar to x \Lambda1 , i.e. R rg. Solving that
problem we find a solution x Iterating that procedure, to find x \Lambdak we
solve problem (ROL) with
Then minimal solution to the above problem.
This problem can be solved with our algorithm, if all the sets R k
are bumpy sets. If m - 3,x Lemma 4 shows that this can be done for any strict
convex distance function d in IR 2 . If we also want to have distance functions with
linear pieces, e.g. l 1 or l 1 distances or any kind of gauges we can use Lemma 5
can be shown, that the sets R k are bumpy sets, if they
do not have any wholes. Even if they have wholes, Lemma 6 remains true, such
that the algorithm can be adopted to solve the problem.
Conclusions
In this paper we have shown how global optimization problems can be solved using
geometrical methods and combinatorial arguments. These discretization approach
proved to be very successful if the original assumptions are weakened, like
in the case of bumpy sets. Moreover, this approach yields numerically stable and
efficient procedures and allows us to easily compute the whole set of optimal solu-
tions. Of course, this approach is also useful for general convex objective functions
using approximation methods, like the ones described in [BHR91]. Therefore our
future work will include the adaption of such approximation methods to (ROL).
Also computational tests and bounding techniques are under consideration.



--R

Sandwich approximation of univariate convex functions with an application to separable convex programming.
The rectilinear distance minisum problem with minimum distance constraints.
Algorithms in Combinatorial Geometry.

A simplex algorithm for piecewise-linear programming I: derivation and proof
A simplex algorithm for piecewise-linear programming II: finiteness
A simplex algorithm for piecewise-linear programming III: computational analysis and applications
Combinatorial algorithms for some 1-facility median problems in the plane
Restricted planar location problems and applications.
Global Optimization.
Algorithmische Geometrie.
bounds for the approximative solution of restricted planar location problems.
Facilities Location: Models
Discretization of Planar Location Problems.

The convergence rate of the sandwich algorithm for approximating convex functions.
Introduction to piecewise-linear topology
--TR
discretization;piecewise linear programs;reverse convex constraints;geometric approach