Optimization problem whose cardinality never exceeds 7 for some reason

Question

I am working on a problem in which I have a collection of $n$ points, $x_1,\dots,x_n$, in the plane, as well as a positive definite matrix $\Sigma$ and another point $\mu$ in the plane. I am trying to assign probabilities $p_1,\dots,p_n$ to these $n$ points in such a way that the mean of the distribution is $\mu$ and the covariance is bounded by $\Sigma$ by a linear matrix inequality, i.e. the following problem: $$\textrm{maximize}_{p_1,\dots,p_n} \sum_i \|x_i\|p_i $$ subject to $$\sum_i p_i = 1$$ $$\sum_i x_i p_i = \mu$$ $$\sum_{i}(x_{i}-\mu)(x_{i}-\mu)^{T}p_{i}\preceq\Sigma $$ $$p_i\geq 0 \forall i$$

I'm solving this numerically and every optimal solution has at most $7$ entries that are nonzero. Is it possible to prove that this must always be the case? If I were to omit the covariance constraint, I'd just have a standard linear program that could be dealt with using complementary slackness conditions, but I have no such luxury here.

Answer 1

The reason for the small cardinality number is not the structur of the optimization problem but the dimension of the $x_i$'s and their particular values. It is easy to construct a problem that has arbitrary cardinality.

Just consider that $x_i = (1/n)e_i$ where $e_i$ is the $i$th identity vector and $\mu = (1/n^2)\mathbf{1}$ is the vector which has its entries all equal to $1/n^2$. Moreover assume that the dimension of the $x_i$'s and $\mu$ is $n$. It is clear that the constraint $\sum_i x_i p_i = \mu$ can only be satisfied with $p_i = 1/n$ (Here, it is assumed that the matrix $\Sigma$ is formed such that $\sum_{i}(x_{i}-\mu)(x_{i}-\mu)^{T}p_{i}\preceq\Sigma$ is satisfied).