9.19. Infimal Convolution#

Note

Some results in this section appear without complete proof at the moment. They have been collected from various sources. The proofs will be added later.

9.19.1. Definition#

Definition 9.82 (Infimal convolution)

Let \(\VV\) be a real vector space. Let \(f, g : \VV \to \ERL\) be extended real-valued functions. Their infimal convolution, denoted by \(f \infimal g : \VV \to \ERL\), is defined as

(9.11)#\[(f \infimal g)(\bx) \triangleq \inf \{ f(\by) + g(\bz) \ST \by, \bz \in \VV, \by + \bz = \bx \}. \]

The infimal convolution of \(f\) with \(g\) is called exact at \(\bx\) if the infimum in (9.11) is attained at some \(\by, \bz \in \VV\) such that \(\by + \bz = \bx\).

The infimal convolution is called exact if it is attained at every \(\bx \in X\).

Remark 9.17 (Alternative definitions)

It is easy to see that

\[ (f \infimal g)(\bx) = \inf \{ f(\by) + g(\bz) \ST \by, \bz \in \VV, \by + \bz = \bx, f(\by) < \infty, g(\bz) < \infty \}. \]

Another formulation is

\[ (f \infimal g)(\bx) = \inf \{ f(\by) + g(\bx - \by) \ST \by \in \VV \}. \]

This definition is reminiscent of the convolution operation in signal processing. The word infimal reminds of the infimum appearing in the definition. This is the motivation for the name infimal convolution.

Infimal convolution is also known as epigraphical addition because performing an infimal convolution of \(f\) and \(g\) amounts to the adding of the strict epigraphs of \(f\) and \(g\). Recall from Definition 2.52 that the strict epigraph of a function \(f : \VV \to \ERL\) is given by

\[ \epi_s f \triangleq \{ (\bx,t) \in \VV \oplus \RR \ST f(\bx) < t \}. \]

We show in Property 9.42 that \(\epi_s f \infimal g = \epi_s f + \epi_s g\).

From the definition, it is clear that \(f \infimal g\) is the largest of all the functions \(h: \VV \to \ERL\) satisfying

\[ h(\by + \bz) \leq f(\by) + g(\bz) \Forall \by, \bz \in X. \]

Example 9.87 (Cost minimization)

Consider a situation where a person sources a certain product from two different manufactures.

  1. The person needs to acquire \(x\) total quantity.

  2. The total supply is given by the equation \(x = y + z\) where \(y\) is the quantity sourced from manufacturer A and \(z\) is the quantity sourced from manufacture B.

  3. Suppose the total cost of acquisition from manufacture A is given by a function \(f(y)\). It may not be linear as the manufacturer may have different levels of discounts as \(y\) increases.

  4. Similarly, the cost of acquisition from manufacture B is given by the function \(g(z)\).

  5. Then the total cost is given by \(f(y) + g(z)\) subject to the condition that \(y + z = x\).

  6. Then the cost minimization problem is given by

    \[ h(x) = \inf \{ f(y) + g(z) \ST x = y + z \} = (f \infimal g) (x). \]

  7. We will also be interested in the set of solutions to the infimal problem; i.e.,

    \[ \{ (y,z ) \ST f(y) + g(z) = (f \infimal g) (x) \}. \]

9.19.2. Basic Properties#

9.19.2.1. Domain#

Property 9.40 (Domain of infimal convolution)

Let \(f, g : \VV \to \ERL\) be given extended valued functions. Then

\[ \dom f \infimal g = \dom f + \dom g. \]

Proof. Let \(\bz \in \dom f + \dom g\).

  1. Then there exist \(\bx \in \dom f\) and \(\by \in \dom g\) such that \(\bz = \bx + \by\).

  2. Then \(f(\bx) < \infty\) and \(g(\by) < \infty\).

  3. By definition of infimal convolution

    \[ (f \infimal g)(\bz) \leq f(\bx) + g(\by) < \infty. \]

  4. Hence \(\bz \in \dom f \infimal g\).

  5. Hence \(\dom f + \dom g \subseteq \dom f \infimal g\).

