Equivalence of closed level sets and lower semi continuity

291 Views Asked by At

Let $E$ be a finite-dimensional inner product space, and $f:E\to [-\infty,\infty]$ be a function whose all level sets are closed. Theorem 2.6 in this beautiful book claims that $f$ is lower semi-continuous. The proof is short but I am not sure how to prove the (probably trivial) part that says

Take $\alpha$ that satisfies $$\lim_{n\to\infty}\inf f(x_n)<\alpha<f(x^*).$$ Then there is a subsequence $\{x_{n_k}\}_{k\geq 1}$ such that $f(x_{n_k})\leq \alpha$ for every $k\geq 1$.

How can we formally prove that the "then" part is correct? Why can't we use "$<\alpha$" instead of "$\leq \alpha$"? Does it suffice to use only the first inequality without the second one?

2

There are 2 best solutions below

6
On

The following very detailed answer is based on the hints from @Kurt in the comments with the original proof in the book. I was mainly missing Lemma 2 below, which seems to be trivial to the author, as the OP staff and commenters, and I will appreciate a reference to a book or the closest lemma. The other lemma and definitions can be found in the cited lectures which were taken from this book. There are related questions in this web-site on the main claim, so I hope it would help them too and appreciate any feedback.

$\newcommand{\REAL}{\mathbb{R}}$ $\newcommand{\Lev}{\mathrm{Lev}}$ $\newcommand{\N}{\mathbb{N}}$ $\newcommand{\R}{\mathbb{\REAL}}$ $\newcommand{\br}[1]{\left\{#1\right\}}$

Notation and basic definitions. The set $\N$ is the union of natural numbers (excluding zero). The set $E$ is a finite-dimensional inner product space (the references may assume $E=\R$ but the proofs hold for the general case). A sequence in a set $S$ is a function $y:\N\to S$ which is denoted by $\br{y_n}_{n\in \N}:=\br{y(n)}_{n\in \N}$. For a strictly increasing sequence $\br{n_k}_{k\in \N}\subseteq \N$, the sequence $\br{x_{n_k}}_{k\in N}$ is called a subsequence. The limit inferior of a sequence $\br{x_n}_{n\in \N}$ is defined by

\begin{equation}\tag{1}\label{infdef} \lim_{n\to\infty}\inf x_n: =\lim_{n\to\infty}(\inf_{m\geq n} x_m). \end{equation} A function $f:E\to [-\infty,\infty]$ is called lower semicontinuous at $x\in E$ if \begin{equation}\label{semis} f(x)\leq \lim_{n\to\infty}\inf f(x_n). \end{equation} for any sequence $\br{x_n}_{n\in \N}\subseteq E$ for which $\lim_{n\to\infty} x_n=x$. The function is lower semicontinuous if it is lower continuous at every $x\in E$. For every $\alpha\in\R$, the $\alpha$-level set of a function $f:E\to[-\infty,\infty]$ is the set $$\Lev(f,\alpha):=\br{x\in E\mid f(x)\leq \alpha}.$$

Lemma 1 (all subsequences of a convergent sequence converge to the same limit as the original sequence) [Theorem 2.5.2 here] Let $\br{x_n}_{n\in \N}\subseteq E$ and $x\in E$ such that $$ \lim_{n\to\infty} x_{n}=x. $$ Let $\br{x_{n_k}}_{k\in N}\subseteq \br{x_n}_{n\in N}$ be a subsequence. Then $$ \lim_{k\to\infty} x_{n_k}=\lim_{n\to\infty} x_n. $$ $\square$

Lemma 2 [Could not find a reference and will appreciate one] Let $\br{x_n}_{n\in \N}\subseteq \REAL$ be a sequence, and $\alpha\in\REAL$ such that \begin{equation}\tag{2}\label{limm} \lim_{n\to\infty} \inf x_n<\alpha. \end{equation} Then, there is a subsequence $\br{x_{n_k}}_{k\in N}$ such that $x_{n_k}<\alpha$ for every $k\in N$. $\newcommand{\eps}{\varepsilon}$

Proof. Let $\ell:=\lim_{n\to\infty} \inf x_n$, $\eps:=\alpha-\ell$, $n_0=-\infty$, and $k=1$. By \eqref{limm} and Definition \eqref{infdef}, there is $z\in \N$ such that, for every $n>\max\{z,n_{k-1} \}$, $$|\inf_{m\geq n}x_{m}-\ell|<\eps.$$ In particular, $\inf_{m\geq n}x_{m}<\ell+\eps=\alpha$.

By the last inequality and the definition of $\inf$, there is an integer $n_k\geq n$ such that $x_{n_k}<\alpha$. By definition of $n$ and $n_k$, we also have $n_k\geq n >n_{k-1}$. Recursively applying the above construction of $x_{n_k}$ for every $k\geq1$, yields the desired subsequence $(x_{n_k})_{k\in\N}$.

$\square$

We are now ready to prove the main claim.

Theorem (closedness of level-sets implies lower semicontinuity) [Theorem 2.6 here] Let $f:E\to[-\infty,\infty]$ such that, for every $\alpha\in\REAL$, the level-set $$\Lev(f,\alpha):=\br{x\in E: f(x)\leq \alpha}$$ is closed. Then $f$ is lower semicontinuous.

Proof. Suppose that all the level sets of $f$ are closed. Assume by contradiction that $f$ is not lower semicontinuous. Hence, there is $x\in E$ and $\br{x_n}_{n\in \N}\subseteq E$ such that \begin{equation}\tag{5}\label{liminfn} \lim_{n\to\infty} x_n=x, \end{equation} and \begin{equation}\tag{6}\label{liminf} \lim_{n\to\infty} \inf f(x_n)< f(x). \end{equation} By \eqref{liminf}, and since $\REAL$ is continuous, there is $\alpha\in\REAL$ such that \begin{equation}\tag{7}\label{asscon} \lim_{n\to\infty} \inf f(x_n)<\alpha <f(x). \end{equation} Using the first inequality of \eqref{asscon}, substituting $x_n:=f(x_n)$ in Lemma 2, yields that there is a subsequence $\br{f(x_{n_k})}_{k\in \N}$ such that $f(x_{n_k})<\alpha$ for every $k\in \N$. That is, \begin{equation}\tag{8}\label{knk2} \text{$x_{n_k}\in \Lev(f,\alpha)$ for every $k\in \N$.} \end{equation} By Lemma 1 and \eqref{liminfn}, respectively, \begin{equation}\tag{9}\label{knk1} \lim_{k\to\infty} x_{n_k} =\lim_{n\to\infty} x_n =x. \end{equation}

Since $\Lev(f,\alpha)$ is closed by assumption, \eqref{knk2} and \eqref{knk1} implies $x\in \Lev(f,\alpha)$. That is, $f(x)\leq \alpha$, contradicting the last inequality of \eqref{asscon}.

$\square$

2
On

Proof that $\liminf\limits_{n\to\infty}x_n<\alpha$ implies the existence of a subsequence $(x_{m_n})$ whose limit is less than $\alpha\,:$

  • Since $\ell$ is the smallest limit point there exists (by definition of limit point) a subsequence $x_{n_k}$ whose limit is $\ell$. Done.

  • When you use the alternative definition of $\liminf\limits_{n\to\infty} x_n$ as being the limit of the sequence $y_n=\inf\limits_{m\ge n}x_n$ then for every $\epsilon>0$ there exists an $N$ s.t. for all $n\ge N$ we have $y_n\in (\ell-\varepsilon,\ell+\varepsilon)\,.$ In particular this holds for $$ \epsilon=\alpha-\ell\,. $$Since $y_n$ is an inf there exists an $m\ge n$ s.t. $x_m\in(\ell-\varepsilon,\ell+\varepsilon)\,.$ We take the smallest such $m$ and label it $m_n$ since it depends on $n\,.$ Likewise, for $k>n$ there exists a smallest $m_k\ge k$ s.t. $x_{m_k}\in(\ell-\varepsilon,\ell+\varepsilon)\,.$ Clearly, $m_k\ge n\,.$ If $m_k$ were less than $m_n$ this would contradict the definition of $m_n\,.$ Therefore the sequence $(m_n)$ is increasing.