L0 norm in JuMp?

Specific Domains Optimization (Mathematical)
1

Hello,

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)

2

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.

3

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

4

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)
3 Likes
5

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

1 Like