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 ${\displaystyle X}$ be a metric space, and ${\displaystyle f^{\nu }:X\to \mathbb {R} }$ a real-valued function for each natural number ${\displaystyle \nu }$. We say that the sequence ${\displaystyle (f^{\nu })}$ epi-converges to a function ${\displaystyle f:X\to \mathbb {R} }$ if for each ${\displaystyle x\in X}$

${\displaystyle {\begin{aligned}&\liminf _{\nu \to \infty }f^{\nu }(x^{\nu })\geq f(x){\text{ for every }}x^{\nu }\to x{\text{ and }}\\&\limsup _{\nu \to \infty }f^{\nu }(x^{\nu })\leq f(x){\text{ for some }}x^{\nu }\to x.\end{aligned}}}$

Extended real-valued extension

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

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

${\displaystyle {\begin{aligned}&\liminf _{\nu \to \infty }f^{\nu }(x^{\nu })\geq f(x){\text{ for every }}x^{\nu }\to x{\text{ and }}\\&\limsup _{\nu \to \infty }f^{\nu }(x^{\nu })\leq f(x){\text{ for some }}x^{\nu }\to x.\end{aligned}}}$

In fact, epi-convergence coincides with the ${\displaystyle \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. ${\displaystyle (f^{\nu })}$ hypo-converges to ${\displaystyle f}$ if

${\displaystyle \limsup _{\nu \to \infty }f^{\nu }(x^{\nu })\leq f(x){\text{ for every }}x^{\nu }\to x}$

and

${\displaystyle \liminf _{\nu \to \infty }f^{\nu }(x^{\nu })\geq f(x){\text{ for some }}x^{\nu }\to x.}$

Relationship to minimization problems

Assume we have a difficult minimization problem

${\displaystyle \inf _{x\in C}g(x)}$

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

${\displaystyle \inf _{x\in C^{\nu }}g^{\nu }(x)}$

for functions ${\displaystyle g^{\nu }}$ and sets ${\displaystyle C^{\nu }}$.

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

${\displaystyle {\begin{aligned}f(x)&={\begin{cases}g(x),&x\in C,\\\infty ,&x\not \in C,\end{cases}}\\[4pt]f^{\nu }(x)&={\begin{cases}g^{\nu }(x),&x\in C^{\nu },\\\infty ,&x\not \in C^{\nu }.\end{cases}}\end{aligned}}}$

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

If ${\displaystyle (f^{\nu })}$ epi-converges to ${\displaystyle f}$, then ${\displaystyle \limsup _{\nu \to \infty }[\inf f^{\nu }]\leq \inf f}$. Furthermore, if ${\displaystyle x}$ is a limit point of minimizers of ${\displaystyle f^{\nu }}$, then ${\displaystyle x}$ is a minimizer of ${\displaystyle f}$. In this sense,

${\displaystyle \lim _{v\to \infty }\operatorname {argmin} f^{\nu }\subseteq \operatorname {argmin} f.}$

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

Properties

• ${\displaystyle (f^{\nu })}$ epi-converges to ${\displaystyle f}$ if and only if ${\displaystyle (-f^{\nu })}$ hypo-converges to ${\displaystyle -f}$.
• ${\displaystyle (f^{\nu })}$ epi-converges to ${\displaystyle f}$ if and only if ${\displaystyle (\operatorname {epi} f^{\nu })}$ converges to ${\displaystyle \operatorname {epi} f}$ as sets, in the Painlevé–Kuratowski sense of set convergence. Here, ${\displaystyle \operatorname {epi} f}$ is the epigraph of the function ${\displaystyle f}$.
• If ${\displaystyle f^{\nu }}$ epi-converges to ${\displaystyle f}$, then ${\displaystyle f}$ is lower semi-continuous.
• If ${\displaystyle f^{\nu }}$ is convex for each ${\displaystyle \nu \in \mathbb {N} }$ and ${\displaystyle (f^{\nu })}$ epi-converges to ${\displaystyle f}$, then ${\displaystyle f}$ is convex.
• If ${\displaystyle f_{1}^{\nu }\leq f^{\nu }\leq f_{2}^{\nu }}$ and both ${\displaystyle (f_{1}^{\nu })}$ and ${\displaystyle (f_{2}^{\nu })}$ epi-converge to ${\displaystyle f}$, then ${\displaystyle (f^{\nu })}$ epi-converges to ${\displaystyle f}$.
• If ${\displaystyle (f^{\nu })}$ converges uniformly to ${\displaystyle f}$ on each compact set of ${\displaystyle \mathbb {R} ^{n}}$ and ${\displaystyle (f^{\nu })}$ are continuous, then ${\displaystyle (f^{\nu })}$ epi-converges and hypo-converges to ${\displaystyle 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

• R. Tyrrell Rockafellar and Roger Wets, Variational Analysis. Chapter 7 ; Vol. 317. Springer Science & Business Media, 2009.
• Peter Kall, Approximation to optimization problems: An elementary review; Mathematics of Operations Research 19, pp. 9–18 (1986)
• Hedy Attouch and Roger Wets, Epigraphical analysis; Annales de l'IHP Analyse non linéaire Vol. 6. 1989.