Sufficient conditions for the uniqueness of the solution to

the Stochastic User Equilibrium problem

Guido Gentile

Dipartimento di Idraulica, Trasporti e Strade

Università degli Studi di Roma “La Sapienza”

[email protected]

Abstract

Referring to additive demand models, the Stochastic User Equilibrium can be formulated in

the reduced space of travel alternative generalized costs as a fixed point problem defined on

ℜ n, where n is the number of travel alternatives minus the number of user classes. Through

the analysis of an equivalent non-linear program, a new sufficient condition for the

uniqueness of the solution to a generic unconstrained fixed point problem is introduced. The

application of this result to the Stochastic User Equilibrium problem permits to derive a

weaker sufficient condition for the uniqueness of the equilibrium than that requiring the

Jacobian of the arc cost function to be positive semi definite. Specifically, it is shown that the

problem admits only one solution also if this Jacobian becomes positive definite when

summed up to the identity matrix multiplied by a positive scalar, whose value is strictly

related to the Jacobian of the demand function. Some elementary cases are presented where

the above condition is employed in order to characterize the equilibrium. This way it is shown

that the lack of definiteness of the arc cost function Jacobian is not a taboo for establishing the

uniqueness of the solution, and the problem of how much this condition may be violated can

and should be addressed with reference to each specific instance of traffic assignment.

1
Introduction

With reference to a congested transport network, traffic assignment consists in the seeking of

a cost and flow pattern resulting from a supply-demand equilibrium where users cannot

improve the utility of their individual travel choice by unilaterally changing it. The Stochastic

User Equilibrium (SUE) problem is a particular instance of traffic assignment, addressed

under the assumption of within-day stationariety, where the demand model is probabilistic,

while the supply model is based on a not necessarily separable arc cost function.

Essentially, two different approaches have been proposed in the literature to formulate the

SUE problem. Here, for the sake of brevity, we recall only some seminal papers, referring for

detailed citations to the books by Sheffi (1985), Patriksson (1994) and Cascetta (2001). The

first approach consists in defining an equivalent non-linear program (Daganzo and Sheffi,

1977; Fisk, 1980; Oppenheim, 1995) in analogy with the “sum integral” model proposed for

the deterministic case in Beckman, McGuire and Winsten (1956), but requires the arc cost

function to have a symmetric Jacobian. The second approach, proposed in Daganzo (1983),

consists in formalizing the equilibrium as a fixed point problem, and permits to address SUE

in a multi-user and multimodal context with elastic demand up to trip generation and

asymmetric arc cost function Jacobian (Cantarella, 1997).

Notoriously, fixed point problems are well suited for the formulation of equilibrium problems,

as they allow for a great flexibility in the definition of the underlying models, while keeping

the mathematical technicalities of the formalization to a minimum. Most of the literature on

fixed point problems addresses the issue of the existence of a solution, while few results are

available to discuss its uniqueness. The most well know sufficient condition guaranteeing the

solution uniqueness requires the fixed point function to be a contraction (Bertsekas, 1995, p.

554). However, this result does not apply to the case of traffic assignment, where it is well

acknowledged that, by simply iterating the fixed point function, a bouncing sequence of

2
points is produced and an equilibrium is usually not attained, so that some averaging process

is needed to achieve convergence (Powell and Sheffi, 1982).

To discuss the uniqueness of the equilibrium in traffic assignment, sufficient conditions

requiring the monotonicity of the arc cost function have been introduced (Smith, 1979;

Dafermos, 1980). However, these monotonicity conditions are not workable in practice, and

are then usually met by requiring the Jacobian of the arc cost function to be definite.

In many cases of practical relevance, for instance when the aim is to represent congestion in

transit systems and/or the interaction among different transport modes on road links, the

monotonicity condition is not satisfied in general and, to the contrary, it is not difficult to find

examples where the solution is not unique (Bellei, Gentile and Papola, 2003). On the other

hand, it is common belief that the monotonicity condition is excessively restrictive, as, in

most instances of the traffic assignment problem for which this uniqueness condition does not

hold, the fixed point algorithms actually converge to the same equilibrium pattern whichever

starting point is considered for the initialization. The present paper aims then at deriving

weaker sufficient conditions for the uniqueness of the equilibrium, in order to provide a

partial theoretical justification of this circumstance.

A new sufficient condition for the uniqueness of the SUE problem has been recently obtained

in Cantarella (2002), by applying the proof of the monotonicity condition given in Cantarella

(1997) to a different fixed point formulation. We will show how this condition can be

interpreted as a particular instance of a more general result.

To this end, we first derive, through the analysis of an equivalent non-linear program, a new

sufficient condition for the uniqueness of the solution to a generic unconstrained fixed point

problem. In order to exploit this result, with reference to the case where the demand model is

additive (that is, when summing up the same constant to the utility of every travel alternative

of a user does not modify his choice probabilities – the concept of travel alternative will be

3
introduced in section 2.1), we propose an alternative fixed point formulation of the SUE

problem defined on the reduced space of travel alternative generalized costs (Bellei, Gentile

and Papola, 2002). On this basis, the interpretation of the newly found uniqueness condition

in terms of properties of the supply and demand models is addressed. This permits to derive a

weaker sufficient condition for the uniqueness of the equilibrium than that requiring the

Jacobian of the arc cost function to be positive semi definite (Cantarella, 1997). Thus, the lack

of definiteness is shown to be not a taboo for establishing the uniqueness of the solution, so

that the problem of how much this condition may be violated can and should be addressed

with reference to each specific instance of traffic assignment. A contribution in this direction

has been recently achieved in D’Acierno, Montella and Gallo (2002) with specific reference

to a bimodal transport network with interaction among busses and cars on road links.

In section 1, by introducing an appropriate gap function, a generic unconstrained fixed point

problem defined through a C1 function is transformed into an equivalent non-linear program.

The analysis of the latter problem permits to establish some properties of the solutions to the

fixed point problem. In particular, applying an original result regarding unconstrained non-

linear programs, referred to as the bend down theorem, a new sufficient condition for the

uniqueness of the solution is derived, requiring the Jacobian of the fixed point function minus

the identity matrix to be non singular.

In section 2, the new unconstrained fixed point formulation of the SUE problem is presented.

On this basis, it is shown that, in order to guarantee the uniqueness of the equilibrium, the

Jacobian of the arc cost function can actually be positive definite when summed up to the

identity matrix multiplied by a positive scalar, whose value is strictly related to the Jacobian

of the demand function, thus achieving the aimed generalization.

In section 3, some elementary cases are presented in order to show how the above condition

can be employed to discuss the uniqueness of the equilibrium. We will make specific

4
reference to the multinomial Logit model, whose choice probabilities are expressed in closed

form, so that the differentiation of the demand function can be performed analytically.

A mathematical appendix is added, where the bend down theorem is established, yielding

sufficient conditions for the global minima of an unconstrained non-linear program to

constitute a simply connected set. Moreover, some results regarding the relation among

eigenvalues, definiteness and monotonicity are presented, and some well-known properties

are reported just to improve readability. All these propositions are used to prove the new

uniqueness condition.

1 Unconstrained fixed point problems

In this section we establish some properties of the solutions to the following fixed point

problem:

x = h(x), x∈ℜ n, (1)

where h is C1. We denote S the set of its solutions, i.e.

S = {x∈ℜ n: x = h(x)}.

1.1 An equivalent non-linear program

We say that two problems are equivalent when they have the same set of solutions. Let d(x)
n
be the difference between the fixed point function h(x) and the point x∈ℜ at which it is

calculated, i.e.

d(x) = h(x)-x.

Considering, for convenience, the gap function ϕ(x) defined as one half of the square of the

Euclidean norm of d(x), i.e.

ϕ(x) = ½ ⋅||d(x)||2 = ½⋅d(x)T⋅d(x),

