The majorization relationship arises frequently in Economic applications, most recently in the context of information design (see Kleiner, Moldovanu and Strack (2021) for instance). This post highlights the connection between optimization problems involving the majorization relationship and polymatroid optimization problems.
The majorization relationship is a partial order on vectors. If is an vector, denote the largest component by . Let and be two vectors in dimensions. The vector is majorized by the vector if
In the typical application one is given a non-negative vector and the goal is to identify a vector that is majorized by to optimize a linear function of . The problem is easily formulated as a linear program. Suppose . Then, our goal is to maximize subject to
A classic result of Hardy, Littlewood and Polya states that is majorized by iff there is a doubly-stochastic matrix such that . By the Birkhoff-von Neumann theorem it means that the set of vectors majorized by is the convex hull of all permutations of , i.e., a permutahedron. Permutahedra are polymatroids (see, for example, Kuipers, Vermeulen and Voorneveld (2010)). Therefore, we can reformulate the linear program above as a polymatroid optimization problem which can be solved via a greedy algorithm. Dahl (2010) gives the underlying submodular function that describes the polymatroid. For each let . Note that depends only on the cardinality of and not itself. Given this, the optimization problem above can be expressed as
There is also a related `minorization’ problem that is of interest (see Akhil and Sundaresan (2016) for a survey):
Dahl (2001) characterizes the extreme points of the feasible region of this program. Morton, von Randow, Ringwald (1985) show that its feasible region can be described as a polymatroid with monotonicity constraints. Set In words if is the largest index such that the set is contained in . Otherwise . Set The function is non-decreasing and submodular on . The feasible region of the minorization problem can be expressed as
Charactertizing the structure of the optimal solution is straightforward. It involves the `pooling’ of some variables. Variables are partitioned into sets consisting of a consecutive sequence of indices. Within each of these sets the variables are equal. Variables from sets with lower’ indices will of course have higher values than variables from sets with larger indices.
For the more general problem of optimizing a linear function over the intersection of a polymatroid and an affine space, see Hartvigsen (1998).