Why does the LINPROG function in the Optimization Toolbox exit saying that the problem is infeasible when there definitely is a feasible solution?

Question

MathWorks Support Team 2013-10-18

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/104255-why-does-the-linprog-function-in-the-optimization-toolbox-exit-saying-that-the-problem-is-infeasible

编辑： MathWorks Support Team 2021-5-12

When the large-scale method is used on a problem with a feasible solution, the following error is generated:

ERROR: Exiting: One or more of the residuals, duality gap, or total relative error has stalled: 
the primal appears to be infeasible (and the dual unbounded). 
(The dual residual < TolFun=1.00e-008.)

The simplex method will solve the problem but is very slow.

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

Answer 1

MathWorks Support Team 2021-5-12

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/104255-why-does-the-linprog-function-in-the-optimization-toolbox-exit-saying-that-the-problem-is-infeasible#answer_113580

编辑：MathWorks Support Team 2021-5-12

This behavior can occur when the matrix 'Aeq' has linearly dependent constraint rows and the LINPROG solvers do not detect these rows which can cause the algorithms to take an excessively long time to converge or fail to converge at all.

Please refer to the following link for details about linearly dependent vectors:

https://en.wikipedia.org/wiki/Linear_independence

As a workaround, you can use the active-set algorithm to obtain the indices of the dependent rows. Then you can remove the dependent rows manually to create new matrices 'rAeq' and 'rbeq', which can be solved by LINPROG. To use the active-set Algorithm, set the 'LargeScale' option to 'off' and 'Simplex' to 'off'(default) using the OPTIMSET function.