ADMMIterations()

The number of ADMM iterations completed during the solve.

Absctract supertype for accelerator activation.

AbstractComplexityWeight

A supertype for weights that are based on the complexity of clique-related operations in the solver algorithm.

All subtypes have to define the function: compute_complexity_savings(n_1::Int, n_2::Int, n_m::Int, edge_weight::Subtype) --> Float64

with

• n1: `|C1|`
• n2: `|C2|`
• n3: `|C1 ∪ C_2|`

AbstractEdgeWeight

A supertype for the weights that are put on the edges of the clique graph.

AbstractGraphBasedMerge

An abstract supertype for merge strategies that work with the reduced clique graph.

AbstractMergeStrategy

An abstract supertype for merge strategies.

A merge strategy determines how the cliques in a clique tree / clique graph are merged to improve computation time of the projection. Each merge strategy should implement the following functions:

• initialise!: Initialise the graph / tree from the input clique graph / tree, allocate memory
• traverse: A method that determines how the clique tree / graph is traversed
• evaluate: A method that decides whether to merge two cliques
• update_strategy!: A method to update local strategy-related information after a merge

AbstractTreeBasedMerge

An abstract supertype for merge strategies that work with the clique tree.

Activate accelerator after accuracy of main algorithm <= start_accuracy.

Box(l, u)

Creates a box or intervall with lower boundary vector $l \in \mathbb{R}^m \cup \{-\infty\}^m$ and upper boundary vector$u \in \mathbb{R}^m\cup \{+\infty\}^m$.

CliqueGraphMerge(edge_weight::AbstractEdgeWeight = ComplexityWeight()) <: AbstractGraphBasedMerge

The (default) merge strategy based on the reduced clique graph $\mathcal{G}(\mathcal{B}, \xi)$, for a set of cliques $\mathcal{B} = \{ \mathcal{C}_1, \dots, \mathcal{C}_p\}$ where the edge set $\xi$ is obtained by taking the edges of the union of clique trees.

Moreover, given an edge weighting function $e(\mathcal{C}_i,\mathcal{C}_j) = w_{ij}$, we compute a weight for each edge that quantifies the computational savings of merging the two cliques. After the initial weights are computed, we merge cliques in a loop:

while clique graph contains positive weights:

• select two permissible cliques with the highest weight $w_{ij}$
• merge cliques $\rightarrow$ update clique graph
• recompute weights for updated clique graph

Custom edge weighting functions can be used by defining your own CustomEdgeWeight <: AbstractEdgeWeight and a corresponding edge_metric method. By default, the ComplexityWeight <: AbstractEdgeWeight is used which computes the weight based on the cardinalities of the cliques: $e(\mathcal{C}_i,\mathcal{C}_j) = |\mathcal{C}_i|^3 + |\mathcal{C}_j|^3 - |\mathcal{C}_i \cup \mathcal{C}_j|^3$.

See also: Garstka, Cannon, Goulart - A clique graph based merging strategy for decomposable SDPs (2019)

ComplexityWeight

An edge weight that approximates the computational savings from merging two cliques Ci and Cj by e(Ci, Cj) = |Ci|^3 + |Cj|^3 - |Ci ∪ Cj|^3.

Constraint{T <: AbstractFloat}(A, b, convex_set_type, dim = 0, indices = 0:0)

Creates a COSMO constraint: Ax + b ∈ convex_set.

By default the following convex set types are supported: ZeroSet, Nonnegatives, SecondOrderCone, PsdCone, PsdConeTriangle.

Examples

julia> COSMO.Constraint([1 0;0 1], zeros(2), COSMO.Nonnegatives)
Constraint
Size of A: (2, 2)
ConvexSet: COSMO.Nonnegatives{Float64}

For convex sets that require their own data, it is possible to pass the pass the instantiated object directly rather than the type name.

Examples

julia> COSMO.Constraint([1 0;0 1], zeros(2), COSMO.Box([-1.;-1.],[1.;1.]))
Constraint
Size of A: (2, 2)
ConvexSet: COSMO.Box{Float64}

The optional arguments dim and indices can be used to specify A and b for subparts of variable x. If x has dimension dim = 4, then x[2] and x[3] can be constrained to the zero cone in the following way:

Examples

julia> c = COSMO.Constraint([1 0;0 1], zeros(2), COSMO.ZeroSet, 4, 2:3)
Constraint
Size of A: (2, 4)
ConvexSet: COSMO.ZeroSet{Float64}

Notice that extra columns of A have been added automatically.

julia>Matrix(c.A)
2×4 Array{Float64,2}:
0.0  1.0  0.0  0.0
0.0  0.0  1.0  0.0

