Their approach minimises the total variation of the geographic location for each person with other the people for which there they have reciprocal mentions. Essentially it's minimising the sum_k of abs(l_i - l_k) where l_i is the location of a particular person and l_k is a "friend". If the members of l_k are spread out geographically around the world you will get poor location accuracy. This is what I mean by not being robust.
As for optimisation: I only read the paper quickly and didn't really see as you formal proof of convergence for their optimisation approach. They should use a scheme which is known to be globally convergent such as LADMPSAP.