Sum of largest components in a vector
Definition
For , the sum of the -largest components in is written as
where is the -th largest component of .
Convexity
The function is convex, since it is the point-wise maximum of linear (hence, convex) functions:
Since the functions inside the maximum are all linear, the function is actually polyhedral.
The convex constraint 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 ( choose ) linear functions involved in the maximum, all obtained by choosing a particular subset of indices in . For example, with and :
Hence, to represent the constraint based on the above, we'd have to list constraints:
The list of constraints needed grows very quickly with : for , , we'd have to list more than linear constraints!
A more efficient representation is based in the following expression, proven below:
In this form, a constraint of the form can be expressed as: there exist a scalar and a -vector such that
The above proves that is convex, since the set of points such that the above holds for some is a polyhedron (hence the function has a convex epigraph). The above representation is much more efficient, as it involves a polyhedron with constraints. The price to pay is a moderate increase in the number of variables, which is now instead of .
The lesson here is that a polyhedron in a -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 are ordered in decreasing fashion: . Then . Now choose such that . We have
Since is attained for a particular choice of , we obtain that is bounded below by the minimum over :
On the other hand, for every , we have
Since the upper bound above is valid for every , it remains valid when minimizing over , and we have
This concludes the proof.
|