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.
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.


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);
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;

  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
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);
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 =


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.
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.




Community Treasure Hunt

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

Start Hunting!