KO
|
EN
gitlite — search
Search
#python
#java
#python3
#arduino
#golang
#machine-learning
#rust
#html
#flask
#javascript
#seismology
#nodejs
Chordal.jl
★ 26
Open GitHub ↗
No description available.
Download README (.md)
Explore Similar Repositories
human-guild
:
Help humans to earn money in digital economy
spotify-get-current-playing-track
:
A quick script to get the current playing song on Spotify
LinearGAN
:
[CVPR 2021] Linear Semantics in Generative Adversarial Networks
MarinDeck4iOS
:
MarinDeck for iOS
qb-scrapyard
:
Scrapyard For QB-Core
// repository documentation
Was this content helpful?
★ 0
(0 ratings)
Select Rating:
★
★
★
★
★
Submit Feedback
Recent Feedback
×
Download README
Do you want to download the
README.md
file for
Chordal.jl
?
Download (.md)
# Chordal [](https://tjdiamandis.github.io/Chordal.jl/dev) [](https://github.com/tjdiamandis/Chordal.jl/actions) [](https://codecov.io/gh/tjdiamandis/Chordal.jl) #### NOTE: This package is very much a work in progress. Feature requests welcome! ## Overview This package implements data structures and subroutines for chordal matrices. It is largely a (work in progress) port of [`CHOMPACK.py`](https://chompack.readthedocs.io/en/latest/) to Julia and currently includes routines for - Chordal Decomposition of PSD matrices - Maximum Determinant PSD completion - Chordality tests and perfect elimination ordering These algorithms are (mostly) based on the multi-frontal algorithms described in [Logarithmic Barriers for Sparse Matrix Cones](https://arxiv.org/abs/1203.2742) and the survey paper [Chordal Graphs and Semidefinite Optimization](https://www.seas.ucla.edu/~vandenbe/publications/chordalsdp.pdf). Additionally, `Chordal.jl` includes utility functions for the elimination tree and clique tree data structures described in these papers. ## Chordal Decomposition Chordal decomposition breaks up a large `n x n` PSD matrix constraint into `K` smaller `n_k x n_k` PSD constraints. These smaller constraints correspond to the cliques in the chordal graph associated with the aggregate sparsity pattern of the problem (i.e., the matrices associated with the constraints and objective function involving the PSD variable). These cliques can be further combined (replacing structural zeros with numeric zeros) to optimize optimization algorithm performance. This package uses the clique graph-based merging scheme introduced by Garstka et al. in [A clique graph based merging strategy for decomposable SDPs](https://arxiv.org/abs/1911.05615) and implemented in [COSMO.jl](https://github.com/oxfordcontrol/COSMO.jl)). ## Additional functionality to include and TODOs - [X] Min rank matrix completion - [X] Utility functions for SDP decomposition with JuMP - [ ] Symbolic and numeric cholesky factorization - [ ] Allow user-specified weight function for clique graph merging - [X] Euclidean distance matrix completion - [ ] Only support LMI form of SDP & use `Dualization.jl` to convert standard form. ## References - Lieven Vandenberghe and Martin Andersen's [Chordal Graphs and Semidefinite Optimization](https://www.seas.ucla.edu/~vandenbe/publications/chordalsdp.pdf) - Martin Andersen, Joachim Dahl, and Lieven Vandenberghe's [Logarithmic Barriers for Sparse Matrix Cones](https://arxiv.org/abs/1203.2742) - Yifan Sun's thesis [Decomposition Methods for Semidefinite optimization](https://escholarship.org/content/qt1cv6981p/qt1cv6981p.pdf) - Yifan Sun, Martin S. Andersen, and Lieven Vandenberghe's [Decomposition in conic optimization with partially separable structure](https://arxiv.org/abs/1306.0057) - Michael Garstka, Mark Cannon, and Paul Goulart's [A clique graph based merging strategy for decomposable SDPs](https://arxiv.org/abs/1911.05615) ## See also - [`COSMO.jl`](https://github.com/oxfordcontrol/COSMO.jl) is a conic solver that uses chordal decomposition for large PSD constraints. - [`CHOMPACK.py`](https://github.com/cvxopt/chompack) includes the same algorithms in Python.
