Finding the Minimal L1 Norm Solution for Ax=b: A Linear Programming Approach

[umarkhan]

Hi,
Can anyone tell me how to find the minimal L1 norm solution to the problem Ax=b using a linear programming method possibly the simplex search??

Any links where I can find something ??

Khan.

 

[blue2script]

I guess this is what you search for:

http://reference.wolfram.com/mathematica/tutorial/ConstrainedOptimizationLinearProgramming.html

Take a look at the paragraph Application Examples of Linear Programming

Cheers
blue2script

 

[umarkhan]

hi,
Thanks for the link. I tried some thing similar for the system x1 + x2 = 1. I converted to linear programming problem and then used linprog from matlab. The trick is to to put the L1 norm minimization in the for of two inequalities for each variable.

f=[1 1 0 0 ]';
A=[-1 0 -1 0;
-1 0 1 0;
0 -1 0 -1;
0 -1 0 1];



b=[0 0 0 0]';

Aeq=[0 0 1 1];
beq=[1];

[x,fval,exitflag,output,lambda] =linprog(f,A,b,Aeq,beq,[0 0 -10 -10]',[1e10 1e10 10 10 ])