---
OA_place: publisher
_id: '21957'
abstract:
- lang: eng
  text: "This thesis investigates algorithmic certification and approximation methods
    for degenerate semidefinite programs (SDPs) and the singular roots of polynomial
    systems. In the first part, we present a hybrid symbolic-numeric algorithm for
    certifying the feasibility of weakly feasible, degenerate SDPs. By reformulating
    linear matrix inequalities (LMIs) into a structured polynomial system via facial
    reduction and incidence varieties, we guarantee the existence of an isolated exact
    solution. This algebraic reduction enables the certification of maximum-rank numerical
    approximations using methods from algebraic geometry.\r\n\r\nIn the second part,
    we address the severe ill-conditioning and loss of quadratic convergence that
    plague standard path-tracking methods near isolated singular roots. To overcome
    this, we propose tracking algorithms that achieve superlinear convergence without
    the computational bloat characteristic of classical deflation techniques. By modeling
    the solution path as a generalized fractional Puiseux series, our approach combines
    an explicitly derived algebraic predictor with a localized hyperplane desingularization
    phase during the corrector step. Furthermore, we introduce a continuous path-limit
    method and an extension of the geometric sequence rule to directly extract exact
    fractional exponents. This bypasses traditional heuristic trial-and-error methods
    and explicitly accommodates sparse series expansions. Numerical experiments confirm
    that our method significantly reduces the cumulative number of matrix inversions
    while achieving high-accuracy root approximations, even for heavily degenerate
    systems exhibiting higher coranks."
acknowledgement: 'Funding: Vienna Graduate School on Computational Optimization (FWF),
  grant DOI: 10.55776/W1260.'
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Jeferson
  full_name: Zapata, Jeferson
  id: 00223538-AF8F-11E9-A4C7-F729E6697425
  last_name: Zapata
citation:
  ama: 'Zapata J. Overcoming degeneracy and singularity: Techniques for semidefinite
    programs and homotopy continuation endgames. 2026. doi:<a href="https://doi.org/10.15479/AT-ISTA-21957">10.15479/AT-ISTA-21957</a>'
  apa: 'Zapata, J. (2026). <i>Overcoming degeneracy and singularity: Techniques for
    semidefinite programs and homotopy continuation endgames</i>. Institute of Science
    and Technology Austria. <a href="https://doi.org/10.15479/AT-ISTA-21957">https://doi.org/10.15479/AT-ISTA-21957</a>'
  chicago: 'Zapata, Jeferson. “Overcoming Degeneracy and Singularity: Techniques for
    Semidefinite Programs and Homotopy Continuation Endgames.” Institute of Science
    and Technology Austria, 2026. <a href="https://doi.org/10.15479/AT-ISTA-21957">https://doi.org/10.15479/AT-ISTA-21957</a>.'
  ieee: 'J. Zapata, “Overcoming degeneracy and singularity: Techniques for semidefinite
    programs and homotopy continuation endgames,” Institute of Science and Technology
    Austria, 2026.'
  ista: 'Zapata J. 2026. Overcoming degeneracy and singularity: Techniques for semidefinite
    programs and homotopy continuation endgames. Institute of Science and Technology
    Austria.'
  mla: 'Zapata, Jeferson. <i>Overcoming Degeneracy and Singularity: Techniques for
    Semidefinite Programs and Homotopy Continuation Endgames</i>. Institute of Science
    and Technology Austria, 2026, doi:<a href="https://doi.org/10.15479/AT-ISTA-21957">10.15479/AT-ISTA-21957</a>.'
  short: 'J. Zapata, Overcoming Degeneracy and Singularity: Techniques for Semidefinite
    Programs and Homotopy Continuation Endgames, Institute of Science and Technology
    Austria, 2026.'
corr_author: '1'
das_tickbox: '1'
date_created: 2026-06-08T13:29:52Z
date_published: 2026-06-09T00:00:00Z
date_updated: 2026-07-27T14:30:42Z
day: '09'
ddc:
- '500'
degree_awarded: PhD
department:
- _id: GradSch
- _id: VlKo
doi: 10.15479/AT-ISTA-21957
doi_confirm: '1'
file:
- access_level: closed
  checksum: b11a959e99d3dcf61040282b5c837141
  content_type: application/zip
  creator: jzapata
  date_created: 2026-06-08T13:20:02Z
  date_updated: 2026-06-08T13:20:02Z
  file_id: '21958'
  file_name: istaustriathesis_JZapata.zip
  file_size: 40811933
  relation: source_file
- access_level: open_access
  checksum: edf1e5899b2e31505cd1aa3fe8bd4b7f
  content_type: application/pdf
  creator: jzapata
  date_created: 2026-06-10T13:33:25Z
  date_updated: 2026-06-10T13:33:25Z
  file_id: '21992'
  file_name: 4_Final_Thesis_JZapata_REX.pdf
  file_size: 2207892
  relation: main_file
  success: 1
