#6456: Upgrade cvxopt in sage from 0.9 to 1.1.3
-------------------------------------------------+--------------------------
Reporter: was | Owner: mabshoff
Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.6.1
Component: packages | Keywords:
Author: Harald Schilly, Dmitrii Pasechnik | Upstream: Completely
fixed; Fix reported upstream
Reviewer: | Merged:
Work_issues: licence |
-------------------------------------------------+--------------------------
Comment(by dimpase):
Replying to [comment:118 drkirkby]:
> If I understand this correctly, the default solver gives a result of
6.2499999 and GLPK gives 6.25. These two are very similar, so although
I've got no idea what sort of relative error can be expected of the
different solvers, intuitively it looks like the two solvers are agreeing
with each other.
these two solvers use rather different algorithms. The default solver uses
an interior point method, and GLPK uses a simplex method. The latter is
exact, the former is approximate. The exactness of the simplex method is
not an absolute given though, as GLPK uses floating points to compute
with, essentially, rational data. On this particular example it seems to
have enough precision to give the exact answer.
>
> I've got no idea if the answer is right though! Is there any theoretical
reason for accepting these answers? Or is the answer accepted just because
that what's the computer gives? If it was possible to compute this in
another way (perhaps using Mathematica or something like that), or better
still a theoretical explanation of why it is right, it would give me
personally more confidence. I really dislike numerical results which are
not substantiated in any way.
This can be checked using the outputs of the solvers (so called
complementary slackness condition).
{{{
sage: v=vector([-1.0,-1.0,-1.0])
sage:
m=matrix([[50.0,24.0,0.0],[30.0,33.0,0.0],[-1.0,0.0,0.0],[0.0,-1.0,0.0],[0.0,0.0,1.0],[0.0,0.0,-1.0
....: ]])
sage: h=vector([2400.0,2100.0,-45.0,-5.0,1.0,-1.0])
sage: sol=linear_program(v,m,h,solver='glpk')
GLPK Simplex Optimizer, v4.44
6 rows, 3 columns, 8 non-zeros
Preprocessing...
2 rows, 2 columns, 4 non-zeros
Scaling...
A: min|aij| = 2.400e+01 max|aij| = 5.000e+01 ratio = 2.083e+00
GM: min|aij| = 8.128e-01 max|aij| = 1.230e+00 ratio = 1.514e+00
EQ: min|aij| = 6.606e-01 max|aij| = 1.000e+00 ratio = 1.514e+00
Constructing initial basis...
Size of triangular part = 2
* 0: obj = -5.100000000e+01 infeas = 0.000e+00 (0)
* 1: obj = -5.225000000e+01 infeas = 0.000e+00 (0)
OPTIMAL SOLUTION FOUND
sage: sol
{'status': 'optimal', 's': (-3.8369307731e-13, 543.75, 0.0, 1.25, 0.0,
0.0), 'primal objective': -52.250000000000014, 'y': (), 'x': (45.0, 6.25,
1.0), 'z': (0.0416666666667, -0.0, 1.08333333333, -0.0, 1.0, -0.0)}
sage: sol['s']*sol['z']
-1.59872115546e-14
sage: sol=linear_program(v,m,h)
sage: sol
{'status': 'optimal', 's': (1.26732907086e-07, 543.750000521,
1.09482003526e-08, 1.24999997812, 1.89761395929e-09, 2.07552470867e-09),
'primal objective': -52.249999985182768, 'y': (), 'x': (45.000000009,
6.24999997613, 1.00000000009), 'z': (0.0416666686307, 3.3075453137e-11,
1.08333341676, 3.70511110788e-08, 11.1479097616, 10.1479097616)}
sage: sol['s']*sol['z']
1.2365642167e-07
}}}
(the fact that {{{sol['s']*sol['z']}}} is 0.0 (well, with an acceptable
error, for both solvers, although the default server could be tuned a bit
better) is that complementary slackness condition in action)
But this is more coding, if done properly.
In fact, a function checking these should become a part of the library.
In this case, however, I am positive the answers are correct, and I can
call myself an expert on this stuff :-)
Dima
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/6456#comment:119>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
