Journal of Convex Analysis Volume 3 (1996), No.1, 71–81

Existence of Feasible Potentials on Infinite Networks

Werner Oettli

Fakultät für Mathematik und Informatik, Universität Mannheim, 68131 Mannheim, Germany. e-mail: oettli@math.uni-mannheim.de

Maretsugu Yamasaki

Department of Mathematics, Shimane University, Matsue, Japan 690. e-mail: yamasaki@botan.shimane-u.ac.jp

Received June 7, 1994 Revised manuscript received July 24, 1995

Dedicated to R. T. Rockafellar on his 60th Birthday

Conditions are given for the existence of feasible potentials on locally finite networks and locally finite hypergraphs.

Keywords : Locally finite networks, locally finite hypergraphs, feasible potentials, feasible flows, Farkas’ Lemma.

1. Introduction and Problem Setting

The problem of finding a potential satisfying given constraints is known as the feasible potential problem. This is one of the fundamental problems in the theory of networks. In this paper we derive necessary and sufficient conditions for the existence of feasible potentials in infinite, but locally finite, networks and more generally in locally finite hypergraphs.

In connection with problems of flows and potentials, the practical need for considering infinite networks has been recognized for a long time. We refer for instance to the monographs [6] and [8]. In these books, the feasible potential problem is discussed only in the case when the contraints are equalities, and their proofs depend essentially on the classical Riesz’ Representation Theorem in a Hilbert space. In this paper we consider the case of upper and lower bounds for potentials and tensions, and our result is based on a fundamental tool of convex analysis, namely a generalized version of Farkas’ Lemma. This is the content of Section 2.

Alternative, and more constructive, proofs for particular cases are given in Sections 3 and 4. Here we combine the Sandwich Theorem of convex analysis with the use of

ISSN 0944-6532 / $ 2.50 ◯^{c} Heldermann Verlag

72 W. Oettli, M. Yamasaki / Existence of Feasible Potentials

paths and cycles.

Discrete potential problems are considered in greater generality in Section 5. Here the feasible potential problem is extended to what we call locally finite hypergraphs. Except for the use of our generalized Farkas’ Lemma, this Section is independent of the previous ones. Our idea is to replace the node-arc incidence function by an arbitrary real-valued function having finite support within the set of nodes and within the set of arcs, respectively. Thus nodes and arcs are treated equally, and there is a symmetric duality between potentials and flows. The feasibility contraints include now also bounds on the discrete Laplacian. At one place we have to introduce an abstract notion of connectedness for such hypergraphs.

Due to the perfect symmetry between nodes and arcs we obtain as a by-product in Section 6 conditions for the existence of feasible flows in locally finite hypergraphs.

We are now going to describe our model in more detail. Let G := {X, Y, K} be a directed, locally finite graph without self-loops. Here X ≠ ∅ is the (arbitrary) set of nodes, Y is the (arbitrary) set of arcs, and K : X × Y → {−1, 0, +1} is the node-arc incidence function of G. For every arc y ∈ Y the initial node x^{−}(y) and the terminal node x^{+}(y) are uniquely defined by the relations K(x^{−}(y), y) = −1, K(x^{+}(y), y) = +1. Local finiteness of G means that, for every x ∈ X, K(x, ·) has finite support in Y.

Let Y denote the space of all real-valued functions defined on Y, and let Y^{∗} denote the subspace of all real-valued functions defined on Y and having finite support. Let Y_{+} (resp. Y_{+}^{∗}) denote the subset of Y (resp. Y^{∗}) which consists of the nonnegative functions. For f ∈ Y and g ∈ Y^{∗} let ⟨f, g⟩ := ∑_{y∈Y} f(y)g(y). Replacing Y by X we define similarly X , X^{∗}, X_{+}, X_{+}^{∗} and ⟨·, ·⟩ : X × X^{∗} → IR. To the function K(x, y) we associate the linear mappings K : X → Y and K^{∗} : Y^{∗} → X^{∗} through

(Kf)(y) := ∑_{x∈X} K(x, y)f(x) = f(x^{+}(y)) − f(x^{−}(y)),

(K^{∗}w)(x) := ∑_{y∈Y} K(x, y)w(y).

Note that ⟨Kf, w⟩ = ⟨f, K^{∗}w⟩ for all f ∈ X , w ∈ Y^{∗} (since all sums are finite, the order of summation can be interchanged freely). Kf is the tension on Y associated to the potential f on X. K^{∗}w is the divergence on X associated to the flow w on Y [7].

