Localization via Range Measurement: proof of intermediate result

In the localization via range measurement problem, the application of Lagrange duality leads to the function of x_0 in mathbf{R}^3, y in mathbf{R}^m_+

 F(x_0,y) := sum_{i=1}^m y_i R_i^2 +max_x : left(|x-x_0|_2^2 - sum_{i=1}^m y_i |x-x_i|_2^2 right).

We can express the function F(x_0,y) in closed-form, as follows.

The objective function of the maximization problem defining F(x_0,y) expresses as

 |x-x_0|_2^2 - sum_{i=1}^m y_i |x-x_i|_2^2 = left(1-sum_{i=1}^m y_i right) x^Tx +2x^T(Xy-x_0) + x_0^Tx_0 + y^T z, hspace{.1in} (*)

where for notational convenience we use the matrix X := (x_1,ldots x_m) and vector with components z_i = R_i^2 - x_i^Tx_i, i=1,ldots,m.

The above immediately implies that the maximum in the definition of F(x_0,y) is +infty when the coefficient of x^Tx is positive. If that coefficient is zero, then we must have x_0 = Xy for F(x_0,y) to be finite. Thus, we impose the constraint

 sum_{i=1}^m y_i > 1 mbox{ or } sum_{i=1}^m y_i = 1 mbox{ and } x_0 = Xy.

Assume that the first constraint holds. When this constraint is in place, computing F(x_0,y) is a concave quadratic maximization problem without any constraints, and can be solved in closed form by taking derivatives. The corresponding maximizer is

 x^ast = frac{1}{sum_{i=1}^m y_i -1} left( Xy - x_0 right).

Plugging that value of x in the objective leads to

 F(x_0,y) = x_0^Tx_0 + y^T z + frac{1}{sum_{i=1}^m y_i -1}|Xy-x_0|_2^2.

Assume now that the second constraint holds: sum_{i=1}^m y_i = 1, and x_0 = Xy. Then F(x_0, y) reduces to the constant part in (*), that is, x_0^Tx_0 + y^T z. To summarize:

 F(x_0,y) = left{ begin{array}{ll}  x_0^Tx_0 + y^T z + frac{|Xy-x_0|_2^2}{sum_{i=1}^m y_i - 1} & mbox{if } sum_{i=1}^m y_i > 1,  x_0^Tx_0 + y^T z & mbox{if } sum_{i=1}^m y_i = 1, ;; x_0 = Xy,  +infty & mbox{otherwise.} end{array} right.