API reference

Block(l::Any[, r::Int, s::Int])

Specifies a block corresponding to the positive semidefinite variable l.

Specifying r,s makes the Block correspond to the r,s subblock of the variable l.

ClusteredLowRankSDP(problem::Problem; prec=precision(BigFloat), verbose=false)

Define a ClusteredLowRankSDP based on problem.

Keyword arguments:

• prec (default: precision(BigFloat)): the precision of the result
• verbose (default: false): print progress to the standard output

Constraint(constant, matrixcoeff, freecoeff[, samples, scalings])

Models a polynomial constaint of the form

\[ ∑_i ⟨ A_i(x), Y_i ⟩ + ∑_j b_j(x) y_j = c(x)\]

using sampling on samples. Here the samples are only required if $A_i$, $b_j$, and $c$ are polynomials. When the coefficient matrix $A_i$ has block structure with equal sized blocks, the Block struct can be used as key to indicate to which subblock the given matrix corresponds.

Arguments:

• constant: The right hand side $c(x)$
• matrixcoeff::Dict: The coefficient matrices for the positive semidefinite matrix variables.
• freecoeff::Dict: The coefficients for the free variables.
• samples::Vector: The sample set on which the constraint should be satisfied. Required for polynomial constraints.
• scalings::Vector: Optional; scale the constraint with a factor depending on the sample index.

DualSolution{T}

A dual solution to the semidefinite program, with fields

• base_ring
• matrixvars::Dict{Any, Matrix{T}}
• freevars::Dict{Any, T}

LowRankMatPol(lambda::Vector, vs::Vector{Vector}[, ws::Vector{Vector}])

The matrix $∑_i λ_i v_i w_i^{\sf T}$ where $v_i$ are the entries of vs and $w_i$ the entries of ws

If ws is not specified, use ws = vs.

Maximize(obj)

Maximize the objective

Minimize(obj)

Minimize the objective

Objective(constant, matrixcoeff::Dict, freecoeff::Dict)

The objective for the Problem.

Arguments:

• constant: A constant offset of the objective value.
• matrixcoeff: A Dict with positive semidefinite matrix variable names as keys and the objective matrices as values.
• freecoeff: A Dict with free variable names as keys and the coefficients as values.

PrimalSolution{T}

A primal solution to the semidefinite program, with fields

• base_ring
• x::Vector{T}
• matrixvars::Dict{Any, Matrix{T}}

    Problem(maximize::Bool, objective::Objective, constraints::Vector{Constraint})

    Problem(obj::Union{Maximize, Minimize}, constraints::Vector)

Combine the objective and constraints into a low-rank polynomial problem.

RoundingSettings(settings...)

Settings for the rounding procedure:

1. Finding the kernel
   • kernel_errbound: (default: 1e-10) the allowed error for the kernel vectors. That is, the maximum entry of Xv is in absolute value at most this
   • kernel_round_errbound: (default: 1e-15) the maximum allowed error when rounding the reduced row-echelon form entrywise
   • kernel_use_primal: (default: true) use the primal solution to find the kernel vectors (otherwise, use an SVD of the dual solution)
   • kernel_lll: (default: false) if true, use the LLL algorithm to find the nullspace of the kernel. Otherwise, use the reduced row-echelon form to find kernel vectors.
   • kernel_bits: (default: 1000) the maximum number of bits to be used in the LLL algorithm (for finding relations or finding the entries of the RREF)
2. Reducing the kernel vectors
   • reduce_kernelvectors: (default: true) apply the reduction step or not
   • reduce_kernelvectors_cutoff: (default: 400) do reduction on the full matrix if its size is at most this cutoff. Otherwise do it on a submatrix
   • reduce_kernelvectors_stepsize: (default: 200) the number of extra columns to take into account in each iteration of the reduction step
3. Transforming the problem and the solution
   • unimodular_transform: (default: true) use a unimodular transform obtained in the reduction step
   • normalize_transformation: (default: true) multiply by a diagonal matrix to get an integer transformation for the problem (for problems over QQ)
4. Finding an approximate solution in the field
   • regularization: (default: 1e-20) use this regularization for solving the extended system
   • approximation_decimals: (default: 40) Approximate the numerical solution using this many digits, entrywise
