I am reading the book "Additional Exercises for Convex Optimization" [ Stephen Boyd & Lieven Vandenberghe 2016 ] where I have difficulties in understanding the content of an exercise.
Problem 4.23 : A theorem due to Schoenberg. Suppose $m$ balls in $\mathbf{R}^n$, with centers $a_i$ and radii $r_i$, have a nonempty intersection. We define $y$ to be a point in the intersection, so $$ \left\|y-a_i\right\|_2 \leq r_i, \quad i=1, \ldots, m \quad\tag{27} $$
Suppose we move the centers to new positions $b_i$ in such a way that the distances between the centers do not increase: $$ \left\|b_i-b_j\right\|_2 \leq\left\|a_i-a_j\right\|_2, \quad i, j=1, \ldots, m \quad\tag{28} $$
We will prove that the intersection of the translated balls is nonempty, i.e., there exists a point $x$ with $\left\|x-b_i\right\|_2 \leq r_i, i=1, \ldots, m$. To show this we prove that the optimal value of $$ \begin{array}{ll} \operatorname{minimize} & t \\ \text { subject to } & \left\|x-b_i\right\|_2^2 \leq r_i^2+t, \quad i=1, \ldots, m, \end{array} \quad\tag{29} $$ with variables $x \in \mathbf{R}^n$ and $t > \in \mathbf{R}$, is less than or equal to zero.
(a) Show that (28) implies that $$ t-\left(x-b_i\right)^T\left(x-b_j\right) \leq-\left(y-a_i\right)^T\left(y-a_j\right) \text { for } i, j \in I $$ if $(x, t)$ is feasible in (29), and $I \subseteq\{1, \ldots, m\}$ is the set of active constraints at $x, t$.
(b) Suppose $x, t$ are optimal in (29) and that $\lambda_1, \ldots, \lambda_m$ are optimal dual variables. Use the optimality conditions for (29) and the inequality in part a to show that $$ t=t-\left\|\sum_{i=1}^m \lambda_i\left(x-b_i\right)\right\|_2^2 \leq-\left\|\sum_{i=1}^m \lambda_i\left(y-a_i\right)\right\|_2^2 $$
I solved two previous problems but I don't understand the content of that exercise:
Question 1: Could you please explain to me why proving that the intersection of the translated balls is nonempty is equivalent to proving that the minimization problem has strictly negative optimal value?
Question 2: After proving the question (b), we obtained
$$ t=t-\left\|\sum_{i=1}^m \lambda_i\left(x-b_i\right)\right\|_2^2 \leq-\left\|\sum_{i=1}^m \lambda_i\left(y-a_i\right)\right\|_2^2 $$
How to conclude that the translated balls have nonempty intersection?
Question 3: Does Strong Duality hold for this optimization problem?
DISCUSSION :
I will first try to elaborate the content of the theorem.
Consider 3 Balls ( which are Circles in 2D ) which have certain Centers & certain Distances between Centers (I will use DC to write that).
When the Balls are $A,B,C_1$ , there is no Point of Intersection (I will use PI to write that)
The theorem is not talking about such cases.
When the Balls are $A,B,C_2$ , there is one Point of Intersection (one PI) & the Intersection Set is not Empty set.
When the Balls are $A,B,C_3$ , there are many PI elements in the Intersection set.
The theorem is talking about such cases.
(A) It is claiming that when Balls have a PI & we move the Balls around or we rotate all the Balls while keeping the Distance between Centers (DC) fixed , then the new Positions will still have a PI.
(B) It is also claiming that when Balls have a PI & we move the Balls around or we rotate all the Balls while reducing some of the Distances between Centers (DC) , then the Circles in the new Positions will still have a PI.
When we keep DC values Constant or we reduce the DC values , available PI will continue to be available.
It is almost obviously true , at least in 1D & 2D & 3D , which we can visualize easily.
INTUITIVE VISUALIZATION :
Let us consider the Case $A,B,C_3$. The DC values are along the lines of the triangle.
We have not indicated the Axis , hence no matter where we put the Axis (equivalently , no matter where we move the circles to) , the Intersection Area will move along.
That is the Case where DC values are not reducing.
When all the Balls move closer , PI will not vanish.
Consider the Case where $A$ & $B$ are fixed & $C$ moves closer to these 2.
It will look like this :
We can see that Points of Intersection is enlarging from green area to blue area.
When $A$ & $B$ get closer , the Intersection area enlarges more.
[[ This Visualization will work for 1D & 3D too. ]]
We indicate the Centers with $a_1,a_2,a_3$ & the new Centers with $b_1,b_2,b_3$.
ALGEBRAIC PROOF :
The textbook itself has this , as-is , including typos :
Schoenberg gave ( in this Paper ) this Outline :
What the writers are trying to convey :
When we have Original Centers $(y-a)^2 \le r^2$ & we convert to New Centers $(x-a)^2 \le r^2$ , we do not know that that inequality is true :
It could be $8^2 \le 6^2$ (not true) or $6^2 \le 6^2$ (true) or $4^2 \le 6^2$ (true) . Hence to make that true , we can write it like $(x-a)^2 \le r^2+t$ & try to get the minimum $t$.
$8^2 \le 6^2+t$ : minimum $t$ is $+28$ (Positive)
$6^2 \le 6^2+t$ : minimum $t$ is $0$
$4^2 \le 6^2+t$ : minimum $t$ is $-20$ (Negative)
Hence when we start with true statement , $t$ can be $0$ or even Negative.
Only when we start with false statement , $t$ is Positive.
When we show that we have Non-Positive Solution to the Minimization Problem , we know that we had true inequality statement : we did have Intersection Point $x$.
ADDENDUM :
You should make some numerical Examples in 2D & 1D & then check the Solutions. It will become clear & almost obvious.
The Question about Strong Duality is premature ( Exercise is from Chapter 4 , while Duality is from Chapter 5 )
I suggest concentrating on the theorem for now & making a new Question later to cover the Strong Duality. You could then mention that new Question here.