[{"title":"Overcoming degeneracy and singularity: Techniques for semidefinite programs and homotopy continuation endgames","file_date_updated":"2026-06-10T13:33:25Z","OA_place":"publisher","degree_awarded":"PhD","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>","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.","ista":"Zapata J. 2026. Overcoming degeneracy and singularity: Techniques for semidefinite programs and homotopy continuation endgames. Institute of Science and Technology Austria.","ieee":"J. Zapata, “Overcoming degeneracy and singularity: Techniques for semidefinite programs and homotopy continuation endgames,” Institute of Science and Technology Austria, 2026.","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>."},"related_material":{"record":[{"id":"21144","status":"public","relation":"part_of_dissertation"}]},"project":[{"grant_number":"W1260-N35","_id":"9B9290DE-BA93-11EA-9121-9846C619BF3A","name":"Vienna Graduate School on Computational Optimization"}],"_id":"21957","oa_version":"Published Version","has_accepted_license":"1","status":"public","publisher":"Institute of Science and Technology Austria","doi_confirm":"1","tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"publication_status":"published","acknowledgement":"Funding: Vienna Graduate School on Computational Optimization (FWF), grant DOI: 10.55776/W1260.","day":"09","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","alternative_title":["ISTA Thesis"],"publication_identifier":{"isbn":["978-3-99078-079-4"],"issn":["2663-337X"]},"year":"2026","author":[{"last_name":"Zapata","full_name":"Zapata, Jeferson","id":"00223538-AF8F-11E9-A4C7-F729E6697425","first_name":"Jeferson"}],"department":[{"_id":"GradSch"},{"_id":"VlKo"}],"date_created":"2026-06-08T13:29:52Z","language":[{"iso":"eng"}],"page":"89","file":[{"content_type":"application/zip","file_size":40811933,"creator":"jzapata","checksum":"b11a959e99d3dcf61040282b5c837141","date_created":"2026-06-08T13:20:02Z","relation":"source_file","file_name":"istaustriathesis_JZapata.zip","date_updated":"2026-06-08T13:20:02Z","access_level":"closed","file_id":"21958"},{"creator":"jzapata","checksum":"edf1e5899b2e31505cd1aa3fe8bd4b7f","date_created":"2026-06-10T13:33:25Z","file_size":2207892,"success":1,"content_type":"application/pdf","date_updated":"2026-06-10T13:33:25Z","access_level":"open_access","file_id":"21992","relation":"main_file","file_name":"4_Final_Thesis_JZapata_REX.pdf"}],"supervisor":[{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"}],"month":"06","das_tickbox":"1","doi":"10.15479/AT-ISTA-21957","oa":1,"date_updated":"2026-07-27T14:30:42Z","article_processing_charge":"No","date_published":"2026-06-09T00:00:00Z","type":"dissertation","ddc":["500"],"corr_author":"1","abstract":[{"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.","lang":"eng"}]},{"title":"Certifying solutions of degenerate semidefinite programs","OA_place":"repository","citation":{"ista":"Kolmogorov V, Naldi S, Zapata J. 2025. Certifying solutions of degenerate semidefinite programs. SIAM Journal on Optimization. 35(3), 1630–1654.","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.","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>.","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.","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>","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>"},"related_material":{"record":[{"id":"21957","status":"public","relation":"dissertation_contains"}]},"oa_version":"Preprint","_id":"21144","status":"public","publisher":"Society for Industrial and Applied Mathematics","external_id":{"arxiv":["2405.13625"]},"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","publication_identifier":{"issn":["1052-6234"],"eissn":["1095-7189"]},"year":"2025","author":[{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Simone","last_name":"Naldi","full_name":"Naldi, Simone"},{"first_name":"Jeferson","id":"00223538-AF8F-11E9-A4C7-F729E6697425","full_name":"Zapata, Jeferson","last_name":"Zapata"}],"date_created":"2026-02-05T13:33:05Z","language":[{"iso":"eng"}],"department":[{"_id":"VlKo"},{"_id":"GradSch"}],"page":"1630-1654","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2405.13625"}],"month":"09","issue":"3","doi":"10.1137/24m1664691","volume":35,"oa":1,"date_updated":"2026-07-27T14:30:41Z","article_processing_charge":"No","date_published":"2025-09-01T00:00:00Z","arxiv":1,"OA_type":"green","type":"journal_article","publication":"SIAM Journal on Optimization","intvolume":"        35","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."}],"quality_controlled":"1","article_type":"original"}]