DualExponentialCone(MAX_ITERS::Int = 100, EXP_TOL = 1e-8)

Creates the dual exponential cone $\mathcal{K}^*_{exp} = \{(x, y, z) \mid x < 0, -xe^{y/x} \leq e^1 z \} \cup \{ (0,y,z) \mid y \geq 0, z \geq 0 \}$

DualPowerCone(alpha::Float64, MAX_ITERS::Int = 20, POW_TOL = 1e-8)

Creates the 3-d dual power cone $\mathcal{K}^*_{pow} = \{(u, v, w) \mid \left( \frac{u}{\alpha}\right)^\alpha \left( \frac{v}{1-\alpha}\right)^{(1-\alpha)} \geq \|w\|, u \geq 0, v \geq 0 \}$ with $0 < \alpha < 1$

ExponentialCone(MAX_ITERS = 100, EXP_TOL = 1e-8)

Creates the exponential cone $\mathcal{K}_{exp} = \{(x, y, z) \mid y \geq 0 ye^{x/y} ≤ z\} \cup \{ (x,y,z) \mid x \leq 0, y = 0, z \geq 0 \}$

Activate accelerator immediately.

Activate accelerator after start_iter iterations of the main algorithm.

	MergeLog

A struct to analyse the clique merges. Introduced for debugging purposes.

Model{T <: AbstractFloat}()

Initializes an empty COSMO model that can be filled with problem data using assemble!(model, P, q,constraints; [settings, x0, s0, y0]).

NoMerge <: AbstractMergeStrategy

A strategy that does not merge cliques.

Nonnegatives(dim)

Creates the nonnegative orthant $\{ x \in \mathbb{R}^{dim} : x \ge 0 \}$ of dimension dim.

ParentChildMerge(t_fill = 8, t_size = 8) <: AbstractTreeBasedMerge

The merge strategy suggested in Sun and Andersen - Decomposition in conic optimization with partially separable structure (2014). The initial clique tree is traversed in topological order and a clique $\mathcal{C}_\ell$ is greedily merged to its parent clique $\mathcal{C}_{par(\ell)}$ if at least one of the two conditions are met

• $(| \mathcal{C}_{par(\ell)}| -| \eta_\ell|) (|\mathcal{C}_\ell| - |\eta_\ell|) \leq t_{\text{fill}}$ (fill-in condition)
• $\max \left\{ |\nu_{\ell}|, |\nu_{par(\ell)}| \right\} \leq t_{\text{size}}$ (supernode size condition)

PowerCone(alpha::Float64, MAX_ITERS::Int = 20, POW_TOL = 1e-8)

Creates the 3-d power cone $\mathcal{K}_{pow} = \{(x, y, z) \mid x^\alpha y^{(1-\alpha)} \geq \|z\|, x \geq 0, y \geq 0 \}$ with $0 < \alpha < 1$

PsdCone(dim)

Creates the cone of symmetric positive semidefinite matrices $\mathcal{S}_+^{dim}$. The entries of the matrix X are stored column-by-column in the vector x of dimension dim. Accordingly $X \in \mathbb{S}_+ \Rightarrow x \in \mathcal{S}_+^{dim}$, where $X = \text{mat}(x)$.

PsdConeTriangle(dim)

Creates the cone of symmetric positive semidefinite matrices. The entries of the upper-triangular part of matrix X are stored in the vector x of dimension dim. A $r \times r$ matrix has $r(r+1)/2$ upper triangular elements and results in a vector of $\mathrm{dim} = r(r+1)/2$.

Examples

The matrix

\[\begin{bmatrix} x_1 & x_2 & x_4\\ x_2 & x_3 & x_5\\ x_4 & x_5 & x_6 \end{bmatrix}\]

is transformed to the vector $[x_1, x_2, x_3, x_4, x_5, x_6]^\top$ with corresponding constraint PsdConeTriangle(6).

Result{T <: AbstractFloat}

Object returned by the COSMO solver after calling optimize!(model). It has the following fields:

ResultInfo{T <: AbstractFloat}

Object that contains further information about the primal residual, the dual residuals and the rho updates.

ResultTimes

Part of the Result object returned by the solver. ResultTimes contains timing results for certain parts of the algorithm:

By default COSMO only measures solver_time, setup_time and proj_time. To measure the other times set verbose_timing = true.

SecondOrderCone(dim)

Creates the second-order cone (or Lorenz cone) $\{ (t,x) \in \mathrm{R}^{dim} : || x ||_2 \leq t \}$.

