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

exitflag= -2exitflag= -3linprogoptimization

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

Best Answer

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.
Related Question