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
-
Official comment
-
Gurobi Staff
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. -
-
-
You can use the addGenConstrNorm method to let Gurobi automatically model the 2-norm.
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 \(AX-X\) term. We can then use the auxiliary variable to model the 2-norm.
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 -
Post is closed for comments.
Comments
5 comments