4
$\begingroup$

Consider the following definition of closed maps, defined in the book Nonlinear Programming by Bazaraa et al.:

Let $X$ and $Y$ be nonempty closed sets in $\mathbb{R}^p$ and $\mathbb{R}^q$, respectively. Let $\mathbf{A} \colon X \to Y$ be a point-to-set map. The map $\mathbf{A}$ is said to be closed at $\mathbf{x} \in X$ if for any sequences $\{\mathbf{x}_k\}$ and $\{\mathbf{y}_k\}$ satisfying

$\mathbf{x}_k \in X, \qquad\qquad\quad \mathbf{x}_k \to \mathbf{x}$

$\mathbf{y}_k \in \mathbf{A}(\mathbf{x}_k), \qquad \mathbf{y}_k \to \mathbf{y}$

we have that $\mathbf{y} \in \mathbf{A}(\mathbf{x})$. The map $\mathbf{A}$ is said to be closed on $Z \subseteq X$ if it is closed at each point in $Z$.

I'm trying to solve the following problem (which is problem 7.7 of the aforementioned book):

Let $\mathbf{A} \colon \mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}^n$ be the point-to-set map defined as follows. Given $\mathbf{x}, \mathbf{z} \in \mathbb{R}^n$, then $\mathbf{y} \in \mathbf{A}(\mathbf{x},\mathbf{z})$ means that $\mathbf{y} = c\mathbf{x} + (1-c)\mathbf{z}$ for some $c \in [0,1]$ and

$\|\mathbf{y}\| \le \| \lambda \mathbf{x} + (1-\lambda)\mathbf{z} \|$ for all $\lambda \in [0,1]$.

Show that the map $\mathbf{A}$ is closed for each of the following cases:

  1. $\|\cdot\|$ denotes the Euclidean norm; that is, $\|\mathbf{g}\| = (\sum_{i=1}^n{{g_i}^2})^{1/2}$.
  2. $\|\cdot\|$ denotes the $\ell_1$ norm; that is, $\|\mathbf{g}\| = \sum_{i=1}^n{|g_i|}$.
  3. $\|\cdot\|$ denotes the sup norm; that is, $\|\mathbf{g}\| = \max_{1 \le i \le n}|g_i|$.

I tried a lot of approaches, but I couldn't figure out what to do. Any hints and suggestions are welcome.

  • 0
    @wildildildlife: You are right; it is more meaningfully written as $\mathbf{A} \colon \mathbb{R}^n \times \mathbb{R}^n \to 2^{\mathbb{R}^n}$. Huard's papers ([[1](http://www.springerlink.com/content/x7px852102m78844/)] and [[2](http://www.springerlink.com/content/g576j60837n6765h/)]) give details on point-to-set maps.2011-03-05

1 Answers 1

3

For two points $a_1, a_2\in\mathbb{R}^n$, let $\mathcal{L}\left(a_1,a_2\right) = \left\{\lambda a_1 + \left(1-\lambda\right)a_2\: |\: \lambda \in \left[0,1\right] \right\}$, the closed line segment in $\mathbb{R}^n$ between the points $a_1$ and $a_2$. Your set map $A$ then takes a pair $\left(x,z\right)$ in $\mathbb{R}^n \times \mathbb{R}^n$ to the points in $\mathcal{L}\left(x,z\right)$ which are of minimal distance to the origin with respect to whatever norm your considering.

In the case of the Euclidean norm, $A\left(x,z\right)$ will only consist of one point for all $\left(x,z\right)\in\mathbb{R}^n \times \mathbb{R}^n$. Suppose that $\alpha_1$ and $\alpha_2$ are two distinct elements of $A\left(x,z\right)$, with $\left|\alpha_1\right| = \left|\alpha_2\right|=r$. Then $\alpha_1$ and $\alpha_2$ are two points on the boundary of an $n$-sphere of radius $r$ centered at the origin, and thus the interior points of $\mathcal{L}\left(\alpha_1,\alpha_2\right)$ are in the interior of this $n$-sphere. Since $\mathcal{L}\left(\alpha_1,\alpha_2\right)$ is contained in $\mathcal{L}\left(x,z\right)$, this contradicts our claim that $\alpha_1$ and $\alpha_2$ are of minimal distance to the origin within $\mathcal{L}\left(x,z\right)$.

It's not so hard to show that the function $f:\mathbb{R}^n \times \mathbb{R}^n \rightarrow \mathbb{R}^n$, defined by letting $f\left(x,z\right)$ equal the one point in $A\left(x,z\right)$, is continuous. This will imply the result you want in the case of the Euclidean norm.

For the other norms, things are a little more complicated. The argument above won't go through because the unit ball in each of these cases will be an $n$ dimensional hyper cube. However, you can show that either $A\left(x,z\right)$ will consist of a single point or that $\mathcal{L}\left(x,z\right)$ will contain some segment that is contained in the boundary of some ball that is centered at the origin, in which case $A\left(x,z\right)$ will be this segment.

Let $\mathcal{U}$ be the set of all $\left(x,z\right)$ in $\mathbb{R}^n \times \mathbb{R}^n$ for which $A\left(x,z\right)$ contains only one element and let $\mathcal{V}$ be the complement of $\mathcal{U}$. It's not too difficult to show that the function $f:\mathcal{U}\rightarrow \mathbb{R}^n$ defined by letting $f\left(x,z\right)$ be the unique point in $A\left(x,z\right)$ is continuous on $\mathcal{U}$, that $\mathcal{U}$ is open in $\mathbb{R}^n \times \mathbb{R}^n$, and that $\mathcal{V}$ has measure zero in $\mathbb{R}^n \times \mathbb{R}^n$.

Now let $\left(x,z\right)$ be an element of $\mathbb{R}^n \times \mathbb{R}^n$, $\left(x_k,z_k\right)$ be a sequence in $\mathbb{R}^n \times \mathbb{R}^n$ that converges to $\left(x,z\right)$, and $y_k \in A\left(x_k,z_k\right)$ a sequence in $\mathbb{R}^n$ that converges to $y\in \mathbb{R}^n$.

If $\left(x_k,z_k\right)$ has a subsequence $\left(x_{n_k},z_{n_k}\right)$ such that $\left(x_{n_k},z_{n_k}\right) \in \mathcal{U}$, for each $n_k$, then $y_{n_k}$ will converge to $y$ and we can use the continuity of $f$ on $\mathcal{U}$ to get the result we want.

Otherwise $\left(x_k,z_k\right)$ will be in $\mathcal{V}$ for all sufficiently large $k$. This puts some restrictions on what $\left(x,z\right)$ can be, and I'm going to leave it to you to figure out how to handle this case.

  • 0
    You're right. My bad!2011-03-06