2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – The Masked Avenger May 29 '14 at 22:53
  • 1
    $\begingroup$ 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$? $\endgroup$ – user35593 May 30 '14 at 7:04
2
$\begingroup$

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

$\endgroup$

Your Answer

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

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