1
$\begingroup$

I'm having quite a bit of difficulty with the following problem from Luenberger's Optimization With Vector Space Methods:

2.9: Let $X$ be a normed linear space and let $x_1, x_2, \ldots, x_n$ be linearly independent vectors from $X$. For fixed $y\in X$, show that there are coefficients $a_1, a_2, \ldots, a_n$ minimizing $\|y - a_1 x_1 - a_2 x_2 - \ldots - a_n x_n\|$.

We're told earlier in the chapter that "an upper semicontinuous functional on a compact subset $K$ of a normed linear space $X$ achieves a maximum on $K$." So I started by considering the functional be $f:\mathbb{R}^n \to \mathbb{R}$ where: $$f(a; x_1, x_2, \ldots, x_n, y) = \|y - a_1 x_1 - a_2 x_2 - \ldots - a_n x_n\|$$ and $a = (a_1, a_2, \ldots, a_n)$. Then, I was hoping to show that $f$ is lower semicontinuous in $a$ and that the function could be restricted to some compact subset $K$ of $\mathbb{R}^n$.

[Question 1: can I just say that I'm only considering $a_1, a_2, \ldots, a_n$ in some set with a given diameter, i.e., just assume that it is totally bounded?]

For the first part, I want to show that $f$ is lower semicontinuous at $a\in K$, so I'm trying to choose $\delta$ so that for those $b\in K$ for which $\|a - b\| < \delta$ the difference between $f(b)$ and $f(a)$ is less than $\epsilon$. The difference is: \begin{align}f(b) - f(a) &= \|y - \sum_{i=1}^n b_i x_i\| -\|y - \sum_{i=1}^n a_i x_i\| \\ &\leq\|\sum_{i=1}^n (a_i - b_i) x_i\| \leq (\max \|x_i\|)\|\sum_{i=1}^n (a_i - b_i)\|\end{align} At this point, I get stuck as to how $\delta$ fits into the second term. One route I tried was letting $\delta = n\max_i |a_i - b_i|$, but I wasn't sure if I could restrict $b_i$ in this manner. I'd also somehow landed on $\delta < \frac{\epsilon\sqrt{n}}{n \max_i \|x_i\|}$, but this didn't seem to work either.

[Question 2: I feel like I'm missing something obvious here, but any tips on showing that this is LSC?]

Also, a more minor question, do you have any advice on how to write this out properly? I apologize it's so messy.

$\endgroup$
1
  • $\begingroup$ The vectors $x_i$ may be finite or infinite dimensional. The vector $a$ is just the $n$ coefficients so it is finite dimensional. $\endgroup$ – akm Sep 12 '20 at 16:02
1
$\begingroup$

After spending more time on the problem, here's what I was able to come up with. I'd appreciate any corrections you could provide:

Let $a = (a_1, a_2, \ldots, a_n)$ and $f: \mathbb{R}^n \to \mathbb{R}$ where $f(a, x_1, x_2, \ldots, x_n, y) = \|y - a_1 x_1 - a_2 x_2 - \ldots - a_n x_n\|$. When $x_1, x_2, \ldots, x_n, y$ are evident or irrelevant, I'll write this as $f(a)$.

If $y$ is in the subspace generated by $x_1, x_2, \ldots, x_n$ then there exist unique coefficients satisfying $f(a) = 0$. Otherwise, because $f(0) = \|y\|$, we can limit attention to coefficients satisfying $f(a) \leq \|y\|$, given by $K = \{a\in \mathbb{R}^n: 0 \leq f(a) \leq \|y\|\}$, where $K$ is bounded below by zero and bounded above by $\|y\|$. To show that $K$ is closed, choose $b \in K^c$ so $\|y - \sum b_i x_i\| > \|y\|$. Then, choosing $\epsilon = \frac{\|y - \sum b_i x_i\| - \|y\|}{\max\|x_i\|}$, if $c\in N_\epsilon(b)$ then $\|y - \sum c_i x_i\| > \|y\|$, meaning that $c\in K^c$ and $K^c$ is open and $K$ is closed. Because $K$ is a subset of Euclidean space and it is closed and bounded, it is compact.

Could someone please double-check the proof that $K$ is open, if possible?

We're told earlier in the chapter that "an upper semicontinuous functional on a compact subset $K$ of a normed linear space $X$ achieves a maximum on $K$." Because we want to prove that $f$ attains a minimum over $K$, we must show that $f$ is lower semicontinuous. Given $\epsilon > 0$, suppose $\|a-b\| < \epsilon/ \max \|x_i\|$. Then

\begin{align} \epsilon > (\max \|x_i\|)\|a - b\| &\geq (\max \|x_i\|)\|\sum_{i=1}^n (a_i - b_i)\| \geq \|\sum_{i=1}^n (a_i - b_i) x_i\| \\ & \geq \|y - \sum_{i=1}^n b_i x_i\| -\|y - \sum_{i=1}^n a_i x_i\| \geq f(b) - f(a) \end{align} and so $f(a) - f(b) < \epsilon$ as desired. Note that $\max \|x_i\| > 0$, since the vectors are independent. Because $f$ is lower semicontinuous over the compact subset $K$, it attains a minimum over the subset.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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