<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">Sorry, I'm merely a user of numerical mathematics, and last time I studied the simplex algorithm was 25 years ago. What I do see is that your objective function depends only on x_5, the last element of the x vector, and that you are trying to maximise x_5, but constrain it to the interval [0, 1] where a) the expected maximum is the lower bound of your interval and b) something weird is going on around x_5 = 1, where I guess the simplex algorithm breaks down. If you relax the bound, say from -0.5 to 1.5, the algorithm finds your expected result easily.</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">Chris</div></div><br><div class="gmail_quote"><div dir="ltr">On Mon, Nov 26, 2018 at 6:36 PM 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">Thank you. That helps a little. What is the definition of singular in<br>
this context?<br>
<br>
You definitely understood my problem. The correct answer should have<br>
been 0, as you correctly surmised.<br>
<br>
I am trying to find a test to see if a union of half planes captures all<br>
of Euclidean n-space.<br>
<br>
On 11/26/18 5:40 PM, Chris F Waigl wrote:<br>
> Hi Stephen,<br>
> <br>
> The problem appears to be singular around the solution. A very quick<br>
> exploration shows me that if you replace your upper bound b by a very<br>
> small epsilon > 0, you get a stable result. <br>
> <br>
> For example: <br>
> b = np.zeros(8) + 0.001<br>
> <br>
> fun: -0.11764011575264395<br>
> message: 'Optimization terminated successfully.'<br>
> nit: 6<br>
> slack: array([0. , 0. , 0.40742577, 0. , 0.40742577, 0. , 0. , 0. , 0.88235988])<br>
> status: 0<br>
> success: True<br>
> x: array([0. , 0. , 0. , 0.0834722 , 0.41811509, 0.11764012])<br>
> <br>
> And for print(np.dot(A, result.x)) I get [ 0.001 0.001 -0.00307426 0.001<br>
> -0.00307426 0.001 0.001 0.001 ]<br>
> <br>
> In the objective function, y_2 = y_4 = -3.0742577 * epsilon, and the<br>
> other 6 values also converge towards zero when epsilon -> 0 . <br>
> <br>
> If I read your problem correctly, your objective function is simply (-1)<br>
> times x_5, the last element of x. The approach above would converge<br>
> towards the trivial solution, x = 0, but your solution above minimizes<br>
> f(x) by maximizing x_5 at 1. If we pick out an x_5, then the problem<br>
> collapses to a new problems to find [x_0 ... x_4] so that A[:, 0:7] *<br>
> [x_0 ... x_4]' < b, where b is (-1) * the last column of your A. But the<br>
> objective function is now indeterminate, so there is nothing to optimize. <br>
> <br>
> HTH,<br>
> <br>
> Chris<br>
> <br>
> On Mon, Nov 26, 2018 at 11:43 AM Montgomery-Smith, Stephen<br>
> <<a href="mailto:stephen@missouri.edu" target="_blank">stephen@missouri.edu</a> <mailto:<a href="mailto:stephen@missouri.edu" target="_blank">stephen@missouri.edu</a>>> wrote:<br>
> <br>
> 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> <mailto:<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>
> <br>
> <br>
> <br>
> -- <br>
> Chris Waigl . <a href="mailto:chris.waigl@gmail.com" target="_blank">chris.waigl@gmail.com</a> <mailto:<a href="mailto:chris.waigl@gmail.com" target="_blank">chris.waigl@gmail.com</a>> .<br>
> <a href="mailto:chris@lascribe.net" target="_blank">chris@lascribe.net</a> <mailto:<a href="mailto:chris@lascribe.net" target="_blank">chris@lascribe.net</a>><br>
> <a href="http://eggcorns.lascribe.net" rel="noreferrer" target="_blank">http://eggcorns.lascribe.net</a> . <a href="http://chryss.eu" rel="noreferrer" target="_blank">http://chryss.eu</a><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>
> <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>