the continuity of argmin

how can I show the minimum of a converging sequence of continuous functions is converging to the minimum of the limit of that sequence.i.e. $$\lim_i \text{argmin}_{x} f_{i}(x)=\text{argmin}_{x} \lim_i f_{i}(x)$$

Solution 1:

$\renewcommand{\Re}{\mathbb{R}}$I think what you need is Theorem 7.33 in (1). First, pointwise convergence of $f^\nu:\Re\to\bar{\Re}$, where $\bar{\Re} = \Re \cup \{+\infty\}$, to a function $f=\lim_\nu f^\nu$ is not in general sufficient to guarantee convergence neither of $\inf f^{\nu}$ to $\inf f$ nor of $\arg\min f^\nu$ (which is a sequence of sets) to $\arg\min f$.

It is generally easier to answer the question "under what conditions $\inf f^\nu$ converges to $\inf \lim_\nu f$?" because the convergence of sets requires the introduction of a new notion of convergence.

As we can see in the animation below, we may have a sequence of continuous functions $f^\nu$ which converge pointwise to a function $f$, but neither the infima nor the sets of minimisers converge as you would expect.

What we need here is an alternative notion of convergence of sequences of functions which is better suited for the study of the convergence of infima and minimiser sets. This is exactly the epigraphical convergence of $\{f_\nu\}$.

Instead of looking at $f^\nu(x)$ at individual points $x\in\Re^n$ we look at the epigraphs $\mathrm{epi} f^\nu$. The epigraph of a function $f;\Re^n\to\bar{\Re}$ is defined as

$$ \mathrm{epi} f =\{(x,\alpha)\in \Re^{n+1}: f(x) \leq \alpha\} $$

We then need to introduce a suitable notion of convergence for sequences of sets. This is the Painleve-Kuratowski convergence, or convergence in the Fell topology.

We then say that a sequence of functions $f^\nu$ converges epigraphically to a function $f$ - we denote $f^\nu \overset{e}{\to} f$ - if the sequence of sets $\{\mathrm{epi}f^\nu\}_\nu$ converges to the epigraph to $f$ in the Painleve-Kuratowski sense.

Now, according to Thm. 7.33 in (1), assuming that the sequence $f^\nu$ is eventually level-bounded (functions $f^\nu$ have bounded level sets $\mathrm{lev}_{\leq \alpha}f^\nu = \{z: f(z) \leq \alpha\}$ for all $\nu\geq \nu_0$ for some $\nu_0\in\mathbb{N}$), and $f^\nu\overset{e}{\to} f$ and $f^\nu$ and $f$ are lower semicontinuous (i.e., they have closed epigraphs) and proper, then $$ \inf f^\nu \to \inf f$$ and the sets $\arg\min f^\nu$ are eventually nonempty and form a bounded sequence with $$ \limsup_\nu (\arg\min f^\nu) \subseteq \arg\min f $$

where $\limsup$ here is the outer limit of a sequence of sets.

Note. in the Wikipedia article on Kuratowski convergence, they use the term "limit superior" in lieu of outer limit. In (1) the authors use the term outer limit instead to avoid any confusion with the set-theoretic limit which is not a topological notion.

Note that it is possible that $\arg\min f$ contains more elements than the outer limit of $\arg\min f^\nu$.

A special case is when $\arg\min f^\nu$ are eventually singletons. Then, you have the required convergence result as you stated it in your question, but this would require additional assumptions such as strict convexity. I otherwise believe that it is quite difficult to establish conditions for the convergence of the minimisers unless you draw restrictive assumptions, e.g., that the functions are nested like $f_1\geq f_2 \geq \ldots$.

It is also important to note that according to the above theorem, the limit of $\arg\min f^\nu$ may not exist.

Now, since the title of your question is about the continuity of $\arg\min$, we should first define a space of functions $\mathcal{Z}$ on functions and equip it with an appropriate topology $\tau$ to judge whether the set-valued functional

$$ \arg\min: \mathcal{Z}\rightrightarrows \Re^n, $$

is continuous. This will be the space of lower semi-continuous and proper functions and the topology will be the topology of total epi-convergence. It would take a lot of time and effort to explain the notion of total epi-convergence, but according to Thm. 7.53 in (1), it is the same as epi-convergence in certain special cases:

when $\mathcal{Z}$ is further restricted to containing : (i) only convex functions (ii) only positive homogeneous functions

Also, if $\{f^\nu\}$ is nonincreasing, then epi-convergence of $f^\nu$ implies its total epi-convergence and, finally, if $\{f^\nu\}$ is equi-coercive, again epi-convergence is the same as total epi-convergence.

Under these assumptions, the mapping $\arg\min: \mathcal{Z}\rightrightarrows \Re^n$ is outer semi-continuous.

(1) R.T. Rockafellar and R.J-B. Wets, Variational Analysis, Grundlehren der mathematischen Wissenshaften, vol. 317, Springer, Dordrecht 2000, ISBN: 978-3-540-62772-2.