Theorem 11, p. 19 — (GM) with α_k = 1/L_f on qS_{L_f,κ_f}: ‖x^k − x̄^k‖² ≤ ((1 − μ_f)/(1 + μ_f))^k ‖x⁰ − x̄⁰‖²

Let $X\subseteq\mathbb R^n$ be a nonempty closed convex set and let $f$ be a convex function on $X$, differentiable at every point of $X$, whose gradient is Lipschitz continuous on $X$ with constant $L_f>0$:

Let $X^*=\arg\min_{x\in X}f(x)$ be nonempty, with optimal value $f^*$, and let $f$ be quasi-strongly convex with constant $\kappa_f>0$: for every $x\in X$ and $\bar x=[x]_{X^*}$ (the Euclidean projection of $x$ onto $X^*$),

That is, $f$ belongs to the class $q\mathcal S_{L_f,\kappa_f}(X)$.

Let $(x^k)_{k\ge0}$ be generated by the projected gradient method (GM) with constant step size $\alpha_k=1/L_f$: $x^0\in X$ and $x^{k+1}=[x^k-\tfrac1{L_f}\nabla f(x^k)]_X$. Write $\bar x^k=[x^k]_{X^*}$ and $\mu_f=\kappa_f/L_f$. Then for every $k\ge0$

The distance of the iterates to the optimal set thus decreases linearly, without strong convexity and without uniqueness of the minimiser; this is the paper's linear convergence result for (GM) on the class $q\mathcal S_{L_f,\kappa_f}$.

Formalization Note The standing assumptions of problem (P) are binders: $X$ closed and convex, $f$ convex on $X$ (ConvexOn), differentiable at each point of $X$ in the ambient space, the Lipschitz bound (1) with $L_f>0$, and a named minimiser xstar $\in X^*$ (so $X^*\neq\emptyset$; $f^*=f(\bar x)$ for any $\bar x\in X^*$). "Simple" (cheap projection) is not a mathematical hypothesis and is dropped; "closed convex function" adds nothing for a real-valued differentiable $f$. Projections $[u]_S$ are encoded by the nearest-point predicate IsNearest S u p ($p\in S$ and $\|u-p\|\le\|u-z\|$ for all $z\in S$), and statements hold for every nearest point; the nearest point onto a nonempty closed convex set is unique, so this is the projection. No hypothesis $\kappa_f\le L_f$ is added: the paper derives $\mu_f\le 1$ in (12) whenever $X\neq X^*$. The theorem's phrase "converges linearly to some optimal point" is rendered by the rate (45), which is what the page proves; convergence of $x^k$ to a limit is not stated. If $\kappa_f>L_f$, inequalities (2) and (10) force $X\subseteq X^*$, so both sides vanish; no hypothesis $\kappa_f\le L_f$ is needed.