Q matrix is not positive semi-definite (PSD) when solving the geometric median problem

Answered

Stefan Nedeljkovic

• May 19, 2022 08:44
• Edited

I'm trying to solve the geometric median problem, as described here: https://documentation.sas.com/doc/en/pgmsascdc/v_025/casmopt/casmopt_conicsolver_examples02.htm

I know that this problem is convex, but Gurobi complains about the Q matrix not being SDP. Here is my Python code: https://pastebin.com/t7jELAfF 

Any help is appreciated!

0

• 

  Jaromił Najman

  Gurobi Staff

  • May 19, 2022 09:33

  The constraint in it's current state is not a SOC by definition due to the linear parts. This can be easily fixed by defining additional variables for each point square

  for i, (point, d) in enumerate(zip(offset_points, D)):
          xp = model.addVar(lb = - GRB.INFINITY, name="xp_point_%d"%(i) )
          yp = model.addVar(lb = - GRB.INFINITY, name="yp_point_%d"%(i) )
          model.addConstr(xp == x - point[0])
          model.addConstr(yp == y - point[1])
          model.addConstr(xp ** 2 + yp ** 2 <= d ** 2, f"dist_const_{i}")
          model.addConstr(0 <= d)

  This should fix your problem.

  0
• 

  Stefan Nedeljkovic

  • May 19, 2022 10:46

  

  

  Thank you very much Jaromil!

  0

Please sign in to leave a comment.