CVXOPT SDP Backend#

AUTHORS:

Ingolfur Edvardsson (2014-05): initial implementation
Dima Pasechnik (2015-12): minor fixes

class sage.numerical.backends.cvxopt_sdp_backend.CVXOPTSDPBackend[source]#

Bases: MatrixSDPBackend

Cython constructor

EXAMPLES:

Sage

sage: from sage.numerical.backends.generic_sdp_backend import get_solver
sage: p = get_solver(solver="CVXOPT")

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_sdp_backend import get_solver
>>> p = get_solver(solver="CVXOPT")

dual_variable(i, sparse=False)[source]#

The \(i\)-th dual variable

Available after self.solve() is called, otherwise the result is undefined

index (integer) – the constraint’s id.

OUTPUT:

The matrix of the \(i\)-th dual variable

EXAMPLES:

Sage

sage: p = SemidefiniteProgram(maximization=False, solver='cvxopt')
sage: x = p.new_variable()
sage: p.set_objective(x[0] - x[1])
sage: a1 = matrix([[1, 2.], [2., 3.]])
sage: a2 = matrix([[3, 4.], [4., 5.]])
sage: a3 = matrix([[5, 6.], [6., 7.]])
sage: b1 = matrix([[1, 1.], [1., 1.]])
sage: b2 = matrix([[2, 2.], [2., 2.]])
sage: b3 = matrix([[3, 3.], [3., 3.]])
sage: p.add_constraint(a1*x[0] + a2*x[1] <= a3)
sage: p.add_constraint(b1*x[0] + b2*x[1] <= b3)
sage: p.solve()                                     # tol 1e-08
-3.0
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()     # tol 1e-07
-3.0
sage: g = sum((B.slack(j)*B.dual_variable(j)).trace() for j in range(2)); g  # tol 1.5e-08
0.0

Python

>>> from sage.all import *
>>> p = SemidefiniteProgram(maximization=False, solver='cvxopt')
>>> x = p.new_variable()
>>> p.set_objective(x[Integer(0)] - x[Integer(1)])
>>> a1 = matrix([[Integer(1), RealNumber('2.')], [RealNumber('2.'), RealNumber('3.')]])
>>> a2 = matrix([[Integer(3), RealNumber('4.')], [RealNumber('4.'), RealNumber('5.')]])
>>> a3 = matrix([[Integer(5), RealNumber('6.')], [RealNumber('6.'), RealNumber('7.')]])
>>> b1 = matrix([[Integer(1), RealNumber('1.')], [RealNumber('1.'), RealNumber('1.')]])
>>> b2 = matrix([[Integer(2), RealNumber('2.')], [RealNumber('2.'), RealNumber('2.')]])
>>> b3 = matrix([[Integer(3), RealNumber('3.')], [RealNumber('3.'), RealNumber('3.')]])
>>> p.add_constraint(a1*x[Integer(0)] + a2*x[Integer(1)] <= a3)
>>> p.add_constraint(b1*x[Integer(0)] + b2*x[Integer(1)] <= b3)
>>> p.solve()                                     # tol 1e-08
-3.0
>>> B = p.get_backend()
>>> x = p.get_values(x).values()
>>> -(a3*B.dual_variable(Integer(0))).trace() - (b3*B.dual_variable(Integer(1))).trace()     # tol 1e-07
-3.0
>>> g = sum((B.slack(j)*B.dual_variable(j)).trace() for j in range(Integer(2))); g  # tol 1.5e-08
0.0

get_objective_value()[source]#

Return the value of the objective function.

Note

Behaviour is undefined unless solve has been called before.

EXAMPLES:

Sage

sage: p = SemidefiniteProgram(solver="cvxopt", maximization=False)
sage: x = p.new_variable()
sage: p.set_objective(x[0] - x[1] + x[2])
sage: a1 = matrix([[-7., -11.], [-11., 3.]])
sage: a2 = matrix([[7., -18.], [-18., 8.]])
sage: a3 = matrix([[-2., -8.], [-8., 1.]])
sage: a4 = matrix([[33., -9.], [-9., 26.]])
sage: b1 = matrix([[-21., -11., 0.], [-11., 10., 8.], [0.,   8., 5.]])
sage: b2 = matrix([[0.,  10.,  16.], [10., -10., -10.], [16., -10., 3.]])
sage: b3 = matrix([[-5.,   2., -17.], [2.,  -6.,   8.], [-17.,  8., 6.]])
sage: b4 = matrix([[14., 9., 40.], [9., 91., 10.], [40., 10., 15.]])
sage: p.add_constraint(a1*x[0] + a2*x[1] + a3*x[2] <= a4)
sage: p.add_constraint(b1*x[0] + b2*x[1] + b3*x[2] <= b4)
sage: N(p.solve(), digits=4)
-3.154
sage: N(p.get_backend().get_objective_value(), digits=4)
-3.154

