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

• Official comment

  

  Simranjit Kaur

  • Gurobi Staff

  November 16, 2025 23:37

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
• 

  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

Post is closed for comments.