Say we want to find a sparse approximate minimizer to the function $f(x) : \mathbb{R}^d \to \mathbb{R}$. Then in line with the work in the field of compressed sensing, we can instead minimize $$f(x) + \lambda \|x\|_1$$ as a convex proxy/relaxation to the desired sparsity constraint on $\|x\|_0$.

But often times optimization problems are actually already restricted to an $\ell^1$ ball. For example, say we are optimizing over the space of discrete probability distributions on $d$ elements, which can be represented as \begin{align*} \text{minimize: } & f(x)\\ \text{subj. to: } & x \succeq 0\\ & \langle \boldsymbol{1}, x \rangle = 1. \end{align*} Call that problem (P). Then since any feasible solution to (P) has $\|x\|_1 = 1$ exactly, adding the objective penalty $\lambda\|x\|_1$ cannot change the optimal solution of the problem.

Question: Is there a way to add a convex penalty / constraint to (P) so that the resulting problem (P') has a sparse solution?

  • $\begingroup$ Sparsity in a discrete probability distribution is not something that is typically desired- could you explain why you want a sparse probability distribution? (It would be much more normal to ask for a maxent distribution for example.) $\endgroup$ – Brian Borchers Aug 31 '19 at 3:51
  • $\begingroup$ One interesting regularizer is $\| x - {\bf 1}/d \|_{1}$, which measures the difference between $x$ and a discrete uniform distribution. This is somewhat similar to maxent in its effect. $\endgroup$ – Brian Borchers Aug 31 '19 at 4:46
  • $\begingroup$ @BrianBorchers, as a example, the discrete distribution might represent the proportion of assets you are investing in at a given point in time. Sparsity of the distribution means your capital is concentrated in a few assets, which could have fewer transaction costs than spreading it among many assets. $\endgroup$ – cdipaolo Aug 31 '19 at 7:04
  • $\begingroup$ Portfolios aren't the same as probabilitiy distributions. A 1-norm regularization problem has been used in portfolio optimization problems that allow for negative investments (shorts) However, the most commonly used approach is 0-1 mixed integer quadratic programming where you can penalize the actual cardinality of the investments active in the portfolio. $\endgroup$ – Brian Borchers Aug 31 '19 at 14:17
  • $\begingroup$ @BrianBorchers Thanks for reminding me that you can use the $\ell^1$ penalty if you allow for shorts. Is there a convex proxy for that cardinality constraint in the case mentioned above though? That’s my main question. $\endgroup$ – cdipaolo Aug 31 '19 at 16:36

Your Answer

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

Browse other questions tagged or ask your own question.