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 where c is a variable index (integer) and v 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 name

INPUT:

  • index (integer) – the col’s id
  • name (char *) – its name. When set to NULL (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 id
  • coeff (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 to NULL (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) where indices lists the entries whose coefficient is nonzero, and to which coeffs associates their coefficient on the model of the add_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 name

INPUT:

  • 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 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().

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