COSMO.Settings{T}(; kwargs) where {T <: AbstractFloat}

Creates a COSMO settings object that is used to pass user settings to the solver.

SuperNodeTree

A structure to represent and analyse the sparsity pattern of the input matrix L.

Note:

Based on the merge_strategy in the constructor, SuperNodeTree might be initialised as a graph, i.e. seperators sep are left empty as well as snd_child and snd_post.

After cliques have been merged, a valid clique tree will be recomputed from the consolidated clique graph.

Workspace{T <: AbstractFloat}()

Initializes an empty COSMO model that can be filled with problem data using assemble!(model, P, q,constraints; [settings, x0, s0, y0]).

ZeroSet(dim)

Creates the zero set $\{ 0 \}^{dim}$ of dimension dim. If x ∈ ZeroSet then all entries of x are zero.

Depth first search on a hashtable H.

Given P, A, sigma and rho return the full KKT condition matrix K.

Given P, A, sigma and rho return the upper / lower triangle, defined by shape, of the KKT condition matrix K.

Count the number of nnz in each column of the lower triangle of the KKT matrix K.

Count the number of nnz in each column of the upper triangle of the KKT matrix K.

Determine and fill in the rowvals Ki and nzvals Kx of the lower triangle of K.

Determine and fill in the rowvals Ki and nzvals Kx of the upper triangle of K.

Check the dimensions of the problem data used to assemble the KKT matrix K.

acceleration_post!(accelerator, ws, num_iter, safeguarding_iter)

A function that the accelerator can use after the nominal ADMM operator step.

In the case of an Anderson Accelerator this is used to check the quality of the accelerated candidate vector and take measures if the vector is of bad quality.

acceleration_pre!(accelerator, ws, num_iter)

A function that the accelerator can use before the nominal ADMM operator step.

In the case of an Anderson Accelerator this is used to calculate an accelerated candidate vector, that overwrites the current iterate.

Loop over all entries (i, j) in the clique and either set the correct row in A_I and b_I if (i, j) is not an overlap or add an overlap column with (-1 and +1) in the correct positions.

admm_w!

ADMM-operator variable w update with over-relaxation parameter α.

admm_x!

Evaluates the proximal operator of 1/2 x'Px + q'x s.t. Ax + s == b.

admm_z!

Evaluates the proximal operator of the Indicator function I_{R^n × K}.

Allocate ADMM- helper variables once the problem dimension is determined.

Given the row, column, and nzval vectors and dimensions, assemble the sparse matrix Aa of the decomposed problem in a slightly more memory efficient way.

Returns the appropriate amount of memory for A.nzval, including, starting from n_start, the (+1 -1) entries for the overlaps.

Scale active constraints by RHO_EQ_OVER_RHO_INEQ and set loose constraints to RHO_MIN.

apply_rho_adaptation_rules!()

Adapts the step-size parameter ρ when multiple conditions are satisfied.

• If automatic rho interval is active, the adaptive_rho_interval is chosen as a fraction of the setup time.

• Adapt rho if the iteration count reaches a multiple of adaptive_rho_interval and the maximum number of allowable updates has not been reached (adaptive_rho_max_adaptions).

• If an accelerator is used, update rho at the next possible iterations, i.e. at the next non-accelerated iteration.

assemble!(model, P, q, constraint(s); [settings, x0, y0, s0])

Assembles a COSMO.Model with a cost function defind by P and q, and a number of constraints.

The positive semidefinite matrix P and vector q are used to specify the cost function of the optimization problem:

min   1/2 x'Px + q'x
s.t.  Ax + b ∈ C

constraints is a COSMO.Constraint or an array of COSMO.Constraint objects that are used to describe the constraints on x.

The optional keyword argument settings can be used to pass custom solver settings:

custom_settings = COSMO.Settings(verbose = true);
assemble!(model, P, q, constraints, settings = custom_settings)

The optional keyword arguments x0 and y0 can be used to provide the solver with warm starting values for the primal variable x and the dual variable y.

x_0 = [1.0; 5.0; 3.0]
COSMO.assemble!(model, P, q, constraints, x0 = x_0)

augment_clique_based!(ws::COSMO.Workspace{T})

If settings.compact_decomposition = true, decompose the problem based on the clique tree.

check_termination!()

Checks the algorithms termination conditions at intervals specified in the settings and updates the algorithm status:

• residuals are "small enough" –> :Solved
• cost value out-ouf-range –> :Unsolved
• infeasibility conditions satisfied –> :Primalinfeasible / :Dualinfeasible
• time limit constraint reached –> :Timelimitreached

