Data

Tools

Indexes

Applications

Experiments

Open Source Science

SDPSymmetryReduction

A julia package to numerically reduce semidefinite programming problems.

https://github.com/danielbrosch/sdpsymmetryreduction.jl

Science Score: 31.0%

This score indicates how likely this project is to be science-related based on various indicators:

  • ✓
    CITATION.cff file
    Found CITATION.cff file
  • ✓
    codemeta.json file
    Found codemeta.json file
  • ○
    .zenodo.json file
  • ○
    DOI references
  • ○
    Academic publication links
  • ○
    Committers with academic emails
  • ○
    Institutional organization owner
  • ○
    JOSS paper metadata
  • ○
    Scientific vocabulary similarity
    Low similarity (10.8%) to scientific vocabulary
Last synced: 11 months ago · JSON representation ·

Repository

A julia package to numerically reduce semidefinite programming problems.

Basic Info
  • Host: GitHub
  • Owner: DanielBrosch
  • License: mit
  • Language: Julia
  • Default Branch: main
  • Homepage:
  • Size: 1.68 MB
Statistics
  • Stars: 5
  • Watchers: 3
  • Forks: 4
  • Open Issues: 2
  • Releases: 7
Created over 5 years ago · Last pushed over 1 year ago
Metadata Files
Readme License Citation

README.md

SDPSymmetryReduction

Stable Dev Build Status Coverage

Numerically reduces semidefinite programming problems by exploiting their symmetry. Input is 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.

Installation

Simply run julia pkg> add SDPSymmetryReduction # Press ']' to enter the Pkg REPL mode.

Main use

The function admissible_subspace determines an optimal admissible partition subspace for the problem. This is done using a randomized Jordan-reduction algorithm, and it returns a Jordan algebra (closed under linear combinations and squaring). SDPs can be restricted to such a subspace without changing their optimal value.

The function blockDiagonalize determines a block-diagonalization of a (Jordan)-algebra given by a partition P using a randomized algorithm.

For more details, see the documentation.

Example: Theta'-function

Let Adj be an adjacency matrix of an (undirected) graph G. Then the Theta'-function of the graph is given by sup dot(J,X) subject to dot(Adj,X) = 0, dot(I,X) = 1, X is positive semidefinite, X is entry-wise nonnegative, where J is the all-ones matrix, and I the identity. Then we can exploit the symmetry of the graph and calculate this function by ```julia using SDPSymmetryReduction using LinearAlgebra, SparseArrays using JuMP, MosekTools

Theta' SDP

N = size(Adj,1) C = ones(N^2) A = hcat(vec(Adj), vec(Matrix(I, N, N)))' b = [0, 1]

Find the optimal admissible subspace (= Jordan algebra)

P = admissible_subspace(C, A, b; verbose=true)

Block-diagonalize the algebra

blkD = blockDiagonalize(P, true)

Calculate the coefficients of the new SDP

PMat = hcat([sparse(vec(P.matrix .== i)) for i = 1:dim(P)]...) newA = A * PMat newB = b newC = C' * PMat

Solve with optimizer of choice

m = Model(Mosek.Optimizer)

Initialize variables corresponding parts of the partition P

>= 0 because the original SDP-matrices are entry-wise nonnegative

x = @variable(m, x[1:dim(P)] >= 0)

@constraint(m, newA * x .== newB) @objective(m, Max, newC * x)

psdBlocks = sum(blkD.blks[i] .* x[i] for i = 1:dim(P)) for blk in psdBlocks if size(blk, 1) > 1 @constraint(m, blk in PSDCone()) else @constraint(m, blk .>= 0) end end

optimize!(m)