For the converse, let \(\bz \in \dom f \infimal g\).

  1. Then \((f \infimal g)(\bz) < \infty\).

  2. First consider the case where \((f \infimal g)(\bz) = t \in \RR\).

  3. Then for any \(\epsilon > 0\), there exist \(\bx, \by\) with \(\bx + \by = \bz\) such that

    \[ t \leq f(\bx) + g(\by) \leq t + \epsilon. \]

  4. Since \(f(\bx) + g(\by)\) is finite, hence \(f(\bx) < \infty\) and \(g(\by) < \infty\).

  5. Hence \(\bx < \dom f\) and \(\by \in \dom g\).

  6. Thus \(\bz = \bx + \by \in \dom f + \dom g\).

  7. Now consider the case where \((f \infimal g)(\bz) = -\infty\).

  8. Then for every \(M \in \RR\), there exist \(\bx, \by\) with \(\bx + \by = \bz\) such that

    \[ f(\bx) + g(\by) \leq M. \]

  9. Thus \(f(\bx) < \infty\) and \(g(\by) < \infty\) for such pairs of \(\bx, \by\).

  10. Consequently \(\bz = \bx + \by \in \dom f + \dom g\).

  11. Combining the two cases \(\dom f \infimal g \subseteq \dom f + \dom g\).

Finally

  1. We have already shown that \(\dom f + \dom g \subseteq \dom f \infimal g\).

  2. Thus \(\dom f + \dom g = \dom f \infimal g\).

9.19.2.2. Epigraph#

Property 9.41 (Connection with epigraph)

\[ (f \infimal g) (\bx) = \inf \{ r \in \RR \ST (\bx, r) \in \epi f + \epi g \}. \]

Proof. Let \(t = (f \infimal g) (\bx)\). Define \(S = \{ r \in \RR \ST (\bx, r) \in \epi f + \epi g \}\). We need to show that \(t\) is the greatest lower bound of the set \(S\).

  1. Let \((\bx,r) \in \epi f + \epi g\).

  2. Then there exists \((\by, r_1) \in \epi f\) and \((\bz, r_2) \in \epi g\) so that \(\bx = \by + \bz\) and \(r = r_1 + r_2\).

  3. Thus \(f(\by) + g(\bz) \leq r_1 + r_2 = r\) (by epigraphs).

  4. By infimal convolution definition \(t \leq f(\by) + g(\bz) \leq r\).

  5. Thus we have shown that \(t \leq r\) if \((\bx, r) \in \epi f + \epi g\).

  6. Thus \(t\) is a lower bound of the set \(S\).

  7. Now choose any \(\epsilon > 0\).

  8. Then there exists \(\by \in \dom f\) and \(\bz \in \dom g\) with \(\bx = \by + \bz\) such that

    \[ f(\by) + g(\bz) \leq t + \epsilon. \]

  9. Note that \((\by, f(\by)) \in \epi f\) and \((\bz, g(\bz)) \in \epi g\).

  10. Hence \((\by + \bz, f(\by) + f(\bz)) \in \epi f + \epi g\).

  11. Consequently \((\by + \bz, t + \epsilon) \in \epi f + \epi g\).

  12. Replacing \(\bx = \by + \bz\), we have \((\bx, t + \epsilon) \in \epi f + \epi g\).

  13. Thus, for every \(\epsilon > 0\), \(t + \epsilon \in S\).

  14. Hence \(t\) must be the greatest lower bound of the set \(S\).

  15. In other words, \(t = \inf S\) as desired.

Property 9.42 (Strict epigraph of infimal convolution)

Let \(f, g : \VV \to \ERL\) be given extended valued functions. Then

\[ \epi_s f \infimal g = \epi_s f + \epi_s g. \]

Proof. We show the set inclusion from both sides.

  1. Let \((\bx, r) \in \epi_s f \infimal g\).

  2. Then \((f \infimal g)(\bx) < r\).

  3. Then there exist \(\by \in \dom f\) and \(\bz \in \dom g\) with \(\bx = \by + \bz\) such that

    \[ f(\by) + g(\bz) < r. \]

    This is directly from the definition of infimal convolution.

  4. Consequently, we can split \(r\) as \(r = r_1 + r_2\) such that \(f(\by) < r_1\) and \(g(\bz) < r_2\).

    1. Let \(s = f(\by)\), \(t = g(\bz)\).

    2. Let \(d = r - (s + t) > 0\).

    3. Let \(e = \frac{d}{2} > 0\).

    4. Let \(r_1 = s + e\) and \(r_2 = t + e\).

    5. Then \(r_1 + r_2 = s + t + 2e = s + t + d = r\).

    6. Also \(f(\by) = s < r_1\) and \(g(\bz) = t < r_2\).

  5. Then \((\by, r_1) \in \epi_s f\) and \((\bz, r_2) \in \epi_s g\) by definition of strict epigraphs.

  6. Hence \((\by + \bz, r_1 + r_2) = (\bx, r) \in \epi_s f + \epi_s g\).

  7. Thus \(\epi_s f \infimal g \subseteq \epi_s f + \epi_s g\)

