# Proving existence of coefficients minimizing $\|y - a_1 x_1 - a_2 x_2 - \ldots - a_n x_n\|$

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.

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

## 1 Answer

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.