# Optimization problem whose cardinality never exceeds 7 for some reason

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.

• Maybe because you have 3 real variable equations and 4 real variable upper bounds given. I'd test the software on examples you can compute by hand. – The Masked Avenger May 29 '14 at 22:53
• What happens if $x_1,\dots,x_n$ are equidistant distributed on a circle around $\mu$? I havent studied this problem in detail but couldnt it be that in this case the probabilietis are just $1/n$? – user35593 May 30 '14 at 7:04

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