Principal majorization ideals and optimization
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\).
- A problem of Mirsky concerning nonsingular doubly stochastic matrices
- Directional-Quasi-Convexity, Asymmetric Schur-Convexity and Optimality of Consecutive Partitions
- Geometry of cuts and metrics
- scientific article; zbMATH DE number 3828715 (Why is no real title available?)
- Inequalities: theory of majorization and its applications
- Lectures on Polytopes
- Majorization polytopes
- The doubly stochastic matrices of a vector majorization
This page was built for publication: Principal majorization ideals and optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5943030)
