Optimization: Solving the problem $\min_{x \in \mathbb{R}^n} \sum_{k=1}^{m} a_k \|x-x_k\|^2$

Question

I do not know how to start with the following exercise:

Let $x_1,x_2,\ldots,x_m \in \mathbb{R}^n$ be arbitrary and $a_1,a_2,\ldots,a_m$ strictly positive real numbers. Solve the following problem:

$$\min_{x \in \mathbb{R}^n} \sum_{k=1}^{m} a_k \|x-x_k\|^2$$

I think that this problem corresponds to finding the point hat is geometricallly "closest" to the $x_k$ (under weighted distances) but I do not know how to go further from here.

Could you help me?

score 2 · Answer 1 · answered Jun 13 '18 at 21:28

2

Given

$$ f(x) = \sum_{k=1}^{m} a_k \|x-x_k\|^2 $$

the stationary point is determined by solving

$$ f'(x)=0 $$

or

$$ \sum_{k=1}^m a_k (x-x_k) = 0\Rightarrow x\sum_{k=1}^m a_k = \sum_{k=1}^m a_k x_k $$

and then

$$ x = \frac{\sum_{k=1}^m a_k x_k}{\sum_{k=1}^m a_k} $$

answered Jun 13 '18 at 21:28

Cesareo

33,252

The derivation is fine if x is one dimensional. What about n dimensional (original question)? – herb steinberg Jun 13 '18 at 21:41
This is a $n$-dimensional solution. Think that $\sum a_k x_k \in R^n$ – Cesareo Jun 13 '18 at 22:16
What does f'(x)=0 mean when x is n dimensional? – herb steinberg Jun 14 '18 at 15:18
It is a short notation for $\nabla f(x) = 0$ – Cesareo Jun 14 '18 at 15:42

Optimization: Solving the problem $\min_{x \in \mathbb{R}^n} \sum_{k=1}^{m} a_k \|x-x_k\|^2$

1 Answers1