Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Please feel free to correct the tags. –  Maryam Mar 4 '11 at 20:25
    
I had never heard the term "point-to-set map", but I would expect it to mean a function which sends a "point" (e.g. in R^n) to a "set of points". Your A seems to send two points (x,z) to the line segment (= "set of points") from x to z. But how can A then have codomain R^n, instead of {lines in R^n} or somethin like that? –  wildildildlife Mar 4 '11 at 23:47
    
@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] and [2]) give details on point-to-set maps. –  Sadeq Dousti Mar 5 '11 at 3:05
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
    
I think the last paragraph is inaccurate. It should read as "Otherwise $(x_k,z_k)$ will be in $\mathcal{V}$ for infinitely many $k$." –  Sadeq Dousti Mar 5 '11 at 19:33
    
@Sadeq: Are you sure? $\mathcal{V}$ is the complement of $\mathcal{U}$, and if there do not exist infinitely many of the $\left(x_k,z_k\right)$ in $\mathcal{U}$ then there must exist some $N$ for which $\left(x_k,z_k\right)\in \mathcal{V}$ for all $k>N$. –  Albert Steppi Mar 5 '11 at 20:37
    
You're right. My bad! –  Sadeq Dousti Mar 6 '11 at 3:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.