Epi-convergence

In mathematical analysis, epi-convergence is a type of convergence for real-valued and extended real-valued functions. Epi-convergence is important because it is the appropriate notion of convergence with which to approximate minimization problems in the field of mathematical optimization. The symmetric notion of hypo-convergence is appropriate for maximization problems. Mosco convergence is a generalization of epi-convergence to infinite dimensional spaces.

Definition

Let $X$ be a metric space, and $f_n:X\to \mathbb{ℝ}$ a real-valued function for each natural number $n$. We say that the sequence $(f^n)$ epi-converges to a function $f:X\to \mathbb{ℝ}$ if for each $x\in X$

$\begin{array}{rl}& \underset{n\to \mathrm{\infty }}{\mathrm{lim\; inf}}{f}_n(x_n)\ge f(x)\text{ for every }{x}_n\to x\text{ and }\\ & \underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}{f}_n(x_n)\le f(x)\text{ for some }{x}_n\to x.\end{array}$

Extended real-valued extension

The following extension allows epi-convergence to be applied to a sequence of functions with non-constant domain.

Denote by $\overline{\mathbb{ℝ}}=\mathbb{ℝ}\cup \{\pm \mathrm{\infty }\}$ the extended real numbers. Let $f_n$ be a function $f_n:X\to \overline{\mathbb{ℝ}}$ for each $n\in \mathbb{\mathbb{N}}$. The sequence $(f_n)$ epi-converges to $f:X\to \overline{\mathbb{ℝ}}$ if for each $x\in X$

$\begin{array}{rl}& \underset{n\to \mathrm{\infty }}{\mathrm{lim\; inf}}{f}_n(x_n)\ge f(x)\text{ for every }{x}_n\to x\text{ and }\\ & \underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}{f}_n(x_n)\le f(x)\text{ for some }{x}_n\to x.\end{array}$

In fact, epi-convergence coincides with the $\mathrm{\Gamma }$-convergence in first countable spaces.

Hypo-convergence

Epi-convergence is the appropriate topology with which to approximate minimization problems. For maximization problems one uses the symmetric notion of hypo-convergence. $(f_n)$ hypo-converges to $f$ if

$\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}{f}_n(x_n)\le f(x)\text{ for every }{x}_n\to x$

and

$\underset{n\to \mathrm{\infty }}{\mathrm{lim\; inf}}{f}_n(x_n)\ge f(x)\text{ for some }{x}_n\to x.$

Relationship to minimization problems

Assume we have a difficult minimization problem

$\underset{x\in C}{\inf }g(x)$

where $g:X\to \mathbb{ℝ}$ and $C\subseteq X$. We can attempt to approximate this problem by a sequence of easier problems

$\underset{x\in C_n}{\inf }{g}_n(x)$

for functions $g_n$ and sets $C_n$.

Epi-convergence provides an answer to the question: In what sense should the approximations converge to the original problem in order to guarantee that approximate solutions converge to a solution of the original?

We can embed these optimization problems into the epi-convergence framework by defining extended real-valued functions

$\begin{array}{rl}f(x)& =\{\begin{array}{ll}g(x),& x\in C,\\ \mathrm{\infty },& x\in ̸C,\end{array}\\ f_n(x)& =\{\begin{array}{ll}{g}_n(x),& x\in C_n,\\ \mathrm{\infty },& x\in ̸C_n.\end{array}\end{array}$

So that the problems $\underset{x\in X}{\inf }f(x)$ and $\underset{x\in X}{\inf }{f}_n(x)$ are equivalent to the original and approximate problems, respectively.

If $(f_n)$ epi-converges to $f$, then $\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}[\inf f_n]\le \inf f$. Furthermore, if $x$ is a limit point of minimizers of $f_n$, then $x$ is a minimizer of $f$. In this sense,

$\underset{n\to \mathrm{\infty }}{\lim }\mathrm{argmin}{f}_n\subseteq \mathrm{argmin}f.$

Epi-convergence is the weakest notion of convergence for which this result holds.

Properties

• $(f_n)$ epi-converges to $f$ if and only if $(-f_n)$ hypo-converges to $-f$.
• $(f_n)$ epi-converges to $f$ if and only if $(\mathrm{epi}{f}_n)$ converges to $\mathrm{epi}f$ as sets, in the Painlevé–Kuratowski sense of set convergence. Here, $\mathrm{epi}f$ is the epigraph of the function $f$.
• If $f_n$ epi-converges to $f$, then $f$ is lower semi-continuous.
• If $f_n$ is convex for each $n\in \mathbb{\mathbb{N}}$ and $(f_n)$ epi-converges to $f$, then $f$ is convex.
• If $f_n^1\le f_n\le f_n^2$ and both $(f_n^1)$ and $(f_n^2)$ epi-converge to $f$, then $(f_n)$ epi-converges to $f$.
• If $(f_n)$ converges uniformly to $f$ on each compact set of ${\mathbb{ℝ}}_n$ and $(f_n)$ are continuous, then $(f_n)$ epi-converges and hypo-converges to $f$.
• In general, epi-convergence neither implies nor is implied by pointwise convergence. Additional assumptions can be placed on an pointwise convergent family of functions to guarantee epi-convergence.

References

• "Epigraphical Limits". Variational Analysis. Grundlehren der mathematischen Wissenschaften. 317. Springer Science & Business Media. 2009. pp. 238–297. doi:10.1007/978-3-642-02431-3_7. ISBN 978-3-540-62772-2. 
• Kall, Peter (1986). "Approximation to optimization problems: an elementary review". Mathematics of Operations Research 11 (1): 9–18. doi:10.1287/moor.11.1.9. 
• Attouch, Hedy (1989). "Epigraphical analysis". Annales de l'Institut Henri Poincaré C 6: 73–100. doi:10.1016/S0294-1449(17)30036-7. Bibcode: 1989AIHPC...6...73A.