0
$\begingroup$

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

enter image description here

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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.