Optimization with maximum number of "nonzero" x

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!

Answer 1

[Walter Roberson]

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.

Answer 2

[Matt J]

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.

Answer 3

[Matt J]

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,

https://www.mathworks.com/matlabcentral/fileexchange/52795-constrained-minimum-l1-norm-solutions-of-linear-equations

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.

Answer 4

[M Mirrashid]

https://ch.mathworks.com/matlabcentral/fileexchange/112600-transit-search-optimization-algorithm-matlab-codes

[alcoach]

Thank you all! I'll try your suggestion and let you know how it goes