(sec:cvx:infimal)=
# 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.
```

## Definition

````{prf:definition} Infimal convolution
:label: def-cvx-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

```{math}
:label: eq-cvx-infimal-convolution
(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 {eq}`eq-cvx-infimal-convolution` 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$.
````

```{prf:remark} Alternative definitions
:label: rem-cvx-infimal-convolution-2

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 {prf:ref}`def-bra-strict-epigraph` 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 {prf:ref}`res-cvx-infimal-strict-epi` 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.
$$
```

```{prf:example} Cost minimization
:label: ex-cvx-infimal-cost-min

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

1. The person needs to acquire $x$ total quantity.
1. 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.
1. 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.
1. Similarly, the cost of acquisition from manufacture B
   is given by the function $g(z)$.
1. Then the total cost is given by $f(y) + g(z)$
   subject to the condition that $y + z = x$.
1. Then the cost minimization problem is given by
   
   $$
   h(x) = \inf \{ f(y) + g(z) \ST x = y + z \}
   = (f \infimal g) (x).
   $$
1. 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) \}.
   $$
```


## Basic Properties

### Domain 

```{prf:property} Domain of infimal convolution
:label: res-cvx-infimal-dom

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

$$
\dom f \infimal g = \dom f + \dom g.
$$
```

```{prf: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$.
1. Then $f(\bx) < \infty$ and $g(\by) < \infty$.
1. By definition of infimal convolution

   $$
   (f \infimal g)(\bz) \leq f(\bx) + g(\by) < \infty.
   $$
1. Hence $\bz \in \dom f \infimal g$.
1. 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$.
1. First consider the case where $(f \infimal g)(\bz) = t \in \RR$.
1. Then for any $\epsilon > 0$, there exist $\bx, \by$ with $\bx + \by = \bz$
   such that

   $$
   t \leq f(\bx) + g(\by) \leq t + \epsilon.
   $$
1. Since $f(\bx) + g(\by)$ is finite, hence $f(\bx) < \infty$
   and $g(\by) < \infty$.
1. Hence $\bx < \dom f$ and $\by \in \dom g$.
1. Thus $\bz = \bx + \by \in \dom f + \dom g$.
1. Now consider the case where $(f \infimal g)(\bz) = -\infty$.
1. Then for every $M \in \RR$, there exist $\bx, \by$ with $\bx + \by = \bz$
   such that

   $$
   f(\bx) + g(\by) \leq M.
   $$
1. Thus $f(\bx) < \infty$ and $g(\by) < \infty$ for such pairs of $\bx, \by$.
1. Consequently $\bz = \bx + \by \in \dom f + \dom g$.
1. 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$.
1. Thus $\dom f + \dom g = \dom f \infimal g$.
```

### Epigraph

```{prf:property} Connection with epigraph
:label: res-cvx-infimal-epi-con

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

```{prf: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$.
1. 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$.
1. Thus $f(\by) + g(\bz) \leq r_1 + r_2 = r$ (by epigraphs).
1. By infimal convolution definition $t \leq f(\by) + g(\bz) \leq r$.
1. Thus we have shown that $t \leq r$ if $(\bx, r) \in \epi f + \epi g$.
1. Thus $t$ is a lower bound of the set $S$.
1. Now choose any $\epsilon > 0$.
1. 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.
   $$
1. Note that $(\by, f(\by)) \in \epi f$ and $(\bz, g(\bz)) \in \epi g$.
1. Hence $(\by + \bz, f(\by) + f(\bz)) \in \epi f + \epi g$.
1. Consequently $(\by + \bz, t + \epsilon) \in \epi f + \epi g$.
1. Replacing $\bx = \by + \bz$, we have $(\bx, t + \epsilon) \in \epi f + \epi g$.
1. Thus, for every $\epsilon > 0$, $t + \epsilon \in S$.
1. Hence $t$ must be the greatest lower bound of the set $S$.
1. In other words, $t = \inf S$ as desired.
```

```{prf:property} Strict epigraph of infimal convolution
:label: res-cvx-infimal-strict-epi

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

$$
\epi_s f \infimal g = \epi_s f + \epi_s g.
$$
```

```{prf:proof}

We show the set inclusion from both sides.

1. Let $(\bx, r) \in \epi_s f \infimal g$.
1. Then  $(f \infimal g)(\bx) < r$.
1. 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.
1. 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)$.
   1. Let $d = r - (s + t) > 0$.
   1. Let $e = \frac{d}{2} > 0$.
   1. Let $r_1 = s + e$ and $r_2 = t + e$.
   1. Then $r_1 + r_2 = s + t + 2e = s + t + d = r$.
   1. Also $f(\by) = s < r_1$ and $g(\bz) = t < r_2$.
1. Then $(\by, r_1) \in \epi_s f$ and $(\bz, r_2) \in \epi_s g$
   by definition of strict epigraphs.
1. Hence $(\by + \bz, r_1 + r_2)  = (\bx, r) \in \epi_s f + \epi_s g$.
1. 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$.
1. 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.
   $$
1. Thus $f(\by) < r_1$ and $g(\bz) < r_2$.
1. Thus $f(\by) + g(\bz) < r_1 + r_2 = r$.
1. Hence $(f \infimal g)(\bx) \leq f(\by) + g(\bz) < r$.
1. Hence $(\bx, r) \in \epi_s f \infimal g$.
1. Hence $\epi_s f + \epi_s g \subseteq \epi_s f \infimal g$.
```




```{prf:property} Epigraph of infimal convolution
:label: res-cvx-infimal-epi

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$.
```

```{prf:proof}
We first show the inclusion.

1. Let $(\bx, r) \in \epi f + \epi g$.
1. 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.
   $$
1. Thus $f(\by) \leq r_1$ and $g(\bz) \leq r_2$.
1. Thus $f(\by) + g(\bz) \leq r_1 + r_2 = r$.
1. Hence $(f \infimal g)(\bx) \leq f(\by) + g(\bz) \leq r$.
1. Hence $(\bx, r) \in \epi f \infimal g$.
1. 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$.
1. Then  $(f \infimal g)(\bx) \leq r$.
1. Consider first the case where $(f \infimal g)(\bx) = -\infty$.
1. 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$.
1. In particular, there exist $\by, \bz$ so that $f(\by) + f(\bz) < r$.
1. Hence $(\bx, r) \in \epi f + \epi g$.
1. Now if $(f \infimal g)(\bx) \in \RR$ then the infimal convolution is exact.
1. 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.
1. Consequently, we can split $r$ as $r = r_1 + r_2$ such that
   $f(\by) \leq r_1$ and $g(\bz) \leq r_2$.
1. Then $(\by, r_1) \in \epi f$ and $(\bz, r_2) \in \epi g$
   by definition of epigraphs.
1. Hence $(\by + \bz, r_1 + r_2)  = (\bx, r) \in \epi f + \epi g$.
1. 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)$.
1. Then $(\bx, t) \in \epi f \infimal g$.
1. 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).
   $$
