Duality for extended infinite monotropic optimization problems

Abstract

We establish necessary and sufficient conditions for strong duality of extended monotropic optimization problems with possibly infinite sum of separable functions. The results are applied to a minimization problem of the infinite sum of proper convex functions. We consider a truncation method for duality and obtain the zero duality gap by using only dual variable of finite support. An application to minimum cost flow problems in infinite networks is also discussed.

1 Introduction

The classical monotropic programming problem, introduced and analyzed by Rockafellar [16], is formulated as follows

$$\begin{aligned}&\mathrm{minimize} \; \; \sum _{i=1}^m f_i(x_i) \\&\mathrm{subject \; to} x\in S, \end{aligned}$$

where $x=(x_1, ... , x_m)\in {\mathbb {R}}^{m}$, $f_i, i=1, ... , m$ are convex functions on ${\mathbb {R}}$ and S is a subspace of ${\mathbb {R}}^m$. Monotropic problems have originally arisen from minimum cost network flow problems [15, 17] and form a particular class of separable convex programming with a lot of applications (see [2, 3, 5, 6, 8] and references given therein). Many duality results that are important in development of computing methods have been recently obtained in [2, 3, 6, 8], in which considerable effort focuses on countably infinite monotropic problems. Optimization problems involving a countably infinite number of variables and a countably infinite number of constraints, are often met in infinite dimensional linear programming, infinite networks and hypernetworks, infinite-horizon planning, Markov decision processes, robust optimization and many other fields ([10, 17,18,19,20]). While under relatively mild conditions, zero duality gap does hold for monotropic problems in finite dimension (Theorem 11D [16]), it is not the case in the infinite dimension. To the best of our knowledge, [6] is the first work that carefully analyzes Fenchel duality for generalized monotropic problems with infinite sums in the framework of proper convex and lower semicontinuous functions. They obtain strong duality under a constraint qualification on the closedness of the sum of the conjugates of the convex functions and generalize the results of finite sums of [3, 5]. Another method has been recently utilized in [8] to establish zero duality gap and strong duality for infinite monotropic problems over intervals of real numbers by means of a suitable sequence of finite monotropic problems. According to this method, the original infinite monotropic problem is truncated into finite ones. An optimal solution of the original problem is obtained as limit of a sequence of optimal solutions of truncated problems, and duality relations are derived from the already acquired duality relations of the finite truncated ones. The main difference between the approach by [6] and the one by [8] is the choice of the dual space. In [6] (see also [9]) the dual variable is taken from the space of sequences with finite support (sequences with only finitely many nonzero terms), while [8] uses sequences with possibly infinite support, which seems to fit better with practical models in infinite horizon planning and infinite networks.

The purpose of our study is to develop a general framework for duality of monotropic optimization problems in which the objective functions are infinite sums of functions. We employ the dual space introduced in [6] to construct dual problems and to establish strong duality for both the primal and the dual problems. With regard to the results of [6] we improve them in the sense that we give both necessary and sufficient conditions for strong duality and show that one of the conditions imposed in [6] on the epigraph of the conjugate function of the objective function can be removed. Besides usual strong duality of type inf(P)= max(D), we also charaterize reverse duality of type min(P)=sup(D). Furthermore, we use the truncation method of [8] to our problem and generalize the main result of [8] on zero duality gap. An interesting outcome of our analysis is the fact that under the same conditions, the dual problem using dual variable from the space of sequences with finite support yields the same zero duality gap as the dual problem using dual variable from the space of sequences with infinite support. This fact is important in computation, especially in solving minimum cost flow problems on infinite networks as described in [8].

The paper is structured as follows. In Sect. 2 we summarize some properties of summable families of real numbers and functions. In Sect. 3 we give a formula to compute the conjugate of the infinite sum of separable functions. Section 4 is devoted to the infinite sum of the epigraphs of separable functions and of their conjugates. Section 5 is the core of our paper where we present a dual problem of the infinite monotropic problem and give regularity conditions for strong duality and reverse strong duality to hold. The results of this section improve those obtained in [6]. We explain also that some regularity conditions of [6] can be removed. In Sect. 6 we apply the results of Sect. 5 to the problem of minimizing an infinite sum of convex functions by reformulating it in form of monotropic problem. Section 7 is devoted to extension of the truncation method of [8] to a more general space setting. In a particular model of [8], although the dual space we are considering is different from the one of [8], we obtain the same dual problems for truncated problems. This enables us to derive a zero duality gap by using dual variable of sequences with finite support instead of sequences with infinite support. Due to a result of [1] on representation of positive linear functionals by finite support positive vectors, we establish equivalence between the algebraic dual of a conic optimization problem and the dual developed in our study. In the final section we consider a minimum cost flow problem in infinite networks. By using a translation of variable, we express the problem in form of infinite monotropic problem. We apply the results obtained in Sect. 7 on zero duality gap to this problem and address a discussion on differences between our approach and the approach of [8, 14].

2 Preliminaries

Throughout this paper ${\mathbb {R}}_\infty := {\mathbb {R}}\cup \{+\infty \}$, $\overline{\mathbb {R}} := {\mathbb {R}}\cup \{\pm \infty \}$, I is a nonempty index set and $\mathcal {I}$ is the set of all nonempty finite subsets of I, partially ordered by inclusion.

Let $\{t_i: i\in I\}$ (or $(t_i)_i$ for short) be a family from ${\mathbb {R}}_\infty$. We define the sum of this family to be the unconditional limit of the finite sums $\sum _{i\in J} t_i, J\in {\mathcal {I}}$ when it exists in $\overline{\mathbb {R}}$ and denote it by $\sum _{i\in I} t_i$. The following remarks will be used in what follows.

Remark 1

For $\{t_i: i\in I\} \subset [0, +\infty ]$ the sum $\sum _{i\in I} t_i$ exists and

$$\begin{aligned} 0\le \sum _{i\in I} t_i = \sup _{I\in {\mathcal {I}}} \sum _{i\in I} t_i\le +\infty . \end{aligned}$$

Remark 2

If $\{t_i: i\in I\} \subset {\mathbb {R}}$ and $\sum _{i\in I} t_i \le t$ for some $t\in {\mathbb {R}}$, then there is $\{s_i: i\in I\} \subset {\mathbb {R}}$ such that $t_i \le s_i$ for all $i\in I$ and $\sum _{i\in I} s_i =t$.

Let $(S_i)_{i}$ be a family of nonempty sets and let $h_i: S_i \rightarrow {\mathbb {R}}, i\in I$ be given. The following remark is very closed to Lemma A.2 [6] and its proof is omitted.

Remark 3

If for every $(x_i)_{i} \in S:= \displaystyle \prod \nolimits _{i\in I} S_i$, the infinite sum $\sum _{i\in I} h_i(x_i)$ exists in $\overline{\mathbb {R}}$, and is not identically equal to $-\infty$, then

$$\begin{aligned} -\infty < \sup _{(x_i)_{i}\in S} \sum _{i\in I} h_i(x_i) = \sum _{i\in I} \sup _{x_i\in S_i} h_i(x_i) \le +\infty . \end{aligned}$$

Let X be a separated locally convex space and let $h: X\rightarrow \overline{\mathbb {R}}$. We recall that the effective domain of h is the set $\mathrm{dom} h:=\{x\in X: h(x) < +\infty \}$. The function h is said to be proper if it does not take the value $-\infty$ and its effective domain is nonempty. The conjugate $h^*$ of h is defined on the topological dual $X^*$ of X by the formula $h^*(x^*):= \sup _{x\in X} (x^*(x) - h(x))\;\; \mathrm{for\; } x^*\in X^*.$ The biconjugate of h is the conjugate of $h^*$ and defined on X by $h^{**}(x):= \sup _{x^*\in X^*} (x^*(x) - h^*(x^*))\;\; \mathrm{for \;} x\in X.$ We know that $h= h^{**}$ if and only if either h is identically equal to $+\infty$, or to $-\infty$, or h is proper convex and lower semicontinuous on X. The set of proper convex and lower semicontinuous functions on X is sometimes denoted by $\Gamma (X)$, and the set of nonnegative proper convex and lower semicontinuous is denoted by $\Gamma _+(X)$.

3 Conjugate of the infinite sum of separable functions

Let $(X_i, X^*_i), i\in I$ be dual pairs of separated locally convex spaces over reals with coupling functions $\langle . , .\rangle _i, i\in I$. We denote by ${\mathcal {X}}$ the product space $\displaystyle \prod \nolimits _{i\in I} X_i$ equipped with the product topology. According to Theorem 4.3 [21], the topological dual of ${\mathcal {X}}$ is the space ${\mathcal {X}}^*$ consisting of all families $(x^*_i)_i\in \displaystyle \prod \nolimits _{i\in I} X_i^*$ which may have only a finite number of nonzero terms (such families are said to be of finite support). The space ${\mathcal {X}}^*$ is algebraically isomorphic to, hence sometimes identified with the direct sum of $X^*_i, i\in I$. The topology on ${\mathcal {X}}^*$ is given by the w*-topology $\sigma ({\mathcal {X}}^*, {\mathcal {X}})$ generated by the coupling function

$$\begin{aligned} \langle (x_i^*)_i, (x_i)_i\rangle := \sum _{i\in I} \langle x_i^*, x_i\rangle _i\; \; \mathrm{for \; } (x_i)_i\in {\mathcal {X}}, (x_i^*)_i\in {\mathcal {X}}^*. \end{aligned}$$

Note that the sum on the right hand side above is well defined as it is a finite sum because all $x^*_i, i\in I$ are zero except for finitely many terms. The canonical projection $p_j$ from ${\mathcal {X}}$ onto $X_j$ is given by

$$\begin{aligned} p_j((x_i)_i):= x_j \;\; \mathrm{for }\; (x_i)_i\in {\mathcal {X}}, \end{aligned}$$

and its transposed $\ell _j: X_j^*\rightarrow {\mathcal {X}}^*$ by

$$\begin{aligned} \ell _j(x_j^*)= (x^*_i)_i \; \mathrm{for }\; x^*_j\in X^*_j, \end{aligned}$$

where $x_i^*= x^*_j$ if $i=j$ and $x_i^*= 0_{X_i^*}$ if $i\not =j$. An extension of $\ell _j$ is $L_j: X_j^*\times {\mathbb {R}}\rightarrow {\mathcal {X}}^*\times {\mathbb {R}}$ defined by

$$\begin{aligned} L_j(x_j^*, r) := (\ell _j(x^*_j), r)\; \mathrm{for }\; x^*_j\in X^*_j, r\in {\mathbb {R}}. \end{aligned}$$

Now we consider a family $\{f_i: X_i \rightarrow {\mathbb {R}}_\infty \}_{i\in I}$ of proper functions and assume the following hypothesis

• (H) For every $(x_i)_i\in {\mathcal {X}}$, $f((x_i)_i):= \sum _{i\in I} f_i(x_i)$ exists in $\overline{\mathbb {R}}$, and $\mathrm{dom} f\not =\emptyset .$

By using the projection $p_i$, each function $f_i$ on $X_i$ can be extended to a function $\hat{f}_i$ on ${\mathcal {X}}$ by $\hat{f}_i := f_i\circ p_i$, and so we can express f as an infinite sum of functions on ${\mathcal {X}}$ by $f= \sum _{i\in I} \hat{f}_i.$ The next result summarizes some relationships between the conjugate functions $f_i^*$, $\hat{f}^*_i$ and $f^*$.

Proposition 1

For every $(x_i^*)_i\in {\mathcal {X}}^*$ and $j\in I$ one has

