Chapter 1

VARIATIONAL GEOMETRY AND EQUILIBRIUM

M. Patriksson

Department of Mathematics Chalmers Univeristy of Technology SE-412 96 Gothenburg, Sweden

mipat@math.chalmers.se

R. T. Rockafellar

Department of Mathematics University of Washington Seattle, WA 98195-4350, USA

rtr@math.washington.edu

Abstract Variational inequalities and even quasi-variational inequalities, as means of expressing constrained equilibrium, have utilized geometric properties of convex sets, but the theory of tangent cones and normal cones has yet to be fully exploited. Much progress has been made in that theory in recent years in understanding the variational geometry of nonconvex as well as convex sets and applying it to optimization problems. Parallel applications to equilibrium problems could be pursued now as well.

This article explains how normal cone mappings and their calculus offer an attractive framework for many purposes, and how the variational geometry of the graphs of such mappings, as nonconvex sets of a special nature, furnishes powerful tools for use in ascertaining how an equilibrium is affected by perturbations. An application to aggregated equilibrium models, and in particular multi-commodity traf�c equilibrium, is presented as an example.

Keywords: variational geometry, normal cones, tangent cones, variational inequalities, quasivariational inequalities, equilibrium, traf�c, multi-commodity �ow, variational analysis, perturbations

1. INTRODUCTION

The concept of equilibrium has long had a close connection with optimization. Traditionally, an equilibrium point x̄ has often been construed as a solution to a vector equation F (x) = 0. In that case, if F is the gradient ∇f of a function f, the equilibrium satis�es ∇f(x̄) = 0 and is said to be described by a �variational principle.� The function f might have a local minimum or maximum at x̄, and indeed variational principles have often centered on minimum energy, but of course x̄ could merely be a �stationary point� of f.

The connection between equilibrium and optimization has really always been on this level. Equilibrium conditions typically are properties that resemble �rstorder conditions for optimality. They do correspond to local optimality in many cases, or at least to a competitive balance among various optimizing agents, but not in every case.

The question of how to account for constraints in formulations of equilibrium has gained in importance in modern times. Some constraints can be handled through the introduction of Lagrange multipliers. Others, though, �t poorly with classical techniques and demand new mathematics in order to achieve satisfactory treatment. Anyway, Lagrange multipliers are something �secondary.� The basic issue is how to relativize an equilibrium to a set C, but there is great diversity in the ways that C might be speci�ed. Such diversity should somehow be accommodated in a �primary� manner.

A major advance came with the notion of a variational inequality over a convex set C, whatever the structure of that set. This innovation, in the era when convex analysis was starting up, provided a broad approach to generalized constraints of convex type. Moreover, through restatements in a Lagrangian setting, it supported treatment of some constraints of nonconvex type as well� provided that those constraints could be represented by multipliers which in turn would be incorporated among the equilibrium variables.

Since then, work on variational inequalities has led to many successes. Extensions such as to quasi-variational inequalities have carried this further. But equilibrium theory has yet to take advantage of some of the recent progress in optimization, where much has been learned about how to handle very general classes of sets C directly, without necessarily introducing multipliers or relying on excursions through convex analysis.

Variational Geometry and Equilibrium 3

The key to those accomplishments in optimization theory has come from variational geometry, i.e., the study of tangent cones and normal cones to a general set C, their properties, relationships, and calculus. Variational geometry has proved to be valuable not only in characterizing optimality but also in understanding how solutions are affected by parametric perturbations. In the latter role it has required abandoning the preconception from convex analysis that tangent cones and normal cones, once they have �rightly� been de�ned, should themselves always be convex.

The aim of this article is to indicate how ideas of variational geometry can more fully be put to use in understanding equilibrium, thereby perhaps opening new avenues of development as well as consolidating some of the theory that already exists.

We begin by reviewing the way that a variational inequality re�ects the concept of a normal cone in convex analysis. We go on then to discuss normal cones to nonconvex sets as they are now understood, demonstrating that quasivariational inequalities correspond, at least sometimes, to normal cones in that wider framework. The crucial object in both cases is a set-valued normal cone mapping N_{C}, yet such mappings are often quite out of sight when people speak of variational or quasi-variational inequalities.

Properties of a normal cone mapping can be very powerful, especially in sensitivity analysis of solutions. In fact the variational geometry of the graphs of normal cone mappings is the mainstay for results in that direction.

We illustrate how that operates by means of a formula for perturbations of equilibrium in a traf�c model where the set C is convex, but instead of being speci�ed directly by equations or inequalities, is expressed as a sum of sets with those speci�cations. We show also, in a different example, how even nonconvex sets C can be amenable to perturbation treatment through their associated normal cone mappings N_{C}.

2. VARIATIONAL INEQUALITIES AND NORMALS TO CONVEX SETS

For simplicity, we focus in this article on equilibrium models in the space IR^{n} and, in other respects too, forgo possibilities for greater generality in order to concentrate on the main points of our discussion.

Let F : IR^{n} → IR^{n} be a continuous mapping (single-valued) and let C ⊂ IR^{n} be a nonempty, closed, convex set. The variational inequality for F over C, with solution x̄, is customarily posed as the condition

x̄ ∈ C,  ⟨F (x̄), x − x̄⟩ ≥ 0 for all x ∈ C.  (1)

In this formulation, a variational inequality is comprised of an in�nite collection of linear inequalities which must be satis�ed by x̄ in addition to the condition x̄ ∈ C, which itself could of course in turn be represented by an in�nite collection of linear inequalities, inasmuch as any closed convex set is the intersection of a collection of closed half-spaces. Nobody insists on always expressing a convex set that way, however, since that would not be convenient and the picture of the set and its geometry could get lost. For the same reason,

(1) can fall short of being the best way to think about a variational inequality, even though it is the source of the �inequality� part of the name.

A better approach is to make use of the normal cone concept in convex analysis [1], [2], which captures the inequality aspect of (1) more conducive to geometric thinking and open-ended calculus. A vector v is said to be normal to the convex set C at a point x̄ if x̄ ∈ C and

⟨v, x − x̄⟩ ≥ 0 for all x ∈ C.  (2)

The set of all such vectors is denoted by N_{C}(x̄) and is called the normal cone to C at x̄. It is indeed a cone (a set containing the origin and including for each of its elements v ≠ 0, if any, the ray {λv | λ ≥ 0}). Moreover it is closed and convex. For points x̄ ∉ C, it is expedient to take N_{C}(x̄) = ∅ so as to get a fully de�ned set-valued normal cone mapping N_{C} : IR^{n} → → IR^{n}. This mapping can be described directly by the optimization rule

