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.

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

${\displaystyle {\begin{aligned}&\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{aligned}}}${\displaystyle {\begin{aligned}&\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{aligned}}}

Assume we have a difficult minimization problem

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

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

${\displaystyle \inf _{x\in C_{n}}g_{n}(x)}${\displaystyle \inf _{x\in C_{n}}g_{n}(x)}

for functions ${\displaystyle g_{n}}${\displaystyle g_{n}} and sets ${\displaystyle C_{n}}${\displaystyle 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

${\displaystyle {\begin{aligned}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{aligned}}}${\displaystyle {\begin{aligned}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{aligned}}}

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

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

${\displaystyle \lim _{n\to \infty }\operatorname {argmin} f_{n}\subseteq \operatorname {argmin} f.}${\displaystyle \lim _{n\to \infty }\operatorname {argmin} f_{n}\subseteq \operatorname {argmin} f.}

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

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

• 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.