Misplaced Pages

Epi-convergence

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

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

lim inf n → ∞ f n ( x n ) ≥ f ( x )  for every  x n → x  and  lim sup n → ∞ f n ( x n ) ≤ f ( x )  for some  x n → 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}}}

Extended real-valued extension

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

Denote by R ¯ = R ∪ { ± ∞ } {\displaystyle {\overline {\mathbb {R} }}=\mathbb {R} \cup \{\pm \infty \}} the extended real numbers. Let f n {\displaystyle f_{n}} be a function f n : X → R ¯ {\displaystyle f_{n}:X\to {\overline {\mathbb {R} }}} for each n ∈ N {\displaystyle n\in \mathbb {N} } . The sequence ( f n ) {\displaystyle (f_{n})} epi-converges to f : X → R ¯ {\displaystyle f:X\to {\overline {\mathbb {R} }}} if for each x ∈ X {\displaystyle x\in X}

lim inf n → ∞ f n ( x n ) ≥ f ( x )  for every  x n → x  and  lim sup n → ∞ f n ( x n ) ≤ f ( x )  for some  x n → 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}}}

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. ( f n ) {\displaystyle (f_{n})} hypo-converges to f {\displaystyle f} if

lim sup n → ∞ f n ( x n ) ≤ f ( x )  for every  x n → x {\displaystyle \limsup _{n\to \infty }f_{n}(x_{n})\leq f(x){\text{ for every }}x_{n}\to x}

and

lim inf n → ∞ f n ( x n ) ≥ f ( x )  for some  x n → x . {\displaystyle \liminf _{n\to \infty }f_{n}(x_{n})\geq f(x){\text{ for some }}x_{n}\to x.}

Relationship to minimization problems

Assume we have a difficult minimization problem

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

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

inf x ∈ C n g n ( x ) {\displaystyle \inf _{x\in C_{n}}g_{n}(x)}

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

f ( x ) = { g ( x ) , x ∈ C , ∞ , x ∉ C , f n ( x ) = { g n ( x ) , x ∈ C n , ∞ , x ∉ C n . {\displaystyle {\begin{aligned}f(x)&={\begin{cases}g(x),&x\in C,\\\infty ,&x\not \in C,\end{cases}}\\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 inf x ∈ X f ( x ) {\displaystyle \inf _{x\in X}f(x)} and inf x ∈ X f n ( x ) {\displaystyle \inf _{x\in X}f_{n}(x)} are equivalent to the original and approximate problems, respectively.

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

lim n → ∞ argmin ⁡ f n ⊆ 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.

Properties

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

References

Categories: