unbounded problem in linprog but not in fmincon

22 views (last 30 days)
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
Star Strider
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).

Sign in to comment.

Accepted Answer

John D'Errico
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
bus14
bus14 on 9 May 2019
This was indeed my mistake Matt J, Thanks
John, Thank you a lot for your extensive explenation. Made it more clear for me.
I know what the desired outcome of the code should be, as this is a code applied to the stochastic farmers problem from a book. So the optimal answers are in fact known. I should have stated this in the question ofcourse.
Many thanks

Sign in to comment.

More Answers (1)

Matt J
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

Community Treasure Hunt

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

Start Hunting!