Is it possible that, given the same problem, fmincon finds a solution and intlinprog does not?

Question

Giosuè Basso 2023-2-22

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1917150-is-it-possible-that-given-the-same-problem-fmincon-finds-a-solution-and-intlinprog-does-not

编辑： Matt J 2023-2-23

I have a system of inequalities i need to solve and the first step is to understand if a simplified version of this problem, lacking some constraints that involve binary variables, exists. In order to do that i first tried using intlinprog as it was going to be the function to use with the added constraints. No feasible solution is found even after changing the LPPreprocess option to 'none'.

Out of curiosity I tried using fmincon with the exact same matrices and cost function and a feasible solution was found.

Why does this happen? Shouldn't both the functions find a feasible solution when they're fed the same problem data?

4 个评论
显示 2更早的评论隐藏 2更早的评论

Giosuè Basso 2023-2-22

编辑：Torsten 2023-2-22

在 MATLAB Online 中打开

The problem I'm giving to both fmincon and intlinprog is just a system of inequalities, no binary variables involved, those are part of a second step.

Here are the matrices involved in the problem:

A =[-1     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0;
     0    -1     0     0     0     0     0     0     0     0     0     0     0     0     0     0;
     0     0    -1     0     0     0     0     0     0     0     0     0     0     0     0     0;
    -1     0     0    -1     0     0     0     0     0     0     0     0     0     0     0     0;
     0     0     0     0    -1     0     0     0     0     0     0     0     0     0     0     0;
     0    -1     0     0     0    -1     0     0     0     0     0     0     0     0     0     0;
     0     0    -1     0     0     0    -1     0     0     0     0     0     0     0     0     0;
    -1     0     0    -1     0     0     0    -1     0     0     0     0     0     0     0     0;
     0     0     0     0     0     0     0     0    -1     0     0     0     0     0     0     0;
     0     0     0     0    -1     0     0     0     0    -1     0     0     0     0     0     0;
     0    -1     0     0     0    -1     0     0     0     0    -1     0     0     0     0     0;
     0     0     0     0     0     0     0     0    -1     0     0    -1     0     0     0     0;
     0     0     0     0    -1     0     0     0     0    -1     0     0    -1     0     0     0;
     0     0     0     0     0     0     0     0     0     0     0     0     0    -1     0     0;
     1     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0;
     1     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0;
     1     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0;
     0     1     0     0     0     0     0     0     0     0     0     0     0     0     0     0;
     0     1     0     0     0     0     0     0     0     0     0     0     0     0     0     0;
     0     1     0     0     0     0     0     0     0     0     0     0     0     0     0     0;
     0     0     1     0     0     0     0     0     0     0     0     0     0     0     0     0;
     1     0     1     0     0     0     0     0     0     0     0     0     0     0     0     0;
     0     0     0     1     0     0     0     0     0     0     0     0     0     0     0     0;
     1     0     0     1     0     0     0     0     0     0     0     0     0     0     0     0;
     0     0     0     0     1     0     0     0     0     0     0     0     0     0     0     0;
     0     1     0     0     1     0     0     0     0     0     0     0     0     0     0     0;
     0     0     0     0     0     1     0     0     0     0     0     0     0     0     0     0;
     0     1     0     0     0     1     0     0     0     0     0     0     0     0     0     0;
     0     0     1     0     0     0     1     0     0     0     0     0     0     0     0     0;
     1     0     0     1     0     0     0     1     0     0     0     0     0     0     0     0;
     0     0     0     0     0     0     0     0     1     0     0     0     0     0     0     0;
     0     0     0     0     1     0     0     0     1     0     0     0     0     0     0     0;
     0     0     0     0     0     0     0     0     0     1     0     0     0     0     0     0;
     0     0     0     0     1     0     0     0     0     1     0     0     0     0     0     0;
     0     1     0     0     0     1     0     0     0     0     1     0     0     0     0     0;
     0     0     0     0     0     0     0     0     1     0     0     1     0     0     0     0;
     0     0     0     0     1     0     0     0     0     1     0     0     1     0     0     0;
     0     0     0     0     0     0     0     0     0     0     0     0     0     1     0     0;
     0     0     0     1     0     0     0     0     0     0     0     0     0     0     1     0;
     0     0     0     0     0     0     0     0     0     1     0     0     0     0     0     1]
A = 40×16
    -1     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0    -1     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0    -1     0     0     0     0     0     0     0     0     0     0     0     0     0
    -1     0     0    -1     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0    -1     0     0     0     0     0     0     0     0     0     0     0
     0    -1     0     0     0    -1     0     0     0     0     0     0     0     0     0     0
     0     0    -1     0     0     0    -1     0     0     0     0     0     0     0     0     0
    -1     0     0    -1     0     0     0    -1     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0    -1     0     0     0     0     0     0     0
     0     0     0     0    -1     0     0     0     0    -1     0     0     0     0     0     0
