---
OA_place: publisher
OA_type: free access
_id: '22774'
abstract:
- lang: eng
  text: 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.
acknowledgement: "This extended abstract is based on the paper [7], accepted for publication
  at SIAM\r\nJ. Opt. on April 22, 2025, to which we refer for technical details and
  complete proofs. This work has been\r\nsupported by the Doctoral Programme Vienna
  Graduate School on Computational Optimization (VGSCO)\r\nwhich was funded by FWF
  (Austrian Science Fund), project W 1260-N35, and partially supported by the\r\nANR
  JCJC project ANR-21-CE48-0006-01 “HYPERSPACE”.\r\n"
article_processing_charge: No
article_type: original
author:
- first_name: Vladimir
  full_name: Kolmogorov, Vladimir
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
- first_name: Simone
  full_name: Naldi, Simone
  last_name: Naldi
- first_name: Jeferson
  full_name: Zapata, Jeferson
  id: 00223538-AF8F-11E9-A4C7-F729E6697425
  last_name: Zapata
citation:
  ama: Kolmogorov V, Naldi S, Zapata J. Certifying solutions of degenerate semidefinite
    programs. <i>ACM Communications in Computer Algebra</i>. 2025;59(4):147-152. doi:<a
    href="https://doi.org/10.1145/3832046.3832063">10.1145/3832046.3832063</a>
  apa: Kolmogorov, V., Naldi, S., &#38; Zapata, J. (2025). Certifying solutions of
    degenerate semidefinite programs. <i>ACM Communications in Computer Algebra</i>.
    ACM. <a href="https://doi.org/10.1145/3832046.3832063">https://doi.org/10.1145/3832046.3832063</a>
  chicago: Kolmogorov, Vladimir, Simone Naldi, and Jeferson Zapata. “Certifying Solutions
    of Degenerate Semidefinite Programs.” <i>ACM Communications in Computer Algebra</i>.
    ACM, 2025. <a href="https://doi.org/10.1145/3832046.3832063">https://doi.org/10.1145/3832046.3832063</a>.
  ieee: V. Kolmogorov, S. Naldi, and J. Zapata, “Certifying solutions of degenerate
    semidefinite programs,” <i>ACM Communications in Computer Algebra</i>, vol. 59,
    no. 4. ACM, pp. 147–152, 2025.
  ista: Kolmogorov V, Naldi S, Zapata J. 2025. Certifying solutions of degenerate
    semidefinite programs. ACM Communications in Computer Algebra. 59(4), 147–152.
  mla: Kolmogorov, Vladimir, et al. “Certifying Solutions of Degenerate Semidefinite
    Programs.” <i>ACM Communications in Computer Algebra</i>, vol. 59, no. 4, ACM,
    2025, pp. 147–52, doi:<a href="https://doi.org/10.1145/3832046.3832063">10.1145/3832046.3832063</a>.
  short: V. Kolmogorov, S. Naldi, J. Zapata, ACM Communications in Computer Algebra
    59 (2025) 147–152.
corr_author: '1'
date_created: 2026-08-30T22:01:44Z
date_published: 2025-12-01T00:00:00Z
date_updated: 2026-09-09T08:17:05Z
day: '01'
department:
- _id: VlKo
doi: 10.1145/3832046.3832063
external_id:
  unknown:
  - '2405.13625'
fulldoi: https://doi.org/10.1145/3832046.3832063
intvolume: '        59'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1145/3832046.3832063
month: '12'
oa: 1
oa_version: Published Version
page: 147-152
project:
- _id: 9B9290DE-BA93-11EA-9121-9846C619BF3A
  grant_number: W1260-N35
  name: Vienna Graduate School on Computational Optimization
publication: ACM Communications in Computer Algebra
publication_identifier:
  eissn:
  - 1932-2240
  issn:
  - 1932-2232
publication_status: published
publisher: ACM
scopus_import: '1'
status: public
title: Certifying solutions of degenerate semidefinite programs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 59
year: '2025'
...