MIQP with matrix multiplication
AnsweredHello. I want to model an objective function which is in the form of AX  X_F where F is the frobenius norm. Fancy way of saying sum the squared terms.
My variable matrix is A and it's square and the data matrix is X. Variable matrix A has a row and column count equal to the row count of X.
It would be of great help if you can show me how I can model this with gurobi and python
Thanks

You can use the addGenConstrNorm method to let Gurobi automatically model the 2norm.
The input arguments of the addGenConstrNorm method are an output variable and a list of single Var objects. Thus, we have to introduce an auxiliary variable and equality constraint for each row of the \(AXX\) term. We can then use the auxiliary variable to model the 2norm.
import gurobipy as gp
from gurobipy import GRB
import numpy as np
N = 3
# some random square matrix
A = np.random.rand(N,N)
m = gp.Model()
X = m.addVars(N, name="X")
# l will hold the rows of AX  X, i.e.,
# l[i] = (sum_j A[i,j]*X[j])  X[i]
l = []
for i in range(N):
lexpr = gp.LinExpr(0)
for j in range(N):
lexpr.add(A[i,j] * X[j])
lexpr.add( 1.0 * X[i])
l.append(lexpr)
# the aux list will hold the auxiliary
# variables used as input for the Norm method
aux = []
for i in range(N):
v = m.addVar(lb=GRB.INFINITY, name="aux%d"%(i))
m.addConstr(v == l[i], name="aux_constr%d"%(i))
aux.append(v)
# finally add the norm constraint
# variable normaux now equals  AX  X _2
normaux = m.addVar(name="normaux")
m.addGenConstrNorm(normaux, aux, 2.0, "normconstr")
# write the model to an LP file to check whether
# everything looks as expected
m.write("myLP.lp")Best regards,
Jaromił0 
Hello, thank you so much for the response.
But I guess there was a misunderstanding though because my variables are A not X. That's also a problem I guess because my variables are in matrix form.
Such as A \in R^mxm, X \in Rmxn where A is the variables and X are the data matrix.
Let me give you the whole model I want to use
min AX  X_F + sum_j(z_j)^2
s.t
sum_i(a_ij) = 1 for every j
sum_j(a_ij) <= Mz_j for every i (Big M notation: M is a number that is very large)
sum_j(a_ij) >= k  (1  z_j)M for every i
a_ij /in [0,1]
z_j /in {0,1}
k /in Z^+
Can you please show me how can I model something like this?
0 
Objective function is:
min AX  X_F + (sum_j z_j)^2
I changed the second term so it's the square of the sum of z_j's
Sorry for the error
0 
This can be achieved in the same way, just with another \(\texttt{for}\)loop. The \( \left(\sum_j z_j\right)^2\) is not a problem. You can introduce an additional variable to model \(w= \sum_j z_j\) and then use this variable for the objective.
import gurobipy as gp
from gurobipy import GRB
import numpy as np
M = 2
N = 3
X = np.random.rand(M,N)
m = gp.Model()
A = m.addVars(M,M,name="a")
l = {}
for i in range(M):
for j in range(N):
lexpr = gp.LinExpr(0)
for k in range(M):
lexpr.add(A[i,k] * X[k,j])
l[i,j] = lexpr  X[i,j]
aux = []
for i in range(M):
for j in range(N):
v = m.addVar(lb=GRB.INFINITY, name="aux%d_%d"%(i,j))
m.addConstr(v == l[i,j], name="aux_constr%d_%d"%(i,j))
aux.append(v)
normaux = m.addVar(name="normaux")
m.addGenConstrNorm(normaux, aux, 2.0, "normconstr")
z = m.addVars(N,name="z")
w = m.addVar(lb=GRB.INFINITY,name="w")
m.addConstr(w == gp.quicksum(z),name="w_sum_z_constr")
m.setObjective(normaux + w*w, GRB.MINIMIZE)
m.write("myLP.lp")Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
4 comments