For the converse

  1. Let \((\bx, r) \in \epi_s f + \epi_s g\).

  2. Then there is \((\by, r_1) \in \epi_s f\) and \((\bz, r_2) \in \epi_s g\) so that

    \[ \bx = \by + \bz \text{ and } r = r_1 + r_2. \]

  3. Thus \(f(\by) < r_1\) and \(g(\bz) < r_2\).

  4. Thus \(f(\by) + g(\bz) < r_1 + r_2 = r\).

  5. Hence \((f \infimal g)(\bx) \leq f(\by) + g(\bz) < r\).

  6. Hence \((\bx, r) \in \epi_s f \infimal g\).

  7. Hence \(\epi_s f + \epi_s g \subseteq \epi_s f \infimal g\).

Property 9.43 (Epigraph of infimal convolution)

Let \(f, g : \VV \to \ERL\) be given functions. Then

\[ \epi f + \epi g \subseteq \epi f \infimal g. \]

The equality holds if and only if the infimal convolution is exact at each \(\bx \in \VV\) where \((f \infimal g) (\bx) \in \RR\).

Proof. We first show the inclusion.

  1. Let \((\bx, r) \in \epi f + \epi g\).

  2. Then there is \((\by, r_1) \in \epi f\) and \((\bz, r_2) \in \epi g\) so that

    \[ \bx = \by + \bz \text{ and } r = r_1 + r_2. \]

  3. Thus \(f(\by) \leq r_1\) and \(g(\bz) \leq r_2\).

  4. Thus \(f(\by) + g(\bz) \leq r_1 + r_2 = r\).

  5. Hence \((f \infimal g)(\bx) \leq f(\by) + g(\bz) \leq r\).

  6. Hence \((\bx, r) \in \epi f \infimal g\).

  7. Hence \(\epi f + \epi g \subseteq \epi f \infimal g\).

Next we show that the reverse inclusion holds if infimal convolution is exact at each \(\bx \in \VV\) where \((f \infimal g) (\bx) \in \RR\).

  1. Let \((\bx, r) \in \epi f \infimal g\).

  2. Then \((f \infimal g)(\bx) \leq r\).

  3. Consider first the case where \((f \infimal g)(\bx) = -\infty\).

  4. Then for any \(M \in \RR\), there exist \(\by \in \dom f\) and \(\bz \in \dom g\) with \(\bx = \by + \bz\) such that \(f(\by) + f(\bz) < M\).

  5. In particular, there exist \(\by, \bz\) so that \(f(\by) + f(\bz) < r\).

  6. Hence \((\bx, r) \in \epi f + \epi g\).

  7. Now if \((f \infimal g)(\bx) \in \RR\) then the infimal convolution is exact.

  8. Since the infimal convolution is exact, hence there exist \(\by \in \dom f\) and \(\bz \in \dom g\) with \(\bx = \by + \bz\) such that

    \[ f(\by) + g(\bz) = (f \infimal g)(\bx) \leq r. \]

    This is directly from the definition of infimal convolution.

  9. Consequently, we can split \(r\) as \(r = r_1 + r_2\) such that \(f(\by) \leq r_1\) and \(g(\bz) \leq r_2\).

  10. Then \((\by, r_1) \in \epi f\) and \((\bz, r_2) \in \epi g\) by definition of epigraphs.

  11. Hence \((\by + \bz, r_1 + r_2) = (\bx, r) \in \epi f + \epi g\).

  12. Thus \(\epi_s f \infimal g \subseteq \epi f + \epi g\).

