Convexity and starshapedness of feasible sets in stationary flow networks

1.   Introduction and motivation

In this paper, we analyze the structure of the set of feasible loads in stationary gas networks.

Gas transport through a pipeline network has been the topic of many articles in the last years. These models are often based on the Euler equations (see [4]) or simplifications like the isothermal Euler equations (see [1,2,9,10,11,12,13]). An overview about existing models and the components of a gas network can be found in [5,16]. In [10] the authors show the existence of a unique stationary state, while in [11,14] the model is analyzed for real gas. Optimal control problems with gas networks are considered for example in [3]

It is important to take into account the uncertainty of the boundary data. This leads to optimization problems with probabilistic constraints (see [17]). Especially the model in [9] is quite interesting, because it gives a new access to this topic with respect to uncertain boundary data. This model has also been studied and extended in [12]. The aim in these works is stochastic optimization resp. to answer the question, how large is the probability for a random Gaussian distributed load vector to be feasible. The main tool in these works to compute this probability is the so-called spheric-radial decomposition (see e.g. [21,22,6,9,8]).

Theorem 1.1. (spheric-radial decomposition, see [9], Theorem 2) Let $\xi \sim \mathcal{N}(0, R)$ be the $n$-dimensional standard Gaussian distribution with zero mean and positive definite correlation matrix $R$. Then, for any Borel measurable subset $M \subseteq \mathbb{R}^n$ it holds that

where $\mathbb{S}^{n-1}$ is the $(n-1)$-dimensional sphere in $\mathbb{R}^n$, $\mu_\eta$ is the uniform distribution on $\mathbb{S}^{n-1}$, $\mu_\chi$ denotes the $\chi$-distribution with $n$ degrees of freedom and $L$ is such that $R = L L^T$ (e.g., Cholesky decomposition).

For optimization techniques, it is always an advantage to know, that the admissible set has a special structure like convexity. For example using the integral in Theorem 1.1 for a set $M$, a sampled point $v \in \mathbb{S}^{n-1}$ and a square matrix $L \in \mathbb{R}^n$ (which is a Cholesky decomposition of the covariance matrix of the distribution), one has to compute the one-dimensional set $\{r \geq 0\ \vert\ r L v \in M \}$. This set can be represented as a union of disjoint intervals, but for big graphs, the number of disjoint intervals can be very large. So the numerical computation of this union can be very time-demanding. The idea of this paper is, that knowledge about the structure of set $M$, which is the set of feasible loads in our model, allows to reduce the time of computation enormously. E.g. if one know that $M$ is convex or star-shaped with respect to some point, the sets $\{r \geq 0\ \vert\ r L v \in M \}$ are just convex intervals. This implies that the algorithm for computing these unions of disjoint intervals can stop as soon as it finds one interval.

The fact that star-shapedness is an important property in this context, was already mentioned in Assumption 2.1 (ⅱ) in [19]. There star-shapedness is required to define a radial function which maps a ray to the intersection of the ray and a given set. Then if the rays and the given set intersect transversally (cf. Assumption 2.2 (ⅲ), [19]), the Implicit Function Theorem can be applied to this radial function and gradients of probability functions can be computed. Convexity of a given set implies this transversal intersection, if the mean of the Gaussian distribution is in the interior of the given set. Thus convexity can be important for computing gradients of probability functions, e.g. in [23] convexity is a general assumption.

In a nutshell, we analyze the set of feasible loads in the mathematical model of gas transport, depending on the topology of the graph and on the pressure bounds at the nodes. In [20], the authors also analyze the structure of feasible sets in the context of gas transport, though in a different way. The main difference of their model is, that they use a mixed-integer flow model for networks with compressor stations. However, our results about convexity and star-shapedness for networks with compressor stations are not stated in [20]. We will illustrate the difference of the results in the appropriate sections. In Section 2, we shortly introduce the mathematical model. In Section 3, we give a result about convexity of a graph with and without compressor edges and in Section 4 we give some results about when the set of feasible loads is star-shaped to some point.

2.   Mathematical modeling

We will use the model introduced in [12], which is an extension of the model in [9]. The difference between these models is, that the model in [9] does not support compressor stations, which are an important element in gas transport. Compressor stations counteract the pressure drop along the pipes caused by friction. The model in [12] supports these elements.

2.1.   Model description

Consider a connected, directed graph $G = (\mathcal{V}^+, \mathcal{E})$ which represents a pipeline gas transport network. We set $\vert \mathcal{V}^+ \vert = n+1$ and $\vert \mathcal{E} \vert = m$ ($m, n \in \mathbb{N}$). We introduce the following notation for graphs:

Definition 2.1. Consider the connected, directed graph $G = (\mathcal{V}^+, \mathcal{E})$:

$(i)$ $h(e)$ denotes the head node of an edge $e$ and $f(e)$ denotes the foot node of an edge $e$ for all $e \in \mathcal{E}$

$(ii)$ $E_0(v) : = \{ e \in \mathcal{E} \vert h(e) = v \text{ or } f(e) = v \}$ denotes all edges which are connected to node $v \in \mathcal{V}^+$

$(iii)$ The matrix $A^+_{i, j} \in \mathbb{R}^{n+1 \times m}$, $A^+_{i, j} = \sigma(v_i, e_j)$ with

is called the incidence matrix of the graph $G$.

The results of this paper mainly depend on the topology of the graph, so we introduce different structures for a graph:

Definition 2.2. Consider the connected, directed graph $G = (\mathcal{V}^+, \mathcal{E})$:

$(i)$ & The graph $G$ is called linear, if $E(v_0) = 1$ and $\vert E(v) \vert \leq 2$ for all $v \in \mathcal{V}^+$

