L0 norm in JuMp?


I would like to minimize the L0-norm of a vector (i.e. the number of non-zero element) using JuMp, but I really struggle to achieve it. I tried to define a function to represent the L0-norm:

count_nonzero(x) = sum(x .!= 0)

Then I created an expression:

@expression(model, expr, count_nonzero(v))

And finally, I tried to formulate my objective:

@NLobjective(model, Min, expr)

But I get an error:

The solver does not support nonlinear problems (i.e., NLobjective and NLconstraint).

Am I missing something? I’m really new to optimization (and to Julia as well) and I am a bit lost…

Thank you for your help!
(I am using Gurobi as an optimizer, which is supposed to support nonlinear problems)

Realize that this is a very nasty discontinuous function to optimize; it is called a “cardinality optimization problem”, and is generally NP hard (to solve exactly).

A common approach is L1 relaxation: replace the L0 norm with an L1 norm, which is often a good approximation and makes the problem much easier to solve. There are lots of references on this subject, often under the topic of compressed sensing.

Thank you so much! It is clearer now, I will try to use L1 instead.

I’m really new to optimization (and to Julia as well)

Hi! Yes, getting used to JuMP takes a bit of time, especially if you don’t have a background in mathematical programming.

As a general rule (with some exceptions), we don’t support arbitrary Julia functions like:

count_nonzero(x) = sum(x .!= 0)
@expression(model, expr, count_nonzero(v))

Instead, if you’re using a solver like Gurobi, you must formulate your problem as a mixed-integer linear or quadratic program using the syntax and functions provided by JuMP.

If you’re using Gurobi, and you want to use the L1-norm, then write:

model = Model()
@variable(model, x[1:4])
@variable(model, t)
@constraint(model, [t; x] in MOI.NormOneCone(length(x) + 1))
@objective(model, Min, t)

Thank you so much! This helped me a lot, I have something that works now, thank you!! :grin:

1 Like