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

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

Answer 1

[Bruno Luong]

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

[wei zhang]

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.

Answer 2

[Bruno Luong]

Well the brute force method is to solve 3 LP problems assuming

• x1 = 0
• x2 = 0
• x3 = 0

and see which returns a solution.

[wei zhang]

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?

Answer 3

[wei zhang]

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

[Bruno Luong]

This method is allright because you have 0-lowerbound and positive upperbound for all x1, x2, x3.

[wei zhang]

@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]

Agree, but I put "<=" instead of "<". In all optimization it requires close inequalities, never open inequalities.

[wei zhang]

Yes, your reminder is right. It should has "=". Thank you.