$(ii)$ & The graph $G$ is called tree-structured, if there exists no edge $e \in \mathcal{E}$ with $h(e) = v_0$ and for all nodes $v \in \mathcal{V}^+$ there is at most one edge $e \in \mathcal{E}$ with $h(e) = v$.

Note, that linear graphs are also tree-structured. Different types of graphs are shown in Figure 1.

For this paper we consider a connected, directed, tree-structured graph $G = (\mathcal{V}^+, \mathcal{E})$ with $\vert \mathcal{V}^+ \vert = n+1$ nodes and $\vert \mathcal{E} \vert = m = n$ edges. We assume, that the root of the tree is the only influx node (gas enters the network) and all other nodes are efflux nodes (gas leaves the network). An edge can either be a flux edge, so the pressure decreases along the edge, or a compressor edge, so the pressure increases along the edge. We define $\mathcal{E}_F$ as the set of all flux edges and $\mathcal{E}_C$ as the set of compressor edges. We have $\mathcal{E} = \mathcal{E}_F \cup \mathcal{E}_C$ with $\mathcal{E}_F \cap \mathcal{E}_C = \emptyset$. We determine a numbering for the nodes and edges of the graph. The input node gets the number $0$ and all other nodes are numbered using breadth-first search or depth-first search. Every edge $e \in \mathcal{E}$ gets the number $\max\{h(e), f(e)\}$.

As notation, we state $\mathcal{V} = \mathcal{V}^+\backslash \{v_0\}$ and $A$ as $A^+$ without the first row, which corresponds to the influx node. Then, the incidence matrix $A$ for tree-structured graphs is square. The following fact is easy to see:

Corollary 1. For a connected, directed, tree-structured graph, the incidence matrix $A$ is an upper triangular matrix with $1$ at its diagonal. Moreover, if the graph is linear, the incidence matrix is $1$ at its diagonal, $-1$ at the diagonal above and $0$ elsewhere.

Because of the triangular structure of the incidence matrix in tree-structured graphs, the matrices are invertible. Using the Gaussian elimination, the following can be shown:

Corollary 2. The inverse of the incidence matrix $A$ of a connected, directed, tree-structured graph is also upper triangular with values in $\{0, 1\}$. Moreover, if the graph is linear, the inverse incidence matrix is $1$ in the upper triangle and $0$ elsewhere.

Let $b^+ \in \mathbb{R}^{n+1}$ with $\mathbb{1}_{n+1}b^+ = 0$ denote the balanced load vector and assume $b_i < 0$ for the node with gas influx and $b_i \geq 0$ for nodes with gas efflux ($i \in \{0, \cdots, n\}$), where $\mathbb{1}_{n+1}$ is the vector of all ones in the dimension $n+1$. Let $q \in \mathbb{R}^m$ denote the flows in the edges and $p^+ \in \mathbb{R}^{n+1}$ denotes the pressures at the nodes. Again we set $b$ resp. $p$ as $b^+$ resp. $p^+$ without the first component, corresponding to the inflow node. For the pressure we consider the constraints $p^+ \in [p^{+, \min}, p^{+, \max}]$. The conservation of mass for the graph is given by

The pressure drop in the flux edges $e \in \mathcal{E}_F$ is given by the so-called Weymouth equation (see e.g. [11])

and for the compressor edges $e \in \mathcal{E}_C$ we have

where $\phi_e$ and $u_e$ are constants. The compressor stations counteract the pressure drop caused by friction in the pipes. For a more detailed model derivation we refer to [5,12,18].

Now, we are interested in a solution of this model. The question that we consider is: For a given load vector $b \in \mathbb{R}^n$ (in a tree-structured graph), when can we find corresponding vectors of pressure and flow, so that the box constraints for the pressure, the equation for mass conservation, the equation for the pressure drop and the equation for the compressor stations are fulfilled? Therefore we define the set of feasible loads (called feasible set, here $M$):

Thus, a vector $b \in \mathbb{R}^n$ of given outflows is feasible if and only if $(-\mathbb{1}_n^T b, b) \in M$.

2.2.   Model characterization

In general, it is not easy to see, when this set is nonempty. For a given load vector, one has to find a pressure and a flow vector to show this set is nonempty. Obviously a solution of this model might not be unique, there may exist more solutions. For characterizing the set of feasible loads for a tree-structured graph with no compressor edges, we define a function

The matrix $\Phi \in \mathbb{R}^{n \times n}$ is a diagonal matrix with the values $\phi_i$ at its diagonal. The components $g_k(b)$ describe the pressure loss from the root to node $v_k$ ($k = 1, \cdots, n$) with the load vector $b$. In [9], the authors characterize the set of feasible loads for tree-structured graphs without compressor stations. The idea is as follows: Consider a feasible pressure at a certain node, i.e. the pressure at this node satisfies the box constraints. With the function $g$, we can follow the change in this pressure along the edges in the graph. We have to guarantee, that the changed pressure also fulfills the box constraints at the other nodes. This is listed in the next theorem.

Theorem 2.3. (see [9], Corollary 1) If the network is a tree with a single entry as its root, then the set of feasible nominations is given by

A complete proof of Theorem 2.3 can be found in [9]. For tree-structured networks with compressor stations, the authors of [12] state a similar characterization. The idea here is to separate a graph with $m_c$ compressor edges in $m_c+1$ subgraphs by removing the compressor edges, but still keep the property of the compressor stations. The subgraphs and the nodes inside every subgraph are numbered by breadth-first search resp. depth-first search. Then the notation is the following: $G_i$ denotes the subgraph with number $i$, $p_{i, k}$, $b_{i, k}$ resp. $g_{i, k}$ denote the $k$-th component of the pressure, load vector resp. pressure loss function of the subgraph $G_i$ and $v_{i, k}$ is the node with number $k$ in $G_i$. This is shown in Figure 2.

