Optimization with maximum number of "nonzero" x

6 views (last 30 days)
alcoach
alcoach on 4 Jun 2022
Commented: alcoach on 7 Jun 2022
Hi everyone,
I'm using fmincon to solve an optimization problem with lb and ub and it works properly. What I'm trying to do (without success) is to limit the number of values of the vector X <> 0.
Let's say that the input vecor X used in the function FUN has 100 elements, I'd want to find a solution using only a predetermined number of elements in X (leaving the remaing at zero).
So for example, the best combination of ten elements of X.
Is that possible with fmincon or other function?
Thanks for your help!

Answers (4)

Walter Roberson
Walter Roberson on 4 Jun 2022
You could probably put in a nonlinear equality constraint
nnz(x)-10
but I think the best you could hope for is one combination of non-zeros, and that it would not try many others.
I think to get the optimal over all possibilities that you would have to try all of the possibilities, over 10^13 of them. I don't think that is realistic.

Matt J
Matt J on 4 Jun 2022
Edited: Matt J on 4 Jun 2022
To handle that with a continuous-domain optimizer like fmincon, you must run a separate fmincon optimization for every possible subset S of non-zero x(i) variables, constraining x(i)=0 for . In your example, with 100 variables and N=10 nonzeros, this will mean exploring ~2e13 subsets, which is prohibitive.
Another way to approach it is to introduce additional, binary variables b(i) with the linear constraints,
M=max(abs(lb,ub));
-M(i).*b(i)<=x(i)<=+M(i).*b(i) %(C1)
sum(b)<=N %(C2)
When a particular b(i) is forced to zero by constraint C2, the corresponding x(i) will be forced to zero as well by C1. This assumes all M(i) are finite. For this approach, however, you would need an optimization routine that can incorporate integer variables, for example intlinprog (if your objective is linear) or ga or patternsearch.

Matt J
Matt J on 4 Jun 2022
Another approach is to reformulate problem in the form,
min. norm(x,1)
s.t. objective(x)<=C %and other constraints
This doesn't give you exact control over the number of non-zeros, but it does tend to encourage sparse solutions.
If your objective and other constraints are linear, you can do this with minL1lin,
You can implement it with fmincon as well. Technically, since norm(x,1) is not differentiable, it violates the assumptions of fmincon, but it is piecewise differentiable, so probably won't work too badly.

M Mirrashid
M Mirrashid on 5 Jun 2022
  1 Comment
alcoach
alcoach on 7 Jun 2022
Thank you all! I'll try your suggestion and let you know how it goes

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!