Problem is unbounded with linprong
Show older comments
Answers (3)
You solved it - f can be made as small as you like. That's what "Problem is unbounded" means.
Unbounded means what it sounds like. We can move in SOME direction, making the objective as small as we wish. I.e., as close to minus infinity as you wish to go. Even though you provide inequality constraints, you can still move without constraint in some direction. Can we identify what such a direction might be?
f=[8 4 -2 6 12]
b=[6;8;12;24;40]
A=[6 4 -1 8 -24;-4 8 6 -2 12;30 9 -12 16 -36;16 -3 2 4 6;24 6 3 2 -12]
linprog(f,A,b)
A even has full rank. But that does not mean the mere inequality constraints are sufficient to bound the problem. You have no bound constraints at all.
rank(A)
Can we find a direction, in which the LP is unbounded? Yes. I'll just generate a large set of random vectors, all of which cause a decrease in the objective. (This is a very lazy method.)
X = randn(5,1000);
X = X.*sign(-f*X); % Force them all to point in a direction that will decrease the objective
ind = find(all(A*X<b,1)); % find all such vectors that are feasible
X = mean(X(:,ind),2) % and then take the mean
A*(1000*X) <= b
format long g
f*[X,1000*X,1e6*X]
So I can go as far out in that direction as I wish, making the objective as close to -inf as I wish.
Again, this is an extremely lazy method. No thought was required at all.
Walter Roberson
on 16 Oct 2022
0 votes
The constraints are used as A*x <= b. The boundary condition would be A*x = b which you could solve with A\b.
But if A*x <= b then can we solve the boundary A*x = b-[0;100;0;0;0]? for example if A(2,:)*x = -92 then that would satisfy A(2,:)*x <= 8 right? Can we get a consistent solution with the modified boundary conditions? If course we can, we just use A\modified b to get the modified x. Then we ask, f*unmodified < f*modified? That is, are the original boundaries the ones that give minimal output? No, the modified boundary gives a more minimal output. And since the system is linear, we can reduce the output arbitrarily.
3 Comments
Walter Roberson
on 16 Oct 2022
syms c [5 1]
out = f*(A\(b-c))
You will get
(11806*c1)/27307 - (3295*c2)/3901 - (16032*c3)/27307 - (21072*c4)/27307 + (18190*c5)/27307 + 12028/3901
which tells us that by making c2 or c3 or c4 arbitrary positive values the outcome can be reduced arbitrarily. Making them positive corresponds to reducing the b value in the corresponding position, making it in some sense more difficult to satisfy... but in so doing the outcome decreases so the optimization is unbounded.
Walter Roberson
on 16 Oct 2022
Now if you require nonnegative x there might be a solution.
Walter Roberson
on 16 Oct 2022
Unfortunately the details of how it determines the problem is unbounded are hidden in toolbox/optim/+optim/+algorithm/LinprogDualSimplex.p
Categories
Find more on Linear Least Squares in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
