A characterization of the algebraic degree in semidefinite programming (Q6157477): Difference between revisions

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.