we introduce the following unconstrained non-linear program:

min x∈ℜ n ϕ(x). (2)

5
Proposition 1 - equivalence

The fixed point problem (1) and the non-linear program (2) are equivalent, i.e.

S = {x∈ℜ n: ϕ(x) ≤ ϕ(y),∀y∈ℜ n }.

Proof.

By definition the norm of a vector is null, if the vector is zero, while it is strictly greater than

zero, otherwise; then, we have:

||d(x)|| = 0, ∀x∈ℜ n | d(x) = 0n and ||d(x)|| > 0, ∀x∈ℜ n | d(x) ≠ 0n ,

proving that the gap function is zero at the solutions to the fixed point problem, while it is

strictly greater than zero elsewhere. 

Because h is C1, the vector function d and then the scalar function ϕ are also C1. Therefore,

their gradients (the gradient of a vector function coincides with its Jacobian transposed) exist

and can be expressed as follows (see the differentiation rules 7 in the appendix):

∇d(x) = ∇h(x) -In , (3)

∇ϕ(x) = ∇d(x)⋅d(x). (4)

Because the non-linear program (2) is unconstrained, the set X s of its stationary points is the

set of the null-gradient points:

X s = {x∈ℜ n: ∇ϕ(x) = 0n}.

We denote X m the set of the local minima, i.e.

X m = {x∈ℜ n: ∃ ε > 0 | ϕ(x) ≤ ϕ(y), ∀y∈N(x, ε)},

where N(x, ε) = {y∈ℜn: ||y – x|| ≤ ε} is the closed ball centred at x∈ℜn with a ray of length

ε > 0. Clearly it is: X m ⊆ X s.

6
1.2 Uniqueness of the solution

In this section we apply the bend down theorem and the implicit function theorem to the non-

linear program (2) in order to establish sufficient conditions for the uniqueness of the solution

to the fixed point problem (1).

To this end, we first establish a condition on the Jacobian of the fixed point function which

implies that the set of the global minima to the non-linear program (2) coincides with that of

its stationary points. The condition is that this Jacobian minus the identity matrix is non-

singular. Moreover, the same condition makes it possible to apply the implicit function

theorem to the fixed point equation. Because the latter ensures local uniqueness, and, based

on the bend down theorem, the set of the solutions is connected, global uniqueness is

guaranteed.

Proposition 2 - Jacobian condition

With reference to the non-linear program (2), if the Jacobian of the fixed point function minus

the identity matrix is non-singular, i.e.

|∇h(x)-In| ≠ 0, ∀x∈ℜ n, (5)

then, the set of the global minima coincides with that of the stationary points, i.e.

S = X s.

Proof.

We first express condition (5) in terms of properties of the eigenvalues (see 8 in the appendix,

where also the notation is introduced) of matrix ∇h(x)-In . Based on properties (53) and (52),

we have that condition (5) is equivalent to requiring that the real eigenvalues of the fixed

point function Jacobian are all different from one, i.e.

λj(∇h(x)) ≠ 1, ∀j∈IR(∇h(x)), ∀x∈ℜ n. (6)

Then, we observe that, by combining (3) with (4), the gradient of the objective function of the

7
non-linear program (2) can be expressed as follows:

∇ϕ(x) = ∇h(x)⋅d(x) - d(x). (7)

Because it is: x∈S → d(x) = 0n , based on (7) we have: x∈S → x∈X s, or equivalently:

S ⊆ X s.

On the basis of (6), we now prove that:

X s ⊆ S,
s
or, equivalently, that: x∈X → x∈S. Let x∈X s, and by contradiction suppose that x∉S.

Because it is: x∈X s, then we have: ∇ϕ(x) = 0n , which, based on (7), can be expressed as:

∇h(x)⋅d(x) = d(x).

Moreover, because it is: x∉S, we have: d(x) ≠ 0n . Then, based on the above equation, a real

valued eigenvalue of ∇h(x) is equal to 1 and d(x) is the corresponding eigenvector. This

contradicts condition (6). Then, it must be: x∈S, proving that X s ⊆ S.

The result S = X s follows immediately from S ⊆ X s and X s ⊆ S, so that, based on proposition

1, the set of the global minima coincides with that of the stationary points. 

Corollary 3 - alternative conditions

Each one of the following conditions implies condition (5):

λj(∇h(x)) < 1, ∀j∈IR(∇h(x)), ∀x∈ℜ n, (8)

λj(∇h(x)) ≤ 0, ∀j∈IR(∇h(x)), ∀x∈ℜ n, (9)

∇h(x)-In < 0, ∀x∈ℜ n, (10)

∇h(x) ≤ 0, ∀x∈ℜ n. (11)

Proof.

With reference to conditions (8) and (9), the result follows immediately from the fact that

condition (6) is equivalent to condition (5). With reference to definiteness conditions (10) and

8
(11), the result follows from (8) and (9), respectively, based on the corollaries 11 and 12 (see

9 in the appendix, where also the notation is introduced). 

Proposition 4 - uniqueness

With reference to the fixed point problem (1), if the Jacobian condition (5) holds, then there

exists at the most one solution.

Proof.

If S = ∅, the above assertion is trivial. Assume then that x*∈S ≠ ∅.

In order to apply the implicit function theorem to the fixed point equation, we shall first

introduce a parametrization of problem (1). Without loss of generality, we assume that the

fixed point function depends on a vector of parameters b∈ℜp, besides the current variable

x∈ℜ n. Moreover, we assume that h is C1 also with respect to b. Let b*∈ℜp be the reference

value of the parameters’ vector.

Because x*∈S, we have: d(x*, b*) = 0n . Moreover, because (5) holds, based on (3) we have:

|∇x d(x*, b*)| ≠ 0. Then, we can apply the implicit function theorem to the non-linear system

of equations d(x, b) = 0n at point (x*, b*), stating that there exist an open ball centred at b*

and having a ray of length ε > 0 where there can be defined a unique one-valued function ξ

such that d(ξ(b), b) = 0n (Apostol, 1974, p. 374). This implies that x* = ξ(b*) is an isolated

solution.

Moreover, because (5) holds, proposition 2 states that: X s = S. Then, because x* is an isolated

solution, it is also a connected component of X s, while, because it is: X m ⊆ X s and S ⊆ X m,

s
we have: X = X m. All the hypothesis of the bend down theorem (proposition 6 in the

appendix) are satisfied, then S is connected.

Because S is connected and x*∈S is an isolated solution, then x* is the only solution. 

9
2 Stochastic User Equilibrium

2.1 Problem formulation

The SUE problem is here addressed in a general framework, allowing for multi-user, multi-

modal and elastic demand modelling, and for the use of not necessarily separable arc cost

functions. In this context is introduced a classical fixed point formulation, on which basis the

existence of an equilibrium is easily established.

The users are grouped into a set U of classes. All individuals belonging to a same class are

assumed to be identical with respect to any characteristic influencing travel behaviour and

externalities.

The multimodal network of infrastructures and services constituting the transport supply is

represented through an oriented graph G = (N, A), where N is the set of the nodes and A is the

set of the arcs.

The flow of users belonging to the generic class u on the generic arc a is denoted fau, while cau

is the corresponding cost. The arc flow and cost pattern are then expressed, respectively, by

the (l × 1) vectors f and c, where l = |A|⋅|U|. In order to represent congestion, a C1 arc cost

function, expressing the arc costs in terms of the arc flows, is introduced:

cau = cau( f ), in compact form: c = c( f ). (12)

The demand model is based on the random utility theory, where the travel behaviour is

represented assuming that each users: a) considers a positive finite number of mutually

exclusive travel alternatives constituting his choice set; b) associates with each travel

alternative of his choice set a utility regarded as a random variable; and c) selects a maximum

