Skip to main content

Second order cone constraint

Answered

Comments

3 comments

  • Maliheh Aramon
    Gurobi Staff Gurobi Staff

    Hi, 

    You can already add a constraint in the form \(||x-c|| \leq r \) and it will be automatically transformed into a form that Gurobi accepts as a quadratic constraint with convex feasible region (see the script below). Adding auxiliary variables/constraints does not make an optimization problem necessarily more difficult. In general, there is no correlation between problem size and the runtime with Gurobi.

    n = 5
    c = np.random.rand(n)

    m = gp.Model()
    x = m.addMVar(n, name="x")
    r = m.addMVar(1, name="r")

    m.addConstr(((x - c) * (x - c)).sum() <= r*r, name="c")
    m.optimize()

    Best regards,

    Maliheh

    1
  • Mindaugas Kepalas
    First Comment
    First Question

    Thank you for the answer.

    I am actually trying to solve the Weber problem using gurobi: for a set of points \[P_1,P_2,\dots, P_n\] find the center of this set in a sense so that the sum of Euclidean distances (not squares, which would be simple) is minimized:

    \[ \min_{C} \sum_{i=1}^N ||P_i-C||_2, \; C \in \mathbb{R}^n \]

    However I get the following error: 

    GurobiError: Q matrix is not positive semi-definite (PSD). Set NonConvex parameter to 2 to solve model.

    Is it possible to formulate this problem as convex optimisation problem using gurobi (it should be convex as far as I know)?

    I am inserting my code in case you would like to take a look. 

    import gurobipy as gp
    from gurobipy import GRB

    N = 20

    np.random.seed(1)

    Qx = np.random.uniform(size=N)
    Qy = np.random.uniform(size=N)
    Q = np.column_stack([Qx, Qy])

    weights = np.ones(N)

    m = gp.Model(name='Weber')
    dist = m.addVars(range(N), vtype=GRB.CONTINUOUS, obj=weights, name="dist", lb=0, ub=GRB.INFINITY)

    x = m.addVar(vtype=GRB.CONTINUOUS, name="x", lb=-GRB.INFINITY, ub=GRB.INFINITY)
    y = m.addVar(vtype=GRB.CONTINUOUS, name="y", lb=-GRB.INFINITY, ub=GRB.INFINITY)

    # point distances to center
    for n in range(N):
        constr_name = f"dist_client{n}"
        m.addConstr((Qx[n]-x)**2 + (Qy[n]-y)**2 <= dist[n]**2, name=constr_name)        

    # The objective is to minimize the sum of total distances
    m.ModelSense = GRB.MINIMIZE

    # Solve
    m.optimize()

    If I change 

    m.addConstr((Qx[n]-x)**2 + (Qy[n]-y)**2 <= dist[n]**2)        

    to

    m.addConstr((Qx[n]-x)**2 + (Qy[n]-y)**2 <= dist[n])        

    code works fine.

    I am also interested as well in multi-Weber formulation problem in gurobi - I have similar issues.

    Help appreciated.

    Thank you.

     

    Regards,

    Mindaugas Kepalas

    0
  • Maliheh Aramon
    Gurobi Staff Gurobi Staff

    Hi, 

    Sorry, my bad. I missed that you are interested in the sum of the \(l_2\) norms. Yes, the function \(\sum_i ||x_i-x||_2\) is convex because any norm function is convex and the sum of the convex functions is also convex. 

    To model the problem such that Gurobi accepts it as convex, we need to use the original idea you also mentioned. Specifically, 

    • Define auxiliary variables \(\texttt{zx}\) and \(\texttt{zy}\) to represent \(\texttt{Qx-x}\) and \(\texttt{Qy-y}\), respectively. 
    • Replace the quadratic constraint with a second-order cone constraint. 

    See your modified script below:

    import gurobipy as gp
    from gurobipy import GRB

    N = 20

    np.random.seed(1)
    Qx = np.random.uniform(size=N)
    Qy = np.random.uniform(size=N)
    Q = np.column_stack([Qx, Qy])
    weights = np.ones(N)

    m = gp.Model(name="Weber")
    dist = m.addVars(
    range(N), vtype=GRB.CONTINUOUS, obj=weights, name="dist", lb=0, ub=GRB.INFINITY
    )

    x = m.addVar(vtype=GRB.CONTINUOUS, name="x", lb=-GRB.INFINITY, ub=GRB.INFINITY)
    y = m.addVar(vtype=GRB.CONTINUOUS, name="y", lb=-GRB.INFINITY, ub=GRB.INFINITY)
    zx, zy = m.addVars(N, name="zx", lb=-GRB.INFINITY, ub=GRB.INFINITY), m.addVars(
    N, name="zy", lb=-GRB.INFINITY, ub=GRB.INFINITY
    )

    m.addConstrs((zx[n] == Qx[n] - x for n in range(N)))
    m.addConstrs((zy[n] == Qy[n] - y for n in range(N)))

    # point distances to center
    for n in range(N):
    constr_name = f"dist_client{n}"
    m.addConstr(zx[n] ** 2 + zy[n] ** 2 <= dist[n] ** 2, name=constr_name)

    # The objective is to minimize the sum of total distances
    m.ModelSense = GRB.MINIMIZE

    # Solve
    m.optimize()

     

    Best regards,

    Maliheh

    0

Please sign in to leave a comment.