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

14 次查看（过去 30 天）
wei zhang
wei zhang 2020-8-19
评论： wei zhang 2020-8-20
(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.

请先登录，再回答此问题。

采纳的回答

Bruno Luong
Bruno Luong 2020-8-20
编辑：Bruno Luong 2020-8-20
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 个评论
wei zhang
wei zhang 2020-8-20
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.

请先登录，再进行评论。

更多回答（2 个）

Bruno Luong
Bruno Luong 2020-8-19
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 个评论
wei zhang
wei zhang 2020-8-20
编辑：wei zhang 2020-8-20
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?

请先登录，再进行评论。

wei zhang
wei zhang 2020-8-20
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 个评论
显示 2更早的评论
Bruno Luong
Bruno Luong 2020-8-20
Agree, but I put "<=" instead of "<". In all optimization it requires close inequalities, never open inequalities.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Linear Programming and Mixed-Integer Linear Programming 的更多信息

标签

产品


版本

R2019a

Community Treasure Hunt

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

Start Hunting!

Translated by