Computing L1 and L2 matrix norms in objective
AnsweredHi,
I currently have a model in which I want to optimize for the L1 norm (i.e. sum of all absolute values) of an expression involving my optimization variable (a matrix). The problem requires some transformations that are much easier to do in matrix form. Here is a snippet in gurobipy:
# N_1 (int)
# k (scalar)
# E (N_1 x N_1 2D np.array)
# P (N_1 1D np.array)
# Create a new model
model = gp.Model('optimization')
# Define the optimization variable with a 0 lower bound:
M = model.addMVar(shape=(N_1, N_1), name='M', lb=0)
# Process the delta ME for the objective:
delta = k*(M  E)
# Normalize each row of the difference
delta = delta/P.reshape(1, 1)
# Define the objective function:
model.setObjective(gp.abs_(delta).sum(), gp.GRB.MINIMIZE)
This yields an error:
AttributeError: 'GenExprAbs' object has no attribute 'sum'
I also tried flattening the expression delta into a vectorthis was not possible because delta was an MLinExpr, and I think I cannot get around defining it as such. So I ask:
1) Is there a way to add all absolute values of an MLinExpr object in gurobi?
2) My problem could also use (at a first pass) the L2 norm (sum of all squared entries in delta). Would that help?
3) Additionally, I would also like to minimize these norms only on the offdiagonal entries of delta. Does gurobipy offer functions similar to np.triu and np.tril? Or is it possible to select entries of delta with a mask of indices?
Thanks!

Hi Gabriel,
Is there a way to add all absolute values of an MLinExpr object in gurobi?
The short answer is: no, you have to introduce auxiliary variables.
It looks like you're wanting to set the 1norm as the objective function:
gp.abs_(delta).sum()
You can appeal to gurobipy.norm here but it can't directly use MLinExpr in the arguments, either a list of variables of a 1dim MVar, so you need to introduce auxiliary variables:
aux1 = model.addMVar((N_1, N_1), lb=float("inf"))
model.addConstr(aux1 == delta)
aux2 = model.addVar()
model.addConstr(aux2 == gp.norm(aux1.reshape((N_1*N_1)),1))
model.setObjective(aux2)Yes, this is clunky, and we will almost certainly simplify this in a future release.
Additionally, I would also like to minimize these norms only on the offdiagonal entries of delta. Does gurobipy offer functions similar to np.triu and np.tril? Or is it possible to select entries of delta with a mask of indices?
Nothing like triu or tril unfortunately but numpy.triu_indices will come in handy:
k = 1 # diagonal offset
n,m = delta.shape
i,j = np.triu_indices(n=n,m=n,k=k)
off_diag_vars = delta[i,j] # pulls the expressions into 1D MLinExpr
aux1 = model.addMVar(off_diag_vars.shape, lb=float("inf"))
model.addConstr(aux1 == off_diag_vars)
aux2 = model.addVar()
model.addConstr(aux2 == gp.norm(aux1,1))
model.setObjective(aux2) Riley
0
Please sign in to leave a comment.
Comments
1 comment