CVXOPT SDP Backend¶
AUTHORS:
- Ingolfur Edvardsson (2014-05) : initial implementation
- Dima Pasechnik (2015-12) : minor fixes
-
class
sage.numerical.backends.cvxopt_sdp_backend.
CVXOPTSDPBackend
¶ Bases:
sage.numerical.backends.generic_sdp_backend.GenericSDPBackend
-
add_linear_constraint
(coefficients, name=None)¶ Add a linear constraint.
INPUT:
coefficients
an iterable with(c,v)
pairs wherec
is a variable index (integer) andv
is a value (matrix). The pairs come sorted by indices. If c is -1 it represents the constant coefficient.name
- an optional name for this row (default:None
)
EXAMPLE:
sage: from sage.numerical.backends.generic_sdp_backend import get_solver sage: p = get_solver(solver = "CVXOPT") sage: p.add_variables(2) 1 sage: p.add_linear_constraint( [(0, matrix([[33., -9.], [-9., 26.]])) , (1, matrix([[-7., -11.] ,[ -11., 3.]]) )]) sage: p.row(0) ([0, 1], [ [ 33.0000000000000 -9.00000000000000] [-9.00000000000000 26.0000000000000], <BLANKLINE> [-7.00000000000000 -11.0000000000000] [-11.0000000000000 3.00000000000000] ]) sage: p.add_linear_constraint( [(0, matrix([[33., -9.], [-9., 26.]])) , (1, matrix([[-7., -11.] ,[ -11., 3.]]) )],name="fun") sage: p.row_name(-1) 'fun'
-
add_linear_constraints
(number, names=None)¶ Add constraints.
INPUT:
number
(integer) – the number of constraints to add.names
- an optional list of names (default:None
)
EXAMPLE:
sage: from sage.numerical.backends.generic_sdp_backend import get_solver sage: p = get_solver(solver = "CVXOPT") sage: p.add_variables(5) 4 sage: p.add_linear_constraints(5) sage: p.row(4) ([], [])
-
add_variable
(obj=0.0, name=None)¶ Add a variable.
This amounts to adding a new column of matrices to the matrix. By default, the variable is both positive and real.
INPUT:
obj
- (optional) coefficient of this variable in the objective function (default: 0.0)name
- an optional name for the newly added variable (default:None
).
OUTPUT: The index of the newly created variable
EXAMPLE:
sage: from sage.numerical.backends.generic_sdp_backend import get_solver sage: p = get_solver(solver = "CVXOPT") sage: p.ncols() 0 sage: p.add_variable() 0 sage: p.ncols() 1 sage: p.add_variable() 1 sage: p.add_variable(name='x',obj=1.0) 2 sage: p.col_name(2) 'x' sage: p.objective_coefficient(2) 1.00000000000000
-
add_variables
(n, names=None)¶ Add
n
variables.This amounts to adding new columns to the matrix. By default, the variables are both positive and real.
INPUT:
n
- the number of new variables (must be > 0)names
- optional list of names (default:None
)
OUTPUT: The index of the variable created last.
EXAMPLE:
sage: from sage.numerical.backends.generic_sdp_backend import get_solver sage: p = get_solver(solver = "CVXOPT") sage: p.ncols() 0 sage: p.add_variables(5) 4 sage: p.ncols() 5 sage: p.add_variables(2, names=['a','b']) 6
-
col_name
(index)¶ Return the
index
th col nameINPUT:
index
(integer) – the col’s idname
(char *
) – its name. When set toNULL
(default), the method returns the current name.
EXAMPLE:
sage: from sage.numerical.backends.generic_sdp_backend import get_solver sage: p = get_solver(solver = "CVXOPT") sage: p.add_variable(name="I am a variable") 0 sage: p.col_name(0) 'I am a variable'
-
dual_variable
(i, sparse=False)¶ 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
EXAMPLE:
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
TESTS:
sage: B.dual_variable(7) ... Traceback (most recent call last): ... IndexError: list index out of range sage: abs(g - B._get_answer()['gap']) # tol 1e-22 0.0
-
get_matrix
()¶ Get a block of a matrix coefficient
EXAMPLE:
sage: p = SemidefiniteProgram(solver="cvxopt") sage: x = p.new_variable() sage: a1 = matrix([[1, 2.], [2., 3.]]) sage: a2 = matrix([[3, 4.], [4., 5.]]) sage: p.add_constraint(a1*x[0] + a2*x[1] <= a1) sage: b = p.get_backend() sage: b.get_matrix()[0][0] ( [-1.0 -2.0] -1, [-2.0 -3.0] )
-
get_objective_value
()¶ Return the value of the objective function.
Note
Behaviour is undefined unless
solve
has been called before.EXAMPLE:
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: round(p.solve(),3) -3.154 sage: round(p.get_backend().get_objective_value(),3) -3.154
-
get_variable_value
(variable)¶ Return the value of a variable given by the solver.
Note
Behaviour is undefined unless
solve
has been called before.EXAMPLE:
sage: from sage.numerical.backends.generic_sdp_backend import get_solver sage: p = get_solver(solver = "cvxopt") 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: round(p.solve(),3) -3.154 sage: round(p.get_backend().get_variable_value(0),3) -0.368 sage: round(p.get_backend().get_variable_value(1),3) 1.898 sage: round(p.get_backend().get_variable_value(2),3) -0.888
-
is_maximization
()¶ Test whether the problem is a maximization
EXAMPLE:
sage: from sage.numerical.backends.generic_sdp_backend import get_solver sage: p = get_solver(solver = "CVXOPT") sage: p.is_maximization() True sage: p.set_sense(-1) sage: p.is_maximization() False
-
ncols
()¶ Return the number of columns/variables.
EXAMPLE:
sage: from sage.numerical.backends.generic_sdp_backend import get_solver sage: p = get_solver(solver = "CVXOPT") sage: p.ncols() 0 sage: p.add_variables(2) 1 sage: p.ncols() 2
-
nrows
()¶ Return the number of rows/constraints.
EXAMPLE:
sage: from sage.numerical.backends.generic_sdp_backend import get_solver sage: p = get_solver(solver = "CVXOPT") sage: p.nrows() 0 sage: p.add_variables(5) 4 sage: p.add_linear_constraints(2) sage: p.nrows() 2
-
objective_coefficient
(variable, coeff=None)¶ Set or get the coefficient of a variable in the objective function
INPUT:
variable
(integer) – the variable’s idcoeff
(double) – its coefficient
EXAMPLE:
sage: from sage.numerical.backends.generic_sdp_backend import get_solver sage: p = get_solver(solver = "CVXOPT") sage: p.add_variable() 0 sage: p.objective_coefficient(0) 0.0 sage: p.objective_coefficient(0,2) sage: p.objective_coefficient(0) 2.0
-
problem_name
(name='NULL')¶ Return or define the problem’s name
INPUT:
name
(char *
) – the problem’s name. When set toNULL
(default), the method returns the problem’s name.
EXAMPLE:
sage: from sage.numerical.backends.generic_sdp_backend import get_solver sage: p = get_solver(solver = "CVXOPT") sage: p.problem_name("There once was a french fry") sage: print(p.problem_name()) There once was a french fry
-
row
(i)¶ Return a row
INPUT:
index
(integer) – the constraint’s id.
OUTPUT:
A pair
(indices, coeffs)
whereindices
lists the entries whose coefficient is nonzero, and to whichcoeffs
associates their coefficient on the model of theadd_linear_constraint
method.EXAMPLE:
sage: from sage.numerical.backends.generic_sdp_backend import get_solver sage: p = get_solver(solver = "CVXOPT") sage: p.add_variables(5) 4 sage: p.add_linear_constraint( [(0, matrix([[33., -9.], [-9., 26.]])) , (1, matrix([[-7., -11.] ,[ -11., 3.]]) )]) sage: p.row(0) ([0, 1], [ [ 33.0000000000000 -9.00000000000000] [-9.00000000000000 26.0000000000000], <BLANKLINE> [-7.00000000000000 -11.0000000000000] [-11.0000000000000 3.00000000000000] ])
-
row_name
(index)¶ Return the
index
th row nameINPUT:
index
(integer) – the row’s id
EXAMPLE:
sage: from sage.numerical.backends.generic_sdp_backend import get_solver sage: p = get_solver(solver = "CVXOPT") sage: p.add_linear_constraints(1, names="A") sage: p.row_name(0) 'A'
-
set_objective
(coeff, d=0.0)¶ Set the objective function.
INPUT:
coeff
– a list of real values, whose ith element is the coefficient of the ith variable in the objective function.d
(double) – the constant term in the linear function (set to \(0\) by default)
EXAMPLE:
sage: from sage.numerical.backends.generic_sdp_backend import get_solver sage: p = get_solver(solver = "CVXOPT") sage: p.add_variables(5) 4 sage: p.set_objective([1, 1, 2, 1, 3]) sage: [p.objective_coefficient(x) for x in range(5)] [1, 1, 2, 1, 3]
-
set_sense
(sense)¶ Set the direction (maximization/minimization).
INPUT:
sense
(integer) :- +1 => Maximization
- -1 => Minimization
EXAMPLE:
sage: from sage.numerical.backends.generic_sdp_backend import get_solver sage: p = get_solver(solver = "CVXOPT") sage: p.is_maximization() True sage: p.set_sense(-1) sage: p.is_maximization() False
-
slack
(i, sparse=False)¶ 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
EXAMPLE:
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 = 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]
TESTS:
sage: B.slack(7) ... Traceback (most recent call last): ... IndexError: list index out of range
-
solve
()¶ Solve the problem.
Note
This method raises
SDPSolverException
exceptions when the solution can not be computed for any reason (none exists, or the LP solver was not able to find it, etc...)EXAMPLE:
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: round(p.solve(), 3) -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: round(p.solve(), 3) -3.154
-
solver_parameter
(name, value=None)¶ 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()
.EXAMPLE:
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
-