| # Sum of largest components in a vector Definition Convexity Efficient representation of the epigraph Proof ## 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.