How to show if $\nabla^2 f(x) \succeq \alpha I$, then the function is $\alpha$-strongly convex?

In my optimization notes I have $$\nabla^2 f(x) \succeq \alpha I \rightarrow \alpha\text{-strongly convex} \,\,\,\,\,\,\forall x$$ where $x \in \mathbb{R}^n$ and $A\succeq B$ means $A-B$ is positive semi-definite.

For the proof we use mean value theorem $$ \nabla f(y)-\nabla f(y) = \int_0^1 \nabla^2 f(x+t(y-x))(y-x)dt $$ where $x, y \in \mathbb{R}^n$ and $0 \leq t \leq 1$. $$ \langle \nabla f(y)-\nabla f(y) ,y-x \rangle= \langle \int_0^1 \nabla^2 f(x+t(y-x))(y-x)dt,y-x \rangle $$ Since $$\nabla^2 f(x+t(y-x)) \succeq \alpha I \tag{1}$$ and the fact that $\langle Ad,d \rangle \geq c\|d\|^2 \leftrightarrow A \succeq cI \tag{2}$

$$ \langle \int_0^1 \nabla^2 f(x+t(y-x))(y-x)dt,y-x \rangle \geq \alpha \|y-x\|^2 \tag{3} $$ I do not understand why how we can use $(1)$ to get $(2)$? Because I do not know why we can use $(1)$ and write $$ A=\int_0^1 \nabla^2 f(x+t(y-x))dt \succeq \int_0^1 \alpha I dt= \alpha I $$ and then use $(2)$.

Is it possible to take integral from any matrix inequality?


In your statement of the "mean value theorem" and in other parts of your post, you are taking the integral of a vector or a matrix, which does not make sense.

I think it would be better to state the integral equality as $$\langle \nabla f(y) - \nabla f(x), y-x \rangle = \int_0^1 \langle \nabla^2 f(x + t(y-x)) (y-x), y-x \rangle \, dt.$$ (This is simply the fundamental theorem of calculus $g(1) - g(0) = \int_0^1 g'(t) \, dt$ applied to $g(t) := \langle \nabla f(x + t(y-x)), y-x \rangle$.)

From here, you can immediately use $\nabla^2 f(x + t(y-x)) (y-x), y-x \rangle \ge \alpha \|y-x\|^2$ from (2), as desired.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.