utility travel alternative. We assume that the travel choice process can be broken down into a

sequence of mobility choices (e.g. to travel or not to travel, by which transport mode, to

which destination and following which path) represented by a choice tree (Ben Akiva and

10
Lerman, 1985). A travel alternative is a path on the choice tree, specifying the choice made at

each level, and its utility is the sum of the utilities associated with each arc of this path. In

particular, each travel alternative (except for the not-to-travel alternative, when present) is

associated with one path on the network connecting the origin node of the trip to the

destination node (the paths associated to a given transport mode may be constituted

exclusively by arcs belonging to a specific sub-graph, as in the case of transit, or not, as in the

case of park and ride). On this basis, user’s behaviour is described in terms of the probability

that each of his travel alternatives has maximum utility.

The du > 0 users constituting the generic class u, share: a) the same individual attributes

characterizing the user as a trip consumer (e.g. age, value of time, and purpose of the trip); b)

the same attributes specifying the production of trip externalities, such as congestion and

pollution (e.g. vehicle type and occupancy rate); and c) the same choice set Ju of travel

alternatives. The utility of the generic travel alternative j∈Ju , is given by the sum of a finite

systematic utility term Vju, and a zero mean random residual εju.

The choice model considered in this paper is assumed to satisfy the following properties: 1) the

random residuals have non-zero finite variance and their joint probability density function is

independent of the systematic utilities, continuous, and strictly positive (probabilistic, additive,

continuous and strictly-positive choice model); and 2) the systematic utility of the generic travel

alternative is given by subtracting the generalized cost Cju of the associated path, which is zero

for the not-to-travel alternative, to a constant utility term Xju independent of congestion, i.e.

Vju = Xju-Cju. (13)

The generalized cost Cju is assumed to be given by the sum of the costs of the arcs

constituting the associated path:

Cju = ∑a∈A cau⋅δauj, in compact form: C = ΔT⋅c, (14)

where δauj = 1, if the path associated with the travel alternative j∈Ju includes arc a, while

11
δauj = 0, otherwise; δauj is the generic element of the (l × m) arc-alternative incidence matrix Δ,

where m = ∑u∈U |Ju|; C is the (m × 1) vector of the travel alternative generalized costs.

The choice probability Pju of the generic travel alternative is by definition the probability of j

being a maximum utility travel alternative among the choice set Ju :

Pju = Pr[∩k∈Ju Vju+εju ≥ Vku+εku]. (15)

Equation (15) expresses the choice probability of the generic travel alternative as a function of

the systematic utilities of all the travel alternatives of the choice set:

Pju = Pju(Vku: k∈Ju). (16)

Based on the assumptions 1) and 2), this function can be proved (Gentile, 2000) to be one-

valued and C1. The flow Fju of the travel alternative is given by multiplying its choice

probability by the number of users of the class:

Fju = du⋅Pju; (17)

then, by definition, we have:

∑ j∈Ju Fju = du . (18)

On the basis of (16) and (13), equation (17) defines the demand function, expressing the

travel alternative flows in terms of the travel alternative generalized costs:

Fju = du⋅Pju(Xju-Cju: k∈Ju), in compact form: F = F(C), (19)

where F is the (m × 1) vector of the travel alternative flows. Because the choice probability

function (16) is one-valued and C1, then also the demand function (19) is such; moreover it

takes values on the compact, convex and non-empty set SF = {F∈ℜm: ψ⋅F = d, F ≥ 0m},

where d is the (|U| × 1) vector whose generic component is du and ψ is the (m × |U|) class-

alternative incidence matrix.

The flow on the generic arc a of users belonging to the generic class u is given by the sum of

the flows of the travel alternatives in the choice set of the class which are associated with a

path including the arc:

12
fau = ∑u∈U ∑ j∈Ju Fju⋅δauj, in compact form: f = Δ⋅F. (20)

Combining (19) and (14) with equation (20) yields the network loading map, expressing the

arc flows in terms of the arc costs:

f(c) = Δ⋅F(ΔT⋅c). (21)

Because the demand function is one-valued and C1, also the network loading map is such;

moreover it takes values on the set Sf = { f ∈ℜl: f = Δ⋅F, F∈SF}, which is compact, convex

and non-empty as SF .

Combining (12) and (20) with equation (14), yields the supply function, expressing the travel

alternative generalized costs in terms of the travel alternative flows:

C(F) = ΔT⋅c(Δ⋅F), (22)

which is C1 as the arc cost function (12).

SUE can be formulated as a fixed point problem, either by combining the demand and the

supply models, or by combining the network loading map and the arc cost function.

By combining the network loading map (21) with the arc cost function (12), SUE is

formulated through the following fixed point problem in the space of arc flows:

f = f(c( f )), f∈Sf . (23)

By combining the demand function (19) with the supply function (22), the problem is

formulated through the following fixed point problem in the space of travel alternative flows:

F = F(C(F)), F∈SF . (24)

Because the demand function and the network loading map are one-valued functions (and not

point-to-set maps, as in the case of the deterministic user equilibrium) problems (23) and (24)

are equivalent, in that the arc flows corresponding through (20) to the solutions in terms of

travel alternative flows of problem (24) solve problem (23) and the travel alternative flows

corresponding through (12), (14) and (19) to the solutions to problem (23) in terms of arc

flows solve problem (24).

13
As an alternative, SUE can be addressed in the space of costs as follows:

c = c(f(c)), c∈ℜl, (25)

C = C(F(C)), C∈ℜm, (26)

yielding another two fixed point problems which are equivalent to (23) and (24), in that the

arc flows corresponding through (21) to the solutions in terms of arc costs of problem (25)

solve problem (23) and the travel alternative flows corresponding through (22) to the

solutions to problem (26) in terms of travel alternative costs solve problem (24).

Because the network loading map (21) and the arc cost function (12) are continuous and the

feasible set Sf is compact, convex and non-empty, based on Brouwer’s theorem (Khamsi and

Kirk, 2001, p. 177) the fixed point problem (23) has at least one solution. This implies the

existence of a solution also for the equivalent problems (24), (25) and (26).

2.2 Review of the sufficient conditions for uniqueness

In this section some well known conditions for the uniqueness of the solution to the SUE

problem are presented together with some recent results.

With reference to the class of demand models considered here (probabilistic, additive,

continuous and strictly-positive choice models), in Cantarella (1997) it is shown that the

network loading map is quasi strictly monotone decreasing (lemmas 3 and 6):

[f(c1)-f(c2)]T⋅(c1-c2) < 0, ∀ c1 ≠ c2 ∈Sc : f(c1) ≠ f(c2), (27)

where Sc = {c∈ℜl: c = c( f ), f ∈Sf} is the feasible arc cost set.

It follows then that it is sufficient for the SUE problem (23) to have a unique solution that the

arc cost function is monotone non decreasing (theorem 2):

[c( f1)-c( f2)] T⋅( f1- f2) ≥ 0, ∀ f1, f2 ∈Sf . (28)

It is well known (see proposition 15 in the appendix) that, as Sf is convex, it is sufficient for

condition (28) to hold that the Jacobian of the arc cost function is positive semi definite for all

14
feasible arc flows, i.e.

∇c( f ) ≥ 0, ∀f∈Sf . (29)

However, there is no supply model having practical relevance satisfying condition (28) but

not condition (29). This suggests that the difference between the two conditions is not

substantial. Condition (29) is the one always utilized in practice to discuss the uniqueness of

the equilibrium, while the more general condition (28) has mainly a theoretical relevance.

A different sufficient condition is established in Cantarella (2002) with reference to problem (25):

(c1-c2)T⋅(c1-c2) > [c(f(c1)) - c(f(c2))]T⋅(c1-c2), ∀ c1 ≠ c2 ∈Sc .

