Similar to this question, how can I formulate a constraint involving max of the form \sum_{i=1}^m [z_i + t]_+ \leq c where [x]_+ = \max(x,0), both t,c \in \mathbb{R}, and z = My \in \mathbb{R}^m for variable y \in \mathbb{R}^n with data matrix M \in \mathbb{R}^{m \times n}. My attempt is
m, n = size(M)
@variable(model, y[1:n])
@variable(model, t)
zz = [M[i,:]'*y + t for i=1:m]
z = [max(zz[i], 0.0) for i=1:m]
@constraint(model, sum(z) <= c)
but I got the following error:
MethodError: no method matching isless(::Float64, ::JuMP.GenericAffExpr{Float64,JuMP.Variable})
I tried adding a non-negative variable s and doing the following
m, n = size(M)
@variable(model, y[1:n])
@variable(model, t)
@variable(model, s >= 0.0)
z = [M[i,:]'*y + t for i=1:m]
@constraint(model, z >= s)
@constraint(model, sum(z) <= c)
but wasn’t sure if this is the standard way of adding this type of constraint. For example, is this what Convex.jl does, or where could I check?
This makes no sense to me. yy is a bunch of expressions, and the “constraint” is not really constraining anything. Also data[i] should probably be data[:,i]. In the question you referred to, the OP was trying to minimize the sum of terms each of which is of the form max(expr, 0), so the standard way is to define z and constrain z >= expr and z >= 0, then minimize z instead, which due to the minimization behavior of the optimization algorithm, z will eventually land on either expr or 0, and in the process expr will be pushed as low as possible until it gets to or below 0, then z will not push it down anymore.
1 Like
Thanks, my original question was off… Edited to reflect my issue better
@variable(model, s[1:m] >= 0.0)
@constraint(model, [i=1:m], s[i] >= z[i])
@constraint(model, sum(s[i] for i=1:m) <= c)
Note that under this transformation, there is no guarantee that s[i] will be exactly equal to max(z[i], 0) (may or may not be the case depending on your objective). s[i] can take any value greater than or equal to max(z[i], 0) as long as sum(s) is less than or equal to c. But satisfying the transformed constraints clearly guarantees satisfying your original constraints. That is for every feasible solution (y_f,t_f,s_f) to the transformed constraints, the solution (y_f, t_f) is guaranteed to satisfy your original constraints. And conversely, for every feasible solution (y_f,t_f) to the original constraints, there exists at least 1 feasible solution (y_f,t_f,s_f) to the transformed constraints by setting s_f[i] = max(z[i], 0) for example, so you are not “missing” on any feasible solution to the original constraints by replacing them with the transformed set of constraints.
2 Likes
Thanks – the feasibility argument makes sense, but why did you constrain the sum of s[i] and not z?. Is there a way to doe the max(z[i] + t, 0) constraint precisely? In Convex.jl, I was able to solve the toy problem:
using Convex
using Mosek
m = 10
n = 3
t = Variable(1)
y = Variable(n)
M = randn(m,n)
c = 100
r = randn(n)
problem = minimize(r'*y)
problem.constraints += [t >= 0]
z = max.([M[i,:]'*y + t for i=1:m], 0.0)
problem.constraints += [sum(z) <= c]
solve!(problem, MosekSolver(),verbose=true)
y.value
but don’t entirely know how Convex is treating that max constraint.
The above transformation will do precisely what you want, just ignore s in the final solution, it doesn’t add any semantics to your model. As for Convex.jl, I haven’t read the src but one possibility is that Convex.jl is doing the same transformation under the hood and is hiding away the s details from you, so you only see what you want to see. Or another possibility is that the max expression is processed as a non-smooth function using sub-gradients, I have no idea which one it is using.
1 Like