Docstrings

BarrierAlg(sub_alg)

A meta-algorithm that handles inequality, bound and semidefinite constraints using a primal log-barrier approach. The barrier coefficient is decayed across a sequence of sub-problems (see BarrierOptions) and each sub-problem is solved with sub_alg, which must handle the constraints that are not barrierified. SDPBarrierAlg is an alias.

BarrierOptions(; kwargs...)

The keyword arguments which can be specified are:

• c_init: (default 1.0) initial value for the barrier coefficient, a real number or a vector with one entry per barrierified constraint group.
• c_decr: (default 0.1) decreasing rate (< 1) multiplying the barrier coefficient every iteration, a real number or a vector.
• n_iter: (default 20) maximum number of sub-problems to solve.
• sub_options: options for the sub-problem's solver.
• keep_all: (default false) if set to true, the result stores the sub-problem results from all the iterations.
• barrier: a BarrierSelection (default: barrierify the semidefinite constraints only).
• adaptive: (default false) decay the barrier coefficient with a superlinear schedule targeting tol within n_iter iterations instead of the fixed c_decr factor.
• tol: (default nothing) stop early when the estimated duality gap c ⋅ m (barrier coefficient times the number of barrier terms) falls below this value.

BarrierResult

Alias of SDPBarrierResult.

BarrierSelection(; ineq = false, box = false, sd = true)

Selects which constraint kinds are converted to barrier terms by BarrierAlg. Each entry is true (all constraints of that kind), false (none) or a vector of constraint indices (those only). Equality constraints can never be barrierified and are always kept for the sub-solver.

The default selects semidefinite constraints only, preserving the historical SDPBarrierAlg behaviour; pass BarrierSelection(ineq = true, box = true) to barrierify inequalities and variable bounds as well.

BlockSDConstraint

A semidefinite constraint whose function returns a vector of matrices (one per block) from a single evaluation. chordal_decompose uses it to evaluate the matrix-valued function once and slice every clique block from that single evaluation instead of re-evaluating it per clique.

The function must return a Vector (or tuple) of symmetric matrices of sizes dims.

PSDMatrixView(offset, dim)

A view of an dim×dim positive semidefinite matrix variable added to a model with add_psd_variable!. Calling M(x) decompresses the symmetric matrix from x using decompress_symmetric:

• if length(x) == nvars(M), x is the variable chunk [x_L; x_D] itself;
• otherwise x is the full flattened variable vector and the chunk is read at the offset recorded when the variable was added.

SDPBarrierAlg(sub_alg)

Alias of BarrierAlg. Historically the barrier meta-algorithm only handled semidefinite constraints; the generalized BarrierAlg now also barrierifies inequalities and variable bounds, selected through BarrierSelection. Both names construct the same meta-algorithm.

SDPBarrierOptions(; kwargs...)

Alias of BarrierOptions (all keyword arguments are shared).

SDPBarrierResult

The result of BarrierAlg (or its alias SDPBarrierAlg) with fields:

• minimum: the best objective value over the sub-problem sequence.
• minimizer: the minimizer attaining minimum.
• results: if keep_all = true in BarrierOptions, the full sub-problem trajectory as a vector of (objective, minimizer) pairs; nothing otherwise.
• optimal_ind: if keep_all = true, the index of the best sub-problem result in results; nothing otherwise.

SDPQuadAlg(sub_alg)

Meta-algorithm eliminating semidefinite constraints through quadratic re-parameterization. Every semidefinite constraint of the model must be a decompress_symmetric-style matrix variable chunk in the (x_L, x_D) layout, and the model variables must consist exactly of those chunks. The re-parameterized problem is solved with sub_alg.

SDPQuadOptions(; sub_options, rank = nothing, diag_floor = 1e-6)

Options of SDPQuadAlg: rank = nothing selects the full-rank Cholesky re-parameterization A = L Lᵀ (with diag(L) ≥ diag_floor bounds); rank = r selects the Burer-Monteiro low-rank re-parameterization A = R Rᵀ with R ∈ R^{n×r}.