5. Rounding the solution to the affine space of constraints
   • redundancyfactor: (default: 10) take at least this times the number of constraints columns as potential pivots
   • pseudo: (default: true) use the psuedo inverse for rounding (this may give solutions with larger bitsize than needed)
   • pseudo_columnfactor: (default: 1.05) For a system of r rows, use r * pseudo_columnfactor number of columns for the pseudo inverse
   • extracolumns_linindep: (default: false) if true, take the extra columns linearly independent of each other (otherwise, random columns)

SampledMPolyRing(base_ring, samples)

A sampled polynomial ring with evaluations in base_ring, only defined on the samples. The samples should be sorted.

SampledMPolyRinElem(parent::SampledMPolyRing, evaluations::Vector)

A sampled polynomial corresponding to the given parent, which evaluates to evaluations on the samples of the parent ring.

SolverFailure(msg)

An error in the solver, with a message.

addconstraint!(problem, constraint)

Add constraint to the constraints of problem.

approximatefekete(basis, samples; base_ring=BigFloat) -> basis, samples

Compute approximate fekete points based on samples and a corresponding orthogonal basis. The basis consists of sampled polynomials, sampled at samples.

This preserves a degree ordering of basis if present.

approximatefeketeexact(R, basis, samples)

Apply approximate fekete but return an exact basis transformation.

as_dual_solution(sol, x)

Undo the vectorization of x.

basic_embedding(exactvalue)

Convert the exact (rational or integer) numbers to floating point approximations.

basis_chebyshev(d::Int,x)

Generate a basis of Chebyshev polynomials of the first kind up to degree d (inclusive).

basis_gegenbauer(d, n, x)

Basis for the Gegenbauer polynomials in dimension n up to degree d. This is the Gegenbauer polynomial with parameter lambda = n/2-1, or the Jacobi polynomial with alpha = beta = (n-3)/2. Normalized to evaluate to 1 at 1. Taken from arxiv/2001.00256, ancillary files, SemidefiniteProgramming.jl.

basis_jacobi(d::Integer, alpha, beta, x)

Generate the Jacobi polynomials with parameters alpha and beta up to degree d (inclusive).

basis_laguerre(d::Integer, alpha, x)

Generate the (generalized) Laguerre polynomials with parameter alpha up to degree d (inclusive).

basis_monomial(d::Int, x...)

Generate the monomial basis in variables x... up to degree d (inclusive).

blocksizes(problem)

Return the sizes of the matrix variables as a dictionary with the same keys

check_problem(problem::LowRankPolProblem)

Check for obvious mistakes in the constraints and objective

check_sdp!(sdp::ClusteredLowRankSDP)

Check whether the constraint matrices are symmetric, and remove empty constraint matrices.

constraints(problem::Problem)

Return the constraints of problem.

convert_to_prec(sdp, prec=precision(BigFloat))

Convert the semidefinite program to a semidefinite program with prec bits of precision, without error bounds.

exact_solution(problem::Problem, primalsol::PrimalSolution, dualsol::DualSolution; transformed=false, FF = QQ, g=1, settings::RoundingSettings=RoundingSettings(), monomial_bases=nothing)

Compute and return an exact solution to the problem, given a primal solution, dual solution and a field FF with approximate generator g. Return (success, exactdualsol) if transformed=false, and (success, pd_transformed_exactsolution, transformations) if transformed=true.

find_field(primalsol, dualsol, max_degree=4; valbound=1e-15, errbound=1e-15, bits=100, max_coeff=1000)

Heuristically find a field over which the kernel can probably be defined.

Only consider values at least valbound in absolute value. Find minimal polynomials such that the chosen entries are approximately generators with an error bound of errbound. Use bits number of bits and reject minimal polynomials with a maximum coefficient of more than max_coeff.

freecoeff(x::Union{Constraint, Objective}, name)

Return the coefficient of the free variable corresponding to name

freecoeffs(x::Union{Constraint, Objective})

Return the dictionary of coefficients for the free variables

freevar(sol, name)

Return the free variable corresponding to name

freevars(sol)

Return the dictionary of the free variables

generic_embedding(exactvalue, g; base_ring=BigFloat)

Convert the exact numbers from a number field to floating point approximations, using a floating point approximation of a generator g of the field.

Convert rationals and integers to the same numbers in base_ring.

linearsystem(problem::Problem, FF=QQ)

Let x be the vcat of the vectorizations of the matrix variables. This function returns the matrix A and vector b such that the constraints are given by the system Ax = b (over the field FF).

linearsystem_coefficientmatching(problem::Problem, monomial_basis::Vector{Vector{MPolyRingElem}}; FF=QQ)

