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

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, 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.

• I think a feasible way is to use directional derivatives in feasible directions: If $x^*$ is a solution and $e$ is a vector such that $x^*+e$ does still fulfill the inequality constraints (i.e. $\langle e,a_n\rangle\leq 0$) and use that $\sum |x_i^*|^p\leq \sum |x_i^*+e_i|^p$. – Dirk Jan 15 '19 at 9:08
• @Dirk Thank you for the answer, but I am not sure I follow. Isn't the inequality you've written trivial since $x^*$ is an optimal solution? – Itay Jan 15 '19 at 18:26
• well, and what are conditions on vectors $a_n$? Say, if $N=1$ and $a_1=(1,2,3,\dots)$, the infimum of $\|x\|_p$ is 0. – Fedor Petrov Jan 15 '19 at 18:59
• Sure, but that's one inequality you can work with, e.g. you could try to plug in $te$ instead of $e$ and divide through $t$ and let $t\to 0$ and maybe arrive at some contradiction if too many $x^*_i$ are non-zero. – Dirk Jan 15 '19 at 19:31
• @FedorPetrov nice example! I now clarified that the vectors $a_n$ are bounded entry-wise. – Itay Jan 16 '19 at 9:24

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

• @Itay yes, of course – Fedor Petrov Jan 16 '19 at 13:20
• Again, nice counter example. In the light of your comment, I guess a more accurate claim should be "if optimal solutions are attainable, then there exists such a solution with a finite support". – Itay Jan 16 '19 at 13:40
• I will however reread the two references (proving it for $p=1$) I gave in the comments to the other answer. It is interesting if the explicitly narrow down their proof to cases when the solution is attainable. – Itay Jan 16 '19 at 13:44
• One could still say on that example is that there exist $K>0$ such that for any $L$, the solution of the optimal problem restricted to $[0,L]$ is on a support of size bounded by $K$. – RaphaelB4 Jan 16 '19 at 13:50
• Thank you very much, works great – Itay Jan 17 '19 at 14:44

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

• Thank you for your answer. If I understand correctly, you say that $a_n\left(i\right)$ goes to zero because you implicitly assume $\left\lVert{a_n}\right\rVert$ is bounded by some constant under some norm. I cannot assume this in my task, and I now added a clarification to the question. Moreover, even if it was true, what happens to this proof if only one coordinate of each vector $a_n$ is nonzero? I guess these limits turn undefined. – Itay Jan 16 '19 at 9:22
• I think that for $a$ merely in $\ell^\infty$ (i.e. only bounded but not decaying to zero) you will not have that $x^*$ must be sparse. – Dirk Jan 16 '19 at 9:32
• @Dirk Even though it is true for $p=1$? – Itay Jan 16 '19 at 9:33
• Are you sure that this is also true for $p=1$? I don't think so… If I remember correctly, most papers that work with $a$'s of infinite length assume $a\in\ell^2$ or some other summability condition which implies decay to zero. – Dirk Jan 16 '19 at 9:35
• In Wei 2018 they use in equation (3.5) $a_n\triangleq \phi\left(x_n\right)$, where $\phi:\mathbb{R}^d\to \mathcal{L}^{\infty}$ (notice $x_n$ are examples, unlike our $x$). Then they show that an equivalent optimization problem to our problem with $p=1$ (eq. B.1 in Appendix B), has finite support (Lemma B.1). – Itay Jan 16 '19 at 9:48