v ∈ N_{C}(x̄) ⟺ x̄ ∈ argmax_{x∈C} ⟨v, x⟩.  (3)

For v ≠ 0, the relation v ∈ N_{C}(x̄) can also seen pictorially as meaning that v is an outward normal to a supporting half-space to C at x̄.

In terms of the normal cone mapping N_{C}, the variational inequality condition in (1) can be recast in the form

−F (x̄) ∈ N_{C}(x̄), or F (x̄) + N_{C}(x̄) ∋ 0,  (4)

with (3) then providing the popular interpretation of a variational inequality as corresponding to optimization of a linear form.

Although the re-expression in (4) might, at �rst, seem to provide nothing much beyond (1), it shifts the perspective from a system of inequalities to �nding a �zero� of a set-valued mapping F + N_{C}. It turns attention to the nature of that mapping and the geometry of its graph. Furthermore, it provides guidance to generalization by suggesting that, when the need arises to go beyond the case of a convex set C, the central issue ought to be what de�nition of normality to adopt in the absence of convexity.

The graph of F + N_{C} depends heavily on the graph of N_{C}. One has y ∈ (F + N_{C})(x) if and only if y − F (x) ∈ N_{C}(x), so that

gph(F + N_{C}) = M^{−1}(gph N_{C}) for M : (x, y) ↦ (x, y − F (x)). (5)

The mapping M is a homeomorphism of IR^{n} with itself, since F has been assumed to be continuous, and it is actually a diffeomorphism when F is smooth (i.e., continuously differentiable). Therefore, the geometry of the graph of N_{C} holds critical information about the variational inequality.

What can be said about that geometry? First and foremost is the fact that gph N_{C} is a graphically Lipschitzian manifold in a global sense. A set is said to be such a manifold of dimension d at one of its points if there is a smooth change of coordinates that transforms it, locally around that point, into the graph of a Lipschitz continuous mapping from d coordinates into the remaining coordinates. In the case of N_{C}, a change of coordinates that is well known to have this effect is

(x, v) ⟷ (z, w) with z = x + v, w = x − v.

It sets up gph N_{C} as the graph of the mapping J : z ↦ (P_{C}(z), z − P_{C}(z)), where P_{C} is the nearest-point projection mapping onto C:

gph N_{C} = {(P_{C}(z), z − P_{C}(z)) | z ∈ IR^{n}}.  (6)

Indeed, the indicated mapping J is one-to-one between z ∈ IR^{n} and (x, v) ∈ gph N_{C} and is globally Lipschitz continuous in both directions. Thus, gph N_{C} is globally a graphically Lipschitzian manifold of dimension n within IR^{2n}.

The representation in (6) is the Minty parameterization of gph N_{C}. It stems from N_{C} being a maximal monotone mapping. Recall that a set-valued mapping S : IR^{n} → → IR^{n} is called monotone if ⟨v′ − v, x′ − x⟩ ≥ 0 whenever v ∈ S(x) and v′ ∈ S(x′), and is said to be maximal in this respect if there is no monotone mapping S′ : IR^{n} → → IR^{n} such that gph S′ ⊃ gph S, gph S′ ≠ gph S. Minty showed in 1962 [3] that the graph of any maximal monotone mapping has a Lipschitz continuous parameterization like (6), except with a certain other mapping P in place of the projection P_{C}. The maximal monotonicity of N_{C} is a property shared with the subgradient mappings associated with lower semicontinuous, proper, convex functions in general and also enjoyed in many other situations, but we will not go into that here. (See [2, Chapter 12], for instance.)

On the basis of (5), the graphically Lipschitzian property of N_{C} carries over locally to F + N_{C} when F is smooth. We will extract more from this later when we turn to the sensitivity analysis of solutions to a variational inequality. Obviously, for any property of N_{C} to be usable in practice there must be machinery for working out in detail how the property is manifested in terms of the speci�c structure of C. We will come back to this once we have passed beyond convexity to broader versions of variational geometry.

Another set-valued mapping that deserves mention here in connection with N_{C} is the tangent cone mapping T_{C} of convex analysis. The tangent cone to C at a point x̄ ∈ C is

T_{C}(x̄) = cl {w = λ(x − x̄) | x ∈ C, λ ≥ 0}.  (7)

Like N_{C}(x̄), it too is a closed convex cone, and moreover these two cones are polar to each other:

\begin{aligned}N_{C}(x̄) & = \{v | ⟨v, w⟩ ≤ 0, ∀w ∈ T_{C}(x̄)\}, \\ T_{C}(x̄) & = \{w | ⟨v, w⟩ ≤ 0, ∀v ∈ N_{C}(x̄)\}. \end{aligned}  (8)

The question of how far this polarity persists when normal cones and tangent cones are generalized will occupy us as we proceed.

3. QUASI-VARIATIONAL INEQUALITIES AND NORMALS TO GENERAL SETS

Suppose now that the set C ⊂ IR^{n}, although still nonempty and closed, is not necessarily convex. What conditions on C and F might be suitable candidates as replacements for a variational inequality? One idea has been a quasi-variational inequality. It depends on the intermediary of a mapping D that assigns to each x ∈ C a set D(x) containing x. With respect to such a mapping D, for which different choices may be admitted, the quasi-variational inequality for F over C, with solution x̄, is the condition

x̄ ∈ C,  ⟨F (x̄), x − x̄⟩ ≥ 0 for all x ∈ D(x̄).  (9)

Usually the requirement x̄ ∈ D(x̄) is added to the statement (9), but we will assume here that

x ∈ D(x) for all x ∈ C.  (10)

In principle no generality is lost by this assumption�for conceptual purposes� since we can arrange for it be satis�ed by replacing C in that situation by its subset C′ = {x ∈ C | x ∈ D(x)}. Although possible �xed-point aspects of a quasi-variational inequality in the more usual formulation are suppressed from view by this device, we can hope then to focus more clearly on the equilibrium aspects related to optimization. The theory of existence of solutions to a quasivariational, posed in our reduced manner, could well require a careful utilization of �xed-point technology through representing our C as the truncation C′ of some larger, possibly convex set C to which the mapping D can be extended, but that is a separate matter which need not distract us from our present goals.

In the special case where D(x) = C for all x ∈ C, the quasi-variational inequality reverts to a variational inequality. Beyond that, as long as the mapping D is closed-convex-valued, (9) can aptly be viewed as a roving variational inequality for F over a set that shifts with the solution candidate. This is appealing especially when D(x) is envisioned as a local approximation to C at x.

For other insights, it will be helpful instead to think of a quasi-variational inequality as maybe involving a �proposal for generalized normality,� at least in some cases. At an arbitrary x̄ ∈ C, let

