# unbounded problem in linprog but not in fmincon

22 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

Star Strider
on 8 May 2019

### 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.

### 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

### Community Treasure Hunt

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

Start Hunting!