# Different results for different LP Methods

I am trying to utilize the Farkas dual as a certificate of primal infeasibility. The goal is to solve the problem

$$\min_{\textbf{y}} \textbf x\cdot \textbf b \text{ subject to } \\ \textbf 1 \geq \textbf x^T \cdot \textbf M \geq \textbf0$$

Where I have that $$\textbf M$$ is a (24,16) real matrix and $$\textbf b$$ is a 24-dimensional vector. The explicit form is below

M = {{1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0}, {0, 1, 0, 0, 0,
1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0}, {0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
1, 0, 0, 0, 1, 0}, {0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
1}, {1, 1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0,
0, 1, 1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0,
1, 1, -1, -1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, -1, -1}, {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,
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}, {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, 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, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0}, {0,
0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,
0, 0, 0, 1}, {1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, {0,
1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0,
0, 0, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0}}

b = {1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
0, 1}

y.b

y1 + y11 + y13 + y16 + y18 + y2 + y20 + y22 + y23 + y3 + y4 + y9


In order to do that I have defined a vector with 24 entries $$y=\{y_1,y_2,\dots,y_{24}\}$$ and auxiliary vectors $$\text{one(zero)}=\{1(0),1(0),\dots,1(0)\}$$. I am trying to use the NMinimize function

NMinimize[y.b, {y.M <= one, y.M >= zero}, y]


But the result says to me that the problem is unbounded. I have also used GLPSOL for the same problem and it answers that the LP problem is unbounded. But what happens is that if I insert the method in the NMinimize function it gives me a result, and if I insert accuracy it gives me an improved result:

NMinimize[y.b, {y.M <= one, y.M >= zero}, y, Method -> "NelderMead"]

{-5.40053, {y1 -> 0.0922053, y2 -> -0.296647, y3 -> -0.818738,
y4 -> 0.609723, y5 -> 1.29137, y6 -> 0.421854, y7 -> 0.870649,
y8 -> -0.105026, y9 -> -1.46683, y10 -> 2.21323, y11 -> 1.20653,
y12 -> 1.23317, y13 -> -1.98561, y14 -> 1.42415, y15 -> 1.33618,
y16 -> 1.04947, y17 -> 1.99946, y18 -> -1.31915, y19 -> 0.114449,
y20 -> -1.22909, y21 -> 0.717296, y22 -> -2.03368, y23 -> 0.791289,
y24 -> -0.165919}}

NMinimize[y.b, {y.M <= one, y.M >= zero}, y, Method -> "NelderMead",
AccuracyGoal -> 20, PrecisionGoal -> 20, WorkingPrecision -> 10]

{-4.743660875, {y1 -> 0.4550257342, y2 -> -0.2450676253,
y3 -> -1.227866662, y4 -> 1.324807345, y5 -> 0.7006766145,
y6 -> 0.4377141941, y7 -> 0.09784371800, y8 -> -0.1520031228,
y9 -> -1.008643621, y10 -> 2.349987553, y11 -> 0.5532254587,
y12 -> 0.3828493780, y13 -> -1.704379657, y14 -> 1.484400130,
y15 -> 1.578911879, y16 -> 0.6246930465, y17 -> 1.468869524,
y18 -> -1.346866435, y19 -> 0.5354049052, y20 -> -1.184812497,
y21 -> 0.9095763760, y22 -> -1.772900962, y23 -> 0.7891250002,
y24 -> -0.6985642959}}


And in fact, if I change methods it gives me different values, which I suppose, means that I have several different solutions

Hence My questions are: 1) Why the problem is unbounded in one case but is not anymore once I choose a particular method? 2) I have different results for different methods, are all of them acceptable? In the case of usage of Farkas lemma is important that the certificate gives a $$\textbf x \cdot \textbf b < 0$$ for at least one solution, so can I conclude the infeasibility, given that all the 3 accurate values are less then zero? 3) Can I conclude that the Melder answer is the global minimum?

• It's unbounded. Selecting method settings forces NMinimize to use methods that fail to recognize this. – Daniel Lichtblau Oct 27 at 20:58