N(x̄) = {v | ⟨v, x − x̄⟩ ≤ 0, ∀x ∈ D(x̄)},  (11)

noting that N(x̄) is a certain closed, convex cone. For x̄ ∉ C, take N(x̄) = ∅. A set-valued mapping N : IR^{n} → → IR^{n} is thereby de�ned for which, in parallel to (4), the quasi-variational inequality (9) comes out as equivalent to

−F (x̄) ∈ N(x̄), or F (x̄) + N(x̄) ∋ 0.  (12)

May the vectors v ∈ N(x̄) rightly be regarded as �normals� to C at x̄, in some reasonable sense? That has to depend on the choice of the mapping D; without a �ltering of possibilities, the results could be too bizarre. Nonetheless, choices of D consistent with �normality� do exist, as will be explained next, even though not every useful example of a quasi-variational would have to conform to such an interpretation.

Three versions of normal cone now dominate theory in the �nite-dimensional context we are operating in. In describing them, we follow the patterns of notation and terminology in the recent book or Rockafellar and Wets [2, Chapter 6]. The regular normal cone to C at a point x̄ ∈ C, consisting of the regular normal vectors v, is

N̂_{C}(x̄) = {v | ⟨v, x − x̄⟩ ≤ o(|x − x̄|) for x ∈ C},  (13)

where | · | denotes the Euclidean norm and the �o� inequality stands for the property that

lim sup_{{x→x̄ \atop x∈C, x≠x̄}} \frac{⟨v, x − x̄⟩}{|x − x̄|} ≤ 0.

The general normal cone to C at x̄, the elements v of which are simply called the normal vectors to C at x̄, is de�ned from this by

N_{C}(x̄) = {v | ∃ x^{ν} ∈ C, v^{ν} ∈ N̂_{C}(x^{ν}), with (x^{ν}, v^{ν}) → (x̄, v)}. (14)

(We systematically use superscript ν = 1, 2, … to express sequences.) The third object,

N̄_{C}(x̄) = closed convex hull of N_{C}(x̄),  (15)

is the Clarke normal cone (see [2, Chapter 6] for more on this cone and its history). Although N̄_{C}(x̄) and N̂_{C}(x̄) are closed convex cones, N_{C}(x̄) is a closed cone that need not be convex. Obviously

N̂_{C}(x̄) ⊂ N_{C}(x̄) ⊂ N̄_{C}(x̄).

The set C is said to be Clarke regular at x̄ if every normal vector is a regular normal vector, i.e., if the limit process in (14) generates no additional vectors v at x̄. In that case, a very important one for many�but not all�applications, all three cones coincide. Such regularity prevails in particular when C is convex; then the �o� term in (13) can be replaced by 0, and normality reduces to the single concept of convex analysis that we were dealing with previously.

To understand how these normal cones might be connected with quasivariational inequalities, ideas of tangency need to brought in. The general tangent cone to C at x̄, the elements of which are simply called tangent vectors, is de�ned through set limits as

T_{C}(x̄) = lim sup_{λ ↘ 0} \frac{1}{λ}(C − x̄),  (16)

whereas the regular tangent cone, consisting of the regular tangent vectors to C at x̄, is

T̂_{C}(x̄) = lim inf_{{λ ↘ 0 \atop x→x̄, x∈C}} \frac{1}{λ}(C − x).  (17)

Both T_{C}(x̄) and T̂_{C}(x̄) are closed cones, the �rst also being called the contingent cone and the second the Clarke tangent cone. Evidently

T_{C}(x̄) ⊃ T̂_{C}(x̄).

When C is convex, T_{C}(x̄) and T̂_{C}(x̄) agree with the tangent cone of convex analysis that was de�ned in (7).

Although T_{C}(x̄) can be nonconvex, T̂_{C}(x̄) is always convex. This surprising property goes hand in hand with another remarkable facts of basic variational geometry:

T_{C}(x̄) = T̂_{C}(x̄) ⟺ N_{C}(x̄) = N̂_{C}(x̄).  (18)

In other words, the case where every normal vector v to C at x̄ is a regular normal vector, which was taken above as the de�nition of Clarke regularity, can equally well be portrayed as the case where every tangent vector w to C at x̄ is a regular tangent vector. (This is why the term �regular� is employed systematically as above.) Besides, one has

T̂_{C}(x̄) = lim inf_{{x→x̄ \atop x∈C}} T_{C}(x),  N_{C}(x̄) = lim sup_{{x→x̄ \atop x∈C}} N̂_{C}(x),  (19)

where the second limit merely restates the de�nition in (14) but the �rst is a rather deep result. Through (18) and (19), Clark regularity can be identi�ed with a semicontinuity property of T_{C} as well as one of N̂_{C}. The reciprocity goes further still with the fact that the following polarity relationships always hold:

\begin{aligned}N̂_{C}(x̄) & = \{v | ⟨v, w⟩ ≤ 0, ∀w ∈ T_{C}(x̄)\}, \\ T̂_{C}(x̄) & = \{w | ⟨v, w⟩ ≤ 0, ∀v ∈ N_{C}(x̄)\}. \end{aligned}  (20)

Therefore, C is Clarke regular at x̄ if and only if T_{C}(x̄) and N_{C}(x̄) are closed convex cones polar to each other. On the other hand,

\begin{aligned}N̄_{C}(x̄) & = \{v | ⟨v, w⟩ ≤ 0, ∀w ∈ T̂_{C}(x̄)\}, \\ T̂_{C}(x̄) & = \{w | ⟨v, w⟩ ≤ 0, ∀v ∈ N̄_{C}(x̄)\}, \end{aligned}  (21)

so that T̂_{C}(x̄) and N̄_{C}(x̄) always form a pair of closed convex cones polar to each other, regardless of Clarke regularity.

We can return now to quasi-variational inequalities. Let us observe that the normal cone schemes generated in that setting by (11), which translates the quasi-variational inequality condition (9) into the mapping formulation in (12), are perhaps not as varied as they might appear. They can really be seen as coming from the choice of a mapping T that assigns to any point x̄ ∈ C a cone T (x̄). Speci�cally, given D let

T (x̄) = {w = λ(x − x̄) | x ∈ K(x̄), λ ≥ 0}.  (22)

The formula for N(x̄) in (11) can then be rewritten equivalently as a polarity relation:

N(x̄) = {v | ⟨v, w⟩ ≤ 0, ∀w ∈ T (x̄)}.  (23)

