Polyhedra and optimization in connection with a weak majorization ordering

UNIVERSITY OF OSLO Department of informatics

Polyhedra and Optimization in Connection with a Weak Majorization Ordering

Geir Dahl

Preprint 10

December 12, 1994

Polyhedra and Optimization in Connection with a Weak Majorization Ordering

Geir Dahl

December 12, 1994

Abstract

We introduce the concept of weakk-majorization extending the clas- sical notion of weak sub-majorization. For integers kandn withkn a vectorx^2Rn is weakly k-majorized by a vectorq ^2Rk if the sum of ther largest components of xdoes not exceed the sum of ther largest components ofq, forr= 1;:::;k. For a givenqthe set of vectors weakly k-majorized byq denes a polyhedronP(q;k), and we determine all its vertices. We also determine the vertices and a complete and nonredun- dant linear description of the integer hull ofP(q;k). The results are used to give simple and ecient (polynomial time) algorithms for associated linear and integer linear programming problems.

Keywords:Majorization; polyhedral combinatorics.

1 Introduction

The concept of majorization has been investigated in a number ofbranches of mathematics and statistics. The notion reects to what extent compo- nents of vectors are spread out. Forp;q^2Rnone says thatpis weakly sub-majorizedbyqif^Pr_j⁼¹p^[j^]Pr

j⁼¹q^[j^]forr= 1;:::;n. Herep^[j^]de- notes thej'th largest component ofp. If also^Pn_j⁼¹pj=^Pn_j⁼¹qj holds, p is majorized by q and we write p q. Several equivalent conditions for (weak sub-) majorization are known (see [8]); for instance, pq i there is a doubly stochastic matrix M ^{2 Rn;n} (i.e. M has nonnegative elements and all row and column sums are 1) with p=Mq. This result can be combined with a theorem of Birkho and von Neumann to give the following geometric interpretation of majorization: pq if and only ifp lies in the convex hull of the set of vectors obtained by permuting the components ofq. The Birkho-von Neumann theorem says that the set of doubly stochastic matrices in ^Rn;n is the convex hull of the set of

Institute of Informatics, University of Oslo, P.O.Box 1080, Blindern, 0316 Oslo, Norway (Email:[email protected])

all permutation matrices, i.e. nn matrices where each row and each column consists of all zeros except for one entry which is 1. A similar characterization holds for weak submajorization, see [8].

An extensive treatment of the theory of majorization as well as its applications is given in the book by Marshall and Olkin [8]. An example of majorization in combinatorial analysis is the theoremofGale and Ryser.

