Solve constrained linear least-squares problem such that A*x<=b

Hello everyone, could you please have a look at the following issue I am having?

I am trying to use lsqlin to calculate constrained x such that A*x<=b, where every A*x has got its own b. With some help I was able to reproduce following function, which does almost what I need:

x = lsqlin(C,d,[-C;C],[-d;0*d+bIsNumber],[],[],[],[],[],opts)

where bIsNumber is a number which is used for calculating every A*x<=b. But how would one alter the function above so that every A*x has got its own (different) b? I tried the following:

x = lsqlin(C,d,[-C;C],[-d;0*d+bIsVector],[],[],[],[],[],opts)

where bIsVector is a vector. But this function is not working.

What am I doing wrong please?

Any help is greatly appreciated

Best regards, LZ

Answer 1

[Sargondjani]

i think you should put up the question in the newsgroup as well. hopefully some linear programming expert will respond...

there is hope, because i think your program is relatively easy... just linear equations! it's just that i dont know much about them

good luck!!

[Zdenek]

Many thanks for your help Sargondjani!!. I have made another question about the linear programming. Hopefully some expert will find it. Thank you, Mr. Teacher :) Best regards and have a nice time. zdenek

Answer 2

[Sargondjani]

i think you misunderstood the format

if A*x<=b looks like:

-x1 + 0*x2 <= b1 0*x1 + x2 <= b2

Then you have to insert it as: A=[-1,0 ; 0,1]; b=[b1;b2];

x = lsqlin([],[],A,b,[],[],[],[],[],opts)

if its not working, pls provide error message

[Zdenek]

Hello Sargondjani, thank you for your time. I am very new to Matlab and not very good at advanced math and maybe have not expressed what I am trying to do correctly. So I will try to explain it on an example.

When we have this (5x4)Matrix C:

2 4 1 3

3 5 2 2

6 6 1 1

0 7 3 7

2 8 4 10

and this (5x1) vector d made of numbers d1.....d5:

25

42

33

78

56

then, I need to find such x that C*x≥d and also, at the same time, every result of C*x should be smaller than another number. So every result of C*x should be in the range of 2 numbers (bottom and top). So far I have this code:

x = lsqlin(C,d,[-C;C],[-d;0*d+bIsNumber],[],[],[],[],[],opts)

where bottom works well - every C*x has got its own bottom number taken from the vector d, but the top number bIsNumber is only one and so is shared by all C*x:

vector d bIsNumber

25 <= C*x1 < 200

42 <= C*x2 < 200

33 <= C*x3 < 200

78 <= C*x4 < 200

56 <= C*x5 < 200

...but what I would like to get should be like this:

vector d bIsVector

25 <= C*x1 < 30

42 <= C*x2 < 50

33 <= C*x3 < 40

78 <= C*x4 < 200

56 <= C*x5 < 180

Can this be solved by lsqlin or any other function in Matlab? If yes, how would you do it please?

Thank you for your patience

Best regards

LZ

Answer 3

[Sargondjani]

you would have to rewrite all the equations as A*x<=b.

 i will show you as if you only had x1 and x2:
25<=C*x1<30   => -C*x1<=-25 & C*x1<=30;
42<=C*x2<50   => -C*x2<=-42 & C*x2<=50;

so A and b are: A=[-C 0; C 0;... % for x1 0 -C; 0 C]; % for x2

b=[-25;30;-42;50];

as for the strict inequality: if that constraint is binding, and you really want strict it, then you might want to use 50-eps in stead of just 50 (eps is smallest number that matlab can handle, so 50-eps is the closest to 50 matlab goes)

I hope you understand...

[Zdenek]

Hello, thank you for your explanation. I hope I understand most of it, but there is one thing I don't.

IF

25<=C*x1<30 => -C*x1<=-25 & C*x1<=30; = -C 0; C 0

then why

42<=C*x2<50 => -C*x2<=-42 & C*x2<=50; = 0 -C; 0 C

when the two statements are identical (except numbers}

so what would be the x3?

33<=C*x3<40 => -C*x3<=-33 & C*x3<=40; = ?? same as x1 or x2 or different?

Thank you very much for your help

LZ

[Sargondjani]

yes, like that... did you try it?? im not sure what you understand, and what you don't understand

do you get that the two inequalities are equivalent to the one which says 33<=C*x3<=40???

Answer 4

[Sargondjani]

hmmm, it doesnt get me 'enters' so format is screwed:

A=[-C, 0; C, 0; 0, -C; 0, C];

[Zdenek]

Hello, I tried this code:

C = 2 4 1 3

3 5 2 2

d = 25

42

lsqlin(C,d,[-C,0;C,0;0,-C;0,C],[-25;30;-42;50],[],[],[],[],[],opts)

and it gives me this error:

Error using horzcat

CAT arguments dimensions are not consistent.

Have you also received this error?

Thank you

[Sargondjani]

I think I understand where things go wrong!! I though C was a number, but i see now that it is a matrix... (i dont use lsqlin normally)

But then your constraints dont make sense, it think. Because your C is a matrix, so C*x is also a matrix... That can not be smaller than a number

So what really are your constraints?

[Zdenek]

Hello, I try to be more detailed. I am very sorry for confusing you. For clarity I will repeat inputs.

We have this m*n(5x4)Matrix C:

2 4 1 3

3 5 2 2

6 6 1 1

0 7 3 7

2 8 4 10

and this (5x1) vector d made of numbers d1...d5:

25

42

33

78

56

then, presumably with LSQLIN I need to find such x (x1,x2,x3,x4,x5) that:

