For strongly convex $f \in C^1$ show that $2\mu \nabla f(x)^T (y-x) + \mu^2 {\lVert y-x \rVert}_2^2 + {\lVert \nabla f(x) \rVert}_2^2 \ge 0$

37 Views Asked by At

Given a $C^1$ function $f: \mathbb{R}^n \to \mathbb{R}$ that is strongly convex such that there is a constant $\mu > 0$ such that:

\begin{gather*} f(y) \ge f(x) + \nabla f(x)^T (y-x) + \frac{\mu}{2} {\lVert y-x \rVert}_2^2, \quad \forall x,y \in \mathbb{R}^n \\ \end{gather*}

show that:

\begin{gather*} f(x) + \nabla f(x)^T (y-x) + \frac{\mu}{2} {\lVert y-x \rVert}_2^2 \ge f(x) - \frac{1}{2\mu} {\lVert \nabla f(x) \rVert}_2^2, \quad \forall x,y \in \mathbb{R}^n \\ \end{gather*}

For strongly convex functions we also know that the following holds:

\begin{gather*} (\nabla f(y) - \nabla f(x))^T (y-x) \ge \mu {\lVert y-x \rVert}_2^2, \quad \forall x,y \in \mathbb{R}^n \\ \end{gather*}

A simplified version of the expression we wish to demonstrate is:

\begin{gather*} 2\mu \nabla f(x)^T (y-x) + \mu^2 {\lVert y-x \rVert}_2^2 + {\lVert \nabla f(x) \rVert}_2^2 \ge 0, \quad \forall x,y \in \mathbb{R}^n \\ \end{gather*}

Those last two terms are obviously non-negative, but the first term may be negative. I don't see any way to algebraically rearrange the given equations to reach the conclusion equation.

1

There are 1 best solutions below

0
On BEST ANSWER

$$ 2\mu\nabla f(x)^T(y - x) + \mu^2 \lVert y - x \rVert_2^2 + \lVert \nabla f(x) \rVert_2^2 = \lVert \nabla f(x) + \mu(y - x) \rVert_2^2 \ge 0 $$