GitHub

SDPSymmetryReduction.jl

A symmetry reduction package for Julia.

Documentation for SDPSymmetryReduction.

This package provides functions to determine a symmetry reduction of an SDP numerically using the Jordan Reduction method.

It assumes that the problem is given in vectorized standard form

sup/inf     dot(C,x)
subject to  Ax = b,
            Mat(x) is positive semidefinite/doubly nonnegative,

where C and b are vectors and A is a matrix.

The function admissible_subspace finds an optimal admissible partition subspace for a given SDP. An SDP can be restricted to such a subspace without changing its optimum. The returned Partition-subspace can then be block-diagonalized using blockDiagonalize.

For details on the theory and the implemented algorithms, check out the reference linked in the repository.

Examples

Documentation

SDPSymmetryReduction.AbstractPartition — Type
AbstractPartition

Abstract type representing partition subspace. A partition subspace is a partition of 1:n × 1:n into disjoint subsets. The first set has a special meaning and should be preserved during refines.

Necessary methods are:

  • (P::AbstractPartition)(M::AbstractMatrix) - construct a partition subspace from a matrix of numerical values.
  • dim(p::AbstractPartition) - the dimension of the partition
  • Base.size(p::AbstractPartition, args...) - follows the Base.size for AbstractArrays
  • Base.fill!(M::AbstractMatrix, p::AbstractPartition; values) - fills M with values according to partition p.
  • refine!(p::AP, q::AP) where {AP<:AbstractPartition} - find coarsest common refinement of p and q and return it as a AP.
source
Base.fill! — Method
fill!(M::AbstractMatrix, p::AbstractPartition; values)

Fill M with values according to partition p.

The fill will to preserve the 0-set.

Examples

julia> q = SR.Partition(Float64[
           1 1 0;
           1 0 5;
           0 3 3
       ]);

julia> fill!(zeros(3,3), q, values=[-1, sqrt(2), π])
3×3 Matrix{Float64}:
 -1.0  -1.0      0.0
 -1.0   0.0      3.14159
  0.0   1.41421  1.41421
source
SDPSymmetryReduction.admissible_subspace — Method
admissible_subspace([Partition{UInt16},] C, A, b[; verbose, atol])

Return the optimal admissible partition subspace for the semidefinite problem

  minimize: ⟨Cᵀ, x⟩
subject to: A·x = b
            Mat(x) ⪰ 0

where C and A are symmetric.

The problem can be restricted to the subspace without changing its optimal value.

The partition is found by a Jordan-reduction algorithm saturating with random squares. With probability 1 the returned subspace is a Jordan algebra (i.e. closed under linear combinations and squaring). See Section 5.2 of Permenter thesis.

Output

  • A Partition subspace P.
source
SDPSymmetryReduction.blockDiagonalize — Method
blockDiagonalize(P::Partition, verbose = true; epsilon = 1e-8, complex = false)

Determines a block-diagonalization of a (Jordan)-algebra given by a partition P using a randomized algorithm. blockDiagonalize(P) returns a real block-diagonalization blkd, if it exists, otherwise nothing.

blockDiagonalize(P; complex = true) returns the same, but with complex valued matrices, and should be used if no real block-diagonalization was found. To use the complex matrices practically, remember that a Hermitian matrix A is positive semidefinite iff [real(A) -imag(A); imag(A) real(A)] is positive semidefinite.

Output

  • blkd.blkSizes is an integer array of the sizes of the blocks.
  • blkd.blks is an array of length dim(P) containing arrays of (real/complex) matrices of sizes blkd.blkSizes. I.e. blkd.blks[i] is the image of the basis element P.matrix .== i.
source
SDPSymmetryReduction.block_norms — Function
block_norms(Q′AQ::AbstractMatrix, eigdec::EigenDecomposition, p=2)

Compute the norms of block endomorphism Q′AQ with respect to the eigenspaces eigdec.

The function returns a symmetric matrix where the (i, j) entry represents the p-norm of the block corresponding to eigenspaces i and j

