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

[math]\displaystyle{ \begin{align} & \liminf_{n \to \infty} f_{n}(x_n) \geq f(x) \text{ for every } x_n \to x \text{ and } \\ & \limsup_{n \to \infty} f_n(x_n) \leq f(x) \text{ for some } x_n \to x. \end{align} }[/math]

Extended real-valued extension

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

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

[math]\displaystyle{ \begin{align} & \liminf_{n \to \infty} f_{n}(x_n) \geq f(x) \text{ for every } x_n \to x \text{ and } \\ & \limsup_{n \to \infty} f_n(x_n) \leq f(x) \text{ for some } x_n \to x. \end{align} }[/math]

In fact, epi-convergence coincides with the [math]\displaystyle{ \Gamma }[/math]-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. [math]\displaystyle{ (f_n) }[/math] hypo-converges to [math]\displaystyle{ f }[/math] if

[math]\displaystyle{ \limsup_{n \to \infty} f_n(x_n) \leq f(x) \text{ for every } x_n \to x }[/math]

and

[math]\displaystyle{ \liminf_{n \to \infty} f_n(x_n) \geq f(x) \text{ for some } x_n \to x. }[/math]

Relationship to minimization problems

Assume we have a difficult minimization problem

[math]\displaystyle{ \inf_{x \in C} g(x) }[/math]

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

[math]\displaystyle{ \inf_{x \in C_{n}} g_n(x) }[/math]

for functions [math]\displaystyle{ g_n }[/math] and sets [math]\displaystyle{ C_n }[/math].

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

[math]\displaystyle{ \begin{align} f(x) & = \begin{cases} g(x), & x \in C, \\ \infty, & x \not \in C, \end{cases} \\[4pt] f_n(x) & = \begin{cases} g_n(x), & x \in C_n, \\ \infty, & x \not \in C_n. \end{cases} \end{align} }[/math]

So that the problems [math]\displaystyle{ \inf_{x \in X} f(x) }[/math] and [math]\displaystyle{ \inf_{x \in X} f_n(x) }[/math] are equivalent to the original and approximate problems, respectively.

If [math]\displaystyle{ (f_n) }[/math] epi-converges to [math]\displaystyle{ f }[/math], then [math]\displaystyle{ \limsup_{n \to \infty} [\inf f_n] \leq \inf f }[/math]. Furthermore, if [math]\displaystyle{ x }[/math] is a limit point of minimizers of [math]\displaystyle{ f_n }[/math], then [math]\displaystyle{ x }[/math] is a minimizer of [math]\displaystyle{ f }[/math]. In this sense,

[math]\displaystyle{ \lim_{n \to \infty} \operatorname{argmin} f_n \subseteq \operatorname{argmin} f. }[/math]

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

Properties

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