Principal majorization ideals and optimization (Q5943030)

This paper considers problems motivated by the optimization of a quadratic function \(x^tAx\), where \(A\) is an \(n\times n\) real matrix. The approach is based on the study of the majorization ideal of a vector: A real vector \(a=(a_1,\ldots,a_n)\) with \(a_1\geq\ldots\geq a_n\) is majorized by another real vector \(b=(b_1,\ldots,b_n)\) with \(b_1\geq\ldots\geq b_n\), if \(\sum_{i=1}^j b_i\geq \sum_{i=1}^j a_i\) for all \(j\), and \(\sum_{i=1}^n b_i\geq \sum_{i=1}^n a_i\). The majorization ideal \(M(b)\) is the set of all vectors \(a\), for which a permutation of components is majorized by a permutation of \(b\). Geometrically, \(M(b)\) is a polytope. The main result of the paper is an algorithmic characterizations of quadratic optimization over \(M(b)\), for a class \(\mathcal D\) of matrices \(A\) that generalize positive semidefinite matrices. Furthermore, the paper describes a number of properties of \(\mathcal D\) that can serve as alternative characterizations, and it describes the geometry of the set \(\mathcal D\).