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: from sage.numerical.backends.generic_sdp_backend import get_solver sage: p = get_solver(solver='CVXOPT')
>>> 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: 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
>>> 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: 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
>>> 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: 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
>>> 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: 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]
>>> 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: 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
>>> 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 parametervalue
– the parameter’s value if it is to be defined, orNone
(default) to obtain its current value
Note
The list of available parameters is available at
solver_parameter()
.EXAMPLES:
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
>>> 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