= Solution
Take $a=\mathbf1$ and $b=k$, so
$$
C=\left\{v\in\mathbb R^n:
0\leq v_i\leq1,\ \sum_{i=1}^nv_i=k\right\}
$$
is 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 gives
$$
\max_{v\in C}x^Tv=x_{[1]}+\cdots+x_{[k]}=h(x).
$$
Equivalently, 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 gives
$$
\operatorname{prox}_{th}(y)=y-tP_C(y/t).
$$
By the <projection onto a box-constrained hyperplane>, $v=P_C(y/t)$ has
$$
v_i=\min\{1,\max\{0,y_i/t-\nu\}\},
\qquad
\sum_i v_i=k.
$$
Consequently the proximal operator is evaluated by solving this one-dimensional equation for $\nu$, then substituting the resulting projection.
Back to article page