It characterizes those vectorsrandcfor which there is a 0/1 matrix with row sumsr(i.e.,i'th row sum isri) and column sumsc; the condition is a simple majorization condition in terms ofcandr. A relation between edge coloring and majorization is discussed in [4]. Majorization also arises in e.g. matrix theory (Hadamard type inequalities, singular values etc.), numerical analysis (condition numbers, matrix approximation etc.) as well as in probability theory and statistics (reliability, stochastic ordering etc.), see [8] .

For generalizations of majorization within a measure theoretical frame- work as well as statistical interpretations, see the extensive treatment in [11]. In [2] approximate majorization is studied.

A central concept in the theory of majorization is that of a Schur- convex function. A function:^Rn!Rthat preserves the ordering given by majorization is called Schur-convex, thus(x)(q) wheneverxq. Thereforeqmaximizes(x) over the setxq, so maximization of Schur- convex functions is easy. The following general method has produced interesting inequalities in the areas mentioned above, see [8]: nd some (simple) underlying majorization which combined with a suitable Schur- convex function leads to the inequality. A simple example, which is useful in this work, is the rearrangement inequality due to Hardy, Littlewood and Polya, see [7], [8]. Leta¹;:::;an and b¹;:::;bn be real numbers. Then

we have: _n

X

i⁼¹a^[i^]b^[n^,i^+1]Xn

i⁼¹aibiXn

i⁼¹a^[i^]b^[i^]: (1) In this paper we study a majorization concept derived from weak sub- majorization by requiring that the ordering of the rlargest components of vectors only hold for r k wherek is some number not exceeding n. This concept, called weakk-majorization, is therefore a weaker notion than weak sub-majorization and it measures the concentration of sums of subvectors up to a given size. Unlike for Schur-convex functions, opti- mization with a weakk-majorization constraint is not a trivial task, and a main purpose of this paper is to study such optimization problems.

This paper is organized as follows. In section 2 we introduce weakk- majorization and describe some ofits basicproperties. Weintroduce linear programming (LP) problems with a weak k-majorization constraint and consider the special casek=nin some detail. In section 3 we study, for k < n,k-majorization polyhedra being the feasible set of these LP prob- lems, and determine all the vertices of these. This also leads to a simple (polynomial) algorithm for solving such LP problems. The remaining part of the paper treats integer linear programming (ILP) problems over the mentioned polyhedra, and vertices as well as complete linear descriptions

are given for the integer hull ofk-majorization polyhedra. Also a linear time algorithm for solving integer linear programming problems with a weakk-majorization constraint is given.

Notation.

^R,^Zand^Qdenote the set of real, integral and rational numbers, respectively, and ^Rm;n is the set of realmn matrices. For q ^{2 Rk} we dene the tail average qs^:k := (1=(k^,s+ 1))^Pk_j⁼_sqj. For each positive integer t we let ^Nt := ^f1;:::;t^g, and for x ^{2 Rn}, x^[j^] is the j'th largest component ofx. When S ^Nn we let ^jS^jdenote the cardinality ofS, and ifx^2Rnwe denex(S) :=^P_j²_Sxj. For concepts and results concerning polyhedra and linear inequalities, see [10]. The characteristic cone of a polyhedron P is denoted by char.cone(P). A pointed polyhedron is integral if all its vertices are integral. The integer hullPI of a (rational) polyhedronP is the polyhedron being the convex hull of all the integral points inP. A setA^Rnis symmetric ifx²A whenever x ² A and is a permutation on^Nn (i.e. a bijection) and where we denex= (x⁽¹⁾;:::;x⁽n⁾). For integersr;s withrs we letCr;s^2Rs;sdenote the 0/1-circulant matrix with elements 0 and 1 and where the ones in rowiare in the positionsj i;i+ 1;:::;i+ (r^,1) mod(s) (sorconsecutive ones are shifted one position to the right for each row). We letei^2Rn be thei'th unit (coordinate) vector in^Rn, i.e., the i'th component ofeiis 1 and all other components are 0.

2 Weak

^k

-majorization and optimization

We study basic properties of weakk-majorization. Associated optimiza- tion problems and polyhedra are also introduced, and the special case k=nis treated in some detail.

Let, throughout this section,k andnbe two given integers such that kn, and letq^2Rk be a given vector called the majorant. We extend the concept of weak sub-majorization intok-majorizationas follows. We say that x ^{2 Rn} is weakly k-majorized by q and write p k q if the following conditions hold:

Pr

j⁼¹x^[j^]Pr

j⁼¹q^[j^] for allr^2Nk: (2) The order of the components in the vectors xandqis irrelevant in this denition, so ifxkq, then alsox⁰kq⁰wherex⁰andq⁰are permutations ofxandq, respectively. We see thatx¹q i maxjxj maxjqj, and that x n q means that x is weakly sub-majorized by q. We also see that, for general k,xk q ix^[k]is weakly sub-majorized byq^[k]where x^[k]= (x^[1];:::;x^[k^]) andq^[k]= (q^[1];:::;q^[k^]). Thus weakk-majorization corresponds to weak sub-majorization on the vectors consisting of the k largest components. Therefore one can formulate equivalent conditions forxk q in terms ofx^[k]andq^[k]. For instance,xk q if and only if there is a doubly stochastic matrixM^2Rk;k such thatx^[k]=q^[k]M.

For z ^{2 Rn} we dene the real-valued function Lz on the interval [0;1] by (i) Lz(r=k) = ^Pr_j⁼¹z^[j^] for r = 0;:::;k, and (ii) Lz is linear

on each subinterval [r=k;(r+ 1)=k], for r = 0;:::;k^,1. This function is piecewise linear, continuous and concave, and it satises Lz(0) = 0, Lz(1) = ^Pk_j⁼¹z^[j^]. We call Lz the L-function associated with z. The dependency onk is suppressed in the notationLz ask is clear from the context. We mention that in [8] Lorentz-curves are discussed, they are similar to ourL-curves dened below but with opposite ordering of the components. TheL-curveassociated withzis the graph ofLz. Majoriza- tion concepts may be described in terms ofL-functions as follows:xkq if and only ifLx Lq (with componentwise ordering), i.e. theL-curve associated withxlies below theL-curve associated withq.

Our main interest is to study optimization problems with a majoriza- tion constraint and with a linear (and nonsymmetric) objective function.

The objective function in our dierent problems will bec^Tx=^Pn_j⁼¹cjxj

which is to be maximized over all vectorsx^2Rn(orx^2Zn) that satisfy ak-majorization constraint. Thus, for instance, we shall study the set of points in^Rnthat are weaklyk-majorized by some vectorq.

We assume hereafter thatq satisesq¹:::qk 0. Letc ^2Rn be a nonnegative objective function. Consider the following optimization problem:

max^fc^Tx^jxkq^g: (3)

A possible interpretation of this problem isas follows. Considernprojects, numbered from 1 ton, and assume thatcjis an expected value or prot associated with projectj. Let the variablexjrepresent the investment in project j. To keep down the overall risk of investing in failure projects , one may require that the investments are suitably spread out. This requirement may be implemented by saying that the investment vector x= (x¹;:::;xn) is weaklyk-majorized by a given vectorq. This prevents investing too much in a single project, too much in any pair of projects etc. The risk aversion may be reected in the choice ofk andq.

Let P(q;k) denote the set of feasible solutions in the optimization problem (3), soP(q;k) =^fx^{2 Rn j}xk q^g. Note that xk qif and only ifx(S)q(^Nr) for each subsetSof^Nnwith^jS^j=rkbecause the maximum value ofx(S) taken over all such subsets is^Pr_j⁼¹x^[j^](confer the rearrangement inequality). It follows that the setP(q;k) is a polyhedron, in fact

P(q;k) =^fx^2Rnjx(S)q(^Nr) for allS ^Nnwithr=^jS^jk^g: (4) The polyhedronP(q;k), called ak-majorization polyhedron, is unbounded, its characteristic cone is^,Rnand it is pointed, i.e. its minimal faces are vertices. Furthermore,P(q;k) is symmetric.

Eachn-majorization polyhedron may be viewed as a polymatroid (see e.g. [5], [6]). Dene the set functionf(S) =^Pr_j⁼¹qj for eachS ^Nn

wherer :=^jS^j. Then it follows from the assumption q¹:::qk 0 that: (i) f is monotone, i.e., f(S) f(T) for S T ^Nn, (ii) f is submodular, i.e.,f(S^[T) +f(S^\T)f(S) +f(T) for allS;T ^Nn, and (iii) f is nonnegative. From (4) we see that P(q;n) = ^fx ^{2 Rn j}

x(S)f(S) for allS^Nn^g, so this is the polymatroid associated with the submodular function f. Edmonds (see [3]) showed that maximizing a nonnegative linear objective function over a polymatroid can be done using the greedy algorithm. Thus, in the case k = n, we can solve the problem (3) by the following greedy algorithm (assume for simplicity that c¹ ::: cn 0): x¹ = f(^f1^g) = q¹, x² = f(^f1;2^g)^,f(^f1^g) = (q¹+q²)^,q¹=q²,:::,xn=f(^Nn)^,f(^Nn^,1) =qn. The optimality of this solution could also be seen as a direct consequence of the rearrangement inequality (1). For k < n, however,P(q;k) may not be a polymatroid and therefore the greedy solution which isxj=qj forjk andxj=qk

for j > kmay not be optimal in (3). As a simple example, let n = 3, k = 2, q = (2;1) andc = (1;1;1). The greedy algorithm produces the nonoptimal solution (2;1;1) while the optimal solution is (3=2;3=2;3=2).

In the next section we shall explain how to repair this by giving an algorithm that solves (3) for generalk. This development will be done by studying properties of thek-majorization polyhedra.

It turns out thatn-majorization polyhedra have a simple, but interest- ing combinatorial structure as briey discussed next. Consider the face M(q;n) ofP(q;n) induced by the valid inequality x(^Nn) q(^Nn), i.e.

M(q;n) =^fx²P(q;n)^jx(^Nn) =q(^Nn)^g. ThenM(q;n) consists of all vectors xthat are majorized by q and it is the base polyhedron of the polymatroid P(q;n). M(q;k) is bounded polyhedron, i.e. a polytope, and its extreme points are all the n! permutations ofq. Assuming that q¹> ::: > qn >0, it can be shown that dim(M(q;k)) =n^,1 and that the linear system x(^Nn) = ^Pn_j⁼¹qj, x(S) ^Pr_j⁼¹qj for all S ^Nn, r:=^jS^jgives a complete and nonredundant linear description ofM(q;n).

Two vertices are adjacent on M(q;n) (i.e., there is a 1-dimensional face containing both vertices) if and only if the permutations (ofq) dening the two vertices dier by an adjacent transposition. Finally, M(q;n) is simple, meaning that each vertex is contained in (the minimum number of) n facets. An interesting special case is when q = (n;n^,1;:::;1).

ThenM(q;n) is called the permutahedron, see [1], [12]. All the properties described above forM(q;n) are well known to hold for the permutahe- dron. In fact, one can show that (forq¹> ::: > qn>0)M(q;n) and the permutahedron are combinatorially equivalent.

The remaining part of this paper is devoted to the study of P(q;k) wheneverk < n.

3 Vertices of

^k

-majorization polyhedra

In this section we nd all the vertices of the k-majorization polyhedron P(q;k). Throughout this section we assume that k < n and also (to avoid degenerate situations) that the given majorant q ^{2 Rk} satises q¹> ::: > qk>0. We deneQ=^Pk_j⁼¹qj.

Dene, fors= 0;:::;k^,1, the vectorw^s, called thes'thq-averageby w^s:= (q¹;:::;qs;qs^+1:k;:::;qs^+1:k) (5)

Note the special cases w⁰ = ( q^1:k;:::;q^1:k) and w^k,1 = (q¹;q²;:::;qk; :::;qk) and that^Pk_j⁼¹wsj = Qas we have ^Ps_j⁼¹qj+ (k^,s) qs^+1:k =

Pk

j⁼¹qj =Q. We also observe that w^s k q. In fact, theL-functions Lw^s andLq (associated withw^sandq, respectively) coincide on [0;s=k] andLw^s(1) =Lq(1). SinceLw^s is linear on [s=k;1] andLq is concave, it follows thatLw^s Lq and thereforew^s k q. Note that, among the vectors that are weaklyk-majorized byq, theq-averagew^sis maximally spread out in its rstkcomponents and minimally spread out (constant) in its remaining components.

The main result of this section says that the vertices ofP(q;k) are the permutations of theq-averages. In order to prove this result we shall need a lemma on tail averages which will be of use later as well.

Lemma 1

Letc= (c¹;:::;ck)^2Rk satisfyc¹:::ck^,1(note thatck

may be arbitrary). Then there is anm^2f1;:::;k^gsuch that

c^1:k:::cm^:kcm^+1:k:::ck^:k=ck: (6)

Proof.

Fort= 1;:::;k^,1 the following relation holds between consecu- tive tail averages: ct^:k=ct=(k^,t+1)+ ct^+1:k(k^,t)=(k^,t+1). Thus ct^:k

is a convex combination ofctand ct^+1:k which leads to, fort= 1;:::;k, (i) ctct^+1:k ⁾ ctct^:kct^+1:k;

(ii) ctct^+1:k ⁾ ctct^:kct^+1:k: ⁽⁷⁾ Let t= k^,1. While ct ct^+1:k andt 1 sett := t^,1 and repeat this procedure. Assume that we here terminate with t=t⁰. If t⁰ = 1 , (7)(i) gives c^1:k :::ck^:k, so (6) holds withm= 1. Ift⁰>1, we have (again by (7)(i))ct⁰ >ct^0+1:k:::ck^:k, and then (7)(ii)) implies that ct^0:kct^0+1:k. Sincecis nonincreasing, we can repeatedly use (7)(ii) and thereby obtain (6) withm=t⁰+ 1.

Theorem 2

The vertex set ofP(q;k) is the setW(q;k) of vectors that can be obtained as permutations of somew^s fors^2f0;:::;k^,1^g.

Proof.

We rst show that each vertex ofP(q;k) lies inW(q;k). by prov- ing that each bounded LP problem overP(q;k) has an optimal solution lying inW(q;k). Letd^2Rn be an objective function and consider the LP problem max^fd^Tx^jx²P(q;k)^g. If somedj <0, then the problem is unbounded asej²P(q;k) for each0. We may therefore assume thatd¹:::dn0. From the rearrangement inequality (1) and the fact that only thek largest components ofxdetermine the feasibility of a point, we may assume that x¹ :::xk = :::=xn. Thus our LP

problem reduces another LP problem max ^Pk_j⁼¹cjxj

subject to

(i) x(^Nr)q(^Nr) forr= 1;:::;k; (ii) xj^+1,xj0 forj= 1;:::;k^,1;

(8)

where we dene cj =dj forj = 1;:::;k^,1 and ck = ^Pn_j⁼_kdj. Note that we here have c¹ ::: ck^,1 whileck can have any value (not exceeding (n^,k+1)dk). The LP dual of this problem is

min ^Pk_i⁼¹yi^Pi j⁼¹qj

subject to

(i) ^Pk_i⁼_ryi+zr^,1,zr=cr forr= 1;:::;k; (ii) y¹;:::;yk;z¹;:::;zk^,10 ( andz⁰=zk= 0):

(9) The variablesz⁰andzkare used for notational simplicity only; these are not variables in the dual problem. We now apply Lemma 1 to the objective functioncand letmbe such that the inequalities (6) hold. Lets=m^,1, and observe thats^2f0;:::;k^,1^g. Let x^2Rkand (y;z)^2RkRk,1 be given by

(i) xj=

qj forj= 1;:::;s, qs^+1:k forj=s+ 1;:::;k; (ii) yj=

8

>

<

>

:

cj^,cj⁺¹ forj= 1;:::;s^,1, cs^,cs^+1:k forj=s,

0 forj=s+1;:::;k^,1, cs^+1:k forj=k;

(iii) zj=

0 forj= 1;:::;s,

(k^,j)( cj^+1:k^,cs^+1:k) forj=s+1;:::;k^,1.

The solution xcan be viewed as the projection ofw^s into the space of the rstkvariables, which implies that xis feasible in (8). We next show that (y;z) is feasible in the dual problem (9). Clearly, yj 0 forj < s since cj cj⁺¹. Also, ys =cs^,cs^+1:k 0 according to our choice of s; see Lemma 1 and (7). The remaining components of y are trivially nonnegative, and therefore y0. It follows from Lemma 1 that z0.

It remains to verify that (y;z) satises constraint (9)(i). Ifrs+ 2, we have^Pk_i⁼_ryi+ zr^,1,zr= cs^+1:k+ (k^,r+ 1)( cr^:k^,cs^+1:k)^,(k^, r)( cr^+1:k^,cs^+1:k) = (k^,r+1) cr^:k^,(k^,r) cr^+1:k=cr. Next, ifr=s+1, we obtain^Pk_i⁼_s⁺¹yi+ zs^,zs⁺¹= cs^+1:k^,(k^,s^,1)( cs^+2:k^,cs^+1:k) = (k^,s) cs^+1:k^,(k^,s^,1) cs^+2:k = cs⁺¹. Finally, when r s we have

Pk

i⁼ryi+ zr^,1,zr = ^Ps_i^=,1_r(ci^,ci^,1) +cs^,cs^+1:k+ cs^+1:k = (cr^,

cr⁺¹)+(cr^+1,cr⁺²)+:::+(cs^,1,cs)+cs=cr. This proves that (y;z) is dual feasible.

The value of the (primal) objective function of (8) in the point xis

Pk

j⁼¹cjxj=^Ps_i⁼¹ciqi+(1=(k^,s))^Pk_i⁼_s⁺¹qi^Pk

j⁼s⁺¹cj=^Ps_i⁼¹ciqi+ cs^+1:k^Pk

j⁼s⁺¹qj. The value of the (dual) objective function of (9) in the point (y;z) is^Pk_i⁼¹yi^Pi

j⁼¹qj = ^Ps_i^=1,1(ci^,ci⁺¹)^Pi_j⁼¹qj+ (cs^,

cs^+1:k)^Ps_j⁼¹qj+ cs^+1:k^Pk

j⁼¹qj=^Ps_j⁼¹cjqj+ cs^+1:k^Pk

j⁼s⁺¹qj. We see that these two values coincide. Therefore, by linear programming duality, it follows that xis optimal in the primal problem (8) and (y;z) is optimal in (9). It follows from the initial problem reduction thatw^sis an optimal solution of max^fd^Tx ^j x ² P(q;k)^g, which proves that each vertex of P(q;k) lies inW(q;k).

To complete the proof we must show that each point in W(q;k) is indeed a vertex ofP(q;k). To do this, assume that somew^sis a convex combination with strictly positive weights of other points z^{m 2}W(q;k), m = 1;:::;N, i.e. w^s = ^PN_m^=1mz^m with ^m > 0 and ^P_m^m = 1.

Since all these points satisfyx¹q¹andw^s1=q¹, we must havez^1r=q¹ for all r. Using a similar argument we can prove thatzrj =qj forj s. All the points z^m lie in P(q;k) so they satisfy the valid inequality x(^Nk) Q, andw^s satises this inequality with equality. This implies thatz^r(^Nk) =Qand therefore by the concavity of theL-functionsLz^r

Lw^s. If one of these inequalities were strict, this would contradict that w^s = ^PN_m^=1mz^m. Thus, Lz^r = Lw^s for all m, from which we get z^m=w^s form= 1;:::;N. This proves thatw^s is an extreme point of P(q;k), and it is therefore also a vertex of this polyhedron. Similarly, we can prove that each permutation ofw^sis a vertex ofP(q;k) and the proof is complete.

An interesting consequence of Theorem 2 is a simple algorithm for solving max ^fc^Tx ^jx k q^g. Initially the components ofc are ordered decreasingly; this can be done in timeO(n²). Assume for simplicity that c is nonincreasing. Next we determine an index m as in Lemma 1 and lets=m^,1. Thenw^s is an optimal solution of the problem! Here the calculation of m is done in linear time by recursive calculations of tail averages. Thus the main work in the algorithm is simply the ordering of the objective function.

We remark that Theorem2 can also be proved by a more direct method without using LP duality. In fact, one can show that ifx is an optimal solution of (8) satisfyingx(^Ns) =q(^Ns) for somes^2f0;:::;k^,1^g, then we can nd an optimal solution xsatisfying xj=qjforrs. By choos- ings maximal with this property, one can nd another optimal solution x satisfying x(^Nk) = ^Pk_j⁼¹qj and with all the remaining components xs⁺¹;:::;xnequal; this solution xis precisely theq-averagew^s.

From Theorem 2 we also obtain an inner description of weakk-major- ization polyhedra by using the fact that the characteristic cone ofP(q;k) is^,Rn.

Corollary 3

P(q;k) = conv(W(q;k))^,Rn, i.e., xk q if and only if x z for some z ^{2 Rn} which is a convex combination of permuted q-

averages.

In Fig.1 we illstrate the intersection betweenP(q;k) and the nonneg- ative orthant fork = 2, n = 3 and q = (2;1). The dierent permuted q-averages are shown.

(2,1,1)

(1,2,1) (3/2,3/2,3/2) (1,1,2)

Figure1: Example,^{P(q ;k )\Rn}.

4 Weak

^k

-majorization and integrality

In this section we study integer linear programming problems with a weak k-majorization constraint. These problems may be motivated by applica- tions concerning e.g. the distribution of indivisible units to locations or projects where it may be natural to impose a majorization constraint to assure a certain level of diversication. Our approach is to study the integer hull of the polyhedronP(q;k) and determine its vertices.

Hereafterk and n are integers satisfyingk < n and the majorant q satises q¹ > ::: > qk > 0. We are interested in the following integer linear programming problem

max^fc^Tx^jxkq;xis integral^g: (10) Note that the feasible set is hereP(q;k)^\Zn. If somecjis negative, then (10) is unbounded, so we hereafter assume thatc¹:::cn. Note that the LP relaxation max^fc^Tx^jx²P(q;k)^gmay have (a unique) optimal solution that is fractional. For instance, consider again the examplen= 3, k = 2,q = (2;1) andc^T = (1;1;1). The optimal solution in P(q;k) is (3=2;3=2;3=2), while the optimal integral solution is (2;1;1).

We observe that the feasible set of (10) is unchanged if we perform integer round-down on each component of the majorantq. Thus we shall hereafter assume thatqis integral (this also strengthen the LP relaxation).

The integer hullQ(q;k) ofP(q;k) is the convex hull of the feasible set in (10), i.e.,

Q(q;k) = conv(^fx^2Rnjxkq;xis integral^g): (11) From general polyhedral theory (see [10]) we know thatQ(q;k)is a polyhe- dron, i.e., it is the solution set of a nite set of linear inequalities. Q(q;k) is pointed and its characteristic cone is^,Rn. Furthermore it is easy to see thatQ(q;k) is symmetric. Note that the problem (10) may be viewed as maximizingc^TxoverQ(q;k).

Some more notation is needed. Let m^max =^bq^1:k^c =^bQ=k^c (recall that Q = ^Pk_j⁼¹qj). For each nonnegative m m^max we dene the following magnitudes

s^m= max^fs < k^jqs^+1:km^g;

m=^Pk_j⁼_sm⁺¹qj^,(k^,s^m,1)m;

q^m= (q¹;:::;qs^m;^m;m;:::;m)^2Rn.

We call q^m a rounded q-averagedue to its near resemblance to the q- averagesw^s(seesection 3). The rsts^mcomponentsaremaximally spread out (w.r.t. q) while the remaining components are minimally spread out:

they are all equal except for the (s^m+ 1)'th which may be viewed as an integrality correction. Observe that if m qk, then s^m = k^,1 andq^m= (q¹;:::;qk;m;:::;m). Finally, we note that ifm := qs^+1:k is integral, thens^m=sandq^m=w^s. Some basic properties ofq^mare given next.

Lemma 4

Let mbe a nonnegative integer withmm^max. Thenq^mis integral, nonincreasing and q^mkq. Furthermoreq^m(^Nk) =Q.

Proof.

It is clear that q^m is integral. To prove that the components of q^m are nonincreasing we shall bound ^m. Let s = s^m. Then we have^m =^Pk_j⁼_s⁺¹qj^,(k^,s^,1)m = (k^,s)( qs^+1:k^,m) +mm because k^,s 1 and qs^+1:k m (due to the denition of s = s^m).

Furthermore^m =^Pk_j⁼_s⁺¹qj^,(k^,s^,1)m ^Pk_j⁼_s⁺¹qj^,(k^,s^, 1) qs^+2:k = ^Pk_j⁼_s⁺¹qj^,Pk

j⁼s⁺²qj = qs⁺¹ < qs. Thusqs > ^m m andq^mis nonincreasing. To prove the majorization, we rst observe that whenj s we haveq^m(^Nj) =q(^Nj) and by the rst part of the proof q^m(^Ns⁺¹) =q(^Ns) +^m < q(^Ns) +qs⁺¹ =q(^Ns⁺¹). This shows that Lq^mLqon [0;(s+1)k]. Next,q^m(^Nk) =q(^Ns)+^m+(k^,s^,1)m= q(^Ns) +^Pk_j⁼_s⁺¹qj = q(^Nk) =Q, so Lq^m(k) = Lq(k). This combined with the concavity ofLq and the fact thatLq^m is linear on [(s+ 1)=k;1]

implies that Lq Lq^m on [(s+ 1)=k;1]. ThusLq Lq^m on [0;1] and thereforeq^mkq.

Note that q^m0 q^m form⁰ :=qk > m, so we havec^Tq^m0 c^Tq^m as the objective functionc is nonnegative. We shall therefore hereafter restrict the attention tom²M :=^fqk;:::;m^maxg. Sinceq is strictly de- creasing, the tail averages are ordered qk^:k<qk^,1:k< ::: <q^1:k. There- fore the closed intervals Is := [ qs^+1:k;qs^:k] for s = 1;:::;k^,1 are all

nonempty and consecutive intervals intersect in one point, namely a tail average ofq. We say thatm²M isq-extremeifmis either the smallest or largest integer in one of the intervalsIs,s= 1;:::;k^,1. Some prop- erties of theq-extreme integers are collected in the next lemma; they are all easy consequences of the denition ofs^m. We letM^ex denote the set ofq-extreme integers.

Lemma 5

Letm²M. Then we have (i) m²Is^m+1;

(ii) ifm²M^ex, thenm equals either^bqs^m+1:k^cor^dqs^m+2:k^e; (iii) m²M^exif and only ifm's is obtained from some tail

averageqs^:k by integer rounding either up or down.

We are now in a position to give the rst main result of this section.

Proposition 6

Each vertex ofQ(q;k) is a permutation of some rounded q-averageq^m withmbeingq-extreme.

Proof.

We consider the ILP problem (10) and may assume that c¹ ::: cn 0 (otherwise a suitable permutation would be introduced below). We shall prove that some roundedq-average is an optimal solution of this problem. From the rearrangement inequality (1) it follows that there exists an optimal solution x satisfyingx¹ ::: xn 0, so we may consider the ILP problem

max^fc^Tx^jxkq;x¹:::xn0;xis integral^g: (12) Note that when xis nonincreasing,xk q holds if and only ifx(^Nr) q(^Nr) forr= 1;:::;k. Thus the variablesxk⁺¹;:::;xndo not enter any of these constraints and we may assume thatxk=:::=xn(asc0). For eachm²M, we consider the problem obtained from (12) by adding the constraintsxk=:::=xn=m. We shall solve this problem directly using previous results, and rst we note that the problem may be considered as one inkvariables:

max^fd^Tx^jxkq;x¹:::xk=m; xis integral^g: (13) where the objective function d is given by dj = cj for j k^,1 and dk=^Pn_j⁼_kcj.

We claim that there exists an optimal solution x of (13) satisfying x(^Nk) =q(^Nk). To prove this, consider an optimal solution withx(^Nk) largest possible. Assume thatx(^Nk)< q(^Nk); we shall deduce a contra- diction. Observe thatx(^Nk)q(^Nk)^,1 asxis integral. Ifxs > xs⁺¹= ::: =xk for somes < k, we let x be the solution obtained from x by increasing the (s+ 1)'th component by 1. Clearly xis decreasing. Fur- thermore, asq is strictly decreasing andxs⁺¹ =:::= xk, the L-curves LxandLq can only intersect on the interval [s=k;1] in one point, namely forj=s=k. ThusLx is strictly belowLq in [(s+ 1)=k;1], and therefore Lx Lq in this interval. Also, in [0;s=k] Lx = Lx, so x k q which implies that x is also optimal. In addition x(^Nk) = x(^Nk) + 1, which contradicts the maximality ofx(^Nk). It remains to discuss the case when

x¹=:::=xk. Asq is strictly decreasing, we must havex(^Nj)< q(^Nj) for all j. Consequently, if we dene the new solution x from xby in- creasing the rst variable by 1, we obtain, as in the rst case discussed, a new optimal solution with x(^Nk) =x(^Nk) + 1 again contradicting the maximality ofx(^Nk). This proves the claim.

Consider (as in the claim above) an optimal solution x^2Rk of (13) with x(^Nk) = q(^Nk). The feasibility of x implies that Lx Lq and LxL⁰ on [0;1] whereL⁰() :=Q^,km(1^,) for ²[0;1]. Therefore L L⁰⁰ := min^fLq;L^0g. It is easy to check thatL⁰⁰ =Lq^m, so we get xkPk(q^m) wherePk(q^m) is the vector (projection) containing the rst k components ofq^m. (Remark: Lq is a function on [0;1], althoughq^m2

Rn). From the discussion in section 2 on optimizing overP(q;n) using the greedy algorithm, it is clear that Pk(q^m) maximizesd^Tz forz ^2Rk satisfying z k Pk(q^m). Thusd^TPk(q^m) d^Tx, and the optimality of xin problem (13) gives that Pk(q^m) is also and optimal solution to that problem.

Finally, by taking the maximum optimal value of the problems (13) over allmwe solve the original problem (10). The optimal value of (13) is (we lets=s^m)^Pk_j⁼¹cjPk(q^m)j=^Ps_j⁼¹cjqj+cs^+1fPk

j⁼s⁺¹qj^,(k^, s^,1)m^g+^Pn_j⁼_s⁺²cjm=^Ps_j⁼¹cjqj+cs^+1Pk

j⁼s⁺¹qj+m^fPn_j⁼_s⁺²cj^,

(k^,s^,1)cs^+1g = (s) +m(s). where (s) and(s) are dened in the obvious way. Observe thatand depends onmbut only through s = s^m. Thus the optimal value for thosem with s^m = s⁰ (for some s⁰) is achieved by choosingm either maximal (if 0) or minimal (if <0) withs^m=s⁰, i.e. mis extreme. Based on the initial discussions in this proof, we can conclude that for someq-extremem²M the rounded q-averageq^mis an optimal solution of (10) which proves that each vertex ofQ(q;k) must be a roundedq-average as desired.

The previous proposition shows the form of each vertex, but it remains to decide if all the solutionsq^m withm extreme are vertices ofQ(q;k).

The answer turns out to be armative, and to prove this we shall rst give an optimization result which is useful later as well. We study the problem max^fc^Tx ^jx ² Q(q;k)^g for a special stair-case objective function. For each real number 1 and each pair of integerss;twith 0s < k <

tn, we denec^s;t()^2Rnby c^s;t() =

( forj= 1;:::;s, 1 forj=s+1;:::;t,

0 forj=t+1;:::;n, (14) and we consider the problem

max^f(c^s;t()^Tx^jx²Q(q;k)^g: (15)

Lemma 7

Let s and t be as above. Denem =^bqs^+1:k^c,m = m+ 1, = (k^,s)m^,Pk_j⁼_s⁺¹qj,¹= (t^,s)=(k^,s) and²= 1 +(t^,k)=. Finally let M() denote the set ofm ²M such thatq^m is an optimal solution of (15).

Then1 and²¹>1; in fact²> ¹holds if and only ifqs^+1:k

is fractional. FurthermoreM() is given by the following expressions:

(i) If1 < ¹, then M() =^fm^maxg. (ii) If=¹, then M() =^fm;:::;m ^maxg. (iii) If¹< < ², then M() =^fm^g.

(iv) If=², then M() =^fm;m^g. (v) If > ², then M() =^fm^g.

Proof.

Letc=c^s;t(). From the denition of mwe get m+1>qs^+1:k= (1=(k^,s))^Pk_j⁼_s⁺¹qj and thus = (k^,s)( m+ 1)^,Pk_j⁼_s⁺¹qj > 0.

As is integral, we get 1. Note that ¹ is well-dened as s < k and also¹ = (t^,s)=(k^,s)>1 becauset > k. Furthermore, we have m+ 1qs^+1:k+ 1, which impliesk^,sand the inequality is strict if qs^+1:k is fractional. Thus² = 1 + (t^,k)= 1 + (t^,k)=(k^,s) = (t^,s)=(k^,s) =¹and here we see that²> ¹if qs^+1:kis fractional.

Consider the optimization problem (15). From Proposition 6, we know that there is an optimal solution of the formq^mfor somem²M^ex. We have c^Tq^m= (^,1)^Xs

j⁼¹qmj+Q+ (t^,k)m: (16) asqmj=mforj k andq^m(^Nk) =Q. This implies that the following set of inequalities hold

c^Tq^qk< ::: < c^Tq^m: (17) In fact, formmwe gets^msand thereforeqmj=qj forj= 1;:::;s. Thus from (16) we getc^Tq^m= (^,1)^Ps_j⁼¹qj+ (t^,k)m+Qwhich is strictly increasing as a function ofm(due tot > k), and all the inequalities in (17) follow.

Next, let m > m, so s^m < s. Then qms⁺¹ = ::: = qmk = m and

Ps

j⁼¹qmj =^Pk_j⁼¹qmj^,Pk

j⁼s⁺¹qmj =Q^,(k^,s)m. By inserting this in (16) we get (^,1)(Q^,(k^,s)m) + (t^,k)m+Q= m+Qwhere

=t^,k^,(^,1)(k^,s)). Therefore is positive (resp. zero, negative) i is smaller than (resp. equal to, larger than)¹ = (t^,s)=(k^,s).

Thus if 1 < ¹, then >0 and thereforec^Tq^m < ::: < c^Tq^mmax. Next, if=¹, then = 0 andc^Tq^m =:::=c^Tq^mmax. And, nally, if > ¹, then <0 andc^Tq^m > ::: > c^Tq^mmax.

It remains to compareq^m and q^m. From (16) we obtain after some calculations that c^Tq^m,c^Tq^m = (^,1)^,(t^,k). Thus (i) if >

1+(t^,k)==², thenc^Tq^m> c^Tq^m, (ii) if=², thenc^Tq^m=c^Tq^m; and (iii) if < ², thenc^Tq^m< c^Tq^m.

The lemma now follows by putting all these inequalities together for varying.

The complete characterization of the vertices of Q(q;k) can now be given.

Theorem 8

The vertex set ofQ(q;k) consists of the vectors that can be obtained as permutations of someq^m withmbeingq-extreme.