source/src/sections/_III_background.tex

\section{Background}

Throughout this paper we assume $X$ and $Y$ are subsets of Euclidean spaces. We write arbitrary subsets with a tilde; for example, $\tilde{X}$ denotes an arbitrary subset of $X$. The exposition below recalls the standard facts about convex conjugation and then introduces the generalized transforms used throughout the paper.

\subsection{Convexity}

Let $f:\,X\to\overline{\R}$ be an extended-real-valued function. The Legendre transform (convex conjugate) of $f$ is the function on the dual space $X^*$ defined by
\begin{align*}
f^*&\, : X^* \to \overline{\R}\\
f^*&(y) = \sup_{x \in X} \{ \langle x, y \rangle - f(x) \}
\end{align*}

The Legendre transform is central to convex analysis: a function is convex if and only if it coincides with the Legendre transform (conjugate) of another function. Equivalently, each convex function may be represented as the upper envelope of its affine supporting functions (its subgradients).

In general, $f^{**} \leq f$, with equality if and only if $f$ is convex and lower semicontinuous (Fenchel--Moreau theorem). Another fundamental result is the Fenchel--Young inequality:
\begin{align*}
\langle x, y \rangle \leq f(x) + f^*(y)
\end{align*}
with equality precisely when $y$ is a subgradient of $f$ at $x$.

These are essential properties conferred by convexity, and analogues of them will be desirable in the generalized theory.

\subsection{Generalized convexity}

Since the Legendre transform is defined via a supremum over affine functions, a natural generalization replaces the inner product with a more general bivariate function $\Phi: X \times Y \to \R$.

We also allow the supremum to be taken over a subset $\tilde{X} \subseteq X$. When $f$ is defined on $\tilde{X}$, we denote its $\tilde{X}$-transform (also called the $\tilde{X}$-conjugate) by a superscript $\tilde{X}$:

\begin{align*}
f^{\tilde{X}}_{\Phi}&\,: Y \to \overline{\R}\\
f^{\tilde{X}}_{\Phi}&(y) = \sup_{x \in \tilde{X}} \{ \Phi(x, y) - f(x) \}
\end{align*}

When $\Phi(x,y)=\langle x,y\rangle$ and $\tilde{X}=X$, these definitions recover the classical Legendre transform and biconjugation.

Standard convexity theory typically considers functions defined on all of $X$, but for our purposes, it is convenient to work with functions defined on arbitrary subsets. We say a function $f$ is $\tilde{X}$-convex (respectively, $\tilde{Y}$-convex) if it is the restriction of a $\tilde{X}$-transform (respectively, $\tilde{Y}$-transform) of some function $g$ to the domain of $f$:
\begin{align*}
    f = (g^{\tilde{X}})_{|\mathrm{dom}(f)}
\end{align*}

Let $\mathcal{C}^{\tilde{X}}(\tilde{Y})$ (respectively, $\mathcal{C}^{\tilde{Y}}(\tilde{X})$) denote the set of all $\tilde{X}$-convex functions with domain $\tilde{Y}$. Again, this coincides with the standard notion of convexity when $\Phi$ is the inner product and $\tilde{X}=X, \tilde{Y}=Y$.

Before proceeding, we establish a few properties of generalized convexity that demonstrate its similarity to standard convexity. These properties will be useful in subsequent sections.

\begin{lemma}[Basic Properties]\label{lem:basic-properties}
If $f,g:\tilde{X} \to \R$, then for all $(x,y)\in\tilde{X}\times\tilde{Y}$:
\begin{align*}
& \Phi(x,y) \le f^{\tilde{X}}(y) + f(x)\\
& f^{\tilde{Y}\tilde{X}}(x) \le f(x)\\
& f \le g \implies f^{\tilde{X}} \ge g^{\tilde{X}}
\end{align*}
\end{lemma}

\begin{proof}
By definition of the $\tilde{X}$-transform,
\begin{align*}
f^{\tilde{X}}(y) &= \sup_{x'\in\tilde{X}} \Phi(x',y) - f(x')\\
&\ge \Phi(x,y) - f(x),
\end{align*}
which yields the first inequality.

For the second property,
\begin{align*}
f^{\tilde{Y}\tilde{X}}(x) &= \sup_{y\in\tilde{Y}}  \Phi(x,y) - f^{\tilde{X}}(y) \\
&\le \sup_{y\in\tilde{Y}}  f(x)  = f(x),
\end{align*}
where the inequality follows from the first property.

For the third property, if $f \le g$ then
\begin{align*}
g^{\tilde{X}}(y) &= \sup_{x\in\tilde{X}} \Phi(x,y) - g(x)\\
&\le \sup_{x\in\tilde{X}} \Phi(x,y) - f(x) = f^{\tilde{X}}(y).
\end{align*}
\end{proof}

The next lemma records a simple monotonicity with respect to enlarging the set over which the transform is taken.

\begin{lemma}[Enlarging Lemma]\label{lem:extend-set}
If $f$ is $\tilde{Y}_1$-convex and $\tilde{Y}_1\subseteq\tilde{Y}_2$, then $f$ is $\tilde{Y}_2$-convex.
\end{lemma}

\begin{proof}
If $f=(g_1^{\tilde{Y}_1})_{|\mathrm{dom}(f)}$ for some $g_1$ on $\tilde{Y}_1$, define
\[g_2(y)=\begin{cases} g_1(y), & y\in\tilde{Y}_1,\\ +\infty, & y\in\tilde{Y}_2\setminus\tilde{Y}_1.\end{cases}\]
Then $g_2^{\tilde{Y}_2}$ restricts to the same function on $\mathrm{dom}(f)$, so $f$ is $\tilde{Y}_2$-convex.
\end{proof}

A useful analogue to the invariance under biconjugation property of convex functions is the following:

\begin{lemma}[Generalized Biconjugation]\label{lem:biconjugation}
Let $f:\,\tilde{X}\to\R$. Then $f$ is $\tilde{Y}$-convex if and only if
\[f = (f^{\tilde{Y}\tilde{X}})_{|\tilde{X}}\]
\end{lemma}
\begin{proof}
If $f$ equals its generalized biconjugate on $\tilde{X}$ then it is, by definition, the transform of $f^{\tilde{X}}$ and hence $\tilde{Y}$-convex. Conversely, suppose $f$ is $\tilde{Y}$-convex so there is $g$ with $f=(g^{\tilde{Y}})_{|\tilde{X}}$. Applying the $\tilde{X}$-transform and then the $\tilde{Y}$-transform yields
\[f^{\tilde{X}}=(g^{\tilde{Y}})^{\tilde{X}}=g^{\tilde{X}\tilde{Y}}\le g,
\]
where the last inequality is implied by Lemma \ref{lem:basic-properties}. Restricting back to $\tilde{X}$ and taking transforms gives
\[ (f^{\tilde{Y}\tilde{X}})_{|\tilde{X}} \ge (g^{\tilde{Y}})_{|\tilde{X}} = f,\]
which together with the general inequality $f^{\tilde{Y}\tilde{X}}\le f$ proves equality.
\end{proof}

As a simple corollary, distinct $\tilde{Y}$-convex functions have distinct $\tilde{X}$-transforms.

\begin{corollary}
If $f,g:\,\tilde{X}\to\R$ are $\tilde{Y}$-convex and $f\neq g$, then $f^{\tilde{X}}\neq g^{\tilde{X}}$.
\end{corollary}