Block Factor-Width-Two Matrices in Semidefinite Programming

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.

• Publication year

  2019

• Venue

  European Control Conference

• Publication date

  2019-03-12

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.23919/ECC.2019.8795689arXiv 1903.04938
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Sparse sum-of-squares (SOS) optimization: A bridge between DSOS/SDSOS and SOS optimization for sparse polynomials

  2018cited by this paper
• Decomposition and Completion of Sum-of-Squares Matrices

  2018cited by this paper
• Scalable analysis of linear networked systems via chordal decomposition

  2018cited by this paper
• Chordal decomposition in operator-splitting methods for sparse semidefinite programs

  2017cited by this paper
• DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization

  2017influential reference
• Block-diagonal solutions to Lyapunov inequalities and generalisations of diagonal dominance

  2017cited by this paper
• Fast ADMM for semidefinite programs with chordal sparsity

  2016cited by this paper
• Fast ADMM for homogeneous self-dual embedding of sparse SDPs

  2016cited by this paper
• On existence of solutions to structured lyapunov inequalities

  2016cited by this paper
• Chordal Graphs and Semidefinite Optimization

  2015cited by this paper
• Sum of Squares Basis Pursuit with Linear and Second Order Cone Programming

  2015cited by this paper
• Decomposition in Conic Optimization with Partially Separable Structure

  2013cited by this paper
• Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding

  2013influential reference
• Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion

  2011cited by this paper
• Convex optimization

  2010cited by this paper
• Moments, Positive Polynomials And Their Applications

  2009cited by this paper
• Algorithm ∗

  2009cited by this paper
• Exploiting Sparsity in Semide(cid:12)nite Programming via Matrix Completion II: Implementation and Numerical Results ?

  2007cited by this paper
• Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity

  2006cited by this paper
• A tutorial on sum of squares techniques for systems analysis

  2005cited by this paper
• YALMIP : a toolbox for modeling and optimization in MATLAB

  2004cited by this paper
• ARTICLE IN PRESS Linear Algebra and its Applications xxx (2005) xxx–xxx www.elsevier.com/locate/laa On factor width and symmetric H-matrices

  2004influential reference
• Exploiting sparsity in semidefinite programming via matrix completion II: implementation and numerical results

  2003cited by this paper
• Symmetry groups, semidefinite programs, and sums of squares

  2002cited by this paper
• The Mosek Interior Point Optimizer for Linear Programming: An Implementation of the Homogeneous Algorithm

  2000influential reference
• Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization

  2000cited by this paper
• An algorithm for sums of squares of real polynomials

  1998cited by this paper
• Linear Matrix Inequalities In System And Control Theory

  1998cited by this paper
• Mathematical Programming manuscript No. (will

  1997cited by this paper
• Linear Matrix Inequalities in Systems and Control Theory

  1994cited by this paper
• Nonnegative Matrices in the Mathematical Sciences

  1979cited by this paper
• Block diagonally dominant matrices and generalizations of the Gerschgorin circle theorem

  1962cited by this paper

• Outer-Iterative Approximation of Semidefinite Programming for Limit Analysis

  2025cites this paper
• Iterative Inner/outer Approximations for Scalable Semidefinite Programs using Block Factor-width-two Matrices

  2022cites this paper
• Block Factor-Width-Two Matrices and Their Applications to Semidefinite and Sum-of-Squares Optimization

  2019cites this paper
• On the Existence of Block-Diagonal Solutions to Lyapunov and ${\mathcal {H}_\infty }$ Riccati Inequalities

  2019cites this paper