Minimization on both sides of inequalities

Question

I was reading a post regarding strong convexity here and was going through the following proposition:

Strong convexity of a continuously differentiable function $f$ implies the following condition: $$\frac{1}{2} ||\nabla f(x)||^2 \geq\mu (f(x)-f(x^*) ,\qquad \forall x $$
Proof:
Taking minimization with respect to y on both sides of
$$f(y)\geq f(x)+\nabla f(x)^T (y-x) + \frac{\mu}{2} ||y-x||^2$$
yields $$f(x^*)\geq f(x)-\frac{1}{2\mu} ||\nabla f(x) ||^2$$
and rearrange it will give us the proof

I don't really get the part where we were asked to perform minimization on both sides of the inequalities. How am I supposed to do that?

Answer 1

The reason is: If $g,h : A \to \mathbb R$ are functions with $$ g(y) \le h(y) \qquad \forall y \in A$$ then $$ \inf_{y \in A} g(y) \le \inf_{y \in A} h(y).$$

To prove this, take a sequence $y_n$ with $h(y_n) \to \inf_{y \in A} h(y)$. Then, $$ \inf_{y \in A} g(y) \le g(y_n) \le h(y_n). $$ Now, $n \to \infty$ gives the desired inequality.

Following up on this, if we try to minimize both sizes of the inequality individually, we will still have correct inequality. Thus, if we minimize the LHS of

$$f(y)≥f(x)+∇f(x)^T(y−x)+\frac{μ}{2}||y−x||^2 ~~~~~~~~~~~(1)$$

with respect to $y$, we get $y_{min{LHS}} = x^*$, and we minimize the right-hand size with respect to $y$ via taking the partial derivative and setting it equal to $0$ to get $$ y_{min_{RHS}} = x - \frac{1}{\mu}\nabla f(x) $$ and if we plug these two back into $(1)$ and rearange, then we can recover your first inequality.