Therefore, instead of speaking at all about a mapping D that assigns to each x ∈ C a set D(x) containing x, one could speak directly, from the start, about a cone-valued mapping T. No generality is lost in this maneuver because, given a choice of T, one can return to a D formulation by taking D(x) = T (x) + x. The putative normal cones N(x̄) that underlie quasi-variational inequalities can thus be interpreted as arising by duality from the introduction of putative tangent cones T (x̄).

Two specializations are now immediate. The choice T (x) = T_{C}(x) turns the quasi-variational inequality into the case of (12) in which N(x) = N̂_{C}(x), whereas the choice T (x) = T̂_{C}(x) corresponds in (12) to N(x) = N̄_{C}(x). When C is Clarke regular, these cases coincide and the quasi-variational inequality comes out as

−F (x̄) ∈ N_{C}(x̄), or F (x̄) + N_{C}(x̄) ∋ 0,  (24)

which exactly mirrors the variational inequality in (4), except that N_{C} is no longer merely the normal cone mapping of convex analysis. When C lacks Clarke regularity, however, the problem of �nding a solution x̄ to (24) does not amount to a quasi-variational inequality, since N_{C}(x̄) can fail then to be convex, whereas any cone N(x̄) coming from a quasi-variational inequality must be convex by (23).

The condition in (24) in the case of a gradient mapping F = ∇f is recognized now as the generally best expression of �rst-order optimality in minimizing f over C, irrespective of Clarke regularity. Research has shown that N_{C} enjoys a more robust calculus than N̂ or N̄, and in addition has deep ties to certain Lipschitz-type properties in geometry and analysis (see Theorem 9.41 of [2], for example). This argues strongly that (24) should perhaps serve broadly as the fundamental model for constrained equilibrium of F relative to C. From that perspective, many quasi-variational inequalities would, in practice, emerge as examples of (24) associated especially with Clarke regular classes of sets C.

Other cones than T_{C}(x̄) or T̂_{C}(x̄) are sometimes encountered as choices of T (x̄) in the paradigm of quasi-variational inequalities. For instance, when C is expressed by a system of equations and inequalities, or even beyond that, one can consider as T (x̄) the set of vectors w for which there is a smooth curve x : [0, ϵ] → C with x(0) = x̄ and x′(0) = w. For most purposes, though, this cone concept, familiar from the Kuhn-Tucker approach to Lagrange multipliers in nonlinear programming, is too feeble to provide much mathematical traction unless some kind of �constraint quali�cation� is ful�lled. Constraint quali�cations typically guarantee, however, that C is Clarke regular at x̄ with cl T (x̄) = T_{C}(x̄) = T̂_{C}(x̄). This version of T (x̄) �ts squarely then with the tangent cones already discussed and does not offer anything signi�cantly different.

A weaker property than Clarke regularity in this context is the derivability of C at x̄. It is said to hold when the �lim sup� in de�nition (16) coincides with the corresponding �lim inf� (with respect to λ), or in other words, when the sets [C − x̄]/λ actually converge to something as λ^{↘}0. The elements of T_{C}(x̄) are then the vectors w such that one can choose x(λ) ∈ C, for λ in an interval [0, ϵ], so as to have x(0) = x̄ and x′_{+}(0) = w. Here x′_{+}(0) is the limit of [x(λ) − x(0)]/λ as λ^{↘}0; only the existence of that one-sided derivative at λ = 0 is required, and at other λ ∈ [0, ϵ], the �curve� need not even be continuous. This is distinctly less restrictive than the curve property of the vectors w in the Kuhn-Tucker cone above. In comparison, de�nition (16) itself only requires of a vector w ∈ T_{C}(x̄) that there be sequences λ^{ν} ^{↘}0 and x^{ν} → x̄ with [x^{ν} − x̄]/λ^{ν} → w.

4. CALCULUS AND SOLUTION PERTURBATIONS

No general formulation of equilibrium for a mapping F relative to a set C would help much unless there were ways of bringing the abstract condition down to the particular structure of C. For equilibrium models in the form (4), or (24), that we have been emphasizing, this means having a good calculus of normal cone mappings N_{C}.

Many results are available in this calculus and can be found in [2, Chapter 6], but here we will state only two of the most fundamental. The �rst result concerns sets that are inverse images of other sets under smooth mappings:

C = A^{−1}(K) = {x | A(x) ∈ K}  (25)

where A : IR^{n} → IR^{m} is continuously differentiable and K ⊂ IR^{m} is closed and nonempty. We denote by ∇A(x̄) the m × n Jacobian matrix of A at x̄ and by ∇A(x̄)^{∗} its transpose. If a point x̄ ∈ C satis�es the constraint quali�cation

y ∈ N_{K}(A(x̄)), ∇A(x̄)^{∗}y = 0 ⟹ y = 0,  (26)

then the (general) normal cone N_{C}(x̄) at that point satis�es the inclusion

N_{C}(x̄) ⊂ {∇A(x̄)^{∗}y | y ∈ N_{K}(A(x̄))}.  (27)

Moreover if K is Clarke regular at A(x̄) (as for instance when K is convex), then C is Clarke regular at x̄ and the inclusion holds as an equation.

For illustration, suppose K is the cone IRm_{−}, which corresponds to C being speci�ed by a system of m smooth inequality constraints. The constraint quali�cation is equivalent then to the standard one of Mangasarian and Fromovitz, and the elements y = (y_{1}, …, y_{m}) of N_{K}(A(x̄)) give the Lagrange multipliers associated with the constraints at x̄. An equilibrium expressed by (24) would therefore involve such multipliers. Equations or mixtures of equations and inequalities can be handled similarly by other choices of K as a cone, but the stated result covers more than just traditional constraint systems and indeed supports an effective calculus of regularity.

Apart from the Clarke regularity case where all three types of normal cone coincide anyway, there is no comparable result for regular normal cones. For Clarke normal cones, the same calculus rule does stay valid; i.e., N̄_{C}(x̄) and N̄_{K}(A(x̄)) can validly replace N_{C}(x̄) and N_{K}(A(x̄)) in (26) and (27). But the corresponding constraint quali�cation,

y ∈ N̄_{K}(A(x̄)), ∇A(x̄)^{∗}y = 0 ⟹ y = 0,  (28)

is much more restrictive than (26). Through polarity, (28) is equivalent to requiring that the (convex) regular tangent cone T̂_{C}(x̄) cannot be separated from the range of the linear transformation w ↦ ∇A(x̄)w, which is a subspace expressible as ∇A(x̄)IR^{n}, and this stipulation can be written in turn as

T̂_{C}(x̄) + ∇A(x̄)IR^{n} = IR^{m}.  (29)

When T̂_{C}(x̄) = {0}, for instance, which is an all too frequent occurrence in working with regular tangents in the absence of Clarke regularity, (29) insists on ∇A(x̄) actually having full row rank m.

