2

Here is the question that I meet.

$$\min_z{\sum_j{\max(0,\Vert z-f_j\Vert_2^2-m_j^2)}}$$

Intuitively speaking, I want to obtain a point $z$ that is nearest to all other points $f_j$, but, when the distance between $f_j$ and $z$ is less than $m_j$, the loss can be omitted.

I cannot solve this problem with a closed form solution, but I can get the optimal solution by enumerating all possible cases through fixing whether the point $z$ is in the circle of $f_j$ or not.

I want to know that if there are any methods that I can use to tackle this problem?

Wei Zhu
  • 21
  • 2
    Welcome to MSE. It is in your best interest that you type your questions (using MathJax) instead of posting links to pictures. – José Carlos Santos Jul 05 '18 at 08:41
  • You could model this as a convex QCQP, $\min_{z,s_j}\sum_j s_j$ s.t. $s_i\ge|z-f_j|^2-m_j^2,s_i\ge 0$. This feels like overkill though. –  Jul 05 '18 at 09:31
  • I'm afraid the approach you describe is already the best one. It's even a bit worse than you say, since the optimum may be on one of the circles -- in that case, each of your cases would yield a result that lies outside the domain for that case, and you'd have to perform the optimization on the circles. The optimum on a circle is at the closest point on the circle to the mean of the other points involved. If the circles intersect, this might again not yield a solution, and then the optimum would be at one of the intersections. – joriki Jul 05 '18 at 09:31
  • Thank you all. Actually, I have tried to formulate the dual of the problem which is, however, pretty complicated and cannot be easily tackled by coordinate descent. I may use QCQP optimizer to tackle this problem since my data is not very large. Thanks again. – Wei Zhu Jul 05 '18 at 13:00

0 Answers0