B = [0;
     0;
     0;
    -3;
     0;
    -3;
    -3;
     0;
     0;
    -3;
     0;
    -3;
     0;
     0;
     1;
     1;
     4;
     1;
     1;
     4;
     1;
     4;
     1;
     4;
     2;
     4;
     2;
     4;
     4;
     1;
     1;
     4;
     1;
     4;
     2;
     4;
     1;
     1;
     1;
     1]
B = 40×1
     0
     0
     0
    -3
     0
    -3
    -3
     0
     0
    -3

While the objective function is:

f = [0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1];
obj = @(x) f*x;

As x(15) and x(16) are additional variables to be minimised in order to make those constraint just < and not <=.

There are no equality constraints, and the solutions must be all >= 0, so the two functions end up being:

solution1 = fmincon(obj,zeros(size(A,2),1),A,B,[],[],zeros(size(A,2),1));
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  6.201197e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  6.201197e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  6.201197e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  6.201197e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  6.201197e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  6.201197e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  6.201197e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  6.201197e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  6.201197e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.680627e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.680627e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  9.258516e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.680627e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.680627e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.680627e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.680627e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.680627e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.680627e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  4.826966e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  4.826966e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  2.645406e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  4.826966e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  4.826966e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  4.826966e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  4.826966e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  4.826966e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  4.826966e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.335809e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.335809e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  2.645443e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.335809e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.335809e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.335809e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.335809e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.335809e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.335809e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.335809e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  3.999469e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  3.999469e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  2.645445e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  3.999469e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  3.999469e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  3.999469e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  3.999469e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  3.999469e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  3.999469e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.104341e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.104341e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  2.645446e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.104341e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.104341e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.104341e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.104341e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.104341e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.104341e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  3.196854e-20.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  3.196854e-20.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.322724e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  3.196854e-20.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  3.196854e-20.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  3.196854e-20.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  3.196854e-20.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  3.196854e-20.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  3.196854e-20.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  8.677267e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  8.677267e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.322724e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  8.677267e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  8.677267e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  8.677267e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  8.677267e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  8.677267e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  8.677267e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  2.452529e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  2.452529e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.322724e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  2.452529e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  2.452529e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  2.452529e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  2.452529e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  2.452529e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  6.579687e-22.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  6.579687e-22.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  5.290895e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  6.579687e-22.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  6.579687e-22.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  6.579687e-22.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  6.579687e-22.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  6.579687e-22.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.827224e-22.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.827224e-22.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  2.645447e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.827224e-22.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.827224e-22.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.827224e-22.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.827224e-22.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  1.827224e-22.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =  2.645447e-17.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Converged to an infeasible point.

fmincon stopped because the size of the current step is less than
the value of the step size tolerance but constraints are not
satisfied to within the value of the constraint tolerance.


Consider enabling the interior point method feasibility mode.
solution2 = intlinprog(f',[],A,B,[],[],zeros(size(A,2),1));
No feasible solution found.

No integer variables specified. Intlinprog stopped because no point satisfies the constraints.

I'm simply trying to see if A*x <= B has a solution.

I hope I've been exhaustive enough, thanks a lot for helping.

Walter Roberson 2023-2-22

I would check whether the fmincon output is a true solution. fmincon uses tolerances to decide whether to terminate, and sometimes proposed parameters get within tolerance but are not true solutions.

Torsten 2023-2-22

I don't see that fmincon succeeds (see above).

请先登录，再进行评论。

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

Answer 1

Matt J 2023-2-22

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1917150-is-it-possible-that-given-the-same-problem-fmincon-finds-a-solution-and-intlinprog-does-not#answer_1177675

编辑：Matt J 2023-2-23

在 MATLAB Online 中打开

Your constraints are not feasible, as can be seen by looking at inequalities 4,15, and 23.

A=A([4,15,23],:); B=B([4,15,23],:);
[array2table(A), array2table(B)]
ans = 3×17 table
    A1    A2    A3    A4    A5    A6    A7    A8    A9    A10    A11    A12    A13    A14    A15    A16    B 
    __    __    __    __    __    __    __    __    __    ___    ___    ___    ___    ___    ___    ___    __

    -1    0     0     -1    0     0     0     0     0      0      0      0      0      0      0      0     -3
     1    0     0      0    0     0     0     0     0      0      0      0      0      0      0      0      1
     0    0     0      1    0     0     0     0     0      0      0      0      0      0      0      0      1

Equalities 15 and 23 say that x1<=1 and x4<=1, which in turn implies that x1+x4<=2. However, inequality 4 states that x1+x4>=3.

The answer to your question, in this situation, is yes. fmincon can find a solution when the constraint set is empty, but it is an infeasible solution, representing some point fmincon reached in its search for a feasible solution before it gave up. Conversely, intlinprog and linprog will not return an infeasible solution.