Finally, to show that this condition is necessary, assume that there exists a point \(\bx \in \VV\) where \((f \infimal g) (\bx) \in \RR\) and the infimal convolution is not exact.

  1. Let \(t = (f \infimal g) (\bx)\).

  2. Then \((\bx, t) \in \epi f \infimal g\).

  3. Since the infimal convolution is not exact, hence for any \(\by \in \dom f\) and \(\bz \in \dom g\) with \(\bx = \by + \bz\)

    \[ t < f(\by) + g(\bz). \]

  4. For contradiction, assume that \((\bx, t) \in \epi f + \epi g\).

  5. Then there exist \((\by, t_1) \in \epi f\) and \((\bz, t_2) \in \epi g\) so that \(\bx = \by + \bz\) and \(t = t_1 + t_2\).

  6. Thus \(f(\by) \leq t_1\) and \(g(\bz) \leq t_2\).

  7. Thus \(f(\by) + g(\bz) \leq t_1 + t_2 = t\).

  8. We have arrived at a contradiction.

  9. Hence \((\bx, t) \notin \epi f + \epi g\).

9.19.2.3. Convexity#

Theorem 9.274 (Infimal convolution of convex functions)

Let \(f : \VV \to \RERL\) be a proper convex function and \(g : \VV \to \RR\) be a real valued convex function. Then \(f \infimal g\) is convex.

Proof. Define \(h(\bx, \by) = f(\by) + g(\bx - \by)\).

  1. Since \(f\) and \(g\) are convex, hence \(h\) is convex.

  2. We can easily show that for any \(\bx \in \VV\), there exists \(\by \in \VV\) such that \(h(\bx, \by) < \infty\).

    1. Pick any \(\bx \in \VV\).

    2. Choose any \(\by \in \dom f\).

    3. Then \(f(\by) < \infty\).

    4. Since \(g\) is real valued, hence \(g(\bx - \by) < \infty\).

    5. Thus \(h(\bx, \by) = f(\by) + g(\bx - \by) < \infty\).

  3. Then due to Theorem 9.118

    \[ (f \infimal g) (\bx) = \inf_{\by \in \VV} h(\bx, \by) = \inf_{\by \in \VV} [f(\by) + g(\bx - \by)] \]

    is convex as a partial minimization of the function \(h(\bx, by)\) w.r.t. \(\by\).

It is still possible that \(f \infimal g\) is not a proper function and may be equal to \(-\infty\) at some \(\bx\).

Example 9.88 (Set distance function as infimal convolution)

Let \(C \subseteq \VV\) be a nonempty convex set.

  1. The indicator function \(I_C\) is a proper convex function.

  2. The norm function \(\| \cdot \|\) is a real valued convex function.

  3. By Theorem 9.274, \(I_C \infimal \| \cdot \|\) is convex.

  4. But then

    \[ (I_C \infimal \| \cdot \|) (\bx) = \inf_{\by \in \VV} (I_C(\by) + \| \bx - \by \|) = \inf_{\by \in C} \| \bx - \by \| = d_C(\bx). \]

  5. Thus \(d_C\) (the distance function to a convex set) is convex.

9.19.3. Conjugates#

Theorem 9.275 (Conjugate of infimal convolution of proper functions)

For two proper functions \(h_1, h_2: \VV \to \RERL\), it holds that:

\[ (h_1 \infimal h_2)^* = h_1^* + h_2^*. \]

Proof. Pick \(\by \in \VV^*\). Then

\[\begin{split} (h_1 \infimal h_2)^* (\by) &= \sup_{\bx \in \VV} \{ \langle \bx, \by \rangle - (h_1 \infimal h_2)(\bx) \}\\ &= \sup_{\bx \in \VV} \{ \langle \bx, \by \rangle - \inf_{\bu \in \VV}(h_1(\bu) + h_2(\bx - \bu) ) \}\\ &= \sup_{\bx \in \VV} \sup_{\bu \in \VV} \{ \langle \bx, \by \rangle - h_1(\bu) - h_2(\bx - \bu) \}\\ &= \sup_{\bu \in \VV} \sup_{\bx \in \VV} \{ \langle \bx - \bu, \by \rangle + \langle \bu, \by \rangle - h_1(\bu) - h_2(\bx - \bu) \}\\ &= \sup_{\bu \in \VV} \{ \sup_{\bx \in \VV} \{ \langle \bx - \bu, \by \rangle - h_2(\bx - \bu) \} + \langle \bu, \by \rangle - h_1(\bu) \}\\ &= \sup_{\bu \in \VV} \{h_2^*(\by) + \langle \bu, \by \rangle - h_1(\bu) \}\\ &= h_2^*(\by) + \sup_{\bu \in \VV} \{\langle \bu, \by \rangle - h_1(\bu) \}\\ &= h_2^*(\by) + h_1^*(\by) \\ &= (h_1^* + h_2^*) (\by). \end{split}\]