In addition, we define $p_{(i, j), k}$, $b_{(i, j), k}$ resp. $g_{(i, j), k}$ as the pressure, load vector resp. pressure loss function, which belongs to the $k$-th subgraph between $G_i$ and $G_j$, s.t. $p_{(i, j), 1}$ and $b_{(i, j), 1}$ belong to $G_i$. Further, $p_{(i, j), k, \ell}$, $b_{(i, j), k, \ell}$ resp. $g_{(i, j), k, \ell}$ is the $\ell$-th component of $p_{(i, j), k}$, $b_{(i, j), k}$ resp. $g_{(i, j), k}$. Similarly, we set $u_{(i, j), k}$ as $k$-th control on the path from $v_{i, 0}$ to $v_{j, 0}$. An example of this notation for $i = 1$ and $j = 5$ is shown in Figure 3. We also define $k^*_{i, j}$ as the largest index of all subgraphs, the paths from the root to $v_{i, 0}$ and $v_{j, 0}$ pass. E.g. we have $k^*_{2, 5} = 1$ and $k^*_{2, 4} = 2$ (cf. Figure 2. Last we define $n^*_{i, j}$ as the number of subgraphs, the path from $v_{i, 0}$ to $v_{j, 0}$ pass and $m^*_{i, j}$ as number of controls, the path from $v_{i, 0}$ to $v_{j, 0}$ pass. E.g. it is $n^*_{1, 5} = 3$ and $m^*_{1, 5} = 2$ (cf. Figure 2 and Figure 3). For better readability, we only write $k^*$ instead of $k^*_{i, j}$ and $n^*$ resp. $m^*$ instead of $n^*_{k^*, i}$ resp. $m^*_{k^*, i}$ ($i, j = 1, \cdots, n$). The notation is also explained in detail in [12] above Theorem 5. Then the idea of guaranteeing feasibility is the same as explained above. In the next theorem, a characterization of the set of feasible loads for tree-structured networks with compressor stations is stated.

Theorem 2.4. (see [12], Theorem 5) For given pressure bounds $p^{+, \min}, p^{+, \max} \in \mathbb{R}^{n+1}$ and controls $u_i \in \mathbb{R}$ ($i = 1, \cdots, m_2$) the following equivalence holds:

A vector $b^+$ with $\mathbb{1}^T b^+ = 0$ is feasible, i.e. $b^+ \in M$, if and only if the following inequalities hold: For all $i = 1, \cdots, m_2+1$ holds (feasibility inside the subgraphs)

For all $i, j = 1, \cdots, m_2+1$ with $i < j$ holds (feasibility between the subgraphs)

The values $\Sigma_{k^*, i}$ and $\Pi_{k^*, j}$ are defined as

and

A complete proof of Theorem 2.4 can be found in [12]. The sum defined in (19) as a combination of pressure loss functions and controls, states the change in pressure along a path between subgraphs, e.g. $\Sigma_{1, 4}(\tilde{b})$ gives the chance in pressure between node $v_{1, 0}$ and $v_{2, 1}$ from Figure 2. One can see, that in both theorems (Theorem 2.3 and Theorem 2.4), the decision whether a given load vector is feasible or not only depends on the pressure bounds. So for a given load vector, one has to check if a number of inequalities depending on the load vector and the pressure bounds are fulfilled. This is an enormous simplification to deal with the set of feasible loads. We mention again here, that we distinguish between the load vector $b^+$ (full load vector) and $b$ (load vector without the first component).

3.   Convexity of the feasible set in linear graphs

Here, we will show that in special cases, the feasible set $M$ (defined in (5)) is convex. As it is mentioned in Section 1, the computation of the probability for a random Gaussian distributed load vector to be feasible by using the {spheric-radial decomposition}, simplifies a lot if one knows that the set of feasible loads is convex. Also in this case it is possible to use other algorithms (see e.g. [7]). Throughout this section, we assume that our graph is linear, that is tree-structured without any branching. Thus, the numbering using depth-first search equals the numbering using breadth-first search. We first show a few auxiliary lemmas for the pressure loss function (defined for tree-structured graphs without compressor edges in (6)). The first Lemma is about evaluating $g(\cdot)$ at a convex combination of load vectors.

Lemma 3.1. Let $M \subseteq \mathbb{R}^n_{\geq 0}$ be the set of feasible loads. For $b, \beta \in M$, constants $\phi_i \geq 0$ ($i = 1, \cdots, n$) and $\lambda \in (0, 1)$, it holds (for all $k = 1, \cdots, n$):

with

Proof. From Corollary 2 we know, that $A^{-1}$ contains only non-negative values. The load vectors $b$ and $\beta$ only corresponds to efflux nodes, so they also contain only non-negative values and thus the pressure loss function can be written as

The square has to be understood component-by-component. We have

We fix a $k \in \{1, \cdots, n\}$. Together with

we get $g_k(\lambda b + (1-\lambda) \beta) =$

which is equivalent to

by using the definition of the function $g$ (see (6)). With $\Sigma_k(b, \beta)$ defined in (21) the Lemma is proven.

We call the term $\Sigma_k(b, \beta)$ the remainder term of $g$ evaluated at a convex combination. In the next Lemma, we prove an estimate for this remainder term.

Lemma 3.2. With the setting of Lemma 3.1, at least one of the following estimates hold:

Proof. For this proof, we use a classical contradiction argument. We suppose that

and thus it holds

Since $2ab \leq a^2 + b^2$ for real numbers $a$ and $b$, with this estimate and the definition of $\Sigma_k(b, \beta)$, it follows

Now the terms on the right are equal to $g_k(b)$ resp. $g_k(\beta)$ and thus it follows

which is a contradiction to (22). Thus Lemma 3.2 is proven.

In the last auxiliary lemma, we prove an estimate for a difference of rest terms.

Lemma 3.3. With the setting of Lemma 3.1 and numbers $k, \ell \in \{1, \cdots, n\}$ (with $k < \ell$), at least one of the following estimates hold:

Proof. We use again an contradiction argument to prove this statement. Suppose, that

then we have

For the left term, we have

and because $k < \ell$ this implies

For the right term in (24) we have

and again because $k < \ell$ it follows

Now, from a binomial formula, we know that $-2ab \geq -(a^2 + b^2)$ for real numbers $a$ and $b$. This leads to the estimate

which is a contradiction to (24). Thus the lemma is proven.

With these auxiliary lemmas we can state the following convexity Theorem. The result is similar to Lemma 3.3 in [20]. But for that result, the authors only consider the conservation of mass (2), not the conservation of momentum (3). For the model considering both, conservation of mass and momentum, they only state, that the set of feasible loads in general is non-convex (see Lemma 4.1 in [20]).

Theorem 3.4. Let pressure bounds $p^{+, \min}, p^{+, \max} \in \mathbb{R}^{n+1}$ with $p_i^{\max} \geq p_j^{\min}$ (for all $i, j = 0, \cdots, n$) be given. Then, for a linear network graph with one single entry and no compressor edges, the set of feasible loads is convex.

Proof. First note, that if the feasible set is empty or contains one element, it is convex. Otherwise, it contains at least two elements. In particular we will use the representation of the feasible set $M$ of Theorem 2.3. The formulation $(-\mathbb{1}^T b, b) \in \mathbb{R}_- \times \mathbb{R}^n_+$ is equivalent to $\mathbb{1}^T b^+ = 0$ for graphs with one single entry. Consider $b^+, \beta^+ \in M$. It holds $\mathbb{1}^T b^+ = 0$, $\mathbb{1}^T \beta^+ = 0$ and all inequalities in Theorem 2.3 are fulfilled. We have to show, that for a $\lambda \in (0, 1)$, the load vector $\lambda b^+ + (1-\lambda) \beta^+$ is also in $M$. First we have

Now we have to show, that the following inequalities (see (7)) for convex combinations of loads for $k, \ell = 1, \cdots, n$ hold:

To show the first inequality in (26) we define $c_{1, k} : = (p_k^{\max})^2 - (p_0^{\min})^2$ and $t_{1, k}(b, \beta) : = c_{1, k} + g_k(\lambda b + (1-\lambda)\beta)$ and we want to show $t_{1, k}(b, \beta) \geq 0$. With Lemma 3.1 it follows

Because $b$ and $\beta$ are feasible, we can use the first inequality in Theorem 2.3 to get the estimate

Now we need an estimate of the form $\Sigma_k(b, \beta) \geq (-c_{1, k})$, but this is not true in general. Here we use the restriction on the pressure bounds. Because $p_i^{\max} \geq p_j^{\min}$ for all $i, j = 0, \cdots, n$, it follows $c_{1, k} \geq 0$ for all $k = 1, \cdots, n$. And because $\Sigma_k(b, \beta) \geq 0$, we have

which implies the first inequality in (26).

We define $c_{2, k} : = (p_0^{\max})^2 - (p_k^{\min})^2$, $t_{2, k}(b, \beta) : = c_{2, k} - g_k(\lambda b + (1-\lambda) \beta)$ and we use again Lemma 3.1 and get

Next because $b$ and $\beta$ are feasible, we use the second inequality in Theorem 2.3 to get the estimate

Now we use the result of Lemma 3.2 to get either

Using again the second inequality in Theorem 2.3, both cases lead to

which is obviously non-negative and thus, we have shown the second inequality in (26). We define $c_{3, k, \ell} : = (p_k^{\max})^2 - (p_\ell^{\min})^2$ and $t_{3, k, \ell}(b, \beta) : = c_{3, k, \ell} + g_k(\lambda b + (1-\lambda)\beta) - g_\ell(\lambda b + (1-\lambda)\beta)$. In the case $k = \ell$ it follows directly $t_{3, k, \ell}(b, \beta) \geq 0$ (because of $c_{3, k, \ell} \geq 0$ due to assumptions). In the case $k \neq \ell$, with Lemma 3.1 it follows

Again because $b$ and $\beta$ are feasible, we use the third inequality in Theorem 2.3 to get

If $\ell < k$, it follows $\Sigma_\ell(b, \beta) < \Sigma_k(b, \beta)$ and thus every term is positive, which implies $t_{3, k, \ell}(b, \beta) \geq 0$. If $\ell > k$, we use the statement of Lemma 3.3. With this, it follows either

In both cases, we can use the third inequality in Theorem 2.3. It follows

which is non-negative. Finally we have shown $t_{3, k, \ell} \geq 0$, so the load vector $(\lambda b + (1-\lambda) \beta)$ is also feasible and thus the set of feasible loads is convex.

Remark 1. The assumption $p_i^{\max} \geq p_j^{\min}$ is not a natural restriction, because otherwise, the trivial solution is no element of the set of feasible loads. We will assume this later also to show star-shapedness. It is interesting to see, that this assumption also occurs in the problem of maximizing booked capacities on stationary tree-structured graphs, in verifying constraint qualifications for certain problems (see Theorem 1 in [15]).

We illustrate the results of Theorem 3.4 in the following examples.

Example 1: Consider the linear graph shown in Figure 4.

We consider three different pressure bounds to show the results of Theorem 3.4. In the first case, we consider $(p^{+, \min})_{a} = [2, 1, 1]^T$ and $(p^{+, \max})_{a} = [2, 2, 2]^T$ with the feasible set $M_{a}$, in the second case we consider $(p^{+, \min})_{b} = [2, 1, 1]^T$ and $(p^{+, \max})_{b} = [3, 2, 2]^T$ with feasible set $M_{b}$ and in the third case, we consider $(p^{+, \min})_{c} = [2.5, 1.5, 1]^T$ and $(p^{+, \max})_{c} = [3, 2.5, 2]^T$ with feasible set $M_{c}$. Together with $\phi_1 = \phi_2 = 1$, we get from Theorem 2.3 the feasible sets

The feasible sets are shown in Figure 5.

One can see, that the feasible sets of case $(a)$ and $(b)$ are convex and the feasible set of case $(c)$ is not. This fits to the result of Theorem 3.4 because in case $(a)$ and $(b)$, the condition $p_i^{+, \max} \geq p_j^{+, \min}$ is fulfilled, but not in case $(c)$.

Example 2: Consider the linear graph shown in Figure 6.

We consider two different pressure bounds to show the results of Theorem 3.4. In the first case, we consider $(p^{+, \min})_{a} = [1, 1, 1, 1]^T$, $(p^{+, \max})_{a} = [3, 3, 3, 3]^T$ and in the second case, we consider $(p^{+, \min})_{b} = [2.5, 2, 1.5, 1]^T$, $(p^{+, \max})_{b} = [3, 2.5, 2, 1.5]^T$. With $\phi_1 = \phi_2 = \phi_3 = 1$, Theorem 2.3 implies

The feasible sets are shown in Figure 7 and Figure 8.

In Figure 7 one can see, that the feasible set $M_{a}$ is convex. In the view from above one can see, that the picture is similar to the picture in the two-dimensional case Figure 5 a). In Figure 8, the feasible set is obviously not convex. This is because the condition $p_i^{\min} \leq p_j^{\max}$ is not fulfilled for every $i, j = 1, \cdots, n$. This feasible set is similar to the set in the two dimensional example in Figure 5 (c).