SUM of Cm1n1*x1 + Cm2n1*x2 + Cm3n1*x3 + Cm4n1*x4 + Cm5n1*x5 ≥ d1

SUM of Cm1n2*x1 + Cm2n2*x2 + Cm3n2*x3 + Cm4n2*x4 + Cm5n2*x5 ≥ d2

SUM of Cm1n3*x1 + Cm2n3*x2 + Cm3n3*x3 + Cm4n3*x4 + Cm5n3*x5 ≥ d3

SUM of Cm1n4*x1 + Cm2n4*x2 + Cm3n4*x3 + Cm4n4*x4 + Cm5n4*x5 ≥ d4

SUM of Cm1n5*x1 + Cm2n5*x2 + Cm3n5*x3 + Cm4n5*x4 + Cm5n5*x5 ≥ d5

these d1,d2,d3,d4,d5 is what I called bottom (constrain? boundary?) numbers.

At the same time I would like to set also top (constrain? boundary?)numbers. like this:

(5x1) vector top made of numbers top1...top5:

30

50

40

200

180

SUM of Cm1n1*x1 + Cm2n1*x2 + Cm3n1*x3 + Cm4n1*x4 + Cm5n1*x5 <= top1

SUM of Cm1n2*x1 + Cm2n2*x2 + Cm3n2*x3 + Cm4n2*x4 + Cm5n2*x5 <= top2

SUM of Cm1n3*x1 + Cm2n3*x2 + Cm3n3*x3 + Cm4n3*x4 + Cm5n3*x5 <= top3

SUM of Cm1n4*x1 + Cm2n4*x2 + Cm3n4*x3 + Cm4n4*x4 + Cm5n4*x5 <= top4

SUM of Cm1n5*x1 + Cm2n5*x2 + Cm3n5*x3 + Cm4n5*x4 + Cm5n5*x5 <= top5

Again, I am sorry for confusing you. Many thanks.Zdenek

Answer 5

[Sargondjani]

o my god, i also didnt read carefull enough. i assumed you wanted to use lsqlin what it is supposed to do: find the best fit for a system of linear equation. but now i understand you just want to find the bounderiers in which the x-values can be, such that the system still solves... lsqlin is not well suited for that, i suppose, because your problem has infinitely many solutions...

and im so sorry, but im not familiar with this type of problem, so you should get some advice from someone who is more familiar with linear programming.

i suppose you can solve the two systems (lower and upper bounderaries) with gaussian elemination and see what the constraints are based on those results. and there is probably a way to solve this with the symbolic solver. i recommend you look in the documentation for that solver first (maybe search symbolic solver linear equations/programming)

good luck man!!

[Zdenek]

Luck is needed a lot :) Someone advised me to use lsqlin and it made a sense to me to find a best fit in given boundaries. I will try to find something about those methods you suggest. It is a shame you cannot help with them as I need someone who is very, very patient, like you :) Aren't you a teacher?

Many many thanks!!

Have a nice time :)

z

[Zdenek]

Well, I am back. Do you think this could be my problem?

http://www.mathworks.com/matlabcentral/answers/34621-least-squares-linear-regression-when-squares-have-to-do-with-elasticity

Answer 6

[Sargondjani]

yes lsqlin gives you the best fit within boundaries, but you are not fitting. you are looking for all possible solutions that satisfy your inequalities (which lsqlin can not do)

anyway, i have looked around abit and matlab can do gaussian elimination for you (at least numerically). gaussian elimination reduces your system of equations to something simpler. check out the function "rref" http://www.mathworks.nl/help/techdoc/ref/rref.html

so try running this for both your systems (one with the larger than and one for the smaller than system). it is possible that this will actually give you the solution...

ps. yes i was a teacher, haha, and i want to start teaching again :-)

[Zdenek]

I was thinking and re-reading our few last posts and I am not quite sure if we understand each other :)

I don't want to find boundaries in which the x-values can be. Actually, I know them. The lower boundary is vector "d" and the upper boundary is vector "top" and what is unknown is x-values, which I am trying to calculate. I had a look at the rref and it does not return x-values.

And also I don't need to know all possible solutions of x-values, I just need the one solution which fits best between vector "d" and "top".

Answer 7

[Sargondjani]

i think i understand your problem. you wrote earlier "So every result of C*x should be in the range of 2 numbers (bottom and top)."

this lsqlin can not do. or at least not 1 one go. what you could do is run lsqlin for the 'lower constraint' and then separately for the 'higher constraint'. this will give you the x values that best match those constraints. but i seriously doubt if there is only one best for either set solution. if any x_i can be in a range of values, i think lsqlin will have a problem solving it.

i would still use rref myself. the rref actually does return x values. do you know what gaussian elimination is? otherwise read about it... if your 2 systems of equations has a solution, or a range of solutions you can surely find it with gaussian elemination

in the example in the documentation on rref, the solutions are: x1=1, x2=3,x3=-3,x4=indeterminate (can take any value), thats how you have to 'read' the reduced echelon form of the matrix...

just try it, ok?

if not, can you post your C matrix, and your vectors with lower bounds and higher bounds nicely? as you put them in matlab with the '[ ]' etc. then i can try

[Zdenek]

Hello Sargondjani. So I have read about gaussian elimination to understand what it does. And I think I got it. The rref returns perfect fit for the "d" or "top" vectors, but some x-values are smaller than 0 and I need all of them to be > 0. That is the thing I have completely forgotten to mention. So, do you know please, what can I do now to get all of these x-values above 0? Again many thanks.z