The above equation, which can be rearranged as follows:

[(c1-c(f(c1))) - (c2-c(f(c2)))]T⋅(c1-c2) > 0, ∀ c1 ≠ c2 ∈Sc ,

implies, in fact, that there cannot exist c1 ≠ c2 ∈Sc such that c1 = c(f(c1)) and c2 = c(f(c2)).

Based on proposition 15, a sufficient condition for the uniqueness of the equilibrium is also:

Il - ∇f(c)⋅∇c( f = f(c)) > 0, ∀c∈conv(Sc),

where conv(Sc) denotes the convex hull of Sc. Note that the above condition is slightly more

general than the one resulting from the application of (10) to problem (25):

∇f(c)⋅∇c( f = f(c)) - Il < 0, ∀c∈ℜl.

2.3 A new uniqueness condition

The result obtained in subsection 1.2, concerning the uniqueness of the solution to a generic

fixed point problem defined on ℜn, could be directly applied to the SUE problem formulated

in the space of costs as in (25) and (26).

However, in order to establish a result in terms of properties of the supply and demand

models separately, and not jointly through the fixed point function, we introduce an

alternative fixed point formulation in the reduced space of travel alternatives. The latter is

obtained by eliminating from the formulation one travel alternative for each class. To this end,

15
we assume that each class has at least two travel alternatives and exploit the following two

properties of the equilibrium model: a) because the demand model is additive, with reference

to each class, it is possible to subtract one component of the travel alternative costs to the

costs of all the travel alternatives of the choice set without modifying the resulting flows; b)

based on the consistency constraint (18), the flow of one travel alternative of the generic class

can be expressed in terms of the flows of all the other travel alternatives of the choice set.

This operation allows to write the Jacobian of the fixed point function as the product of two

matrices strictly related to the Jacobian of the demand function and of the supply function,

respectively, the first one of which is symmetric and negative definite. This way, proposition

14 in the appendix can be applied in order to establish a condition on the supply and demand

models which guarantees that all the eigenvalues of the fixed point function Jacobian have

real part smaller than one. On this basis, proposition 4 can be applied to ensure the uniqueness

of the equilibrium.

Based on which alternatives are chosen for the reduction operation, vector F is consistently

partitioned into two sub-vectors, i.e.

F - = I -⋅F and F ° = I °⋅F, (30)

having respectively dimensions (n × 1), with n = m-|U|, and (|U| × 1):

F = I - T⋅F - +I ° T⋅F °, (31)

where the matrices I - and I ° are obtained from the identity matrix Im by removing the rows

corresponding to the eliminated alternatives and to those remaining, respectively.

Let Č - be the (n × 1) vector obtained by subtracting to the components of the (n × 1) vector

I - ⋅C the corresponding component of the (|U| × 1) vector I °⋅C, i.e.

Č - = Ω⋅C, (32)

where:

Ω = I -⋅(Im - ψT⋅I °). (33)

16
In order to express the vectors F ° and F as a function of F -∈SF - = {F -∈ℜn: ψ⋅I - T⋅F - ≤ d, F -≥ 0n},

the following functions are introduced, respectively:

D°(F -) = d - ψ⋅I - T⋅F -, (34)

D(F -) = I - T⋅F - + I ° T⋅D°(F -). (35)

Recall that, because the demand model is additive, for any C∈ℜm it is:

F(C) = F(I - T⋅Ω⋅C). (36)

Based on (30), (36) and (35), the fixed point problem (24) becomes:

F - = I -⋅F(I - T⋅Ω⋅C(D(F -))), F -∈SF -, (37)

while, because for any F∈SF it is:

F = D(I -⋅F), (38)

based on (32) and (36), the fixed point problem (26) becomes:

Č - = Ω⋅C(D(I -⋅F(I - T⋅Č -))), Č -∈ℜn. (39)

Problem (39) is suitable to be analyzed through the methodology defined in section 1 because

the feasible set coincides with the space of reduced cost vectors. Consistently, in the

following we set Č - = x and:

h(x) = Ω⋅C(D(I -⋅F(I - T⋅x))), x∈ℜn. (40)

The SUE problem has thus been reformulated as an instance of the generic fixed point (1).

Then, in order to apply proposition 4, we now differentiate equation (40) using the derivation

rules 7 in the appendix. Differentiating equations (22), (34) and (35) yields, respectively:

∇C(F) = ΔT⋅∇c( f = Δ⋅F)⋅Δ, (41)

∇D°(F -) = -I -⋅ψT, (42)

∇D(F -) = I -⋅(Im - ψT⋅I °) = Ω. (43)

Then, differentiating equation (40) and using (38) yields:

∇h(x) = I -⋅∇F(C = I - T⋅x)⋅I - T ⋅ Ω⋅∇C(F = F(I - T⋅x))⋅ΩT, (44)

17
which, based on (41), can be also expressed as:

∇h(x) = I -⋅∇F(C = I - T⋅x)⋅I - T ⋅ Ω⋅ΔT⋅∇c( f = Δ⋅F(I - T⋅x))⋅Δ⋅ΩT. (45)

Proposition 5 - uniqueness of SUE

If, at each feasible arc flow f∈Sf , the Jacobian of the arc cost function summed up to the

identity matrix multiplied by the following positive scalar:

α = -max{(e / ||Δ⋅ΩT⋅e ||)T⋅[I -⋅∇F(C = I - T⋅x)⋅I - T] -1⋅(e / ||Δ⋅ΩT⋅e ||):

e∈ℜn, ||e|| = 1, ||Δ⋅ΩT⋅e || > 0, x∈ℜn}, (46)

is positive definite, i.e.

∇c( f ) +α⋅Il > 0, ∀f∈Sf , (47)

then the solution to the SUE problem is unique.

Proof.

With reference to any given x∈ℜn, let:

A = [I -⋅∇F(C = I - T⋅x)⋅I - T] and B = [Ω⋅ΔT⋅∇c( f = Δ⋅F(I - T⋅x))⋅Δ⋅ΩT].

Equation (45) becomes: ∇h(x) = A⋅B. Moreover, it is proved in Gentile (2002) that A is

symmetric and negative definite. Based on (46), we then have that α is positive.

In hypothesis (47), which based on (55) can be expressed as:

gT⋅∇c( f )⋅g > -α, ∀g∈ℜl: ||g|| = 1, ∀f∈Sf ,

let g = Δ⋅ΩT⋅e / ||Δ⋅ΩT⋅e ||, with e∈ℜn: ||e|| = 1, ||Δ⋅ΩT⋅e || > 0, and f = Δ⋅F(I - T⋅x)∈Sf .

Based on (46), we have:

(Δ⋅ΩT⋅e / ||Δ⋅ΩT⋅e ||)T⋅∇c( f = Δ⋅F(I - T⋅x))⋅(Δ⋅ΩT⋅e / ||Δ⋅ΩT⋅e ||) > -α ≥

≥ (e / ||Δ⋅ΩT⋅e ||)T⋅[I -⋅∇F(C = I - T⋅x)⋅I - T] -1⋅(e / ||Δ⋅ΩT⋅e ||). (48)

If ||Δ⋅ΩT⋅e || = 0, then: eT⋅B⋅e = 0; while, because A < 0, based on (58), it is: eT⋅(-A-1)⋅e > 0.

18
On these bases, we have:

eT⋅(B-A-1)⋅e > 0, ∀e∈ℜn: ||e|| = 1, ∀x∈ℜn

meaning that B-A-1 is positive definite for each x∈ℜn.

Then, based on proposition 14, all eigenvalues of A⋅B have real part smaller than one. On this

basis, condition (8) holds, so that, based on corollary 3 and proposition 4, the equilibrium is

unique. 

3 Numerical applications

3.1 Logit demand model

In the elementary cases presented in the following the demand model is multinomial Logit.

