Separating convexity, strong convexity, smoothness and Lipschitzness

ProofIntermediate⏱ 30 minOptimizationcounterexamplespropertiesindependence

Problem

Consider four properties of a function $f:\R\to\R$ :

(C) $f$ is convex;
(SC) $f$ is $\mu$ -strongly convex for some $\mu>0$ ;
(S) $f$ is $L$ -smooth for some $L$ , i.e. differentiable with $f'$ being $L$ -Lipschitz;
(K) $f$ is $K$ -Lipschitz for some $K$ .

Only (SC) $\Rightarrow$ (C) holds by definition. Show that one further implication is forced and that the remaining combinations are all realisable:

Prove that (SC) and (K) cannot hold simultaneously on all of $\R$ .
Give an $f$ satisfying (C) and (S) but neither (SC) nor (K), and prove it has these properties.
Give an $f$ satisfying (C) and (K) but not (S).
Give an $f$ satisfying (S) and (K) but not (C).
Give an $f$ satisfying (SC) and (S), and compute its condition number.

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

Hints — 0 of 3 revealed

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

Problem	Field	Type	Difficulty	Time
Pairwise independence does not imply independence	Probability	Proof	Foundation	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
First-order characterisation of convexity	Optimization	Proof	Beginner	30 min
Strong convexity implies the Polyak–Lojasiewicz inequality	Optimization	Proof	Intermediate	30 min