partial-minimization

Convexity Under Operators: Supremum, Infimum, Marginal Infimum and Infimum Convolution

Convex functions are central in convex optimization, and it’s natural to ask whether convexity is preserved under common operations like taking the supremum, infimum, or partial minimization. This post explores the following progression:

• The supremum over a family of convex functions is convex.
• The infimum over a family of convex functions is not necessarily convex.
• However, if the function is jointly convex, then the partial infimum over one variable does preserve convexity.
• A generalization of the convexity of partial infimum, called infimum convolution between two jointly convex functions is also convex.

We explore these ideas with proofs and remarks that illuminate why they are true.

---

Section 1. Definitions of convex functions

Before exploring how convexity behaves under operations like supremum, infimum, or marginalization, we recall key definitions from convex analysis.

Convex Function

A function $F: \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}$ is called convex if its domain $\operatorname{dom} F := \{x \in \mathbb{R}^n \mid F(x) < +\infty\}$ is convex, and for all $x_1, x_2 \in \operatorname{dom} F$ and $\theta \in [0,1]$, we have

$$F(\theta x_1 + (1 - \theta)x_2) \leq \theta F(x_1) + (1 - \theta)F(x_2).$$

This inequality expresses that the graph of $F$ lies below the line segment connecting $F(x_1)$ and $F(x_2)$ — a hallmark of convexity.

---

Jointly Convex Function

Let $f: \mathbb{R}^n \times \mathbb{R}^m \to \mathbb{R} \cup \{+\infty\}$. We say that $f$ is jointly convex in $(x, y)$ if its domain $\operatorname{dom} f := \{(x, y) \mid f(x, y) < +\infty\}$ is convex, and for all $(x_1, y_1), (x_2, y_2) \in \operatorname{dom} f$ and $\theta \in [0, 1]$:

$$f(\theta x_1 + (1 - \theta)x_2, \theta y_1 + (1 - \theta)y_2) \leq \theta f(x_1, y_1) + (1 - \theta) f(x_2, y_2).$$

This means $f$ behaves like a convex function on the product space $\mathbb{R}^n \times \mathbb{R}^m$ — convex with respect to both variables simultaneously, not separately.

Joint convexity is stronger than separate convexity in $x$ and $y$; that is, $x \mapsto f(x, y)$ and $y \mapsto f(x, y)$ can both be convex without $f(x, y)$ being jointly convex.

Example 1: $f(x) = \langle a, x\rangle$ is convex.
Example 2: $f(x, y) = \langle a, x\rangle + \langle b, y\rangle$ is jointly convex.
Example 3: $f(x, y) = \langle x, y\rangle$ is convex in $x$ and in $y$ but not jointly convex in $(x, y)$

These definitions set the stage for the key results to come, where we examine how the convexity of such functions is preserved under optimization operations like $\sup$, $\inf$, marginalization and convolution.

---

Section 2. Supremum of Convex Functions Is Convex

Theorem

Let $\{f_y(x) = f(x, y)\}_{y \in Y}$ be a family of convex functions indexed by $y \in Y$ (with $Y$ arbitrary — finite or infinite). Define:

$$F(x) := \sup_{y \in Y} f(x, y).$$

Then $F$ is convex.

Proof

Let $x_1, x_2 \in \mathbb{R}^n$, and $\theta \in [0, 1]$. Define $x_\theta = \theta x_1 + (1 - \theta)x_2$.

For each $y \in Y$, since $f(x, y)$ is convex in $x$:

$$f(x_\theta, y) \leq \theta f(x_1, y) + (1 - \theta)f(x_2, y).$$

Taking the supremum over all $y \in Y$ on both sides:

$$F(x_\theta) = \sup_{y \in Y} f(x_\theta, y) \leq \sup_{y \in Y} \left[ \theta f(x_1, y) + (1 - \theta) f(x_2, y) \right].$$

Using the fact that $\sup$ is sublinear in this context:

$$F(x_\theta) \leq \theta \sup_{y \in Y} f(x_1, y) + (1 - \theta) \sup_{y \in Y} f(x_2, y) = \theta F(x_1) + (1 - \theta) F(x_2).$$

Thus, $F$ is convex.

---

Section 3. Infimum of Convex Functions May Not Be Convex

While the supremum of convex functions preserves convexity, the infimum does not in general, i.e.
$$F(x) := \inf_{y \in Y} f(x, y)$$
is not convex.

Counterexample: Let

$$f_1(x) = (x - 1)^2, \quad f_2(x) = (x + 1)^2.$$

Define:

$$F(x) = \inf \{f_1(x), f_2(x)\}.$$

Then:

$$F(x) = \begin{cases} (x+1)^2, & x \leq 0 \\ (x-1)^2, & x \geq 0 \end{cases}$$

This function is not convex.

---

But wait!

If infimum does not preserve the convexity, then if we add extra condition on $f$, can we obtain convexity after applying infimum? The answer is yes!

Let $f(x, y)$ be jointly convex in $(x, y)$, and define the marginal minimum

$$F(x) := \inf_{y \in Y} f(x, y).$$

Then $F$ is convex in $x$.

