Opened 4 years ago

Closed 4 years ago

Last modified 3 years ago

#20506 closed enhancement (fixed)

dual variables handling in SDP solver(s)

Reported by: dimpase Owned by:
Priority: major Milestone: sage-7.2
Component: numerical Keywords:
Cc: srobik, mkoeppe, fbissey Merged in:
Authors: Dima Pasechnik Reviewers: Matthias Koeppe
Report Upstream: N/A Work issues:
Branch: 572b630 (Commits) Commit:
Dependencies: #19072 Stopgaps:

Description

At present only primal variables are made available in SemidefiniteProgram(), although the dual variables are typically also provided by backends. This ticket added access to dual (and slack) variables.

Attachments (1)

xx.sage (1000 bytes) - added by dimpase 4 years ago.
run this as ./sage <xx.sage

Download all attachments as: .zip

Change History (42)

comment:1 Changed 4 years ago by dimpase

  • Cc srobik mkoeppe added
  • Status changed from new to needs_review

the dependence on #19072 may be ignored for all practical purposes.

comment:2 follow-up: Changed 4 years ago by mkoeppe

I'm a bit puzzled why you would want doctests for the particular floating point noise that you get from this version of the solver. Seems like extra work every time the package is upgraded?

comment:3 in reply to: ↑ 2 Changed 4 years ago by dimpase

Replying to mkoeppe:

I'm a bit puzzled why you would want doctests for the particular floating point noise that you get from this version of the solver. Seems like extra work every time the package is upgraded?

I tried to round things using '...' etc as much as possible. I can in principle go further with replacing things like

    sage: (p.slack(0)*p.dual_variable(0)).trace()
    1.71...e-07

by

    sage: 0.0e0 <= (p.slack(0)*p.dual_variable(0)).trace() < 1.75e-07
    True

Eventually we should think how to adapt your testing framework to SDP.

comment:4 follow-up: Changed 4 years ago by mkoeppe

How about

sage: (p.slack(0)*p.dual_variable(0)).trace()  # tol 1e-6
0

comment:5 Changed 4 years ago by git

  • Commit changed from 73e2bf6b76fcecdd4f388caa8c3016707aa5013f to df80c5a7736bf85ccb62b0f2d9120cd3de641399

Branch pushed to git repo; I updated commit sha1. New commits:

df80c5ausing #tol

comment:6 in reply to: ↑ 4 Changed 4 years ago by dimpase

Replying to mkoeppe:

How about

sage: (p.slack(0)*p.dual_variable(0)).trace()  # tol 1e-6
0

good idea, fixed!

comment:7 follow-up: Changed 4 years ago by mkoeppe

There are more places in the file that could use the #tol. And perhaps there should be an example in which the slack is not 0.

comment:8 Changed 4 years ago by git

  • Commit changed from df80c5a7736bf85ccb62b0f2d9120cd3de641399 to b91e62d7827e3dcc7d478d0a44dc7913fc5d7008

Branch pushed to git repo; I updated commit sha1. New commits:

b91e62dexample with non-0 slack

comment:9 in reply to: ↑ 7 Changed 4 years ago by dimpase

Replying to mkoeppe:

There are more places in the file that could use the #tol.

I did add it all over the place, in fact.

And perhaps there should be an example in which the slack is not 0.

OK, see the last commit.

comment:10 Changed 4 years ago by mkoeppe

I mean these ones in cvxopt_sdp_backend.

    cpdef dual_variable(self, int i, sparse=False):
[...]
            sage: p.add_constraint(b1*x[0] + b2*x[1] <= b3)
            sage: p.solve()
            -2.9999999...
            sage: B=p.get_backend()
            sage: x=p.get_values(x).values()
            sage: -(a3*B.dual_variable(0)).trace()-(b3*B.dual_variable(1)).trace()
            -3.0000000...

comment:11 Changed 4 years ago by git

  • Commit changed from b91e62d7827e3dcc7d478d0a44dc7913fc5d7008 to 462e5b1df19e0845078bad9686f2848aad503f21

Branch pushed to git repo; I updated commit sha1. New commits:

462e5b1more #tol tags

comment:12 follow-up: Changed 4 years ago by mkoeppe

