linprog error message: the dual appears to be infeasible (and the primal unbounded).

4 次查看（过去 30 天）
Mehdi
Mehdi 2015-6-30
评论： Mehdi 2015-7-3
Hi I am trying to solve a linear optimization problem using linprog but I get the following errors most of the times (exitflag= -3 or -2).
*Exiting: One or more of the residuals, duality gap, or total relative error has stalled
*Exiting: One or more of the residuals, duality gap, or total relative error has grown 100000 times greater than its minimum value so far
I think the the problem is that some of my constraints are very small numbers compared to others. For example, A and b matrices look something like the following.
A = [1 1 0 0; 0 0 .5 1; 0 1e-8 0 1e-9]
b = [1 0 1e-12]
Moreover, when I get this error, some variables in the output of the optimization problem are negative, while I have a constraint that the variables must be non-negative.
Any idea to solve this issue would be appreciated.
Thanks
  1 个评论
Mehdi
Mehdi 2015-6-30
编辑：Mehdi 2015-6-30
the elements of A and b I wrote are not for a real example. I just wanted to show the scales of the numbers.
The followings are an example that I got exitflag = -2.
A =[
0.33 -1 0 0
0.5 -1 0 0
1 -1 0 0
-1 0 0 0
1 0 0 0
0 0 1 -1
0 0 -1 0
0 0 1 0
-5.22e-07 0 -3.69e-07 0 ]
b' = [ 0 2.46e-07 1.76e-05 0 0.1 0 0 0.1 -1e-11]
c' = [0 1 0 1]

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Matt J
Matt J 2015-6-30
编辑：Matt J 2015-6-30
It might be a good idea to give us the complete example so that we can run it ourselves. One thing I notice, however, is that your inequality constraints are degenerate. In particular, the second inequality
0.5*x(3)+x(4)<=0
together with the the non-negativity constraint implies that the only feasible x are those in the subspace where x(3)=x(4)=0. However, I'm pretty sure linprog requires that the inequality constraints specify a region with positive volume in R^4. Otherwise, the problem is unstable. Small perturbations of the data can render the problem infeasible, as for example when you replace the second constraint with
0.5*x(3)+x(4)<= -1e-20
If you know in advance that x(3)=x(4)=0 in advance, just remove them from the problem.
  4 个评论
显示 2更早的评论
Matt J
Matt J 2015-7-1
By multiplying 'b' by a big nubmer...The exit flag is not 1 but the result is correct.
When I implement my recommendations above, I get an exitflag of 1,
A =[
0.33 -1 0 0
0.5 -1 0 0
1 -1 0 0
0 0 1 -1
-5.22e-07 0 -3.69e-07 0];
b = [ 0 2.46e-07 1.76e-05 0 -1e-11]';
c = [0 1 0 1]';
lb=[0, -inf,0,-inf];
ub=[0.1,inf,0.1,inf];
A(end,:)=A(end,:)*1e7; b(end)=b(end)*1e7;
options = optimoptions('linprog','Algorithm','simplex','TolFun',1e-12);
[output, value, exitflag]=linprog(c,A,b,[],[],lb,ub,[],options)
Optimization terminated.
output =
1.0e-04 *
0.1916
0.0933
0
0
value =
9.3325e-06
exitflag =
1
Mehdi
Mehdi 2015-7-3
Thanks a lot Matt. This solves the exitflag issue for most of the cases but for some few cases the exitflag is still -2 and the result is not correct (the output for the second variable as well as the final value is 0).
This case, for instance:
A = [ 0.5 -1
1 -1
-0.0010438 0];
b = [0 1.3413e-05 -1e-11]';
c = [0 1]';
lb=[0, 0];
ub=[0.1, 0.1];
A(end,:)=A(end,:)*1e7; b(end)=b(end)*1e7;
options = optimoptions('linprog','Algorithm','simplex','TolFun',1e-12);
[output, value, exitflag]=linprog(c,A,b,[],[],lb,ub,[],options)
output =
9.5807e-09
0
value =
0
exitflag =
-2
I solved this problem with a different tool and I write it here which might be helpful for thise who have similar problem.
I used the CVX in MATLAB and set the cvx_precision to high. Although it is slower than linprog, it finds the exact result for this problem.
for the same input as above:
n = 2;
cvx_begin quiet
cvx_precision high
variable x(n)
minimize(c'*x)
subject to
A*x <= b;
0 <= x <= .1;
cvx_end
x
cvx_optval
x =
9.5807e-09
4.7903e-09
cvx_optval =
4.7903e-09

请先登录，再进行评论。

更多回答（1 个）

Alan Weiss
Alan Weiss 2015-6-30
I cannot reproduce your result. When I entered the following, I got an answer:
A =[
0.5 -1 0 0 0 0
1 -1 0 0 0 0
-1 0 0 0 0 0
1 0 0 0 0 0
0 0 1 -1 0 0
0 0 -1 0 0 0
0 0 1 0 0 0
0 0 0 0 1 -1
0 0 0 0 -1 0
0 0 0 0 1 0
-1.04e-07 0 -7.03e-08 0 -8.17e-08 0
];
b = [ 0 7.94e-06 0 0.1 0 0 0.1 0 0 0.1 -1e-11]';
x = linprog(zeros(6,1),A,b)
Optimization terminated.
x =
0.0945
86.2581
0.0856
75.3455
0.0856
75.3455
This solution indeed satisfies the constraints:
A*x-b
ans =
-86.2108
-86.1636
-0.0945
-0.0055
-75.2599
-0.0856
-0.0144
-75.2599
-0.0856
-0.0144
-0.0000
Alan Weiss
MATLAB mathematical toolbox documentation
  9 个评论
显示 7更早的评论
Torsten
Torsten 2015-7-2
If you multiply b by a factor of 1e10, you will also have to multiply A with this big number to get an equivalent problem to the one you started with.
Best wishes
Torsten.
Matt J
Matt J 2015-7-2
In addition to what Torsten said, scaling the entire A,b data will not fix the original problem because the relative magnitudes of the last row to the other rows remains the same.
That is why I proposed scaling the final rows only, as in my Comment here,
http://www.mathworks.com/matlabcentral/answers/225887#comment_295767

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Solver Outputs and Iterative Display 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by