A characterization of the algebraic degree in semidefinite programming
Consider the semidefinite programming (SDP) problem in the form \[ \text{maximize trace }(B \cdot Y )\text{ subject to }Y \in \mathcal U\text{ and }Y \succeq 0, \] where \(B\) is a real symmetric \(n \times n\)-matrix, \(\mathcal U\) is a \(m\)-dimensional affine subspace in the \(\binom{n+1}{2}\)-dimensional space of real \(n \times n\)-symmetric matrices, and \(Y \succeq 0\) means that \(Y\) is positive semidefinite. We know that the coordinates of the optimal solution are the roots of some univariate polynomials. If the data are generic, then the degree of these polynomials depends only on the rank \(r\) of the optimal solution. This is what we call the algebraic degree \(\delta (m, n,r)\) in the semidefinite programming. Note that the algebraic degree \(\delta (m, n,r)\) is well-defined only if the triple \((m, n,r)\) satisfies the following Pataki's inequalities \[ \binom{n-r+1}{2} \leq m \leq \binom{n+1}{2}-\binom{r+1}{2}. \] \textit{J. Nie} et al. [Math. Program. 122, No. 2 (A), 379--405 (2010; Zbl 1184.90119)] first introduced and showed that the algebraic degree \(\delta (m, n,r)\) in semidefinite programming coincides with a degree of a dual variety , by using methods from complex algebraic geometry. In particular, one of their main results was a collection of explicit formulas of the algebraic degree \(\delta (m, n,r)\) for various special values of \( m, n,r\) which was obtained via computing the Euler numbers of smooth varieties, the degrees of determinantal varieties, and so on. Moreover, they also gave a general formula of the algebraic degree \(\delta (m, n,r\)) which was conjectured to hold arbitrary values of \(m, n\) and \(r\). \par In this paper, the authors provide a combinatorial approach for calculating the algebraic degrees using doubly symmetric polynomials. More concretely, they show that the algebraic degree \(\delta (m, n,r)\) can be expressed in terms of the coefficient of a certain monomial in a doubly symmetric polynomial. By this characterization, the duality relation of the algebraic degree \(\delta (m, n,r)\) can be easily obtained. As an application, they apply this characterization to reprove many interesting results of Nie, Ranestad and Sturmfels via some facts about symmetric polynomials.
- A combinatorial proof of Dyson's conjecture
- A formula for the algebraic degree in semidefinite programming
- A general formula for the algebraic degree in semidefinite programming
- An identity involving symmetric polynomials and the geometry of Lagrangian Grassmannians
- An introduction to symmetric functions and their combinatorics
- scientific article; zbMATH DE number 1270593 (Why is no real title available?)
- scientific article; zbMATH DE number 1181673 (Why is no real title available?)
- Identities involving (doubly) symmetric polynomials and integrals over Grassmannians
- On Giambelli's theorem on complete correlations
- Sequences of Enumerative Geometry: Congruences and Asymptotics
- Symmetric functions, Schubert polynomials and degeneracy loci. Transl. from the French by John R. Swallow
- The algebraic degree of semidefinite programming
- The degree of \(\text{SO}(n,\mathbb{C})\)
- Algebraic degree in semidefinite and polynomial optimization
- On matrix algebras associated to sum-of-squares semidefinite programs
- A general formula for the algebraic degree in semidefinite programming
- Algebraic degree of polynomial optimization
- The algebraic degree of the Wasserstein distance
- The algebraic degree of semidefinite programming
This page was built for publication: A characterization of the algebraic degree in semidefinite programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6157477)
