Second order cone constraint
AnsweredHello, I would like to add a second-order cone constraint of the form \[||x-c|| \leq r\] Here x is an N-dimensional vector (unknown), c is a "center" (known, N-dimensional), r is (unknown) variable and ||...|| is Euclidean norm.
I have found in the examples that it is possible to specify a constraint of the form \[x^2+y^2 \leq r^2\] where all three variables are unknown.
In this manner it would be possible to introduce N variables \[y_1=x_1-c_1, \; y_2=x_2-c_2\] and etc. and then add constraint \[y_1^2+y_2^2+...+y_N^2\leq r^2,\] but this adds N auxiliary variables and N equality constraints and I assume this should make the problem more complicated.
Is there a better approach?
Thanks.
-
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 -
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 -
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.
Comments
3 comments