@show termination_status(m) @show value(newC * x) ``` There are more examples in the documentation.

Citing

See CITATION.bib for the relevant reference(s).

Owner

  • Name: Daniel Brosch
  • Login: DanielBrosch
  • Kind: user
  • Company: Tilburg University

PhD-candidate at Tilburg University. Mostly focused on symmetric semidefinite and polynomial optimization. Currently working on flag sums-of-squares.

Citation (CITATION.bib) 

@article{brosch2020jordan,
      title={Jordan symmetry reduction for conic optimization over the doubly nonnegative cone: theory and software}, 
      author={Daniel Brosch and Etienne de Klerk},
      year={2020},
      eprint={2001.11348},
      archivePrefix={arXiv},
      primaryClass={math.OC}
}

GitHub Events

Total
  • Create event: 4
  • Commit comment event: 6
  • Release event: 3
  • Watch event: 1
  • Delete event: 2
  • Issue comment event: 24
  • Push event: 10
  • Pull request event: 8
  • Fork event: 2
Last Year
  • Create event: 4
  • Commit comment event: 6
  • Release event: 3
  • Watch event: 1
  • Delete event: 2
  • Issue comment event: 24
  • Push event: 10
  • Pull request event: 8
  • Fork event: 2

Committers

Last synced: over 3 years ago

All Time
  • Total Commits: 32
  • Total Committers: 3
  • Avg Commits per committer: 10.667
  • Development Distribution Score (DDS): 0.219
Top Committers
Name Email Commits
Daniel Brosch d****h@o****m 25
Daniel Brosch D****h@o****m 5
Daniel Brosch 7****h@u****m 2

Issues and Pull Requests

Last synced: 11 months ago

All Time
  • Total issues: 3
  • Total pull requests: 5
  • Average time to close issues: less than a minute
  • Average time to close pull requests: 3 months
  • Total issue authors: 2
  • Total pull request authors: 3
  • Average comments per issue: 2.33
  • Average comments per pull request: 5.6
  • Merged pull requests: 5
  • Bot issues: 0
  • Bot pull requests: 0
Past Year
  • Issues: 2
  • Pull requests: 5
  • Average time to close issues: N/A
  • Average time to close pull requests: 3 months
  • Issue authors: 1
  • Pull request authors: 3
  • Average comments per issue: 0.5
  • Average comments per pull request: 5.6
  • Merged pull requests: 5
  • Bot issues: 0
  • Bot pull requests: 0
View more stats
Top Authors
Issue Authors
  • kalmarek (2)
  • JuliaTagBot (1)
Pull Request Authors
  • kalmarek (6)
  • sebastiendesignolle (2)
  • blegat (2)
Top Labels
Issue Labels
Pull Request Labels

Packages

  • Total packages: 1
  • Total downloads:
    • julia 2 total
  • Total dependent packages: 0
  • Total dependent repositories: 0
  • Total versions: 6
juliahub.com: SDPSymmetryReduction

A julia package to numerically reduce semidefinite programming problems.

  • Versions: 6
  • Dependent Packages: 0
  • Dependent Repositories: 0
  • Downloads: 2 Total
Rankings
Dependent repos count: 9.9%
Average: 38.8%
Dependent packages count: 38.9%
Stargazers count: 52.9%
Forks count: 53.5%
Last synced: 11 months ago

Dependencies

.github/workflows/CI.yml actions
  • actions/checkout v4 composite
  • codecov/codecov-action v2 composite
  • julia-actions/cache v2 composite
  • julia-actions/julia-buildpkg v1 composite
  • julia-actions/julia-processcoverage v1 composite
  • julia-actions/julia-runtest v1 composite
  • julia-actions/setup-julia v2 composite
.github/workflows/CompatHelper.yml actions
.github/workflows/TagBot.yml actions
  • JuliaRegistries/TagBot v1 composite
.github/workflows/documentation.yml actions
  • actions/checkout v4 composite
  • julia-actions/julia-buildpkg v1 composite
  • julia-actions/julia-docdeploy v1 composite
  • julia-actions/setup-julia latest composite
.github/workflows/register.yml actions
  • julia-actions/RegisterAction latest composite