source
SDPSymmetryReduction.dim — Function
dim(ap::AbstractPartition)

The dimension of the partition subspace ap.

!!! note

The 0-set (the first subset) has a special meaning and is not accounted

for the calculation.

Examples

julia> q = SR.Partition(Float64[
           1 1 0;
           1 0 5;
           0 3 3
       ]);

julia> SR.dim(q)
3

julia> p = SR.Partition([
           1 1 2;
           1 2 5;
           2 3 3
       ]);

julia> SR.dim(p)
4
source
SDPSymmetryReduction.eigen_decomposition — Method
eigen_decomposition(P::AbstractPartition, A::AbstractMatrix; atol=1e-12*size(A,1))

Find eigenspace decomposition of partition subspace P by inspecting a generic element thereof.

Returns (ed::EigenDecomposition, K) where K is a partition of eigen-spaces of ed into isomorphism classes. If the computed K is suspected to be inconsistent with ed (e.g. transitivity fails because of lack of precision) NumericalInconsistency exception will be thrown.

Follows Algorithm 4.1 of

K. Murota et. al. A Numerical Algorithm for Block-Diagonal Decomposition of Matrix *-Algebras, Part I: Proposed Approach and Application to Semidefinite Programming Japan Journal of Industrial and Applied Mathematics, June 2010 DOI: 10.1007/s13160-010-0006-9

source
SDPSymmetryReduction.irreducible_decomposition — Function
irreducible_decomposition(ed::EigenDecomposition, K, P::AbstractPartition[, A])

Find a decomposition of (ed, K) into irreducible subspaces.

Eigenspaces determined to be isomorphic by K will be merged together and a single column vector from each irreducible subspace for each isomorphism class will be returned. This method uses a generic element of the Jordan algebra defined by P and is therefore non-deterministic and may suffer from numerical errors.

Note

While the vectors of eigen_decomposition determine an isomorphism of vector spaces, irreducible_decomposition defines only a projection.

Follows Section 4.3 Decomposition into irreducible components of

K. Murota et. al. A Numerical Algorithm for Block-Diagonal Decomposition of Matrix *-Algebras, Part I: Proposed Approach and Application to Semidefinite Programming Japan Journal of Industrial and Applied Mathematics, June 2010 DOI: 10.1007/s13160-010-0006-9

source
SDPSymmetryReduction.isomorphism_partition — Method
isomorphism_partition(ed::EigenDecomposition, A::AbstractMatrix[; atol])

Partition eigen-subspaces of ed into isomorphism classes based on a generic element A.

Computes partition K of Murota et al. as defined in Algorithm 4.1, Step 3.

source
SDPSymmetryReduction.log_histogram — Method
log_histogram(X, num_bins::Integer; atol)

Compute a logarithmically spaced histogram for the absolute values in X.

The bin edges are determined using an exponential scale between the smallest and largest absolute values in X, with a lower bound enforced by atol.

Returns the number of elements in each bin and the logarithmically spaced bin edges.

source
SDPSymmetryReduction.otsu_threshold — Method
otsu_threshold(X::AbstractArray; atol)

Return a scalar threshold value that separates the entries of X into two classes.

The computation is based on Otsu-based thresholding. The method maximizes the variance between two classes in a histogram representation of norms, determining an optimal binarization threshold.

The methods assumes a logarithmic histogram over orders of magnitude spanned by the element type of X.

source
SDPSymmetryReduction.randomize — Method
randomize([T=Float64, ]P::AbstractPartition)

Return a Matrix{T} filled with random values according to partition subspace P.

0-set of P will be mapped to zero(T).

Examples

julia> q = SR.Partition([
           1 1 0;
           1 0 5;
           0 3 3
       ]);

julia> SR.randomize(q)
3×3 Matrix{Float64}:
 0.916099  0.916099  0.0
 0.916099  0.0       0.0117013
 0.0       0.052362  0.052362
source
SDPSymmetryReduction.refine! — Function
refine!(p::AP, q::AP) where AP<:AbstractPartition

Find the coarsest common refinement of partitions p and q modifying p in-place.

source