Python

>>> from sage.all import *
>>> p = SemidefiniteProgram(solver="cvxopt", maximization=False)
>>> x = p.new_variable()
>>> p.set_objective(x[Integer(0)] - x[Integer(1)] + x[Integer(2)])
>>> a1 = matrix([[-RealNumber('7.'), -RealNumber('11.')], [-RealNumber('11.'), RealNumber('3.')]])
>>> a2 = matrix([[RealNumber('7.'), -RealNumber('18.')], [-RealNumber('18.'), RealNumber('8.')]])
>>> a3 = matrix([[-RealNumber('2.'), -RealNumber('8.')], [-RealNumber('8.'), RealNumber('1.')]])
>>> a4 = matrix([[RealNumber('33.'), -RealNumber('9.')], [-RealNumber('9.'), RealNumber('26.')]])
>>> b1 = matrix([[-RealNumber('21.'), -RealNumber('11.'), RealNumber('0.')], [-RealNumber('11.'), RealNumber('10.'), RealNumber('8.')], [RealNumber('0.'),   RealNumber('8.'), RealNumber('5.')]])
>>> b2 = matrix([[RealNumber('0.'),  RealNumber('10.'),  RealNumber('16.')], [RealNumber('10.'), -RealNumber('10.'), -RealNumber('10.')], [RealNumber('16.'), -RealNumber('10.'), RealNumber('3.')]])
>>> b3 = matrix([[-RealNumber('5.'),   RealNumber('2.'), -RealNumber('17.')], [RealNumber('2.'),  -RealNumber('6.'),   RealNumber('8.')], [-RealNumber('17.'),  RealNumber('8.'), RealNumber('6.')]])
>>> b4 = matrix([[RealNumber('14.'), RealNumber('9.'), RealNumber('40.')], [RealNumber('9.'), RealNumber('91.'), RealNumber('10.')], [RealNumber('40.'), RealNumber('10.'), RealNumber('15.')]])
>>> p.add_constraint(a1*x[Integer(0)] + a2*x[Integer(1)] + a3*x[Integer(2)] <= a4)
>>> p.add_constraint(b1*x[Integer(0)] + b2*x[Integer(1)] + b3*x[Integer(2)] <= b4)
>>> N(p.solve(), digits=Integer(4))
-3.154
>>> N(p.get_backend().get_objective_value(), digits=Integer(4))
-3.154

get_variable_value(variable)[source]#

Return the value of a variable given by the solver.

Note

Behaviour is undefined unless solve has been called before.

EXAMPLES:

Sage

sage: p = SemidefiniteProgram(solver="cvxopt", maximization=False)
sage: x = p.new_variable()
sage: p.set_objective(x[0] - x[1] + x[2])
sage: a1 = matrix([[-7., -11.], [-11., 3.]])
sage: a2 = matrix([[7., -18.], [-18., 8.]])
sage: a3 = matrix([[-2., -8.], [-8., 1.]])
sage: a4 = matrix([[33., -9.], [-9., 26.]])
sage: b1 = matrix([[-21., -11., 0.], [-11., 10., 8.], [0.,   8., 5.]])
sage: b2 = matrix([[0.,  10.,  16.], [10., -10., -10.], [16., -10., 3.]])
sage: b3 = matrix([[-5.,   2., -17.], [2.,  -6.,   8.], [-17.,  8., 6.]])
sage: b4 = matrix([[14., 9., 40.], [9., 91., 10.], [40., 10., 15.]])
sage: p.add_constraint(a1*x[0] + a2*x[1] + a3*x[2] <= a4)
sage: p.add_constraint(b1*x[0] + b2*x[1] + b3*x[2] <= b4)
sage: N(p.solve(), digits=4)
-3.154
sage: N(p.get_backend().get_variable_value(0), digits=3)
-0.368
sage: N(p.get_backend().get_variable_value(1), digits=4)
1.898
sage: N(p.get_backend().get_variable_value(2), digits=3)
-0.888

Python

