Set representation of Ball in $\mathbf{R}^{n}$

Question

While studying optimization, I came across the following problem:

Problem: (exactly as written in Boyd's convex optimization book)

We consider the problem of finding the largest Euclidean ball that lies in a polyhedron described by linear inequalities, $$ \mathcal{P}=\left\{x \in \mathbf{R}^{n} \mid a_{i}^{T} x \leq b_{i}, i=1, \ldots, m\right\} $$ (The center of the optimal ball is called the Chebyshev center of the polyhedron; it is the point deepest inside the polyhedron, i.e., farthest from the boundary; see $\S 8.5 .1 .$ ) We represent the ball as $$ \mathcal{B}=\left\{x_{c}+u \mid\|u\|_{2} \leq r\right\} $$ The variables in the problem are the center $x_{c} \in \mathbf{R}^{n}$ and the radius $r$; we wish to maximize $r$ subject to the constraint $\mathcal{B} \subseteq \mathcal{P}$.

What is the issue?

I cannot figure out why we can represent the ball as: $$ \mathcal{B}=\left\{x_{c}+u \mid\|u\|_{2} \leq r\right\} $$

The description I have always used is as follows:

$$ B_{2}\left(x_{c}, r\right)=\left\{x \mid\left\|x-x_{c}\right\|_{2} \leq r\right\}=\left\{x \mid\left(x-x_{c}\right)^{T}\left(x-x_{c}\right) \leq r^{2}\right\} $$

In fact, Boyd even mentions that the ball can be written as: $$ B_{1}\left(x_{c}, r\right)=\left\{x_{c}+r u \mid\|u\|_{2} \leq 1\right\} $$

So what I am trying to achieve is a proof which clearly states that $$B_{1} = B_{2}$$

Attempt:

Let's prove that $B_{1} \subseteq B_{2}$. Let $p \in B_{1}\left(x_{c}, r\right)$. Then $$ p-x_{c}=r u \Rightarrow\left\|p-x_{c}\right\|=\|r u\|=|r| \cdot\|u\| \leqslant r \cdot 1 $$

which implies that $p \in B_{2}\left(x_{c}, r\right)$.

Now we must prove that $B_{2} \subset B_{1}$. I have no idea. I got stuck and the only thing I was able to do was picking $p \in B_{2}\left(x_{c}, r\right)$ and writing what it was supposed to satisfy, but it did not go further than that.

Thanks in advance, Lucas

Answer 1

You can use essentially the same argument in reverse.

Let $p\in B_2$. $\|p-x_c\|\le r\implies\|p-x_c\|=r\cdot\theta,\,\theta\in[0,1]$. Since $r$ is positive, $r=|r|$. Now $\|p-x_c\|=|r|\cdot\|u\|,\,\|u\|=\theta\in[0,1]\implies\|p-x_c\|=\|ru\|$ and $p-x_c=ru,\,p=ru+x_c\in B_1$.

Note that two vectors may have the same magnitude but still be different, but importantly all possible equivalent $p$ such that $\|p-x_c\|=\|ru\|$, for some $u$, are also contained in either ball.

Therefore $p\in B_2\implies p\in B_1,p\in B_1\implies p\in B_2\therefore B_1(r,x_c)=B_2(r,x_c)$.