Proving an infinite norm minimization problem has finite support (non-convex p-norms)

Question

Consider an optimization problem over infinite variables:

$$ \begin{align} \min_{x}~& {\left\lVert{x}\right\rVert }_p \\ \text{s.t}~& \left\langle x, a_n\right\rangle \ge 1~,~\forall n=1,\dots,N \end{align} $$ where $N\in\mathbb{N}$, $x$ and $\left\{a_n\right\}_{n=1}^{N}$ are all infinite-length vectors, the $a$'s are constant vectors, and ${\left\lVert{\cdot}\right\rVert }_p$ is the $p$-norm.

Clarification on the constraints (edited): we can assume each entry of the constraint vectors is bounded by a constant $r>0$, that is $\forall{n\in\left[{N}\right]},i: \left\lvert{a_n\left({i}\right)}\right\rvert \le r$. Unfortunately, we cannot assume that these entire vectors $\left\{{a_n}\right\}_{n=1}^{N}$ are bounded under some norms.

Prove: if the minimum is attainable, then there exists an optimal solution $x^*$ whose support, i.e. $\text{supp}\left(x^*\right)$, is finite (where the support of a vector is its non-zero entries).

I am especially interested in cases where $0<p<1$, when the objective function is no longer convex.

---

When $p=1$, there are some known proofs (e.g. on Wei 2018), but as far as I understand they all use the convexity of the $p$-norm when $p\ge 1$, e.g. to apply strong duality to the dual problem and show that there are optimal solutions with a support of at most $N$.

I started reading about quasi-convex optimization (since $p$-norms for $p\in\left[0,1\right]$ are quasi-convex), but I was thinking maybe there is a simple solution I am missing out.

---

Update: since it is already known for $p=1$, one could (at least practically) expect the sparsity would only improve for lower values of $p$. So if there are some theoretical results in that spirit, they could be relevant.

---

Any help or directions will be highly appreciated.

Answer 1

If $p=1$, $N=1$ and $a_1=(1/2,2/3,3/4,4/5,\ldots)$, the infimum equals 1 and is not achieved on a finitely supported vector (moreover, it is not achieved at all).

However if $0<p<1$ and the minimizer $x$ exists, it must have finite support (namely, of size at most $N$). To prove this, assume the contrary. Without loss of generality $x_1,\dots,x_{N+1}$ are positive. Choose a non-zero vector $b=(b_1,\dots,b_{N+1},0,0,\dots)$ orthogonal to all $a_i$'s. Choose small $t$ so that $x_i-t|b_i|>0>0$ for all $i=1,\dots,N+1$. Then by concavity of the function $x^p$ we have $$x_1^p+\ldots+x_{N+1}^p> \frac12\left((x_1+tb_1)^p+\ldots+(x_{N+1}+tb_{N+1})^p+\\+(x_1-tb_1)^p+\ldots+(x_{N+1}-tb_{N+1})^p\right).$$ Therefore one of the vectors $x\pm tb$ has smaller $p$-norm than $x$.

For $p>1$ the claim is completely false. Say, if $p=2$, $N=1$, the minimum is achieved on the vector proportional to $a_1$.

Answer 2

If one use Lagrange multipliers, there exist $\mu_1, \mu_2 , \cdots \mu_N$ such that $$ \begin{cases} p|x^*(i)|^{p-1}=\sum_{n=1}^N \mu_n a_n(i) \quad\text{ or}\\ |x^*(i)|=0\end{cases}$$ for all $i$. If $0<p<1$, and for every $n$, $\lim_{i\rightarrow \infty}a_n(i)= 0$ and then $$ \lim_{i\rightarrow \infty}\big(\frac{1}{p}\sum_n \mu_n a_n(i)\big)^{1/(p-1)}=\infty$$ but obviously $x^*(i)$ is bounded so $x^*(i)=0$ for large $i$.