Linprog optimisation with slack variable. How do I formulate the matices?

I am trying to do a basic linear fitting optimisation, but am not getting the results that I am expecting. I have generated data for x and y - x=linspace(0,1,50) and y = 4x-1. And need to use a slack variable.

My optimisation problem then becomes

    min(a,b,s) s subject to -s <= a*x(i)+b-y(i) <= s

The code I am using to try and get a = 4 and b= -1 is:

    %    a  b  s
    f = [0 ;0 ;1];
    A1 = [ J ones(N,1)];
    A2 = [-J ones(N,1)];
    A = [A1 ;A2]; 
    b1 = y;
    b2 = -y;
    b  = [b1 ;b2];
    [a b s] = linprog(f,A,b);

J has been defined as [x ones(50,1)]

Can anybody help me please?

Thanks in advance.

Answer 1

[Torsten]

A1 = [x,ones(N,1),-ones(N,1)];
A2 = [-x,-ones(N,1),-ones(N,1)];
A = [A1;A2];
b = [y;-y];
f = [0;0;1];
linprog(f,A,b)

Best wishes

Torsten.

[Manie Conradie]

Thanks Torsten!

How a simple minus sign can cause trouble.

I have run the code and get the message

    Exiting: One or more of the residuals, duality gap, or total relative         error has stalled:
         both the primal and the dual appear to be infeasible.

Do you know what this means?

[Torsten]

It cannot happen that an optimization in the l_inf norm becomes infeasible.

Are you sure that your x and y vectors contain real numbers and are of length N ?

Best wishes

Torsten.

[Manie Conradie]

Managed to solve the problem. Although I cannot say what the problem was.

As you mentioned it is indeed the L-inf norm. But what boggles me, is where is the square of the error calculated in this implementation?

I am also doing one for the L-1 norm, and again I don't see where I should implement the absolute value part of the definition. Or is this the -s<f<s part of it?

Could you perhaps explain this to me please?

Thanks very much.

Manie

[Manie Conradie]

Sorry, mixing up the L-2 norm and the L-inf norm.

Answer 2

[Torsten]

l_1-norm:

The problem can be formulated as

min: sum_i s_i

|a*x(i)+b-y(i)| <= s_i

or equivalently

min: sum_i s_i

-s_i <= a*x(i)+b-y(i) <= s_i

l_infinity norm:

The problem can be formulated as

min: s

|a*x(i)+b-y(i)| <= s

or equivalently

min: s

-s <= a*x(i)+b-y(i) <= s

Best wishes

Torsten.