Solutions to Affine Generalized Equations Using Proximal Mappings.
The normal map has proven to be a powerful tool for solving generalized equations of the form: find z &#949; C, with 0 &#949; F(z) a convex set and NC(z) is the normal cone to C at z. In this paper, we use the T-map, a generalization of the normal map, to solve equations of the more general form: find z &#949; dom(T), with 0 &#949; F(z) We present a path-following algorithm that determines zeros of coherently oriented piecewise-affine functions, and we use this algorithm, together with the T-map, to solve the generalized equation for affine, coherently oriented functions F, and polyhedral multifunctions T. The path-following algorithm we develop here extends the piecewise-linear homotopy framework of Eaves to the case where a representation of a subdivided manifold is unknown.
Introduction
This paper is concerned with solving generalized equations [20, 21] of the form
where T is a maximal monotone multifunction from IR n into IR n and F is a continuously differentiable
function from an open
set\Omega oe dom(T ) into IR n . We recall that a monotone multifunction T
is a point to set mapping such that for each in the graph of T ,
where h\Delta; \Deltai denotes the inner product, T is maximal if its graph is not properly contained in that
of any other monotone multifunction and dom(T ) represents the effective domain of T .
To date, most of the algorithmic development for generalized equations has been focused on the
special case where T := NC , the normal cone to a convex set C, defined by
This case yields the generalized equation
This material is based on research supported by National Science Foundation Grant CCR-9157632, the Air Force
Office of Scientific Research Grant F49620-94-1-0036, and the Department of Energy Grant DE-FG03-94ER61915
y Mathematics Department, University of Colorado, Denver, Colorado 80217
z Computer Sciences Department, University of Wisconsin, Madison, Wisconsin 53706
Many problems from mathematical programming, equilibrium, complementarity and other fields
can be expressed in this form. For example, if F := rf , then (2) represents the first order necessary
optimality conditions for the problem
minimize f(x)
subject to x 2 C:
Another important instance of (2) is the variational inequality problem, which is to find z 2 C
such that
This problem is known to be equivalent to (2) (see [21]).
As a final example, we mention the complementarity problem; this has a wealth of applications
and appears in a variety of forms [13]. The standard nonlinear complementarity problem is to find
such that
It is well known [13, 15] that complementarity problems can be reformulated as variational inequal-
ities, and therefore can be treated in the context of the generalized equation (2).
A prominent tool for solving (2) is the normal map [8, 22, 26]. The normal map FC for a
function F
and a nonempty, closed, convex set C
oe\Omega is defined by
where -C (x) denotes the projection (with respect to the Euclidean norm) of x onto the set C. The
importance of the normal map lies in the fact that solving (2) is equivalent to finding a zero of
the normal map FC . Specifically, if x is a zero of the normal map, then z := -C (x) solves (2).
Conversely, if z is a solution to (2), then x := z \Gamma F (z) is a zero of the normal map. Thus, the
problem of solving the generalized equation (2), which is expressed with set-valued functions, is
reduced to finding a zero of a piecewise smooth, single-valued function.
Several algorithms have been developed based on this idea. Most of these algorithms are based
on the theory of piecewise linear homotopies given by Eaves [9]. The specialization of the general
algorithm given in [9] determines a zero of the normal map by tracing the zero curve of a piecewise
linear homotopy mapping. It is shown in [12] that Lemke's famous method [16] for solving linear
complementarity problems is conceptually equivalent to path following in a corresponding piecewise
linear system. This idea is easily extended to more general algorithms [10, 11]. Based on Eaves'
work, Cao and Ferris [3] analyzed an algorithm for solving affine (i.e. F (x) is affine) variational
inequality problems over polyhedral sets and showed that Lemke's method processed matrices in
the class PC [2].
For non-affine problems with C rectangular, Ralph [18] proposed a Newton-based algorithm
where at each iteration the Newton point is calculated by solving an affine variational inequality
(AVI) that is a linearization of the normal map equation at the current point. This approach
was developed computationally by Dirkse and Ferris [5, 6, 7] to produce PATH, an efficient and
robust code for solving mixed complementarity problems. A similar approach was developed by
Rutherford [24].
In this paper, we begin to generalize the above class of algorithms by removing the restriction
that T be the normal cone to a convex set. As a first step, in this paper we focus on solving the
affine generalized equation where F is an affine function and T is polyhedral (that is, the graph of
T is the union of finitely many convex polyhedrons).
Our strategy is, in essence, a generalization of the AVI algorithm of Cao and Ferris. We use
a generalization of the normal map to reformulate (1) as a zero finding problem of a piecewise
affine function; then we use the piecewise-linear homotopy framework of Eaves [9] to generate an
algorithm for determining zeros of piecewise-affine functions. We describe this algorithm in detail
in Section 2 and prove that under the assumption of coherent orientation, the algorithm finds a
zero after a finite number of steps.
The remainder of the paper describes how the algorithm is used to solve affine generalized
equations. In Section 3 we discuss a generalization of the normal map called the T-map. This
mapping, which to our knowledge was introduced by Minty [17], provides a means of reformulating
generalized equations involving operators T that do not necessarily correspond to the normal cone of
any set. After describing this reformulation, we focus on the case where T is polyhedral. This case
can be viewed as an extension of the special case where T := NC , with C a convex polyhedron. In
Section 4 we describe how the algorithm presented in Section 2 can be used to solve affine generalized
equations. In Section 5 we further specialize to the case where T is separable. Finally, in Section 6
we discuss how the algorithm can be applied to solve piecewise linear-quadratic programming
problems [25].
Some words about notation are needed. The notation that T is a point
to set mapping, or multifunction, which maps points in IR n to subsets of IR n . In discussing multi-
functions, we may refer either to a point to set mapping, T (\Delta), or to the graph of that mapping,
T , which is the set T := f(x; y) j y 2 T (x)g. The expression T \Gamma1 (\Delta) is defined as a set inverse; i.e.,
Tg. The effective domain of T , is defined
by dom(T ) := fxjT (x) 6= ;g.
In discussing matrices and vectors, subscripts are used to refer to components. For example
refer to the ith row, jth column, and (i; j)th entry of A, respectively. We may also
use index sets to refer to specific components. For example if g.
Further, we use the MATLAB notation of a comma to separate columns, and a semicolon to
separate rows. For example (x; y) is a row vector, whereas (x; y) is a column vector. Unless
otherwise indicated, all vectors are taken to be column vectors. Superscripts are used to indicate
an iteration count, index, or some other label for matrices and vectors. In contrast, for scalars,
sets, and functions, subscripts are used as labels.
For a set C, aff(C), int(C), ri(C), rec(C), dim(C), and ffi(\DeltajC ) refer to the affine hull, interior,
relative interior, recession cone, dimension, and indicator function of C respectively. (see [23] for
definitions of these terms).
2 Algorithm for Finding Zeros of M-PA Maps
Our first task is to describe an algorithm for finding zeros of piecewise affine functions. The
algorithm we present can be viewed as a generalization of Lemke's method for the linear complementarity
problem and of the algorithm for solving affine variational inequalities over convex
polyhedral sets that was described in [3]. The theoretical basis for the algorithm is derived from
the theory of piecewise-linear homotopies given in [9].
In order to describe the algorithm carefully, we need some preliminary definitions.
Definition 2.1 (cell) A polyhedral convex set oe ae IR n is called a cell. If then oe is
called a k-cell. Let oe := fxjAx - ag, where A 2 IR p\Thetan , and a 2 IR p , with p a nonnegative integer.
Then (p; A; a) is said to represent oe. If p is the smallest number for which a representation of oe
exists, then (p; A; a) is called a minimal representation of oe. A set - 2 IR n is called a face of oe if
for some set of indices ff ae g. If dim(-) = i, then - is called an
i-face of oe.
any cell has a minimal representation.
Definition 2.2 (piecewise affine) Let M be a collection of n-cells and let M :=
oe2M oe. A
is said to be piecewise-affine with respect to M, denoted M-PA, if for each
(i.e. the restriction of F to oe) is affine. If F is M-PA for some M satisfying the
above assumptions, then we say that F is piecewise affine.
Note that in the above definition, if M is convex, then the function F must be continuous on
M , because F must be single-valued on the boundaries between cells. Furthermore, in contrast to
the work of Eaves [9], M is not required to correspond to a subdivided manifold.
Definition 2.3 (function representation) Let M be a collection of n-cells in IR n , let F be a
M-PA function, and let oe be an n-cell of M. Let b oe 2 IR m and let B oe be an m \Theta n matrix.
is said to represent F on oe if F
We now describe an algorithm to find a zero of an M-PA function G, for a given collection of
cells M. We will assume that representations of the cells of M and of the map G have already
been constructed. The basis of the algorithm is to construct a piecewise affine homotopy mapping
F (x; -) with the following properties
1. is a zero of F if and only if x   is a zero of G.
2. A point direction (d 1 ; \Gamma1) is known such that - 1 - 0 and F
for all - 0.
The algorithm uses a method described by Eaves [9] to trace the zero curve of F , proceeding in the
direction (d 1 ; \Gamma1) from the starting point To prove that the algorithm finds a solution in
a finite number of steps, we restrict ourselves to the case where G is coherently oriented:
Definition 2.4 (coherent orientation) Let G be an M-PA map with representation (B oe ; b oe ) on
each oe 2 M. We say that G is coherently oriented if
is nonzero and constant for all oe in M, where
Since M is finite and
oe2M rec(oe), and further that there
is a oe such that int(rec(oe)) 6= ;. Choose d such that \Gammad 2 int(rec(oe)). Then for any x 0 in IR n , and
for all - sufficiently large, x
In the AVI algorithm described by Cao and Ferris, the cell oe and the direction d were constructed
by finding an extreme point x e of the set C. The cell was then given by oe := x e +NC (x e ), and the
direction d was chosen such that \Gammad was in the interior of NC (x e ). For our algorithm, rather than
constructing the cell and direction, we can rely instead on the fact that since IR
then for any direction d, there will be a cell oe d for which \Gammad 2 rec(oe d ). Note further that for each
cell oe, the boundary rec(oe) n int(rec(oe)) of rec(oe) has Lebesgue measure zero. Therefore, since the
number of cells is finite,
oe2M rec(oe) n int(rec(oe)) has measure zero. Thus, for almost all d, there
will be a cell oe d for which \Gammad 2 int(rec(oe d )).
Thus, if x 0 is any point in IR n , then for all - sufficiently large, x lie interior to the
cell oe d . In other words, the cell can be chosen simply by picking an arbitrary d and proceeding in
the direction \Gammad until a cell oe d is reached for which \Gammad is in the recession cone of oe d . For almost
all d (excepting a set of Lebesgue measure zero), \Gammad will be in the interior of rec(oe d ). We note,
however, that for some special cases, construction of an extreme point may still be preferable.
Once d and oe d have been identified, the homotopy map can be constructed. Let (B; b) be the
representation of G in oe d . Define a function F :
Note that F (x; exactly when Under the assumption that G is coherently oriented,
Then, since \Gammad 2 int(rec(oe d ))), there exists - 0 - 0 such that w(-) 2 int(oe d ); 8- 0 . Thus, for
0:
By choosing d, we see that F satisfies the conditions needed
for the homotopy map. We are now ready to state the algorithm, which is given in Figure 1. Note
that by normalizing d in the discussion above to be a unit vector, we can start the algorithm from
the point constructed above with oe 1 := oe d .
Some comments about Algorithm AGE are in order:
1. Most of the work in the algorithm is in step 8 where the direction (d
At the end of this section, in Theorem 2.13, we show that B is a rank-1 matrix. Thus,
an efficient implementation of the algorithm can be obtained by keeping the matrices B k in
factored form and performing rank-1 updates of the factors at each step of the algorithm.
2. At step 8 in the algorithm, there may be more than one possible choice of cells oe k+1 . However,
a lexicographic ordering, as described by Eaves [9, Section 15], can be used to resolve any
ambiguity concerning which cell to choose. The use of such a lexicographic ordering will
be assumed in the convergence proof, and will be presented in more detail in the discussion
preceding Lemma 2.9.
3. The requirement that
arbitrarily chosen to force the choice of d k+1 to be unique.
4. The requirement that x guarantees that the zero curve of F (x; -) :=
contains a ray, and therefore assures us that it will not have any loops. This
fact will be useful in our convergence proof. However, we shall also show that, under the
assumption of coherent orientation, v k is always negative, which by itself guarantees that no

Figure

1: Algorithm AGE
Given a finite collection of n-cells M such that
and an M-PA function G on IR n .
Let G have representation (B
Repeat for
0g.
output("ray termination"); return.
Else
output("solution found at", x k+1 ); return.
Else
determine oe k+1 (possibly using lexicographic ordering),
d k+1 , and v k+1 such that
d k+1 points into oe k+1 from x k+1 ,
and oe
loops occur. Thus, under the assumption of coherent orientation, it is not necessary to find a
ray start. However, in future work, we will prove convergence for a broader class of problems,
in which case the ray start requirement will be useful.
The next few pages are devoted to proving the following convergence theorem:
Theorem 2.5 Let M be a finite collection of n-cells whose relative interiors are disjoint and whose
union is IR n . Let G be a coherently oriented, M-PA function. Algorithm AGE, using lexicographic
ordering, terminates after finitely many steps with a zero x   of G.
Proof (Outline) There are three main parts to the proof. First, as Lemma 2.9, we will show that
the algorithm terminates at a solution if M is a subdivision of IR n (see Definition 2.6). Second, in
Lemma 2.11, we will show that even if M is not a subdivision of IR n , there is a refinement (see
Definition 2.10) N of M that is a subdivision. Finally, we show in Lemma 2.12 that if a subdivision
N is a refinement of M, then running the algorithm using N will generate exactly the same path
as would be generated by using M. Thus, the fact that the algorithm terminates at a solution
using N guarantees that it will terminate at a solution using M.
We now prove the three lemmas mentioned above. At this point, we recommend that the
impatient reader skip ahead to Theorem 2.13. Our proof technique is based on the work of Eaves
[9]. Eaves' analysis relies heavily on the notion of a subdivided manifold:
Definition 2.6 (subdivided manifold) Let N be a set in some Euclidean space, and let N be a
finite or countable collection of n-cells in that space such that
oe2N oe. Let ~
N be the collection
of all faces of elements of N . (N; ~
N ) is a subdivided n-manifold if
1. any two n-cells of N are either disjoint or meet in a common
2. each point of N has a neighborhood meeting only finitely many n-cells of N ;
3. each (n \Gamma 1)-cell of ~
N lies in at most two n-cells;
If (N; ~
N ) is a subdivided n-manifold for some subdivision N , we call N an n-manifold and we call
N a subdivision of N .
The following lemma shows that when in Definition 2.6 is redundant. This
result was proved by Robinson [22] in the proof of Proposition 2.4. While Robinson's proposition
is stated for the normal manifold, his proof is valid for general subdivisions of IR n .
Lemma 2.7 If N is a collection of cells whose union is IR n and if N satisfies 1 and 2 of Definition
2.6, then N is a subdivision of IR n .
The next step in our analysis is to prove that the algorithm works whenever M is a subdivision
of IR n . In this case, by defining S := foe \Theta IR + joe 2 Mg, we see that S is a subdivision of IR n \Theta IR
and further that F is S-PA. The starting point of the algorithm lies interior to the cell
of S. Further, the ray f(x lies within j 1 . Let ~
S be the
collection of all faces of elements of S. Algorithm AGE is then seen to be equivalent to the algorithm
described by Eaves [9, Section 10.2], with the following relationships between the algorithms:
Eaves' Algorithm Algorithm AGE
To discuss the behavior of this algorithm in more detail, we need some definitions from [9].
Definition 2.8 (regularity) Let (N; ~
N ) be a subdivided (n be the collection
of n-cells in ~
be a N-PA map. A point x in N is said to be degenerate
(otherwise regular) if x lies in a cell oe of ~
N with dim(F (oe)) ! n. A value y in F (N) is said to be
a degenerate value (otherwise a regular value) if F \Gamma1 (y) contains a degenerate point.
Note that if y is a regular value, then F \Gamma1 (y) cannot intersect any k-cells of S with k ! n.
By the assumption of coherent orientation, G is one-to-one in every n-cell of M. Thus,
of S. Since the starting point of the algorithm
is interior to j 1 , it is a regular point of F . According to [9, Theorem 15.13], since S is finite, the
algorithm generates, in finitely many steps, either a point in the boundary of IR n \Theta IR
or a ray in F \Gamma1 (0) different from the starting ray. In the first case, we know that -
the boundary of IR n \Theta IR + is IR n \Theta f0g. It then follows, from our earlier remarks that x   satisfies
Therefore, to guarantee that the algorithm finds a solution, we need only show that it
cannot produce a ray different from the starting ray.
We first consider the case when 0 is a regular value of F . In this case, by [9, Theorem 9.1],
F \Gamma1 (0) is a 1-manifold which is subdivided by sets of the form j
cannot intersect any k-cells with k ! n, each point on F \Gamma1 (0) is in at most two (n + 1)-cells of S.
Thus, in step 8 of the algorithm, the choice of oe k+1 is well-defined. (The only difficulty would be
if lies in only one (n so that no oe k+1 could be selected. But in this case,
would be a boundary point of IR n \Theta IR + . Thus, - so the algorithm would have
terminated in step 5.)
be the direction of the path within the (n of S, and let G have representation
on the n-cell oe k of M. Then by [9, Lemma 12.3], the curve index, given
by
is constant everywhere along the path. Since v for the starting direction (d
G is coherently oriented, it follows that v k is negative in each cell that the path enters. But this
means that the parameter - decreases strictly in each cell. Thus, after finitely many steps, we must
have
When 0 is a degenerate value of F , F \Gamma1 (0) may intersect a k-cell of S with k ! n. Thus, in
step 8 of the algorithm, there may be multiple choices for which cell oe k+1 to enter next. To address
this problem, a lexicographic ordering can be used to resolve ambiguities concerning which cell the
path will enter. Such a scheme is conceptually equivalent to solving a perturbed problem, which
we now describe.
be an (n+1) \Theta n matrix such that [X; d 1 ] is of rank (n+1). Define the vector
(note: the superscripts here refer to exponentiation). Define
Algorithm AGE is interior to j 1 , then
small enough ffl. Further, since (\Gammad
the starting conditions needed to apply the algorithm
to the perturbed problem given by
where p(ffl) := F
Y is an invertible n \Theta n matrix, so that by [9, Lemma 14.2], p(ffl) is a
regular value for all ffl sufficiently small. Thus, by the arguments given above for regular values,
using Algorithm AGE to solve the perturbed problem will, after a finite number of steps J , produce
a point (x J (ffl)) such that G(x J
be the sequence of points generated by the algorithm for the perturbed prob-
lem. By the discussion in [9, Section 15], there is a sequence of matrices X k 2 IR (n+1)\Thetan and a
sequence of points ffl. The points
are exactly the sequence of points generated by the algorithm for solving the unperturbed
problem using the lexicographic ordering. Since the algorithm terminates after J steps for all small
ffl, we see that - J It follows that - further that G(x J
Thus, using a lexicographic ordering, the algorithm finds a solution after a finite number of steps.
We have proved the following lemma:
Lemma 2.9 Let M be a subdivision of IR n and A T be a coherently oriented, M-PA function.
Algorithm AGE, using lexicographic ordering, terminates after finitely many steps with a zero x
of G.
We now address the case where M is not a subdivision of IR n . We begin by proving that M
can be refined to produce a subdivision.
Definition 2.10 (refinement) Let M and N be finite collections of n-cells. N is said to be a
refinement of M if each cell oe of M is the union of a finite collection of cells - i of N , and if each
cell of N is contained in some cell of M.
The following lemma is proved by Hudson [14, Lemma 1.5], however, using different nomencla-
ture. In particular, the term "subdivision" is used in place of our term "refinement".
Lemma 2.11 Let M := fC i g be a collection of J ! 1 n-cells which covers IR n . There exists a
subdivision N of IR n such that N is a refinement of M.
We now show that using N , the algorithm follows the same path as it would using M.
Lemma 2.12 Let G be an M-PA function, where M is a finite collection of relatively disjoint
n-cells whose union is IR n . Let N be a refinement of M such that N is a subdivision of IR n . Then
Algorithm AGE, using lexicographic ordering, will find a solution x   to in a finite number
of steps. Furthermore, the sequence of points generated by the algorithm using M is a subsequence
of the points that would be generated using N .
Proof Consider first running the algorithm using N instead of M. By Lemma 2.9, the algorithm
will terminate after some finite number of steps J . The algorithm will visit a sequence of n-
cells f- k g ae N , and will generate a sequence of points f(x k ; - k )g and directions f(d k ; v k )g, for
be the unique cell in M that contains - 1 . Then for
be the smallest index greater than j i\Gamma1 such that - j i
be the unique
cell in M that contains -
. Let K be such that j This process defines a sequence of cells
We will show that if the algorithm is run using M, then the sequence of points f(-
generated by the algorithm satisfies the equation (-
for each i. Thus, (-
so the algorithm finds a solution after a finite number of steps.
be the sequence of directions chosen by the algorithm using M. Clearly, since the
algorithm is started at the point in the direction (d 1 ; \Gamma1), the following is true: (-
), and the first cell visited by the algorithm is oe 1 .
We now proceed by induction: Assume that (-
), and that,
using M, the ith cell visited by the algorithm is oe i . We shall prove that (-
), and that the (i 1)st cell visited by the algorithm is oe i+1 .
be the representation of G on oe i . This is also the representation of G on - k whenever
. Thus, in step 8 of the algorithm using N , the direction (d
entering cell - k+1 must satisfy
coherently oriented, B i is invertible. Further,
by our earlier discussion, v k+1 is negative. Thus, the direction is uniquely determined by the
representation. In particular, (d
From this it
is clear that x j i+1 lies on the ray f- is on the
boundary of oe i .
If the ray f- i (')j' - 0g contains a point in the interior of oe i , then the ray cannot be extended
past x j i+1 without exiting oe i . Thus, x g. In other words,
If the ray f- i (')j' - 0g does not contain an interior point of oe i , then we must resort to the
lexicographic ordering to prove that x j
are relatively disjoint convex
sets, there exists a separating hyperplane H i defined by a vector c i , and a scalar ff i such that
. Suppose we run the algorithm using N
to solve the perturbed problem G ffl (x) := defined by (6). Then,
small enough, the algorithm will visit the same sequence of cells f- k g as it visits in the
unperturbed problem. Also, by our earlier discussion, the algorithm will generate the sequence of
points is a fixed sequence of matrices.
Since 0 is a regular value of G ffl , dim(G ffl (- k
k. Thus, G \Gamma1
ffl (0) contains
only one point in - k
namely x k+1 . Therefore, the direction d k+1 must point into the interior
of - k+1 .
By similar arguments as before, x j i+1 lies on the ray f- i
But, since d k+1 points into the interior of - j i
, this ray must contain a point -
x in the interior of
. It follows that c i ? d
Thus, even for the unperturbed problem, the ray - i (') cannot be extended past the point x
without crossing the hyperplane H i , and thereby exiting oe i . Thus, x
Finally, note that for all small ffl, the point x j i+1 (ffl) is a regular point, so - (j i+1 \Gamma1) and - j i+1
are the only n-cells of N that contain x j i+1 (ffl). Thus, oe i and oe i+1 are the only n-cells of M that
contain x j i+1 (ffl). Thus, for all small ffl, the algorithm, using M will enter cell oe i+1 at the next
iteration. But this means that using lexicographic ordering the algorithm will enter cell oe i+1 next
when solving the unperturbed problem. Finally, since the representation of G on oe i+1 is identical
to the representation of G on - j i+1
, we must have
The lemma is now proved by induction.
This completes the proof of Theorem 2.5. Our final task in this section is to establish the claim
made in Comment 1 following Algorithm AGE.
Theorem 2.13 Under the hypothesis of Theorem 2.5, let foe k g be the sequence of cells chosen in
Step 8 of Algorithm AGE using lexicographic ordering, and let (B
has rank 1.
Proof Using lexicographical ordering, the algorithm will choose the same cell oe k+1 in step 8 as
it would when solving the perturbed problem for small ffl. However, 0 is a regular value for the
perturbed problem, so - k := oe k
must have dimension n \Gamma 1. Now, for any two points
Thus, dim
3 The T-map
The T-map, denoted F T , is a generalization of the normal map that is formed by replacing the
projection operator -C in (3) by the resolvent operator Specifically, the T-map
is given by
We assume throughout that T is a maximal monotone operator. In this case, Minty [17] showed
that P T is a continuous, single-valued, nonexpansive function defined on all of IR n . Since the image
of P T is dom(T ) (which is contained in the domain of F
,\Omega\Gamma3 it follows that F T is a single-valued
function defined on all of IR n .
By [1, Example 2.1.2], I + T is monotone, and therefore P T is monotone. We now show that
solving GE(F; T ) is equivalent to finding a zero of F T .
Theorem 3.1 Given a maximal monotone multifunction
be defined by (7). If x is a zero of F T , then z := P T (x) solves GE(F; T ).
Conversely, if z solves GE(F; T ), then x := z \Gamma F (z) is a zero of F
Proof Suppose F T
Conversely, suppose \GammaF (z) 2 T (z) and let x := z \Gamma F (z). Then x
So far, we have not made any assumptions on T other than that it is maximal monotone. We
now focus on the case where T is polyhedral.
Definition 3.2 (polyhedral) A multifunction T is polyhedral if its graph is the union of finitely
many polyhedral convex sets.
Our first task will be to show that, for polyhedral T , the resolvent operator
a piecewise-affine map.
Lemma 3.3 A single-valued multifunction whose graph is a convex polyhedron is
affine on dom(T ).
Proof Assume dom(T ) 6= ;. (Otherwise the lemma is true vacuously). Since the graph of T is a
polyhedron, T can be written as
nonnegative integer. Let K := fijA Tg. In words,
K is the set of row indices for which the corresponding constraint is active for all points in T .
We first establish the fact that ker B f0g. To do this, let H := fiji 62 Kg. Then for
each
is the
cardinality of the index set H. Note that (~x; ~
y) is a convex combination of points in T and is
therefore also in T . Further, A i\Delta ~
. But since T is single-valued, -
Now, by the definition of K, we have (x; Conversely, suppose
9-y such that (x; -
. But this means
that A implies that -
f0g. That is -
y. We have thus
shown that
Finally, since ker B has a left inverse R 2 IR m\Thetap . Thus, for x 2 dom(T ),
So T is an affine function on dom(T ).
Theorem 3.4 Given a maximal monotone polyhedral multifunction , the resolvent
operator affine function on all of IR n .
Proof Since T is polyhedral, I +T is also polyhedral [19] and therefore so is P
is a finite collection of polyhedral convex sets. Let C i be the projection of \Gamma i
onto the domain of P T (i.e., C
is defined on all of IR n ,
is closed, its
complement, nM := IR n n M , is open. Thus, nM is either the empty set, or it has nonempty
interior. But nM ae S
Thus, nM has no interior. In other words
To show that P T is M-PA, all that is needed is to show that for each C i 2 M, the restriction
of P T to C i is affine. However, since P T is single-valued, the graph of P T restricted to C i is simply
the convex polyhedral set \Gamma i . By Lemma 3.3, P T is affine on C i .
Corollary 3.5 If T is polyhedral and F is affine, then the T-map, F T , defined by (7) is piecewise
affine.
4 Affine Generalized Equations
We now show how to apply the algorithm of Section 2 to construct an algorithm to solve the affine
generalized equation:
where A 2 IR n\Thetan , a 2 IR n , and T is a maximal monotone polyhedral multifunction. For this
problem, the T-map is given by
As was shown in Section 3, for polyhedral T , A T is piecewise affine with respect to some finite
collection M of n-cells whose union is IR n . Thus, to complete the description of the algorithm for
affine generalized equations, it remains to show how to generate the representations.
The task of constructing M is dependent upon how T is described. For example, in [22], T is
taken as the normal cone NC to a polyhedral convex set C. M is then chosen to be the normal
manifold, which is defined in terms of the nonempty faces F i of C. Specifically, the cells of the
normal manifold are defined by
is the common value of N F i
for x 2 ri(F i ). This particular choice of cells leads to the
algorithm given in [3].
For more general T , we assume that T is described as the union of a finite collection of polyhedral
convex sets C i . We can then describe P T as the union of the sets S i g.
By projecting each S i onto the domain of P T , we produce a collection of sets
Since we know dom(P T
To provide an example of this process, we return to the case where . Observe that
fxg \Theta N
Thus, we see that NC is the union of the polyhedral convex sets
It follows that the process described above yields the normal manifold.
Robinson [22, Proposition 2.4] proved that the normal manifold is a subdivision of IR n . However,
in general, the collection of cells M generated by the above process is not a subdivision. This can
be demonstrated by the following example. Let
and let T :=
that T is simply the zero mapping, and is thus a maximal monotone
multifunction. However, employing our procedure for constructing M, we obtain oe
. Since oe 1
is not a face of oe 1 , we see that M := foe is not a subdivision of IR n .
Since P T is single-valued, then by Lemma 3.3, P T is affine on each cell oe i 2 M. A representation
of A T on each cell is then given by (9). In order to have a workable description of these affine maps,
it would appear necessary to exploit the underlying structure of T . One such case is the subject of
the next section.
A particularly important class of affine variational inequalities is that for which the set C is rect-
angular, i.e., C is defined by the constraints
l - z - u
where l and u are vectors in IR n , with l problem
class has a number of features that are very attractive for pivotal algorithms similar to Algorithm
AGE. In particular, the cells of linearity of the normal map are rectangular, and furthermore the
normal map itself takes on a very simple form. Specifically, for an affine function F (z) := Az
the matrix used to represent the normal map on any cell is formed simply by replacing some of the
columns of A by the corresponding columns of the identity matrix.
Rectangular variational inequalities are also attractive from a theoretical standpoint. In par-
ticular, if at least one of l i and u i is finite for each i, then the normal map is coherently oriented
with respect to C if and only if A is a P-matrix.
Definition 5.1 ([4]) A matrix A is said to be a P-matrix if all its principal minors are positive.
Note that when C is rectangular, then NC
that we can extend the notion of rectangularity to generalized equations by requiring that the
multifunction T be separable, i.e., it is of the form
where for each i, T i is a maximal monotone polyhedral multifunction from IR to IR. With such a T ,
we shall see that the cells of linearity of the T-map A T are rectangular.
We begin by looking at the resolvent operator . Note that
where for each i, P T i
is a continuous piecewise affine function, it follows that
is a a continuous piecewise affine function from IR into IR. Let k i be the number of breakpoints
of
. Then, for some strictly increasing sequence of breakpoints f- ij
of coefficients fd ij
d
Note that since P T is monotonic and nonexpansive, 0 - d ij - 1.
The breakpoint sequence defines a subdivision of IR given by M
We then define a subdivision of IR n by
defined by oe [j 1 ;j 2 ;:::;j n
\Theta
Clearly, P T (and therefore A T ) is M-PA. This establishes our earlier statement that the cells of
linearity of A T are rectangular. For each cell oe [j 1 ;j 2 ;:::;j n ] of M, define a diagonal matrix D [j 1 ;j 2 ;:::;j n ]
by
. Further, define the vector b [j 1 ;j 2 ;:::;j n
represented by (D [j 1 ;j 2 ;:::;j n the T-map is given
by
A T
\Deltan
Thus, we see that the matrix M [j 1 ;j 2 ;:::;j n ] which represents A T on oe [j 1 ;j 2 ;:::;j n ] has columns which
are convex combinations of columns of A and the corresponding columns of I .
We now set about proving the main result of this section. Namely, if A is a P-matrix, then A T
is coherently oriented for any separable polyhedral maximal monotone multifunction T . We first
need to prove two technical lemmas.
Lemma 5.2 If A and B are n \Theta n matrices where B is rank-1 such that det(A) ? 0 and
Proof
(j 1 ;:::;j n )
where the summation is taken over all possible choices of (j
is either A \Deltai or
-B \Deltai . Since B is rank-1, the determinants in the above sum are zero for all choices that include at
least two columns of -B. Thus,
Thus, is an affine function of -, which is positive at Thus, it is
positive for all - 2 [0; 1].
Lemma 5.3 Let A be an n \Theta n matrix and let fB be a collection of rank-1 n \Theta n matrices.
choices of -
for all choices of - i 2 [0; 1].
Proof (By induction). The lemma is true for suppose the lemma is
true for all k ! m, we shall prove the lemma true for
Suppose is a collection of rank-1 n \Theta n matrices such that
choices of - or 1. Let -
A := A +B m . Then -
A and fB
the conditions of the lemma for
Similarly, with -
A := A, we have
From these two results, we see that if we let ~
A := A
A and B m
satisfy the hypotheses for Lemma 5.2. Thus, for -m 2 [0; 1]
Theorem 5.4 If A is a P -matrix, then for any separable maximal monotone polyhedral multi-function
T , the T-map A T defined by (9) has the property that in any cell of linearity, the matrix
representing A T has positive determinant. In particular, A T is coherently oriented.
Proof Let A T have the representation ( -
b) in the n-cell oe. By the our earlier discussion, -
A can be
formed by replacing columns of A by a convex combination of columns of A and the corresponding
columns of the identity matrix. Thus, the matrix is of the form
\Deltai . Observe that B i is a rank-1 matrix.
Since A is a P-matrix, the matrix formed by replacing an arbitrary set of columns of A by corresponding
columns of the identity matrix has positive determinant. Thus, the matrices
satisfy the hypotheses of Lemma 5.3. Thus, by Lemma 5.3, det( -
Corollary 5.5 If A is a P-matrix and T is a separable maximal monotone polyhedral multifunction,
then using lexicographic ordering, Algorithm AGE will find a solution to A T in a finite
number of steps.
6 Piecewise Linear-Quadratic Programming
We conclude by giving an example of a well known problem in mathematical programming that
can be solved using the technique we have presented. The piecewise linear-quadratic programming
problem (PLQP) is given by
S f1g are convex piecewise linear-quadratic
defined below.
Definition 6.1 A function f :
S f1g is piecewise linear-quadratic if domf is closed and
convex and there exists a finite subdivision M of dom(f) such that for each oe 2 M, f joe is a
quadratic function.
Note that domf is polyhedral, and further that since the cells in the subdivision are closed, f is a
continuous function on domf .
The optimality conditions for PLQP are stated by the relation
where @h is the convex subdifferential operator defined by
Under an appropriate constraint qualification (i.e. ri(A(dom(f)))
T ri(dom(OE)) 6= ;), it follows that
Thus, for the optimality conditions to be satisfied, there must be an x 2 dom(f) and y 2 @OE(Ax)
such that \GammaA ? y 2 @f(x). By [23, Theorem 23.5], the first statement is equivalent to
where OE   is the conjugate of OE. The optimality conditions are then
Thus, if we define
A :=
the optimality conditions for PLQP can stated as the generalized equation
The fact that T is polyhedral was shown in [25]. Thus, the optimality conditions for the piecewise
linear-quadratic program can be expressed as an affine generalized equation, which can then be
solved using our algorithm.

Acknowledgement

The authors would like to thank Stephen Robinson for constructive comments, suggestions and
pertinent references that greatly improved the presentation of the material given in this paper.



--R

Op'erateurs Maximaux Monotones et Semi-Groupes de Contractions dans les Espaces de Hilbert
PC matrices and the linear complementarity problem.
A pivotal method for affine variational inequalities.
The Linear Complementarity Problem.
Robust Solution of Mixed Complementarity Problems.
The PATH solver: A non-monotone stabilization scheme for mixed complementarity problems
A pathsearch damped Newton method for computing general equilibria.
On the basic theorem of complementarity.
A short course in solving equations with PL homotopies.
Computing stationary points.
Computing stationary points
Equivalence of LCP and PLS.
Engineering and economic applications of complementarity prob- lems
Piecewise Linear Topology.
Generalized complementarity problem.
Equilibrium points of bimatrix games.

Global convergence of damped Newton's method for nonsmooth equations
Some continuity properties of polyhedral multifunctions.
Generalized equations and their solution: Part I: Basic theory.
Generalized equations.
Normal maps induced by linear transformations.
Convex Analysis.
MILES: A mixed inequality and nonlinear equation solver.
On Monotropic Piecewise Quadratic Programming.
A note on computing equilibria in economies with activity analysis models of production.
--TR
normal map;homotopy;generalized equations;piecewise affine