How to impose that the solution takes zeros values in some elements using fmincon?

Hello !

My initial value is of size n and my objective function is :

objective=@(f) 0

Let us assume that :

m<=n.

I would like to impose that the solution f takes m non null values and the rest are 0.

I tried out the following non-linear constraint :

size(find(f~=0),1)-m 

But I get the following message :

Converged to an infeasible point.

fmincon stopped because the size of the current step is less than
the default value of the step size tolerance but constraints are not
satisfied to within the default value of the constraint tolerance.

<stopping criteria details>

[Matt J]

Presumably there are other constraints? Otherwise, a trivial solution to your problem is,

f=[ones(1,m), zeros(1,n-m)]

[wiem abd]

Yes I am trying to add constraints gradually. Actually, I have the following constraint :

sum(f)- BW

where BW= 100*1e+6

But I think it is easy to solve it. I don't know why it converges to an infeasible point.

[Matt J]

fmincon is the wrong tool for what you are trying to do. We need to see the full problem to recommend something better. That means all the constraints, including whether some of the unknowns are integers.

[wiem abd]

The unknowns are real values f. Please see below my non-linear constraints

epsilon=1e-6;
S =   1.0e+10 *[   0.0155
    0.1318
    0.0002
    0.0037
    0.0657
    0.1125
    0.0245
    1.3337];
n=6;
m=2;
C=10*1e+6;
function [c,ceq] = mycon_Taylor(f,S,n,m,BW,epsilon,C)
%UNTITLED5 Summary of this function goes here
%   Detailed explanation goes here

% Compute nonlinear inequalities at x.

c=[sum(f)- BW;
(1/epsilon)-sum(f(1:m)'*log(1+(S(n+1:n+m)./f(1:m))));
(sum(f(1:m)'*log(1+(S(n+1:n+m)./f(1:m))))-C);
(size(find(f~=0),1)-m)];
ceq=[];

end

[wiem abd]

Actually the third constraint contains an other part

(sum(f(1:m)'*log((SNR(n+1:n+m)+f(1:m))))+sum((b-f).*log(SNR(1:n)+(b-f)))-C

where b is known and the size of b is n.

That's why I am imposing that m of n elements of f are 0.

Indeed, the problem is substract m elements of b

Answer 1

[Matt J]

It looks like you simply need f(1:m) >=0 in order for the log expressions to work. Why not just put lower bounds on them lb(1:m)=0?

[wiem abd]

Yes I have defined lb(1:n)=0.

But I need m elements of n to be exactly equal to 0.

[Matt J]

Yes I have defined lb(1:n)=0.

No, I wrote lb(1:m)=0, because if you don't impose the constraint that f(1:m)>=0 then the expression you posted,

log(1+(S(n+1:n+m)./f(1:m))

will have a problematic division ./f(1:m) in it.

As for f(m+1:n), if you already know those are zero, I don't see why you are including them as unknowns in your problem. Just write your objective and constraint function with those values assumed to be zero already. But if you insist on treating them as unknowns, you can tell fmincon to force them to zero by setting both the upper and lower bounds appropriately:

lb(m+1:n)=0;
ub(m+1:n)=0;

[wiem abd]

Actually the third constraint contains an other part

(sum(f(1:m)'*log((SNR(n+1:n+m)+f(1:m))))+sum((b-f).*log(SNR(1:n)+(b-f)))-C

where b is known and the size of b is n.

That's why I am imposing that m of n elements of f are 0.

Indeed, the problem is to substract m elements of b. Therefore, the size of f is n also.

[Matt J]

No, that's still no reason to be treating knowns as unknowns. You could write your constraint function in terms of an m-variable vector x as follows,

  function [c,ceq] = mycon_Taylor(x,S,n,m,BW,epsilon,C)  

   bmf=b;
   bmf(1:m)=bmf(1:m)-x;
  
   c = (  sum(x'*log((SNR(n+1:n+m)+x )))+sum( bmf.*log(SNR(1:n)+bmf) )-C;

   ceq=[];
  
  end

[wiem abd]

I want the algorithm to choose from which b(i) to substract f(i). It should not necessarily be the first m values that maximize my objective function.

[Matt J]

Here are the constraints as you originally showed them to us.

c=[sum(f)- BW;
(1/epsilon)-sum(f(1:m)'*log(1+(S(n+1:n+m)./f(1:m))));
(sum(f(1:m)'*log(1+(S(n+1:n+m)./f(1:m))))-C);
(size(find(f~=0),1)-m)];

There is no way the second constraint can be satisfied if any of the first m values of f(i) are zero, because then you will have a division by 0. This then implies, by the 4th constraint, that all f(i) must be zero for i>m.

[wiem abd]

Thank you very much !

I got it :)

Answer 2

[John D'Errico]

To me, it means the constraints written don't correctly encapsulate the stated goals. One of those stated goals is there must be a set of exactly m non-zero elements, but they lie in some unknown order, and fmincon is being asked to find those non-zero placements, as well as the value of the non-zeros too.

But if that is true, then fmincon cannot be used to find that result, since this makes the objective function a seemingly non-differentiable one. As well the constraint

(size(find(f~=0),1)-m)

is non-differentiable, but worse, is a discontinuous function of the parameter space. That is a serious problem for FMINCON.

Another tool (probably GA from the global optimization toolbox, but NOT FMINCON) is needed for this problem.

I would strongly suggest the problem should really be written in a different form, perhaps something like this:

There are 2*m unknowns. The first m of them are the values of the unknown elements, the non-zeros, written in sequence from the first to the last non-zero.

Unknowns m+1:2*m are distinct integers, from the set [1:n]. They must be distinct, and increasing in order. These are easy constraints to apply, in fact, they can be written as linear constraints, since we need only

f(I) <= f(i+1) + 1

for all i >= m+1 and i <= 2*m-1. Then, with bounds on those elements forcing them to lie in the interval [1,n] and with integer constraints forcing elements (m+1:2*m) to be integer, we will get the necessary set of integer indices.

Again, GA should have no problem in solving the indicated class of problem.

Given the set of 2*m unknowns and those constraints, now your objective function becomes simple. Construct the full vector of length n as

fvals = f(1:m);
flocs = f(m+1:2*m)
fn = zeros(1,n);
fn(flocs) = fvals;

Finally, you can now evaluate the objective function as a function of the vector fn. As you can see, it has exctly n elements, at the locations indicated.

You no longer need a constraint of the form

(size(find(f~=0),1)-m)

because that is trivially and implicitly true. We enforce that constraint by the way we have constructed the problem. The other constraints, for example, sum(f) - BW, now becomes sum(fvals) - BW.

And, again you will need to impose the appropriate bound and inequality constraints on the integer elements of f.

All of this is now admissable as a problem statement, but ONLY if you use GA.

Do you see that what is needed is to look at the problem in the correct way? It is NOT that you need to find a vector of length n. What you need to find are m values, AND a set of m integer indices. Given those two sets of numbers (with the constraints as I have indicated) they completely define the vector of length n that you claim to need.