UNIVERSITY OF PISA
Department of Economics and Management SANT’ANNA SCHOOL OF ADVANCED STUDIES
Master of Science in Economics MASTER’S THESIS
Variational Inequality Theory and Supply Chain Networks
Advisor
Prof. Laura Carosi
Candidate Mirko Sembranti
Contents
Introduction 7 1 Mathematical Prerequisites 9 1.1 Convexity . . . 9 1.2 3 Types of Monotonicity . . . 11 1.3 Lipschitz Functions . . . 12 1.4 Optimality Conditions . . . 13 1.5 Graph Theory . . . 131.6 Paths and Subgraphs properties . . . 16
2 Variational Inequality Theory 18 2.1 Why Variational Inequality Theory . . . 18
2.2 Problem Definition . . . 19
2.3 Existence and Uniqueness Results . . . 20
2.4 Partitionability of VI . . . 22
2.5 Stability and Non Parametric Sensitivity Analysis . . . 25
2.6 Parametric Sensitivity Analysis . . . 27
3 Problem classes 30 3.1 Optimization Problems . . . 30
3.2 Complementarity Problem . . . 34
3.3 Fixed Point Problems . . . 37
4 Supply Chain Theory 40 4.1 An Introductory Model to Supply Chain Networks . . . 40
4.2 The Literature on Supply Chain Networks with disruption risks 45 4.3 What is a supply chain network, the role of disruption risks . . 46 4.4 A Supply Chain model with disruption risks and random demand 48
4.5 Retailer Behavior . . . 51
4.6 The Market Equilibrium VI Conditions . . . 52
5 Industrial Networks with Endogenous Risk Aversion to Dis-ruption risks 54 5.1 Manufacturer’s case . . . 55
5.2 Retailer’s case . . . 59
5.3 Market Equilibrium Conditions . . . 63
5.4 Sensitivity Analysis . . . 67
Introduction
The research field of Variational Inequalities came to exist with the resolution of the Ambiguous Boundary Conditions Problem, posed by the Italian Pro-fessor Antonio Signorini in 1959, and named after him by Gaetano Fichera, former pupil which proved the existence of a solution in 1963 [2].
The problem had many implication within mathematics, computer science, engineering and economics nonetheless, initial results were generalized to In-finite dimensional spaces by Stampacchia [37].
A finite dimensional breakthrough came with Dafermos, [8] in 1980, with an application of the Variational Inequality Theory to transportation networks. Three years later, [11], Dafermos and Nagurney developed a literature on competitive oligopolies treated within a VI framework, and in the same year, Dafermos published a General Iterative Scheme to solve VI problems and determine equilibrium solutions.
in 1991, Harker [20] developed a theoretical link between VI theory and Game Theory under non disjoint strategic sets.
In [28], a network equilibrium model is formulated by Nagurney, Dong and Zhang, in [23], Nagurney et al introduce the role of disruption risks. Later publications include [1], [16], [27], the topics addressed involves both appli-cations within the economic theory and theoretical results pertinent to the field.
In our work we tried to account for the most foundational mathematical properties pertinent to the field of Variational Inequalities, we collected and organized the basic theorems for the existence and uniqueness of a solution, and sensitivity analysis nonetheless.
We present several problem classes, such as optimization, complementarity and fixed point problems, with a particular emphasis on the connection be-tween Karash Kuhn Tucker systems and Variational Inequalities.
risks as presented by [28], we also develop some links with graph theory, as already developed in [39].
Finally, we propose an original capacity based model of industrial competi-tion, we try to account for a few of the empirical regularities within industrial scenarios.
We suggest that a formulation based on disruption risks, supply chain con-tracts and size-based technology can provide a good hypothetical representa-tion of industrial strategic behavior, while explaining a few of the regularities observed in the evolutionary literature.
Chapter 1
Mathematical Prerequisites
1.1
Convexity
Definition 1.1 Let Rn denote the n-dimensional set of real numbers, a sub-set K ⊂ Rn is convex if ∀(x, y) ∈ K , ∀α ∈ [0, 1] , the line segment of the
elements still belongs to K, or, formally :
αx + (1 − α)y ∈ K; ∀(x, y) ∈ K, ∀α ∈ [0, 1] Some typical convex sets are presented below
Definition 1.2 (Hyperplane) S = [x : Ptx = α], where p is a nonzero
vector in Rn, called the normal to the hyperplane, and α is a scalar.
Definition 1.3 (Half-Space) : S = [x : Ptx ≥ α], where p is a non zero
vector in Rn and α is a scalar.
Definition 1.4 (Open Half-Space) S = [x : ptx < α], where p is a
nonzero vector in Rn and α is a scalar
Definition 1.5 (Polyhedral Set) S = [x : Ax ≤ b], where A is an m × n matrix and b is a m-vector.
Definition 1.6 (Polyhedral Cone) : S = [x : Ax ≤ 0], where A is a m × n matrix
Definition 1.7 (Cone)
Definition 1.8 (Convex Functions) Let S be a nonempty convex set in Rn. The function f : S → Rn is said to be convex on S if :
f (λx1+ (1 − λ)x2) ≤ λf (x1) + (1 − λ)f (x2), ∀x1, x2 ∈ S, ∀λ ∈ [0, 1]
Definition 1.9 (Tangent Cone) The tangent cone of K at a vector x ∈ K, consists of all vectors d ∈ Rn, called tangent vectors to K at x, for which there
exists a sequence of vectors yv ⊂ K and a sequence of positive scalars τv such
that lim v→∞y v = x lim lim v→∞τ v = 0 lim lim v→∞ yv−x τv = d
Definition 1.10 (Normal Cone) The normal cone, denoted as N (x; K), given a set K of x ∈ K, is the collection of all vectors d ∈ Rn which forms
an obtuse angle at x ∈ K, or equivalently
N (x; K) = {d ∈ Rn d(y − x) ≤ 0 ∀y ∈ K}
Proposition 1.11 Let K be a convex subset of Rn, and let x ∈ K be
arbi-trary. Then
T (x; K) = −N (x; K)
Definition 1.12 (Linearization cone) Consider a set K = [x ∈ Rn : h(x) = 0 g(x) ≤ 0], with h : Rn → Rl and g : Rn → Rm being contin-uously differentiable vector maps.
The linearization cone is denoted as L(x; K) and it is defined as follows L(x; K) = [v ∈ Rn : vT∇hj(x) = 0, ∀j = 1, ..l vT∇gi(x) ≤ 0, ∀i ∈ I(x)]
with
I(x) = [i : gi(x) = 0]
Definition 1.13 (Abadie constraint qualification) Consider a set K = [x ∈ Rn : h(x) = 0 g(x) ≤ 0], with h : Rn → Rl and g : Rn → Rm being
continuously differentiable vector maps. The Abadie constraint qualification (Abadie CQ) is satisfied if the linearization cone is equal to the tangent cone, that is T (x; K) ⊂ L(x; K)
Provided that the Tangent cone is always contained in the Linearization one, if the Abadie’s CQ are satisfied, it is T (x; K) = L(x; K). Furthermore, if T (x; K) is a polyhedral set, then T (x; K) = L(x; K).
It can be shown that a vector x ∈ K is a local minimizer of a given map θ(x), if and only if
(y − x)tθ(x) ≥ 0 ∀y ∈ T (x; K)
Given the joint conditions that the Tangent Cone is a polyhedral set, and the Abadie CQ holding on K, a vector y ∈ L(x; K) solves the minimization problem.
Definition 1.14 (Pseudoconvex Function) Let f : X → R be such that Dom f is an open convex set, let f be differentiable on Dom f . The function f is called pseudoconvex if ∀x, y ∈ dom f , it holds :
h∇f (x), y − xi ≥ 0 → f (y) ≥ f (x)
Definition 1.15 (Quasi-Convexity) Let S denote a nonempty convex set in Rn. Define a function as f : S → R, it is said that f is quasi-convex on S if for all pairs (x1, x2) ∈ S it holds :
f (λx1 + (1 − λ)x2) ≤ max{f (x1), f (x2)} ∀λ ∈ [0, 1]
1.2
3 Types of Monotonicity
Here we present basic definitions of monotonicity used throughout the thesis. Definition 1.16 (Monotonicity) F (x) is monotone on K if
[F (x1) − F (x2)]T(x1− x2) ≥ 0, ∀x1, x2
∈ K Definition 1.17 (Strict Monotonicity)
[F (x1) − F (x2)]T(x1 − x2) > 0, ∀x1, x2
∈ K, x1 6= x2
Definition 1.18 (Strong Monotonicity)
[F (x1) − F (x2)]T(x1− x2) ≥ α||x1− x2||2, ∀x1, x2 ∈ K With α being a positive constant defined on R++.
Local monotonicity requires the concept of neighborhood, consider a ball B(¯x) in Rn centered in ¯x, then we proceed to state :
Definition 1.19 (Local Monotonicity) F (x) is monotone on K if [F (x1) − F (x2)]T(x1− x2) ≥ 0, ∀x1, x2
∈ K ∩ B(¯x)
Definition 1.20 (Local Strict Monotonicity) F (x) is locally monotone at ¯x if
[F (x1) − F (x2)]T(x1− x2) ≥ 0, ∀x1, x2
∈ K ∩ B(¯x), x1 6= x2
Definition 1.21 (Local Strong Monotonicity) F (x) is locally strongly monotone at ¯x if for some α > 0
[F (x1) − F (x2)]T(x1− x2) ≥ α||x1− x2||2 ∀x1, x2
∈ K ∩ B(¯x)
1.3
Lipschitz Functions
Lipschitz continuity is particularly relevant in a Variational Inequality Frame-work, since it’s a necessary condition to ensure the convergence of the Mod-ified Projection Method.
Definition 1.22 (Lipschitzian Mapping) Let p ∈ R, let C ⊂ Lp be a
nonempty subset.
A mapping T : C → Lp is called p-Lipschitzian mapping if there exists a
constant L ≥ 0, such that
p(T (f ) − T (g)) ≤ Lp(f − g), ∀f, g ∈ C
Moreover, if L ≤ 1, p is called a non-expansive mapping, while if L < 1 is called a contraction mapping.
Definition 1.23 F (x) is Lipschitz continuous on K if there exists a constant L > 0, such that
||F (x1) − F (x2)|| ≤ L||x1− x2||, ∀x1, x2
1.4
Optimality Conditions
Proposition 1.24 Consider the following minimization problem, with func-tions f, gi, hi : Rn→ R and let X be a nonempty open set in Rn.
minimize x f(x) subject to gi(x) ≤ 0 ∀i ∈ {1, ., m} hi(x) = 0 ∀i ∈ {1, ., p} x ∈ X, (1.1)
If the Abadie’s CQ are verified, and x∗ is a solution of Problem {1.1}, then there exist vectors µ ∈ Rm, λ ∈ Rm such that
0 = f (x) + m X i=1 µi∇hi+ p X i=1 λi∇gi(x) 0 = h(x) 0 ≤ λ ⊥ g(x) ≤ 0
Corollary 1.25 The condition uigi(x∗) = 0 is called the complementarity
slackness condition, and stipulates that either ui = 0 or gi(x∗) = 0
Proposition 1.26 if x∗ is a local optimal solution, under a suitable con-straint qualification, there exists a vector (u, v) such that :
∇f (x∗) + m X i=1 ui∇gi(x∗) + l X i=1 vi∇hi(x∗) = 0 uigi(x∗) = 0, ∀i ∈ {1, ., m} ui ≤ 0, ∀i ∈ {1, ., f }
1.5
Graph Theory
The following results and methodologies are based on the work of Wataru [39], we start by enlisting the relevant definitions, i.e. nodes, edges, degree distributions, motif , random graphs and clustering.
K¨onigsberg presented in 1736, it provide means to describe spatial relation-ships, and it is used within economics to describe a wide range of phenomena. A weighted graph consists of a triple
G = (N, L, W )
with N denoting the number of nodes (sometimes being called vertexes within the literature), and L the number of links, that is, connections within differ-ent nodes.
W Denotes the set of all graph weights, in our successive models, the weights will be variational inequalities, and the weighted graph will become a gradient network.
Another common element within the theory is the Adjacency matrix A, that is, a symmetric matrix whose number of rows and columns is precisely equal to the collection of all nodes N .
The elements of the Adjacency matrix are denoted as aij , they are equal to
1 whether a link exists within node i and j, and 0 otherwise.
Example 1.27 An example of Adjacency Matrix with all nodes being con-nected, a triangle. A = 0 1 1 1 0 1 1 1 0
The number of incident links, with loops being counted twice, is defined as the Valency (or sometimes called degree) of a node x within a graph, or equivalently, V al(G, x).
In an undirected graph, the valency of a node can be calculated by summing up the elements of it’s respective row within the Adjacency matrix.
We provide a couple of results related to the valency, the former states that the sum of the valencies of all nodes is twice the number of all existing links, while the second provides an additional rule to identify nodes with odd valency.
a) X
x∈N (G)
b) In any graph, the number of nodes of odd valency is even.
Example 1.28 As a simple example, consider the graph G2 denoted by the
following Adjacency Matrix
Aexample = 0 1 1 1 0 0 1 0 0
The graph has three nodes and 2 links, hence point a holds X
x∈N (G2)
V al(x, G2) = 4 = 2L
Consider now the number of nodes with odd valency, only 1 node has 2 links, while the remaining 2 only 1, hence also point b applies.
Definition 1.29 (Subgraphs) A graph H is a subgraph of a graph G if N (H) ⊆ N (G), and L(H) ⊆ L(G) if it holds without equality, we say that H is a proper subgraph of G
Two results follows as immediate consequences. a) Any subgraph of a sub-graph of G is a subsub-graph of G. b) Suppose that N ⊆ N (G) and L ⊆ L(G), then in order for a subgraph H of G exists, such that L(H) = L, and N (H) = N , it’s necessary and sufficient that N includes the two ends in G of each member of N
Definition 1.30 (Nodes of attachment) denote π and Π as the null set and the null graph respectively.
We also denote as |S| the number of members of a finite set S. Let H be a subgraph of a graph G.
A node of attachment of H in G is a node of H that is incident in G with a node not belonging to N (H).
We denote the set of nodes of attachment of H in G by W (G, H)
From the definition, we can draw 2 additional conclusions : a) W (G, G) = W (G, Π) = π
b) W (G, H) ⊆ N (H)
Point a states that the number of nodes of attachment within the same graph is always null, due to the fact that all nodes belong to the same graph. The second point states that the number of nodes of attachment can’t be greater then the total amount of nodes belonging to the subgraph.
Theorem 1.31 (The complement of a subgraph) Consider any subgraph H of a graph G. There exists a subgraph Z of G whose nodes are the mem-bers of N (G) − N (H), and whose links are the memmem-bers of L(G) − L(H), together with the nodes of attachment of H in G. We call Z the complement of H in G.
1.6
Paths and Subgraphs properties
Definition 1.32 (Paths and Walks) A path in a graph G is a finite se-quence
P = (a0, A1, a1, A2..AN −1, aN)
whose terms are respectively, a succession of nodes and links For i ∈ {1, n}, ai−1 and ai are the two ends of Ai, with no node being repeated twice. A
walk, denoted as W , follows the same definition, but nodes can be repeated. Lemma 1.33 A Path is always a Walk
Example 1.34 An example of walk which is also a path is given by W = (a0, A1, a1, A2, a3)
An example of walk which is not a path is given by P = (a0, A1, a1, A2, a3, A3, a0)
Definition 1.35 (Detachment module) Given a Graph G, and a pair of subgraphs {A, B}, such that for all the elements of the nodes and links of the graph it holds
[N (A), N (B)] ⊆ N (G) and [L(A), L(B)] ⊆ L(G)
Definition 1.36 (Connection module) We say that G is a connected modulo J , or J connected, if it has no J -detached subgraph other then G itself, and the subgraphs of J . Equivalently, we say that a subgraph H of G is J connected if it is connected modulo it’s subgraph H ∩ J
Definition 1.37 (Isthmuses) Let A be a link of a graph G. We denote by G0A the graph obtained from G by deleting the link A. G0A is the spanning subgraph G : (N (G) − A) of G Saying that an Isthmus A does exists for a graph G, is equivalent to state that I(G, A) = 1, conversely, if it does not, I(G, A) = 0.
Then two relationships descends directly from the definition : N (G0A) = N (G)
Chapter 2
Variational Inequality Theory
2.1
Why Variational Inequality Theory
When we refer to the Variational Inequality Theory (VI from now on), we are addressing the scalar solution to a gradient problem, we are thus look-ing for the particular vector that render our own functions orthogonal to an identified set.
It’s intuitive to understand that to find the VI solution implies to solve sev-eral problems altogether.
At the same time, it’s obvious that assessing why and how VI are to be em-ployed is an issue bigger then designing a correct set of functions.
In our economic narration, VI are useful weights of a network, it’s worth to stress again that VI networks present an intersection with graph theory, and that building a VI network is equivalent to design a typical undirected weighted network, in this sense, the economic applications are humongous. Another point regards the role of rationality within our economic environ-ment, it’s worth to stress that quasi-rational models are still readily appli-cable within a VI framework, the truth of the statement may eventually be proved by means of the CP problem presented in the next pages : optimizing behavior can still imply inefficiency and also partial rationality.
2.2
Problem Definition
Definition 2.1 The V I(F, K) problem, where K ⊂ Rn denotes a closed convex set of Rn, and F denotes a given continuous function such that
F : K → Rn, is to determine a vector x∗
∈ K ⊂ Rn such that
F (x∗)T(x − x∗) ≥ 0, ∀x ∈ K Or equivalently
hF (x)∗, x − x∗i ≥ 0
This formulation states that F (X∗)T ⊥ K at the point x∗ ∈ K , i.e. the function F is “orthogonal” to K.
The set of all the solutions of V I(F, K) is defined as
Sol(K, F ) = [x∗ ∈ K : F (x∗)(x − x∗) ≥ 0, ∀x ∈ K]
and Sol(K, F ) ⊂ K , and since K is closed ,it follows that Sol(K, F ) is closed as well.
A geometric interpretation can be given as it follows : a point x∗ is a solution to the V I(F, K) problem if and only if F (x) forms a non-obtuse angle with every vector (y − x)∀y ∈ K. Therefore, we can define the normal cone to K at x0 to be the set
N (x0; K) = {d ∈ Rn: dT(y − x0) ≤ 0, ∀y ∈ K}
Therefore we can state that a vector x ∈ K solves the V I(F, K) if and only if −F (x) is a normal vector to K at x; or equivalently
0 ∈ F (x) + N (x; K)
The vectors in the set are defined as normal vectors to the set K at x0. It will be shown, later in the exposition, that a vector x belongs to the set Sol(F, K) if and only if x is a zero to the mapping F , or, equivalently, F−1(0)∩ K ⊂ Sol(F, K). The argument implies, more generally, that the function F (x) verifies with equality whenever the solution of V I(F, K) belongs to the topological interior of K.
Proposition 2.2 Let K = Rn , and let F : Rn → Rn be a given function. A
Proof if F (x∗) = 0 ,then inequality holds with equality, conversely, if x∗ is a solution, let x = x∗− F (x∗), which implies. once substituted in the VI
problem, that
F (x∗)(−F (x∗)) ≥ 0, thus F (x∗) = 0
2.3
Existence and Uniqueness Results
This subsection recollects the conditions for both the existence of a solution and it’s own uniqueness.
Theorem 2.3 if K is a compact convex set and F (x) is continuous on K, then the variational inequality problem admits at least one solution x∗. Proof According to Brouwer’s Fixed Point Theorem, given a map P : K → K, with P continuous, there is at least one x∗ ∈ K, such that x∗ = Pk(x∗− γF (x∗)), the result follows from {3.17}
In case of an unbounded feasible set K, Brouwer’s Fixed Point Theorem is no longer applicable; the existence of a solution to a variational inequality problem can be established under further conditions.
Let BR(0) denote a closed ball with radius R centered at 0, let KR =
K ∩ BR(0). Then KR is bounded. Let V I(F, KR) be the corresponding
variational inequality problem.
A particular results can guarantee the existence of a solution also if the set K is unbounded.
Theorem 2.4 V I(F, K) admits a solution if and only if there exists an R > 0 and a subset KR, with solution of V I(F, KR), denoted by XR∗ such that
||XR∗|| < R.
Proof Suppose that V I(F, K) has a solution x∗ and ||x∗|| < R. Since KR⊂ K
F (x∗)T(y − x∗) ≥ 0 ∀y ∈ K → F (x∗)T(y − x∗) ≥ 0 ∀y ∈ KR
Conversely, if ||XR|| < R for large enough R holds, then for any y ∈ K,
F (x∗R)T(w − x∗ R) ≥ 0 and F (x ∗ R)T(y − x ∗ R) ≥ 0, ∀y ∈ K
Corollary 2.5 If F (x) satisfies the coercivity condition : (F (x) − F (x0))T(x − x0)
||x − x0||
→ ∞ as ||x|| → ∞ for some x ∈ K, and for some x0 ∈ K.
Then V I(F, K) always has a solution.
Theorem 2.6 Let F (x) be a strictly monotone function on K. Then the solution is unique, if one exists.
Proof Suppose that x1 and x∗ are both solutions such that x1 differs
from x∗. Since they are both solutions, they must satisfy : F (x1)T(x0− x1) ≥ 0, ∀x0
∈ K F (x∗)T(x0− x∗) ≥ 0, ∀x0 ∈ K
Respectively, substitute x0 = x∗ in the former and x0 = x1 in the latter, summing up the inequalities yields :
[F (x1) − F (x∗)T](x∗− x1) ≥ 0
which contradicts the initial assumption of strict monotonicity, hence x1 = x∗
This theorem links itself with the next one, monotonicity and positive defi-niteness are related as it follows
Theorem 2.7 Assume that F (x) is continuously differentiable on K, and that the Jacobian Matrix
∇F (x) = ∂F1 ∂x1 . . . ∂Fn ∂xn .. . . .. ... ∂Fn ∂x1 . . . ∂Fn ∂xn
is symmetric and positive semidefinite (positive definite), then F (x) is mono-tone (strictly monomono-tone).
Proof The proof requires the Mean Value Theorem. For all x1, x2 ∈ K,
let
φ(t) = F (x2+ t(x1 − x2))T(x1− x2); 0 ≤ t ≤ 1
Then φ(t) is continuously differentiable on [0, 1], and
φ(1) − φ(0) = F (x1)T(x1− x2) − F (x2)T(x1− x2) = (F (x1) − F (x2))T(x1− x2)
By the Mean value theorem there exists some θ ∈ [0, 1] such that :
φ(1)−φ(0) = φ0(θ)(1−0) = (x1−x2)T∇F (x2+θ(x1−x2))(x1−x2) = (x1−x2)T∇F (x)(x1−x2)
where x = x2 + θ(x1 − x2) ∈ K. Letting v = x1 − x2, since ∇F (X) is
positive definite, the expression must be ≥ 0 . Hence : (F (x1) − F (x2))T(x1− x2) ≥ 0
That is, F(x) is monotone.
Theorem 2.8 Assume that F (x) is strongly monotone. Then there exists precisely one solution x∗ to V I(F, K).
Proof Existence follows from the fact that strong monotonicity implies coercivity, uniqueness instead descends from the fact that strong monotonic-ity implies strict monotonicmonotonic-ity.
2.4
Partitionability of VI
Definition 2.9 Let F : K ⊂ Rn → Rn be continuous, where K is a convex
set. The function F is said to be partitionable of order m over K if [F (x) − F (y)]T(x − y) =
m
X
i=1
[fi(xi) − fi(yi)]T(xi− yi)
For some continuous functions
, with convex domains Ki ∈ Rni; m
X
i=1
ni = n, each and everyone containing
an open neighborhood of Rni, such that
m
Y
i=1
Ki = K ⊂ Rni
, and for any xi, yi; i = 1, . . . m x =
x1 .. . xm and y = y1 .. . ym . fi are called partitions of F . The partitions of a partitionable functions are not, in gen-eral, unique. Also, separable functions defined over Cartesian products are a subclass of a class of partitionable variational inequalities.
In the case that the feasible set K is a Cartesian product of sets, it may be expressed as K = m Y i=1 Ki Theorem 2.10 A function F = F1 .. . Fm , F : m Y i=1 Ki → R Pni i=1 is partitionable
of order m if and only if there exist constant matrices Mij; j = (i + 1 . . . , m)
; i = 1, . . . m − 1, of dimension ni× nj such that
Fi(x) = fi(xi) + X j>i Mijxj − X j<i MijTxj, i ∈ (1 . . . m).
More precisely, fi(xi), ∀i are the principal partitions of F .
Theorem 2.11 Let F : K ∈ Rni → Rni be partitionable with partitions
fi : Ki ∈ Rni → Rni; i = 1, . . . , m. The function F is monotone if and only
if all the fi are monotone.
Proof Assume that F is monotone. Let x1 and y1 be arbitrary elements
of K1, and let xi be the corresponding elements of Ki, to establish that f1 is
the column vector with components {x1, . . . xm}, and y denote the column
vector with components {y1, x2, xm}. Then observe that
[f1(x1) − f1(y1)]T(x1− y1) = [f1(x1) − f1(y1)](x1 − y1) + m X i=2 [fi(xi) − fi(xi)] T (xi− xi) = [F (x) − F (y)]T(x − y) ≥ 0
Hence f1 is monotone, the same reasoning can be repeatedly applied to the
generality of all i, it follows that fi ∀i is monotone.
Conversely, assume that the fi, i ∈ {1, . . . , m} are monotone, and choose an
x and y ∈ K, the components x and y are equivalent, respectively, to x1 .. . xm and y1 .. . ym
, with xi, yi ∈ Ki respectively. To show that F is monotone, notice [F (x) − F (y)]T(x − y) = m X i=1 [fi(xi) − fi(xi)]T(xi− yi) ≥ m X i=1 0 = 0
and therefore F is monotone.
Theorem 2.12 Let F : K ∈ Rn → Rn be partitionable with partitions f i :
Ki ∈ Rni → Rni; i = 1, . . . m. The function F is strictly or strongly monotone
if and only if all of the fi are strictly or strongly monotone
Proof by analogous argument, as above.
Theorem 2.13 Let F : K ∈ Rn → Rn be partitionable with partitions f i :
Ki ∈ Rni → Rni; i = 1, . . . m. The function F is coercive if and only if all of
the fi are coercive.
2.5
Stability and Non Parametric Sensitivity
Analysis
If the problem is subjected to perturbations, the stability and sensitivity analysis allows to compute changes in the equilibrium patterns, sensitivity analysis is approached both from a global perspective and as a local (para-metric) point of view.
Results are now presented first by giving relevance to the general V I(F, K) problem, and then moving forward to the partitionable V I(F, K). The only assumption is the existence of a solution, given a perturbation F∗, of V I(F∗, K). The first result holds whether the non perturbated function F is strongly monotone, it states that the relative variation in the solution, given a perturbation, cannot be less then the positive constant by which strong monotonicity is defined.
Theorem 2.14 Let α be a positive constant in the definition of Strong Mono-tonicity, then
||x∗− x|| ≤ 1 α||F
∗
(x∗) − F (x∗)||
We can write down the result in a more explicit form to clarify the mean-ing.
||F∗(x∗) − F (x∗)||
||x∗− x|| ≥ α
Theorem 2.15 Let F : K ⊂ Rn → Rn be any continuous strictly monotone
function over the convex set K. Let F∗ : K ⊂ Rn → Rn be any other
continuous function over K. Let x and x∗ denote the solutions to V I(F, K) and V I(F∗, K) respectively.
If x 6= x∗, then
[F∗(x∗) − F (x∗)]T(x∗ − x) < 0.
Let F be a partitionable function, then the perturbed function is defined below Definition 2.16 Fi∗(xi) = fi∗(xi) + X j>i Mij(xj) − X j<i MijTxj, i = 1, . . . m
Theorem 2.17 Let F : K ∈ Rn → Rn be partitionable of order m, with
strictly monotone principal functions fi(xi), and define the matrices Mij as
previously. Consider a perturbation fi∗(xi) of the partitions fi(xi) and define
F∗(x). Let x denote the solution of V I(F, K), and x∗ as the solution to V I(F, K), where x 6= x∗. Then
m X i=1 [fi(x∗i) − fi(x∗i)]T(x ∗ i − xi) < 0
Proof First observe that for any x = x1 .. . xm and y = y1 .. . ym in the feasible set K, the following equality holds true
[F∗(x) − F (x)]T(x − y) =
m
X
i=1
[fi∗(xi) − fi(yi)]T(xi− yi)
, from which it descends also that [F∗(x∗) − F (x∗)]T(x∗− x) =
m
X
i=1
[fi∗(x∗) − fi(x∗)](x∗i − xi)
Strict monotonicity of the partitions fi implies the strict monotonicity of
F (x), from {2.15}
[F∗(x∗) − F∗(x)](x∗− x) < 0 Consequently, by partitionability, is implied
m
X
i=1
[fi∗(x∗) − fi(x∗)](x∗i − xi) < 0
The theorem allows to isolate the effect of the perturbation of a single vector over the solution of the V I problem, with respect of this point, if we consider sequences in Rn, the perturbation can be written as it follows
[F∗(x∗m) − F∗(x∗m)](x∗m− xm) < 0
From the fact that both f∗ and f are evaluated at the same point x∗m, knowl-edge of the perturbation allows to identify the solution variation, this de-scends directly from the fact that at least f is monotone.
Theorem 2.18 Let F : K ⊂ Rn → Rn be partitionable of order m, with
strictly monotone principal partitions fi(xi). Define the matrices Mij as
before. Let x denote the solution to V I(F, K) and x∗ as the solution of V I(F∗, K, with x 6= x∗, it follows that :
m
X
i=1
[fi∗(x∗i) − fi(xi)](x∗i − xi) ≤ 0
Proof Note that for any two elements x = x1 .. . xm and y = y1 .. . ym in K, it follows [F∗(y) − F (x)]T(y − x) = m X i=1 [fi∗(yi) − fi∗(xi)](yi− xi)
Letting y = x∗, one obtains
[F∗(x∗) − F (x)]T(x∗− x) =
m
X
i=1
[fi∗(x∗i) − fi∗(xi)](x∗i − xi)
From theorem {2.17} it holds :
m
X
i=1
[fi∗(x∗i) − fi(xi)](x∗i − xi) < 0
2.6
Parametric Sensitivity Analysis
Definition 2.19 The parametric variational inequality problem is defined as it follows : determine x∗ ∈ Kλ, such that :
F (x∗, λ)T(x − x∗) ≥ 0, ∀x ∈ Kλ (1.57)
Where F (x, λ) is a given function defined on the set (x, λ), with λ ∈ Λ, x ∈ Kλ, and taking values in Rn, Λ is an open subset of Rk, and [Kλ , λ ∈ Λ] is
a family of closed convex subsets of Rn.
Assuming that it exists a solution ¯x∗ for some ¯λ ∈ Λ, it is possible to de-termine conditions under which, for each λ in a neighborhood of ¯λ, there’s a unique x∗(λ) near ¯x∗, and the function x∗(λ) is continuous, Lipschitz con-tinuous, or differentiable. Assume that the function F (x, λ) is defined on B( ¯x∗) ∩ Λ, where B( ¯x∗) is the closure of a ball in Rn centered at ¯x∗, if
F (x, λ) satisfies the following condition of local strong monotonicity Condition 2.20
[F (x1, λ) − F (x2, λ)]T(x1− x2) ≥ α||x1 − x2||2 ∀λ ∈ Λ ∀x1, x2 ∈ B(¯x∗)
Definition 2.21 (Local Lipschitz continuity condition)
||F (x1, λ) − F (x2, λ)|| ≤ L||x1− x2||, ∀λ ∈ Λ, ∀x1, x2 ∈ B( ¯x∗)
with α and L being positive constants.
Three lemmas follow up with respect of local subsets of K.
Lemma 2.22 Fix γ ∈ (0, α/L2], where α and L are given in (1.58) and
(1.59) respectively. Then there exists a scalar β such that ||G∗(x, λ) − G∗(y, λ)|| ≤ β||x − y|| (1.61) ∀x, y ∈ B( ¯(x∗)), λ ∈ Λ where
(1 − γα)12 ≤ β < 1
.
Proof : Since both Kλand B( ¯x∗) are closed and convex, also Kλ∩B(¯(x∗))
must be, implying that
G∗(x, λ) = PKλ[x − γF (x, λ)] is non expansive, or, equivalently
||G∗(x, λ) − G∗(y, λ)||2(x − y) − ||γ(F (x, λ) − F (y, λ))||2 = ||x − y||2− 2γ(x − y)T[F (x, λ) − F (y, λ)] + γ2||F (x, λ) − F (y, λ)||2
≤ (1 − 2γα + γ2L2)||x − y||2 ≤ (1 − γα)||x − y||2 , which implies the previous statement.
Lemma 2.23 For every λ ∈ Λ the map G∗(x, λ) defined by (1.60) has a unique fixed point x∗(λ).
Lemma 2.24 Let ¯x∗ be the solution of , for ¯λ ∈ Λ. Assume that F (¯x∗, λ) is continuous in λ at ¯λ and that for any given ¯y ∈ B( ¯x∗) the map
λ → PKλ∩B( ¯x∗)(¯y)
is continuous (or Lipschitz continuous) in λ at ¯λ. Then x∗(λ) is continuous (or Lipschitz continuous) in λ at ¯λ
Proof Fix λ ∈ Λ. Using triangle inequality and (1.61) one has that ||x∗(λ) − x∗(¯λ)|| = ||G∗(x∗(λ), λ)) − G∗(x∗(¯(λ)¯λ)|| ≤ ||G∗(x∗(λ), λ) − G∗(x∗( ¯(λ)), λ)|| +||G∗(x∗( ¯(λ))λ) − G∗(x∗(¯λ), ¯λ)|| ≤ β||x∗(λ) − x∗(¯λ)|| + ||G∗(x∗)(¯λ, λ) − G∗(x∗(¯λ), ¯λ)|| (1.63)
Applying (1.60) and corollary 1.1, one obtains : ||G∗(x∗(¯λ), λ) − G∗(x∗(¯λ), ¯λ)|| = PKλ∩ B( ¯x∗)[x∗ (¯λ) − γF (x∗(¯λ, ¯λ)) = PKλ∩B( ¯x∗)[x∗(¯λ) − γF (x∗(¯λ), λ)] − P Kλ∩B(x∗)[x ∗ (¯λ) − γF (x∗(¯λ), ¯λ)]|| +||PKλ∩B( ¯x∗)[x∗(¯λ) − γF (x∗(¯λ), ¯λ)]|| ≤ γ||F (x∗(¯λ), λ) − F (x∗(¯λ), ¯λ)|| + ||PKλ∩B(x∗)[x∗(¯λ) − γF (x∗(¯λ), ¯λ)] −||PK¯λ∩B(x∗)[x ∗ (¯λ) − γF (x∗(¯λ), ¯λ)]|| (1.64)
Combining (1.63) and (1.64), and using the relationship x∗(¯λ) = ¯x∗ one
obtains : ||x∗(λ) − ¯x∗|| ≤ γ 1 − β||F ( ¯x ∗, λ − F ( ¯x∗ , ¯λ)|| + 1 1 − β||PKλ∩B( ¯¯ x∗)[ ¯x ∗− γF ( ¯x∗, ¯λ)] − P K¯λ∩B( ¯x∗)[ ¯x ∗− γF ( ¯x∗ , ¯λ)]||
from which the conclusion follows, provided that γ is small enough so that ¯
Chapter 3
Problem classes
In this chapter, we present several classes of subproblems apt to be formulated in VI terms.
3.1
Optimization Problems
We present the main relationship between VI and Optimization Problems, the relationship with KKT system and Convex Programming.
With regard to our intentions, VI theory intertwines mathematical network theory and economic rational approaches, thus providing the modeling input necessary to explain the rational components of competition and, nonethe-less, possibilities of optima and market efficiency.
Proposition 3.1 Let x∗ be a solution to the optimization problem Min
x f (x)
s.t. x ∈ K
Where f is a continuously differentiable function and K is a closed and convex set. Then x∗ is a solution of the variational inequality problem :
∇f (x∗)T(x − x∗) ≥ 0 ∀x ∈ K
Proof let θ(t) = f (x∗ + t(x − x∗)), for t ∈ [0, 1], since θ(t) achieves it’s minimum at t = 0, 0 ≤ θ0(0) = ∇f (x∗)T(x − x∗), that is, x∗ is a solution of
Here we propose the reversed argument instead.
Proposition 3.2 If f (x) is a convex function, and x∗is a solution to V I(∇f, K), then x∗ solves the optimization problem.
Proof since f (x) is convex, f (x) ≥ f (x∗) + ∇f (x∗)T(x − x∗
), ∀x ∈ K but ∇f (x∗)(x − x∗) = 0, since x∗ is a solution to V I(∇f, K). Therefore, one concludes that f (x) ≥ f (x∗) ∀x ∈ K that is, x∗ is a minimum point of the mathematical programming problem.
Definition 3.3 An n×x matrix M (x), whose elements mij; i ∈ {1, ..., n}, j ∈
{1, ..., n} are functions defined on the set S ⊂ Rn , is said to be positive
semidefinite on S if
vTM v ≥ 0 ∀x ∈ Rn x ∈ S
It is said to be positive definite on S if
vTM (x)v > 0 ∀v 6= 0 v ∈ Rn x ∈ S
It is said to be strongly positive definite on S if vtM (x)v ≥ a|x||
Note that γ(x) is the smallest eigenvalue, which is necessarily real, of the symmetric part of M (x), that is, 12[M (x) + M (x)T] , then it follows that : M (x) is positive semidefinite on S if and only if γ(x) ≥ 0, ∀x ∈ S;
M (x) is positive definite on S if and only if γ(x) > 0, ∀x ∈ S
M (x) is strongly positive definite on S if and only if γ(x) ≥ α > 0, ∀x ∈ S Theorem 3.4 Assume that F (x) is continuously differentiable on K, and that the Jacobian Matrix
∇F (x) = ∂F1 ∂x1 . . . ∂Fn ∂xn .. . . .. ... ∂Fn ∂x1 . . . ∂Fn ∂xn
is symmetric and positive semidefinite. Then there is a real valued convex function f : K → R1 satisfying
∇f (x) = F (x)
with x∗ being both the solution of V I(F, K) and the mathematical pro-gramming problem :
Min
x f (x)
s.t. x ∈ K
(3.1)
Now consider the same problem, with f being continuously differentiable over an open subset of K ⊆ Rn.
Min
x f (x)
s.t. x ∈ K
(3.2) Given the set convexity, any local minimizer x must satisfy
(y − x)T∇f (x) ≥ 0, ∀y ∈ K
Which in turn, is equivalent to V I(∇f (x), K), whose solution is the station-ary point problem associated with the optimization.
In particular, by denoting F (x) = ∇f (x), we are exactly specifying that F (x) is a gradient map, the gradient condition is equivalent to the integrability condition of F over the domain.
Proposition 3.5 Let x ∈ Sol(f, K). If Abadie CQ holds at x, then there exists µ ∈ Rl and λ ∈ Rm+ such that
F (x) + l X k=1 µj∇hj(x) + m X i=1 λi∇gi(x) = 0 h(x) = 0 λ ⊥ g(x) = 0 (3.3)
Proof Note immediately that if x ∈ Sol(F, K), then x solves the nonlinear programming problem
s.t. y ∈ K
Since {3.3} is the KKT system of the nonlinear program, the first point is proved.
Conversely, if hj is affine, and gi is convex, if (x∗, µ, λ) solves {3.3}, then
x∗ ∈ Sol(K, F )
The KKT system presented above, is denoted as the MiCP problem with a finitely defined set K.
Given a problem of the form V I(F, K), we can introduce the (vector) La-grangian Function, which is given by
L(x, µ, λ) = F (x) + m X i=1 µi∇hi+ p X i=1 λi∇gi(x) ∀(x, µ, λ) ∈ Rn+m+p
It is important to notice that for the VI problem, the Lagrangian is a vector function, while for a non linear programming, the Lagrangian is scalar valued. The triple (x, µ, λ) which solves the Lagrangian is called a KKT triple of V I(F ; K).
Remark 3.6 (Constraint Qualifications) Consider again the Proposition {3.5}, whether the Abadie’s CQ does not hold, the Proposition remains valid whether one of the following constraint qualifications holds.
1) Slater’s CQ
2) Linear Independence CQ 3) Cottle’s CQ
4) Zangwill’s CQ
5) Karash Kuhn Tucker’s CQ
A more in depth description of the constraints and their characteristics can be found in [3]
Finally, we propose the Minty Variational Inequality problem (MVI), which is a generalization of the classic VI problem elaborated in 1962 by Minty.
The problem can be formulated as follows :
Definition 3.7 (Minty Variational Inequality) Find ¯x ∈ K such that hF (y), y − ¯xi ≥ 0 ∀y ∈ K
, with K being a nonempty subset.
The main difference being that the value of ¯x solves F (y) for all y ∈ K, while the standard VI problem requires to find a specific vector such that F (¯x) = 0. Finally, finding the solution to MVI is a sufficient condition for optimization.
3.2
Complementarity Problem
When the set K is a cone, the VI problem admits a form known as Comple-mentarity Problem [16]. A more rigorous definition is given below.
Definition 3.8 Given a cone K, and a mapping F : K → Rn, the
comple-mentarity problem, denoted as CP (K, F ), is to find a vector x ∈ Rn such that
F (x) ∈ K∗ x ∈ K x ⊥ F (x)
where K∗ = {d ∈ Rn : vTd ≥ 0, ∀v ∈ K}, i.e. K∗ is the set of all vectors
which makes a non obtuse angle with every vector in K
If the mapping F is affine, that is, whenever F (x) = M x + b , and M is a n × n matrix and b an n × 1 vector, with F : Rn
+→ Rn, the formulation is
denoted as “linear complementarity problem”.
The Variational Inequality problem and the Complementarity Problem are related by the following proposition
Proposition 3.9 V I(F, Rn
+) and the Complementarity problem have
pre-cisely the same solutions, if any.
Proof It is established that if x∗ satisfies V I(F, Rn), then it also satisfies the complementarity problem defined above.
Substituting x = x∗+ ei into V I(F, Rn+), where ei denotes the n-dimensional
vector with 1 in the i-th row and 0 elsewhere, one concludes that Fi(x∗) ≥ 0,
and F (x∗) ≥ 0.
Substituting now x = 2x∗ into the variational inequality, one obtains : F (x∗)T(x∗) ≥ 0
Substituting then x = 0 into the variational inequality, one obtains F (x∗)(−x∗) ≥ 0
Taking the results together, it is implied that F (x∗)Tx∗ = 0 Conversely, if x∗
satisfies the complementarity problem, then F (x∗)T(x − x∗) ≥ 0 since x ∈ Rn+ and F (x∗) ≥ 0
We can further generalize the result by considering the Mixed Comple-mentarity Problem (MiCP), which is a generalization of the CP when K is a special cone Rn1 × Rn2, with n
1+ n2 = n. we proceed to define
Definition 3.10 Let G and H be two mappings from Rn1 × Rn2
+ into Rn1
and Rn2 respectively.
The MiCP (G, H) is to find a pair of vectors (u,v) belonging to Rn1 × Rn2
such that
G(u, v) = 0 u free 0 ≤ v ⊥ H(u, v) ≥ 0
The CP and MiCP are special cases where K is a cone, for instance, consider the affine function
F (x) = q + M x ∀x ∈ Rn +
for some vector q ∈ Rn+ and matrix M ∈ Rn×n, in this case, V I(K, q, M ) is
equivalent to V I(K, F ), additionally, if K is a polyhedral set, then we have the Affine Variational Inequality AV I(K, q, M )
If the function is non linear, but the set is Polyhedral, then we have the Linearly Constrained VI problem.
The importance of the AVI problem and the Linearly constrained VI prob-lem is linked again to the Abadie’s CQ conditions. In particular, whether the set K is polyhedral cone, which is the defining condition of both problems,
we have that the Tangent cone equals the Linearization Cone.
Consequently, the Abadie’s CQ are verified, and the AVI problem can be derived by a KKT formulation.
With regard of the MiCP issue, we recall the following proposition, linking the solution to the set K being a polyhedron.
Proposition 3.11 Let K be a polyhedron. A vector x solves the V I(K, F ) if and only if there exist vectors λ ∈ Rm and µ ∈ Rl such that
0 = F (x) + CTµ + ATλ 0 = d − Cx 0 ≤ λ ⊥ (b − Ax) ≥ 0
Consider now the postulate of Abadie’s constraint qualifications, stating that the tangent cone of K at x equals to the following linearization cone
L(x; K) = [v ∈ Rn: vT∇hj(x) = 0, ∀j = 1, .., l
vT∇gi(x) ≤ 0, ∀i ∈ I(x)]
with
I(x) = [i : gi(x) = 0]
the Linearization Cone is also equivalent to a polyhedral set , and the couple of vectors (λ, µ) by which the constraints qualifications are satisfied corresponds to the solutions of a M iCP (h, g).
More precisely, the KKT formulation obtained as F (x) + m X j=1 µj∇hj(x) + m X i=1 λi∇gi(x) 0 = h(x) 0 ≤ λ ⊥ g(x) ≤ 0
corresponds to a M iCP (g, h) conversion of a Linearly Constrained VI prob-lem, with a solution given by the vectors (x, µ, λ).
We conclude by pointing that the MiCP and the Linearly Constrained VI are equivalent formulations of the same problem.
To solve the MiCP implies to identify a couple of vectors (µ, λ) by which also the Linearly Constrained VI is solved.
3.3
Fixed Point Problems
Fixed point (FP) theory has a primary role within economic theory, it is used to compute and design solutions to market clearing problems in economics and finance, supply chain and logistics.
In this section we present the basic FP Theorem, the theoretical link between VI and FP, and other theoretical results.
Theorem 3.12 fixed point theorem
Let K be a nonempty compact convex set in Rn+, and f a continuous
mapping from K into itself.
Then f has a fixed point x∗, i.e. a point x∗ in K such that f (x∗) = x∗ The same result can be achieved within a VI framework, consider the following proposition.
Proposition 3.13 Let K be a nonempty subset of Rn, and G : K → K. If
the mapping F : K → K is defined by
F (x) = x − G(x)
then the VI formulation is equivalent to a Fixed Point Problem.
Proof
Let ¯x ∈ K be a fixed point of the problem, then F (¯x) = 0 and the problem solves the VI.
Conversely, suppose that ¯x solves F (¯x) = ¯x − G(¯x), then G(¯x) ∈ K , letting x = G(¯x) yields
−||¯x − G(¯x)||2 ≥ 0 , that is ¯x = G(¯x)
We now introduce the Projection Operator, which is relevant to link FP-theory and VI solutions.
Proposition 3.14 Let K be a closed convex set in Rn. Then for each x ∈
Rn, there is a unique point y ∈ K, such that ||x − y|| ≤ ||x − z||, ∀z ∈ K, and y is known as the orthogonal projection of x on the set K with respect to the Euclidean norm, that is
y = Pkx = argmin||x − z||; ∀z ∈ K
Proof Let x be a fixed point and let w ∈ K.
Minimizing ||x − z|| over all z ∈ K is equivalent to minimize the same func-tion over all z ∈ K such that ||x − z|| ≤ ||x − w|| , which is a compact set. The function g defined by g(z) = ||x − z||2 is continuous.
Existence of a minimizing y follows on the proposition that a continuous function on a compact set always attains its minimum. To prove that y is unique, observe that the square of the Euclidean norm is a strictly convex function. Hence, g is strictly convex and its minimum is unique.
Theorem 3.15 Let K be a closed convex set. Then y = Pkx if and only if
(y − x)T(z − y) ≥ 0 ∀z ∈ K .
Proof
Notice that y = Pkx is the minimizer of g(z) over all z ∈ K. Since
∇g(z) = 2(z − x) the result follows from the optimality conditions for con-strained optimization problems.
Corollary 3.16 Let K be a closed convex set. Then the projection operator Pk is non expansive, i.e.
||Pkx − Pkx0|| ≤ ||x − x0||, ∀x, x0 ∈ Rn
.
Theorem 3.17 Assume that K is closed and convex. Then x∗ ∈ K is a solution of the variational inequality problem V I(F, K) if and only if, for any γ > 0, x∗ is a fixed point of the map
implying :
x∗ = PK(x∗− γF (x∗))
Proof Suppose that x∗ is a solution of the variational inequality, i.e. F (x∗)T(x − x∗
) ≥ 0 ∀x ∈ K
Multiplying the above inequality by −γ, and adding x∗T(x − x∗) on both sides of the inequality yields :
x∗T(x − x∗) ≥ [x∗− γF (x∗)]T(x − x∗
) ∀x ∈ K From theorem {3.15} :
x∗ = PK(x∗− γF (x∗))
Conversely, if x∗ = PK(x∗− γF (x∗) holds and γ ≥ 0, then it follows
x∗T(x − x∗) ≥ (x∗− γF (x∗)(x − x∗) ∀x ∈ K implying
F (x∗)T(y − x) ≥ 0 ∀y ∈ K
The orthogonal projection of the vector (x∗ − γF (x∗)), namely x∗, due
to the fact that the square of the norm is strictly convex, admits only one solution, therefore x∗ is both a unique fixed point and the solution of the VI problem.
Chapter 4
Supply Chain Theory
4.1
An Introductory Model to Supply Chain
Networks
This section is introductory to the Network Literature, we consider the model of Nagurney, Dong and Zhang [28] Consider m different manufacturers, each producing an individual output flow, given by qi with i ∈ {1, n}, the
produc-tion is grouped within the vector Q1 ∈ Rm +.
Transactions are conducted with j different retailers, with j ∈ {1, m} Each Manufacturer is charged with a production cost, defined as
fi = fi(qi) ∀i
sells his products to n different retailers, and charges prices given by p1∗ ij with
j ∈ {1, m}. The total amount of transactions per manufacturer is given by
qi = m
X
j=1
qij
The market price is given by p∗ij. Let Q =
m
X
i=1
qi be the total production within the market.
Additionally, conducting transactions induces costs given by ci = ci(qij) ∀i ∈ {1, n} ∀j ∈ {1, m}
Each manufacturer faces a profit maximization problem given by max qij Πi(qi) = m X j=1 p∗ijqij − fi(Q1) − m X j=1 c(qij) s.t m X j=1 qij ≥ 0 And equivalently min qij −Πi(qi) = − m X j=1 p∗ijqij + fi(Q1) + m X j=1 c(qij) s.t − m X j=1 qij ≤ 0
Denote now as q∗i the solution to the maximization problem. Also, let gj(qi) ≥ 0 be an equivalent formulation of the constraint
m
X
j=1
qij ≥ 0,
the Lagrangian formulation is denoted as Li(qi, λ) = − m X j=1 p∗ijqij + fi(Q1) + m X j=1 c(qij) + m X j=1 λjqij
With the necessary conditions
gj(qij) ≥ 0 ∀j ∈ {1, m} (4.1)
and
λ∗jgj(qij∗) = 0 ∀j ∈ {1, m} (4.2)
and the stationarity condition
∇L(qi∗, λ∗j) = 0 (4.3) From the condition {4.2}, with qi∗ being strictly positive, we have that
L(q∗i, λ∗) = −Πi(q∗)
Consider now a restriction function Θ(t) with t ∈ [0, 1] such that, Θ(t) = −Πi(q∗+ t(q − q∗))
since q∗ is the minimum point of −Πi(q), it follows that Θ(t) achieves it’s
minimum at t = 0, taking the derivative of Θ(t) and letting t = 0 yields Θ0(0) = −Π0i(q∗)(q − q∗)
a variational formulation that we denote as V I(Π, Rm +) h(Π(qi), (qi− q∗i)i = m X j=1 [c0ij(q∗i) + fi0(Q1∗) − p∗ij](qij − q∗ij)
From the stationarity condition {4.3} it holds that
m X j=1 [∂cij(q ∗ i) ∂qij + fi(Q 1∗) qij − p∗ij](qij − q∗ij) = 0 ∀qij ∈ R+m
and holds with inequality whether we consider qi 6= qi∗ since q ∗
i is a minimum
point. The variational formulation holds for each manufacturer, consider the profit function
Πi(q) : R+ → Rm+
having n manufacturers, we can group all profit functions within a vector map
Π(Q1) : Rn→ Rm
The variational formulation of the whole market is given by
n X i=1 m X j=1 [c0ij(q∗i) + fi0(Q∗) − p∗ij](qij − qij∗) ≥ 0 ∀qij ∈ Rnm+
Which is true since qij∗ is the minimizing quantity for each manufacturer. Consider now the retailers, as stated previously, there are m retailers, they trade with o markets by charging a price p2∗jk , with j ∈ {1, m} and k ∈ {1, o}, each shipment is denoted as
qjk = o
X
k=1
qjk
each retailer sustains generic costs equal to cj = cj(Q1)
They are also charged by p1∗
ijqij for each unit they buy from manufacturers.
Also, retailer flows can’t be greater then the amount sold by the manufac-turers, implying n X i=1 qij ≥ o X k=1 qjk ∀j ∈ {1, m}
Denote now the retailer profit function as Π2(q
jk), and let Π2j = p2∗j o X k qjk− cj(Q1) − m X i=1 p1∗ijqij ∀j ∈ {1, m}
The retailer maximization problem can be written as min qij −Π2 j(qjk) = −p2∗j o X k=1 qjk + cj(Q1) + n X i=1 p1∗ijqij o X k=1 qjk − j X i=1 qij ≤ 0 (4.4)
The variational formulation is obtained in a procedure similar to the man-ufacturer’s case.
Consider the retailer profit function −Π2
j(qjk), and consider the relative
La-grangian L(qjk, qij, λ2j), we have L(qjk, qij, λ2) = −p2∗j o X k=1 qjk+ cj(Q1) + m X i=1 p∗ijqij+ λ2j[ o X k=1 qjk− m X i=1 qij] (4.5)
Consider now the KKT conditions for this problem, from the Lagrangian we obtain the following system
∂L(qjk, ...) ∂qjk = −p2∗j + λ2j = 0 ∀j ∈ {1, m} ∂L(qjk,...) ∂qij = p 1∗ ij + ∂cj(Q1) ∂qij − λ 2 j = 0 ∀i ∈ {1, n} ∂L(qjk,..) ∂λ2 j = l X i=1 qij − o X k=1 qjk ≥ 0 ∀j ∈ {1, m}
Related Slackness Condition λ2 j[ o X k=1 qjk− m X i=1 qij] = 0 ∀j ∈ {1, m} (4.6)
From the manufacturer’s problem we know that p1∗ ij+
∂cij
∂qij are strictly positive,
then, putting together the first and second equations, we know that p1∗j = λ2j
and both are strictly positive nonetheless. Therefore, the slackness condition holds when
m X i=1 qij = o X k=1 qjk
We know also that
qij∗ > 0 ∀i and j
hence, from the Slackness condition we know that qjk must be positive and
equal to qij . We can proceed to define a restriction function Θ(t) with
t ∈ [0, 1] such that
Θ0(t) = ∇L(qjk∗ + t(qjk − qjk∗ ), q ∗
ij + t(qij − q∗ij), λ
2∗+ t(λ2− λ2∗))
Taking the derivative with respect of t and setting t = 0 yields ∂Θ(t) ∂t t=0 = m X i=1 [p∗ij +∂cj(Q 1) qij − λ2][q ij − q∗ij] + o X k=1 [−p2∗j + λ2j][qjk− q∗jk] +[ n X i=1 qij − o X k=1 qjk][λ2j − λ2∗j ] ≥ 0 ∀j ∈ {1, ., m}
which holds true since the solution of the VI formulation is the minimiz-ing triple (qij∗.qjk∗ , λ2) Also, since q∗
ij minimizes for every j, it also holds at
aggregate level, therefore we can write the VI formulation as Dong’s
m X j=1 n X i=1 [p∗ij +∂cj(Q 1) qij − λ2 j][qij − qij∗] + m X j=1 o X k=1 [−p2∗j + λ2j][qjk − q∗jk] + [ n X i=1 m X j=1 qij − m X j=1 o X k=1 qjk][λ2j − λ 2∗ j ] ≥ 0
We can derive the basic market equilibrium conditions from the La-grangian derivatives, consider again the Slackness condition in {4.6}, we
know that λ2
j will be strictly positive whether p2∗j will be different from 0, so
that given an optimal amount produced by the manufacturers qij∗ for all i, also qjk will be positive for all j and k.
Consider the case in which p2∗
j is instead null, then λ2j is null as well, it does
not matter anymore whether the capacities produced by the manufacturers are positive, the Slackness condition can hold without qjk being optimal.
The equilibrium condition can therefore be written as follows
o X k=1 qjk − m X i=1 qij∗ = 0 if p 2∗ j > 0 ≤ 0 ifp2∗ j = 0
Next models will be structured around the same framework presented in this section.
4.2
The Literature on Supply Chain Networks
with disruption risks
In order to better explain the modern foundations of VI theory, we have to look back at 1959.
That was the year when the first mathematical variational problem, namely, the “Signorini’s problem was formulated, and four year later, solved by Fichera.
In 1980, however, it was published the first book on Variational Inequalities and related applications, by Stampacchia and Kinderlher [38], and in 1983, by Antman, it was shown that to solve a VI problem was mathematically equivalent to find the solution of an optimization problem [2].
One of the first social applications regarded the optimization of traffic flows in 1984, [10], with the same methodology being successfully imported in eco-nomics.
The work was a starter due to the fact that it provided the application of two modern algorithms, namely the Equilibration method, and the projec-tion method, by which the Euler method descends.
The most prominent applications to supply chain network were made by Nagurney’s et al [22], providing one of the first economic supply chain mod-els of optimization.
From that moment to nowadays, the supply chain theory, as presented by the author, exploded toward notoriousness.
In a strongly connected economy, where disruptions, mergers, acquisitions, and nonetheless industrial and international competition are typical, models that provide the theoretical framework by which these scenarios can be an-alyzed are of the utmost importance.
Supply chain network analysis, based on optimization, thus provides a neo-classical frameworks and, together, allows for innovative applications, as an example, the possibility of bicriteria methods, Qiang [41], and humanitarian aid frameworks, Nagurney [35]. The role of supply chain analysis does not rest only in the design of an elegant economic theory, by providing a reliable solution to the concerns of optimization, measures of network efficiency and algorithms for convergence to equilibria are of equal importance.
To name a few, the Balancing Algorithm, the Projection Method and the Euler Methods allows to find optimal points also in analytically intractable frameworks [27].
In our work, we will present not only models of general equilibria applied to disruption risks, but also present the conditions for convergence and evaluate the role of strategic behavior.
4.3
What is a supply chain network, the role
of disruption risks
In order to understand what is a Supply Chain network, we have to de-compose it to the theoretical components, namely, the supply chain and the comprehending network.
A supply chain is a sequence of suppliers, each and everyone placed within a particular stage of the production process, culminating into the trade with a multiplicity of demand markets.
Supply chains are an essential component of modern society, products are made due to the cooperation between different firms, in order to cut down costs and promoting specialization.
On the other side, we have to state what is a network, and why did we choose to represent supply chains by means of network models.
It’s worth to highlight that network models, portrayed at the basic compo-nents, are nothing but a collection of nodes, links and weights.
relation-ships of trade, in order to produce as efficiently as possible a given collection of goods.
Nodes can be virtually anything, provided that a mathematical relationship between the described objects exists.
Links are, generally speaking, relationships expressed in binary terms, to our task, trading is a perfect case.
In order to allow for maximization within networks, we have to refer to the third component of a network, namely, weights.
A weight, as the node and the link, can still be anything : In a supply chain network, the weights may be the vectors of marginal utilities, costs and prices by which the maximization process occurs.
Are there relevant properties?
In first place, supply chain networks, as originally portrayed by Nagurney [27], are always connected.
It’s always possible to “walk ” from a node to the extreme opposite one, a directional link always exists.
Is it possible to observe, in some particular cases, the disruption of a given sequence within a supply chain?
What are the possible disruptions that can occur?
We can distinguish two mathematically relevant “network disruption risks”, the first is quantifiable, the second only accountable, namely, link disruption and node disruption, in our work, we will consider only the former.
Node disruption regards a variation in the number of nodes considered within the network.
Link disruption identifies the change in relationships within the supply chain, it occurs for countless reasons, ranging from “non disruptive ones”, such as mergers and acquisitions, to the disruptive cases, such as market failures, ecological catastrophes, transport incidents and man made attacks.
In an economic sense, the disruption risk is a cost to be accounted, as [23] already presented.
To treat disruptions as stochastic costs works particularly well for the eco-nomic paradigm, it allows to take into account both the impact and the risk attitude of the affected firms [35].
Softer ways to disrupt a supply chain could be caused by the interruption of a trade contract, from the exploitation of new transportation routes, from the obsolescence of chain products.
In general however, disruptions management depend from factors such as the firm’s size and the supply chain resources.
All these “disruption ” possibilities lead to the same mathematical paradigm, namely, the evaluation of the loss of efficiency within a given link, where as inefficiency implies a loss of utility within the supply chain.
The loss is calculated by computing the difference between the utility (or profit, productivity etc.) for the network after and previous to the trade link removal.
Such a difference gives us the loss of network efficiency due to the disruption. In order to account for the loss in efficiency, general knowledge about the distribution of disruptions, and of the related density, are necessary.
It’s worth to stress that within an economic framework, aggregates and mar-ket components are subject to disruptions, we can at least count two major categories, namely, supply and demand disruptions [35]. The latter encom-passes all sorts of events capable to produce a variation in overall aggregate demand.
In cases of positive variations, the final consequence will be a cost related to the unsatisfied demand, while conversely we will have costs related to sur-pluses.
We can observe, in general, that costs are as higher as the frequency and intensity of the disruption can be, with the peak being reached in the case of the most unwelcome events, such as ecological disruptions : [23] , additional cost factors, related to the tardiness of the relief, to the distance between the helpers and the disruption location may be included as model components. In the next section, we present a basic supply chain model, after introducing the behavioral rules for manufacturers, retailers, and finally, the equilibrium conditions, we proceed to illustrate a theorem of general equilibrium, thus demonstrating that since the problem can be formulated by means of VI theory, then an optimal equilibrium exists under very broad mathematical properties.
4.4
A Supply Chain model with disruption
risks and random demand
The model consists of m manufacturers, a generic manufacturer is denoted by i, there are also n retailers, a generic one denoted as j, finally, we can count o final demand markets.
Since we are within a network contest, we can count i transportation links between manufacturers and retailers and l transportation links between re-tailers and the o demand markets.
For each link sequence ij, there are g transportation modes, the generic one being denoted by u.
Manufacturer’s behavior
All manufacturers are characterized by the same homogeneous product q, the product shipment between a generic manufacturer i and retailer j, given a transportation mode u, is denoted as qu
ij.
The collection of all production output and shipments, respectively falls un-der the vectors q and Q1. The cost of producing one unit of good is denoted
as fi(qi).
The total amount of product shipped from a manufacturer has to equal the total amount produced, so that for each manufacturer it must hold :
qi = n X j=1 g X u=1 qiju ∀i ∈ (1, .., m)
It is assumed that disruptions will affect the manufacturing process, the latter being influenced at cost function level.
It is introduced stochasticity within the production, for each manufacturer i there’s a random parameter αi, with a corresponding cumulative distribution
function Fi(αi) .
It is assumed that fi(q, αi) = fi(Q1, αi), so that the cost of all produced
goods is equivalent to the cost of all shipped goods. The expected production cost for firm i, is denoted by
E[Fi(Q1, αi)] =
Z
αi
fi(Q1)dFi(αi) ∀i ∈ (1, .., m)
The variance of the production cost is denoted as V Fi(Q1), with i = 1, ..m.
As assumed previously, each manufacturer has g different types of transporta-tion modes available, disruptransporta-tion applies to each one. Denote βiju as a random parameter associated with the transportation cost of shipping between i and j through mode u.
The density function of disruptions is denoted as Fu
ij(βiju) ∀i ∈ (1, .., m), ∀j ∈
(1, .., n), ∀u ∈ (1, .., g).
The transportation cost between manufacturer i and retailer j is denoted by the function cu
ij(qiju, βiju), ∀i, j, u Finally, we denote, respectively, the expected
shipment cost and the related variance as : E[Ciju](qiju, βiju) =
Z
βiju
cuij(qiju)dF (βiju) ∀i ∈ (1, ..m), ∀j ∈ (1, ..n), ∀u ∈ (1, ..g) V ar(Ciju(qiju, βiju)) ∀i ∈ (1, ..m), ∀j ∈ (1, ..n), ∀u ∈ (1, ..g)
In Nagurney’s model the manufacturer’s risk attitude is denoted as θi, by
which the variance is discounted.
Let pu∗ijqiju denote the profits for producer i given prices p. Maximization involves profit maximization.
The problem can be expressed as
Max qu ij n X j=1 g X u=1 puijqiju − E[Fi(Q1, αi)] − n X j=1 g X u=1 [E(Ciju)(qiju, βi)] −θi[V Fi(Q1, αi) + n X j=1 g X u=1 V Ciju(qiju, βi)] s.t qiju ≥ 0 ∀ i, j, u
in order, the first term represents the revenues, the second the expected dis-ruption on shipments, the third represents the risks involved with production. The final one denotes the variance related to the risk of producing and trans-porting. Based on Nagurney’s VI framework, the problem is rewritten as follows : Determine Q1∗∈ Rmng+ satisfying : m X i=1 n X j=1 g X u=1 [∂E[Fi(Q 1∗)] ∂qu ij +E(C u ij)(qiju∗) ∂qu ij +θi( ∂Fi(Q1∗) ∂qiju∗) + ∂V Cu ij(qiju∗) ∂qiju∗ ] × [q u ij − q u∗ ij ] ≥ 0
4.5
Retailer Behavior
Behaviors trade relationships are inflowing with the manufacturers and out-flowing with the demand markets.
The price charged by the retailers is denoted as pv∗
2jk , in order to ship a unit
of product to market k through transportation mode v.
It is assumed that certain disruptions will affect the retailers, denote as Φj
the random parameter associated with the handling cost of retailer j. Again, it is assumed that h different transportation modes exists for each retailer-market relationship.
For each retailer, there are h different transportation modes to the final mar-kets.
The cumulative distribution function of Φ is denoted by Fi(Φi) ∀ i.
Let qv
ik denote the product shipment between j and k by means of mode v,
retailers expected cost of handling the shipment is given by E[Cj1(Q1, Φj)] =
Z
Φi
cj(Q1)dFj(Φj) ∀ j = 1, ..., m
The variance of the cost function is denoted by V Cj1(Q1, Φj) , and they
dis-count it with their individual risk attitude Γj .
In a similar case to the manufacturer’s one, retailers want to maximize their profits, taking into account both the prices and the costs charged by disrup-tions at manufacturer level.
max qjk o X k=1 h X v=1 pv∗2jkqjk− E[Cj1(Q1, Φj)] − m X i=1 g X u=1 pu∗1ijqiju − ΓjV Cj1(Q1, Φ) s.t. o X k=1 h X v=1 qjkv ≤ m X i=1 g X u=1 quij
Along with the non negativity constraint for the quantities. The profit max-imization problem is expressed in terms of VI as follows :
Determine (Q1∗, Q2∗, γ∗) ∈ R+mng+noh+n such that
m X i=1 n X j=1 g X u=1 [∂E[C 1 j(Q1∗, φj)] ∂qu ij + pu∗ij + Γj ∂V C1 j(Q1∗, φj) ∂qu∗ ij − γ∗] × [quij− qu∗ ij ]
