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

9 次查看（过去 30 天）
Zdenek
Zdenek 2012-4-7
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

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

采纳的回答

Sargondjani
Sargondjani 2012-4-9
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!!
  1 个评论
Zdenek
Zdenek 2012-4-9
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

请先登录，再进行评论。

更多回答（6 个）

Sargondjani
Sargondjani 2012-4-7
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
  1 个评论
Zdenek
Zdenek 2012-4-8
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

请先登录，再进行评论。

Sargondjani
Sargondjani 2012-4-8
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...
  2 个评论
Zdenek
Zdenek 2012-4-8
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
Sargondjani 2012-4-8
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???

请先登录，再进行评论。

Sargondjani
Sargondjani 2012-4-8
hmmm, it doesnt get me 'enters' so format is screwed:
A=[-C, 0; C, 0; 0, -C; 0, C];
  3 个评论
显示 1更早的评论
Sargondjani
Sargondjani 2012-4-8
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
Zdenek 2012-4-8
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

请先登录，再进行评论。

Sargondjani
Sargondjani 2012-4-8
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!!
  2 个评论
Zdenek
Zdenek 2012-4-8
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
Zdenek 2012-4-8
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

请先登录，再进行评论。

Sargondjani
Sargondjani 2012-4-8
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 :-)
  1 个评论
Zdenek
Zdenek 2012-4-8
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".

请先登录，再进行评论。

Sargondjani
Sargondjani 2012-4-8
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
  1 个评论
Zdenek
Zdenek 2012-4-9
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

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Linear Least Squares 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by