Let x be the vcat of the vectorizations of the matrix variables. This function returns the matrix A and vector b such that the constraints obtained from coefficient matching are given by the system Ax = b over the field FF, with one constraint per monomial in monomial_basis. The problem should not contain SampledMPolyRingElem's for this to work.

matrixcoeff(x::Union{Constraint, Objective}, name)

Return the matrix coefficient corresponding to name

matrixcoeffs(x::Union{Constraint, Objective})

Return the dictionary of matrix coefficients

matrixvar(sol, name)

Return the matrix variable corresponding to name

matrixvars(sol)

Return the dictionary of matrix variables

model_psd_variables_as_free_variables!(problem::Problem, as_free)

Model the positive semidefinite variables with names in as_free using free variables, and add extra constraints to set them equal to auxilliary positive semidefinite variables.

objective(x::Union{Maximize, Minimize, Problem})

Return the objective.

objvalue(problem::Problem, sol::DualSolution)

Return the objective value of the dual solution with respect to the given objective or problem.

objvalue(objective::Objective, sol::DualSolution)

optimal(x::Status)

Return whether the solutions corresponding to this status are optimal.

partial_linearsystem(problem::Problem, sol::DualSolution, columns::Union{DualSolution, Vector{Int}})

Let x be the vcat of the vectorizations of the matrix variables. Let I be the index set of the columns. This function returns the matrix AI and vector b-Ax such that the constraints for the error vector e using variables indexed by I are given by the system AIe = b-Ax.

sample_points_chebyshev(d, a = -1, b = 1; T=BigFloat) -> Vector{T}

Generate the d+1 Chebyshev points in [a,b].

sample_points_chebyshev_mod(d, a = -1, b = 1; T=BigFloat) -> Vector{T}

Generate the d+1 modified chebyshev points in [a,b], the chebyshev points divided by cos(pi/(2(d+1))).

sample_points_padua(d; T=BigFloat) -> Vector{Vector{T}}

Generate the Padua points for degree d.

sample_points_rescaled_laguerre(d; T=BigFloat) -> Vector{T}

Generate 'rescaled laguerre' points, as in SDPB.

sample_points_simplex(n, d; T=BigFloat) -> Vector{Vector{T}}

Generate the rational sample points in the unit simplex with denominator d.

sampled_polynomial_ring(base_ring, samples)

Create a SampledMPolyRing with values in base_ring defined on samples. The samples should be sorted.

sdpa_sparse_to_problem(filename,obj_shift = 0; T=Float64)

Define the Problem from the file filename assuming it is in SDPA sparse format, using the number type T. Optionally add an objective shift.

slacks(problem, dualsol)

Compute the difference between the left hand side and the right hand side of all constraints

	solvesdp(problem::Problem; kwargs...)

    solvesdp(sdp::ClusteredLowRankSDP; kwargs...)

Solve the semidefinite program generated from problem or sdp.

Keyword arguments:

• prec (default: precision(BigFloat)): the precision used
• gamma (default: 0.9): the step length reduction; a maximum step length of α reduces to a step length of max(gamma*α,1)
• beta_(in)feasible (default: 0.1 (0.3)): the amount mu is tried to be reduced by in each iteration, for (in)feasible solutions
• omega_p/d (default: 10^10): the starting matrix variable for the primal/dual is omega_p/d*I
• maxiterations (default: 500): the maximum number of iterations
• duality_gap_threshold (default: 10^-15): how near to optimal the solution needs to be
• primal/dual_error_threshold (default:10^-30): how feasible the primal/dual solution needs to be
• max_complementary_gap (default: 10^100): the maximum of dot(X,Y)/nrows(X) allowed
• need_primal_feasible/need_dual_feasible (default: false): terminate when the solution is primal/dual feasible
• verbose (default: true): print information after every iteration if true
• step_length_threshold (default: 10^-7): the minimum step length allowed
• primalsol (default: nothing): start from the solution (primalsol, dualsol) if both primalsol and dualsol are given
• dualsol (default: nothing): start from the solution (primalsol, dualsol) if both primalsol and dualsol are given
• safe_step (default: true): use only 'safe' steps with step length at most 1, and take alphap = alphad when the the solution is primal and dual feasible

to_field(v, N, g; bits=100, errbound=1e-15)

Find an approximation of v in the number field N, using the approximate generator g of N.

vectorize(sol)

Vectorize the solution by taking the upper triangular part of the matrices. The variables are first sorted by size and then by hash.