The advantage of using this model lays in the fact that its choice probabilities are expressed in

closed form, so that the demand function Jacobian is obtained analytically when calculating

equation (46). In this case, equation (16) becomes:

exp (V ju θu )
P (V : k ∈ J u ) =
u u
, (49)
∑ exp (V θu )
j k u
k
k∈J u

where θu is a constant parameter proportional to the standard deviation of εju.

Differentiating the above equation yields:

δhj δhk
⋅ exp (V j θu ) ⋅ ∑ exp (Vk θu ) − ∑ ⋅ exp (Vku θu ) ⋅ exp (V ju θu )
u u
∂ Puj (Vku : k ∈ J u ) θu k∈J u k∈J u θu
= =
∂Vhu ⎛ ⎞
2

⎜ ∑e k
Vu θu
⎟
⎝ k∈Ju ⎠

⎛ ⎞
1 exp (V ju θu ) ⎜ j exp (Vhu θu ) ⎟ 1
= ⋅ ⋅ δh − ⎟ = θ ⋅ Pj ⋅ ( δh − Ph ) , (50)
u j u

θu ∑ exp (Vku θu ) ⎜ ∑ exp (Vk θu ) ⎟ u

u
⎜
k∈J u ⎝ k∈J u ⎠

where δh j = 1, if h = j, while δh j = 0, otherwise. On this basis, the generic element of the

19
Jacobian of the demand function (19) is:

∂ Fju ( Cku : k ∈ J u ) ∂ Pju (Vku : k ∈ J u )

⋅ Pj ⋅ ( δhj − Phu ) .
du u
= −d u ⋅ =− (51)
∂C u
h ∂Vh u
θu

3.2 The case of elastic demand

Consider the elementary network consisting of a single arc that connects one o/d couple.

Users choose whether making a trip (travel alternative 1) or staying at home (travel alternative

2). Suppose that the congestion on the network is represented through the following BPR arc

cost function:

c( f ) = L⋅[1+γ⋅( f /k)4],

where L is the zero-flow travel time, k is the arc capacity, while γ is a constant parameter

determining how much the arc cost increases (γ > 0), or decreases (γ < 0), with the flow. The

Jacobian of the arc cost function is then given by:

∇c( f ) = (4 /f )⋅L⋅γ⋅( f /k) 4,

The demand flow d travelling between the o/d couple is split between the two travel

alternatives on the basis of the Logit formula (49), where we assume: V1 = X-c and V2 = 0,

implying that making the trip yields, besides the travel cost, a utility X, while staying at home

yields zero utility.

Because it is: n = 1, equation (46) becomes:

α = -1 /||Δ⋅ΩT||2⋅max{[I -⋅∇F(I - T⋅x)⋅I - T] -1: x∈ℜn}.

Based on (51) we have: [I -⋅∇F(I - T

⋅x)⋅I - T
] = -(d/θ)⋅P1⋅P2 . The product P1⋅P2 reaches its

maximum value 0.25 at P1 = P2 = 0.5. Moreover, it is: Δ = (1, 0) and Ω = (-1, 1), so that we

have: ||Δ⋅ΩT|| = 1. On this basis, it is: α = 4⋅θ /d.

Because it is: l = 1, hypothesis (47) becomes:

(4 /f )⋅L⋅γ⋅( f /k)4 > -4⋅θ /d, ∀ 0 ≤ f ≤ d.

20
We then have:

γ > -(θ /L) / (d /k)4.

When γ > 0, the uniqueness of the equilibrium is guaranteed regardless the congestion level;

on the contrary, when γ < 0, the sufficient condition for the uniqueness of the equilibrium,

becomes:

d 1 θ
< 4 ⋅ .
k −γ L

Figure 1 below shows that, when the network tends to be congested (that is, the demand is

high with respect to the arc capacity) and the choice model tends to be deterministic (that is,

the standard deviation of random residuals is low with respect to the travel cost), the

uniqueness of the equilibrium may result unguaranteed. Actually, as it is shown in figure 2,

high congestion may yield multiple equilibrium solutions.

2
1.8
d 1 θ
1.6 < 4 ⋅
k −γ L
1.4
1.2
d /k

1
uniqueness
0.8 is guaranteed
0.6
0.4
0.2
0
0 2 4 6 8 10
θ /L

Figure 1. Field of values of the ratios d/k and θ/L where the uniqueness of the equilibrium is

guaranteed.

21
 1
d/k = 0.9 1
d/k = 1.3
0.9 0.9
0.8 0.8
0.7 0.7
0.6 0.6
0.5 0.5
0.4 0.4
0.3 0.3
0.2 0.2
0.1 0.1
0 0
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

1
d/k = 1.5 1
d/k = 1.8
0.9 0.9
0.8 0.8
0.7 0.7
0.6 0.6
0.5 0.5
0.4 0.4
0.3 0.3
0.2 0.2
0.1 0.1
0 0
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Figure 2. Fixed points in terms of f1 /d for different values of the ratio d/k. With reference to

each diagram, the intersections between the thick line and the thin line represent the

equilibrium flow patterns. The case θ /L = 2 has been considered, where for d/k < 1 the

uniqueness of the equilibrium is guaranteed, while θ /X = 10.

3.3 The case of an actuated traffic light

Consider a network consisting of two arcs (travel alternatives 1 and 2) that connect the same

o/d couple. Suppose that these arcs terminate with an actuated traffic light operating with the

minimum cycle T = k⋅L /(k-f1-f2), where L is the lost time and k is the arcs’ capacity. The cost

of each arc is equal to one half of its red light:

c1 = 0.5⋅L⋅(k-f1) /(k-f1-f2) , c2 = 0.5⋅L⋅(k-f2) /(1-f1-f2).

The Jacobian of the arc cost function is then given by:

0.5 ⋅ L ⎛ −2 ⋅ k + 2 ⋅ f 1 + f k− f ⎞
∇c ( f ) = ⋅⎜ ⎟ .
(k − f1 − f 2 ) k − f1 − 2 ⋅ k + 2 ⋅ f 2 + f1 ⎠
2
⎝
22
The demand flow d < k travelling between the o/d couple is split between the two travel

alternatives on the basis of the Logit formula (49), where we assume: V1 = -c1 and V2 = -c2.

Also in this case it is: n = 1. Moreover, it is: Δ = I2 and Ω = (-1, 1), so that we have:

||Δ⋅ΩT|| = 21/2. On this basis, it is: α = 2⋅θ /d,

Ω⋅ΔT⋅∇c( f )⋅Δ⋅ΩT = -0.5⋅L /(k-f1-f2)2⋅[3⋅k -2⋅( f1+ f2)].

Then, the first inequality of equation (48), which is a sufficient condition for the uniqueness

of the equilibrium, becomes: (2⋅L+4⋅θ)⋅(d/k)2 -(3⋅L +8⋅θ)⋅d/k +4⋅θ > 0.

Then, because it is: d/k < 1, we have:

d ( 3 + 8 ⋅ θ L ) − 9 + 16 ⋅ θ L
< .
k (4 + 8 ⋅ θ L)
Figure 3 below shows again that, when the network tends to be congested and the choice

model tends to be deterministic, the uniqueness of the equilibrium may result unguaranteed.

Actually, as it is shown in figure 4, high congestion may yield multiple equilibrium solutions.

1
d ( 3+8⋅θ L ) − 9 +16⋅θ L
0,9 <
k ( 4 +8⋅θ L )
0,8
0,7
0.63
0,6
d /k

0,5
uniqueness
0,4 is guaranteed
0,3
0,2
0,1
0
0 2 4 6 8 10
θ /L

Figure 3. Field of values of the ratios d/k and θ/L where the uniqueness of the equilibrium is

guaranteed.

23
 1
