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

edit

Let   be a metric space, and   a real-valued function for each natural number  . We say that the sequence   epi-converges to a function   if for each  

 

Extended real-valued extension

edit

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

Denote by   the extended real numbers. Let   be a function   for each  . The sequence   epi-converges to   if for each  

 

In fact, epi-convergence coincides with the  -convergence in first countable spaces.

Hypo-convergence

edit

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

 

and

 

Relationship to minimization problems

edit

Assume we have a difficult minimization problem

 

where   and  . We can attempt to approximate this problem by a sequence of easier problems

 

for functions   and sets  .

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

 

So that the problems   and   are equivalent to the original and approximate problems, respectively.

If   epi-converges to  , then  . Furthermore, if   is a limit point of minimizers of  , then   is a minimizer of  . In this sense,

 

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

Properties

edit
  •   epi-converges to   if and only if   hypo-converges to  .
  •   epi-converges to   if and only if   converges to   as sets, in the Painlevé–Kuratowski sense of set convergence. Here,   is the epigraph of the function  .
  • If   epi-converges to  , then   is lower semi-continuous.
  • If   is convex for each   and   epi-converges to  , then   is convex.
  • If   and both   and   epi-converge to  , then   epi-converges to  .
  • If   converges uniformly to   on each compact set of   and   are continuous, then   epi-converges and hypo-converges to  .
  • 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

edit
  • Rockafellar, R. Tyrrell; Wets, Roger (2009). "Epigraphical Limits". Variational Analysis. Grundlehren der mathematischen Wissenschaften. Vol. 317. Springer Science & Business Media. 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; Wets, Roger (1989). "Epigraphical analysis". Annales de l'Institut Henri Poincaré C. 6: 73–100. Bibcode:1989AIHPC...6...73A. doi:10.1016/S0294-1449(17)30036-7.