Classify the type of constraint of the box into loose inequality (-1), inequality (0) or equality (+1).

For inequality and box constraints, check if any constraints are obviously loose or tight.

Classify the inequality constraints as loose, if b very large, as s = -Ax + b >= 0.

Return the row ranges of each clique after the decomposition of C shifted by row_start.

clique_tree_from_graph!(clique_graph::SuperNodeTree)

Given the cliques and edges of a clique graph, this function computes a valid clique tree.

This is necessary to perform the psd completion step of the dual variable after solving the problem.

Computes the nonexpansive operator residual norm, i.e. f(wprev) = || wprev - w ||_2.

Given a list of edges, return an adjacency hash-table table with nodes from 1 to num_vertices.

compute_reduced_clique_graph!(sep::Array{Set{Int}, 1}, snd::Array{Set{Int}, 1})

Compute the reduced clique graph (union of all clique trees) given an initial clique tree defined by its supernodes snd and separator sep sets.

We are using the algorithm described in Michel Habib and Juraj Stacho - Polynomial-time algorithm for the leafage ofchordal graphs (2009), which computes the reduced clique graph in the following way:

1. Sort all minimal separators by size
2. Initialise graph CG(R) with cliques as nodes and no edges
3. for largest unprocessed separator S and | add an edge between any two cliques C1 and C2 if they both contain S and are in different connected components of CG(R) and store in edges. | Compute an edge weight used for merge decision and store in val. | Store the index of the separator which is the intersection C1 ∩ C2 in iter end

Compute the edge weight between all cliques specified by the edges (rows, cols).

For a cone C determine the sum of vector-dimensions of its cliques after decomposition (dim) and the total number of overlaps between them (overlaps).

Given two cliques c1 and c2 in the tree t, return the parent clique first.

Given the maximum weight spanning tree represented by E, determine a parent structure snd_par for the clique tree.

edge_metric(c_a::AbstractVector, c_b::AbstractVector, edge_weight::AbstractComplexityWeight)

Given two cliques c_a and c_b return a value for their edge weight.

empty_model!(model)

Resets all the fields of model to that of a model created with COSMO.Model() (apart from the settings).

Decide whether to merge the two cliques with clique indices cand.

Returns the appropriate amount of memory for the columns of the augmented problem matrix A, including, starting from n_start, the columns for the (+1 -1) entries for the overlaps.

Compute the amount of fill-in created by merging two cliques with the respective supernode and separator dimensions.

Return the dimension of the problem after a clique tree based decomposition, given the sparsity patterns in sp_arr.

Find connected components in undirected separator graph represented by H.

Find the transformation matrix H to decompose the vector s into its parts and stacks them into sbar

find_graph!(ci, rows::Array{Int, 1}, N::Int, C::AbstractConvexSet)

Given the indices of non-zero rows in rows:

• Compute the sparsity pattern and find a chordal extension using QDLDL with AMD ordering F.perm.
• If unconnected, connect the graph represented by the cholesky factor L

find_neighbors(edges::SparseMatrixCSC, c::Int)

Find all the cliques connected to c which are given by the nonzeros in (c, 1:c-1) and (c+1:n, c).

Given a sparse matrix S, write the columns and non-zero values into the first numnz entries of J and V.

Free unneccessary memory after merging completed.

Free all memory before exiting optimize!

For a PSD cone C of dimension nBlk, return the number of entries/rows in vectorized form.

get_block_indices(snd::Array{Int}, sep::Array{Int})

For a clique consisting of supernodes snd and seperators sep, compute all the indices (i, j) of the corresponding matrix block in the format (i, j, flag) where flag is equal to 0 if entry (i, j) corresponds to an overlap of the clique and 1 otherwise.

Nv is the number of vertices in the graph that we are trying to decompose.

Return clique with post order ind (prevents returning empty arrays due to clique merging)

Returns the number of rows and the number of overlaps of all the blocks (cliques) represented in the tree after decomposition.

Return an array of MergeLogs corresponding to the decomposed cones.

A sparse vector that maps the index of svec(i, j) = k to the actual index of where that entry is stored in A.rowval.

Given the svec index k and an offset row_range_col.start, return the location of the (i, j)th entry in the row vector rowval.

Check if s ∩ s2 == s3.

Return the number of elements in s ∩ s2.

Check whether the pair of cliques are in different components.

isdisjoint(c_a, c_b, is_sorted = false)

Checks whether two sets c_a, c_b have no common elements. Assumes by default that the sets are sorted.

Check whether edge is permissible for a merge. An edge is permissible if for every common neighbor N, C1 ∩ N == C2 ∩ N or if no common neighbors exist.

