Block Factor-Width-Two Matrices in Semidefinite Programming

Aivar Sootla, Yang Zheng, Antonis Papachristodoulou
3/12/2019
math.OCeess.SY

No confident code implementation found for this paper.

Abstract

In this paper, we introduce a set of block factor-width-two matrices, which is a generalisation of factor-width-two matrices and is a subset of positive semidefinite matrices. The set of block factor-width-two matrices is a proper cone and we compute a closed-form expression for its dual cone. We use these cones to build hierarchies of inner and outer approximations of the cone of positive semidefinite matrices. The main feature of these cones is that they enable a decomposition of a large semidefinite constraint into a number of smaller semidefinite constraints. As the main application of these classes of matrices, we envision large-scale semidefinite feasibility optimisation programs including sum-of-squares (SOS) programs. We present numerical examples from SOS optimisation showcasing the properties of this decomposition.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Block Factor-width-two Matrices and Their Applications to Semidefinite and Sum-of-squares Optimization

93% match2019

Riemannian Structure and Optimization for a Class of Low-Parametric Orthogonal Matrices

77% match1 repo2026

Decomposed Structured Subsets for Semidefinite and Sum-of-Squares Optimization

77% match2019

Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization

75% match2022

Exploiting Low-Rank Structure in Semidefinite Programming by Approximate Operator Splitting

75% match1 repo972018

COSMO: A conic operator splitting method for convex conic problems

74% match1 repo3192019

Cite this paper

@article{sootla2019block,
  title  = {Block Factor-Width-Two Matrices in Semidefinite Programming},
  author = {Aivar Sootla and Yang Zheng and Antonis Papachristodoulou},
  year   = {2019},
  eprint = {1903.04938},
  archivePrefix = {arXiv},
  url    = {https://arxiv.org/abs/1903.04938}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/1903.04938.svg)](https://codeofpaper.com/paper/1903.04938)

Discussion