Principal majorization ideals and optimization (Q5943030): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0024-3795(01)00268-3 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2080217325 / rank | |||
Normal rank |
Latest revision as of 12:12, 30 July 2024
scientific article; zbMATH DE number 1642118
Language | Label | Description | Also known as |
---|---|---|---|
English | Principal majorization ideals and optimization |
scientific article; zbMATH DE number 1642118 |
Statements
Principal majorization ideals and optimization (English)
0 references
11 November 2002
0 references
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\).
0 references
majorization
0 references
convexity
0 references
polytopes
0 references
partition lattices
0 references
0 references