I am attempting to find a proof of strong-convexity implying the Polyak- Lojasiewicz (PL) inequality is satisfied. As I understand it, strong convexity means that: $$ \textbf{H} f \succcurlyeq \mu I$$ for some $\mu>0$, where $\textbf{H}f$ is the Hessian matrix of $f$ and $I$ is the identity matrix.
The PL inequality states that:
$$\frac{1}{2}\|\nabla f(x)\|^2 \geq \mu(f(x) - f(x^*))$$
where $x^*$ is the value of $x$ for which $f(x)$ is minimized.
This paper http://www.optimization-online.org/DB_FILE/2016/08/5590.pdf states that if a function is strongly convex with constant $\mu$, then it must satisfy the PL inequality with the same constant (page 4, section 2.3, first sentence).
I found a source that says this can be done by minimizing the following inequality:
$$f(y)\ge f(x)+\nabla f(x)^T(y-x)+\frac{\mu}{2}\lVert y-x \rVert^2 \tag{1}$$
in terms of $y$ to get $$f(x^*) \ge f(x)-\frac{1}{2\mu}\|\nabla f(x)\|^2.$$
I don't understand this. How exactly is the inequality being minimized in terms of $y$ here? How do I go from strong convexity to equation (1) to this result?
Wow, this was a very confusing statement they gave there, but eventually I was able to get to it. Since $f$ is $\mu$-strongly convex, then we have $$f(y)\geq f(x)+\nabla f(x)^T(y-x)+\frac{\mu}{2}\|y-x\|^2$$ Now, minimize the inequity with respect to $y$. Minimization maintains the inequality relation, therefore we will focus on each side separately. LHS is straightforward and we have: $$\min_y \{f(y)\} = f(x^*)$$ To solve the RHS we will differentiate with respect to $y$ to obtain $$\frac{\partial RHS}{\partial y}=\nabla f(x)+\mu(y-x)=0\iff y=x-\frac{1}{\mu}\nabla f(x)$$ Plug back the optimal $y$ we found to the RHS and we get $$f(x)-\frac{1}{\mu}\|\nabla f(x)\|^2 + \frac{1}{2\mu}\|\nabla f(x)\|^2$$ and overall we have $$f(x^*)\geq f(x)-\frac{1}{2\mu}\|\nabla f(x)\|^2$$