SDPQuadResult

The result of SDPQuadAlg with fields:

• minimum: the objective value at the minimizer.
• minimizer: the minimizer in the (x_L, x_D) variable layout of the original model, i.e. the decompressed entries of the re-parameterized factor variables.

add_psd_variable!(model, dim; init = I(dim))

Add the variables of a symmetric dim×dim positive semidefinite matrix to the model as one chunk in the (x_L, x_D) layout (the strict lower-triangular entries followed by the diagonal), with the diagonal constrained to be non-negative. Returns a PSDMatrixView that decompresses the matrix from a variable vector.

model = Model()
M = add_psd_variable!(model, 3)
model.objective = x -> -loglikelihood(MvNormal(μ, M(x[1])), samples)

aggregate_sparsity(f, x0::AbstractVector, dim::Int)

Structural sparsity pattern of the matrix-valued function f (returning a dim×dim matrix) at x0, computed with reverse-mode AD: entry (i, j) is structurally nonzero if f(x)[i, j] depends on any variable.

chordal_decompose(model::VecModel, patterns; x0 = nothing)
chordal_decompose(model::VecModel; x0)

Replace each semidefinite constraint P(x) ⪰ 0 of model with a single BlockSDConstraint whose function evaluates P once and returns every maximal-clique submatrix P(x)[C, C] of a chordal extension of the constraint's sparsity pattern. The two models are equivalent (Grone-Johnson-Sá-Wolkowicz).

patterns is a vector with one sparsity pattern per semidefinite constraint (or a single pattern when the model has one constraint). Entries may be nothing to probe the sparsity of the constraint at x0 (the union of the structural AD dependence pattern and the numerical support of P(x0)).

If x0 is provided, every nonzero entry of P(x0) must lie inside the pattern, otherwise an error is thrown: sparsity exploitation is only valid when the pattern covers all entries the constraint can have.

chordal_extension(pattern::SparseMatrixCSC)

Chordal extension of the graph of the sparsity pattern, computed with a sparse Cholesky factorization (AMD ordering). Returns the maximal cliques of the extended graph as a vector of index vectors in the original vertex ordering. Each clique is fully connected in pattern, so symmetric_pattern(pattern) restricted to any clique is dense.

decompress_symmetric

For example: a 3*3 positive semidefinite matrix: [ a b d; b c e; d e f ] represents by: [ x_D[1] x_L[3] x_L[2]; x_L[1] x_D[2] x_L[1]; x_L[2] x_L[3] x_D[3] ]

• x_L::AbstractArray: representing lower triangular part of a n*n matrix, length should be (n^2-n)÷2
• x_D::AbstractArray: representing diagonal part of a n*n matrix, length should be n

project_psd(A::AbstractMatrix)

Orthogonal projection of the symmetric part of A onto the cone of positive semidefinite matrices. If A = U Λ Uᵀ is a symmetric eigendecomposition, the projection is U max(Λ, 0) Uᵀ.

project_psd_neg(A::AbstractMatrix)

Orthogonal projection of the symmetric part of A onto the cone of negative semidefinite matrices, computed via the Moreau decomposition Π_{S₋ⁿ}(A) = A - Π_{S₊ⁿ}(A).

psd_infeasibility(P::AbstractMatrix)

Distance of the symmetric part of P from the cone of positive semidefinite matrices, i.e. ‖Π_{S₋ⁿ}(P)‖_F (the Frobenius norm of the negative eigenvalues). Returns 0 if and only if P is positive semidefinite.

symmetric_pattern(pattern::SparseMatrixCSC)

Symmetrized structural sparsity pattern of pattern, augmented with the diagonal.

to_barrier(model, c; selection = BarrierSelection(ineq = false, box = false, sd = true), ε = 1e-6)

Build the sub-model of the barrier method: the selected constraints are removed and encoded in the log-barrier objective (with coefficient vector c, one entry per selected constraint group). The default selection matches the historical SDPBarrierAlg behaviour (semidefinite constraints only).