Consider the ellipsoid described by the inequality $(x - x_c)^T P^{-1} (x - x_c) \leq 1$, where the vector $x_c \in \mathbb{R}^n$ denotes the center of the ellipsoid and the symmetric positive definite matrix $P \in \mathbb{S}^{n \times n}$ describes its shape. We do not know the parameters $x_c$ and $P$ exactly, but we know "interval bounds" for them. Concretely, we are given that $x_c \in \mathbf{x_c} \in \mathbb{IR}^n$ and $P \in \mathbf{P} \in \mathbb{IR}^{n \times n}$, where $\mathbb{IR} = \lbrace [x, y] \mid x, y \in \mathbb{R} \wedge x \leq y \rbrace$ denotes the set of all intervals. [1] A point $x \in \mathbb{R}^n$ (possibly) belongs to this "fuzzy" ellipsoid if there exists a $P \in \mathbf{P}$ and $x_c \in \mathbf{x_c}$ such that $(x - x_c)^T P^{-1} (x - x_c) \leq 1$.

The question is to find "non-fuzzy" parameters $x^*_c \in \mathbb{R}^n$ and $P^* \in \mathbb{S}^{n \times n}$ such that the ellipsoid defined by these parameters contains all points that possibly belong to the original "fuzzy" ellipsoid, and it is minimal. By minimal, I mean that it has the smallest volume possible.

I am also interested in non-optimal, but "easily" computable and reasonably small ellipsoids that satisfy the containment criterion.

Note: This paper of Arnold Neumaier gives a formula for "fuzzy" affine transformations of ellipsoids. One way to attack the problem could be finding interval bounds for the square root of the matrix $P$ (denote by $\sqrt{\mathbf{P}}$), and treat the original "fuzzy" ellipsoid as the image of the unit ball under the "fuzzy" affine transformation $x \to \sqrt{\mathbf{P}} x + \mathbf{x_c}$. This procedure will yield a non-optimal ellipsoid that satisfies the containment criterion. However, such an approach is not only computationally expensive, but might also result in (too) big ellipsoids in many cases. I couldn't figure out if (and how) Neumaier's result can be applied in a smarter way.

[1] The relation $\in$ is to be interpreted element-wise here.

  • $\begingroup$ How wide are your bounds for $P$ and $x_c$? $\endgroup$ – Arnold Neumaier Jul 30 '15 at 17:11
  • $\begingroup$ and how big is $n$? $\endgroup$ – Arnold Neumaier Jul 30 '15 at 17:23
  • $\begingroup$ @ArnoldNeumaier: Dimensionality varies within 10 and 100. Bounds for parameters $P$ and $x_c$ are quite narrow, but I am not sure how I can reasonably quantify that statement. $\endgroup$ – Mehmet Ozan Kabak Jul 30 '15 at 17:42

Your Answer

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

Browse other questions tagged or ask your own question.