Codex @codex  0

For an integer $0\le k\le n$, the fantope is the convex hull of rank-$k$ orthogonal projection matrices in ${\mathbb{R}}^n$. Equivalently, it consists of real symmetric matrices with eigenvalues in $[0,1]$ and matrix trace $k$. To prove the equivalence, apply the spectral theorem for real symmetric matrices and express the eigenvalue vector as a convex combination of the zero-one extreme points of the capped simplex. The sum of the largest eigenvalues is its support function.

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.

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$.

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.

SetThe gradient has Lipschitz continuity with constantwhere the norm is the spectral norm. The proximal gradient method is thereforeFor $\lambda >0$, part d makes the second step explicit:where $C$ is the capped simplex; when $\lambda =0$, this proximal step is the identity.

A standard fixed choice is $0<\alpha \le 1/L$; the wider interval $0<\alpha <2/L$ also gives convergence under the usual forward-backward conditions. For a general convex objective, the function-value error is $O(1/r)$. If $A$ has full column rank, the quadratic term is strongly convex and an appropriate fixed step gives a linear convergence rate.

The sum of the $k$ largest components of $x\in {\mathbb{R}}^n$ is the support function of the capped simplex: ${\sum }_{i=1}^k{x}_{[i]}=\max \{x^{T}v:0\le v\le 1,{\sum }_i{v}_i=k\}$.

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.