file_date_updated: 2026-06-10T13:33:25Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: '89'
project:
- _id: 9B9290DE-BA93-11EA-9121-9846C619BF3A
  grant_number: W1260-N35
  name: Vienna Graduate School on Computational Optimization
publication_identifier:
  isbn:
  - 978-3-99078-079-4
  issn:
  - 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
  record:
  - id: '21144'
    relation: part_of_dissertation
    status: public
status: public
supervisor:
- first_name: Vladimir
  full_name: Kolmogorov, Vladimir
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
title: 'Overcoming degeneracy and singularity: Techniques for semidefinite programs
  and homotopy continuation endgames'
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: dissertation
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2026'
...
---
OA_place: repository
OA_type: green
_id: '21144'
abstract:
- lang: eng
  text: 'This paper deals with the algorithmic aspects of solving feasibility problems
    of semidefinite programming (SDP), aka linear matrix inequalities (LMIs). Since
    in some SDP instances all feasible solutions have irrational entries, numerical
    solvers that work with rational numbers can only find an approximate solution.
    We study the following question: Is it possible to certify feasibility of a given
    SDP using an approximate solution that is sufficiently close to some exact solution?
    Existing approaches make the assumption that there exist rational feasible solutions
    (and use techniques such as rounding and lattice reduction algorithms). We propose
    an alternative approach that does not need this assumption. More specifically,
    we show how to construct a system of polynomial equations whose set of real solutions
    is guaranteed to have an isolated correct solution (assuming that the target exact
    solution is maximum-rank). This allows, in particular, for us to use algorithms
    from real algebraic geometry for solving systems of polynomial equations, yielding
    a hybrid (or symbolic-numerical) method for SDPs. We experimentally compare it
    with a pure symbolic method in [D. Henrion, S. Naldi, and M. Safey El Din, SIAM
    J. Optim., 26 (2016), pp. 2512–2539]; the hybrid method was able to certify feasibility
    of many SDP instances on which the aforementioned paper failed. Our approach may
    have further applications, such as refining an approximate solution using methods
    of numerical algebraic geometry for systems of polynomial equations.'
article_processing_charge: No
article_type: original
arxiv: 1
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>SIAM Journal on Optimization</i>. 2025;35(3):1630-1654. doi:<a href="https://doi.org/10.1137/24m1664691">10.1137/24m1664691</a>
  apa: Kolmogorov, V., Naldi, S., &#38; Zapata, J. (2025). Certifying solutions of
    degenerate semidefinite programs. <i>SIAM Journal on Optimization</i>. Society
    for Industrial and Applied Mathematics. <a href="https://doi.org/10.1137/24m1664691">https://doi.org/10.1137/24m1664691</a>
  chicago: Kolmogorov, Vladimir, Simone Naldi, and Jeferson Zapata. “Certifying Solutions
    of Degenerate Semidefinite Programs.” <i>SIAM Journal on Optimization</i>. Society
    for Industrial and Applied Mathematics, 2025. <a href="https://doi.org/10.1137/24m1664691">https://doi.org/10.1137/24m1664691</a>.
  ieee: V. Kolmogorov, S. Naldi, and J. Zapata, “Certifying solutions of degenerate
    semidefinite programs,” <i>SIAM Journal on Optimization</i>, vol. 35, no. 3. Society
    for Industrial and Applied Mathematics, pp. 1630–1654, 2025.
  ista: Kolmogorov V, Naldi S, Zapata J. 2025. Certifying solutions of degenerate
    semidefinite programs. SIAM Journal on Optimization. 35(3), 1630–1654.
  mla: Kolmogorov, Vladimir, et al. “Certifying Solutions of Degenerate Semidefinite
    Programs.” <i>SIAM Journal on Optimization</i>, vol. 35, no. 3, Society for Industrial
    and Applied Mathematics, 2025, pp. 1630–54, doi:<a href="https://doi.org/10.1137/24m1664691">10.1137/24m1664691</a>.
  short: V. Kolmogorov, S. Naldi, J. Zapata, SIAM Journal on Optimization 35 (2025)
    1630–1654.
date_created: 2026-02-05T13:33:05Z
date_published: 2025-09-01T00:00:00Z
date_updated: 2026-07-27T14:30:41Z
day: '01'
department:
- _id: VlKo
- _id: GradSch
doi: 10.1137/24m1664691
external_id:
  arxiv:
  - '2405.13625'
intvolume: '        35'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2405.13625
month: '09'
oa: 1
oa_version: Preprint
page: 1630-1654
publication: SIAM Journal on Optimization
publication_identifier:
  eissn:
  - 1095-7189
  issn:
  - 1052-6234
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
related_material:
  record:
  - id: '21957'
    relation: dissertation_contains
    status: public
status: public
title: Certifying solutions of degenerate semidefinite programs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 35
year: '2025'
...