# Sparsity-Promoting Convex Optimization Over Simplex

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?

• 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.) Aug 31 '19 at 3:51
• 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. Aug 31 '19 at 4:46
• @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. Aug 31 '19 at 7:04
• 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. Aug 31 '19 at 14:17
• @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. Aug 31 '19 at 16:36

Very interesting question.

One option is to relax the cardinality regularizer to the reciprocal of an infinity norm, i.e., replace $$\mathrm{card}(x)$$ with $$1 / \|x\|_{\infty}.$$ This yields a non-convex problem, but one that can be solved by solving $$n$$ convex programs, each of dimension $$n+1$$.

In particular, the problem $$\begin{equation*} \begin{array}{ll} \mbox{minimize} & f(x) + \lambda /\|x\|_{\infty} \\ \mbox{subject to} & x \geq 0 \\ & \mathbf{1}^Tx = 1 \end{array} \end{equation*}$$

is equivalent to solving the following problem, for $$i = 1, \ldots, n$$,

$$\begin{equation*} \begin{array}{ll} \mbox{minimize} & f(x) + t \\ \mbox{subject to} & x_i \geq \lambda / t \\ & x \geq 0 \\ & \mathbf{1}^Tx = 1 \\ & t \geq 0 \end{array} \end{equation*}$$

and taking as the solution with smallest optimal value to be the solution of your original problem (here, $$t \in \mathbf{R}_{+}$$ is a slack variable).

In some settings, it can be shown that this relaxation exactly recovers the minimum-cardinality solution.

This relaxation is suggested in the paper "Recovery of Sparse Probability Measures via Convex Programming," which explains how to solve the relaxed problem and characterizes its solutions.

• This is a great answer — thank you! That paper is very interesting and an easy read. Apr 26 '20 at 17:29