Epi-convergence explained

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 R a real-valued function for each natural number n . We say that the sequence (f ^{n} ) epi-converges to a function f: X \to R if for each x \in X \begin{align} & \liminf _{n} f _{n} (x _{n)} \geq f(x) forevery x _{n} \to x and \\ & \limsup _{n} f _{n(x} _{n)} \leq f(x) forsome x _{n} \to x. \end{align}

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{ R }= \mathbb \cup \ the extended real numbers. Let f _{n} be a function f _{n:X} \to \overline{ R } for each n \in N . The sequence (f _{n)} epi-converges to f: X \to \overline{ R } if for each x \in X \begin{align} & \liminf _{n} f _{n} (x _{n)} \geq f(x) forevery x _{n} \to x and \\ & \limsup _{n} f _{n(x} _{n)} \leq f(x) forsome x _{n} \to x. \end{align}

In fact, epi-convergence coincides with the

\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\limsup _{n} f _{n(x} _{n)} \leq f(x) forevery x _{n} \to x

and

\liminf _{n} f _{n(x} _{n)} \geq f(x) forsome x _{n} \to x.

Relationship to minimization problems

Assume we have a difficult minimization problem

inf _{x} g(x)

where

g: X \to R and C \subseteq X . We can attempt to approximate this problem by a sequence of easier problemsinf _{x \in C _{n}} 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{align} f(x) & = \begin{cases} g(x), & x \in C, \ inf ty, & x \not \in C, \end{cases} \\[ 4 pt] f _{n(x)} & = \begin{cases} g _{n(x),} & x \in C _{n,} \ inf ty, & x \not \in C _{n.} \end{cases} \end{align}

So that the problems

inf _{x} f(x) and inf _{x} f _{n(x)} are equivalent to the original and approximate problems, respectively.

If

(f _{n)} epi-converges to f , then \limsup _{n} [ inf f _{n]} \leq inf f . Furthermore, if x is a limit point of minimizers of f _{n} , then x is a minimizer of f . In this sense,\lim _{n} \operatorname{argmin} f _{n} \subseteq \operatorname{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 (\operatorname{epi} f _{n)} converges to \operatorname{epi} f as sets, in the Painlevé–Kuratowski sense of set convergence. Here, \operatorname{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 N and (f _{n)} epi-converges to f , then f is convex.

• If

f ^{1} _{n} \leq f _{n} \leq f ^{2} _{n} and both (f ^{1} _{n)} and (f ^{2} _{n)} epi-converge to f , then (f _{n)} epi-converges to f .

• If

(f _{n)} converges uniformly to f on each compact set of R _{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

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