>>> from sage.all import *
>>> p = SemidefiniteProgram(solver="cvxopt", maximization=False)
>>> x = p.new_variable()
>>> p.set_objective(x[Integer(0)] - x[Integer(1)] + x[Integer(2)])
>>> a1 = matrix([[-RealNumber('7.'), -RealNumber('11.')], [-RealNumber('11.'), RealNumber('3.')]])
>>> a2 = matrix([[RealNumber('7.'), -RealNumber('18.')], [-RealNumber('18.'), RealNumber('8.')]])
>>> a3 = matrix([[-RealNumber('2.'), -RealNumber('8.')], [-RealNumber('8.'), RealNumber('1.')]])
>>> a4 = matrix([[RealNumber('33.'), -RealNumber('9.')], [-RealNumber('9.'), RealNumber('26.')]])
>>> b1 = matrix([[-RealNumber('21.'), -RealNumber('11.'), RealNumber('0.')], [-RealNumber('11.'), RealNumber('10.'), RealNumber('8.')], [RealNumber('0.'),   RealNumber('8.'), RealNumber('5.')]])
>>> b2 = matrix([[RealNumber('0.'),  RealNumber('10.'),  RealNumber('16.')], [RealNumber('10.'), -RealNumber('10.'), -RealNumber('10.')], [RealNumber('16.'), -RealNumber('10.'), RealNumber('3.')]])
>>> b3 = matrix([[-RealNumber('5.'),   RealNumber('2.'), -RealNumber('17.')], [RealNumber('2.'),  -RealNumber('6.'),   RealNumber('8.')], [-RealNumber('17.'),  RealNumber('8.'), RealNumber('6.')]])
>>> b4 = matrix([[RealNumber('14.'), RealNumber('9.'), RealNumber('40.')], [RealNumber('9.'), RealNumber('91.'), RealNumber('10.')], [RealNumber('40.'), RealNumber('10.'), RealNumber('15.')]])
>>> p.add_constraint(a1*x[Integer(0)] + a2*x[Integer(1)] + a3*x[Integer(2)] <= a4)
>>> p.add_constraint(b1*x[Integer(0)] + b2*x[Integer(1)] + b3*x[Integer(2)] <= b4)
>>> N(p.solve(), digits=Integer(4))
-3.154
>>> N(p.get_backend().get_variable_value(Integer(0)), digits=Integer(3))
-0.368
>>> N(p.get_backend().get_variable_value(Integer(1)), digits=Integer(4))
1.898
>>> N(p.get_backend().get_variable_value(Integer(2)), digits=Integer(3))
-0.888

slack(i, sparse=False)[source]#

Slack of the \(i\)-th constraint

Available after self.solve() is called, otherwise the result is undefined

index (integer) – the constraint’s id.

OUTPUT:

The matrix of the slack of the \(i\)-th constraint

EXAMPLES:

Sage

sage: p = SemidefiniteProgram(maximization = False, solver='cvxopt')
sage: x = p.new_variable()
sage: p.set_objective(x[0] - x[1])
sage: a1 = matrix([[1, 2.], [2., 3.]])
sage: a2 = matrix([[3, 4.], [4., 5.]])
sage: a3 = matrix([[5, 6.], [6., 7.]])
sage: b1 = matrix([[1, 1.], [1., 1.]])
sage: b2 = matrix([[2, 2.], [2., 2.]])
sage: b3 = matrix([[3, 3.], [3., 3.]])
sage: p.add_constraint(a1*x[0] + a2*x[1] <= a3)
sage: p.add_constraint(b1*x[0] + b2*x[1] <= b3)
sage: p.solve()                         # tol 1e-08
-3.0
sage: B = p.get_backend()
sage: B1 = B.slack(1); B1               # tol 1e-08
[0.0 0.0]
[0.0 0.0]
sage: B1.is_positive_definite()
True
sage: x = sorted(p.get_values(x).values())
sage: x[0]*b1 + x[1]*b2 - b3 + B1       # tol 1e-09
[0.0 0.0]
[0.0 0.0]

Python

