Minimizing a function of a complex variable

Question

Given complex numbers $z_1,z_2,z_3,\ldots,z_n \in \mathbb{C}.$ Does there exist a $z \in \mathbb{C}$, for which the function $$f(z) = \sum_{j=1}^n |z-z_j|$$ achieves a global minimum? If yes, then find $z$.

Not sure how to approach this problem. Any advice?

Answer 1

This is equivalent to the geometric median problem in $\mathbb{R}^2$. That is: for each $z_j$, define $$\bar{z}_j \triangleq \begin{bmatrix} \Re z_j \\ \Im z_j \end{bmatrix}$$ Then the geometric median is the solution of $$\bar{z}=\arg\min \sum_{i=1}^n \|z-\bar{z}_j\|_2.$$ To recover your answer, $z=\bar{z}_1+j\bar{z}_2$. Note that if we were minimizing the sum of squared distances/magnitudes, the simple mean $z=n^{-1}\sum_j z_j$ would be the answer.

According to this article, when the points are not collinear, the geometric median is unique. When all of the points lie on a straight line, the minimum is achieved at any one-dimensional median, which may not be unique.

There is no closed-form solution for arbitrary $n$. However, it's a simple convex optimization problem, so a variety of approaches can be applied to it. For example, with my Matlab toolbox CVX it can be expressed thusly, assuming the complex values $z_j$ are stored in the vector z_in:

cvx_begin
    variable z complex
    minimize(sum(abs(z-z_in))
cvx_end

CVX effectively makes use of the $\mathbb{R}^2$ mapping above, and converts the model to a second-order cone program (SOCP). The equivalent SOCP standard form is $$\begin{array}{ll} \text{minimize} & \textstyle \sum_j y_j \\ \text{subject to} & \| \bar{z} - \bar{z}_j \| \leq y_j, ~ j=1,2,\dots,n \end{array}$$ where the variables are $\bar{z}\in\mathbb{R}^2$ and $\bar{y}\in\mathbb{R}^n$ and the values $\bar{z}_j$ are defined above. There are plenty of solvers out there that can handle SOCP, so there's no need to use CVX if you don't want to.

Wikipedia describes Weiszfeld's algorithm, and claims it converges almost always. Expressed in this complex form, we have

$$z^{(i+1)} = \frac{ \sum_j z_j / | z_j - z^{(i)} | }{ \sum_j 1 / | z_j - z^{(i)} |}$$ The article claims that difficulties arise if the initial iterate (or presumably any others) coincides exactly with one of the points. It seems to me that the geometric mean would be a good initial point in practice, save this one caution.