kruskal!(E::SparseMatrixCSC, num_cliques::Int)

Kruskal's algorithm to find a maximum weight spanning tree from the clique intersection graph.

E[i,j] holds the cardinalities of the intersection between two cliques (i, j). Changes the entries in the connectivity matrix E to a negative value if an edge between two cliques is included in the max spanning tree.

This is a modified version of https://github.com/JuliaGraphs/LightGraphs.jl/blob/master/src/spanningtrees/kruskal.jl

Store information about the merge of the two merge candidates cand.

Convert the matrix indices (i, j) of A ∈ R^{m x n} into the corresponding linear index of v = svec(A, ::UpperTriangle).

Convert the matrix indices (i, j) of A ∈ R^{m x n} into the corresponding linear index of v = vec(A).

max_elem(A::SparseMatrixCSC)

Find the matrix indices (i, j) of the first maximum element among the elements stored in A.nzval

Merge two cliques cand of the tree t that are in a parent - child relationship.

Given a supernode elimination tree t and a merge strategy strategy, merge the cliques in the tree.

Given the clique graph t merge the two cliques with indices in cand.

Given the clique tree t merge the two cliques with indices in cand as parent-child.

Given the nominal entry position k = svec(i, j) find and modify with new_row_val the actual location of that entry in the global row vector rowval.

Determine the total number of sets num_total after decomposition and the number of new psd cones num_new_psd_cones.

Return the number of rho adaptions so far.

optimize!(model)

Attempts to solve the optimization problem defined in COSMO.Model object with the user settings defined in COSMO.Settings. Returns a COSMO.Result object.

Find the index of k=svec(i, j) in the parent clique par_clique.

Print information about the accelerator at the start.

print_merge_logs(ws; print_max = 10)

Print the merge logs for each decomposed cone in the problem.

The dual variable μ can be recovered from w, s via Moreau decomposition: μ = ρ (w - Π(w)).

	reorder_snd_consecutively!(sntree, ordering)

Takes a SuperNodeTree and reorders the vertices in each supernode (and separator) to have consecutive order.

The reordering is needed to achieve equal column structure for the psd completion of the dual variable Y. This also modifies ordering which maps the vertices in the sntree back to the actual location in the not reordered data, i.e. the primal constraint variable S and dual variables Y.

Reset ADMM variables to last non-accelerated point.

reverse_decomposition!(ws::COSMO.Workspace, settings::COSMO.Settings)

After the problem has beend solved, undo the chordal decomposition.

Depending on the kind of transformation that was used, this involves:

• Reassembling the original matrix S from its blocks
• Reassembling the dual variable MU and performing a positive semidefinite completion.

Round x to the closest multiple of N.

Find the separator graph H given a separator and the relevant index-subset of cliques.

set!(model, P, q, A, b, convex_sets, [settings])

Sets model data directly based on provided fields.

Given the row vector and colptr of a sparse matrix, sort the entries within rowvals and nzvals withing the first n0 columns.

Traverse the clique tree in descending topological order and split the clique sets into supernodes and separators.

symmetrize_full!(A)

Symmetrizes the matrix A by calculating A = 0.5 * (A + A') and storing the result in-place.

symmetrize_upper!(A)

Symmetrizes the matrix A by calculating A = 0.5 * (A + A') but only performs the operation on the upper triangular part.

Find the next two cliques in the clique graph t to merge.

Traverse tree t in descending topological order and return parent and clique (root has highest order).

Check whether the model will contain any PSD constraints with unsupported Floating-point precision.

Find the size of the set A ∪ B under the assumption that A and B only have unique elements.

update!(model, q = nothing, b = nothing)

Updates the model data for b or q. This can be done without refactoring the KKT matrix. The vectors will be appropriatly scaled.

Update the diagonal rho entries in the lower right hand corner of the KKT matrix K.

After a merge happened, update the reduced clique graph.

After a merge attempt, update the strategy information.

Given the side dimension of a PSD cone return the number of stored entries.

warm_start!(model, x0, y0)

Provides the COSMO.Model with warm starting values for the primal variable x and the dual variable y.

warm_start_dual!(model, y0, [ind])

Provides the COSMO.Model with warm starting values for the dual variable y. ind can be used to warm start certain components of y.

warm_start_primal!(model, x0, [ind])

Provides the COSMO.Model with warm starting values for the primal variable x. ind can be used to warm start certain components of x.

warm_start_slack!(model, s0, [ind])

Provides the COSMO.Model with warm starting values for the primal slack variable s. ind can be used to warm start certain components of s.