1. For contradiction, assume that $(\bx, t) \in \epi f + \epi g$.
1. 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$.
1. Thus $f(\by) \leq t_1$ and $g(\bz) \leq t_2$.
1. Thus $f(\by) + g(\bz) \leq t_1 + t_2 = t$.
1. We have arrived at a contradiction.
1. Hence $(\bx, t) \notin \epi f + \epi g$.
```

### Convexity

```{prf:theorem} Infimal convolution of convex functions
:label: res-cvx-infimal-convex-proper

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.
```

```{prf:proof}

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

1. Since $f$ and $g$ are convex, hence $h$ is convex.
1. 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$.
   1. Choose any $\by \in \dom f$.
   1. Then $f(\by) < \infty$.
   1. Since $g$ is real valued, hence $g(\bx - \by) < \infty$.
   1. Thus $h(\bx, \by) = f(\by) + g(\bx - \by) < \infty$.
1. Then due to {prf:ref}`res-cvxf-partial-minimization-proper`

   $$
   (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$.


```{prf:example} Set distance function as infimal convolution
:label: ex-cvx-set-dist-infimal

Let $C \subseteq \VV$ be a nonempty convex set.

1. The indicator function $I_C$ is a proper convex function.
1. The norm function $\| \cdot \|$ is a real valued convex function.
1. By {prf:ref}`res-cvx-infimal-convex-proper`, $I_C \infimal \| \cdot \|$
   is convex.
1. 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).
   $$
1. Thus $d_C$ (the distance function to a convex set) is convex.
```

## Conjugates

```{prf:theorem} Conjugate of infimal convolution of proper functions
:label: res-cvx-infimal-proper-conjugate

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

$$
(h_1 \infimal h_2)^*  = h_1^*  + h_2^*.
$$
```

```{prf:proof}
Pick $\by \in \VV^*$. Then

$$
(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).
$$
```


```{prf:theorem} Conjugate of sum of convex functions
:label: res-cvx-sum-proper-conjugate

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^*.
$$
```

```{prf:proof}
The proof is more complicated and requires the application
of Fenchel's duality theorem ({prf:ref}`res-opt-fenchel-duality-theorem`).

1. Pick any $\by \in \VV^*$.
1. Elaborating the conjugate function

   $$
   (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)  \}\\
   $$
   where $g(\bx) = h_2(\bx) - \langle \bx, \by \rangle$.
1. We note that since $h_2$ is a real valued convex function, hence $g$ is also
   a real valued convex function.
1. We note that

   $$
   (\relint \dom h_1) \cap (\relint \dom g) = (\relint \dom h_1) \cap \VV
   = \relint \dom h_1 \neq \EmptySet.
   $$
1. Applying the Fenchel's duality theorem ({prf:ref}`res-opt-fenchel-duality-theorem`),

   $$
   \inf_{\bx \in \VV} \{ h_1(\bx) + g(\bx)  \} = 
   \sup_{\bz \in \VV} \{ -h_1^*(\bz) - g^*(-\bz)  \}.
   $$
1. Further 

   $$
   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 ).
   $$
1. Consequently

   $$
   (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).
   $$

This completes the proof.
```

```{prf:corollary} Function sum as conjugate of infimal convolution of conjugates
:label: res-cvx-conj-inf-conj-eq-sum

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^*)^*.
$$
```

```{prf:proof}

We proceed as follows.

1. Since $h_1$ is proper and $h_2$ is real valued,
   hence $h_1 + h_2$ is proper.
1. Since both $h_1$ and $h_2$ are closed functions,
   hence $h_1 + h_2$ is closed.
1. Since both $h_1$ and $h_2$ are convex functions,
   hence $h_1 + h_2$ is convex.
1. Thus $h_1 + h_2$ is a proper, closed convex function.
1. By {prf:ref}`res-cvxf-biconjugate-proper-closed-convex`,

   $$
   (h_1 + h_2)^{**} = h_1 + h_2.
   $$
1. By {prf:ref}`res-cvx-sum-proper-conjugate`,

   $$
   (h_1 + h_2)^* = h_1^* \infimal h_2^*.
   $$
1. Hence

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

```{prf:theorem} Representation of the infimal convolution by conjugates
:label: res-cvx-infimal-conjugate-rep

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^*)^*.
$$
```

```{prf:proof}
We proceed as follows.

