$$\frac{2 \alpha_k}{\varGamma} [f(x_k)-f^*]  \leq \|x_k-x_*\|^2 -\|x_{k+1}-x_*\|^2+ \rho\alpha_k^2 , \qquad k = 0,1, \ldots.$$ Hence, performing the sum of the above inequality for $k = 0, 1, \ldots, N,$ we have $$\frac{2}{\varGamma} \sum_{k=0}^{N} \alpha_k [f(x_k)-f^*] \leq \|x_0-x_*\|^2-\|x_{N+1}-x_*\|^2+\rho\sum_{k=0}^{N}\alpha_k^2.$$ Therefore, $$\frac{2}{\varGamma} \, \min \left\{f(x_k) - f^{*}: ~ \, k = 0, 1,\ldots, N \right\} \sum_{k=0}^{N}\alpha_k \leq \|x_0 - x_{*}\|^2 +\rho\sum_{k=0}^{N}\alpha_k^{2},$$ which is equivalent to the desired inequality.

Analysis of the subgradient-InexP method with Polyak’s stepsize rule {#Sec:AnalysisPolyak}
--------------------------------------------------------------------

In this section we will analyze the subgradient-InexP method with Polyak’s step sizes. [*Throughout this section, we assume also that $\Omega^* \neq \varnothing$ and $\{x_k\}$ is a sequence generated by Algorithm \[Alg:INP\] with the stepsize given by Rule \[Poliak.Step\]*]{}.

\[Le:FejerConvPolyak\] Let $x\in \Omega^*$. Then, the following inequality holds $$\label{eq:MainIneqPolyak}
        \|x_{k+1}-x\|^2\leq \|x_k-x\|^2 - \underline{\beta} \frac{\left[f(x_k)-f^*\right]^2}{\|s_k\|^2}, \qquad\qquad k=0, 1, \ldots.$$

Considering that $x\in \Omega^*$ we have $f^*= f(x)$. The combination of with implies $2t_k\epsilon_k\leq 2\mu \beta_k^2 [f(x_k)-f^*]^2/\|s_k\|^2$. Moreover, also implies that $t_k^2\|s_k\|^2 = \beta_k^2[f(x_k)-f^*]^2/\|s_k\|^2$. Thus, we conclude form that $$\label{eq:mdpss}
    \|x_{k+1}-x\|^2\leq \|x_k-x\|^2 -\left(2-\nu\beta_k-2\mu \beta_k\right)\beta_k\frac{\left[f(x_k)-f^*\right]^2}{\|s_k\|^2}, \qquad k=0, 1, \ldots.$$ On the other hand, gives us $\beta_k<1/(2\mu+\nu)$, which is equivalent to $2-\nu\beta_k-2\mu \beta_k>1$. Therefore, since also gives $\underline{\beta}\leq \beta_k$, we conclude that implies .

In the following theorem we 