Let A, B ∈ Y be given such that A(y) ≤ B(y) on Y. Let β ∈ X be given such that 0 ≤ β(x) on X. We want to find a necessary and sufficient condition for the existence of a function u ∈ X (potential function) satisfying the following requirements:

0 ≤ u(x) ≤ β(x) on X,  (1)
A(y) ≤ (Ku)(y) ≤ B(y) on Y.  (2)

2. Existence Result

For w ∈ Y^{∗} let w^{+}(y) := max{0, w(y)}, w^{−}(y) := max{0, −w(y)}. Similarly we define f^{+}, f^{−} for f ∈ X^{∗}. For w ∈ Y^{∗} let l(w) and ϱ(w) be given as

l(w) := ⟨A, w^{+}⟩ − ⟨B, w^{−}⟩,
ϱ(w) := ⟨β, (K^{∗}w)^{+}⟩.

The functions ϱ and −l are sublinear on Y^{∗}. In particular there holds

l(w_{1} + w_{2}) ≥ l(w_{1}) + l(w_{2}).

Now we have the following result.

Theorem 2.1. Problem (1), (2) has a solution u ∈ X if, and only if, the following condition holds:

l(w) ≤ ϱ(w) for all w ∈ Y^{∗}.  (C1)

Before proceeding with the proof of Theorem 2.1 we have to establish a generalization of Farkas’ Lemma [2, p.134]. Recall that if F is a real topological vector space with continuous dual F^{∗} (the space of all continuous linear forms on F), and if Q ⊆ F is a convex cone, then the polar cone of Q is defined as Q^{0} := {ξ ∈ F^{∗} | ⟨x, ξ⟩ ≥ 0 ∀x ∈ Q}.

Lemma 2.2. Let the following assumptions hold:

• E is a real topological vector space, F is a locally convex topological vector space;

• P ⊆ E is a nonempty convex set, and δ_{P} (v) := inf_{u∈P} ⟨u, v⟩ for all v ∈ E^{∗};

• Q ⊆ F is a convex cone, and Q^{0} ⊆ F^{∗} is its polar cone;

• T : E → F is linear, T^{∗} : F^{∗} → E^{∗} is such that ⟨T e, φ⟩ = ⟨e, T^{∗}φ⟩ for all e ∈ E, φ ∈ F^{∗};

• f_{0} ∈ F is a fixed element;

• T (P) + Q is closed in F.

Then from δ_{P} (T^{∗}φ) ≤ ⟨f_{0}, φ⟩ for all φ ∈ Q^{0}, it follows that f_{0} ∈ T (P) + Q.

Proof. Assume, for contradiction, that f_{0} is not an element of the closed convex set T (P) + Q. Then from the strong separation theorem in a locally convex space [5, p.65] there exist φ ∈ F^{∗} and t ∈ IR such that

\begin{aligned}t & > ⟨f_{0}, φ⟩, \\ t & ≤ ⟨T p + q, φ⟩ = ⟨p, T^{∗}φ⟩ + ⟨q, φ⟩ for all p ∈ P, q ∈ Q. \end{aligned}

From the latter inequality follows φ ∈ Q^{0} and t ≤ δ_{P} (T^{∗}φ). Together with the first inequality we obtain δ_{P} (T^{∗}φ) > ⟨f_{0}, φ⟩, and this contradicts the hypothesis of the lemma.

Remark 2.3. If P, in addition, is a cone, then δ_{P} (v) = 0 if v ∈ P^{0}, and δ_{P} (v) = −∞ if v ∉ P^{0}. Hence the conclusion of Lemma 2.2 reads in this case: If 0 ≤ ⟨f_{0}, φ⟩ for all φ ∈ Q^{0} satisfying T^{∗}φ ∈ P^{0}, then f_{0} ∈ T (P) + Q.

Whenever we apply Lemma 2.2 we shall provide Y = IR^{Y} (the space of all real-valued functions on Y) with the product topology. Then Y^{∗} as defined in paragraph 1 can be identified with the continuous dual of Y. In fact, every continuous linear form λ(·) on Y can be represented as

λ(f) = ∑_{i=1}^{k} λ_{i}f(y_{i}) with k ∈ IN, y_{i} ∈ Y, λ_{i} ∈ IR,

hence it can be identified with the function λ̃ ∈ Y^{∗} given by