Theorem 9.276 (Conjugate of sum of convex functions)

Let \(h_1 : \VV \to \RERL\) be a proper convex function and \(h_2 : \VV \to \RR\) be a real valued convex function. Then

\[ (h_1 + h_2)^* = h_1^* \infimal h_2^*. \]

Proof. The proof is more complicated and requires the application of Fenchel’s duality theorem (Theorem 10.85).

  1. Pick any \(\by \in \VV^*\).

  2. Elaborating the conjugate function

    \[\begin{split} (h_1 + h_2)^* (\by) &= \sup_{\bx \in \VV} \{ \langle \bx, \by \rangle - (h_1 + h_2)(\bx) \}\\ &= \sup_{\bx \in \VV} \{ \langle \bx, \by \rangle - h_1(\bx) - h_2(\bx) \}\\ &= -\inf_{\bx \in \VV} \{ h_1(\bx) + h_2(\bx) - \langle \bx, \by \rangle \}\\ &= -\inf_{\bx \in \VV} \{ h_1(\bx) + g(\bx) \}\\ \end{split}\]

    where \(g(\bx) = h_2(\bx) - \langle \bx, \by \rangle\).

  3. We note that since \(h_2\) is a real valued convex function, hence \(g\) is also a real valued convex function.

  4. We note that

    \[ (\relint \dom h_1) \cap (\relint \dom g) = (\relint \dom h_1) \cap \VV = \relint \dom h_1 \neq \EmptySet. \]

  5. Applying the Fenchel’s duality theorem (Theorem 10.85),

    \[ \inf_{\bx \in \VV} \{ h_1(\bx) + g(\bx) \} = \sup_{\bz \in \VV} \{ -h_1^*(\bz) - g^*(-\bz) \}. \]

  6. Further

    \[\begin{split} g^*(-\bz) &= \sup_{\bx \in \VV} \{ \langle \bx, - \bz \rangle - g(\bx) \}\\ &= \sup_{\bx \in \VV} \{ \langle \bx, - \bz \rangle - h_2(\bx) + \langle \bx, \by \rangle \}\\ &= \sup_{\bx \in \VV} \{ \langle \bx, \by - \bz \rangle - h_2(\bx) \}\\ &= h_2^*(\by - \bz ). \end{split}\]

  7. Consequently

    \[\begin{split} (h_1 + h_2)^* (\by) &= -\inf_{\bx \in \VV} \{ h_1(\bx) + g(\bx) \} \\ &= - \sup_{\bz \in \VV} \{ -h_1^*(\bz) - g^*(-\bz) \}\\ &= \inf_{\bz \in \VV} \{h_1^*(\bz) + g^*(-\bz) \}\\ &= \inf_{\bz \in \VV} \{h_1^*(\bz) + h_2^*(\by - \bz )\} \\ &= (h_1^* \infimal h_2^*) (\by). \end{split}\]

This completes the proof.

Corollary 9.28 (Function sum as conjugate of infimal convolution of conjugates)

Let \(h_1 : \VV \to \RERL\) be a proper closed convex function and \(h_2 : \VV \to \RR\) be a real valued convex function. Then

\[ h_1 + h_2 = (h_1^* \infimal h_2^*)^*. \]

Proof. We proceed as follows.

  1. Since \(h_1\) is proper and \(h_2\) is real valued, hence \(h_1 + h_2\) is proper.

  2. Since both \(h_1\) and \(h_2\) are closed functions, hence \(h_1 + h_2\) is closed.

  3. Since both \(h_1\) and \(h_2\) are convex functions, hence \(h_1 + h_2\) is convex.

  4. Thus \(h_1 + h_2\) is a proper, closed convex function.

  5. By Theorem 9.242,

    \[ (h_1 + h_2)^{**} = h_1 + h_2. \]

  6. By Theorem 9.276,

    \[ (h_1 + h_2)^* = h_1^* \infimal h_2^*. \]

  7. Hence

    \[ h_1 + h_2 = (h_1 + h_2)^{**} = [(h_1 + h_2)^*]^* = [h_1^* \infimal h_2^*]^*. \]