In contrast, the more versatile constraint quali�cation (26) is not equivalent to a condition in terms of tangent vectors (apart from the case of Clarke regularity). Tangency conditions are thus distinctly weaker and less far-reaching than normality conditions in variational geometry. This is counter to popular thinking that tangent vectors ought to be �primary� and normal vectors �secondary.�

The second of the fundamental rules in the calculus of normal cone mappings that we will look at here concerns images instead of inverse images. Suppose that

C = A(K) = {A(u) | u ∈ K}  (30)

where A : IR^{m} → IR^{n} is continuously differentiable and K ⊂ IR^{m} is closed and nonempty. Under the assumption that A^{−1}(B) ∩ K is bounded in IR^{m} for every bounded set B ⊂ IR^{n}, one has for any x̄ ∈ C that

\begin{matrix}N̂_{C}(x̄) ⊂ \{v | ∀ u ∈ A^{−1}(x̄) ∩ K: A(u)^{∗}v ∈ N̂_{K}(u)\}, \\ N_{C}(x̄) ⊂ \{v | ∃ u ∈ A^{−1}(x̄) ∩ K: A(u)^{∗}v ∈ N_{K}(u)\}. \end{matrix}  (31)

If A is af�ne and K is convex, so C is convex (hence Clarke regular), one has

N_{C}(x̄) = {v | A(u)^{∗}v ∈ N_{K}(u)} for any single u ∈ A^{−1}(x̄) ∩ K. (32)

The boundedness assumption is only needed for the second inclusion in (31); it is super�uous for the validity of the �rst inclusion in (31) or for the convex case in (32), provided that C is closed.

Note that this second rule provides no normal cone equation or criterion for Clarke regularity in a nonconvex setting, and in that way it contrasts with the �rst rule. Both rules have many consequences, obtained through special choices of A and K.

Next we take up the topic of solution perturbations. We adopt for this purpose the equilibrium model in (24), which we know covers variational inequalities and a major class of quasi-variational inequalities, but we now consider F to be parameterized by an element w belonging to an open set W ⊂ IR^{d}. The object of study is the (generally set-valued) solution mapping

S : w ∈ W ↦ {x | F (w, x) + N_{C}(x) ∋ 0}.  (33)

Our analysis centers on a �xed pair (w̄, x̄) in the graph of S, i.e., with x̄ ∈ S(w̄), and the issue of what may happen to x̄ under perturbations of w̄.

We suppose that F is continuously differentiable on W × IR^{n} and denote its Jacobians in the w and x arguments by ∇_{w}F (w, x) and ∇_{x}F (w, x). We make the following assumption of ample parameterization:

∇_{w}F (w̄, x̄) has full rank n.  (34)

This assumption is relatively unrestrictive, in the sense that the introduction of additional �canonical� parameters can always force it to be satis�ed. More on this matter and the results quoted below can be found in the paper of Dontchev and Rockafellar [5], in complement to the book of Rockafellar and Wets [2].

Ample parameterization guarantees in particular that S is graphically Lipschitzian of dimension d around (w̄, x̄) when N_{C} is graphically Lipschitzian of dimension n around (x̄, v̄), where v̄ = −F (w̄, x̄). As we know from earlier, N_{C} meets that provision when C is convex, but it also does when C is a nonconvex set expressible in the form (25) with K convex and the constraint quali�cation (26) ful�lled at x̄. Through various choices of K, that covers cases where C is speci�ed by smooth equations and inequalities under the Mangasarian-Fromovitz constraint quali�cation.

We will be occupied by a concept of differentiation for set-valued mappings that is based on the variational geometry of the graph of S in IR^{d} × IR^{n}. The graphical derivative of S at w̄ for x̄ is the mapping DS(w̄^{|} x̄) : IR^{d} → → IR^{n} de�ned by

x′ ∈ DS(w̄^{|} x̄)(w′) ⟺ (w′, x′) ∈ T_{gph S}(w̄, x̄).  (35)

When x̄ is the only element of S(w̄), the notation simpli�es to DS(w̄) and D^{∗}S(w̄). If S were actually differentiable at w̄, these would be the linear mappings associated with the Jacobian matrix and its transpose, but of course we cannot count on that special case and have to proceed more generally.

The mapping S is called proto-differentiable at w̄ for x̄ when gph S is derivable at (w̄, x̄). This property is of particular interest when S is graphically Lipschitzian, as we can commonly expect from of the observations above. If S were single-valued and Lipschitz continuous on an neighborhood of w̄ (for which criteria are available in some cases�see Dontchev and Rockafellar [5] for an overview), proto-differentiability would reduce to semi-differentiability: DS(w̄) would be a single-valued, positively homogeneous, Lipschitz continuous mapping such that

S(w) = S(w̄) + DS(w̄)(w − w̄) + o(|w|).  (36)

This is the same as classical differentiability, except for DS(w̄) not having to be a linear mapping. An expansion like (36) is not characteristic of protodifferentiability in general, but proto-differentiability nonetheless corresponds to a strong kind of approximation when S is graphically Lipschitzian. Indeed, with respect to a coordinate change as in the de�nition of the latter property, which identi�es gph S locally�from a different angle�as the graph of a single-valued Lipschitz continuous mapping, proto-differentiability of S turns into semi-differentiability of that mapping. Conditions guaranteeing the protodifferentiability of S therefore have some importance.

These concepts of graphical differentiation are applicable also to the mapping N_{C}, and this will be the key. The graphical derivatives of S are given by the formula

\begin{matrix}DS(w̄^{|} x̄)(w′) = \{x′ | − G(w′, x′) ∈ DN_{C}(x̄^{|} v̄)(x′) \}, where \\ G(w′, x′) = ∇_{w}F (w̄, x̄)w′ + ∇_{x}F (w̄, x̄)x′, v̄ = −F (w̄, x̄). \end{matrix} (37)

Through this, S is proto-differentiable at w̄ for x̄ if and only if N_{C} is protodifferentiable at x̄ for v̄. Moreover, that is true for instance when C has a general constraint representation as in (25) with K polyhedral convex and the constraint quali�cation (26) satis�ed at x̄; in particular, it is true when C itself is polyhedral convex.

The formula for DN_{C}(x̄^{|} v̄) in the general case of a constraint representation of C as in (25) will not be presented; it is available in the book of Rockafellar and Wets [2]. We concentrate rather on the case where C itself is polyhedral convex. The formula then is appealingly simple:

DN_{C}(x̄^{|} v̄) = N_{T} for the cone T = T_{C}(x̄) ∩ v̄^{⊥},  (38)