The patchbot complains about decreased coverage; probably _get_answer

comment:13 Changed 4 years ago by git

  • Commit changed from 462e5b1df19e0845078bad9686f2848aad503f21 to 604153bf8a00375192e0ff304f373101997fae66

Branch pushed to git repo; I updated commit sha1. New commits:

604153bextra test, two useless lines removed

comment:14 in reply to: ↑ 12 Changed 4 years ago by dimpase

Replying to mkoeppe:

The patchbot complains about decreased coverage; probably _get_answer

thanks; hopefully fixed now.

comment:15 Changed 4 years ago by mkoeppe

  • Reviewers set to Matthias Koeppe
  • Status changed from needs_review to positive_review

Looking good.

comment:16 Changed 4 years ago by vbraun

  • Status changed from positive_review to needs_work
sage -t --long src/sage/numerical/sdp.pyx
**********************************************************************
File "src/sage/numerical/sdp.pyx", line 73, in sage.numerical.sdp
Failed example:
    opt = p.solve()
Exception raised:
    Traceback (most recent call last):
      File "/Users/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.numerical.sdp[15]>", line 1, in <module>
        opt = p.solve()
      File "sage/numerical/sdp.pyx", line 946, in sage.numerical.sdp.SemidefiniteProgram.solve (/Users/buildslave-sage/slave/sage_git/build/src/build/cythonized/sage/numerical/sdp.c:7984)
        self._backend.solve()
      File "sage/numerical/backends/cvxopt_sdp_backend.pyx", line 424, in sage.numerical.backends.cvxopt_sdp_backend.CVXOPTSDPBackend.solve (/Users/buildslave-sage/slave/sage_git/build/src/build/cythonized/sage/numerical/backends/cvxopt_sdp_backend.c:5326)
        raise SDPSolverException("CVXOPT: Terminated early due to numerical difficulties or because the maximum number of iterations was reached.")
    SDPSolverException: CVXOPT: Terminated early due to numerical difficulties or because the maximum number of iterations was reached.
**********************************************************************
File "src/sage/numerical/sdp.pyx", line 78, in sage.numerical.sdp
Failed example:
    print 'Objective Value:', round(opt,3)
Exception raised:
    Traceback (most recent call last):
      File "/Users/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.numerical.sdp[16]>", line 1, in <module>
        print 'Objective Value:', round(opt,Integer(3))
    NameError: name 'opt' is not defined
**********************************************************************
File "src/sage/numerical/sdp.pyx", line 97, in sage.numerical.sdp
Failed example:
    p.dual_variable(1)
Expected:
    [ 85545.1... -85545.1...]
    [-85545.1...  85545.1...]
Got:
     [ 88653817081280.4 -88653817022970.2]
    [-88653817022970.2  88653816964660.0]
**********************************************************************
File "src/sage/numerical/sdp.pyx", line 103, in sage.numerical.sdp
Failed example:
    opt-((p.dual_variable(0)*a3).trace()+(p.dual_variable(1)*b3).trace())  # tol 8e-08
Exception raised:
    Traceback (most recent call last):
      File "/Users/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.numerical.sdp[20]>", line 1, in <module>
        opt-((p.dual_variable(Integer(0))*a3).trace()+(p.dual_variable(Integer(1))*b3).trace())  # tol 8e-08
    NameError: name 'opt' is not defined
**********************************************************************
File "src/sage/numerical/sdp.pyx", line 110, in sage.numerical.sdp
Failed example:
    (p.slack(0)*p.dual_variable(0)).trace()       # tol 2e-07
Expected:
    0.0
Got:
    0.0003622770309448242
Tolerance exceeded:
    0.0 vs 0.0003622770309448242, tolerance 4e-04 > 2e-07
**********************************************************************
1 item had failures:
   5 of  41 in sage.numerical.sdp
    [283 tests, 5 failures, 0.67 s]

comment:17 Changed 4 years ago by dimpase

  • Cc fbissey added

hmm, why do these tests fail on Gentoo, and on Gentoo only? Do these patchbots have some sort of strange configuration of numerics?

comment:19 follow-up: Changed 4 years ago by fbissey

I don't really have a clue but I can test this in sage-on-gentoo for kicks.

