Certifying solutions of degenerate semidefinite programs
Kolmogorov V, Naldi S, Zapata J. 2025. Certifying solutions of degenerate semidefinite programs. ACM Communications in Computer Algebra. 59(4), 147–152.
Download (ext.)
Journal Article
| Published
| English
Scopus indexed
Author
Kolmogorov, VladimirISTA;
Naldi, Simone;
Zapata, JefersonISTA
Corresponding author has ISTA affiliation
Department
Abstract
We consider the problem of certifying the feasibility of a (possibly degenerate) semidefinite programming problem represented by rational input data together with a numerical solution that is guaranteed to be sufficiently close to an exact solution of maximal rank. Our method constructs a polynomial system whose set of real solutions has an isolated point that satisfies the input program. An experimental comparison between the corresponding symbolic-numerical algorithm and the purely symbolic algorithm from [3, 5] shows that the hybrid algorithm is able to certify instances where the exact method fails.
Publishing Year
Date Published
2025-12-01
Journal Title
ACM Communications in Computer Algebra
Publisher
ACM
Acknowledgement
This extended abstract is based on the paper [7], accepted for publication at SIAM
J. Opt. on April 22, 2025, to which we refer for technical details and complete proofs. This work has been
supported by the Doctoral Programme Vienna Graduate School on Computational Optimization (VGSCO)
which was funded by FWF (Austrian Science Fund), project W 1260-N35, and partially supported by the
ANR JCJC project ANR-21-CE48-0006-01 “HYPERSPACE”.
Volume
59
Issue
4
Page
147-152
ISSN
eISSN
IST-REx-ID
Cite this
Kolmogorov V, Naldi S, Zapata J. Certifying solutions of degenerate semidefinite programs. ACM Communications in Computer Algebra. 2025;59(4):147-152. doi:10.1145/3832046.3832063
Kolmogorov, V., Naldi, S., & Zapata, J. (2025). Certifying solutions of degenerate semidefinite programs. ACM Communications in Computer Algebra. ACM. https://doi.org/10.1145/3832046.3832063
Kolmogorov, Vladimir, Simone Naldi, and Jeferson Zapata. “Certifying Solutions of Degenerate Semidefinite Programs.” ACM Communications in Computer Algebra. ACM, 2025. https://doi.org/10.1145/3832046.3832063.
V. Kolmogorov, S. Naldi, and J. Zapata, “Certifying solutions of degenerate semidefinite programs,” ACM Communications in Computer Algebra, vol. 59, no. 4. ACM, pp. 147–152, 2025.
Kolmogorov V, Naldi S, Zapata J. 2025. Certifying solutions of degenerate semidefinite programs. ACM Communications in Computer Algebra. 59(4), 147–152.
Kolmogorov, Vladimir, et al. “Certifying Solutions of Degenerate Semidefinite Programs.” ACM Communications in Computer Algebra, vol. 59, no. 4, ACM, 2025, pp. 147–52, doi:10.1145/3832046.3832063.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Google Scholar