<div dir="ltr"><div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">Hi Stephen,</div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">The problem appears to be singular around the solution. A very quick exploration shows me that if you replace your upper bound b by a very small epsilon > 0, you get a stable result. </div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">For example: </div><div class="gmail_default" style=""><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">b = np.zeros(8) + 0.001</div><div class="gmail_default" style=""><pre style="font-family:arial,helvetica,sans-serif"> fun: -0.11764011575264395
message: 'Optimization terminated successfully.'
nit: 6
slack: array([0. , 0. , 0.40742577, 0. , 0.40742577, 0. , 0. , 0. , 0.88235988])
status: 0
success: True
x: array([0. , 0. , 0. , 0.0834722 , 0.41811509, 0.11764012])</pre>And for print(np.dot(A, result.x)) I get [ 0.001 0.001 -0.00307426 0.001 -0.00307426 0.001 0.001 0.001 ]</div><div class="gmail_default" style=""><br></div><div class="gmail_default" style="">In the objective function, y_2 = y_4 = -3.0742577 * epsilon, and the other 6 values also converge towards zero when epsilon -> 0 . </div><div class="gmail_default" style=""><br></div><div class="gmail_default" style="">If I read your problem correctly, your objective function is simply (-1) times x_5, the last element of x. The approach above would converge towards the trivial solution, x = 0, but your solution above minimizes f(x) by maximizing x_5 at 1. If we pick out an x_5, then the problem collapses to a new problems to find [x_0 ... x_4] so that A[:, 0:7] * [x_0 ... x_4]' < b, where b is (-1) * the last column of your A. But the objective function is now indeterminate, so there is nothing to optimize. </div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><br></div><div style="font-family:arial,helvetica,sans-serif">HTH,</div><div style="font-family:arial,helvetica,sans-serif"><br></div><div style="font-family:arial,helvetica,sans-serif">Chris</div></div></div></div></div><br><div class="gmail_quote"><div dir="ltr">On Mon, Nov 26, 2018 at 11:43 AM Montgomery-Smith, Stephen <<a href="mailto:stephen@missouri.edu">stephen@missouri.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">I am trying to solve a linear programming problem. The constraint is of<br>
the form A.x <= 0. But linprog gives an answer that doesn't satisfy the<br>
constraint.<br>
<br>
The attached program gives A.x as<br>
<br>
[-2.32109228 2.32017594 4.71436317 3.6433767 -4.26629574 2.32384597<br>
-1.96166184 -4.96206197]<br>
<br>
which definitely doesn't satisfy the constraint. Is this a bug, or some<br>
subtle floating point error?<br>
<br>
Program follows (also as attachment):<br>
<br>
from scipy.optimize import linprog<br>
import numpy as np<br>
<br>
A = [[0.5919650431077654, -0.5271408402306996, 0.6096719792636803,<br>
1.2379670854947114, 0.2656040423387233, -0.972363043155988],<br>
[-0.5914974900295467, -0.5266568950860249, 0.6105433925177587,<br>
1.258297461476007, -0.285688537323182, 0.9726089241528251],<br>
[-0.593015674004932, 0.5280764198909397, 0.6078385518701857,<br>
-1.1964319796886902, -0.2223431679788034, -0.9740888117098865],<br>
[0.5935986604093653, 0.5285277328950352, 0.6068764832493029,<br>
-1.1752312553140132, 0.19916734259906424, 0.976063912714949],<br>
[0.593015674004932, -0.5280764198909397, -0.6078385518701857,<br>
-1.1964319796886902, -0.2223431679788034, -0.9740888117098865],<br>
[-0.5935986604093653, -0.5285277328950352, -0.6068764832493029,<br>
-1.1752312553140132, 0.19916734259906424, 0.976063912714949],<br>
[-0.5919650431077654, 0.5271408402306996, -0.6096719792636803,<br>
1.2379670854947114, 0.2656040423387233, -0.972363043155988],<br>
[0.5914974900295467, 0.5266568950860249, -0.6105433925177587,<br>
1.258297461476007, -0.285688537323182, 0.9726089241528251]]<br>
e = [0, 0, 0, 0, 0, -1]<br>
bounds = [(None, None), (None, None), (None, None), (None, None), (None,<br>
None), (0, 1)]<br>
b = [0]*len(A)<br>
result = linprog(e, A_ub = A, b_ub = b, bounds = bounds)<br>
print np.matmul(A, result.x)<br>
<br>
_______________________________________________<br>
SciPy-User mailing list<br>
<a href="mailto:SciPy-User@python.org" target="_blank">SciPy-User@python.org</a><br>
<a href="https://mail.python.org/mailman/listinfo/scipy-user" rel="noreferrer" target="_blank">https://mail.python.org/mailman/listinfo/scipy-user</a><br>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><font face="arial, helvetica, sans-serif">Chris Waigl . <a href="mailto:chris.waigl@gmail.com" target="_blank">chris.waigl@gmail.com</a> . <a href="mailto:chris@lascribe.net" target="_blank">chris@lascribe.net</a><br><a href="http://eggcorns.lascribe.net" target="_blank">http://eggcorns.lascribe.net</a> . <a href="http://chryss.eu" target="_blank">http://chryss.eu</a></font></div></div></div></div></div>