Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 339 / 1

Suppose $y$ in the capped simplex has a coordinate strictly between zero and one. Since ${\sum }_i{y}_i=k$ is an integer, it cannot have exactly one such coordinate: the other coordinates would contribute an integer sum. Hence there are distinct $i,j$ with $0<y_i,y_j<1$.

Choose $0<\epsilon <\min \{y_i,1-y_i,y_j,1-y_j\}$ and set $y^{\pm }=y\pm \epsilon (e_i-e_j)$, where $e_i,e_j$ are standard basis vectors. Both perturbed vectors satisfy the coordinate bounds and have the same coordinate sum. They are distinct and $y=(y^{+}+y^{-})/2$, so $y$ is not an extreme point.

Conversely, every zero-one vector in this convex polytope is an extreme point. If it were a nontrivial convex combination of two feasible vectors, each coordinate equal to zero would force both corresponding coordinates to be zero, and each coordinate equal to one would force both to be one. Thus the two vectors would equal the original one. The extreme points are therefore exactly the indicators of $k$-element subsets.

The required linear program isThere are $2n$ inequality constraints and one equality constraint, all independent of $x$.

The feasible set is the capped simplex, a nonempty compact set. A linear function attains its maximum at an extreme point; the previous part identifies these as the indicators of $k$-element subsets. At such a vector, the objective is the sum of the selected coordinates. Maximizing selects the $k$ largest coordinates, including when some are negative or tied. Equivalently, $f_k$ is the support function called the sum of the largest components.

Keep $y\ge 0$ as the domain restriction, introduce nonnegative Lagrange multipliers $s_i$ for $y_i\le 1$, and introduce a free multiplier $t\in \mathbb{R}$ for ${\sum }_i{y}_i=k$. The maximizing Lagrangian isIts supremum over $y\ge 0$ is finite exactly when $s+t1\ge x$, and then equals $kt+{\sum }_i{s}_i$. By linear programming duality, since the primal is feasible and bounded,Minimizing over $s$ for fixed $t$ gives $s_i=(x_i-t{)}_{+}$, the positive part of a real-valued function. Thus the threshold formula for the sum of the largest components isFor a direct attainment check, order the coordinates $x_{[1]}\ge \cdots \ge x_{[n]}$. Any $t\in [x_{[k+1]},x_{[k]}]$ is optimal for $k<n$, while any $t\le x_{[n]}$ is optimal for $k=n$.

Substitute the dual linear program from the previous part and optimize jointly over $x,t,s$. The result isThe objective is linear, and the constraints are equalities or inequalities between affine functions, so this is a linear program. For each fixed feasible $x$, minimizing over $t,s$ gives exactly $f_k(x)$ by the threshold formula for the sum of the largest components; hence the reformulation preserves the optimal value and optimal $x$ whenever an optimum exists.

Replace coordinate inequalities by the Loewner order and coordinate sums by matrix trace. The maximizing semidefinite program isIts feasible set is the fantope. In an orthonormal eigenbasis of $X$, its objective is ${\sum }_i{\lambda }_i(X)Y_{ii}$, and the diagonal entries of $Y$ belong to the capped simplex. Choosing $Y$ as the orthogonal projection matrix onto the largest $k$ eigenvectors attains the sum of the largest eigenvalues, as in the Ky Fan maximum principle.

The minimizing semidefinite program isFor example, its Lagrangian arises by assigning $S⪰0$ to $I-Y⪰0$, keeping $Y⪰0$ in the domain, and using free $t$ for $\mathrm{tr}Y=k$. Finiteness of the supremum over $Y$ requires $S+tI-X⪰0$.

Equality follows directly by choosing $S$ to have eigenvalues $({\lambda }_i(X)-t{)}_{+}$ in the same orthonormal eigenbasis, with $t$ between the $k$th and $(k+1)$st eigenvalues, or below the smallest one for $k=n$. This is the threshold semidefinite program for the largest eigenvalues, and it also verifies the endpoint case $k=n$.