Before we give a statement about convexity in a graph with compressor edges, we shortly explain the idea how to treat graphs with compressor edges. The main idea is to remove the compressor edges from the graph, but still keep the properties of the compressors. That means we separate a graph with $m \in \mathbb{N}$ compressor edges to $m+1$ subgraphs, which are not connected, but which interact with each other. We numerate the subgraphs exactly like we numerate the nodes inside a subgraph (with breadth-first search or depth-first search). This is explained in detail in [12], Section 3. We formulate an auxiliary lemma for the sum $\Sigma_{k^*, i}(b)$ (defined in (19)) first. For an easier notation, we can use the fact, that the graph is linear. The notation in [12] is motivated by paths in tree-structured graphs, but for linear graphs, there exists only one path in the graph. So for the next lemma, we state that $g_{i, j}(b_i)$ is the $j$-th component of the pressure loss function $g$ for the $i$-th subgraph and $b_i$ is the load vector (without the first component) for the $i$-th subgraph. Further, $n_i+1$ is the number of nodes in the $i$-th subgraph, numbered from $0$ to $n_k$. Analogously, $\phi_{i, j}$ belongs to the edge with number $j$ in the $i$-th subgraph.

Lemma 3.5. For vectors $b, \beta \in \mathbb{R}^n_{\geq 0}$, constants $\phi_k \in \mathbb{R}_{\geq 0}$ ($i = 1, \cdots, n$) and $\lambda \in (0, 1)$, it holds (for $i = 1, \cdots, n$):