>>> from sage.all import *
>>> p = SemidefiniteProgram(maximization = False, solver='cvxopt')
>>> x = p.new_variable()
>>> p.set_objective(x[Integer(0)] - x[Integer(1)])
>>> a1 = matrix([[Integer(1), RealNumber('2.')], [RealNumber('2.'), RealNumber('3.')]])
>>> a2 = matrix([[Integer(3), RealNumber('4.')], [RealNumber('4.'), RealNumber('5.')]])
>>> a3 = matrix([[Integer(5), RealNumber('6.')], [RealNumber('6.'), RealNumber('7.')]])
>>> b1 = matrix([[Integer(1), RealNumber('1.')], [RealNumber('1.'), RealNumber('1.')]])
>>> b2 = matrix([[Integer(2), RealNumber('2.')], [RealNumber('2.'), RealNumber('2.')]])
>>> b3 = matrix([[Integer(3), RealNumber('3.')], [RealNumber('3.'), RealNumber('3.')]])
>>> p.add_constraint(a1*x[Integer(0)] + a2*x[Integer(1)] <= a3)
>>> p.add_constraint(b1*x[Integer(0)] + b2*x[Integer(1)] <= b3)
>>> p.solve()                         # tol 1e-08
-3.0
>>> B = p.get_backend()
>>> B1 = B.slack(Integer(1)); B1               # tol 1e-08
[0.0 0.0]
[0.0 0.0]
>>> B1.is_positive_definite()
True
>>> x = sorted(p.get_values(x).values())
>>> x[Integer(0)]*b1 + x[Integer(1)]*b2 - b3 + B1       # tol 1e-09
[0.0 0.0]
[0.0 0.0]

solve()[source]#

Solve the problem.

Note

This method raises SDPSolverException exceptions when the solution cannot be computed for any reason (none exists, or the LP solver was not able to find it, etc…)

EXAMPLES:

Sage

sage: p = SemidefiniteProgram(solver="cvxopt", maximization=False)
sage: x = p.new_variable()
sage: p.set_objective(x[0] - x[1] + x[2])
sage: a1 = matrix([[-7., -11.], [-11., 3.]])
sage: a2 = matrix([[7., -18.], [-18., 8.]])
sage: a3 = matrix([[-2., -8.], [-8., 1.]])
sage: a4 = matrix([[33., -9.], [-9., 26.]])
sage: b1 = matrix([[-21., -11., 0.], [-11., 10., 8.], [0.,   8., 5.]])
sage: b2 = matrix([[0.,  10.,  16.], [10., -10., -10.], [16., -10., 3.]])
sage: b3 = matrix([[-5.,   2., -17.], [2.,  -6.,   8.], [-17.,  8., 6.]])
sage: b4 = matrix([[14., 9., 40.], [9., 91., 10.], [40., 10., 15.]])
sage: p.add_constraint(a1*x[0] + a3*x[2] <= a4)
sage: p.add_constraint(b1*x[0] + b2*x[1] + b3*x[2] <= b4)
sage: N(p.solve(), digits=4)
-3.225
sage: p = SemidefiniteProgram(solver="cvxopt", maximization=False)
sage: x = p.new_variable()
sage: p.set_objective(x[0] - x[1] + x[2])
sage: a1 = matrix([[-7., -11.], [-11., 3.]])
sage: a2 = matrix([[7., -18.], [-18., 8.]])
sage: a3 = matrix([[-2., -8.], [-8., 1.]])
sage: a4 = matrix([[33., -9.], [-9., 26.]])
sage: b1 = matrix([[-21., -11., 0.], [-11., 10., 8.], [0.,   8., 5.]])
sage: b2 = matrix([[0.,  10.,  16.], [10., -10., -10.], [16., -10., 3.]])
sage: b3 = matrix([[-5.,   2., -17.], [2.,  -6.,   8.], [-17.,  8., 6.]])
sage: b4 = matrix([[14., 9., 40.], [9., 91., 10.], [40., 10., 15.]])
sage: p.add_constraint(a1*x[0] + a2*x[1] + a3*x[2] <= a4)
sage: p.add_constraint(b1*x[0] + b2*x[1] + b3*x[2] <= b4)
sage: N(p.solve(), digits=4)
-3.154

Python

