Is the Dikin Ellipsoid actually a ball?

Question

I have the inequality (row wise): $Ax \leq b$

The Dikin ellipsoid centered at $x_0$ with radius $r$ is:

$$\{z \quad | \quad (z-x_0)^T(z-x_0) \leq \frac{r^2}{H(x_0)}\}$$

where,

$$H(x_0) = \sum \frac{a_i * a_i^T}{(b_i - a_ix_0)^2}$$

$a_i$ is the $i^{th}$ row of $A$. $b_i$ is the $i^{th}$ element of $b$.

this seems like a ball to me, with radius $\frac{r}{\sqrt{H(x_0)}}$

Some references for the Dikin Ellipsoid:

http://stanford.edu/class/ee364b/lectures/dikin_slides.pdf http://ie.technion.ac.il/~ehazan/courses/LPpoly12/dan.pdf

Answer 1

Judging from the slides you provided, I think you have misunderstood the definition. In the Preliminaries section I see the definition: $$\{z \quad | \quad (z-x_0)^TH_{x_0}(z-x_0) \leq r^2\}$$ where $H_{x_0}$ is defined by $$H_{x_0} = \sum \frac{a_i^T * a_i}{(b_i - a_ix_0)^2}$$ where $a_i$ are row vectors of the matrix $A$.

However, $H_{x_0}$ is not a constant. Instead, it is a matrix acting on the vector $(z - x_0)$ in the definition of the ellipse above. You can see that it is a matrix because it is a sum of multiplications of the form $a_i^T * a_i$ which are matrices.

Answer 2

In this case it is indeed a ball in $\mathbb R^n$ with the usual Euclidean norm with the radius you say and a center at $x_0$.