where v̄^{⊥} denotes the subspace orthogonal to v̄. The polyhedral cone T in (38) is the critical cone to C at x̄ for v̄ and can be expressed equivalently by

T = argmax_{x′∈TC (x̄)}⟨v̄, x′⟩ = T_{D}(x̄) for D = argmax_{x∈C} ⟨v̄, x⟩.  (39)

It is revealed now by (37) that when C is polyhedral convex, the vectors x′ ∈ DS(w̄^{|} x̄)(w′), describing the differential perturbations of x̄ associated with a differential perturbation w′ of w̄, are then the solutions to an auxiliary variational inequality over the critical cone T:

DS(w̄^{|} x̄)(w′) = {x′ | − G(w′, x′) ∈ N_{T} (x′) }, where
G(w′, x′) = ∇_{w}F (w̄, x̄)w′ + ∇_{x}F (w̄, x̄)x′,
T = T_{C}(x̄) ∩ F (w̄, x̄)^{⊥}
= T_{D}(x̄) for D = argmin_{x∈C} ⟨F (w̄, x̄), x⟩.

(40)

An alternative description of how the sensitivity analysis of a parameterized variational inequality over a polyhedral set can be carried out has been presented by Robinson [6]. It is likewise based in effect on (38) but in this case in terms of �normal maps� that express the Minty parameterization of the graphs of N_{C} and N_{T}. For nonpolyhedral C, a framework of normal maps is less attractive, but formulas for DN_{C}(x̄^{|} v̄) exist still in some major situations, as mentioned.

5. APPLICATION TO AN EQUILIBRIUM MODEL WITH AGGREGATION

These calculus results, culminating for the polyhedral case in the perturbation formula (40), have been elaborated by Patriksson and Rockafellar [4] in the framework of aggregation, which underlies traf�c equilibrium. Consider the solution mapping S in (33) for the case of a parameterized variational inequality, or equilibrium model, having

C = C_{1} + ⋯ + C_{r} with each C_{k} polyhedral convex.  (41)

Here C is the image A(K) of the set K = C_{1} × ⋯ × C_{r} under the linear transformation A : (x_{1}, …, x_{r}) ↦ x_{1} + ⋯ + x_{r}. The normal cone rule in (32) applies and says that, for any x̄ ∈ C and any choice of vectors x̄_{k} ∈ C_{k} with x̄ = x̄_{1} + ⋯ + x̄_{r}, one has

N_{C}(x̄) = N_{C_{1}}(x̄_{1}) ∩ ⋯ ∩ N_{C_{r}}(x̄_{r}).  (42)

The normal cones in this formula are polyhedral convex and have the corresponding tangent cones as their polars, so by taking polars on both sides of (42) one gets the dual formula

T_{C}(x̄) = T_{C_{1}}(x̄_{1}) + ⋯ + T_{C_{r}}(x̄_{r}),  (43)

again with all cones polyhedral convex. The especially interesting thing now is the form of the critical cone T, as described by (38), (39) or equivalently (40) with v̄ = −F (w̄, x̄):

T = T_{1} + ⋯ + T_{r} with each T_{k} polyhedral convex  (44)

for the cones

T_{k} = T_{C_{k}}(x̄_{k}) ∩ F (w̄, x̄)^{⊥}

= T_{D_{k}}(x̄_{k}) for D_{k} = argmin_{x_{k}∈C_{k}} ⟨F (w̄, x̄), x_{k}⟩. (45)

The auxiliary variational inequality in (40) thus exhibits in this case an aggregation structure mirroring that in the given variational inequality under (41). We see further that the normal cone N_{T} (x′) in (40) has the expression

N_{T} (x′) = N_{T_{1}}(x′_{1}) ∩ ⋯ ∩ N_{T_{r}}(x′_{r})

for any x′_{k} ∈ T_{k} with x′ = x′_{1} + ⋯ + x′_{r}. (46)

Therefore, the differential perturbations x′ of x̄ associated with a differential perturbation w′ of w̄ are the vectors of the form

x′ = x′_{1} + ⋯ + x′_{r} in which
x′_{k} minimizes ⟨G(w′, x′), · ⟩ over T_{k}.

(47)

In our paper [4], we have worked out in detail the implications of this for solution perturbations to network models of traf�c equilibrium with origindestination pairs. Here we apply it to a simpler yet broader model of multicommodity �ow.

Let G = (N , A) be a transportation network, where N and A are the sets of nodes and arcs (directed links). For k = 1, …, r, let x_{k}(j) denote the quantity of �ow of commodity type k in the arc j ∈ A. Let b_{k}(i) be the given supply of commodity type k at node i ∈ N, with negative supply corresponding to demand and zero supply expressing a conservation requirement. The �ows x_{k} : A → IR of type k that we admit are the ones belonging to the polyhedral convex set

\begin{matrix}C_{k} = \{x_{k} | x_{k}(j) ∈ I_{k}(j) ∀ j ∈ A, \\ ∑_{j∈A} e(i, j)x_{k}(j) = b_{k}(i) ∀ i ∈ N \}, \end{matrix}  (48)

where e(i, j) is the incidence of node i with arc j (this being +1 if i is the initial node of j, but −1 if i is the terminal node of j, and 0 otherwise), and I_{k}(j) is a nonempty, closed interval constraining the �ow values allowed for commodity k in arc j. (As a special case, one could have I_{k}(j) = [0, 0] in certain arcs where commodity k is not permitted.)

Equilibrium in the multi-commodity setting revolves around minimizing the travel costs for the individual commodities while coping with the fact that those costs depend on the aggregate �ow contributed by these commodities and thus re�ect an interdependence among the different kinds of traf�c. The travel cost in arc j is a function t_{j}(x) of the aggregate �ow x = x_{1} + ⋯ + x_{r}. An equilibrium consists, by de�nition, of a collection of commodity �ows x̄_{k} ∈ C_{k} for k = 1, …, r such that

x̄_{k} ∈ argmin_{x_{k}∈C_{k}} ∑_{j∈A} t̄(j)x_{k}(j), with t̄(j) = t_{j}(x̄), x̄ = x̄_{1} + ⋯ + x̄_{r}. (49)

Traf�c equilibrium, so de�ned, can be translated into a variational inequality in two ways, �extensive� or �aggregate.� Let

t : (w, x) ↦ (…, t_{j}(w, x), …)

be the mapping that, for a given pair (w, x), assigns to the arcs j ∈ A the corresponding travel costs t_{j}(w, x). The sum in (49) can be construed then as ⟨t(x̄, w̄), x_{k}⟩. In the extensive formulation of equilibrium, the focus is on elements