>>> from sage.all import *
>>> p = SemidefiniteProgram(solver="cvxopt", maximization=False)
>>> x = p.new_variable()
>>> p.set_objective(x[Integer(0)] - x[Integer(1)] + x[Integer(2)])
>>> a1 = matrix([[-RealNumber('7.'), -RealNumber('11.')], [-RealNumber('11.'), RealNumber('3.')]])
>>> a2 = matrix([[RealNumber('7.'), -RealNumber('18.')], [-RealNumber('18.'), RealNumber('8.')]])
>>> a3 = matrix([[-RealNumber('2.'), -RealNumber('8.')], [-RealNumber('8.'), RealNumber('1.')]])
>>> a4 = matrix([[RealNumber('33.'), -RealNumber('9.')], [-RealNumber('9.'), RealNumber('26.')]])
>>> b1 = matrix([[-RealNumber('21.'), -RealNumber('11.'), RealNumber('0.')], [-RealNumber('11.'), RealNumber('10.'), RealNumber('8.')], [RealNumber('0.'),   RealNumber('8.'), RealNumber('5.')]])
>>> b2 = matrix([[RealNumber('0.'),  RealNumber('10.'),  RealNumber('16.')], [RealNumber('10.'), -RealNumber('10.'), -RealNumber('10.')], [RealNumber('16.'), -RealNumber('10.'), RealNumber('3.')]])
>>> b3 = matrix([[-RealNumber('5.'),   RealNumber('2.'), -RealNumber('17.')], [RealNumber('2.'),  -RealNumber('6.'),   RealNumber('8.')], [-RealNumber('17.'),  RealNumber('8.'), RealNumber('6.')]])
>>> b4 = matrix([[RealNumber('14.'), RealNumber('9.'), RealNumber('40.')], [RealNumber('9.'), RealNumber('91.'), RealNumber('10.')], [RealNumber('40.'), RealNumber('10.'), RealNumber('15.')]])
>>> p.add_constraint(a1*x[Integer(0)] + a3*x[Integer(2)] <= a4)
>>> p.add_constraint(b1*x[Integer(0)] + b2*x[Integer(1)] + b3*x[Integer(2)] <= b4)
>>> N(p.solve(), digits=Integer(4))
-3.225
>>> p = SemidefiniteProgram(solver="cvxopt", maximization=False)
>>> x = p.new_variable()
>>> p.set_objective(x[Integer(0)] - x[Integer(1)] + x[Integer(2)])
>>> a1 = matrix([[-RealNumber('7.'), -RealNumber('11.')], [-RealNumber('11.'), RealNumber('3.')]])
>>> a2 = matrix([[RealNumber('7.'), -RealNumber('18.')], [-RealNumber('18.'), RealNumber('8.')]])
>>> a3 = matrix([[-RealNumber('2.'), -RealNumber('8.')], [-RealNumber('8.'), RealNumber('1.')]])
>>> a4 = matrix([[RealNumber('33.'), -RealNumber('9.')], [-RealNumber('9.'), RealNumber('26.')]])
>>> b1 = matrix([[-RealNumber('21.'), -RealNumber('11.'), RealNumber('0.')], [-RealNumber('11.'), RealNumber('10.'), RealNumber('8.')], [RealNumber('0.'),   RealNumber('8.'), RealNumber('5.')]])
>>> b2 = matrix([[RealNumber('0.'),  RealNumber('10.'),  RealNumber('16.')], [RealNumber('10.'), -RealNumber('10.'), -RealNumber('10.')], [RealNumber('16.'), -RealNumber('10.'), RealNumber('3.')]])
>>> b3 = matrix([[-RealNumber('5.'),   RealNumber('2.'), -RealNumber('17.')], [RealNumber('2.'),  -RealNumber('6.'),   RealNumber('8.')], [-RealNumber('17.'),  RealNumber('8.'), RealNumber('6.')]])
>>> b4 = matrix([[RealNumber('14.'), RealNumber('9.'), RealNumber('40.')], [RealNumber('9.'), RealNumber('91.'), RealNumber('10.')], [RealNumber('40.'), RealNumber('10.'), RealNumber('15.')]])
>>> p.add_constraint(a1*x[Integer(0)] + a2*x[Integer(1)] + a3*x[Integer(2)] <= a4)
>>> p.add_constraint(b1*x[Integer(0)] + b2*x[Integer(1)] + b3*x[Integer(2)] <= b4)
>>> N(p.solve(), digits=Integer(4))
-3.154

solver_parameter(name, value=None)[source]#

Return or define a solver parameter

INPUT:

name (string) – the parameter
value – the parameter’s value if it is to be defined, or None (default) to obtain its current value.

Note

The list of available parameters is available at solver_parameter().

EXAMPLES:

Sage

sage: from sage.numerical.backends.generic_sdp_backend import get_solver
sage: p = get_solver(solver="CVXOPT")
sage: p.solver_parameter("show_progress")
False
sage: p.solver_parameter("show_progress", True)
sage: p.solver_parameter("show_progress")
True

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_sdp_backend import get_solver
>>> p = get_solver(solver="CVXOPT")
>>> p.solver_parameter("show_progress")
False
>>> p.solver_parameter("show_progress", True)
>>> p.solver_parameter("show_progress")
True