$$\begin{aligned} \hat{f}^*_j ((x_i^*)_i)= \left\{ \begin{array}{ll} f^*_j(x^*_j) &{} \; \mathrm{if \; } \ell _j(x^*_j)= (x_i^*)_i\\ +\infty &{} \;\mathrm{else.} \end{array} \right. \end{aligned}$$

(1)

In particular $\mathrm{epi\; } \hat{f}^*_j = L_j (\mathrm{epi\; } f^*_j).$ Moreover, under (H), the sum $\sum _{i\in I} f_i^*(x_i^*)$ exists in ${\mathbb {R}}_\infty$ and

$$\begin{aligned} -\infty < f^*((x_i^*)_i) = \sum _{i\in I} f_i^*(x_i^*) \le +\infty . \end{aligned}$$

(2)

If, in addition, $f_i, i\in I$ are proper convex and lower semicontinuous and $\mathrm{dom}\; f^*\not =\emptyset$, then f is proper convex and lower semicontinuous too.

Proof

The formula (1) and equality $\mathrm{epi\; } \hat{f}^*_j = L_j (\mathrm{epi\; } f^*_j)$ follow immediately from the definitions of $\hat{f}_j, \ell _j$ and $L_j$ (see also [6] (20)). Furthermore, since dom$f \subseteq \prod _{i\in I} \mathrm{dom} f_i$, we have

$$\begin{aligned} f^*((x^*_i)_i)= \sup _{(x_i)_i\in \prod _{i\in I} \mathrm{dom} f_i} \sum _{i\in I} \big (\langle x_i^*, x_i\rangle - f_i(x_i)\big ). \end{aligned}$$

Due to Remark 3 we switch $\sup$ and $\sum$ to obtain

$$\begin{aligned} f^*((x^*_i)_i)= & {} \sum _{i\in I} \sup _{x_i\in \mathrm{dom} f_i} \big (\langle x_i^*, x_i\rangle - f_i(x_i)\big )\\= & {} \sum _{i\in I} f^*_i(x_i^*), \end{aligned}$$

which proves (2) (see also Remark 2.1(ii) [6] for this relation in the case where $x^*\in \mathrm{dom} f^*$ and f is convex). For the last statement, let $(\overline{x}_i^*)_i \in \mathrm{dom } f^*$. By (2) one has $f^*((\overline{x}_i^*)_i ) = \sum _{i\in I} f^*_i(\overline{x}_i^*) <+\infty$. Actually, $\sum _{i\in I} f^*_i(\overline{x}_i^*)\in {\mathbb {R}}$ because $\mathrm{dom} f\not =\emptyset$ (by (H)), and so $f^*((\overline{x}_i^*)_i ) \not =-\infty .$ For every $i\in I$, we define a function $h_i: X_i\rightarrow {\mathbb {R}}_\infty$ by

$$\begin{aligned} h_i(x_i):= f_i(x_i)-\langle \overline{x}^*_i, x_i\rangle +f^*_i(\overline{x}^*_i). \end{aligned}$$

In view of the Fenchel inequality, $h_i\in \Gamma _+(X_i)$. Consequently, $\hat{h}_i:= h_i\circ p_i\in \Gamma _+({\mathcal {X}})$. By introducing $k((x_i)_i) := \sum _{i\in I} \big (\langle \overline{x}^*_i, x_i\rangle - f^*_i(\overline{x}^*_i)\big )$ for $(x_i)_i\in {\mathcal {X}}$, we have

$$\begin{aligned} f((x_i)_i) + k((x_i)_i) = \sum _{i\in I} \hat{h}_i((x_i)_i). \end{aligned}$$

Observe that $\mathrm{dom}(f+k)= \mathrm{dom} f$ because the function k is linear continuous. Moreover, being the supremum of the family $\{\sum _{i\in J} \hat{h}_i: J\in {\mathcal {I}}\}$ of functions from $\Gamma _+({\mathcal {X}})$, the function $h:= f+k$ belongs to $\Gamma _+({\mathcal {X}})$ too. By this $f= h-k\in \Gamma ({\mathcal {X}}).$ $\square$

We notice that equality in (2) may fail if domf is empty as it is shown in the next example.

Example 1

Let $I= {\mathbb {N}}$, $X_i= {\mathbb {R}}$ and $f_i(x_i)= 1/i$ for $x_i\in X_i$ and $i\in I$. For every $(x_i)_i\in {\mathcal {X}}$ we have $f((x_i)_i) = \sum _{i\in I} f_i(x_i) = \sum _{i=1}^\infty 1/i = +\infty$. Hence $f^*((x_i^*))= -\infty$ for all $(x_i^*)_i\in {\mathcal {X}}^*$. Let $(\overline{x}_i^*)_i\in {\mathcal {X}}^*$ be such that $\overline{x}_1^*\not =0$ and $\overline{x}^*_i=0$ for $i\ge 2$. Then, $f_1^*(\overline{x}_1^*) = +\infty$ and $f_i^*(\overline{x}_i^*) = - 1/i, i\ge 2$. Consequently, $\sum _{i\in I} f_i^*(\overline{x}_i^*) = +\infty$ and $f^*((\overline{x}_i^*)_i) \not = \sum _{i\in I} f_i^*(\overline{x}_i^*).$

4 Infinite sums of epigraphs

Let $(Z, Z^*)$ be a dual pair of separated locally convex spaces. The coupling function between Z and $Z^*$ is denoted $\langle . , . \rangle$. Let $\{z_i: i\in I\}$ be a family in Z. We say that z is the w-sum of this family and write $z=\sum _{i\in I}^w z_i$ if for every $z^*\in Z^*$ one has $\langle z^*, z\rangle = \sum _{ i\in I} \langle z^*, z_i\rangle$. Similarly, $z^*$ is the w*-sum of a family $\{z_i^*: i\in I\} \subset Z^*$ (we write $z^*=\sum _{i\in I}^{w^*} z^*_i$ ) if $\langle z^*, z\rangle = \sum _{ i\in I} \langle z_i^*, z\rangle$ for all $z\in Z$. The w-sum of a family of sets $\{A_i: i\in I\}\subset Z$ and the w*-sum of a family $\{B_i: i\in I\}\subset Z^*$ are respectively defined by

$$\begin{aligned} {\sum _{i\in I}}^w A_i:= & {} \left\{ {\sum _{i\in I}}^w z_i: z_i\in A_i, i\in I\right\} \\ {\sum _{i\in I}}^{w^*} B_i:= & {} \left\{ {\sum _{i\in I}}^{w^*} z^*_i: z^*_i\in B_i, i\in I\right\} \end{aligned}$$

We now concentrate on the case $Z= {\mathcal {X}}\times {\mathbb {R}}$, $Z^*= {\mathcal {X}}^*\times {\mathbb {R}}$ and study the families $\{ \mathrm{epi} f_i: i\in I\}$ and $\{ \mathrm{epi} f^*_i: i\in I\}$.

Let’s denote the canonical projection of ${\mathcal {X}}^*$ onto $X^*_j$ by $q_j$ and its transposed from $X_j$ into ${\mathcal {X}}$ by $m_j$, that is, for $x_j\in X_j$, $m_j(x_j)= (x_i)_i$ with $x_i=x_j$ if $i=j$ and $x_i=0_{X_i}$ if $i\not =j$. An extention $M_j: X_j\times {\mathbb {R}} \rightarrow {\mathcal {X}}\times {\mathbb {R}}$ of $m_j$ is given by $M_j(x_j, r):= (m_j(x_j), r)$ for $x_j\in X_j$ and $r\in {\mathbb {R}}.$

Lemma 1

The following assertions hold true.

• (i) $\sum _{i\in I}^w m_i(x_i) = (x_i)_i$ for $(x_i)_i\in {\mathcal {X}}$.

• (ii) $\sum _{i\in I}^w m_i(A_i) = \prod _{i\in I} A_i$ for $A_i\subset X_i, i\in I$.

• (iii) $\sum _{i\in I}^w M_i(C_i) = \{ ((x_i)_i, \sum _{i\in I}r_i)\in {\mathcal {X}}\times {\mathbb {R}}: (x_i, r_i)\in C_i\}$ for $C_i\subset X_i\times {\mathbb {R}}, i\in I$.

Proof

Let $(x_i)_i\in {\mathcal {X}}$. For each $(x_i^*)_i\in {\mathcal {X}}^*$ we have

$$\begin{aligned} \langle (x_i^*)_i, (x_i)_i\rangle = \sum _{i\in I} \langle x_i^*, x_i\rangle = \sum _{i\in I} \langle q_i((x_j^*)_j), x_i\rangle = \sum _{i\in I} \langle x_i^*, m_i(x_i)\rangle . \end{aligned}$$

Hence $(x_i)_i = \sum _{i\in I}^w m_i(x_i)$. For the second assertion, let $a_i\in A_i, i\in I$. By (i), $\sum _{i\in I}^w m_i(a_i) = (a_i)_i \in \prod _{i\in I} A_i$, which proves $\sum _{i\in I}^w m_i(A_i) \subset \prod _{i\in I} A_i$. Conversely, let $(a_i)_i\in \prod _{i\in I} A_i$. Again, by (i), $(a_i)_i=\sum _{i\in I}^w m_i(a_i) \in \sum _{i\in I}^w m_i(A_i)$ and (ii) follows.

For the last assertion let $((a_i)_i, r)= \sum _{i\in I}^w M_i(x_i, r_i)= \sum _{i\in I}^m (m_i(x_i), r_i)$ for some $(x_i,r_i)\in C_i, i\in I$. It follows that $(a_i)_i=\sum _{i\in I}^w m_i(x_i)$ and $r=\sum _{i\in I} r_i$. By (i), $a_i=x_i$ and shows that $(a_i,r_i)\in C_i, i\in I$. Conversely, let $((x_i)_i, \sum _{i\in I}r_i)\in {\mathcal {X}}\times {\mathbb {R}}$ with $(x_i, r_i)\in C_i, i\in I$. Then $r:= \sum _{i\in I}r_i\in {\mathbb {R}}$ and by (i), $((x_i)_i, r)= \sum _{i\in I}^w (m_i(x_i), r_i) = \sum _{i\in I}^w M_i(x_i, r_i)\in \sum _{i\in I}^w M_i(C_i),$ which completes the proof. $\square$

Proposition 2

Assume that f does not take the value $-\infty$ and that (H) holds. Then

$$\begin{aligned} \mathrm{epi} f = {\sum _{i\in I}}^w M_i(\mathrm{epi} f_i). \end{aligned}$$

Proof

By definition $((x_i)_i, r)\in \mathrm{epi} f$ if and only if $-\infty< f((x_i)_i) = \sum _{i\in I} f_i(x_i)\le r<+\infty$. In view of Remark 2 the second inequality holds if and only if there are $r_i\in {\mathbb {R}}$ such that $(x_i, r_i)\in \mathrm{epi} f_i, i\in I$ and $\sum _{i\in I} r_i=r$. In view of Lemma 1 (iii), this is equivalent to $((x_i)_i, r)\in \sum _{i\in I}^w M_i(\mathrm{epi} f_i).$ The proof is complete. $\square$

A dual version of Lemma 1 and of Proposition 2 is given next.

Lemma 2

The following assertions hold true.

• (i) $\sum _{i\in I}^{w^*} \ell _i(x^*_i) = (x^*_i)_i$ for $(x^*_i)_i\in {\mathcal {X}}^*$.

• (ii) $\sum _{i\in I}^{w^*} \ell _i(B_i) ={\mathcal {X}}^*\cap \prod _{i\in I} B_i$ for $B_i\subset X^*_i, i\in I$.

• (iii) $\sum _{i\in I}^{w^*} L_i(D_i) = \{ ((x^*_i)_i, \sum _{i\in I}r_i)\in {\mathcal {X}}^*\times {\mathbb {R}}: (x^*_i, r_i)\in D_i\}$ for $D_i\subset X^*_i\times {\mathbb {R}}, i\in I$.

Proof

Apply the argument similar to that of Lemma 1. $\square$

Proposition 3

Under (H) one has

$$\begin{aligned} \mathrm{epi} f^* = {\sum _{i\in I}}^{w^*} L_i(\mathrm{epi} f^*_i) = {\sum _{i\in I}}^{w^*} \mathrm{epi} \hat{f}^*_i. \end{aligned}$$

Proof

Apply the argument of Proposition 2 by using Lemma 2. $\square$

5 Duality for infinite monotropic problems

In this section we assume that $f_i, i\in I$ are proper convex and lower semicontinuous functions satisfying (H) and $\mathrm{dom} f^* \not =\emptyset .$

In view of Proposition 1 the function f is proper convex and lower semicontinuous too. We consider the following extended infinite monotropic problem

$$\begin{aligned} (\mathrm{P}^g_{(\overline{x}^*_i)_i}) \qquad \begin{array}{ll} \inf &{}\; \sum _{i\in I} (f_i(x_i) -\langle \overline{x}^*_i , x_i\rangle ) + g((x_i)_i)\\ (x_i)_i\in {\mathcal {X}},&{} \end{array} \end{aligned}$$

where g is a proper convex and lower semicontinuous function on ${\mathcal {X}}$ and $(\overline{x}^*_i)_i\in {\mathcal {X}}^*$ is given. The infimum of $(\mathrm{P}^g_{(\overline{x}^*_i)_i})$ is denoted by $\inf (\mathrm{P}^g_{(\overline{x}^*_i)_i})$, or by $\min (\mathrm{P}^g_{(\overline{x}^*_i)_i})$ if the optimal value is attained. We have

$$\begin{aligned} - \inf (\mathrm{P}^g_{(\overline{x}^*_i)_i}) = (f+g)^*((\overline{x}^*_i)_i) \le (f^*\Box g^*)((\overline{x}^*_i)_i), \end{aligned}$$

(3)

where $(f^*\Box g^*)$ denotes the infimal convolution of $f^*$ and $g^*$, that is,

$$\begin{aligned} (f^*\Box g^*)(( x^*_i)_i):= \inf _{(y^*_i)_i\in {\mathcal {X}}^*} (f^*((y^*_i)_i) + g^*((x_i^*-y_i^*)_i)\; \; \mathrm{for \; } (x_i^*)_i\in {\mathcal {X}}^*. \end{aligned}$$

(4)

The above infimal convolution is said to be exact if the infimum on the right hand side is attained at some $(y^*_i)_i \in {\mathcal {X}}^*$.

We deduce the Fenchel conjugate dual of $(\mathrm{P}^g_{(\overline{x}^*_i)_i}):$

$$\begin{aligned} (\mathrm{D}^g_{(\overline{x}^*_i)_i})\qquad \begin{array}{ll} \sup &{}\; - \big (f^*((x^*_i)_i) + g^*((\overline{x}^*_i-x^*_i)_i)\big ) \\ (x^*_i)_i\in {\mathcal {X}}^*.&{} \end{array} \end{aligned}$$

Because elements of ${\mathcal {X}}^*$ are of finite support, this dual is also referred to as finite support dual. Due to Proposition 1 it can be written as

$$\begin{aligned} (\mathrm{D}^g_{(\overline{x}^*_i)_i}) \qquad \begin{array}{ll} \sup &{}\; - \big (\sum _{i\in I} f^*_i(x^*_i) + g^*((\overline{x}^*_i-x^*_i)_i)\big )\\ (x_i^*)_i\in {\mathcal {X}}^*.&{} \end{array} \end{aligned}$$

Similar to the case of $(\mathrm{P}^g_{(\overline{x}^*_i)_i})$, the supremum of $(\mathrm{D}^g_{(\overline{x}^*_i)_i})$ is denoted by $\sup (\mathrm{D}^g_{(\overline{x}^*_i)_i})$, or by $\max (\mathrm{D}^g_{(\overline{x}^*_i)_i})$ if the optimal value is attained. The standard weak duality relation is immediate from (3), namely,

$$\begin{aligned} \inf (\mathrm{P}^g_{(\overline{x}^*_i)_i}) = -(f+g)^*((\overline{x}^*_i)_i) \ge -(f^*\Box g^*)((\overline{x}^*_i)_i) = \sup (\mathrm{D}^g_{(\overline{x}^*_i)_i}). \end{aligned}$$

When the above inequality is equality, $(\mathrm{P}^g_{(\overline{x}^*_i)_i})$ is said to have zero duality gap, and if in addition the optimal value of the dual is achieved, we have strong duality for the primal problem, in which case $(\mathrm{P}^g_{(\overline{x}^*_i)_i})$ is called stable in some literature [7, 12]. Thus, the strong duality property is nothing, but the expression

$$\begin{aligned} (f+g)^*((\overline{x}^*_i)_i) = (f^*\Box g^*)((\overline{x}^*_i)_i), \end{aligned}$$

(5)

in which the infimal convolution is exact. Strong duality for the dual problem refers to the case when $\min (\mathrm{P}^g_{(\overline{x}^*_i)_i}) = \sup (\mathrm{D}^g_{(\overline{x}^*_i)_i})$.

We give below the main result of this section on a necessary and sufficient condition for strong duality. We shall need Theorem 9.2 [4] which states that if $h_1$ and $h_2$ are proper convex, lower semicontinuous functions on a separated locally convex space Z such that dom$h_1\cap$ dom$h_2 \not =\emptyset$ and V is a nonempty subset of $Z^*$, then $(h_1+h_2)^*(z^*)= \min \{h_1^*(y^*)+h_2^*(z^*-y^*): y^*\in Z^*\}$ for every $x^*\in V$ if and only if the set $Q:=$ epi$h_1^* +$ epi$h_2^*$ is $w^*$-closed regarding the set $V\times {\mathbb {R}}$ in the sense that $Q\cap (V\times {\mathbb {R}}) = \overline{Q}^{w^*}\cap (V\times {\mathbb {R}})$, where $\overline{Q}^{w^*}$ denotes the closure of Q in the weak* topology of $Z^*\times {\mathbb {R}}$.

Theorem 1

Let $g, f_i, i\in I$ be proper convex and lower semicontinuous functions satisfying (H) such that $\mathrm{dom} f\cap \mathrm{dom} g \not =\emptyset$ and let $(\overline{x}^*_i)_i\in {\mathcal {X}}^*$ be given. Assume $\sum _{i\in I} f_i^*(z^*_i) \in {\mathbb {R}}$ for some $(z^*_i)_i\in {\mathcal {X}}^*$. Then the following statements are equivalent:

• (i) $\inf (\mathrm{P}^g_{(\overline{x}^*_i)_i}) = \max (\mathrm{D}^g_{(\overline{x}^*_i)_i}).$

• (ii) The set $\sum _{i\in I}^{w^*} L_i(\mathrm{epi} f_i^*) + \mathrm{epi} g^*$ is $w^*$-closed regarding the set $\{(\overline{x}^*_i)_i\}\times {\mathbb {R}}.$

In particular, (i) holds for every $(\overline{x}^*_i)_i\in {\mathcal {X}}^*$ if and only if the set $\sum _{i\in I}^{w^*} L_i(\mathrm{epi} f_i^*) + \mathrm{epi} g^*$ is $w^*$-closed.

Proof

We observe that in view of Proposition 1 the function f is proper convex and lower semicontinuous. By Theorem 9.2 [4] cited above,

$$\begin{aligned} -(f+g)^*(( x_i^*)_i) = \max \{-f^*((y^*_i)_i) - g^*((x^*_i-y^*_i)_i): (y^*_i)_i\in {\mathcal {X}}^*\} \end{aligned}$$

(6)

if and only if epi$f^*+$ epi $g^*$ is $w^*$-closed regarding the set $\{(\overline{x}^*_i)_i\}\times {\mathbb {R}}$. Since (6) is exactly (i), it remains to apply Proposition 3 to obtain epi$f^*+$ epi $g^*= {\sum _{i\in I}}^{w^*} L_i(\mathrm{epi} f^*_i) + \mathrm{epi} g^*$ and the equivalence between (i) and (ii). The second statement of the theorem visibly follows from the first one. The proof is complete. $\square$

The next theorem characterizes strong duality for the dual problem. We denote by $\tilde{g}$ the function $(x_i)_i \mapsto g(-(x_i)_i) + \sum _{i\in I} \langle \overline{x}_i^*, x_i\rangle$ on ${\mathcal {X}}$. One has $\tilde{g}^*((x^*_i)_i) = g^*((\bar{x}^*_i - x^*_i)_i),$ which yields

$$\begin{aligned} \mathrm{dom} \tilde{g}^*= (\bar{x}^*_i)_i - \mathrm{dom} g^*. \end{aligned}$$

(7)

Theorem 2

Let $g, f_i, i\in I$ be proper convex and lower semicontinuous functions satisfying (H) such that $\mathrm{dom} f^*\cap - \big (\mathrm{dom} g^* - (\overline{x}_i^*)_i\big )\not =\emptyset$. Then the following statements are equivalent:

• (i) $\min (\mathrm{P}^g_{(\overline{x}^*_i)_i}) = \sup (\mathrm{D}^g_{(\overline{x}^*_i)_i}).$

• (ii) The set $\sum _{i\in I}^{w} M_i(\mathrm{epi} f_i) + \mathrm{epi} \tilde{g}$ is closed regarding the set $\{0_{{\mathcal {X}}}\}\times {\mathbb {R}}.$

Proof

By the definition of $\tilde{g}$ we express $\inf (\mathrm{P}^g_{(\overline{x}^*_i)_i})$ and $\sup (\mathrm{D}^g_{(\overline{x}^*_i)_i})$ as

$$\begin{aligned} \inf (\mathrm{P}^g_{(\overline{x}^*_i)_i})= & {} (f\Box \tilde{g})(0_{{\mathcal {X}}}) \\ \sup (\mathrm{D}^g_{(\overline{x}^*_i)_i})= & {} (f^*+ \tilde{g}^*)^*(0_{{\mathcal {X}}}). \end{aligned}$$

Since f and $\tilde{g}$ are proper convex, lower semicontinuous functions, and in view of (7), $\mathrm{dom} f^* \cap \mathrm{dom} \tilde{g}^* \not =\emptyset$, we may apply the dual version of Theorem 9.2 [6] with $V= \{0_{{\mathcal {X}}} \}$ to obtain equivalence between (i) and the closedness of $\mathrm{epi} f+ \mathrm{epi} \tilde{g}$ regarding the set $\{0_{{\mathcal {X}}} \} \times {\mathbb {R}}.$ It remains to apply Proposition 2 to conclude. $\square$

We wish to apply Theorems 1 and 2 to problems with set constraints. Let K be a nonempty closed convex set in ${\mathcal {X}}$. We consider the problem

$$\begin{aligned} (\mathrm{P})\qquad \begin{array}{ll} \inf &{}\; \sum _{i\in I} f_i(x_i)\\ (x_i)_i\in K. &{} \end{array} \end{aligned}$$

By setting $g:=\delta _K$ the indicator function of K, the dual of (P) can be written as

$$\begin{aligned} (\mathrm{D})\qquad \begin{array}{ll} \sup &{}\; - \big (\sum _{i\in I} f^*_i(x^*_i) + \delta _K^*(-(x^*_i)_i)\big )\\ (x_i^*)_i\in {\mathcal {X}}^*.&{} \end{array} \end{aligned}$$

The conjugate $\delta ^*_K$ of $\delta _K$ is often denoted $\sigma _K$ (the support function of K) and given by

$$\begin{aligned} \sigma _K((x^*_i)_i) := \sup _{(x_i)_i\in K} \sum _{i\in I} \langle x^*_i, x_i\rangle . \end{aligned}$$

Corollary 1

Let $f_i, i\in I$ be proper convex and lower semicontinuous functions satisfying (H) such that $\mathrm{dom} f\cap K \not =\emptyset$. Then the following statements are equivalent:

• (i) $\inf (\mathrm{P}) = \max (\mathrm{D}).$

• (ii) The set $\sum _{i\in I}^{w^*} \mathrm{epi} (\hat{f}_i)^* + \mathrm{epi} \sigma _K$ is $w^*$-closed regarding the set $\{0_{\mathcal {X}^*}\}\times {\mathbb {R}}.$

Proof

Apply Theorem 1 with $\overline{x}_i^*= 0_{X_i^*}, i\in I$. $\square$

Remark 4

According to Proposition 1, under (H) the existence of $(z^*_i)_i\in {\mathcal {X}}^*$ such that $\sum _{i\in I} f_i^*(z^*_i) \in {\mathbb {R}}$ is equivalent to dom$f^*\not =\emptyset$.

Remark 5

A sufficient condition for (i) of Corollary 1 was already given by Theorem 3.5 [6] which requires f to be proper lower semicontinuous and $\mathrm{epi} f^* = \sum _{i\in I}^{w^*} \mathrm{epi} (\hat{f}_i)^*$ in addition to (ii). Note that in view of Proposition 1 and Proposition 3, these two conditions always hold under (H).

Corollary 2

Let $f_i, i\in I$ be proper convex and lower semicontinuous functions satisfying (H) such that $\mathrm{dom} f^*\cap (- \mathrm{dom} \sigma _K )\not =\emptyset$. Then the following statements are equivalent:

• (i) $\min (\mathrm{P}) = \sup (\mathrm{D}).$

• (ii) The set $\sum _{i\in I}^{w} M_i(\mathrm{epi} f_i) + K\times {\mathbb {R}}_+$ is closed regarding the set $\{0_{{\mathcal {X}}}\}\times {\mathbb {R}}.$

Proof

Apply Theorem 2 with $\overline{x}_i^*= 0_{X_i^*}, i\in I$. $\square$

6 Problems with infinite sum of convex functions

We consider the following problem

$$\begin{aligned} (\mathrm{P}_{\overline{x}^*})\qquad \begin{array}{ll} \inf &{}\; \sum _{i\in I} f_i(x) - \langle \overline{x}^*, x\rangle \\ x\in X, &{} \end{array} \end{aligned}$$

where $(X, X^*)$ is a dual pair of separated locally convex spaces, $(f_i)_{i\in I}$ is a family of proper convex, lower semicontinuous functions on X and $\overline{x}^*\in X^*$ is given. We wish to apply the method of monotropic programming developed in the previous section to this problem. To this end we set $X_i=X, i\in I$ and assume the following hypothesis

• (H’) For every $(x_i)_i\in {\mathcal {X}}$, $f((x_i)_i):= \sum _{i\in I} f_i(x_i)$ exists in $\overline{\mathbb {R}}$ , and there is some $\overline{x}\in X$ such that $\sum _{i\in I} f_i(\overline{x}) \in {\mathbb {R}}$.

By definition ${\mathcal {X}}= X^I$, hence its dual ${\mathcal {X}}^*$ can be identified with the space $(X^*)^{[I]}$ consisting of all families $(x^*_i)_i\in (X^*)^I$ with finitely many nonzero terms. We consider the linear mapping $L: X \rightarrow {\mathcal {X}}$ defined by $L(x)= (x)_i$, where $(x)_i$ denotes the element $(x_i)_i\in {\mathcal {X}}$ with $x_i=x$ for all $i\in I$. Let $S:= L(X)$. It is a closed linear subspace of ${\mathcal {X}}$, called also the diagonal subspace of ${\mathcal {X}}$. By using $g=\delta _S$ and by choosing $(\overline{x}_i^*)_i \in {\mathcal {X}}^*$ such that $\sum _{i\in I} \overline{x}_i^*= \overline{x}^*$, we may express $(\mathrm{P}_{\overline{x}^*})$ in form of monotropic programming problem

$$\begin{aligned} (\mathrm{P}^{\delta _S}_{(\overline{x}^*_i)_i}) \qquad \begin{array}{ll} \inf &{}\; \sum _{i\in I} (f_i(x_i) -\langle \overline{x}^*_i , x_i\rangle ) + \delta _S((x_i)_i)\\ (x_i)_i\in {\mathcal {X}}.&{} \end{array} \end{aligned}$$

In order to obtain a dual of $(\mathrm{P}_{\overline{x}^*})$ by the construction presented in Sect. 5, we compute $g^*= \delta _S^*= \delta _{S^\perp }$, where $S^\perp$ is the orthogonal of S, that is,

$$\begin{aligned} S^\perp =\left\{ (x^*_i)\in {\mathcal {X}}^*: \sum _{i\in I} \langle x^*_i, x\rangle =0 \mathrm{\; for \; all \;} x\in X\right\} = \left\{ (x^*_i)\in {\mathcal {X}}^*: {\sum _{i\in I}}^{w^*} x^*_i =0_{X^*} \right\} . \end{aligned}$$

Let $A: {\mathcal {X}}^* \rightarrow X^*$ denote the transposed of L, that is,

$$\begin{aligned} A((x^*_i)_i) = {\sum _{i\in I}}^{w^*} x_i^*\; \mathrm{for\; every\; } (x^*_i)_i\in {\mathcal {X}}^*. \end{aligned}$$

Note that $\sum _{i\in I}^{w^*} x_i^*$ is a finite sum and therefore the superscript ”$^{w^*}$” in the expressions of $S^\perp$ and of $A((x^*_i)_i)$ can be omitted. It follows that $S^\perp$ coincides with the kernel $ker\; A$ of A. We deduce the dual of $(\mathrm{P}_{\overline{x}^*})$:

$$\begin{aligned} (\mathrm{D}_{\overline{x}^*}) \qquad \begin{array}{ll} \sup &{}\; -\sum _{i\in I} f^*_i(x_i^*)\\ (x^*_i)_i\in (X^*)^{[I]}, &{} A((x^*_i)_i) = \overline{x}^*. \end{array} \end{aligned}$$

Theorem 3

Let $(f_i)_{i\in I}$ be a family of proper convex lower semicontinuous functions on X satisfying (H’). Assume that there is some $(z_i^*)_i\in (X^*)^{[I]}$ such that $\sum _{i\in I} f^*_i(z_i^*) < +\infty$. Then for every $\overline{x}^*\in X^*$, the following statements are equivalent.

• (i) $\inf (\mathrm{P}_{ \overline{x}^*})= \max (\mathrm{D}_{ \overline{x}^*})$.

• (ii) $\sum _{i\in I}^{w^*} L_i (\mathrm{epi} f_i^*) + ker A\times \{0\}$ is $w^*$-closed regarding $A^{-1}(\overline{x}^*)\times {\mathbb {R}}$.

In particular (i) holds for all $\overline{x}^*\in X^*$ if and only if the set $\sum _{i\in I}^{w^*} L_i (\mathrm{epi} f_i^*) + ker A\times \{0\}$ is $w^*$-closed in $(X^*)^{[I]}\times {\mathbb {R}}.$

Proof

Let $g:= \delta _S$. We have epi$g^*= ker A\times {\mathbb {R}}_+$. In view of Theorem 1, (i) holds true if and only if $\sum _{i\in I}^{w^*} L_i (\mathrm{epi} f_i^*) + ker A\times {\mathbb {R}}_+$ is $w^*$-closed regarding $A^{-1}(\overline{x}^*)\times {\mathbb {R}}$. Let us fix an index $i_0\in I$. For any $t>0$, $(x^*_i)_i\in ker A$ and for $(x_{i_0}^*, t_{i_0})\in$ epi $f^*_{i_0}$, one may express $L_{i_0} (x^*_{i_0}, t_{i_0}) + ((x^*_i)_i, t) = L_{i_0} (x^*_{i_0}, t_{i_0}+t) + ((x^*_i)_i, 0)$, in which $(x_{i_0}^*, t_{i_0}+t)\in$ epi $f^*_{i_0}$. This implies that $\sum _{i\in I}^{w^*} L_i (\mathrm{epi} f_i^*) + ker A\times {\mathbb {R}}_+ = \sum _{i\in I}^{w^*} L_i (\mathrm{epi} f_i^*) + ker A\times \{0\}$ and establishes equivalence between (i) and (ii). $\square$

Similar to (5), the strong duality property in Theorem 3(i) can be expressed in terms of infimal convolution as follows. Let $\phi _i, i\in I$ be a family of proper functions on $X^*$ such that for every $(x^*_i)_i\in (X^*)^{[I]},$ $\sum _{i\in I} \phi _i (x^*_i) \in \overline{\mathbb {R}}$. We define the generalized infimal convolution of this family to be

$$\begin{aligned} (\Box _{i\in I} \phi _i) (x^*):= \inf _{(x^*_i)_i\in (X^*)^{[I]}, \sum _{i\in I} x^*_i =x^* } \sum _{i\in I} \phi _i (x^*_i) \end{aligned}$$

and say that $\Box _{i\in I} \phi _i$ is exact at $x^*$ if the infimum is attained. Thus, Theorem 3(i) signifies that $(\sum _{i\in I} f_i)^*(\bar{x}^*) = (\Box _{i\in I} f_i) (\bar{x}^*)$ with the infimal convolution exact at $\bar{x}^*$. Note that this definition of infimal convolution is different from the one given in [13], in which a space larger than $(X^*)^{[I]}$ was used for taking the infimum. Of course, when I is finite, they are all the same and coincide with the classical definition of infimal convolution known from convex analysis. Let us denote

$$\begin{aligned} {\sum _{i\in I}}^{\bigotimes } \mathrm{epi} \phi _i := \left\{ \sum _{i\in I} (x_i^*, t_i): (x_i^*, t_i)\in \mathrm{epi} \phi _i, i\in I, (x^*_i)_i\in (X^*)^{[I]} \right\} . \end{aligned}$$

It can be seen that

$$\begin{aligned} \mathrm{epi}_s (\Box _{i\in I} \phi _i) \subseteq {\sum _{i\in I}}^{\bigotimes } \mathrm{epi} \phi _i \subseteq \mathrm{epi} (\Box _{i\in I} \phi _i), \end{aligned}$$

where $\mathrm{epi}_s$ stands for the strict epigraph. Moreover, the second inclusion is equality if and only if the infimal convolution is exact on $X^*$.

Corollary 3

Let $(f_i)_{i\in I}$ be a family of proper convex lower semicontinuous functions on X satisfying (H’). Assume that there is some $(z_i^*)_i\in (X^*)^{[I]}$ such that $\sum _{i\in I} f^*_i(z_i^*) < +\infty$. Then the following statements are equivalent.

• (i) $(\sum _{i\in I} f_i)^*= \Box _{i\in I} f_i^*$ and the infimal convolution is exact on $X^*$.

• (ii) $\mathrm{epi}(\sum _{i\in I} f_i)^* = \sum _{i\in I}^{\bigotimes } \mathrm{epi} f^*_i$.

• (iii) $\sum _{i\in I}^{\bigotimes } \mathrm{epi} f^*_i$ is $w^*$-closed in $X^*\times {\mathbb {R}}$.

• (iv) $\sum _{i\in I}^{w^*} L_i (\mathrm{epi} f_i^*) + ker A\times \{0\}$ is $w^*$-closed in $(X^*)^{[I]}\times {\mathbb {R}}$.

Proof

By (i) we have $\mathrm{epi}(\sum _{i\in I} f_i)^* = \mathrm{epi} (\Box _{i\in I} f_i^*),$ which, in view of the discussion before this corollary, gives (ii). The implication $(ii) \Rightarrow (iii)$ is clear because $(\sum _{i\in I} f_i)^*$ is a convex and $w^*$-lower semicontinuous function. For the implication $(iii) \Rightarrow (iv)$ we consider the mapping $\tilde{A}: (X^*)^{[I]}\times {\mathbb {R}} \rightarrow X^*\times {\mathbb {R}}$ defined by $\tilde{A} ( (x^*_i)_i, t) = (A((x_i^*)_i), t) = (\sum _{i\in I} x^*_i, t)$. It is a $w^*$-continuous linear mapping with $ker \tilde{A} = ker A\times \{0\}$. Moreover, by applying Lemma 2(iii) to the case $X_i=X, D_i= \mathrm{epi} f^*_i, i\in I$, we obtain that

$$\begin{aligned} \tilde{A} \left( {\sum _{i\in I}}^{w^*} L_i (\mathrm{epi} f_i^*) \right) = {\sum _{i\in I}}^{\bigotimes } \mathrm{epi} f^*_i. \end{aligned}$$

Consequently,

$$\begin{aligned} \tilde{A}^{-1} \left( {\sum _{i\in I}}^{\bigotimes } \mathrm{epi} f^*_i \right)= & {} {\sum _{i\in I}}^{w^*} L_i (\mathrm{epi} f_i^*) + ker \tilde{A} \\= & {} {\sum _{i\in I}}^{w^*} L_i (\mathrm{epi} f_i^*) + ker {A}\times \{0\}. \end{aligned}$$

Hence, $\sum _{i\in I}^{w^*} L_i (\mathrm{epi} f_i^*) + ker A\times \{0\}$ is $w^*$-closed because $\tilde{A}$ is $w^*$-continuous.

Finally, under (iv), in view of Theorem 3, we have $\inf (\mathrm{P}_{ \overline{x}^*})= \max (\mathrm{D}_{ \overline{x}^*})$, for any $\bar{x}^*\in X^*$, which yields (i). $\square$

In the next corollary M is an extension of L, mapping from $X\times {\mathbb {R}}$ to ${\mathcal {X}}\times {\mathbb {R}}$ defined by $M(x,t)= (L(x), t)$ for $(x,t)\in X\times {\mathbb {R}}$.

Corollary 4

Let $(f_i)_{i\in I}$ be a family of proper convex lower semicontinuous functions on X satisfying (H’). Assume that there is some $(z_i^*)_i\in ker A$ such that $\sum _{i\in I} f^*_i(z_i^*) < +\infty$. Then for every $\overline{x}^*\in X^*$, the following statements are equivalent.

• (i) $\min (\mathrm{P}_{ \overline{x}^*})= \sup (\mathrm{D}_{ \overline{x}^*})$.

• (ii) $\sum _{i\in I}^{w} M_i (\mathrm{epi} f_i) + M(\mathrm{epi } \langle \overline{x}^*, .\rangle )$ is closed regarding $\{0_{X^I} \}\times {\mathbb {R}}$.

Proof

Pick $(\bar{x}^*_i)_i\in {\mathcal {X}}^*$ such that $\sum _{i\in I} \bar{x}^*_i= \bar{x}^*$ and consider $\tilde{g} ((x_i)_i) := \delta _S(-(x_i)_i)+ \sum _{i\in I} \langle \overline{x}_i^*, x_i\rangle .$ We have $((x_i)_i, t)\in$ epi $\tilde{g}$ if and only if $(x_i)_i\in S$ and $\sum _{i\in I} \langle \overline{x}_i^*, x_i\rangle \le t$, or equivalently, $x_i=x, i\in I$ for some $x\in X$ and $\langle \overline{x}^*, x\rangle \le t$. Hence, epi$\tilde{g}= M(\mathrm{epi } \langle \overline{x}^*, .\rangle$. It remains to apply Theorem 2 to achieve the proof. $\square$

We finish this section by an example to illustrate Corollary 3.

Example 2

Let X be a Hilbert space and $\{ a_i: i\in {\mathbb {N}} \}$ be a family of vectors in X with $\sum _{i=1}^\infty \Vert a_i\Vert <+\infty$. Consider the functions $f_i:= \langle a_i, .\rangle + \delta _B, i\in {\mathbb {N}},$ where $\langle ., .\rangle$ is the inner product and B is the unit ball of X. For every $(x_i)_i\in X^{{\mathbb {N}}}$ we have

$$\begin{aligned} \sum _{i\in {\mathbb {N}}} f_i(x_i)= & {} \left\{ \begin{array}{ll} \langle a_i, x_i\rangle &{} \; \mathrm{if \;} x_i\in B, i\in {\mathbb {N}}\\ +\infty &{} \; \mathrm{else, } \end{array}\right. \end{aligned}$$

and (H’) holds. Moreover, direct calculation shows that

$$\begin{aligned} f^*_i (x^*)= & {} \Vert x^*- a_i\Vert \; \mathrm{for \; } i\in {\mathbb {N}}, x^*\in X\\ \sum _{i\in {\mathbb {N}}} f_i^*(x^*_i)= & {} \sum _{i\in {\mathbb {N}}} \Vert x_i^*-a_i\Vert < +\infty \; \mathrm{for }\; (x^*_i)_i\in X^{[{\mathbb {N}}]}\\ \left( \sum _{i\in {\mathbb {N}}} f_i\right) ^*(x^*)= & {} \Vert x^*-a\Vert , \end{aligned}$$

where $a= \sum _{i=1}^\infty a_i$. It follows that all the assumptions of Corollary 3 are satisfied. We wish to prove the following statement: Equality

$$\begin{aligned} \Vert x^*-a\Vert = \min _{ (x^*_i)_i \in X^{[{\mathbb {N}}]}, \sum _{i=1}^\infty x^*_i= x^* } \sum _{i\in {\mathbb {N}}} \Vert x^*_i - a_i\Vert \end{aligned}$$

(8)

holds true for every $x^*\in X$ (which is Corollary3(i)) if and only if $a_i=0_X$ for all but finitely many $i\in {\mathbb {N}}$.

Indeed, if $a_i=0_X, i\ge k$ for some $k\ge 1$, then $\sum _{i\in {\mathbb {N}}} f_i(x)= \sum _{i=1}^k f_i(x)$ for $x\in X$. Since the convex functions $f_1, ... , f_k$ are finite and continuous at $0_X$, in view of Theorem 1, page 178 [11] we have

$$\begin{aligned} \left( \sum _{i\in {\mathbb {N}}} f_i\right) ^*(x^*)= \left( \Box _{i=1}^k f_i^*\right) (x^*)\; \mathrm{for}\; x^*\in X^* \end{aligned}$$

with the infimal convolution exact. Thus, there exist some $z^*_i\in X^*, i=1, ... , k$ such that $\sum _{i=1}^k z^*_i= x^*$ and $\left( \sum _{i\in {\mathbb {N}}} f_i\right) ^*(x^*)= \sum _{i=1}^k f^*_i(z^*_i).$ Set

$$\begin{aligned} \bar{x}^{*}_i := \left\{ \begin{array}{ll} z^*_i &{} \; \mathrm{if\; } i\le k\\ 0_{X^*}&{} \; \mathrm{else.\; } \end{array} \right. \end{aligned}$$

Then $(\bar{x}^*_i)_i\in (X^*)^{[{\mathbb {N}}]}$, $\sum _{i\in {\mathbb {N}}} \bar{x}^*_i= x^*$ and

$$\begin{aligned} \left( \sum _{i\in {\mathbb {N}}} f_i\right) ^*(x^*)= & {} \sum _{i=1}^k \Vert z^*_i-a_i\Vert = \sum _{i\in {\mathbb {N}}} \Vert \bar{x}^*_i-a_i\Vert = \sum _{i\in {\mathbb {N}}} f^*_i(\bar{x}^*_i)\\\ge & {} \inf _{(x^*_i)_i\in (X^*)^{[{\mathbb {N}}]}, \sum _{i\in {\mathbb {N}}} x^*_i=x^*} \sum _{i\in {\mathbb {N}}} f_i^*(x_i^*) \\\ge & {} \left( \sum _{i\in {\mathbb {N}}} f_i\right) ^*(x^*), \end{aligned}$$

which gives (8). Conversely, assume an infinite number of $a_i's$ are nonzero, say $a_i\not =0$ for all $i \ge 1$. By definition we have

$$\begin{aligned} {\sum _{i\in I}}^{\bigotimes } \mathrm{epi} f^*_i = \left\{ \sum _{i=1}^\infty (x^*_i, r_i): \Vert x_i^*-a_i\Vert \le r_i, i\in {\mathbb {N}}, (x^*_i)_i \in X^{[{\mathbb {N}}]} \right\} . \end{aligned}$$

For every $n\ge 1$, set

$$\begin{aligned} x^{*n}_i := \left\{ \begin{array}{ll} a_i &{} \; \mathrm{if\; } i\le n\\ 0_X&{} \; \mathrm{else\; } \end{array} \right. \qquad \mathrm{and}\; \; r^{n}_i := \left\{ \begin{array}{ll} 0&{} \; \mathrm{if\; } i\le n\\ \Vert a_i\Vert &{} \; \mathrm{else.\; } \end{array} \right. \end{aligned}$$

Then $( x^{*n}_i , r^n_i)\in \mathrm{epi } f^*_i$ and $( x^{*n}_i )_i\in X^{[{\mathbb {N}}]}$ for all $n\ge 1$. Consequently, $\big ((\sum _{i=1}^n a_i, \sum _{i=n+1}^\infty r_i)\big )_n$ is a sequence in the set $\sum _{i\in I}^{\bigotimes } \mathrm{epi} f^*_i$. Note, however, that its limit when n tends to $\infty$ is equal to (a, 0) and does not lie in $\sum _{i\in I}^{\bigotimes } \mathrm{epi} f^*_i$. Thus, the latter set is not $w^*$-closed in $X^*$. According to Corollary 3, (8) is not true.

7 Truncation method

Throughout this section we assume that $I= {\mathbb {N}}$ and $X_i, i\in {\mathbb {N}}$ are finite dimensional spaces. We study problem (P) with K a closed linear subspace of ${\mathcal {X}}:= \prod _{i\in {\mathbb {N}}} X_i$, namely,

$$\begin{aligned} (\mathrm{P})\qquad \begin{array}{ll} \inf &{}\; \sum _{i\in {\mathbb {N}}} f_i(x_i) \\ \mathrm{s.t.} &{} (x_i)_i\in K. \end{array} \end{aligned}$$

This problem is known as a countably infinite monotropic problem. It has numerous applications in infinite network optimization and infinite horizon planning, and was thoroughly analyzed in [8] when $X_i= {\mathbb {R}}$ and the domains of $f_i$ are segments. We shall make the following hypothesis on the functions $f_i$:

(H”) The functions $f_i, i\in {\mathbb {N}}$ are proper convex, lower semicontinuous with compact domains, and satisfy $\sum _{i=1}^\infty \Vert f_i\Vert <+\infty$, where $\Vert f_i\Vert := \sup _{x_i\in \mathrm{dom} f_i} \vert f_i(x_i)\vert$.

It is clear that under (H”) the family of functions $(f_i)_i$ satisfies (H) too. Moreover, dom$f= \prod _{i\in {\mathbb {N}}} \mathrm{dom} f_i.$

Lemma 3

Let $(x^*)_i\in {\mathcal {X}}^*$. Under (H”), the sum $\sum _{i\in I} f_i^*(x_i^*)$ exists and

$$\begin{aligned} -\infty< f^*((x_i^*)_i) = \sum _{i\in I} f_i^*(x_i^*) < +\infty . \end{aligned}$$

(9)

Moreover, f is proper convex and lower semicontinuous.

Proof

In view of Proposition 1 it suffices to show that $\sum _{i\in I} f_i^*(x_i^*)$ is finite for every $(x^*_i)_i\in {\mathcal {X}}^*$. In fact, by definition,

$$\begin{aligned} \vert f^*_i(x_i^*)\vert= & {} \vert \sup _{x_i\in \mathrm{dom} f_i} (\langle x^*_i, x_i\rangle - f_i(x_i)) \vert \\\le & {} \vert \sup _{x_i\in \mathrm{dom} f_i} \langle x^*_i, x_i\rangle \vert + \Vert f_i\Vert . \end{aligned}$$

Since only a finite number of $x_i^*$ are nonzero and dom $f_i$ are compact, the sum $\sum _{i=1}^\infty \vert \sup _{x_i\in \mathrm{dom} f_i} \langle x^*_i, x_i\rangle \vert$ is finite. This and (H”) imply that

$$\begin{aligned} \vert \sum _{i\in I} f_i^*(x_i^*)\vert \le \sum _{i=1}^\infty \vert \sup _{x_i\in \mathrm{dom} f_i} \langle x^*_i, x_i\rangle \vert +\sum _{i=1}^\infty \Vert f_i\Vert <+\infty \end{aligned}$$

and complete the proof. $\square$

By using the construction of dual given in Sect. 5, we obtain a dual of (P):

$$\begin{aligned} (\mathrm{D})\qquad \begin{array}{ll} \sup &{}\; -\sum _{i=1}^\infty f_i^*(x^*_i) \\ \mathrm{s.t.} &{} (x^*_i)_i \in K^\perp , \end{array} \end{aligned}$$

where $K^\perp := \{(x^*_i)_i\in {\mathcal {X}}^*: \sum _{i=1}^\infty \langle x^*_i, x_i\rangle =0 \mathrm{\; for \; all \;} (x_i)_i \in K\}$.

To establish a relationship between (P) and (D), we follow the method of [8] to consider the truncated problems

$$\begin{aligned} (\mathrm{P}_n) \qquad \begin{array}{ll} \inf &{}\; \sum _{i=1}^n f_i(x_i) \\ \mathrm{s.t.} &{} x_i\in \mathrm{dom} f_i, i=1, ... , n; (x_1, ... , x_n)\in K_n, \end{array} \end{aligned}$$

where

$$\begin{aligned} K_n:= \left\{ (x_1, ... , x_n)\in \prod _{i=1}^n X_i: \mathrm{there \; is \;} (y_i)_i\in K \; \mathrm{such\; that\; } x_i=y_i, i=1, ... , n\right\} . \end{aligned}$$

The dual of (P$_n$) is given by

$$\begin{aligned} (\mathrm{D}_n) \qquad \begin{array}{ll} \sup &{}\; -\sum _{i=1}^n f_i^*(x^*_i) \\ \mathrm{s.t.} &{} x^*_i\in X^*_i, i=1, ... , n; (x^*_1, ... , x^*_n)\in K^\perp _n, \end{array} \end{aligned}$$

where

$$\begin{aligned} K^\perp _n:= \left\{ (x^*_1, ... , x^*_n)\in \prod _{i=1}^n X^*_i: \sum _{i=1}^n \langle x^*_i, x_i\rangle =0 \mathrm{\; for \; all \;} (x_1, ... , x_n) \in K_n\right\} . \end{aligned}$$

The following proposition generalizes Proposition 18 [8].

Proposition 4

Assume that (P) has a feasible solution. Then, problems (P) and (P$_n$) have optimal solutions and $\lim _{n\rightarrow \infty } \min (P_n) = \min (P).$

Proof

Let $(x_i)_i$ be a feasible solution of (P). By definition, $(x_i)_i\in K \cap \prod _{i\in {\mathbb {N}}} \mathrm{dom} f_i.$ It follows that $(x_1, ... , x_n)\in K_n\cap \prod _{i=1}^n \mathrm{dom} f_i$, and hence $(x_1, ... , x_n)$ is a feasible solution of $(P_n)$. Moreover, by hypothesis the function $\sum _{i=1}^n f_i(x_i)$ is proper convex and lower semicontinuous, and the feasible set $K_n\cap \prod _{i=1}^n \mathrm{dom} f_i$ of (P$_n$) is compact. Therefore, (P$_n$) admits an optimal solution. Similarly, in view of Lemma 3 the function f is proper convex and lower semicontinuous, and the feasible set $K\cap \prod _{i\in {\mathbb {N}}} \mathrm{dom} f_i$ of (P) is compact in the product topology. Therefore, (P) admits an optimal solution too.

Let $\bar{x}(n)\in K_n\cap \prod _{i=1}^n \mathrm{dom} f_i$ be an optimal solution of (P$_n$). By definition, there is some $y(n)\in K$ such that $\bar{x}_i(n)= y_i(n), i=1, ... , n.$ Choose $z(n) \in \prod _{i=n+1}^\infty \mathrm{dom} f_i$ and set $\bar{z}(n):= (\bar{x}(n), z(n)) \in \prod _{i=1}^\infty \mathrm{dom} f_i$. Since $\prod _{i=1}^\infty \mathrm{dom} f_i$ is compact and the product space $\prod _{i=1}^\infty X_i$ is metrisable, without loss of generality, we may assume that the sequence $\{ \bar{z}(n)\}_n$ converges to some $\bar{z}\in \prod _{i=1}^\infty \mathrm{dom} f_i$.

Claim 1. $\bar{z}$ is a feasible solution of (P).

It suffices to prove that $\bar{z}\in K$. Suppose to the contrary that $\bar{z}\not \in K$. Since K is closed, there is an open neighborhood U of $\bar{z}$ in ${\mathcal {X}}$ such that $U\cap K=\emptyset$. By the definition of the product topology, there are some $N\ge 1$ and open sets $U_i\subset X_i, i=1, ... , N$ such that $\bar{z}\in U':=U_1\times ... \times U_N\times \prod _{i=N+1}^\infty X_i\subset U$. Moreover, because $\{ \bar{z}(n)\}_n$ converges to $\bar{z}$, there is some $N'\ge N$ such that $\bar{z}(n)\in U'$ for all $n\ge N'$. In particular, $\bar{x}(n)=(\bar{z}_1(n), ... , \bar{z}_n(n))\in U_1\times ... \times U_n$ for $n\ge N'$. This implies $y(n)\in U'$ for $n\ge N'$ and contradicts the fact that $y(n) \in K$ and $K\cap U=\emptyset$.

Claim 2. $\bar{z}$ is an optimal solution of (P).

Indeed, if not, there exists a feasible solution $\bar{x}\in K$ such that $\sum _{i=1}^\infty f_i(\bar{x}_i) < \sum _{i=1}^\infty f_i(\bar{z}_i)$. Let $\epsilon >0$ be such that

$$\begin{aligned} \sum _{i=1}^\infty f_i(\bar{x}_i) +\epsilon \le \sum _{i=1}^\infty f_i(\bar{z}_i). \end{aligned}$$

(10)

Since f is lower semicontinuous (Lemma 3) and $\sum _{i=1}^\infty \Vert f_i\Vert <+\infty$, we may choose N sufficiently large such that $f(\bar{z}) \le f(\bar{z}(N)) +\epsilon /4$ and $\sum _{i=N+1}^\infty \Vert f_i\Vert <\epsilon /4$. This and (10) imply that

$$\begin{aligned} \sum _{i=1}^N f_i(\bar{x}_i) \le \sum _{i=1}^\infty f_i(\bar{x}_i) +\epsilon /4 \le \sum _{i=1}^\infty f_i(\bar{z}_i) - 3\epsilon /4 \le \sum _{i=1}^\infty f_i(\bar{z}_i(N)) - \epsilon /2. \end{aligned}$$

Since $\bar{z}_i(N) = \bar{x}_i(N)$ for $i=1, ... , N$, we deduce also

$$\begin{aligned} \sum _{i=1}^N f_i(\bar{x}_i) \le \sum _{i=1}^N f_i(\bar{z}_i(N))+\sum _{i=N+1}^\infty f_i(\bar{z}_i(N)) - \epsilon /2\le \sum _{i=1}^N f_i(\bar{x}_i(N)) - \epsilon /4, \end{aligned}$$

which contradicts the fact that $(\bar{x}_1, ... , \bar{x}_N)\in K_N\cap \prod _{i=1}^N \mathrm{dom} f_i$ and $\bar{x}(N)$ is an optimal solution of (P$_N$).

Claim 3. $\lim _{n\rightarrow \infty } f(\bar{z}(n)) = f( \bar{z})$.

In fact, as f is lower semicontinuous (Lemma 3) and in view of Claim 1, we have min(P)=$f(\bar{z}) \le \liminf _{n\rightarrow \infty } f(\bar{z}(n)).$ Suppose to the contrary that Claim 3 is not true. There exists $\epsilon >0$ and a subsequence $\{ \bar{z}(n_k)\}_k$ such that $f(\bar{z}) +\epsilon \le f(\bar{z}(n_k))$ for all $k\ge 1$. Choose $k_0$ sufficiently large such that $\sum _{i=n_{k_0}+1}^\infty \Vert f_i\Vert <\epsilon /4$. Then,

$$\begin{aligned} \sum _{i=1}^{n_{k_0}} f_i(\bar{z}_i) +3\epsilon /4 \le f(\bar{z}) +\epsilon \le \sum _{i=1}^{n_{k_0}} f_i(\bar{z}_i(n_{k_0})) + \epsilon /4, \end{aligned}$$

which implies that

$$\begin{aligned} \sum _{i=1}^{n_{k_0}} f_i(\bar{z}_i) < \sum _{i=1}^{n_{k_0}} f_i(\bar{z}_i(n_{k_0})) . \end{aligned}$$

Since $(\bar{z}_1, ... , \bar{z}_{n_{k_0}})\in K_{n_{k_0}} \cap \prod _{i=1}^{n_{k_0}} \mathrm{dom} f_i$ and $\bar{x}(n_{k_0}) = (\bar{z}_1(n_{k_0}), ... , \bar{z}_{n_{k_0}}(n_{k_0}))$, the latter strict inequality contradicts the fact that $\bar{x}(n_{k_0})$ is an optimal solution of (P$_{n_{k_0}}$).

Finally, in view of Claim 3 we obtain that

$$\begin{aligned} \lim _{n\rightarrow \infty } \vert \min (P) - \min (P_n)\vert= & {} \lim _{n\rightarrow \infty } \vert f(\bar{z}) - \sum _{i=1}^n f_i(\bar{x}_i(n)) \vert \\= & {} \lim _{n\rightarrow \infty } \vert f(\bar{z}) - f(\bar{z}(n)) + \sum _{i=n+1}^\infty f_i(\bar{z}_i(n) )\vert \\\le & {} \lim _{n\rightarrow \infty } \vert f(\bar{z}) - f(\bar{z}(n))\vert + \lim _{n\rightarrow \infty }\sum _{i=n+1}^\infty \Vert f_i\Vert \\\le & {} 0, \end{aligned}$$

and complete the proof. $\square$

Lemma 4

Let $f_1, ... , f_n$ be proper convex and lower semicontinuous with compact domains. If (P$_n$) has a feasible solution, then

$$\begin{aligned} \min (P_n) =\sup (D_n) \in {\mathbb {R}}. \end{aligned}$$

Proof

Let ${\mathcal {X}}_n^*:= \prod _{i=1}^n X_i^*$ and consider the function $\phi$ on ${\mathcal {X}}_n^*$ defined by $\phi (x_1^*, ... , x_n^*) : = \sum _{i=1}^n f_i^*(x_i^*)$ for $(x_1^*, ... , x_n^*)\in {\mathcal {X}}_n^*$. For each $i \ge 1$, since dom$f_i$ is compact, the level sets $\{ x\in X_i: f_i(x) \le t\}, t\in {\mathbb {R}}$ are compact. In view of Theorem 6.3.9 [12], $f^*_i$ is continuous and finite at $0_{X_i^*}$. Hence $\phi$ is continuous and finite at $0_{{\mathcal {X}}_n^*}$. By Theorem 1 (page 178) [11] there exists some $\bar{x}_i \in X_i, i=1, ... , n$ such that

$$\begin{aligned} +\infty > \inf (P_n) \ge \sup (D_n)= & {} (\phi +\delta _{K_n^\perp })^* (0_{X_i^*}) \\= & {} \phi ^*(\bar{x}_1, ... , x_n) + \delta ^*_{K_n^\perp } (-(\bar{x}_1, ... , \bar{x}_n))\\= & {} \sum _{i=1}^n f_i(\bar{x}_i) + \delta _{K_n}(-(\bar{x}_1, ... , \bar{x}_n))\\\ge & {} \inf (P_n). \end{aligned}$$

We deduce that $(\bar{x}_1, ... , \bar{x}_n) \in K_n$ and

$$\begin{aligned} +\infty> \sum _{i=1}^n f_i(\bar{x}_i) = \min (P_n) = \sup (D_n) > -\infty . \end{aligned}$$

The proof is complete. $\square$

Lemma 5

Assume (H”) holds, (P) has a feasible solution and $\sup (D)\ge \sup (D_n)$ for $n\ge 1$. Then $\lim _{n\rightarrow \infty } \sup (D_n) = \sup (D)$ and min(P)=sup(D).

Proof

By Proposition 4 and Lemma 4, we have

$$\begin{aligned} \min (P)=\lim _{n\rightarrow \infty } \min (P_n)=\lim _{n\rightarrow \infty } \sup (D_n). \end{aligned}$$

This and the hypothesis $\sup (D)\ge \sup (D_n)$ yield $\min (P) \le \sup (D)$. The latter inequality and the weak duality relation $\min (P) \ge \sup (D)$ give min(P)=sup(D). Equality $\lim _{n\rightarrow \infty } \sup (D_n) = \sup (D)$ is then immediate. $\square$

Here is the main result on strong duality for (D).

Theorem 4

Assume (H”) holds, (P) has a feasible solution and the functions $f_i, i\in {\mathbb {N}}$ are nonnegative. Then min(P)=sup(D).

Proof

We wish to apply Lemma 5. It suffices to prove that sup(D) $\ge \sup (D_n)$ for $n\ge 1$. Indeed, let $(x^*_1, ... ,x^*_n)\in K_n^\perp .$ Denote $(\tilde{x}^*_i)_i\in {\mathcal {X}}$ the vector with $\tilde{x}^*_i=x^*_i, i=1, ... , n$ and $\tilde{x}^*_i=0_{X^*_i}$ for $i>n$. It is clear that $(\tilde{x}^*_i)_i\in K^\perp .$ Moreover, because $f_i, i\in {\mathbb {N}}$ are nonnegative, we have $f^*_i(0_{X^*_i}) \ge 0$ for all $i\ge 1$ and obtain

$$\begin{aligned} \sup (D)\ge -\sum _{i=1}^\infty f^*_i(\tilde{x}^*_i) = -\sum _{i=1}^n f^*_i(x^*_i) - \sum _{i=n+1}^\infty f^*_i(0_{X^*_i}) \ge -\sum _{i=1}^n f^*_i(x^*_i). \end{aligned}$$

Since $(x^*_1, ... ,x^*_n)\in K_n^\perp$ was arbitrarily given, we deduce that sup(D) $\ge \sup (D_n)$ and complete the proof. $\square$

Remark 6

It is worthwhile noticing that in the case $X_i={\mathbb {R}}$ and dom$f_i=[a_i, b_i]$ with $a_i<b_i$, the truncated problems $(P_n)$ and their duals $(D_n)$ coincide with those developed in [8]. Despite this, the finite support dual (D) is different from the dual problem presented in [8], which is given by

$$\begin{aligned} (\mathrm{D'}) \qquad \begin{array}{ll} \sup &{}\; -\sum _{i=1}^\infty f_i^*(x^*_i) \\ \mathrm{s.t.} &{} (x^*_i)_i\in \widehat{K}^\perp , \end{array} \end{aligned}$$

where $\widehat{K}^\perp$ consists of $(x^*_i)_i\in {\mathbb {R}}^{{\mathbb {N}}}$ such that

• (a) $\sum _{i=1}^\infty \vert x^*_i\vert \max \{\vert a_i\vert , \vert b_i\vert \} <+\infty ;$

• (b) $\sum _{i=1}^\infty \vert x^*_i x_i\vert <+\infty$ for all $(x_i)_i\in K$;

• (c) $\sum _{i=1}^\infty x^*_i x_i =0$ for all $(x_i)_i\in K$.

Let us denote the linear subspace of all $(x^*_i)_i\in {\mathbb {R}}^{{\mathbb {N}}}$ satisfying (a) and (b) by $\Lambda$. Then ${\mathcal {X}}^*\subset \Lambda$ and $K^\perp \subset \widehat{K}^\perp \subset \Lambda$. The weak duality relation $\sup (D') \le \inf (P)$ being clear, we obtain that $\sup (D)\le \sup (D')\le \inf (P).$ Under the hypotheses of Theorem 4 we have min(P)=sup(D) and hence min(P)=sup(D’) too. The latter duality relation is essentially the result of Section 3 of [8]. The advantage of (D) over (D’) is the fact that the dual variable of (D) may have only a finite number of nonzero components. It is also interesting to note that the space $\Lambda$ depends on the magnitude of the segments $[a_i,b_i], i\in {\mathbb {N}}$, which means that for each problem one has to deal with its own space of dual variable. Of course, $\Lambda$ becomes ${\mathcal {X}}^*$ (which is ${\mathbb {R}}^{ [{\mathbb {N}}]}$ in this case) when a) holds true for any segments $[a_i, b_i]$, and hence (D’) coincides with (D).

Remark 7

The fact that a finite support dual and a dual with variable of infinite support from the algebraic dual space $({\mathcal {X}})'$ of ${\mathcal {X}}$ may provide the same zero duality gap, has already been presented in [1] for semi-infinite programming problems. This is possible because for $X={\mathbb {R}}$, linear functionals from $({\mathbb {R}}^{{\mathbb {N}}})'$ that are positive on ${\mathbb {R}}_+^{{\mathbb {N}}}$ can be represented by positive finite support vectors from ${\mathbb {R}}_+^{[{\mathbb {N}}]}$ (Lemma 2.1, [1]), which implies that problem with dual variable taken from $({\mathbb {R}}_+^{{\mathbb {N}}})'$ is equivalent to the finite support one. Let us see this in the case of set constrained problem discussed in Sect. 5 when $X_i= {\mathbb {R}}, i\in {\mathbb {N}}$ and K is a convex cone. We consider the following conic optimization problem

$$\begin{aligned} (\mathrm{CP}) \qquad \begin{array}{ll} \inf &{}\; f((x_i)_i) \\ s.t. &{} (x_i)_i \in K, \end{array} \end{aligned}$$

where $f((x_i)_i):= \sum _{i\in {\mathbb {N}}} f_i(x_i)$ with $f_i: {\mathbb {R}} \rightarrow \overline{\mathbb {R}}, i\in {\mathbb {N}}$ proper convex functions, is assumed to be proper, and K is a convex cone in ${\mathbb {R}}^{{\mathbb {N}}}$ that contains ${\mathbb {R}}_+^{{\mathbb {N}}}$. We recall that the algebraic conjugate $h^\#$ of a convex function h on ${\mathbb {R}}^{{\mathbb {N}}}$ is defined by the same formula as for the usual Fenchel conjugate $h^*$, that is,

$$\begin{aligned} h^\# (\phi ):= \sup _{(x_i)_i\in {\mathbb {R}}^{{\mathbb {N}}} }\big ( \phi ((x_i)_i) - h((x_i)_i)\big ), \; \; \phi \in ({\mathbb {R}}^{{\mathbb {N}}})'. \end{aligned}$$

By applying the method of Sect. 5 and by using the algebraic conjugate, we obtain an algebraic dual of (CP) in the form

$$\begin{aligned} (\mathrm{AD}) \qquad \begin{array}{ll} \sup &{}\; - f^\# (\phi ) \\ \mathrm{s.t.} &{} \phi \in K^\#, \end{array} \end{aligned}$$

where $K^\#:= \{ \phi \in ({\mathbb {R}}^{{\mathbb {N}}})' : \phi ((x_i)_i)\ge 0 \mathrm{\; for\; all \; } (x_i)_i\in K\}$. Because ${\mathbb {R}}_+^{{\mathbb {N}}} \subseteq K$, elements of $K^\#$ are positive on ${\mathbb {R}}_+^{{\mathbb {N}}}$. In view of Lemma 2.1, [1], one may express $K^\# = K^\#\cap {\mathbb {R}}_+^{[{\mathbb {N}}]}$. In other words, $K^\#= K^+$ where $K^+:= \{ (x^*_i)_i\in {\mathbb {R}}^{[{\mathbb {N}}]}: \sum _{i\in {\mathbb {N}}} x^*_i x_i \ge 0 \mathrm{\; for\; all \; } (x_i)_i\in K\}$. It is clear that if $\phi \in K^\#$ is represented by $(x^*_i)_i\in {\mathbb {R}}_+^{[{\mathbb {N}}]}$, then $f^\#(\phi ) = f^*((x^*_i)_i)$. In view of Proposition 1, problem (AD) becomes

$$\begin{aligned} \qquad \begin{array}{ll} \sup &{}\; - \sum _{i\in {\mathbb {N}}} f^*_i(x^*_i) \\ \mathrm{s.t.} &{} (x^*_i)_i \in K^+, \end{array} \end{aligned}$$

which is the finite support dual studied in the frame of the present work.

8 Minimum cost flows on infinite networks

In this section we discuss the problem of minimum cost flows on infinite networks introduced and studied in [8, 14]. Let $G:=(N,A)$ denote an infinite directed network in which N is a countable set of nodes and A is the set of arcs consisting of ordered tuples (i, j) for $i,j\in N$. Arc flows are denoted $x_{ij}$ on arc $(i,j)\in A$ and satisfy capacity constraints $0\le x_{ij} \le u_{ij}$ with $u_{ij}\in (0, +\infty )$. Cost functions on arcs are denoted $c_{ij}$ for $(i,j)\in A$ and assumed to be defined and nonnegative on $[0, u_{ij}]$. It is commonly assumed that G is locally finite in the sense that there are only finite number of arcs connected to a node. The minimum cost flow problem on G is formulated as follows

$$\begin{aligned} (\mathrm{P'}) \qquad \begin{array}{ll} \inf &{}\; \sum _{(i,j)\in A} c_{ij}(x_{ij}) \\ s.t. &{} (x_{ij})_{(i,j)}\in Q\\ &{} 0\le x_{ij} \le u_{ij}, (i,j)\in A, \end{array} \end{aligned}$$

where Q is the set of flows that satisfy the supply-demand constraints

$$\begin{aligned} \sum _{\{j: (i,j)\in A\}} x_{ij} - \sum _{\{j: (j,i)\in A\}} x_{ji} = s_i, \; i\in N. \end{aligned}$$

(11)

The real numbers $s_i$ are given and known as sources at nodes $i\in N$. If $s_i>0$, node i is called a supply node; if $s_i<0$, node i is called a demand node; and when $s_i=0$, node i is called a transshipment node. The constraints (11) are named supply, demand and transshipment constraints accordingly. We refer the interested readers to [8, 14] for more details on infinite networks.

Since the set Q in (P’) is not a linear space, Ghate [8] has proposed an approach of introducing a countable set of artificial nodes $N_k$ to every non-transshipment node k, which generates a set $A_k$ of artificial arcs. The capacity constraints on artificial arcs $(i,j)\in A_k$ are set to be $s_k\le x_{ij}\le s_k$. Problem (P’) is then equivalent to the so-called circulation problem

$$\begin{aligned} (\mathrm{P''}) \qquad \begin{array}{ll} \inf &{}\; \sum _{(i,j)\in \tilde{A}} c_{ij}(x_{ij}) \\ s.t. &{} (x_{ij})_{(i,j)}\in \tilde{Q}\\ &{} 0\le x_{ij} \le u_{ij}, (i,j)\in A\\ &{} s_k\le x_{ij}\le s_k, (i,j)\in A_k \mathrm{\; for \;} k \; \mathrm{with\; } s_k\not =0, \end{array} \end{aligned}$$

where $\tilde{A}= A\cup \big (\cup _{k\in N} A_k\big )$, $\tilde{N}= N\cup \big (\cup _{k\in N} N_k\big )$, $c_{ij}(x_{ij})=0$ for $(i,j)\in \tilde{A} \setminus A$, and $\tilde{Q}$ consists of flows on the enlarged network $\tilde{G}:=(\tilde{N}, \tilde{A})$ satisfying the transshipment constraints only

$$\begin{aligned} \sum _{\{j: (i,j)\in \tilde{A}\}} x_{ij} - \sum _{\{j: (j,i)\in \tilde{A}\}} x_{ji} = 0, i\in \tilde{N}. \end{aligned}$$

(12)

Observe that by extending $c_{ij}$ on ${\mathbb {R}}$ with $c_{ij}(x_{ij})=+\infty$ for $x_{ij}\not \in [0,u_{ij}]$ when $(i,j)\in A$ and for $x_{ij}\not =s_k$ when $(i,j)\in A_k$, problem (P”) is an infinite monotropic problem in which $\tilde{Q}$ is a linear subspace of ${\mathbb {R}}^{\tilde{A}}$. We should underline that the sets of artificial nodes and artificial arcs must be chosen so that the enlarged network $\tilde{G}$ remains locally finite. If $\tilde{G}$ is locally finite, for each $i\in \tilde{N}$ the sets $\{j: (i,j)\in \tilde{A}\}$ and $\{j: (j,i)\in \tilde{A}\}$ are finite. Hence, the solution set of each equation in (12) is a closed linear subspace, which implies that $\tilde{Q}$ is a closed subspace of ${\mathbb {R}}^{\tilde{A}}$ (see also Lemma 7.1 [8]). When $\tilde{G}$ is not locally finite, $\tilde{Q}$ is not necessarily closed. Of course, if $\tilde{Q}$ is closed, then the results of Sect. 7 can be applied to (P”). Every optimal solution of (P”) produces an optimal solution of (P’) by omitting all flows on artificial arcs. Moreover, (P’) and (P”) have the same optimal value. We notice also that despite the introduction of countable numbers of artificial nodes and arcs, $(\tilde{G})$ remains a countably infinite network. This being said, when one examines a finite subnetwork of G, its associated enlarged subnetwork is no longer finite because of infinite artificial nodes and flows added to that subnetwork.

We now present an approach to solve (P’) without using the circulation problem. Fix a solution $(\widehat{x}_{ij})_{ij}$ from Q and define K to be the set of flows that satisfy the transshipment constraints

$$\begin{aligned} \sum _{\{j: (i,j)\in A\}} x_{ij} - \sum _{\{j: (j,i)\in A\}} x_{ji} = 0, i\in N. \end{aligned}$$

Then $Q= (\widehat{x}_{ij})_{ij} +K$ and (P’) is equivalent to the following problem

$$\begin{aligned} (\mathrm{\widehat{P}}) \qquad \begin{array}{ll} \inf &{}\; \sum _{(i,j)\in A} \widehat{c}_{ij}(y_{ij}) \\ s.t. &{} (y_{ij})_{ij}\in K, \end{array} \end{aligned}$$

where

$$\begin{aligned} \widehat{c}_{ij} (y_{ij}) = \left\{ \begin{array}{ll} c_{ij}(y_{ij}+\widehat{x}_{ij}) &{} \; \mathrm{if }\; y_{ij}\in [- \widehat{x}_{ij}, u_{ij}-\widehat{x}_{ij}] \\ +\infty &{} \; \mathrm{else.\;} \end{array} \right. \end{aligned}$$

According to the construction of dual developed in Sect. 5, the dual of $(\widehat{P})$ is given by

$$\begin{aligned} (\mathrm{\widehat{D}}) \qquad \begin{array}{ll} \sup &{}\; - \sum _{(i,j)\in A} \big ( c^*_{ij}(y^*_{ij}) - \langle y^*_{ij}, \widehat{x}_{ij}\rangle \big ) \\ s.t. &{} (y^*_{ij})_{ij}\in K^\perp . \end{array} \end{aligned}$$

By the technique of layers [14, 22] one decomposes N into finite subsets $N_n, n\ge 1$ such that $N_n\subset N_{n+1}$ and $N= \cup _{n\ge 1} N_n$. The sets of arcs connected to the nodes of $N_n$ are denoted by $A_n, n\ge 1$. The sets $K_n$ are defined from K as before; that is, $(x_{ij})_{(i,j)\in A_n} \in K_n$ if and only if there is some $(y_{ij})_{(i,j)\in A} \in K$ such that $x_{ij}=y_{ij}$ for all $(i,j)\in A_n$. This produces a sequence of truncated problems

$$\begin{aligned} (\mathrm{\widehat{P}_n}) \qquad \begin{array}{ll} \inf &{}\; \sum _{(i,j)\in A_n} \widehat{c}_{ij}(y_{ij}) \\ s.t. &{} (y_{ij})_{ij}\in K_n, \end{array} \end{aligned}$$

and their duals

$$\begin{aligned} (\mathrm{\widehat{D}}_n) \qquad \begin{array}{ll} \sup &{}\; - \sum _{(i,j)\in A_n} \big ( c^*_{ij}(y^*_{ij}) - \langle y^*_{ij}, \widehat{x}_{ij}\rangle \big ) \\ s.t. &{} (y^*_{ij})_{ij}\in K_n^\perp . \end{array} \end{aligned}$$

Proposition 5

Assume that (P’) has a feasible flow and that the cost functions $c_{ij}$ are convex, continuous and nonnegative functions on $[0, u_{ij}], \; (i,j)\in A$ and $\sum _{(i,j)\in A} \Vert c_{ij}\Vert <+\infty$. Then $\min (P') = \sup (\widehat{D})$.

Proof

Since (P’) has a feasible solution, $(\widehat{P})$ has a feasible solution too. Moreover, $\Vert \widehat{c}_{ij}\Vert = \Vert c_{ij}\Vert$ for all $(i,j)\in A$. Hence the functions $\widehat{c}_{ij}, (i,j)\in A$ satisfy (H”). Furthermore, since $\widehat{c}_{ij}(y_{ij}) = c_{ij}(y_{ij}+ \widehat{x}_{ij}) \ge 0$ on dom$\widehat{c}_{ij}= [- \widehat{x}_{ij}, u_{ij}-\widehat{x}_{ij}]$, we may apply Theorem 4 to obtain $\min (\widehat{P}) = \sup (\widehat{D})$, which gives $\min (P') = \sup (\widehat{D})$ because (P’) and $(\widehat{P})$ have the same optimal value. $\square$

Remark 8

We wish to highlight the fact that the dual problem $(\widehat{D})$ differs in two aspects from the dual problem studied in [8]. First, the dual $(\widehat{D})$ is constructed for $(\widehat{P})$ while the dual of [8] is constructed for the circulation problem. Second, the dual variable of $(\widehat{D})$ takes values in ${\mathbb {R}}^{[A]}$ that only have finite support, while the dual variable of [8] takes values in a particular subspace of ${\mathbb {R}}^{A}$ with infinite support in general.

Remark 9

The conclusion of Proposition 5 can also be obtained from the results of Sect. 5, without recourse to truncated problems. In fact, let us express $(\widehat{P})$ in form of unconstrained problem

$$\begin{aligned} \qquad \begin{array}{ll} \inf &{}\; \sum _{(i,j)\in A} \widehat{c}_{ij}(y_{ij}) + \delta _K ( (y_{ij})_{ij})\\ &{} (y_{ij})_{ij} \in {\mathbb {R}}^{A}. \end{array} \end{aligned}$$

Denote the set $\sum _{(i,j)\in A}^w M_{ij}\big (\mathrm{epi}\; \widehat{c}_{ij}\big ) + K\times {\mathbb {R}}_+$ by Z. We prove that this set is closed regarding the set $\{0_{{\mathcal {X}}} \}\times {\mathbb {R}}$. Assume $\{z^\nu \}_\nu$ is a sequence in Z converging to $(0_{{\mathcal {X}}}, \bar{t})$ with $\bar{t}\in {\mathbb {R}}$. Let $z^\nu = \sum _{(i,j)\in A} M_{ij} (y^\nu _{ij}, r^\nu _{ij})+ (b^\nu , t^\nu )$ with $(y^\nu _{ij}, r^\nu _{ij}) \in \mathrm{epi} \widehat{c}_{ij}$, $b^\nu \in K$ and $t^\nu \in {\mathbb {R}}_+$ for all $\nu$ and for $(i,j)\in A$. Then $(y_{ij}^\nu )_\nu$ is a sequence in $[- \widehat{x}_{ij}, u_{ij}-\widehat{x}_{ij}]$ and $r^\nu _{ij}\ge 0$. Since $t^\nu \ge 0$, we may assume that $\{r^\nu _{ij}\}_\nu$ converges to some $r_{ij}\ge 0, \; (i,j)\in A,$ and $\{t^\nu \}_\nu$ converges to $t:=\bar{t}- \sum _{(i,j)\in A} r_{ij}\in {\mathbb {R}}_+$. Furthermore, as the epigraph of $\widehat{c}_{ij}$ is closed, we may also suppose that $\{(y^\nu _{ij}, r^\nu _{ij})\}_\nu$ converges to some $(y_{ij}, r_{ij})\in \mathrm{epi} \widehat{c}_{ij}$. Then $\{b^\nu \}_\nu$ converges to $b:=- \sum _{(i,j)\in A} m_{ij} y_{ij}\in K$ due to the fact that K is closed. We deduce that $(0_{{\mathcal {X}}}, \bar{t})= \sum _{(i,j)\in A} M_{ij}(y_{ij}, r_{ij}) + (b, t) \in Z$. By this, Z is closed regarding the set $\{0_{{\mathcal {X}}} \}\times {\mathbb {R}}$. In view of Theorem 2, $\min (\widehat{P})= \sup (\widehat{D})$, and hence $\min (P')= \sup (\widehat{D})$.