1. By {prf:ref}`res-cvx-infimal-proper-conjugate`

   $$
   (h_1 \infimal h_2)^*  = h_1^*  + h_2^*.
   $$
1. Since $h_1$ is proper and convex and $h_2$ is real valued and convex,
   hence by {prf:ref}`res-cvx-infimal-convex-proper`,
   $h_1 \infimal h_2$ is convex.
1. By hypothesis $h_1 \infimal h_2$  is also real valued.
1. Thus $h_1 \infimal h_2$  is proper and closed.
1. Since $h_1 \infimal h_2$ is proper, closed and convex; 
   hence by {prf:ref}`res-cvxf-biconjugate-proper-closed-convex`

   $$
   (h_1 \infimal h_2)^{**} = h_1 \infimal h_2.
   $$
1. Hence
 
   $$
    h_1 \infimal h_2 = [(h_1 \infimal h_2)^*]^*
    = [h_1^*  + h_2^*]^*.
   $$
```

## 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.

```{prf:theorem} Infimal convolution
:label: res-cvx-infimal-convolution-is-convex

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.
```

```{prf: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$.
1. Sum of convex sets is convex. Hence, $F$ is a convex set.
1. 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$.
1. It follows that $f_i(\bx_i) \leq t_i$ for $i=1,\dots,m$.
1. Consequently, $f_1(\bx_1) + \dots + f_m(\bx_m) \leq t_1 + \dots + t_m$.
1. By {prf:ref}`res-cvxf-construct-convex-sets-dirsum`,
   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.
1. Let $T = \{t \in \RR \ST (\bx, t) \in F \}$. 
   Then $g(\bx) = \inf T$.
1. 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 \}.
   $$
1. We claim that $g = f$.

To show that $g=f$, we need to do the following.

1. Show that $\dom f = \dom g$.
1. 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$.
1. Thus, there is no $(\bx_i, t_i) \in F_i$ for $i=1,\dots,m$
   such that $\bx = \bx_1 + \dots + \bx_m$.
1. 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$.
1. 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$.
1. 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$.
1. Thus, $f(\bx) = \infty$.
1. Thus, $\bx \notin \dom f$.


Assume that $\bx \notin \dom f$.

1. Then, $f(\bx) = \infty$.
1. 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$.
1. 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$.
1. 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$.
1. 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$.
1. Thus, there is no $(\bx_i, t_i) \in F_i$ for $i=1,\dots,m$
   such that $\bx = \bx_1 + \dots + \bx_m$.
1. Thus, there is no $t \in \RR$ such that $(\bx, t) \in F$.
1. 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).
   $$
1. 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.
   $$
1. 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.
   $$
1. 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$.
1. 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.
   $$
1. 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.
   $$
1. 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.
```