unbounded problem in linprog but not in fmincon

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

[John D'Errico]

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]

If I remember correctly, the original problem is described in this post: fmincon unidentified variable in objective function (link).

Answer 1

[John D'Errico]

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.

[Matt J]

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.

[bus14]

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

Answer 2

[Matt J]

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