Sum of largest components in a vector

  • Definition

  • Convexity

  • Efficient representation of the epigraph

  • Proof

Definition

For x in mathbf{R}^n, the sum of the k-largest components in x is written as

  s_k(x) := sum_{i=1}^k x_{[i]},

where x_{[i]} is the i-th largest component of x.

Convexity

The function s_k(x) is convex, since it is the point-wise maximum of linear (hence, convex) functions:

  s_k(x) = max_{(i_1,ldots,i_k) in {1,ldots,n}^k} : x_{i_1} + ldots + x_{i_k}.

Since the functions inside the maximum are all linear, the function s_k is actually polyhedral.

The convex constraint s_k(x) le alpha can implemented in CVX by invoking sum_largest. (See here for an example.)

Efficient representation of the epigraph

The above representation is a very cumbersome representation, and is not used by CVX internally. Indeed, there are C_{n,k} (n choose k) linear functions involved in the maximum, all obtained by choosing a particular subset of k indices in {1,ldots,n}. For example, with k=2 and n=4:

 s_2(x) = max(x_1+x_2,x_2+x_3,x_3+x_1,x_1+x_4,x_2+x_4,x_3+x_4).

Hence, to represent the constraint s_k(x) le alpha based on the above, we'd have to list 6 constraints:

 x_1+x_2le alpha, ;;x_2+x_3le alpha, ;;x_3+x_1le alpha, ;;x_1+x_4le alpha, ;;x_2+x_4le alpha, ;;x_3+x_4 le alpha.

The list of constraints needed grows very quickly with n,k: for n=100, k=10, we'd have to list more than 10^{13} linear constraints!

A more efficient representation is based in the following expression, proven below:

  s_k(x) = min_t : kt + sum_{i=1}^n max(0, x_i-t).

In this form, a constraint of the form s_k(x) le alpha can be expressed as: there exist a scalar t and a n-vector u such that

     	kt + sum_{i=1}^n u_i le alpha, ;; u ge 0, ;; u_i ge x_i- t , ;; i=1,ldots,n.

The above proves that s_k is convex, since the set of points (x,alpha) such that the above holds for some u,t is a polyhedron (hence the function has a convex epigraph). The above representation is much more efficient, as it involves a polyhedron with 2n+1 constraints. The price to pay is a moderate increase in the number of variables, which is now 2n+1 instead of n.

The lesson here is that a polyhedron in a n-dimensional space, with an exponential number of facets, can be represented as a polyhedron in a higher dimensional space with a moderate number of facets. By adding just a few dimensions to the problem we are able to deal (implicitly) with a very high number of constraints.

Proof

A proof based on the powerful concept of duality is here.

We can assume without loss of generality that the elements of x are ordered in decreasing fashion: x_1,ldots,x_n. Then s_k(x) = x_1+ldots+x_k. Now choose t such that x_k ge t ge x_{k+1}. We have

 kt + sum_{i=1}^n max(0, x_i-t) = kt + sum_{i=1}^k (x_i-t) = sum_{i=1}^k x_i = s_k(x).

Since s_k(x) is attained for a particular choice of t, we obtain that s_k(x) is bounded below by the minimum over t:

  s_k(x) ge min_t : kt + sum_{i=1}^n max(0, x_i-t).

On the other hand, for every t, we have

        begin{array}{rcl} s_k(x) &=& displaystylesum_{i=1}^k (x_i-t+t) = kt + displaystylesum_{i=1}^k (x_i-t)  &le& kt + displaystylesum_{i=1}^k max(0, x_i-t)  le  kt + displaystylesum_{i=1}^n max(0, x_i-t)  . end{array}

Since the upper bound above is valid for every t, it remains valid when minimizing over t, and we have

  s_k(x) le min_t : kt + sum_{i=1}^n max(0, x_i-t).

This concludes the proof.