The sum $\Sigma_{k^*, i}(\cdot)$ is defined in (19) and $\Sigma_{k^*, i}(b, \beta)$ is defined as:

Note, that for $i, j \in \{1, \cdots, m+1\}$ the index $k^*$ is defined as the largest index of all subgraphs, the paths from the root to the $i$-th and to the $j$-th subgraph pass (see [12] for details). This index does not influence our computation, so we do not go into detail here.

Proof of Lemma 3.5. For $i \in \{1, \cdots, m+1\}$ and $b, \beta \in M$ we have

Then from Lemma 3.1 it follows

which can be written as

With the definition of the sum in (19) it follows

and thus the lemma is proven.

For the next convexity theorem, we need a second auxiliary lemma.

Lemma 3.6. With the setting of Lemma 3.5, at least one of the following estimates hold:

Proof. The proof is similar to the proof of Lemma 3.2.

With these results, we can formulate a Theorem about convexity in general linear graphs.

Theorem 3.7. Consider a linear graph $G = (\mathcal{V}, \mathcal{E})$ with compressor edges. Let pressure bounds $p^{+, \min}, p^{+, \max} \in \mathbb{R}^{n+1}$ with $p_i^{\max} \geq p_j^{\min}$ (for all $i = 0, \cdots, n$), constants $\phi_i \in \mathbb{R}^n_{\geq 0}$ ($i = 1, \cdots, n$) and controls $u_i$ (for $i = 1, \cdots, m$) be given. Additionally, let

hold for $i = 2, \cdots, m+1$. Then the set of feasible loads for a linear graph with compressor edges is convex.