Furthermore, there is a more general result! Let $f$ and $g$ are jointly convex, then
$$h(x, z) := \inf_{y \in Y} f(x, y) + g(y, z)$$
is jointly convex.

In the next two sections, we will prove theses.

---

Section 3. Marginal Minimum of Jointly Convex Function

Theorem

Let $f(x, y)$ be jointly convex on $\mathbb{R}^n \times \mathbb{R}^m$, and $Y \subseteq \mathbb{R}^m$ be convex. Define the partial minimum function:

$$F(x) := \inf_{y \in Y} f(x, y).$$

Then $F$ is convex.

Proof Sketch

Let $x_1, x_2 \in \mathbb{R}^n$, and $\theta \in [0,1]$. Let $x_\theta = \theta x_1 + (1 - \theta) x_2$.

For $\varepsilon > 0$, choose $y_1, y_2 \in Y$ such that:

• $f(x_1, y_1) \leq F(x_1) + \varepsilon$
• $f(x_2, y_2) \leq F(x_2) + \varepsilon$

Let $y_\theta = \theta y_1 + (1 - \theta)y_2 \in Y$ (by convexity of $Y$). By joint convexity:

$$f(x_\theta, y_\theta) \leq \theta f(x_1, y_1) + (1 - \theta) f(x_2, y_2).$$

So:

$$F(x_\theta) \leq f(x_\theta, y_\theta) \leq \theta F(x_1) + (1 - \theta) F(x_2) + \varepsilon.$$

Letting $\varepsilon \to 0$ gives:

$$F(x_\theta) \leq \theta F(x_1) + (1 - \theta) F(x_2),$$

proving convexity.

---

Section 4. Infimum Convolution of Jointly Convex Functions

We now extend the result from Section 3 to a more general setting involving two jointly convex functions.

Theorem

Let $f(x, y)$ be jointly convex in $(x, y) \in \mathbb{R}^n \times \mathbb{R}^m$ and $g(y, z)$ be jointly convex in $(y, z) \in \mathbb{R}^m \times \mathbb{R}^k$, and let $Y \subseteq \mathbb{R}^m$ be a convex set. Define

$$h(x, z) := \inf_{y \in Y} \left[ f(x, y) + g(y, z) \right].$$

Then $h(x, z)$ is jointly convex in $(x, z)$.

Proof

Let $(x_1, z_1), (x_2, z_2) \in \mathbb{R}^n \times \mathbb{R}^k$ and let $\theta \in [0,1]$. Define:

$$(x_\theta, z_\theta) := \theta (x_1, z_1) + (1 - \theta)(x_2, z_2).$$

For any $\varepsilon > 0$, choose $y_1, y_2 \in Y$ such that:

$$f(x_1, y_1) + g(y_1, z_1) \leq h(x_1, z_1) + \varepsilon, \\ f(x_2, y_2) + g(y_2, z_2) \leq h(x_2, z_2) + \varepsilon.$$

Let $y_\theta := \theta y_1 + (1 - \theta)y_2 \in Y$ (by convexity of $Y$). Using joint convexity of $f$ and $g$:

$$f(x_\theta, y_\theta) \leq \theta f(x_1, y_1) + (1 - \theta) f(x_2, y_2), \\ g(y_\theta, z_\theta) \leq \theta g(y_1, z_1) + (1 - \theta) g(y_2, z_2).$$

Adding both inequalities:

$$f(x_\theta, y_\theta) + g(y_\theta, z_\theta) \leq \theta \left[ f(x_1, y_1) + g(y_1, z_1) \right] + (1 - \theta)\left[ f(x_2, y_2) + g(y_2, z_2) \right].$$

Hence:

$$h(x_\theta, z_\theta) \leq f(x_\theta, y_\theta) + g(y_\theta, z_\theta) \leq \theta h(x_1, z_1) + (1 - \theta) h(x_2, z_2) + \varepsilon.$$

Since $\varepsilon > 0$ is arbitrary, taking the limit yields:

$$h(x_\theta, z_\theta) \leq \theta h(x_1, z_1) + (1 - \theta) h(x_2, z_2),$$

which proves that $h$ is jointly convex in $(x, z)$.

---

Summary

Let’s recap the natural flow of ideas:

1. Supremum of convex functions:

   • $\sup_{y \in Y} f(x, y)$ is convex if each $f(x, y)$ is convex in $x$.
   • Holds for any index set $Y$ — even infinite.

2. Infimum of convex functions:

   • $\inf_{y \in Y} f(x, y)$ is not necessarily convex.
   • Can fail even for simple convex quadratic functions.

3. Marginal Infimum of jointly convex function:

   • $\inf_{y \in Y} f(x, y)$ is convex if $f(x, y)$ is jointly convex and $Y$ is convex.
   • This is especially useful in partial minimization, parametric optimization, and duality.

4. Infimum convolution of two jointly convex functions:

   • $\inf_{y \in Y} f(x, y) + g(y, z)$ is convex in $(x, z)$ if $f$ and $g$ are jointly convex and $Y$ is convex.
   • This family of functions form a semigroup.

Understanding these operations sharpens your ability to reason about convexity in convex optimization.