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](https://arxiv.org/abs/1810.05369)), 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.



Proving an infinite norm minimization problem has finite support (non-convex p-norms)
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$.