Proof. The proof is similar to the proof of Theorem 3.4. First mention, that if the set of feasible loads is empty or contains only one element, it is convex. Otherwise, let $b^+, \beta^+ \in M$ (let $M$ be the set of feasible loads), then $b, \beta \in \mathbb{R}^n_{\geq 0}$. For $\lambda \in (0, 1)$, (25) holds. Also the inequalities (8)-(10) hold for the load vector $(\lambda b + (1-\lambda) \beta)$ for every subgraph because of Theorem 3.4. We have to show, that inequalities (11)-(18) hold for the convex combination $(\lambda b + (1-\lambda) \beta)$. For indices $i, j \in \{1, \cdots, m+1\}$ with $i < j$, the subgraph $G_i$ is on the path from $G_1$ to $G_j$, so the index $k^*$ is equal to $i$ and thus the sum $\Sigma_{k^*, i}(\cdot)$ is zero for the inequalities (11) - (18), but the sum $\Sigma_{k^*, j}(\cdot)$ not. Define

with $\Pi_{k^*, i}$ defined in (20). Because $k^* = i$, it is $\Pi_{k^*, i} = 1$ and with (27), it follows

With the definition of $\Pi_{k^*, j}$ (see 20), we have

Thus we have $c_{4, i, j} \geq 0$. We define

Then we can use Lemma 3.5 to get

Now we use inequality (11) itself for the feasible vectors $b$ and $\beta$ and get the estimate

and from this it follows

Because $c_{4, i, j} \geq 0$ and $\Sigma_{k^*, j}(b, \beta) \geq 0$, it follows $t_{4, i, j}(b, \beta) \geq 0$ and thus, inequality (11) holds for $(\lambda b + (1-\lambda) \beta)$. For the next inequality, we define

and

Because $\Pi_{k^*, i} = 1$ and $\Pi_{k^*, j} \geq 1$, we have $c_{5, i, j} \geq 0$. We use Lemma 3.5 to get

Then, we use the inequality (12) itself for feasible $b$ and $\beta$ and get

from which it follows

Now we use Lemma 3.6. It follows either

In both cases, we can use again inequality (12) to get

which is obviously non-negative. Thus inequality (12) holds for $(\lambda b + (1-\lambda) \beta)$. The proof for the inequalities (13), (15) and (17) works analogously to the proof of (11) and the proof of (14), (16) and (18) works analogously to the proof of (12). Then every inequality of Theorem 2.4 holds for the load vector $(\lambda b + (1-\lambda) \beta)$ and thus the theorem is proven.

Remark 2. The extra condition $(p_i^{\max})^2 \geq u_{i-1} (p_{i-1}^{\min})^2$ of Theorem 3.7 is sufficient for convexity, but not necessary. The feasible set of a linear graph with compressor edges can also be convex even if the extra condition is not fulfilled.

The following example illustrates the results.

Example 3. : Consider the minimal graph with a compressor edge shown in Figure 9.

We consider two different controls for pressure bounds $(p^{+, \min}) = [1, 1, 1, 1]^T$ and $(p^{+, \max}) = [3, 2, 2, 1.5]^T$ to show the results to show the results of Theorem 3.7. In the first case, we consider $u_{a} = 2$ and in the second case, we consider $u_{b} = 4$. Then from Theorem 2.4 we get

The feasible sets are shown in Figure 10 and Figure 11.

In both cases, one can see that the feasible sets are convex. Even if in case $(b)$ the condition $(p_{i, 0}^{\max})^2 \geq u_{i-1} (p_{i-1, 0}^{\max})^2$ is not fulfilled. But this is stated in Remark 2. The condition $p_i^{\max} \geq p_j^{\min}$ is also not fulfilled in case $(b)$, this leads to the case, that the vector $\mathbb{0}_3 \notin M_{b}$.

4.   Star-shapedness of the feasible set in tree-structured graphs

In this section, we will show that for tree-structured graphs, the feasible set is star-shaped to some special points. Like it is mentioned in Section 1, computing the intervals, in which a line through a fixed point intersects the set of feasible loads, is much easier if one knows that the set is star-shaped to this point. First we show the following auxiliary lemma.

Lemma 4.1. Let $G = (\mathcal{V}, \mathcal{E})$ be a tree-structured graph without compressor edges. For $b \in \mathbb{R}^n$ and $\lambda \in (0, 1)$, the pressure loss function defined in (6) is:

Proof. Consider $b \in \mathbb{R}^n$ and $\lambda \in (0, 1)$. We have

since $\lambda$ is non-negative.

Now we formulate a theorem about when the set of feasible loads is star-shaped. This result is equal to {Lemma 4.2} in [20]. However, we state this theorem here because we prove it differently and we will use the proof for a similar result for networks with compressor stations later. As mentioned in Section 1, the main difference between the models is the modeling of the compressor stations.

Theorem 4.2. Let pressure bounds $p^{+, \min}, p^{+, \max} \in \mathbb{R}^{n+1}$ with $p_i^{\max} \geq p_j^{\min}$ (for all $i, j = 0, \cdots, n$) be given. If the network graph is tree-structured with one input node and does not contain compressor edges, then the set of feasible loads $M$ is star-shaped with respect to the point $\mathbb{0} \in \mathbb{R}^{n+1}$.

Proof. Let $M$ be the set of feasible loads. To show this result, we have to show that for a feasible load vector $b \in M \subseteq \mathbb{R}^n_{\geq 0}$, the vector $\lambda b$ is also feasible for $\lambda \in [0, 1]$. That means the vector $\lambda b$ fulfills the inequalities in Theorem 2.3 (for $b = \mathbb{0}$, it is $\lambda b = 0$). First mention, that $\mathbb{0}$ is feasible. If $b = 0$, it follows $g(b) = 0$ and because $p_i^{\max} \geq p_j^{\min}$ for all $i, j = 0, \cdots, n$, it follows $p_i^{\max} - p_j^{\min} \geq 0$ for all $i, j = 0, \cdots, n$. Thus, all inequalities in Theorem 2.3 hold and $\mathbb{0}$ is feasible. So if the set of feasible loads contains only one element, the statement of Theorem 4.2 is obviously true. Else, consider $b \in M\backslash \{ \mathbb{0} \}$. For $i \in 1, \cdots, n$, we define

