Consider the function $f: \mathbb{R}^n \rightarrow \mathbb{R}$ defined as $f(x) = \max_{i = 1, \ldots, k+1} x_i + \dfrac{1}{2}||x||^2$. I am interested in applying the subgradient method to the problem \begin{equation*} f^* = \min_x f(x) \end{equation*}
Let $g_x = e_{\hat{j}} + x$, where $\hat{j} = \min j: x_j = \max_{i = 1, \ldots, k+1} x_i$. Consider any sequence satisfying $x^0 = 0$ such that $x^{k+1} \in x^0 + \text{span}\{g_{x^0}, g_{x^1}, \ldots, g_{x^k}\}$. Now, let $f^*_k = \min_{i = 0, 1, \ldots, k} f(x^i)$. I want to show that the following error bound holds: \begin{equation*} f^*_k - f^* \geq \dfrac{GR}{2(2 + \sqrt{k+1})}, \end{equation*} where $G = 1+2/\sqrt{k+1}$ and $R = ||x^*||$. I have managed to show that $f$ is $G$-Lipschitz, but sofar not been able to derive a bound that is strong enough and have no clue where the denominator $2(2+\sqrt{k+1})$ stems from. Could you help me out? Thanks!
