MIQP with matrix multiplication

Answered

Yağız Dereboy

• May 16, 2022 09:12

Hello. 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

0

• 

  Jaromił Najman

  Gurobi Staff

  • May 16, 2022 13:02
  • Edited

  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
• 

  Yağız Dereboy

  • May 16, 2022 13:19

  

  

  

  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
• 

  Yağız Dereboy

  • May 16, 2022 13:26
  • Edited

  

  

  

  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
• 

  Jaromił Najman

  Gurobi Staff

  • May 17, 2022 06:30
  • Edited

  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.