and

Then with Lemma 4.1 we have

Because $b$ is feasible, we can use the first inequality in Theorem 2.3. It follows

Because $c_{1, i} \geq 0$ (due to $p_i^{\max} \geq p_j^{\min}$) and $\lambda \in [0, 1]$, it follows $t_{1, i}(b) \geq 0$ and thus the first inequality in Theorem 2.3 holds. Next define

Then due to Lemma 4.1 we have

We use the second inequality of Theorem 2.3 and get

and it follows $t_{1, i}(b) \geq 0$. Thus, the second inequality in Theorem 2.3 holds. Last, we define

With Lemma 4.1 it follows

We use the third inequality in Theorem 2.3, we have

so it follows $t_{3, i, j}(b) \geq 0$. Thus all inequalities of Theorem 2.3 are fulfilled for $(\lambda b)$ and the proof is complete.

With the next example, we illustrate why we need the statement $p^{+, \max} \geq p^{+, \min}$.

Example 4: Consider the minimal tree shown in Figure 12.

We consider the two cases $(p^{+, \min})_{a} = [2, 1, 1]^T$, $(p^{+, \max})_{a} = [3, 2, 2]^T$ with the feasible set $M_{a)}$ and $(p^{+, \min})_{b} = [2.5, 1.5, 1]^T$, $(p^{+, \max})_{b} = [3, 2.5, 2]^T$ with the feasible set $M_{b)}$. Then, for $\phi_1 = \phi_2$, we get from Theorem 2.3

The feasible sets are shown in Figure 13.

One can see, that in case $(a)$, the set of feasible loads is star-shaped to the point $\mathbb{0} \in \mathbb{R}^2$, in case $(b)$ this is not true. This is because the condition for the pressure bounds does not hold. But the set in case $(b)$ still has the special property that the intersection of every line through the root and the feasible set is convex. This property is stated later in Lemma 4.4.

Example 5: Consider the minimal tree shown in Figure 14.

We consider the two cases $p_{a}^{\min} = [1, 1, 1, 1]^T$, $p_{a}^{\max} = [3, 2, 2, 2]^T$ with the feasible set $M_{a}$ and $p_{b}^{\min} = [2, 1, 1, 1]^T$, $p_{b}^{\max} = [3, 2, 2, 1.5]^T$ with the feasible set $M_{b}$. From Theorem 2.3 it follows

The feasible sets are shown in Figure 15 and Figure 16.

As in Example 4, the feasible set in case $(a)$ is star-shaped to the point $\mathbb{0} \in \mathbb{R}^3$, the set in case $(b)$ is not. But again, the intersection of every line through the root and the set of feasible loads is convex (see Lemma 4.4).

Next we show, that the statement of Theorem 4.2 also holds for tree-structured graphs with compressor edges. This result is not stated in [20].

Theorem 4.3. Let controls $u_i \in \mathbb{R}$ ($i = 1, \cdots, m$) be given. Let $p_i^{\max} \geq p_j^{\min}$ hold for every subgraph and let (27) hold, i.e. $(p_{i, 0}^{\max})^2 \geq u_{i-1} (p_{i-1, 0}^{\max})^2$. Then the set of feasible loads of a tree-structured graph with compressor edges is star-shaped to the point $\mathbb{0} \in \mathbb{R}^n$.

Proof. Consider $b^+ \in \mathbb{R}^{n+1}$ and $\lambda \in [0, 1]$. We have to show, that the inequalities (8)-(18) hold for the load vector $\lambda b$. Theorem 4.2 we know, that (8)-(10) are fulfilled for every subgraph. For the sum defined in (19) we know from Lemma 4.1 ($i \in \{1, \cdots, n\}$)

The proof follows the structure of the proof of Theorem 4.2. We set

and

Then with (29) we have

and

Because $b$ is feasible, we can use inequality (11) resp. (12) to get the estimates

and

From Theorem 3.7 we know that $c_{4, i, j}, c_{5, i, j} \geq 0$ because of the condition $(p_{i, 0}^{\max})^2 \geq u_{i-1} (p_{i-1, 0}^{\max})^2$. So both, $t_{4, i, j}(b)$ and $t_{5, i, j}(b)$ are non-negative due to our assumptions. Thus inequality (11) and (12) hold for $(\lambda b)$. All other inequalities can be shown analogously. That means the feasible set for tree-structured graphs with compressor edges is star-shaped to the point $\mathbb{0}_{n+1}$ and thus the proof is complete.

The last statement in this section is motivated by case b) in Example 4 (see Figure 13). Because we want to know, when the intersection of a line and the set of feasible loads is convex, we formulate the following lemma.

Lemma 4.4. Let $M \subseteq \mathbb{R}^n$ be the set of feasible loads of a tree-structured graph. Then, for a point $b \in \mathbb{R}^n$, the set $L : = \{ \beta \in M \vert \beta = \lambda b\ (\lambda \in [0, 1]) \}$ is convex.

Remark 3. The statement of Lemma 4.4 is a generalized star-shapedness property with respect to the point $\mathbb{0} \in \mathbb{R}^n$. A set $S$ is star-shaped with respect to a point $s$ if $s \in S$ and if for every direction $d \in \mathbb{R}^n$, the line from $s$ in direction $d$ has a convex intersection with the set $S$. If $S$ is generalized star-shaped to the point $s$, the same property holds for $s \notin S$, so here the point $s$ need not to be in the set $S$. For the computation in the spheric-radial decomposition, this situation is as useful as the classical star-shapedness property.

