First-order characterisation of convexity

ProofBeginner⏱ 30 minOptimizationconvexitytangent planecharacterisation

Theory: Convex Sets, Convex Functions, Smoothness and Strong Convexity →

Problem

Prove that a differentiable $f$ on an open convex set is convex if and only if $f(y)\ge f(x)+\langle\nabla f(x),y-x\rangle$ for all $x,y$ , and that it is $\mu$ -strongly convex if and only if the same holds with an extra $\frac\mu2\|y-x\|_2^2$ .

Write a complete argument. Every inequality you use should be one you could state precisely.

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems

Problem	Field	Type	Difficulty	Time
Convexity of the logistic loss	Classical ML	Proof	Beginner	15 min
Equality in Jensen's inequality	Foundations	Proof	Beginner	15 min
Every norm is convex, and the operator norm is a supremum of linear functions	Optimization	Proof	Beginner	15 min
Existence and uniqueness of the minimiser	Optimization	Proof	Beginner	15 min
Separating convexity, strong convexity, smoothness and Lipschitzness	Optimization	Proof	Intermediate	30 min