Certifying Solutions of Degenerate Semidefinite Programs.
Saved in:
| Title: | Certifying Solutions of Degenerate Semidefinite Programs. |
|---|---|
| Authors: | Kolmogorov, Vladimir1 (AUTHOR) vnk@ist.ac.at, Naldi, Simone2 (AUTHOR) simone.naldi@unilim.fr, Zapata, Jeferson1 (AUTHOR) Jeferson.Zapata@ist.ac.at |
| Source: | SIAM Journal on Optimization. 2025, Vol. 35 Issue 3, p1630-1654. 25p. |
| Subjects: | Semidefinite programming, Optimization algorithms, Feasibility studies, Algorithms, Heuristic, Algebraic geometry, Polynomials |
| Abstract: | 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. [ABSTRACT FROM AUTHOR] |
| Copyright of SIAM Journal on Optimization is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 189109889 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Certifying Solutions of Degenerate Semidefinite Programs. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Kolmogorov%2C+Vladimir%22">Kolmogorov, Vladimir</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> vnk@ist.ac.at</i><br /><searchLink fieldCode="AR" term="%22Naldi%2C+Simone%22">Naldi, Simone</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> simone.naldi@unilim.fr</i><br /><searchLink fieldCode="AR" term="%22Zapata%2C+Jeferson%22">Zapata, Jeferson</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> Jeferson.Zapata@ist.ac.at</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22SIAM+Journal+on+Optimization%22">SIAM Journal on Optimization</searchLink>. 2025, Vol. 35 Issue 3, p1630-1654. 25p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Semidefinite+programming%22">Semidefinite programming</searchLink><br /><searchLink fieldCode="DE" term="%22Optimization+algorithms%22">Optimization algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Feasibility+studies%22">Feasibility studies</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Heuristic%22">Heuristic</searchLink><br /><searchLink fieldCode="DE" term="%22Algebraic+geometry%22">Algebraic geometry</searchLink><br /><searchLink fieldCode="DE" term="%22Polynomials%22">Polynomials</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of SIAM Journal on Optimization is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=189109889 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1137/24M1664691 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 25 StartPage: 1630 Subjects: – SubjectFull: Semidefinite programming Type: general – SubjectFull: Optimization algorithms Type: general – SubjectFull: Feasibility studies Type: general – SubjectFull: Algorithms Type: general – SubjectFull: Heuristic Type: general – SubjectFull: Algebraic geometry Type: general – SubjectFull: Polynomials Type: general Titles: – TitleFull: Certifying Solutions of Degenerate Semidefinite Programs. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Kolmogorov, Vladimir – PersonEntity: Name: NameFull: Naldi, Simone – PersonEntity: Name: NameFull: Zapata, Jeferson IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 07 Text: 2025 Type: published Y: 2025 Identifiers: – Type: issn-print Value: 10526234 Numbering: – Type: volume Value: 35 – Type: issue Value: 3 Titles: – TitleFull: SIAM Journal on Optimization Type: main |
| ResultId | 1 |