(x_{1}, …, x_{r}) ∈ Γ = C_{1} × ⋯ × C_{r}

and the mapping

Φ : (w, x_{1}, …, x_{r}) ↦ (t(w, x), …, t(w, x)) (r copies).

Normal cones to Γ are given by

N_{Γ}(x̄_{1}, …, x̄_{r}) = N_{C_{1}}(x̄_{1}) × ⋯ × N_{C_{r}}(x̄_{r}),

so the condition in (49) comes out as

−Φ(w̄, x̄_{1}, …, x̄_{r}) ∈ N_{Γ}(x̄_{1}, …, x̄_{r}),  (50)

or in other words, the parameterized variational inequality over Γ for Φ.

In the aggregate formulation of equilibrium, on the other hand, the condition in (49) is rendered as

−t(w̄, x̄) ∈ N_{C}(x̄) for C = C_{1} + ⋯ + C_{r}.  (51)

It purely and simply refers to aggregate �ows. The extensive and aggregate formulations of equilibrium are equivalent on the basis of the normal cone formula (42) that holds under (41). To pass from (51) to (50), an arbitrary choice can be made of commodity �ows x̄_{k} such that x̄_{1} + ⋯ + x̄_{r} = x̄. (Such �ows x̄_{k} can be determined computationally by solving a system of linear equations and inequalities.) Obviously the aggregate version involves vastly fewer variables, but the aggregate polyhedron C does not come with a direct speci�cation in terms of linear constraints.

To see next what happens with perturbations of equilibrium in this traf�c situation, with emphasis on the aggregate model, suppose that the travel costs depend on a parameter vector w ∈ W ⊂ IR^{d}, so that we have t_{j}(w, x) in arc j and altogether a mapping t : (w, x) ↦ t(w, x). Consider the associated solution mapping

S : w ↦ {x ∈ C | − t(w, x) ∈ N_{C}(x)} with C = C_{1} + ⋯ + C_{r} (52)

along with a particular w̄ ∈ W and a corresponding aggregate �ow x̄ ∈ S(w̄). Assume that the mapping t is continuously differentiable and, as the F in (34), satis�es our ample parameterization condition:

∇_{w}t(w̄, x̄) has full rank n = |A|,  (53)

where |A| is the cardinality of A; in other words, for any choice of values t′(j) for j ∈ A, there exists w′ such that ∇_{w}t_{j}(w̄, x̄)w′ = t′(j) for all j.

We wish to specialize the perturbation formula (40) to this framework with F = t. For this purpose we make an arbitrary choice of �ows x̄_{k} ∈ C_{k} yielding x̄_{1} + ⋯ + x̄_{r} = x̄ and let

T = T_{1} + ⋯ + T_{r} with

T_{k} = T_{D_{k}}(x̄_{k}) for D_{k} = argmin_{x_{k}∈C_{k}}⟨t(w̄, x̄), x_{k}⟩, (54)

noting that D_{k} is again polyhedral. The aggregate cone T, likewise polyhedral, is the critical cone on which the formula in (40) will operate, as we already have established. The mapping G in this formula will be given by

\begin{matrix}G(w′, x′) = ∇_{w}t(w̄, x̄)w′ + ∇_{x}t(w̄, x̄)x′ \\ with x′ = x′_{1} + ⋯ + x′_{r}, x′_{k} ∈ T_{k}. \end{matrix}  (55)

Therefore, in the network context the differential perturbations x′ of x̄ associated with a differential perturbation w′ of w̄ are the vectors of the form

x′ = x′_{1} + ⋯ + x′_{r} in which x′_{k} minimizes

⟨∇_{w}t(w̄, x̄)w′ + ∇_{x}t(w̄, x̄)x′, · ⟩ over T_{k}. (56)

The question, though, is how to understand through (54) the special nature of the subcones T_{k} in this network context. In particular, we wish to know whether the calculation of perturbations by way of (56) comes down to solving another traf�c equilibrium problem of reduced type.

In investigating that, we can invoke the known optimality conditions for a linear min cost network �ow problem as applied to the subproblems in (56) that de�ne the sets D_{k}. It will be demonstrated now constructively in this way that the cones T_{k} in (54) have the form

\begin{matrix}T_{k} = \{x′_{k} | x′_{k}(j) ∈ I′_{k}(j) ∀ j ∈ A, \\ ∑_{j∈A} e(i, j)x_{k}(j) = 0 ∀ i ∈ N \}, \end{matrix}  (57)

where each I′_{k}(j) is an interval of the type [0, 0], [0, ∞), (−∞, 0], or (−∞, ∞). Since this form is just like that of the sets C_{k} in (48), except that the intervals I′_{k}(j) are much more special and the quantities b_{k}(j) have become 0, it will follow that the perturbation formula (56) does indeed amount to solving a special traf�c equilibrium subproblem.

Optimality conditions for the problem of minimizing the linear function ⟨t(w̄, x̄), · ⟩ over C_{k}, with C_{k} having the general form in (48), are available in [7, Chapter 7]. They involve the notion of a potential u : N → IR and its differential Δu : A → IR, where

Δu(j) = − ∑_{i∈N} u(i)e(i, j) = u(�nal node of j) − u(initial node of j).

According to these results, a �ow x_{k} belongs to the argmin set D_{k} in this problem if and only if x_{k} ∈ C_{k} and there is a potential u_{k} such that

Δu_{k}(j) − t_{j}(w̄, x̄) ∈ N_{I_{k}(j)}(x_{k}(j)) for every arc j ∈ A.  (58)

