Decomposition of arrow type positive semidefinite matrices with application to topology optimization

DOI10.1007/S10107-020-01526-WzbMATH Open1478.90080arXiv1911.09412OpenAlexW2990431365MaRDI QIDQ2235142FDOQ2235142

Authors: Michal Kočvara 

Publication date: 20 October 2021

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: Decomposition of large matrix inequalities for matrices with chordal sparsity graph has been recently used by Kojima et al. cite{kim2011exploiting} to reduce problem size of large scale semidefinite optimization (SDO) problems and thus increase efficiency of standard SDO software. A by-product of such a decomposition is the introduction of new dense small-size matrix variables. We will show that for arrow type matrices satisfying suitable assumptions, the additional matrix variables have rank one and can thus be replaced by vector variables of the same dimensions. This leads to significant improvement in efficiency of standard SDO software. We will apply this idea to the problem of topology optimization formulated as a large scale linear semidefinite optimization problem. Numerical examples will demonstrate tremendous speed-up in the solution of the decomposed problems, as compared to the original large scale problem. In our numerical example the decomposed problems exhibit linear growth in complexity, compared to the more than cubic growth in the original problem formulation. We will also give a connection of our approach to the standard theory of domain decomposition and show that the additional vector variables are outcomes of the corresponding discrete Steklov-Poincar'{e} operators.

Full work available at URL: https://arxiv.org/abs/1911.09412

Recommendations

• Sum-of-squares chordal decomposition of polynomial matrix inequalities
• Decomposition in conic optimization with partially separable structure
• Chordal decomposition in operator-splitting methods for sparse semidefinite programs
• Exploiting structured sparsity in large scale semidefinite programming problems
• Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results

zbMATH Keywords

domain decompositionsemidefinite optimizationtopology optimizationchordal graphspositive semidefinite matrices

Mathematics Subject Classification ID

Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) Semidefinite programming (90C22) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Compliance or weight optimization in solid mechanics (74P05)

Cites Work

• Title not available (Why is that?)
• Positive definite completions of partial Hermitian matrices
• Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
• Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion
• Multidisciplinary free material optimization
• Positive semidefinite matrices with a given sparsity pattern
• On the existence of convex decompositions of partially separable functions
• A Finite Element Analysis of Optimal Variable Thickness Sheets
• A direct proof for the matrix decomposition of chordal-structured positive semidefinite matrices
• Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results

Cited In (3)

• Linear optimization over homogeneous matrix cones
• A graphic structure based branch-and-bound algorithm for complex quadratic optimization and applications to magnitude least-square problem
• The last dozen of years of or research in Czechia and Slovakia

Uses Software

• Matlab
• Mosek
• SparseCoLO

This page was built for publication: Decomposition of arrow type positive semidefinite matrices with application to topology optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2235142)