d/k = 0.5 1
d/k = 0.8
0,9 0,9
0,8 0,8
0,7 0,7
0,6 0,6
0,5 0,5
0,4 0,4
0,3 0,3
0,2 0,2
0,1 0,1
0 0
0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

1
d/k = 0.9 1
d/k = 0.95
0,9 0,9
0,8 0,8
0,7 0,7
0,6 0,6
0,5 0,5
0,4 0,4
0,3 0,3
0,2 0,2
0,1 0,1
0 0
0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

Figure 4. Fixed points in terms of f1 /d for different values of the ratio d/k. With reference to

each diagram, the intersections between the thick line and the thin line represent the

equilibrium flow patterns. The case θ /L = 2 has been considered, where case for d/k < 0.63

the uniqueness of the equilibrium is guaranteed.

Conclusion

With reference to a generic fixed point problem defined through a C1 function on ℜn,

applying an original result regarding unconstrained non-linear programs (referred to as the

bend down theorem), a new sufficient condition for the uniqueness of the solution is derived,

requiring the Jacobian of the fixed point function minus the identity matrix to be non-singular.

In order to exploit this result, referring to the case where the demand model is additive, an

alternative fixed point formulation of the SUE problem defined on the reduced space of travel

alternative generalized costs has been proposed. On these bases, we have derived the

following sufficient condition for the uniqueness of the equilibrium: the Jacobian of the arc
24
cost function plus the identity matrix multiplied by a positive scalar, whose value is strictly

related to the Jacobian of the demand function, is positive definite; which is weaker than

requiring the Jacobian of the arc cost function to be positive semi definite.

Acknowledgments

I could not write this work without the active support of Professor Natale Papola and of

Professor Giulio Erberto Cantarella. In particular, the bend down theorem is to be considered

a joined achievement.

References

T. M. Apostol, Mathematical analysis: second edition, Addison-Wesley, Boston, MA (1974).

F. Jr. Ayres, Theory and problems of matrices, Schaum, New York, NY (1962).

M. Beckman, C. B. McGuire and C. B. Winsten, Studies in the economics of transportation,

Yale University Press, New Haven, CT (1956).

G. Bellei, G. Gentile and N. Papola, “Network pricing optimization in multi-user and

multimodal context with elastic demand”, Transportation Research B 36, 779-798 (2002).

G. Bellei, G. Gentile and N. Papola, “Assegnazione alle reti multimodali in presenza di

congestione”, in Metodi e tecnologie dell’ingegneria dei trasporti. Seminario 2001, G.

Cantarella and F. Russo (eds), Franco Angeli, Milan, Italy (2003).

M. Ben Akiva and S. Lerman, Discrete choice analysis: theory and application to travel

demand, MIT Press, Cambridge, MA (1985).

D. Bertsekas, Nonlinear programming, Athena Scientific, Bellmont, MA (1995).

G. E. Cantarella, “A general fixed-point approach to multimode multi-user equilibrium

assignment with elastic demand”, Transportation Science 31, 107-128 (1997).

G. E. Cantarella, “Condizioni di unicità dei flussi e dei costi di equilibrio stocastico”, in

Metodi e tecnologie dell’ingegneria dei trasporti. Seminario 2000, G. Cantarella and F. Russo

25
(eds), Franco Angeli, Milan, Italy (2002).

E. Cascetta, Teoria e metodi dell’ingegneria dei sistemi di trasporto, UTET, Turin, Italy

(1998).

E. Cascetta, Transportation systems engineering: theory and methods, Kluwer Academic

Publishers, Dordrecht, The Netherlands (2001).

L. D’Acierno, B. Montella and M. Gallo, “Multimodal assignment to congested networks:

fixed-point models and algorithms”, in Proceedings of PTRC 2002 “European Transport

Conference 2002”, Cambridge, UK (2002).

S. C. Dafermos, “Traffic equilibrium and variational inequalities”, Transportation Science 14,

42-54 (1980).

C. F. Daganzo and Y. Sheffi, “On stochastic models of traffic assignment”, Transportation

Science 11, 253-274 (1977).

C. F. Daganzo, “Stochastic network equilibrium with multiple vehicle types and asymmetric,

indefinite link cost Jacobians”, Transportation Science 17, 282-300 (1983).

C. Fisk, “Some developments in equilibrium traffic assignment”, Transportation Research B

14, 243-255 (1980).

G. Gentile, Il problema di progetto di rete in contesto multiutente, multimodo e a domanda

elastica, Ph.D. thesis, Università degli Studi di Roma “La Sapienza”, Rome, Italy (2000).

G. H. Golub and C. F. Van Loan, Matrix computations. 3rd edition, Johns Hopkins University

Press, Baltimore, MD (1996).

M. A. Khamsi and W. A. Kirk, An introduction to metric spaces and fixed point theory, John

Wiley & Sons, Inc. (2001).

N. Oppenheim, Urban travel demand modelling, John Wiley, New York, NY (1995).

M. Patriksson, The traffic assignment problem: models and methods, VSP, Utrecht, The

Netherlands (1994).

26
W. B. Powell and Y. Sheffi, “The convergence of equilibrium algorithms with predetermined

step sizes”, Transportation Science 16, 45-55 (1982).

Y. Sheffi, Urban transportation networks: equilibrium analysis with mathematical

programming methods, Prentice-Hall, Englewood Cliffs, NJ (1985).

M. J. Smith, “The existence, uniqueness and stability of traffic equilibria”, Transportation

Research B 13, 295-304 (1979).

27
Appendix

The bend down theorem

It is here established a new sufficient condition for the existence of a global minimum to an

unconstrained non-linear program whose objective function is C1. The condition is that at

least one stationary point exists, at least one among all the connected components of the set of

the stationary points is bounded, and each stationary point is a local minimum. In other words,

this implies that the function is bounded from below and attains its minimum at some finite

point.

Moreover, the same condition is proved to ensure that all local minima belong to a simply

connected set and then are guaranteed to be global.

The name of the theorem is meant to recall the base idea: in a neighborhood of an isolated

local minimum the objective function increases; then, in order to decrease so having the

possibility of yielding another non-connected local minimum, being C1 it has to pass first

through a stationary point, which is not a minimum, where it can bend down. In the case

where n = 1, the assertion is trivial. But in the more general case where n > 1 it is not

immediate. On the contrary, at a first glace it seams that a surface can increase and decrease

without passing through a flat point.

Proposition 6 - bend down theorem

With reference to the generic unconstrained non-linear program

min x∈ℜ n ϕ(x)

whose objective function ϕ is C1,

let:

X s be the set of the stationary (null-gradient) points, i.e. X s = {x∈ℜ n: ∇ϕ(x) = 0n},

28
X m be the set of the local minima, i.e. X m = {x∈ℜ n: ∃ ε > 0 | ϕ(x) ≤ ϕ(y), ∀y∈N(x, ε)}

where N(x, ε) = {y∈ℜn: ||y – x|| ≤ ε} is the closed ball centred at x∈ℜn with a ray of length ε > 0,

S be the set of the global minima, i.e. S = {x∈ℜ n: ϕ(x) ≤ ϕ(y), ∀y∈ℜ n}.

If:

a) there is at least one stationary point, i.e. X s ≠ ∅,

b) at least one among the connected components of X s is bounded,

c) each stationary point is a local minimum, i.e. X s = X m ;

then, the set of the global minima:

i) is non-empty, i.e. S ≠ ∅,

ii) is simply connected,

iii) coincides with that of the stationary points, i.e. S = X s.

Proof.

Consistently with a) and b), let X* ⊆ X s be a bounded and connected set of stationary points

which is separate from any other stationary point. Based on c) the points of X* are all local

minima. Then, they all have the same value of objective function: ϕ(x) = ϕ*, ∀x∈X*.

Moreover, because ϕ is continuous, then X* is closed.

