7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Dirk Jan 15 '19 at 9:08
  • $\begingroup$ @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? $\endgroup$ – Itay Jan 15 '19 at 18:26
  • 1
    $\begingroup$ 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. $\endgroup$ – Fedor Petrov Jan 15 '19 at 18:59
  • $\begingroup$ 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. $\endgroup$ – Dirk Jan 15 '19 at 19:31
  • $\begingroup$ @FedorPetrov nice example! I now clarified that the vectors $a_n$ are bounded entry-wise. $\endgroup$ – Itay Jan 16 '19 at 9:24
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @Itay yes, of course $\endgroup$ – Fedor Petrov Jan 16 '19 at 13:20
  • $\begingroup$ 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". $\endgroup$ – Itay Jan 16 '19 at 13:40
  • $\begingroup$ 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. $\endgroup$ – Itay Jan 16 '19 at 13:44
  • 1
    $\begingroup$ 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$. $\endgroup$ – RaphaelB4 Jan 16 '19 at 13:50
  • $\begingroup$ Thank you very much, works great $\endgroup$ – Itay Jan 17 '19 at 14:44
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Itay Jan 16 '19 at 9:22
  • $\begingroup$ 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. $\endgroup$ – Dirk Jan 16 '19 at 9:32
  • $\begingroup$ @Dirk Even though it is true for $p=1$? $\endgroup$ – Itay Jan 16 '19 at 9:33
  • $\begingroup$ 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. $\endgroup$ – Dirk Jan 16 '19 at 9:35
  • $\begingroup$ 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). $\endgroup$ – Itay Jan 16 '19 at 9:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.