2
$\begingroup$

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.

1 Answers 1

1

Well, here is a 'counterexample' in a limiting sense.

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$).

  • 0
    For instance, what happens if $p=2$???2012-05-11