Continuity of argmin

Where here we ask what happens to the infima and sets of minimisers of sequences of functions \{f_n\}_n? under what conditions do these converge? what is an appropriate notion of convergence for functions which transfers the convergence to the corresponding sequence of its minima and minimizers? This poses a question of continuity for the infimum (as an operator) as well as the set of minimisers (as a multi-valued operator). We aim at characterising the continuity of these operators.

Pointwise convergence of f^\nu:\mathbb{R}\to\bar{\mathbb{R}}, where \bar{\mathbb{R}} = \mathbb{R} \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 in principle 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.

Figure 1. Failure of pointwise convergence of convex functions to lead to convergence of the infima of the sequence of functions.

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 \mathbb{R}^n we look at the epigraphs \mathrm{epi} f^\nu. The epigraph of a function f:\mathbb{R}^n\to\bar{\mathbb{R}} is defined as

\begin{aligned} \mathrm{epi} f =\{(x,\alpha)\in \mathbb{R}^{n+1}: f(x) \leq \alpha\} \end{aligned}

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

\begin{aligned} \inf f^\nu \to \inf f \end{aligned}

and the sets \arg\min f^\nu are eventually nonempty and form a bounded sequence with

\begin{aligned} \limsup_\nu (\arg\min f^\nu) \subseteq \arg\min f \end{aligned}

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, we have a strong convergence result, but this would require additional assumptions such as strict convexity. It is otherwise quite difficult to establish conditions for the convergence of the minimisers unless we 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.

Regarding 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

\begin{aligned} \arg\min: \mathcal{Z}\rightrightarrows \mathbb{R}^n, \end{aligned}

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 \mathbb{R}^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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

mathbabe

Exploring and venting about quantitative issues

Look at the corners!

The math blog of Dmitry Ostrovsky

The Unapologetic Mathematician

Mathematics for the interested outsider

Almost Sure

A random mathematical blog

Mathematix

Mathematix is the mathematician of the village of Asterix

%d bloggers like this: