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

DOI10.1007/S10107-020-01526-WMaRDI QIDQ2235142zbMATHOpenAlexFDO

Authors Michal Kočvara

Publication date 20 October 2021

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 4193023 (Why is no real title available?)
• 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 linear and nonlinear matrix inequalities via positive semidefinite matrix completion
• Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
• Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results
• Multidisciplinary free material optimization
• On the existence of convex decompositions of partially separable functions
• Positive definite completions of partial Hermitian matrices
• Positive semidefinite matrices with a given sparsity pattern

Cited in

(3)

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

Describes a project that uses

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)