In the trivial case where X* = ℜn, it is: S = X*, and the results i), ii) and iii) follow. In the

following it is address the case where X* ⊂ ℜn.

To this end it is useful to define by Xℓ , with ℓ ≥ 0, a set having the following properties:

1) it is strictly contained in ℜn, i.e. Xℓ ⊂ ℜn,

2) its interior Xℓ° contains X*, i.e. Xℓ° ⊇ X*,

3) it is closed, bounded and connected,

4) at its boundary ∂Xℓ the objective function has a same value ℓ+ϕ*, while at the complement

of X* with respect to its interior Xℓ° the objective function has a value belonging to the

29
 open interval (ϕ*, ℓ+ϕ*), i.e.

ϕ(x) -ϕ* = 0, ∀x∈X*,

0 < ϕ(x) -ϕ* < ℓ, ∀x∈((Xℓ \ ∂Xℓ ) \ X*),

ϕ(x) -ϕ* = ℓ, ∀x∈∂Xℓ ,

5) it contains no other stationary points besides X*, i.e. (Xℓ ∩ X s) = X*.

Clearly, if such a set exists, it is unique: in fact, if by contradiction there were two such sets,

at the boundary of their intersection minus the intersection of their boundaries, which is not

empty because the interiors of both sets contain X*, the value of the objective function would

be ℓ, despite these points are internal to one of the two sets, so that such value should be

smaller than ℓ.

In the following we will define an expansion operation on Xℓ yielding a set Xℓ+Δℓ with the

same properties of Xℓ but with a higher value of objective function at the boundary. On this

basis, we will build starting from X* = X0 a sequence of sets, where the interior of each set

contains the previous ones, until we get the whole space ℜn, thus proving the theorem.

With reference to a point x∈∂Xℓ , for each direction y∈Yx pointing outwards from Xℓ , i.e.

Yx = {y∈ℜn: ||y|| = 1 , ∃ θxy > 0 | x+θ⋅y ∉ Xϕ(x) , ∀θ∈(0, θx y]} ,

let αx y be the maximum value of α, bounded to a fixed value αM > 0, such that the function

ϕ(x+β⋅y) is strictly monotone increasing with respect to β∈(0, α); formally, it is:

αxy = max{α: α ≤ αM , ∇ϕ(x+β⋅y)T ⋅ y > 0, ∀β∈(0, α)}.

As ϕ is C1, we have that αxy > 0 both for ℓ = 0, because any x∈∂X* is a local minimum (the

directional derivative is positive right out of X* and its sign holds for a finite step), and for

ℓ > 0, because based on 5) and 4), respectively, the gradient ∇ϕ(x) at any point x∈∂Xℓ is non-

null and points outwards from Xℓ (the positive sign of the directional derivative holds for a

finite step). Note that the bound αM is introduced in order to avoid that αxy → ∞. Then,

30
besides the case αxy = αM , at the point x+αxy ⋅y the gradient becomes perpendicular to the

direction y , while based on c) it cannot be null. Let now αx be the infimum of αxy with

respect to y in Yx , i.e. αx = inf{αxy : y∈Yx}; clearly it is 0 < αx ≤ αM.

On this basis we can define the set Aℓ = Xℓ ∪ x∈∂Xℓ N(x, αx), as the union of Xℓ and of the

closed balls N(x, αx) centred at the points of the boundary of Xℓ with a ray αx . By

construction, Aℓ is closed, bounded, connected and its interior Aℓ° contains Xℓ; moreover Aℓ

does not contain other stationary points besides X*, as at any point of (Aℓ \ Xℓ) ϕ is strictly

monotone increasing along at least one direction.

The expansion of Xℓ can be then achieved as follows. Let Δℓ = 0.5 ⋅ min{ϕ(z)-ℓ: z∈∂Aℓ}.

Because ϕ is continuous and ∂Aℓ is closed and bounded, Δℓ is well defined. Now, for each

point z∈∂Aℓ , consider the projection p(z) of z on Xℓ: p(z) = argmin{||z-x||: x∈Xℓ}; clearly it is:

p(z) ≠ z. Because ϕ(p(z)+β⋅(z-p(z))) is strictly monotone increasing with respect to β∈(0, 1),

that is along the segment connecting p(z) to z itself, at each z∈∂Aℓ we have: ϕ(z) > ℓ. This

implies that Δℓ is strictly positive and that there is a point p(z)+ηz⋅(z-p(z)) , with ηz ∈(0, 1), at

which the value of the objective function is ℓ+Δℓ, i.e. ϕ(p(z)+ηz⋅(z-p(z))) = ℓ+Δℓ. The set

Xℓ+Δℓ is defined as the union of Xℓ with all the segments, for each z on the boundary of Aℓ ,

from p(z) to such a point:

Xℓ+Δℓ = Xℓ ∪ z∈∂Aℓ {w∈ℜ n : w = p(z)+α⋅(z-p(z)), ∀α∈(0, ηz]}.

By construction, properties 1) - 5) hold with respect to Xℓ+Δℓ .

Consider now all possible ℓ ≥ 0 for which there exist a set Xℓ , and let:

λ = sup{ℓ ≥ 0: ∃ Xℓ},

Zλ = lim ℓ → λ Xℓ .

Clearly Zλ does not satisfy some of the properties 1) - 5), otherwise the expansion operation

would have been possible.

31
Two cases may occur: λ = ∞ , λ < ∞.

In the case λ = ∞, if by contradiction Zλ ⊃ ℜn, then the points of ∂Zλ would be infinite points.

But ϕ is continuous, then Zλ = ℜn.

In the case λ < ∞, because by construction the limit set Zλ satisfies properties 2) - 4), then it

does not satisfy either 1) or 5). Based on 4), the latter possibility contradicts hypothesis c),

then it is: Zλ = ℜn.

Because in both cases Zλ = ℜn, by construction there is no other stationary point in ℜn besides

X*, i.e. X s = X*. Then, if X* is simply connected, the results i), ii) and iii) follow immediately.

Suppose that by contradiction X* is not simply connected. Clearly through the expansion

operations its holes tend to reduce to single points. However, this can happen, neither for a

finite ℓ, as this implies that a local maximum is achieved, nor for ℓ → ∞, as this implies the

existence of an infinite point. 

40 40
X30
30 30
∂X30 x*
20 10
20
X30 10 20
10
x 1 xs x* ∂X30
30 s
x
20

10
x1
20
30
40
a) b)

Figure 5. In the two examples above λ = 30 because for X30 (grey areas), while properties

1)-4) hold, property 5) does not, due to the existence of a stationary point xs on ∂X30. This

allows for the existence of another local minimum x1, separated from x* = X*, but having the

same value of objective function. However, based on property 4) in the proof, xs is not a local

minimum, so that hypothesis c) is violated.

32
The bend down theorem induces to point out the class of C1 functions whose stationary points

are local minima constituting a bounded set. These functions share the fundamental property

of pseudo-convex functions (a C1 functions is pseudo-convex if ∇ϕ(x1)T⋅(x2-x1) ≥ 0 implies

ϕ(x1) ≥ ϕ(x2); that is, if the function increases locally in some direction at x1, it increases

globally in that direction): local minima are guaranteed to be global and are connected among

themselves.

50 70

40
30 20 10 60

x1
10
20
20
30
50
x1
40
30

a) x2
b)

Figure 6. a) Example of a function which is not pseudo-convex (for instance, see direction

x2-x1 at x1) yet belongs to the class of C1 functions whose stationary points are local minima.

b) Example of a pseudo-convex function having a stationary point x1 which is not a local

minimum.

33
Eigenvalues and definiteness of real matrices

7 - Some differentiation rules

∇f(g(x)) = ∇g(x)⋅∇f(g = g(x)),

