2
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$ Jun 12 '17 at 14:40
  • $\begingroup$ 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. $\endgroup$ Jun 13 '17 at 6:24
6
$\begingroup$

It's SOCP representable, in fact it almost doesn't get more SOCP than this.

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.

$\endgroup$
7
  • 1
    $\begingroup$ Johan is correct that this is easy to formulate in SOCP form. $\endgroup$ Jun 11 '17 at 21:18
  • 1
    $\begingroup$ Perhaps you should use a modelling tool such as YALMIP or CVX to make sure it is done correctly. $\endgroup$ Jun 12 '17 at 6:08
  • 3
    $\begingroup$ I'm guessing that the problem here is the assumption that you can go from SOCP -> QCP. $\endgroup$ Jun 12 '17 at 14:43
  • 2
    $\begingroup$ 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. $\endgroup$ Jun 12 '17 at 17:59
  • 2
    $\begingroup$ I tested and removed the non-negativity bound and then cplex complained about Q not being positive semi-definite $\endgroup$ Jun 12 '17 at 20:12

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .