Chordal.jl

KO | EN

gitlite — search

#javascript #python #react #typescript #go #golang #deep-learning #linux #java #windows #security #mcp #ios #open-source

(★ 26)

No description available.

Chordal.jl Latest Version Download

Download Latest Version (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# Chordal
[![Dev](https://img.shields.io/badge/docs-dev-blue.svg)](https://tjdiamandis.github.io/Chordal.jl/dev)
[![Build Status](https://github.com/tjdiamandis/Chordal.jl/workflows/CI/badge.svg)](https://github.com/tjdiamandis/Chordal.jl/actions)
[![codecov](https://codecov.io/gh/tjdiamandis/Chordal.jl/branch/main/graph/badge.svg?token=ZPW6OXSD9A)](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.

Chordal.jl

Chordal.jl Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

Chordal.jl

Chordal.jl Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

Download README