Non-linear unconstrained optimization problem

[JuanHu]

So I'm currently trying to use Gurobi to solve a non-linear unconstrained optimization problem in the form of:

min   sqrt[(x-x1)^2+(y-y1)^2] +sqrt[(x-x2)^2+(y-y2)^2]+ sqrt[(x-x3)^2+(y-y3)^2] +...

I know Gurobi cannot solve this type of problem directly, so I tried to use piecewise linear functions to approximate it but so far it only works for functions of single variable, but I want an optimal solution over both x and y.

I was wondering if there's any existing library that can solve this type of problem, or built-in functions use gradient descent algorithm like what excel solver does? Is there a good way to solve this type of problem?

Thanks!

[Johan Löfberg]

This is an SOCP-representable function which Gurobi supports

let  = [x;y] etc and you have 

minimize norm(z-z1) + norm(z-z2) + ....

which you can write as

minimize t1+t2+...

subject to norm(z-z1)<=t1, norm(z-z2)<=t2

those constraints are standard SOCP cones which Gurobi has direct support for

[Tobias Achterberg]

Exactly. And to avoid confusion, you need to write the constraints in quadratic form (and
not take the square root), like this:

z ^2 - 2 z * z1 + z1 ^2 - t1 ^2 <= 0

Regards,

Tobias

[JuanHu]

Thanks for the answer! However, I'm not sure about how to initialize a vector variable z = [x;y], could you explain more about this?

[JuanHu]

Thanks!

However I'm confused about how to represent norm(z-z1) and z = [x;y] in gurobi?

[Tobias Achterberg]

Don't get confused by the vector syntax. This has nothing to do with Gurobi.

As far as I understand, with given points (x1,y1), (x2,y2), ..., (xn,yn) you
want to find the point (x,y) that has the smallest sum of Euclidean distances to
the given points. Hence, you want to solve

min sqrt((x-x1)^2 + (y-y1)^2) + ... + sqrt((x-xn)^2 + (y-yn)^2)

What you need to do is to formulate this as a second order cone program (SOCP)
as follows:

min t1 + ... + tn
s.t. x^2 - 2*x*x1 + x1^2 + y^2 - 2*y*y1 + y1^2 <= t1^2
...
x^2 - 2*x*xn + xn^2 + y^2 - 2*y*yn + yn^2 <= tn^2

If you move variables to the left and constants to the right, this looks as follows:

min t1 + ... + tn
s.t. x^2 + y^2 - t1^2 - 2*x1*x - 2*y1*y <= - x1^2 - y1^2
...
x^2 + y^2 - tn^2 - 2*xn*x - 2*yn*y <= - xn^2 - yn^2

Make sure that you create variables x and y as free variables (i.e., with lower
bound -infinity and upper bound +infinity), while the t1,...,tn variables are
non-negative (i.e., lower bound 0, upper bound +infinity).

The constraints are so-called "rotated second order cones", with which Gurobi
can deal with. My guess is that the problem is very easy to solve.


Best regards,

Tobias

[JuanHu]

Thank you so much!