Theorem 9.277 (Representation of the infimal convolution by conjugates)

Let \(h_1 : \VV \to \RERL\) be a proper convex function and \(h_2 : \VV \to \RR\) be a real valued convex function. Suppose \(h_1 \infimal h_2\) is a real valued function. Then

\[ h_1 \infimal h_2 = (h_1^* + h_2^*)^*. \]

Proof. We proceed as follows.

  1. By Theorem 9.275

    \[ (h_1 \infimal h_2)^* = h_1^* + h_2^*. \]

  2. Since \(h_1\) is proper and convex and \(h_2\) is real valued and convex, hence by Theorem 9.274, \(h_1 \infimal h_2\) is convex.

  3. By hypothesis \(h_1 \infimal h_2\) is also real valued.

  4. Thus \(h_1 \infimal h_2\) is proper and closed.

  5. Since \(h_1 \infimal h_2\) is proper, closed and convex; hence by Theorem 9.242

    \[ (h_1 \infimal h_2)^{**} = h_1 \infimal h_2. \]

  6. Hence

    \[ h_1 \infimal h_2 = [(h_1 \infimal h_2)^*]^* = [h_1^* + h_2^*]^*. \]

9.19.4. Convexity#

An interesting application of constructing a convex function from a convex set in \(\VV \oplus \RR\) is the fact that addition of epigraphs leads to another convex function. This is also known as infimal convolution.

Theorem 9.278 (Infimal convolution)

Let \(f_1, \dots, f_m : \VV \to \RERL\) be proper convex functions. Let \(f : \VV \to \RERL\) be defined as

\[ f(\bx) = \inf \{f_1(\bx_1) + \dots + f_m(\bx_m) \ST \bx_i \in \VV, \bx_1 + \dots + \bx_m = \bx \}. \]

Then, \(f\) is a proper convex function.

Proof. Let \(F_i = \epi f_i\) and \(F = F_1 + \dots + F_m\).

  1. Since \(f_i\) is convex, hence \(F_i = \epi f_i\) are convex sets for \(i=1,\dots,m\).

  2. Sum of convex sets is convex. Hence, \(F\) is a convex set.

  3. By definition of \(F\), \((\bx, t) \in F\) if and only if there exists \(\bx_i \in \VV\) and \(t_i \in \RR\) with \((\bx_i, t_i) \in F_i\) such that \(\bx = \bx_1 + \dots + \bx_m\) and \(t = t_1 + \dots + t_m\).

  4. It follows that \(f_i(\bx_i) \leq t_i\) for \(i=1,\dots,m\).

  5. Consequently, \(f_1(\bx_1) + \dots + f_m(\bx_m) \leq t_1 + \dots + t_m\).

  6. By Theorem 9.111, a function \(g: \VV \to \RERL\) defined as

    \[ g(\bx) \triangleq \inf \{t \in \RR \ST (\bx, t) \in F \} \]

    is a proper convex function.

  7. Let \(T = \{t \in \RR \ST (\bx, t) \in F \}\). Then \(g(\bx) = \inf T\).

  8. We note that

    \[ T = \{t \ST (\bx_i, t_i) \in F_i, t = t_1 + \dots + t_m, \bx = \bx_1 + \dots + \bx_m \}. \]

  9. We claim that \(g = f\).

To show that \(g=f\), we need to do the following.

  1. Show that \(\dom f = \dom g\).

  2. Then, show that for every \(\bx \in \dom f\), \(f(\bx) = g(\bx)\).

Assume that \(\bx \notin \dom g\).

  1. Then, there is no \(t \in \RR\) such that \((\bx, t) \in F\).

  2. Thus, there is no \((\bx_i, t_i) \in F_i\) for \(i=1,\dots,m\) such that \(\bx = \bx_1 + \dots + \bx_m\).

  3. Thus, for every \(\bx_i \in \VV\) such that \(\bx = \bx_1 + \dots + \bx_m\) there is at least one \(i\) such that there is no \(t_i \in \RR\) such that \((\bx_i, t_i) \in F_i\).

  4. Thus, for every \(\bx_i \in \VV\) such that \(\bx = \bx_1 + \dots + \bx_m\) there is at least one \(i\) such that \(f_i(\bx_i) = \infty\).

  5. Thus, for every \(\bx_i \in \VV\) such that \(\bx = \bx_1 + \dots + \bx_m\), \(f_1(\bx_1) + \dots + f_m(\bx_m) = \infty\).

  6. Thus, \(f(\bx) = \infty\).

  7. Thus, \(\bx \notin \dom f\).

Assume that \(\bx \notin \dom f\).

  1. Then, \(f(\bx) = \infty\).

  2. Thus, for every \(\bx_i \in \VV\) such that \(\bx = \bx_1 + \dots + \bx_m\), \(f_1(\bx_1) + \dots + f_m(\bx_m) = \infty\).

  3. Thus, for every \(\bx_i \in \VV\) such that \(\bx = \bx_1 + \dots + \bx_m\), there exists at least one \(i\) such that \(f_i(\bx_i) = \infty\).

  4. Thus, for every \(\bx_i \in \VV\) such that \(\bx = \bx_1 + \dots + \bx_m\), there exists at least one \(i\) such that \(\bx_i \notin \dom f_i\).

  5. Thus, for every \(\bx_i \in \VV\) such that \(\bx = \bx_1 + \dots + \bx_m\), there exists at least one \(i\) such that there is no \(t_i \in \RR\) with \((\bx_i, t_i) \in F_i\).

  6. Thus, there is no \((\bx_i, t_i) \in F_i\) for \(i=1,\dots,m\) such that \(\bx = \bx_1 + \dots + \bx_m\).

  7. Thus, there is no \(t \in \RR\) such that \((\bx, t) \in F\).

  8. Thus, \(\bx \notin \dom g\).

Thus, \(\bx \notin \dom f \iff \bx \notin \dom g\). Thus, \(\dom f = \dom g\).

Let us now consider some \(\bx \in \dom f = \dom g\). Then, both \(f(\bx)\) and \(g(\bx)\) are finite. Our goal is to show that \(f(\bx) = g(\bx)\).

We first show that \(f(\bx) \leq g(\bx)\).

  1. For every \(\bx_i \in \VV\) with \(\bx = \bx_1 + \dots + \bx_m\), and \(f_i(\bx_i)\) finite, we have:

    \[ f(\bx) \leq f_1(\bx_1) + \dots + f_m(\bx_m). \]

  2. Thus, for every \((\bx_i, t_i) \in F_i\) with \(\bx = \bx_1 + \dots + \bx_m\), we have

    \[ f(\bx) \leq f_1(\bx_1) + \dots + f_m(\bx_m) \leq t_1 + \dots + t_m. \]

  3. Thus, for every \((\bx, t) \in F\) with \((\bx_i, t_i) \in F_i\), \(\bx = \bx_1 + \dots + \bx_m\), \(t = t_1 + \dots + t_m\), we have

    \[ f(\bx) \leq t. \]

  4. Taking the infimum on the R.H.S. over the set \(T\), we get

    \[ f(\bx) = f(\bx) \leq g(\bx) = z. \]

Now, for contradiction, assume that \(f(\bx) < g(\bx)\).

  1. For every \(t \in \RR\) such that \((\bx, t) \in F\), we have \(g(\bx) \leq t\).

  2. Thus, for every \((\bx_i, t_i) \in F_i\) with \(\bx = \bx_1 + \dots + \bx_m\), we have

    \[ g(\bx) \leq t_1 + \dots + t_m. \]

  3. Then, for every \((\bx_i, t_i) \in F_i\) with \(\bx = \bx_1 + \dots + \bx_m\), we have

    \[ f(\bx) < t_1 + \dots + t_m. \]

  4. Thus, there exists \(r > 0\) such that for every \((\bx_i, t_i) \in F_i\) with \(\bx = \bx_1 + \dots + \bx_m\), we have

    \[ f(\bx) + r \leq t_1 + \dots + t_m. \]

TO BE COMPLETED.