6
$\begingroup$

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?

$\endgroup$
5
  • $\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$ Aug 31, 2019 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$ Aug 31, 2019 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, 2019 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$ Aug 31, 2019 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, 2019 at 16:36

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ This is a great answer — thank you! That paper is very interesting and an easy read. $\endgroup$
    – cdipaolo
    Apr 26, 2020 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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