λ̃(y) := \{ \begin{matrix}λ_{i}, & if y = y_{i} (i = 1, …, k), \\ 0 & else. \end{matrix}

Likewise we shall provide X = IR^{X} with the product topology. In this setting Y_{+}^{∗} and X_{+}^{∗} become the polar cones of Y_{+} and X_{+} respectively, i.e., (Y_{+})^{0} = Y_{+}^{∗} and (X_{+})^{0} = X_{+}^{∗}. Now we are ready to prove Theorem 2.1.

Proof of Theorem 2.1: The necessity of (C1) is easily seen. Indeed, let u ∈ X be a solution of (1), (2). Then for every w ∈ Y^{∗} we have

⟨A, w^{+}⟩ − ⟨B, w^{−}⟩ ≤ ⟨Ku, w^{+}⟩ − ⟨Ku, w^{−}⟩ = ⟨Ku, w⟩ = ⟨u, K^{∗}w⟩
≤ ⟨u, (K^{∗}w)^{+}⟩
≤ ⟨β, (K^{∗}w)^{+}⟩,

and therefore l(w) ≤ ϱ(w). So (C1) holds. We turn now to sufficiency. If w_{1} ≥ 0, w_{2} ≥ 0, w = w_{1} − w_{2} and A ≤ B, then

⟨A, w_{1}⟩ − ⟨B, w_{2}⟩ ≤ ⟨A, w^{+}⟩ − ⟨B, w^{−}⟩.

Therefore from (C1) we obtain:

0 ≤ ϱ(w_{1} − w_{2}) − ⟨A, w_{1}⟩ + ⟨B, w_{2}⟩ for all w_{1} ∈ Y_{+}^{∗}, w_{2} ∈ Y_{+}^{∗}.  (3)

We now substitute in Lemma 2.2:

E := X , F := Y × Y,
P := {u ∈ X | 0 ≤ u ≤ β},
δ_{P} (v) = inf_{u∈P} ⟨u, v⟩ = −⟨β, v^{−}⟩,
Q := Y_{+} × Y_{+}, Q^{0} = Y_{+}^{∗} × Y_{+}^{∗},
T := (−K, K) : X → Y × Y,
T^{∗}(w_{1}, w_{2}) = −K^{∗}(w_{1} − w_{2}),
f_{0} := (−A, B).

Then from (3) follows 0 ≤ −δ_{P} (T^{∗}φ)+⟨f_{0}, φ⟩ for all φ = (w_{1}, w_{2}) ∈ Q^{0}. So the hypothesis of Lemma 2.2 is satisfied. The conclusion of Lemma 2.2 gives f_{0} ∈ T (P) + Q, i.e.,

(−A, B) ∈ (−K, K)(P) + (Y_{+} × Y_{+}).

So there exists u ∈ P such that −A ∈ −Ku + Y_{+}, B ∈ Ku + Y_{+}. Then u is a solution to (1), (2). It remains to verify the closedness of the set

T (P) + Q = (−K, K)(P) + (Y_{+} × Y_{+})

which is needed for Lemma 2.2. Recall that X and Y are endowed with the product topology. So convergence in X and Y means pointwise convergence. From this it is easily seen that the mapping K : X → Y is continuous. The set P = ∏_{x∈X}[0, β(x)] (a product of compact intervals) is compact in X according to Tychonoff’s Theorem. Hence (−K, K)(P), being the continuous image of a compact set, is compact. Since Y_{+} × Y_{+} is closed, and since the sum of a compact set and a closed set is closed, we obtain that T (P) + Q is closed in Y × Y. This completes the proof of Theorem 2.1.

3. Alternative Approach

We suppose now that the graph G is finitely connected, and we give for this case another proof of the sufficiency of (C1) which does not employ Farkas’ Lemma, but relies instead on paths and cycles. We recall the following. A path P in G is a triplet P = {X(P), Y (P), p}, where

• X(P) = {x_{0}, x_{1}, …, x_{n}} is a finite nonempty sequence of nodes,

• Y (P) = {y_{1}, …, y_{n}} is a finite sequence of pairwise different arcs with K(x_{i−1}, y_{i}) · K(x_{i}, y_{i}) = −1 for i = 1, …, n,

• p ∈ Y^{∗} (the path function) is given by

\begin{aligned}p(y_{i}) & := K(x_{i}, y_{i}) for i = 1, …, n, \\ p(y) & := 0 for y ∉ Y (P). \end{aligned}

A path from a ∈ X to b ∈ X is a path with x_{0} = a, x_{n} = b. A cycle is a path with x_{0} = x_{n}. We denote by P_{a,b} the set of all paths from a to b, and we denote by Z the set of all cycles. Finite connectedness of G means that P_{a,b} ≠ ∅ for all a, b ∈ X. Henceforth we identify a path P with its path function p, and we write accordingly p ∈ P_{a,b}, p ∈ Z, etc. The empty path p̃ = 0 belongs to Z as well as to P_{a,a} for all a ∈ X. We fix now a ∈ X and conduct the proof of the sufficiency of (C1) as follows.

Second Proof of Theorem 2.1: From (C1) we have l(w) ≤ ϱ(w) on Y^{∗}, where l is superlinear and ϱ is sublinear. From the Sandwich Theorem [2, p.112] there exists a linear function ξ on Y^{∗} such that

l(w) ≤ ξ(w) ≤ ϱ(w) on Y^{∗}.  (4)

For two paths p_{1}, p_{2} ∈ P_{a,x} we obtain from (4), since K^{∗}(p_{1} − p_{2}) = 0, that ξ(p_{1} − p_{2}) ≤ ϱ(p_{1} − p_{2}) = 0. Likewise we obtain ξ(p_{2} − p_{1}) ≤ 0. Since ξ is linear this implies ξ(p_{1}) = ξ(p_{2}). From this follows ξ(p) = 0 for all p ∈ Z (since every cycle p can be represented as p = p_{1} − p_{2} with p_{1}, p_{2} ∈ P_{a,x} for a suitably chosen x ∈ X). We can now define unambiguously u ∈ X by

u(x) := ξ(p) for some p ∈ P_{a,x}.

This implies in particular u(a) = 0, since p̃ = 0 is in P_{a,a}. We show first that u fulfills (2). Let y be any arc, and set x_{1} := x^{−}(y), x_{2} := x^{+}(y). Denote by p_{0} the path from x_{1} to x_{2} consisting only of the arc y. There exists p_{1} ∈ P_{a,x_{1}} such that u(x_{1}) = ξ(p_{1}). Then p_{1} + p_{0} = p_{2} + \overline{p}, where p_{2} ∈ P_{a,x_{2}} and \overline{p} ∈ Z. Consequently

u(x_{2}) = ξ(p_{2}) = ξ(p_{2} + \overline{p}) = ξ(p_{1} + p_{0}) = u(x_{1}) + ξ(p_{0})
≥ u(x_{1}) + l(p_{0}) [from (4)]
= u(x_{1}) + A(y).

So u(x_{2}) − u(x_{1}) ≥ A(y). Likewise we obtain u(x_{1}) − u(x_{2}) ≥ −B(y). Since (Ku)(y) = u(x_{2}) − u(x_{1}), we have A ≤ Ku ≤ B, and u fulfills (2). Now we verify that u fulfills (1). Let p ∈ P_{a,x}. Then, from (4),

u(x) = ξ(p) ≤ ϱ(p) = β(x).

Assume for the moment that β(a) = 0. Then

−u(x) = −ξ(p) = ξ(−p) ≤ ϱ(−p) = β(a) = 0.

Thus 0 ≤ u ≤ β, and u fulfills (1). If β(a) > 0 we proceed as follows. We form an extended graph G^{∗} by adding to G a new node a^{∗} and a new arc y^{∗} which has a^{∗} as initial node and a as terminal node. We define the additional data β(a^{∗}) := 0, A(y^{∗}) := 0, B(y^{∗}) := β(a). We denote by l^{∗} and ϱ^{∗} the corresponding extensions of l and ϱ to G^{∗}. Then

l^{∗}(w(y^{∗}), w) = l(w) − B(y^{∗})(w(y^{∗}))^{−}
= l(w) − β(a)(−w(y^{∗}))^{+},
ϱ^{∗}(w(y^{∗}), w) = ϱ(w) − β(a)k^{+} + β(a)(k + w(y^{∗}))^{+},

where k := (K^{∗}w)(a). From the subadditivity of the function (·)^{+} follows l^{∗}(w(y^{∗}), w) − ϱ^{∗}(w(y^{∗}), w) ≤ l(w) − ϱ(w). Thus, the validity of (C1) carries over from G to G^{∗}. On G^{∗}, since β(a^{∗}) = 0, the previous reasoning applies, and we obtain a feasible potential u^{∗} on X ∪ {a^{∗}}. The restriction of u^{∗} to X satisfies the original requirements (1), (2).

4. A Particular Case

We consider now the case where the potential u(·) is only requested to have property (2). If G is finite the former problem (1), (2) can be reduced to this one by working with an augmented graph [4, p.192]. In the present setting this approach is not feasible, since the resulting graph might no longer be locally finite. We consider the following condition:

l(p) ≤ 0 for all p ∈ Z.  (C2)

For finite graphs it is shown in [1, p.157] that (C2) is necessary and sufficient for the existence of a potential u ∈ X which satisfies (2). Below we extend this result to finitely connected graphs and — what is more important — give a constructive proof for the existence of such a potential.

Let us agree to call two paths or cycles p_{1} and p_{2} parallel iff

p_{1}(y) · p_{2}(y) ≥ 0 for all y ∈ Y.

If p_{1}, p_{2} are parallel, then l(p_{1} + p_{2}) = l(p_{1}) + l(p_{2}). We note that from (C2) follows for every fixed a ∈ X that

l(p_{1}) + l(−p_{2}) ≤ 0 for all p_{1}, p_{2} ∈ P_{a,x} and for all x ∈ X,  (5)

since p_{1}−p_{2} can be represented as a sum of parallel cycles p̃_{i} and therefore l(p_{1})+l(−p_{2}) ≤ l(p_{1} − p_{2}) = l(∑_{i} p̃_{i}) = ∑_{i} l(p̃_{i}) ≤ 0.

Theorem 4.1. Let G be finitely connected. Then condition (C2) is necessary and sufficient for the existence of a function u ∈ X which satisfies (2).

Proof. If p is a cycle, then K^{∗}p = 0. Therefore, if u fulfills (2) and p ∈ Z, we obtain

l(p) = ⟨A, p^{+}⟩ − ⟨B, p^{−}⟩
≤ ⟨Ku, p^{+}⟩ − ⟨Ku, p^{−}⟩
= ⟨Ku, p⟩ = ⟨u, K^{∗}p⟩
= 0.

Thus (C2) is a necessary condition. To prove sufficiency, assume that (C2) holds. Fix a ∈ X. For every x ∈ X define

u(x) := sup{l(p) | p ∈ P_{a,x}}.

From (5) follows u(x) < ∞ for all x. Moreover we have u(a) = 0, since l(p) ≤ 0 for all p ∈ P_{a,a}, with equality holding for p = 0 ∈ P_{a,a}. We show that u fulfills (2). Let y be any arc, and set x_{1} := x^{−}(y), x_{2} := x^{+}(y). Let p_{0} be the path from x_{1} to x_{2} consisting only of the arc y. Let ε > 0. There exists p_{1} ∈ P_{a,x_{1}} such that l(p_{1}) ≥ u(x_{1}) − ε. Then p_{1} + p_{0} = p_{2} + p̃, where p_{2} ∈ P_{a,x_{2}}, p̃ ∈ Z, and p_{2}, p̃ are parallel. So

l(p_{2}) + l(p̃) = l(p_{2} + p̃) = l(p_{1} + p_{0}) ≥ l(p_{1}) + l(p_{0}),

and therefore

\begin{aligned}u(x_{2}) & ≥ l(p_{2}) ≥ l(p_{2}) + l(p̃) ≥ l(p_{1}) + l(p_{0}) ≥ u(x_{1}) − ε + l(p_{0}) \\ & = u(x_{1}) − ε + A(y). \end{aligned}

Since ε > 0 was arbitrary, u(x_{2}) − u(x_{1}) ≥ A(y). Similarly we obtain u(x_{1}) − u(x_{2}) ≥ −B(y), and u is a solution of (2).

5. Generalization

We consider now discrete potential problems in somewhat greater generality. Let X and Y be arbitrary sets, and ψ(·, ·) : X × Y → IR a function such that for each x ∈ X and y ∈ Y, ψ(x, ·) and ψ(·, y) have finite support on Y and X respectively. We call the triplet H := {X, Y, ψ} a (locally finite) hypergraph, for short. X , X^{∗}, Y, Y^{∗} have the same meaning as before. We define the discrete derivative d : X → Y and discrete Laplacian Δ : X → X through

(du)(y) := ∑_{x∈X} ψ(x, y)u(x),
(Δu)(x) := ∑_{y∈Y} ψ(x, y)(du)(y).

Given α, β ∈ X , A, B ∈ Y, λ, μ ∈ X such that α ≤ β, A ≤ B, λ ≤ μ, we consider the existence of u ∈ X which satisfies the following conditions:

α ≤ u ≤ β on X,  (6)
A ≤ du ≤ B on Y,  (7)
λ ≤ Δu ≤ μ on X.  (8)

We obtain a feasibility condition for this problem from Lemma 2.2. To formulate this we introduce the following notations. Define d^{∗} : Y^{∗} → X^{∗} through

(d^{∗}f)(x) := ∑_{y∈Y} ψ(x, y)f(y).

Then ⟨du, f⟩ = ⟨u, d^{∗}f⟩ for all u ∈ X , f ∈ Y^{∗}. If u ∈ X^{∗}, then clearly Δu ∈ X^{∗}, too. So we can define Δ^{∗} : X^{∗} → X^{∗} through Δ^{∗} := Δ|_{X^{∗}}. Then ⟨Δu, w⟩ = ⟨u, Δ^{∗}w⟩ for all u ∈ X , w ∈ X^{∗}.

Theorem 5.1. There exists u ∈ X which satisfies (6), (7), (8) if, and only if, the following condition is satisfied:

0 ≤ ⟨β, h^{+}⟩ − ⟨α, h^{−}⟩ + ⟨B, f^{+}⟩ − ⟨A, f^{−}⟩ + ⟨μ, g^{+}⟩ − ⟨λ, g^{−}⟩  (C3)
for all f ∈ Y^{∗}, g ∈ X^{∗}, h ∈ X^{∗}satisfying h + d^{∗}f + Δ^{∗}g = 0.

Proof. If u is a solution to (6), (7), (8) and f, g, h are as in (C3), then

0 = ⟨u, h + d^{∗}f + Δ^{∗}g⟩
= ⟨u, h⟩ + ⟨du, f⟩ + ⟨Δu, g⟩
= ⟨u, h^{+}⟩ − ⟨u, h^{−}⟩ + ⟨du, f^{+}⟩ − ⟨du, f^{−}⟩ + ⟨Δu, g^{+}⟩ − ⟨Δu, g^{−}⟩
≤ ⟨β, h^{+}⟩ − ⟨α, h^{−}⟩ + ⟨B, f^{+}⟩ − ⟨A, f^{−}⟩ + ⟨μ, g^{+}⟩ − ⟨λ, g^{−}⟩.

Thus (C3) holds. To prove sufficiency we note that from c_{1} ≥ c_{2}, d_{1} ≥ 0, d_{2} ≥ 0, d = d_{1} − d_{2} it follows that ⟨c_{1}, d^{+}⟩ − ⟨c_{2}, d^{−}⟩ ≤ ⟨c_{1}, d_{1}⟩ − ⟨c_{2}, d_{2}⟩. Therefore (C3) implies (in fact, is equivalent with)

0 ≤ ⟨β, h^{+}⟩ − ⟨α, h^{−}⟩ + ⟨B, f_{1}⟩ − ⟨A, f_{2}⟩ + ⟨μ, g_{1}⟩ − ⟨λ, g_{2}⟩  (9)
for all f_{1}, f_{2} ∈ Y_{+}^{∗}, g_{1}, g_{2} ∈ X_{+}^{∗}, h ∈ X^{∗} such that
h + d^{∗}(f_{1} − f_{2}) + Δ^{∗}(g_{1} − g_{2}) = 0.

Now we substitute in Lemma 2.2:

E := X , F := Y × Y × X × X ,
P := {u ∈ X | α ≤ u ≤ β},
δ_{P} (v) = inf_{u∈P} ⟨u, v⟩ = ⟨α, v^{+}⟩ − ⟨β, v^{−}⟩,
Q := Y_{+} × Y_{+} × X_{+} × X_{+}, Q^{0} = Y_{+}^{∗} × Y_{+}^{∗} × X_{+}^{∗} × X_{+}^{∗},
T := (d, −d, Δ, −Δ) : X → Y × Y × X × X ,
T^{∗}(f_{1}, f_{2}, g_{1}, g_{2}) = d^{∗}(f_{1} − f_{2}) + Δ^{∗}(g_{1} − g_{2}),
f_{0} := (B, −A, μ, −λ).

Then from (9) it follows that 0 ≤ −δ_{P} (T^{∗}φ) + ⟨f_{0}, φ⟩ for all φ = (f_{1}, f_{2}, g_{1}, g_{2}) ∈ Q^{0}. From Lemma 2.2 we obtain that f_{0} ∈ T (P) + Q, i.e.,

(B, −A, μ, −λ) ∈ (d, −d, Δ, −Δ)(P) + (Y_{+} × Y_{+} × X_{+} × X_{+}).

So there exists u ∈ P such that

B ≥ du, −A ≥ −du, μ ≥ Δu, −λ ≥ −Δu.

Then u satisfies (6), (7), (8). The closedness of the set T (P) + Q follows as in the proof of Theorem 2.1.

If we omit requirement (8), then correspondingly in condition (C3) we have to delete all terms involving g; this is easily read off from the proof of Theorem 5.1. Likewise, if we omit requirement (7), then we have to cancel in (C3) all terms involving f. For reference we note this as a corollary where, however, instead of (C3) we employ the equivalent condition (9).

Corollary 5.2. There exists u ∈ X which satisfies (6), (8) if, and only if,

\begin{matrix}0 ≤ ⟨β, h^{+}⟩ − ⟨α, h^{−}⟩ + ⟨μ, g_{1}⟩ − ⟨λ, g_{2}⟩ \\ for all g_{1}, g_{2} ∈ X_{+}^{∗} and h := Δ^{∗}(g_{2} − g_{1}). \end{matrix}

Now we want to omit condition (6) from the requirements for u. We say that H is connected iff for every a ∈ X, b ∈ X there exists p ∈ Y^{∗} such that

|f(b) − f(a)| ≤ |⟨df, p⟩| for all f ∈ X .

For comparison we note that, if H := G and p ∈ P_{a,b}, then f(b) − f(a) = ⟨Kf, p⟩.

Theorem 5.3. Let X and Y be countable. Assume that H is connected, and that ∑_{x∈X} ψ(x, y) = 0 for all y ∈ Y. Then there exists u ∈ X which satisfies (7) and (8) if, and only if, the following condition is satisfied:

0 ≤ ⟨B, f^{+}⟩ − ⟨A, f^{−}⟩ + ⟨μ, g^{+}⟩ − ⟨λ, g^{−}⟩  (C4)
for all f ∈ Y^{∗}, g ∈ X^{∗}satisfying d^{∗}f + Δ^{∗}g = 0.

Proof. Necessity of (C4) is straightforward. To prove sufficiency we note that (C4) is equivalent with

0 ≤ ⟨B, f_{1}⟩ − ⟨A, f_{2}⟩ + ⟨μ, g_{1}⟩ − ⟨λ, g_{2}⟩  (10)
for all f_{1}, f_{2} ∈ Y_{+}^{∗}, g_{1}, g_{2} ∈ X_{+}^{∗}
such that d^{∗}(f_{1} − f_{2}) + Δ^{∗}(g_{1} − g_{2}) = 0.

For applying Lemma 2.2 we make the same substitutions as in the proof of Theorem 5.1, with one exception: P is now chosen as P := X. Then P^{0} = {0_{X^{∗}}}, and from (10) it follows that

0 ≤ ⟨f_{0}, φ⟩ for all φ = (f_{1}, f_{2}, g_{1}, g_{2}) ∈ Q^{0} such that T^{∗}φ ∈ P^{0}.

Anticipating the closedness of T (P) + Q, it results from Lemma 2.2 and Remark 2.3 that f_{0} ∈ T (P) + Q, i.e., there exists u ∈ X such that f_{0} ∈ T u + Q. Then u fulfills (7) and (8). We have still to prove the closedness of the set

T (P) + Q = (d, −d, Δ, −Δ)(X) + (Y_{+} × Y_{+} × X_{+} × X_{+}).

In order to keep notations simple we shall only prove the closedness of the set

C := (d, −d)(X) + (Y_{+} × Y_{+}),

the general case presenting no additional difficulties. X and Y are provided with the product topology. Assume that (\overline{B}, −\overline{A}) is in the closure of C. Since Y has a countable neighborhood base of the origin, there exists a countable sequence {(B^{n}, −A^{n})} ⊆ C such that B^{n} → \overline{B} and A^{n} → \overline{A} pointwise on Y as n → ∞. Then there exists a sequence {u^{n}} ⊆ X such that A^{n} ≤ du^{n} ≤ B^{n} for all n. Clearly the sequence {(du^{n})(y)} remains bounded for every y ∈ Y (this argument would fail if we had to admit generalized sequences). Fix a ∈ X. The assumption ∑_{x∈X} ψ(x, y) ≡ 0 ensures that for every constant function γ ∈ X we have d(u^{n} − γ) = du^{n}. Hence, by subtracting suitable constants, we may assume that u^{n}(a) = 0 for all n. Since H is connected there exists for every x ∈ X some p ∈ Y^{∗} such that

|⟨du^{n}, p⟩| ≥ |u^{n}(x) − u^{n}(a)| = |u^{n}(x)| for all n.

From this and the boundedness of the sequence {(du^{n})(y)} for all y ∈ Y it follows, since p has finite support, that the sequence {u^{n}(x)} is bounded for every x ∈ X, i.e., there exists d(x) ≥ 0 such that

−d(x) ≤ u^{n}(x) ≤ d(x) for all n.

Hence {u^{n}} ⊆ ∏_{x∈X}[−d(x), +d(x)], and the latter set is compact by Tychonoff’s Theorem. So there exists a subsequence, again denoted by u^{n}, such that u^{n} → \overline{u} ∈ X pointwise as n → ∞. Since d is continuous it follows that du^{n} → d\overline{u}. Then it is easily seen that \overline{A} ≤ d\overline{u} ≤ \overline{B}, and (\overline{B}, −\overline{A}) is in C. So C is closed. This completes the proof of Theorem 5.3.

6. Feasible flows

Since H is symmetric with regard to the roles played by X and Y, Theorem 5.1 carries over to problems of feasible flows. Let H be as introduced in the previous paragraph. We define the discrete divergence D : Y → X through

(Df)(x) := ∑_{y∈Y} ψ(x, y)f(y),

and we define D^{∗} : X^{∗} → Y^{∗} through

(D^{∗}g)(y) := ∑_{x∈X} ψ(x, y) g(x).

Note that Δ = D ∘ d. We consider the problem of finding a flow w ∈ Y such that

V ≤ w ≤ W on Y,  (11)
λ ≤ Dw ≤ μ on X,  (12)

where V ≤ W on Y and λ ≤ μ on X [3]. In complete analogy with Corollary 5.2 we obtain

Theorem 6.1. There exists w ∈ Y satisfying (11), (12) if, and only if,

0 ≤ ⟨W, f^{+}⟩ − ⟨V, f^{−}⟩ + ⟨μ, h_{1}⟩ − ⟨λ, h_{2}⟩  (C5)
for all h_{1}, h_{2} ∈ X_{+}^{∗} and f := D^{∗}(h_{2} − h_{1}).

If H := G (which means that ψ(x, y) coincides with K(x, y) as defined in paragraph 1), then condition (C5) is equivalent to the discrete conditions

0 ≤ ⟨W, f_{1}^{−}⟩ − ⟨V, f_{1}^{+}⟩ + ⟨μ, h_{1}⟩ for all h_{1} ∈ X_{0,1}^{∗} and f_{1} := D^{∗}h_{1},
0 ≤ ⟨W, f_{2}^{+}⟩ − ⟨V, f_{2}^{−}⟩ − ⟨λ, h_{2}⟩ for all h_{2} ∈ X_{0,1}^{∗} and f_{2} := D^{∗}h_{2}.

Here X_{0,1}^{∗} is the class of all functions from X^{∗} which assume only the values 0 and 1, i.e., which are characteristic functions of finite subsets of X. We refer to [3] for details.

References

[1] C. Berge, A. Ghouila-Houri: Programmes, jeux et réseaux de transport. Dunod, Paris, 1962.

[2] H. König: On some basic theorems in convex analysis, pp.107–144 in Modern Applied Mathematics, ed. by B. Korte. North-Holland, Amsterdam, 1982.

[3] W. Oettli, M. Yamasaki: On Gale’s feasibility theorem for certain infinite networks. Arch. Math. 62 (1994) 378–384.

[4] R.T. Rockafellar: Network Flows and Monotropic Optimization. Wiley, New York, 1984.

[5] H.H. Schaefer: Topological Vector Spaces. Springer-Verlag, New York, 1971.

[6] P.M. Soardi: Potential Theory on Infinite Networks (Lecture Notes in Mathematics, 1590). Springer-Verlag, Berlin Heidelberg, 1994.

[7] M. Yamasaki: Extremum problems on an infinite network. Hiroshima Math. J. 5 (1975) 223–250.

[8] A.H. Zemanian: Infinite Electrical Networks. Cambridge University Press, Cambridge, 1991.

82 W. Oettli, M. Yamasaki / Existence of Feasible Potentials HIER :

Leere Seite