Moreover the potentials u_{k} that �ll this role for a particular x_{k} ∈ D_{k} are precisely the solutions to a certain dual problem (as explained in [7]. Therefore, we can arbitrarily select one such ū_{k} (obtained for instance as a by-product of using algorithms such as in [7] to solve the cost minimization problem in question), and the �ows x_{k} ∈ D_{k} will be characterized then as the ones for which the values x_{k}(j) satisfy the condition in (58). But this is equivalent to saying that in terms of the intervals

Ī_{k}(j) = \{ \begin{matrix}I_{k}(j) & if Δū_{k}(j) − t_{j}(w̄, x̄) = 0, \\ \{ right endpoint of I_{k}(j)\} & if Δū_{k}(j) − t_{j}(w̄, x̄) > 0, \\ \{ left endpoint of I_{k}(j)\} & if Δū_{k}(j) − t_{j}(w̄, x̄) < 0, \end{matrix} (59)

one has

\begin{matrix}D_{k} = \{x_{k} | x_{k}(j) ∈ Ī_{k}(j) ∀ j ∈ A, \\ ∑_{j∈A} e(i, j)x_{k}(j) = b_{k}(i) ∀ i ∈ N \}. \end{matrix}  (60)

In other words, D_{k} is, like C_{k}, a �ow polyhedron, but with respect to certain smaller intervals Ī_{k}(j) dictated by the optimality.

Tangent cones to polyhedral convex sets speci�ed by linear constraint systems are readily determined. We immediately get from (60) that, for any particular x̄_{k} ∈ D_{k}, we have

\begin{matrix}T_{D_{k}}(x̄_{k}) = \{x′_{k} | x′_{k}(j) ∈ T_{Ī_{k}(j)}(x̄_{k}(j)) ∀ j ∈ A, \\ ∑_{j∈A} e(i, j)x′_{k}(j) = 0 ∀ i ∈ N \}. \end{matrix}  (61)

It remains then only to set I′_{k}(j) = T_{Ī_{k}(j)}(x̄_{k}(j)) for all j ∈ A, so that

I′_{k}(j) = \{ \begin{matrix}[0, 0] & if x̄_{k}(j) is an interior point of Ī_{k}(j), \\ [0, ∞) & if x̄_{k}(j) is the left endpoint (only) of Ī_{k}(j), \\ (−∞, 0] & if x̄_{k}(j) is the right endpoint (only) of Ī_{k}(j), \\ (−∞, ∞) & if Ī_{k}(j) is the one-point interval \{x̄_{k}(j)\}. \end{matrix} (62)

In summary, perturbations in this network setting can be calculated by resolving the equilibrium condition (56) for a �differential� multi-commodity �ow problem having linear costs and constraints as in (57) and (62).

This equilibrium subproblem can itself be articulated further now in either extensive or aggregate form and in that manner tackled as a variational inequality. In extensive form, there are many variables once more, in principle, but it can be seen from the derivation of the intervals I′_{k}(j) in (62) from the intervals Ī_{k}(j) in (59) that I′_{k}(j) = [0, 0] whenever Ī_{k}(j) is a one-point interval. In fact, that can be anticipated to most arcs j, in which case the �ow variables x_{k}(j) for those arcs can be suppressed by setting them equal to 0. Thus, the number of variables involved in the subproblem is likely really to be very much smaller than in the original problem.

In aggregate form, there are other possibilities for the equilibrium subproblem that calculates perturbations. It has the form

−∇_{w}t(w̄, x̄)w′ − ∇_{x}t(w̄, x̄)x′ ∈ N_{T} (x′) for T = T_{1} + ⋯ + T_{r}, (63)

the cones T_{k} being speci�ed by the �ow constraints in (57) and (62). The usual dif�culty in this picture would be that such constraints do not carry over to a direct constraint representation of T, but because we are dealing with �ows, there are additional tools available. The �ows in T_{k} are �circulations� without source or sink, and the intervals I′_{k}(j) merely impose �sign restrictions� on what can pass through the various arcs j; when I′_{k}(j) reduces to 0, the arc can effectively be deleted in consideration of commodity k. The theory of conformal realization of �ows in [7, Chapter 4B] can be utilized to obtain�in a constructive manner�a representation

T_{k} = { ∑_{l=1}^{L_{k}} λ_{kl}e_{kl} | λ_{kl} ∈ Λ_{kl}}

in which each e_{kl} is a so-called elementary �ow (nonzero only on the arcs of an elementary closed path) and each Λ_{kl} is either the interval [0, ∞) or the interval (−∞, ∞). Having determined such representations for the cones T_{k}, one could combine them into one for T and in that way arrive through a change of variables at a version of the aggregate variational inequality in terms of the variables λ_{kl}, of which there might not be very many.

Finally, something should be said about the role of quasi-variational inequalities in traf�c equilibrium. Our discussion has centered on variational inequalities only, but research on quasi-variational inequality models has also been carried out in this setting; see for example De Luca and Maugeri [8, 9, 10]. Such efforts have been directed toward more general models than ours that treat elastic supplies and demands; they can be construed as models in which the values b_{k}(i) are not �xed but rather can respond to the costs achieved at optimality. In passing to that kind of framework, would the quasi-variational inequalities so obtained, once �truncated� in the manner we adopted in Section 3, �t with pattern of generalized tangent and normal cones that we have suggested?

That could well be the case, but there might be a simpler alternative. Elastic supplies and demands can also be handled in many cases by expanding the network to allow for additional arcs which connect supply nodes and demand nodes to the �outside world� and then introducing further traf�c costs on those arcs. In this way, a quasi-variational inequality of such type can, at least in typical cases like those with simple origin-destination pairs, be reformulated as an ordinary variational inequality in the expanded network. The fact that our model allows general intervals I_{k}(j) may help in that respect, since an arc introduced for only one of the commodities can be assigned the trivial interval [0, 0] for the other commodities.

References

[1] R.T. Rockafellar (1970), Convex Analysis, Princeton University Press, Princeton, New Jersey (available from 1997 also in paperback in the series Princeton Landmarks in Mathematics).

[2] R.T. Rockafellar and R.J-B Wets (1998), Variational Analysis, Springer Verlag, Berlin.

[3] G. J. Minty (1962), Monotone (nonlinear) operators in Hilbert space, Duke Mathematical Journal 29, 341�346.

[4] M. Patriksson and R. T. Rockafellar (2001), Sensitivity analysis of variational inequalities over aggregated polyhedra, with application to traf�c equilibria, preprint.

[5] A. L. Dontchev and R. T. Rockafellar (2001), Ample parameterization of variational inclusions, SIAM Journal on Optimization, to appear.

[6] S. M. Robinson (1995), Sensitivity analysis of variational inequalities by normal-map techniques, in Variational Inequalities and Network Equilibrium Problems (F. Giannessi and A. Maugeri, editors), Plenum Press, 257�269.

[7] R. T. Rockafellar (1984), Network Flows and Monotropic Optimization, Wiley; republished in 1998 by Athena Scienti�c.

[8] M. De Luca and A. Maugeri (1988), Quasi-variational inequalities and applications to equilibrium problems with elastic demand, in Nonsmooth Optimization and Related Topics (F. H. Clarke, V.F. Dem’yanov, and F. Giannessi, editors), Plenum Press, 61�77.

[9] A. Maugeri (1995), Variational and quasi-variational inequalities in network �ow models. Recent developments in theory and algorithms, in Variational Inequalities and Network Equilibrium Problems (F. Giannessi and A. Maugeri, editors), Plenum Press, 195�211.

[10] M. De Luca (1995), Generalized quasi-variational inequalities and traf�c equilibrium problems, in Variational Inequalities and Network Equilibrium Problems (F. Giannessi and A. Maugeri, editors), Plenum Press, 45�54.