Proof of Lemma 4.4. First, if the set $L$ is empty or contains only one element, it is convex. We only consider the case $b \in \mathbb{R}^n_{\geq 0}$, because otherwise, the set $L$ contains at most one element (the point $\mathbb{0} \in \mathbb{R}^n$). This is, because all load vectors (without the first component) are non-negative due to our network graph has only one inflow node. We separate the proof in two parts. In the first part, we prove Lemma 4.4 for tree-structured networks without compressor edges, in the second part we prove it for general tree-structured networks.

Part I: Proof for trees without compressor edges: We first prove this lemma for trees without compressor edges. Consider $b \in \mathbb{R}^n_{\geq 0}$ and assume, that the feasible set contains at least two elements. Consider $\beta_1, \beta_2 \in M$ with $\beta_1 = \lambda_1 b$ and $\beta_2 = \lambda_2 b$ ($0 \leq \lambda_1 < \lambda_2 \leq 1$). Then, the inequalities in Theorem 2.3 hold for $\beta_1$ and $\beta_2$. We have to show, that these inequalities also hold for $\beta = \lambda b$ for all $\lambda \in [\lambda_1, \lambda_2]$. The first inequality for $\beta_1$ is

which is equal to

From Lemma 4.1, it follows

and this also holds for every $\lambda \geq \lambda_1$, especially for $\lambda \in [\lambda_1, \lambda_2]$. The second inequality for $\beta_2$ is

This is equal to

and due to Lemma 4.1 it follows

This also holds for $\lambda \leq \lambda_2$, especially for every $\lambda \in [\lambda_1, \lambda_2]$. The third inequality in Theorem 2.3 is

The term on the right in both cases has the same sign, because if $g_k(\beta_1) - g_\ell(\beta_1) < 0$, then due to Lemma 4.1 this is equal to $\lambda_1^2 (g_k(b) - g_\ell(b)) < 0$ and the sign is independent of $\lambda_1$. Thus this also holds for $\beta_2 = \lambda_2 b$. So if $g_k(b) - g_\ell(b) \geq 0$, we follow the argumentation of the first inequality, we have shown here. And if $g_k(b) - g_\ell(b) < 0$, we follow the argumentation of the second inequality, we have shown here. Thus, all inequalities in Theorem 2.3 hold for $\beta = \lambda b$ for all $\lambda \in [\lambda_1, \lambda_2]$ and the lemma is proven for trees without compressor stations.

Part II: Proof for general trees: Now we prove this lemma for general trees with compressor edges. This part of the proof follows the structure of Part I. Consider $b \in \mathbb{R}^n_{\geq 0}$ and $\beta_1, \beta_2 \in M$ with $\beta_1 = \lambda_1 b$ and $\beta_2 = \lambda_2 b$ ($0 \leq \lambda_1 < \lambda_2 \leq 1$). We have to show, that all inequalities in Theorem 2.4 hold for $\beta = \lambda b$ with $\lambda \in [\lambda_1, \lambda_2]$. The inequalities (8) - (10) follow directly from the first part of the proof. Consider inequality (11):

We follow the argumentation of the third inequality in Part I of the proof. The term on the right is either negative or non-negative. If it is non-negative, we follow the argumentation of the first inequality in Part I, if it is negative, we follow the argumentation of the second inequality in Part I. We can use the same arguments to show the inequalities (12) - (18) for $\beta = \lambda b$ with $\lambda \in [\lambda_1, \lambda_2]$. Thus, all inequalities in Theorem 2.4 are fulfilled for $\beta = \lambda b$ with $\lambda \in [\lambda_1, \lambda_2]$ and the set $L$ is convex. So Lemma 4.4 is proven.

The statement of Lemma 4.4 is mentioned and illustrated in Example 4 and Example 5. This is listed here, because it also belongs to the problems mentioned in Section 1.

5.   Conclusion

In this paper we have shown that the structure of the set of feasible loads in the context of stationary gas networks mainly depends on the topology of the network graphs. In the easiest case, if the network graph is linear, convexity of the set of feasible loads can be shown with very weak assumptions. If the network graph is more complex, but still does not contain circles, we have shown, that under weak assumptions, the feasible set is always star-shaped with respect to the point $\mathbb{0} \in \mathbb{R}^n$. For even weaker assumptions, we introduced the generalized star-shapedness (see Lemma 4.4), which is also very useful for the computation in the spheric-radial decomposition.

In [9], also the case of a network, which is a cycle, is considered. Then, the representation of the set of feasible loads shown in Theorem 2.3 is completed with an equality. For this framework, one can also show, that the set of feasible loads is star-shaped to the point $\mathbb{0} \in \mathbb{R}^n$. Convexity in this case does not hold, not even in the simplest case of a network cycle of three nodes (see [9], {Section 5}).

As mentioned in Section 1, knowing the structure of the set of feasible loads helps to analyze this model for random load vectors as it is done in [9] and [12]. There, the authors use the spheric-radial decomposition to handle the probabilistic load vectors. This leads to optimization problems with probabilistic constrains or chance constraints (see [17]). The main part of using the spheric-radial decomposition (see Theorem 1.1) is to compute the integral in (1). If one knows e.g. that the feasible set is convex, this integral is a lot easier to compute and thus, this simplifies the optimization done in [12].

6.   Conflict of interests

The authors declare that there is no conflict of interest regarding the publication of this paper.

Acknowledgments

This work was supported by DFG in the framework of the Collaborative Research Centre CRC/Transregio 154, Mathematical Modelling, Simulation and Optimization Using the Example of Gas Networks, project C03.