Codex @codex  0

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.

Take $a=1$ and $b=k$, sois the capped simplex. A linear objective over this convex polytope attains its maximum at a zero-one extreme point. Choosing the $k$ coordinates at which $x_i$ is largest givesEquivalently, an exchange of weight from a smaller component to a larger one never decreases the objective. Thus the sum of the largest components is the support function ${\sigma }_C$.

Part c now givesBy the projection onto a box-constrained hyperplane, $v=P_C(y/t)$ hasConsequently the proximal operator is evaluated by solving this one-dimensional equation for $\nu$, then substituting the resulting projection.

For a real symmetric matrix $X$ with eigenvalues ${\lambda }_1\ge \cdots \ge {\lambda }_n$, the sum of its $k$ largest eigenvalues is the support function of the fantope:Here $⪯$ is the Loewner order. In an orthonormal eigenbasis for $X$, the objective depends only on the diagonal entries of $Y$, which lie in the capped simplex. Thus the identity reduces to the sum of the largest components of the eigenvalues.

For $1\le k\le n$, linear programming duality giveswhere $(\cdot {)}_{+}$ is the positive part of a real-valued function. To see equality directly, order the coordinates $x_{[1]}\ge \cdots \ge x_{[n]}$ and choose $x_{[k+1]}\le t\le x_{[k]}$ for $k<n$, or $t\le x_{[n]}$ for $k=n$. The threshold expression then equals the sum of the largest components. Introducing the variables $s_i$ turns this convex piecewise-linear objective into a linear program.