unbounded problem in linprog but not in fmincon
2 views (last 30 days)
Show older comments
HI,
I am running an optimization problem. It is just a linear problem. Which is why I used linprog to solve it.
However, when I ran the code it returned that the problem was unbounded an no solution could be found.
therafter, I tried solving the same problem with Fmincon. Now I did get the right outcome.
Does anyone know how this works or what could be the cause
2 Comments
John D'Errico
on 8 May 2019
We see nothing of what you did in either case. So we need to take your word for it that you wrote correct code in both cases to solve fundamentally identical problems. And we need to accept that you do know that you did, indeed find the "correct" solution with fmincon.
So, what could be the cause? Without seeing what you did, it would be just a wild guess.
Star Strider
on 8 May 2019
If I remember correctly, the original problem is described in this post: fmincon unidentified variable in objective function (link).
Accepted Answer
John D'Errico
on 8 May 2019
Edited: John D'Errico
on 8 May 2019
This is your problem?
A=[ 1 1 1 0 0 0 0 0 0; -2.5 0 0 1 -1 0 0 0 0;0 -3 0 0 0 1 -1 0 0;0 0 -20 0 0 0 0 1 1;0 0 0 0 0 0 0 1 0];
b=[500;-200;-240;0;6000];
lb=[zeros(1,9)];
ub=[];
F = [150 230 260 238 -170 210 -150 -36 -10];
[x,fval,exitflag] = linprog(F,A,b,[],[],lb,ub)
Problem is unbounded.
x =
[]
fval =
[]
exitflag =
-3
So, is it unbounded? LINPROG seems confidant. But is it? First, does fmincon agree?
x0 = repmat(50,9,1);
[x,fval,exitflag] = fmincon(@(x) dot(F,x),x0,A,b,[],[],lb,ub)
Solver stopped prematurely.
fmincon stopped because it exceeded the function evaluation limit,
options.MaxFunctionEvaluations = 3.000000e+03.
x =
100.21
78.188
300.27
1382.4
9.1121e+10
136.57
7.8729e+10
6000
5.143
fval =
-2.73e+13
exitflag =
0
Um, fmincon did not say the problem is unbounded. But it clearly is! It did not return an exitflag of -3. So what? Is this the correct solution? NO. Fmincon stopped prematurely. It ran out of function evals before it managed to decide the problem is unbounded. Tht does NOT mean fmincon solved the problem, or that it is not unbounded. Look at the final objectiove: -2,73e13. Is that REAL BIG and negative? YES.
F has negative elements in it. So we can make F as small as we wish, by making the corresponding elements of x positive and large.
First, see if we can find a nonnegative solution to the inequality constraint problem. That is, does a feasible solution exist at all? That problem is easy.
xnn = lsqnonneg(A,b)
xnn =
120
80
300
100
0
0
0
6000
0
This is clearly a feasible solution to the inequality constraint array.
A*xnn - b
ans =
0
0
0
0
0
And it has a moderately large negative objective.
F*xnn
ans =
-77800
Now, as long as we can move in a way that make none of these elements negative, but still decrease the objective, we will have an unbounded problem.
So, how can we perturb the feasible solution xnn, in a way that will make the objective function as large negative as we wish? In fact, fmincon told us the answer. The "Solution" that fmincon returns has x(5) and x(7) very large. (I could have done this in other ways, but fmincon makes it easy to see.)
So, try this:
xpert = zeros(9,1);
xpert([5 7]) = 1
xpert =
0
0
0
0
1
0
1
0
0
I will claim that the vector
xnn + k*xpert
satisfies the equality constraint array. Since xnn and xpert are both entirely non-negative vectors, then as long as k is a positive number, then that sum is also always entirely positive. I'll let MATLAB write it out for you:
syms k
xnn + k*xpert
ans =
120
80
300
100
k
0
k
6000
0
[A*(xnn + k*xpert),b]
ans =
[ 500, 500]
[ - k - 200, -200]
[ - k - 240, -240]
[ 0, 0]
[ 6000, 6000]
So, as long as k is a positive number, then xnn + k*xpert is fully positive, AND it always satisfies the inequality constraints. But what is the objective function?
dot(F,xnn + k*xpert)
ans =
- 320*k - 77800
I can make that as close to -inf as I desire, merely by increasing k. The result will always be feasible for any positive k.
THE PROBLEM IS UNBOUNDED. PERIOD. fmincon never said that it had converged to a solution. linprog was entirely correct in its assessment. And you are completely incorrect that fmincon gave the "right" answer. There is no correct answer, except that the problem truly is unbounded.
2 Comments
Matt J
on 8 May 2019
I think I see the discrepancy. F should be as follows
F=[150 230 260 -170 238 -150 210 -36 -10];
bus14 had the coefficients out of order.
More Answers (1)
Matt J
on 8 May 2019
If the problem is as below, then I obtain the same solution essentially from both linprog and fmincon
FUN= @(x) 150*x(1)+230*x(2)+260*x(3)+238*x(5)-170*x(4)+210*x(7)-150*x(6)-36*x(8)-10*x(9);
%FUN= @v 150*v(1)+230*v(2)+260*v(3)+238*v(5)-170*v(4)+210*v(7)-150*v(6)-36*v(8)-10*v(9);
x0=[50,50,50,50,50,50,50,50,50];
A=[ 1 1 1 0 0 0 0 0 0; -2.5 0 0 1 -1 0 0 0 0;0 -3 0 0 0 1 -1 0 0;0 0 -20 0 0 0 0 1 1;0 0 0 0 0 0 0 1 0];
b=[500;-200;-240;0;6000];
lb=[zeros(1,9)];
ub=[];
[sol0,fval0,exitflag0] = fmincon(FUN,x0,A,b,[],[],lb,ub); %Using fmincon
F=[150 230 260 -170 238 -150 210 -36 -10]; %Using linprog
[sol1,fval1,exitflag1] = linprog(F,A,b,[],[],lb,ub);
this produces,
>> fval0,fval1
fval0 =
-1.1860e+05
fval1 =
-1.1860e+05
>> [sol0(:),sol1(:)]
ans =
1.0e+03 *
0.1200 0.1200
0.0800 0.0800
0.3000 0.3000
0.1000 0.1000
0.0000 0
0.0000 0
0.0000 0
6.0000 6.0000
0.0000 0
0 Comments
See Also
Categories
Find more on Get Started with Optimization Toolbox 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!