Changed 4 years ago by dimpase

run this as ./sage <xx.sage

comment:20 in reply to: ↑ 19 Changed 4 years ago by dimpase

Replying to fbissey:

I don't really have a clue but I can test this in sage-on-gentoo for kicks.

Could you please run (on the a recent beta - the ticket branch is not needed) the attached file, and post the output? (Basically, there should not be any ZeroDivisionError: float division by zero)

comment:21 follow-up: Changed 4 years ago by fbissey

7.2.beta6+ (I am on Volker's branch sometime yesterday), not very promising

fbissey@QCD-nzi3 ~ $ sage
┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 7.2.beta6, Release Date: 2016-04-28               │
│ Type "notebook()" for the browser-based notebook interface.        │
│ Type "help()" for help.                                            │
└────────────────────────────────────────────────────────────────────┘
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Warning: this is a prerelease version, and it may be unstable.     ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
sage: from cvxopt import matrix as mat, solvers
sage: c = mat([-1.,1.])
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-2-14ab25c781f3> in <module>()
----> 1 c = mat([-RealNumber('1.'),RealNumber('1.')])

TypeError: invalid type in list

comment:22 in reply to: ↑ 21 Changed 4 years ago by dimpase

Replying to fbissey:

7.2.beta6+ (I am on Volker's branch sometime yesterday), not very promising

you missed the 1st line: preparser(False)

(probably cause you tried sage xx.sage rather than sage <xx.sage)

fbissey@QCD-nzi3 ~ $ sage
┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 7.2.beta6, Release Date: 2016-04-28               │
│ Type "notebook()" for the browser-based notebook interface.        │
│ Type "help()" for help.                                            │
└────────────────────────────────────────────────────────────────────┘
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Warning: this is a prerelease version, and it may be unstable.     ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
sage: from cvxopt import matrix as mat, solvers
sage: c = mat([-1.,1.])
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-2-14ab25c781f3> in <module>()
----> 1 c = mat([-RealNumber('1.'),RealNumber('1.')])

TypeError: invalid type in list
Last edited 4 years ago by dimpase (previous) (diff)

comment:23 Changed 4 years ago by fbissey

That explains!

fbissey@QCD-nzi3 ~ $ sage < xx.sage 
┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 7.2.beta6, Release Date: 2016-04-28               │
│ Type "notebook()" for the browser-based notebook interface.        │
│ Type "help()" for help.                                            │
└────────────────────────────────────────────────────────────────────┘
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Warning: this is a prerelease version, and it may be unstable.     ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
sage: sage: sage: sage: sage: sage: sage: sage: sage: sage: sage:      pcost       dcost       gap    pres   dres   k/t
 0: -1.2413e+00 -2.7310e+01  2e+01  3e-01  1e+01  1e+00
 1: -1.4977e+00 -3.1971e+00  6e-01  2e-02  9e-01  2e-01
 2: -1.2729e+00 -2.1411e+00  6e-01  1e-02  5e-01  2e-01
 3: -1.1436e+00 -1.2534e+00  8e-02  1e-03  6e-02  2e-02
 4: -1.1034e+00 -1.2438e+00  3e-01  2e-03  8e-02  4e-02
 5: -1.0500e+00 -1.0609e+00  2e-02  1e-04  7e-03  4e-03
 6: -1.0338e+00 -1.0407e+00  4e-02  1e-04  6e-03  7e-03
 7: -1.0201e+00 -1.0209e+00  8e-03  2e-05  1e-03  1e-03
 8: -1.0176e+00 -1.0176e+00  4e-02  4e-05  2e-03  4e-03
 9: -1.0071e+00 -1.0069e+00  3e-03  3e-06  1e-04  5e-04
10: -1.0042e+00 -1.0038e+00  4e-03  2e-06  8e-05  6e-04
11: -1.0027e+00 -1.0026e+00  1e-03  4e-07  2e-05  2e-04
12: -1.0028e+00 -1.0022e+00  8e-03  1e-06  5e-05  7e-04
13: -1.0009e+00 -1.0009e+00  6e-04  8e-08  4e-06  7e-05
14: -1.0005e+00 -1.0004e+00  3e-04  2e-08  1e-06  5e-05
15: -1.0003e+00 -1.0002e+00  8e-04  2e-08  1e-06  1e-04
16: -1.0000e+00 -1.0000e+00  9e-05  2e-09  1e-07  1e-05
17: -9.9992e-01 -9.9990e-01  2e-04  2e-09  8e-08  2e-05
18: -9.9986e-01 -9.9986e-01  2e-05  2e-10  1e-08  4e-06
19: -9.9985e-01 -9.9984e-01  8e-05  3e-10  1e-08  9e-06
20: -9.9982e-01 -9.9982e-01  9e-06  3e-11  1e-09  1e-06
21: -9.9982e-01 -9.9981e-01  3e-05  3e-11  2e-09  3e-06
22: -9.9981e-01 -9.9981e-01  3e-06  4e-12  2e-10  5e-07
23: -9.9981e-01 -9.9981e-01  1e-05  7e-11  1e-10  1e-06
24: -9.9980e-01 -9.9980e-01  1e-06  7e-12  5e-10  2e-07
25: -9.9980e-01 -9.9980e-01  3e-06  2e-08  1e-09  4e-07
26: -9.9980e-01 -9.9980e-01  4e-07  3e-09  5e-11  6e-08
Optimal solution found.
sage: sage: sage: sage: sage: sage: sage: sage: sage: sage: sage: sage: sage: sage: sage: sage: ---------------------------------------------------------------------------
SDPSolverException                        Traceback (most recent call last)
<ipython-input-25-de8ebd622e01> in <module>()
----> 1 p.solve() # boom - division by 0

/usr/lib64/python2.7/site-packages/sage/numerical/sdp.pyx in sage.numerical.sdp.SemidefiniteProgram.solve (/scratch2/portage/sci-mathematics/sage-9999/work/sage-9999/src-python2_7/build/cythonized/sage/numerical/sdp.c:7919)()
    902             3.0
    903         """
--> 904         self._backend.solve()
    905         return self._backend.get_objective_value()
    906 

/usr/lib64/python2.7/site-packages/sage/numerical/backends/cvxopt_sdp_backend.pyx in sage.numerical.backends.cvxopt_sdp_backend.CVXOPTSDPBackend.solve (/scratch2/portage/sci-mathematics/sage-9999/work/sage-9999/src-python2_7/build/cythonized/sage/numerical/backends/cvxopt_sdp_backend.c:5165)()
    418             pass
    419         elif self.answer['status'] == 'primal infeasible':
--> 420             raise SDPSolverException("CVXOPT: primal infeasible")
    421         elif self.answer['status'] == 'dual infeasible':
    422             raise SDPSolverException("CVXOPT: dual infeasible")

SDPSolverException: CVXOPT: primal infeasible
sage: sage: sage: Exiting Sage (CPU time 0m0.60s, Wall time 0m2.40s).

This is sage-on-gentoo. Does SDP needs a particular dependency enabled in CVXOPT that I could have missed?

comment:24 Changed 4 years ago by dimpase

OK, I just found that the problem is not Gentoo-only, it is CPU-related (Xeon only?) (is QCD-nzi3 Xeon, too?)

Reproducible on

Intel(R) Xeon(R) CPU  X5660  @ 2.80GHz (UGent, Gentoo)
Intel(R) Xeon(R) CPU @ 2.30GHz         (SMC, Ubuntu)

Will now see if this is Atlas-related (by trying "dumb" Atlas).

But the bug is very unpleasant; in the attached script the result of runningsol = solvers.sdp(c, Gs=G, hs=h) changes after unrelated (although in the same code-path) lines 13-27.

comment:25 Changed 4 years ago by fbissey

Not an actual Xeon but I am not completely sure

processor	: 11
vendor_id	: GenuineIntel
cpu family	: 6
model		: 44
model name	: Intel(R) Core(TM) i7 CPU         970  @ 3.20GHz
stepping	: 2
microcode	: 0xc
cpu MHz		: 3238.432
cache size	: 12288 KB

Also, sage-on-gentoo above uses openblas...

comment:26 Changed 4 years ago by dimpase

On Intel(R) Core(TM) i7-4510U CPU @ 2.00GHz (laptop, Ubuntu) as well as on Intel(R) Core(TM) i7-4770 CPU @ 3.40GHz (desktop, Fedora-23) the script works.

comment:27 Changed 4 years ago by fbissey

I will build a vanilla 7.2.beta6 and see what happens.

comment:28 follow-up: Changed 4 years ago by dimpase

the failure with xx.sage attachment is also reproducible on OSX (Core2Duo CPU), although it's slightly different (the 2nd and 3rd calls to the solver return "infeasible" rather than bail out with zero division).

So this looks like an genuine bug in CVXOPT interface, or in CVXOPT itself, or both. Somehow it seems to retain too much state. I wish we had an OSX patchbot...

comment:29 Changed 4 years ago by fbissey

For info, vanilla sage same machine

fbissey@QCD-nzi3 ~/sandbox/git-fork/sage $ ./sage < ~/xx.sage 
┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 7.2.beta6, Release Date: 2016-04-28               │
│ Type "notebook()" for the browser-based notebook interface.        │
│ Type "help()" for help.                                            │
└────────────────────────────────────────────────────────────────────┘
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Warning: this is a prerelease version, and it may be unstable.     ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
sage: sage: sage: sage: sage: sage: sage: sage: sage: sage: sage:      pcost       dcost       gap    pres   dres   k/t
 0: -1.2413e+00 -2.7310e+01  2e+01  3e-01  1e+01  1e+00
 1: -1.4977e+00 -3.1971e+00  6e-01  2e-02  9e-01  2e-01
 2: -1.2729e+00 -2.1411e+00  6e-01  1e-02  5e-01  2e-01
 3: -1.1436e+00 -1.2534e+00  8e-02  1e-03  6e-02  2e-02
 4: -1.1034e+00 -1.2438e+00  3e-01  2e-03  8e-02  4e-02
 5: -1.0500e+00 -1.0609e+00  2e-02  1e-04  7e-03  4e-03
 6: -1.0338e+00 -1.0407e+00  4e-02  1e-04  6e-03  7e-03
 7: -1.0201e+00 -1.0209e+00  8e-03  2e-05  1e-03  1e-03
 8: -1.0176e+00 -1.0176e+00  4e-02  4e-05  2e-03  4e-03
 9: -1.0071e+00 -1.0069e+00  3e-03  3e-06  1e-04  5e-04
10: -1.0042e+00 -1.0038e+00  4e-03  2e-06  8e-05  6e-04
11: -1.0027e+00 -1.0026e+00  1e-03  4e-07  2e-05  2e-04
12: -1.0028e+00 -1.0022e+00  8e-03  1e-06  5e-05  7e-04
13: -1.0009e+00 -1.0009e+00  6e-04  8e-08  4e-06  7e-05
14: -1.0005e+00 -1.0004e+00  3e-04  2e-08  1e-06  5e-05
15: -1.0003e+00 -1.0002e+00  8e-04  2e-08  1e-06  1e-04
16: -1.0000e+00 -1.0000e+00  9e-05  2e-09  1e-07  1e-05
17: -9.9992e-01 -9.9990e-01  2e-04  2e-09  8e-08  2e-05
18: -9.9986e-01 -9.9986e-01  2e-05  2e-10  1e-08  4e-06
19: -9.9985e-01 -9.9984e-01  8e-05  3e-10  1e-08  9e-06
20: -9.9982e-01 -9.9982e-01  9e-06  3e-11  1e-09  1e-06
21: -9.9982e-01 -9.9981e-01  3e-05  3e-11  1e-09  3e-06
22: -9.9981e-01 -9.9981e-01  3e-06  4e-12  2e-10  5e-07
23: -9.9981e-01 -9.9981e-01  1e-05  4e-10  1e-10  1e-06
24: -9.9980e-01 -9.9980e-01  1e-06  4e-11  2e-10  2e-07
25: -9.9980e-01 -9.9980e-01  3e-06  2e-08  2e-10  4e-07
26: -9.9980e-01 -9.9980e-01  4e-07  2e-09  1e-09  6e-08
Optimal solution found.
sage: sage: sage: sage: sage: sage: sage: sage: sage: sage: sage: sage: sage: sage: sage: sage: ---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)
<ipython-input-25-de8ebd622e01> in <module>()
----> 1 p.solve() # boom - division by 0

/home/fbissey/sandbox/git-fork/sage/src/sage/numerical/sdp.pyx in sage.numerical.sdp.SemidefiniteProgram.solve (/home/fbissey/sandbox/git-fork/sage/src/build/cythonized/sage/numerical/sdp.c:7916)()
    902             3.0
    903         """
--> 904         self._backend.solve()
    905         return self._backend.get_objective_value()
    906 

/home/fbissey/sandbox/git-fork/sage/src/sage/numerical/backends/cvxopt_sdp_backend.pyx in sage.numerical.backends.cvxopt_sdp_backend.CVXOPTSDPBackend.solve (/home/fbissey/sandbox/git-fork/sage/src/build/cythonized/sage/numerical/backends/cvxopt_sdp_backend.c:5103)()
    412             solvers.options[k] = v
    413 
--> 414         self.answer = solvers.sdp(c,Gs=G_matrix,hs=h_matrix)
    415 
    416         #possible outcomes

/home/fbissey/sandbox/git-fork/sage/local/lib/python2.7/site-packages/cvxopt/coneprog.py in sdp(c, Gl, hl, Gs, hs, A, b, solver, primalstart, dualstart, options, **kwargs)
   4110         ds = None
   4111 
-> 4112     sol = conelp(c, G, h, dims, A = A, b = b, primalstart = ps, dualstart = ds, options = options)
   4113     if sol['s'] is None:
   4114         sol['sl'] = None

/home/fbissey/sandbox/git-fork/sage/local/lib/python2.7/site-packages/cvxopt/coneprog.py in conelp(c, G, h, dims, A, b, primalstart, dualstart, kktsolver, xnewcopy, xdot, xaxpy, xscal, ynewcopy, ydot, yaxpy, yscal, **kwargs)
   1393         # Update lambda and scaling.
   1394 
-> 1395         misc.update_scaling(W, lmbda, ds, dz)
   1396 
   1397         # For kappa, tau block:

/home/fbissey/sandbox/git-fork/sage/local/lib/python2.7/site-packages/cvxopt/misc.py in update_scaling(W, lmbda, s, z)
    626         # r := r*lambda^{-1/2}; rti := rti*lambda^{-1/2}
    627         for i in range(m):
--> 628             a = 1.0 / math.sqrt(lmbda[ind+i])
    629             blas.scal(a, r, offset = m*i, n = m)
    630             blas.scal(a, rti, offset = m*i, n = m)

ZeroDivisionError: float division by zero
sage: sage: ---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)
<ipython-input-26-9348eec359de> in <module>()
----> 1 sol = solvers.sdp(c, Gs=G, hs=h) # boom - division by 0

/home/fbissey/sandbox/git-fork/sage/local/lib/python2.7/site-packages/cvxopt/coneprog.py in sdp(c, Gl, hl, Gs, hs, A, b, solver, primalstart, dualstart, options, **kwargs)
   4110         ds = None
   4111 
-> 4112     sol = conelp(c, G, h, dims, A = A, b = b, primalstart = ps, dualstart = ds, options = options)
   4113     if sol['s'] is None:
   4114         sol['sl'] = None

/home/fbissey/sandbox/git-fork/sage/local/lib/python2.7/site-packages/cvxopt/coneprog.py in conelp(c, G, h, dims, A, b, primalstart, dualstart, kktsolver, xnewcopy, xdot, xaxpy, xscal, ynewcopy, ydot, yaxpy, yscal, **kwargs)
   1393         # Update lambda and scaling.
   1394 
-> 1395         misc.update_scaling(W, lmbda, ds, dz)
   1396 
   1397         # For kappa, tau block:

/home/fbissey/sandbox/git-fork/sage/local/lib/python2.7/site-packages/cvxopt/misc.py in update_scaling(W, lmbda, s, z)
    626         # r := r*lambda^{-1/2}; rti := rti*lambda^{-1/2}
    627         for i in range(m):
--> 628             a = 1.0 / math.sqrt(lmbda[ind+i])
    629             blas.scal(a, r, offset = m*i, n = m)
    630             blas.scal(a, rti, offset = m*i, n = m)

ZeroDivisionError: float division by zero
sage: Exiting Sage (CPU time 0m0.73s, Wall time 0m3.58s).

If you think the problem is upstream, they are quite responsive in chasing issue.

comment:30 Changed 4 years ago by git

  • Commit changed from 604153bf8a00375192e0ff304f373101997fae66 to 0760b6f47cfbddfc381903211e741aee50d63ad3

Branch pushed to git repo; I updated commit sha1. New commits:

ac99206Merge branch 'develop' into sdpdual
0760b6fforgotten cinitialisation, fixed OSX errors

comment:31 in reply to: ↑ 28 Changed 4 years ago by dimpase

Replying to dimpase:

the failure with xx.sage attachment is also reproducible on OSX (Core2Duo CPU), although it's slightly different (the 2nd and 3rd calls to the solver return "infeasible" rather than bail out with zero division).

OSX is fixed by the latest commit. But it does not fix the Gentoo Xeon case...

Does it fix sage-on-gentoo with openblas case?

comment:32 Changed 4 years ago by git

  • Commit changed from 0760b6f47cfbddfc381903211e741aee50d63ad3 to 38a2bd69eaa9b47d1c3856722c2abd28264e74d2

Branch pushed to git repo; I updated commit sha1. New commits:

38a2bd6forgotten cinitialisation in the cvxopt LP interface

comment:33 Changed 4 years ago by fbissey

I will need to put that in a patch and rebuild since it is .pyx in the case of sage-on-gentoo that means rebuilding the whole library and the doc (but not the dependencies). I'll put both commits.

comment:34 Changed 4 years ago by fbissey

No changes for sage-on-gentoo when including the last two commits (and only those not the rest of the branch).

comment:35 Changed 4 years ago by fbissey

No impact on vanilla sage on the same machine.

comment:36 follow-up: Changed 4 years ago by git

  • Commit changed from 38a2bd69eaa9b47d1c3856722c2abd28264e74d2 to 83210c91601a00020772510ff5977d0c007ce4d5

Branch pushed to git repo; I updated commit sha1. New commits:

8f2bf00Merge remote-tracking branch 'trac/u/dimpase/sdpdual' into sdpd
02157adremoving numerically unstable test - will be on another ticket
83210c9Merge branch 'u/dimpase/sdpdual' of trac.sagemath.org:sage into sdpd

comment:37 Changed 4 years ago by git

  • Commit changed from 83210c91601a00020772510ff5977d0c007ce4d5 to 572b630527b6c6a29853f18bedd3bcea9e30ca57

Branch pushed to git repo; I updated commit sha1. New commits:

572b630trim numerical noise further

comment:38 Changed 4 years ago by dimpase

  • Status changed from needs_work to needs_review

I removed the "unstable" example. Now sage4 bot (and the rest) should be happy. It will go on another ticket.

comment:39 Changed 4 years ago by mkoeppe

  • Status changed from needs_review to positive_review

comment:40 Changed 4 years ago by vbraun

  • Branch changed from u/dimpase/sdpdual to 572b630527b6c6a29853f18bedd3bcea9e30ca57
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:41 in reply to: ↑ 36 Changed 3 years ago by dimpase

  • Commit 572b630527b6c6a29853f18bedd3bcea9e30ca57 deleted

Replying to git:

02157adremoving numerically unstable test - will be on another ticket

this is traced down to wrongly set refinement parameter in numerical/backends/cvxopt_sdp_backend.py

diff --git a/src/sage/numerical/backends/cvxopt_sdp_backend.pyx b/src/sage/numerical/backends/cvxopt_sdp_backend.pyx
index 6c24173..b65d4bc 100644
--- a/src/sage/numerical/backends/cvxopt_sdp_backend.pyx
+++ b/src/sage/numerical/backends/cvxopt_sdp_backend.pyx
@@ -63,7 +63,7 @@ cdef class CVXOPTSDPBackend(GenericSDPBackend):
                       "abstol":1e-7,
                       "reltol":1e-6,
                       "feastol":1e-7,
-                      "refinement":0 }
+                      "refinement":1 }
         self.answer = {}
         if maximization:
             self.set_sense(+1)

Will be fixed on #21778

Note: See TracTickets for help on using tickets.