Solving rank-constrained semidefinite programs in exact arithmetic

DOI10.1145/2930889.2930925MaRDI QIDQ2985848zbMATH OpenOpenAlexWikidataFDO

Authors Simone Naldi

Publication date 10 May 2017

Published in Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

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

zbMATH Keywords

exact algorithmsLMIpolynomial optimizationrank constraintssemidefinite programmingspectrahedrasums of squares

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Semidefinite programming (90C22) Nonconvex programming, global optimization (90C26)

Abstract: We consider the problem of minimizing a linear function over an affine section of the cone of positive semidefinite matrices, with the additional constraint that the feasible matrix has prescribed rank. When the rank constraint is active, this is a non-convex optimization problem, otherwise it is a semidefinite program. Both find numerous applications especially in systems control theory and combinatorial optimization, but even in more general contexts such as polynomial optimization or real algebra. While numerical algorithms exist for solving this problem, such as interior-point or Newton-like algorithms, in this paper we propose an approach based on symbolic computation. We design an exact algorithm for solving rank-constrained semidefinite programs, whose complexity is essentially quadratic on natural degree bounds associated to the given optimization problem: for subfamilies of the problem where the size of the feasible matrix is fixed, the complexity is polynomial in the number of variables. The algorithm works under assumptions on the input data: we prove that these assumptions are generically satisfied. We also implement it in Maple and discuss practical experiments.

Recommendations

• Solving rank-constrained semidefinite programs in exact arithmetic
• Exact algorithms for linear matrix inequalities
• A class of semidefinite programs with rank-one solutions

Cited in

(9)

• Solving rank-constrained semidefinite programs in exact arithmetic
• Contracting optimally an interval matrix without loosing any positive semi-definite matrix is a tractable problem
• Exact algorithms for linear matrix inequalities
• Grothendieck inequalities for semidefinite programs with rank constraint
• Symbolic computation in hyperbolic programming
• Finding maximum rank moment matrices by facial reduction on primal form and Douglas-Rachford iteration
• A class of semidefinite programs with rank-one solutions
• Solving parametric linear matrix inequalities
• Semidefinite programming and arithmetic circuit evaluation

Describes a project that uses

Uses Software

• SPECTRA
• Maple
• FGb

This page was built for publication: Solving rank-constrained semidefinite programs in exact arithmetic

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