# Reformulating a Euclidean distance minimization problem into a semidefinite program

The following minimization problem is a Euclidean distance form of a single-facility location problem

$$\min \quad \sum_j \sqrt {(x-a_j)^2+(y-b_j)^2}$$

where $(x,y)$ and $(a_j,b_j)$ are the coordinates of the new facility and current facilities, respectively.

I mistakenly tried to reformulate it as a second-order conic program (SOCP) and found that it is not possible. I wonder, is it possible to reformulate it as a convex program using semidefinite cones?

• Your premise is wrong. This is indeed SOCP representable, as Johan says. But formulating SOCPs as QCPs is not straightforward, because not all SOCPs can be formulated as QCPs. Each solver has a specific way of representing SOCPs. Jun 12 '17 at 14:40
• As you said, the issue here is going from SOCP to QCP. Thanks @Johan for his reformulation $s+t$ subject to $|q||≤t,||p||≤s$, I forgot to add non-negativity on $t,s$. Hence, the problem becomes QCP as well. Jun 13 '17 at 6:24

For instance, minimizing $||q|| + ||p||$ is equivalent to minimizing $s + t$ subject to $||q||\leq t, ||p||\leq s$ which is an SOCP in standard form.
• I believe a typical mistake is to forget to add non-negativity on the convexity-destroying term, i.e. the SOCP $||q||\leq t$ is written as the quadratic constraint $q^Tq-t^2\leq 0$ when using cplex etc, and it is crucial to include $t\geq 0$, otherwise the model is not a QCP version of a SOCP. Jun 12 '17 at 17:59