Suppose that $f − \frac{1}{2}m||x||^2$ is convex where $f$ is differentiable.
- Show that:
$f(αx + (1-α)y) ≤ αf(x) + (1-α)f(y) - \frac{α(1−α)m}{2}||x−y||^2$, $α∈(0,1)$
To start, I tried to apply the definition of convexity to the given function but I am not sure how to do that?
- Show the following without assuming the existence of the Hessian:
$f(y) ≥ f(x) + ∇f(x) · (y − x) + \frac{m}{2} ||y - x||^2$
What does it mean when the question states without assuming the existence of Hessian. Does it mean I cannot add $∇^2f$ into the inequality?
- Then, prove that $f$ has a global minimzer.
$[∇f(x) - ∇f(y)] · (x - y) ≥ m||x - y||^2$
I tried using the proof of contradiction where I suppose $f$ does not have a global minimizer, but I am not sure.
Assume $m>0$. Some hints:
For 1: Let $g(x) = f(x) - \frac12 m \vert x \vert^2$. Since $g$ is convex, for all $\alpha \in [0,1]$, we have that $$g(\alpha x + (1-\alpha) y)\leqslant \alpha g(x) +(1-\alpha ) g(y). $$ Expand out the definition of $g$ - group the terms coming from $f$ together and the terms coming from the $-\frac12 m \vert x \vert^2$ together. Using that $\vert x-y\vert^2=\vert x \vert^2-2 x \cdot y + \vert y \vert^2$ the terms coming from $-\frac12 m \vert x \vert^2$ simplify to give you the required identity.
For 2: Given that $f$ is differentiable, recall that for any $v\in \mathbb R^n \setminus \{ 0\}$, $$ \nabla f(x) \cdot v = \lim_{h \to 0} \frac{f(x+hv)-f(x)}h . $$ If $x=y$ then your identity is trivial, so assume $y\neq x$ and take $v=y-x$. Then $$ f(x+hv)=f((1-h)x+h y) ,$$ so apply Part 1 with $\alpha = 1-h$.
For 3: First, assuming that there is a global minimiser, can you prove uniqueness? Let $x,y\in \mathbb R^n$ be global minimisers. From Part 2, $$ 0 \leqslant \frac12 m \vert x-y\vert^2 \leqslant f(y)-f(x)-\nabla f(x) \cdot (y-x). $$ What is the value of $\nabla f(x)$? Can you bound $f(y)-f(x)$ from above? Remember $y$ is a global minimiser of $f$.