Majorization & Polymatroids | The Leisure of the Theory

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 $x$ is an $n-$ vector, denote the $j^th$ largest component by $x_[j]$ . Let $x$ and $b$ be two vectors in $n$ dimensions. The vector $x$ is majorized by the vector $b$ if

$\sum_j \leq ix_[j] \leq \sum_j \leq ib_[j],\, \forall i \leq n-1$

$\sum_j=1^nx_[j] = \sum_j=1^nb_[j]$

In the typical application one is given a non-negative vector $b$ and the goal is to identify a vector $x$ that is majorized by $b$ to optimize a linear function of $x$ . The problem is easily formulated as a linear program. Suppose $b_1 \geq b_2 \geq \ldots \geq b_n \geq 0$ . Then, our goal is to maximize $cx$ subject to

$\sum_j \leq ix_j \leq \sum_j \leq ib_j\,\, \forall i \leq n-1$

$\sum_j=1^nx_j = \sum_j=1^nb_j$

$x_1 \geq x_2 \geq \ldots \geq x_n \geq 0$

A classic result of Hardy, Littlewood and Polya states that $x$ is majorized by $b$ iff there is a doubly-stochastic matrix $\Pi$ such that $x=\Pi b$ . By the Birkhoff-von Neumann theorem it means that the set of vectors majorized by $b$ is the convex hull of all permutations of $b$ , 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 $S \subseteq \1, \ldots, n\=N$ let $f(S) = \sum_j=1^b_j$ . Note that $f(S)$ depends only on the cardinality of $S$ and not $S$ itself. Given this, the optimization problem above can be expressed as

$\max cx$

subject to

$\sum_j=1^nx_j = f(N)$

$\sum_j \in Sx_j \leq f(S)\,\, \forall S \subset N$

$x_j \geq 0\,\, \forall j$

There is also a related `minorization’ problem that is of interest (see Akhil and Sundaresan (2016) for a survey):

$\min cx$

subject to

$\sum_j \leq ix_j \geq \sum_j \leq ib_j\,\, \forall i \leq n-1$

$\sum_j=1^nx_j = \sum_j=1^nb_j$

$x_1 \geq \ldots \geq x_n \geq 0$

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 $g(S) = \max \\sum_i=1^jb_i: \1, 2, \ldots, j\ \subseteq S\\,\, \forall S \subseteq N.$ In words $g(S) = \sum_i=1^jb_i$ if $j$ is the largest index such that the set $\1, 2, \ldots, j\$ is contained in $S$ . Otherwise $g(S)=0$ . Set $f(S) =g(N) - g(N \setminus S)$ The function $f(S)$ is non-decreasing and submodular on $N$ . The feasible region of the minorization problem can be expressed as

$\sum_j \in Sx_j \leq f(S)\,\, \forall S \subset N$

$\sum_j \in Nx_j = f(N)$

$x_1 \geq \ldots \geq x_n \geq 0$

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).