Fast implementation for semidefinite programs with positive matrix completion
From MaRDI portal
Abstract: Solving semidefinite programs (SDP) in a short time is the key to managing various mathematical optimization problems. The matrix-completion primal-dual interior-point method (MC-PDIPM) extracts a sparse structure of input SDP by factorizing the variable matrices. In this paper, we propose a new factorization based on the inverse of the variable matrix to enhance the performance of MC-PDIPM. We also use multithreaded parallel computing to deal with the major bottlenecks in MC-PDIPM. Numerical results show that the new factorization and multithreaded computing reduce the computation time for SDPs that have structural sparsity.
Recommendations
- Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results
- An inexact dual logarithmic barrier method for solving sparse semidefinite programs
- Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
- Algorithm 925, parallel solver for semidefinite programming problem having sparse Schur complement matrix
- Semidefinite Programming in the Space of Partial Positive Semidefinite Matrices
Cites work
- A distributed method for solving semidefinite programs arising from ad hoc wireless sensor network localization
- Algorithm 920: SFSDP: a sparse version of full semidefinite programming relaxation for sensor network localization problems
- Algorithm 925, parallel solver for semidefinite programming problem having sparse Schur complement matrix
- An Interior-Point Method for Semidefinite Programming
- Basic Linear Algebra Subprograms for Fortran Usage
- CSDP, A C library for semidefinite programming
- Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
- Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Interior-Point Methods for the Monotone Semidefinite Linear Complementarity Problem in Symmetric Matrices
- LAPACK Users' Guide
- Large-scale semidefinite programs in electronic structure calculation
- Multifrontal parallel distributed symmetric and unsymmetric solvers
- On the Shannon capacity of a graph
- Positive definite completions of partial Hermitian matrices
- Primal--Dual Path-Following Algorithms for Semidefinite Programming
- Primal-Dual Interior-Point Methods for Self-Scaled Cones
- Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
- Semidefinite optimization
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
Cited in
(7)- Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results
- An efficient second-order cone programming approach for optimal selection in tree breeding
- scientific article; zbMATH DE number 4178733 (Why is no real title available?)
- Using optimization to obtain a width-independent, parallel, simpler, and faster positive SDP solver
- \(LDL^T\) direction interior point method for semidefinite programming
- Exploiting aggregate sparsity in second-order cone relaxations for quadratic constrained quadratic programming problems
- A new algorithm for positive semidefinite matrix completion
This page was built for publication: Fast implementation for semidefinite programs with positive matrix completion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3458828)
