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.
And it has a moderately large negative objective.
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.
Best Answer