# Exercise: optimization and limit

Let $\underline{a}_N:=(a_1,...,a_N)^\top \in \mathbb{R}^N$ denote a vector of lenght $N$.

Define $$x_N^* := \arg \min_{x \in \mathbb{R}} \left\| \underline{a}_N - x \mathbb{1}_N \right\|_p$$

where $\mathbb{1}_N = (1,1,...,1)^\top \in \mathbb{R}^N$ and $\left\| \cdot \right\|_p$ is the $p$-norm, defined as $\left\| y \right\|_p = \left( \sum_{i=1}^N |y|^p \right)^{1/p}$.

Also define $$\xi_N^* := \arg \min_{x \in \mathbb{R}} \left\{\left\| \underline{a}_N - x \mathbb{1}_N \right\|_p + x \right\}$$

Prove that $$\lim_{N \rightarrow \infty} |x_N^* - \xi_N^*| = 0$$

Notes: I tried differentiating $\left\| \underline{a}_N - x \mathbb{1}_N \right\|_p$ with respect to $x$, but then you get $|a_i - x|$ that is not differentiable. I mean that if we assume that $a_i - x > 0 \ \forall i$ then we don't need the absolute value in the norm definition.

-

Take $p=1$, and let the vector $\underline{a}_N$ be the first $N$ elements of the following sequence $(0,1,0,1,0,1,...)$. Then, the sequence of costs for the norm minimization problems are: $$|x|, \ |x|+|1-x|, \ 2|x|+|1-x|,\ 2|x|+2|1-x|,\ ...$$ The minimizing $x$ (more than a single point for some problems) for these problems are: $$0, \ [0,1], \ 0, \ [0,1], \ ...$$ The minimizing $x$ for the perturbed problem is always $0$.
So, we could take the minimizers of the first problem as $(0,1,0,1,0,1,...)$, in which case the limit of the differences doesn't even exist (it alternates between $0$ and $1$).
Interesting. Then what happens if we have $p$ even? – Adam May 10 '12 at 15:40
For instance, what happens if $p=2$??? – Adam May 11 '12 at 15:37