MATLAB Answers

How to set the constraints of L0- norm in linear programming?

25 views (last 30 days)
wei zhang
wei zhang on 19 Aug 2020
Commented: wei zhang on 20 Aug 2020
(sorry, I miss the objective function before. I have edited it well)
I am trying to set the L0-norm constraints, which give a constrain on the element of the variables.
e.g. I have 3 variables, x1 x2 x3. and I have some "normal" constraints, like below.
x1>0;
x1<0.3;
x2>0;
x1<0.4;
x3>0;
x1<0.5;
The object function to get the mininum is
fx = - (x1+x2+x3);
But I have a L0- norm like constrains. That is the maxinum amount of the chosen variable from x1,x2,x3 is 2.
|x1|0 + |x2|0+|x3|0 <=2 (sorry I don't know how to input the corner mark).
So the answer should be [0,0.3,0.4] ,that is, x2 and x3 chosen. How to make this constrains in Matlab? Could I use Mixed-integer linear programming (MILP) to achieve it? Could anyone give me some suggestions on it? That will be very appreciated.

  0 Comments

Sign in to comment.

Accepted Answer

Bruno Luong
Bruno Luong on 20 Aug 2020
Edited: Bruno Luong on 20 Aug 2020
Brute-force method
% Original LP problem
f = -ones(1,3);
A=[-eye(3);
eye(3)];
b = [0 0 0 0.3 0.4 0.5]';
fvalmin = Inf;
for i=1:3
% Add constraint x(i)==0, meaning l0-norm is <= 2
Aeq = zeros(1,3);
Aeq(i) = 1;
beq = 0;
[xi,fvali] = linprog(f,A,b,Aeq,beq);
% Select the solution that returns minimal cost
if fvali < fvalmin
x = xi;
fvalmin = fvali;
end
end
x

  1 Comment

wei zhang
wei zhang on 20 Aug 2020
Thank you for your codes. It is very clearly that you make the brute force with
Aeq(i) = 1;
If the size of the variables (in this case is 3) and the constraints of L0-norm is bigger (in this case is 2), it is complex to set the brute force loop (maybe just for me).
I made an MILP answer, too. This function seems has a built-in loop as brute force, maybe a Branch and Bound method.

Sign in to comment.

More Answers (2)

Bruno Luong
Bruno Luong on 19 Aug 2020
Well the brute force method is to solve 3 LP problems assuming
  • x1 = 0
  • x2 = 0
  • x3 = 0
and see which returns a solution.

  1 Comment

wei zhang
wei zhang on 20 Aug 2020
Sorry I missed the objective function in the problem description at first. I corrected it well. I surveyed the brute force method on the internet. I know some idea of it. But for the 3 LP problem, could you give me a link? Is it like the branch and bound method?

Sign in to comment.


wei zhang
wei zhang on 20 Aug 2020
I found an answer to my own question. I transfer the problem to MILP problem. The idea is from stackExchange.
If I make anything wrong, please point it out.
I add three auxilary integer variables, as x4,x5,x6; with range[0,1]
And three inequality formula
x1<0.3*x4;
x2<0.4*x5;
x3<0.5*x6;
The code is below,
f = -[1;1;1;0;0;0];
intcon = [4,5,6];
A1 = [0,0,0,1,1,1];
b1 = 2;
A2 = zeros(3,6);
A2(1,1)=1;
A2(1,4)=-0.3;
A2(2,2)=1;
A2(2,5)=-0.4;
A2(3,3)=1;
A2(3,6)=-0.5;
b2 = zeros(3,1);
A = [A1;A2];
b = [b1;b2];
lb = zeros(6,1);
ub = [inf;inf;inf;1;1;1];
x0 = [];
Aeq =[];
beq =[];
%%
x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0);
%%
>> x
x =
0
0.4
0.5
0
1
1

  4 Comments

Show 1 older comment
wei zhang
wei zhang on 20 Aug 2020
@Bruno Luong
I think I could do it in the similar way, if the variables don't have 0-lowerbound and positive upperbound.
In general cases , a<x<b, and x could be zero ( for not chosen).
I may add an integer auxiliary variable z . z could be 0 or 1.
Then I have two inequation.
-x+az<0;
x-bz<0;
Then I could do it in the MILP way. Am I right?
Bruno Luong
Bruno Luong on 20 Aug 2020
Agree, but I put "<=" instead of "<". In all optimization it requires close inequalities, never open inequalities.
wei zhang
wei zhang on 20 Aug 2020
Yes, your reminder is right. It should has "=". Thank you.

Sign in to comment.

Products


Release

R2019a

Community Treasure Hunt

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

Start Hunting!