How to set the number of non-zero elements in variable?

Nonconvex
1

How to set the number of non-zero elements in variable lambda in constraint condition ? For example : length(find (lambda>0))=5 (using matlab code)

nvars = 100;
cvx_begin
    variable lambda(1,nvars);     
    minimize (function(lambda))
    subject to
       
        sum(lambda) == 1;
        lambda>=0;
cvx_end

Best Regards,

Hope to get your response soon.

Lingjun (ljk.kong@gmail.com)

2

I mean that I want to find lambda(1,nvars)to make the function has the minimized value. I just want to set the number of nonzero elements in vector lambda(1,nvars). As normal, I can get the lambda(1,nvars) using CVX. But I can’t know exact number of nonzero elements in vector lambda. Can we fix the the number of nonzero elements in vector variable lambda?

Best Regards,

Hope to get your response soon.

Lingjun (ljk.kong@gmail.com)

3

This is not a convex constraint and therefore outside of the scope of CVX. If lambda is integer valued, then (it’s still not convex but) you could treat it as a mixed integer disciplined convex program. However, based on your question it doesn’t sound like this is the case.

4

I mean that I want to find lambda(1,nvars)to make the function has the minimized value. I just want to set the number of nonzero elements in vector lambda(1,nvars). As normal, I can get the lambda(1,nvars) using CVX. But I can’t know exact number of nonzero elements in vector lambda.

5

As Bien correctly states, this is a nonconvex formulation. However, it can be expressed using CVX’s mixed-integer capabilities, assuming you have a CVX Professional license and Gurobi or MOSEK installed:

cvx_begin
    variable lambda(1,nvars);
    variable is_nonzero(1,nvars) binary;
    minimize(function(lambda))
    subject to
        0 <= lambda <= is_nonzero;
        sum(lambda) == 1;
        sum(is_nonzero) == 5;
cvx_end

Technically speaking, this does not constrain the number of non-zero values to be exactly 5; it constrains it to be 5 or fewer. But this is the closest you can get.

Keep in mind that cardinality constraints such as these are combinatorial in nature. While mixed-integer solvers will probably have no difficulty reaching a solution for small values of nvars, the complexity grows exponentially as nvars grows.