∇[A⋅f(x)] = ∇f(x)⋅AT,
∇[f(x)T⋅h(x)] = ∇f(x)⋅h(x) + ∇h(x)⋅f(x). 

8 - Some properties of the eigenvalues

Referring to a generic square matrix A∈ℜn×n, let λj(A) = λjR(A) + i⋅λjC(A) be the j-th of its n

eigenvalues and λ(A) be the associated diagonal matrix. Recalling that a complex valued

eigenvalue always occurs jointly with its complex conjugate, let IR(A) be the set of indices

individuating the real valued eigenvalues, and IC(A) be a set of indices individuating complex

valued eigenvalues such that there is one index for each conjugated couple of eigenvalues.

The following properties hold:

λ(b⋅A + c⋅In) = b⋅λ(A) + c⋅In , for any b∈ℜ and c∈ℜ, (52)

|A| = ∏ j = 1 , … , n λj(A) = ∏ j∈IR(A) λj(A) ⋅ ∏ j∈IC(A) [λjR(A)2 + λjC(A)2], (53)

λ(A) = λ(W⋅A⋅W -1), for any W∈ℜn×n: |W | ≠ 0. (54)

For further details see Golub and Van Loan (1996), p. 310. 

9 - Some properties of definite matrices

Referring to a generic square matrix A∈ℜn×n, for shortness we denote definiteness as follows:

A > 0 ≡ xT⋅A⋅x > 0, ∀x∈ℜn: x ≠ 0,

A ≥ 0 ≡ xT⋅A⋅x ≥ 0, ∀x∈ℜn.

The following properties hold:

A > 0 ↔ eT⋅A⋅e > 0, ∀e∈ℜn: ||e|| = 1, (55)

34
A > 0 → W⋅A⋅W T > 0, for any W∈ℜn×n: |W | ≠ 0, (56)

A ≥ 0 → W⋅A⋅W T ≥ 0, for any W∈ℜm×n. (57)

Moreover, if the matrix at hand is symmetric, i.e. A T = A, the following properties hold:

A > 0 → A-1 > 0, (58)

A > 0 → ∃W∈ℜn×n: |W| ≠ 0, A = W⋅W T. (59)

For further details see Golub and Van Loan (1996), p. 141, Bertsekas (1995), p. 545, Ayres

(1962), p. 134. 

Proposition 10

A real matrix B∈ℜn×n that when summed up to a real matrix A∈ℜn×n yields a positive (semi)

definite real matrix, has generic eigenvalue with real part (equal to or) greater than

-z H⋅A⋅z / ||z||2, where z is a correspondent eigenvector.

Proof.

Because A+B is positive (semi) definite, we have:

xT⋅(A+B)⋅x ≥ 0, ∀x∈ℜn | xT⋅(A+B)⋅x > 0, ∀x∈ℜn: x ≠ 0 ,

which can be written as follows:

xT⋅B⋅x ≥ -xT⋅A⋅x, ∀x∈ℜn | xT⋅B⋅x > -xT⋅A⋅x, ∀x∈ℜn: x ≠ 0 . (60)

Let λj(B) = λjR(B) + i⋅λjC(B) be the generic eigenvalue of B and z = (zR +i⋅zI) ≠ 0 a

correspondent eigenvector; we have:

B⋅(zR +i⋅zI) = (λjR(B) + i⋅λjC(B))⋅(zR +i⋅zI).

The above equation is equivalent to the following system of two equations:

B⋅zR = λjR(B)⋅zR -λjC(B)⋅zI , B⋅zI = λjR(B)⋅zI +λjC(B)⋅zR .

Left-multiplying the two equations of the above system by zRT and zIT, respectively, we

obtain:

zRT⋅B⋅zR = λjR(B)⋅zRT⋅zR -λjC(B)⋅zRT⋅zI , zIT⋅B⋅zI = λjR(B)⋅zIT⋅zI +λjC(B)⋅zIT⋅zR .

35
On the basis of (60), the right side of the above two equations is, respectively, equal to or

greater than -zR T⋅A⋅zR and -zI T⋅A⋅zI . Moreover, because it is: (zR + i⋅zI) ≠ 0, in the case where

A+B is positive definite at least one of them is strictly greater. Then, their sum, which is equal

to:

λjR(B)⋅zRT⋅zR -λjC(B)⋅zRT⋅zI +λjR(B)⋅zIT⋅zI +λjC(B)⋅zIT⋅zR = λjR(B) ⋅ (||zR||2 + ||zI||2) = λjR(B) ⋅ ||z||2,

is (equal to or) greater than:

-zR T⋅A⋅zR -zI T⋅A⋅zI = -(zR - i⋅zI) T⋅A⋅(zR + i⋅zI) = -z H⋅A⋅z.

Because it is: z ≠ 0, we than have:

λjR(B) ≥ -z H⋅A⋅z / ||z||2 | λjR(B) > -z H⋅A⋅z / ||z||2 ,

which proves the assertion. 

Corollary 11

A real matrix B∈ℜn×n that when summed up to the identity matrix yields a positive (semi)

definite real matrix, has all eigenvalues with real part (equal to or) greater than minus one.

Proof.

With reference to proposition 10, let A = In. 

Corollary 12

A positive (semi) definite real matrix B∈ℜn×n has all eigenvalues with (null or) positive real

part.

Proof.

With reference to proposition 10, let A = 0n. 

36
Proposition 13

The product of a symmetric positive definite real matrix A∈ℜn×n and of a positive (semi)

definite real matrix B∈ℜn×n, not necessarily symmetric, has all eigenvalues with (null or)

positive real part (it is well known that the product of two definite matrices is not definite).

Proof.

Because A is a symmetric positive definite real matrix, based on proposition (59) there exist a

non-singular real matrix W∈ℜn×n such that A = W⋅W T. Left-multiplying by W -1 and right-

multiplying by W both sides of the relation A⋅B = W⋅W T⋅B yields: W -1⋅A⋅B⋅W = W T⋅B⋅W.

Then, based on proposition (54), we have: λ(A⋅B) = λ(W T⋅B⋅W ).

Because B is positive (semi) definite, based on propositions (56) and (57) also W T⋅B⋅W is

such. Then, based on corollary 12, all the eigenvalues of W T⋅B⋅W have positive real part, and

so does the product A⋅B. 

Proposition 14

The product of a symmetric negative definite real matrix A∈ℜn×n and of a real matrix

B∈ℜn×n, not necessarily symmetric, that when summed up to -A-1 yields a positive definite

real matrix, has all eigenvalues with real part smaller than one.

Proof.

Following the same reasoning developed in the first part of the proof of proposition 13, we

have: λ(-A⋅B) = λ(W T⋅B⋅W).

Because B -A-1 is positive definite, based on (56) also W T⋅(B -A-1)⋅W = W T⋅B⋅W + In is such,

where it is: -A-1 = W T-1⋅W -1. Then, based on corollary 11, all the eigenvalues of W T⋅B⋅W

have real part greater than minus one, so that, based on (52), all the eigenvalues of the product

A⋅B have real part smaller than one. 

37
Proposition 15

Let f : X⊆ℜn → ℜn, be a C1 function defined on a convex set X. If its Jacobian ∇f(x)T is

positive definite (semi positive definite) for each x∈X, then the function is strictly monotone

increasing (monotone non decreasing):

∇f(x) > 0, ∀x∈X → [f(x 1) -f(x 2)] T⋅(x 1-x 2) > 0, ∀x 1, x 2∈ℜn, x 1≠ x 2,

∇f(x) ≥ 0, ∀x∈X → [f(x 1) -f(x 2)] T⋅(x 1-x 2) ≥ 0, ∀x 1, x 2∈ℜn.

Proof.

See Cascetta (1998), p. 654, and Bertsekas (1995), p. 561. 

38