# Prove that a function is strongly convex

Let $$f(x) := \|x\|_2 + \lambda \|x-y\|_2^2$$ where $$\lambda > 0$$, and $$x, y \in \Bbb R^n$$. How to prove that function $$f$$ is strongly convex?

I tried to prove this using the definition of a strongly convex function:

If $$f$$ is twice differentiable then it is strongly convex with parameter $$m$$ if and only if $$\nabla^2 f \geq m I$$ for any $$x$$ in the domain

I computed

$$\nabla f = \frac{x}{\|x\|_2} + (x-a), \qquad\qquad \nabla^2f = \frac{I}{\|x\|_2} - \frac{1}{\|x\|_2^2} + I$$

but then I don't know how to proceed to show that $$\nabla^2 f \geq mcI$$. Moreover, I should prove this for all $$x$$ in the domain, but this expression is not defined for $$x=0$$.

• can you include your attempt? Apr 23 at 15:27
• @SiongThyeGoh I included my attempt in the original question. Apr 23 at 17:42
• Where does $a$ come from? Apr 24 at 11:32

Your $$f$$ is the sum of $$\| x \|_2$$, which is convex, and a strongly convex function $$\lambda \| x - y \|_2^2$$. Then you can use this fact:

Fact: If $$f_1, f_2$$ are convex and $$f_2$$ is strongly convex with modulus $$\mu > 0$$, then $$f_1 + f_2$$ is strongly convex with modulus $$\mu$$ as well.

You can try to prove this fact just by combining the (sub)gradient inequalities for the two functions.

• Thank you! Can you please tell me the reference of the fact? Is it in a textbook? Apr 23 at 18:21
• You can probably find it in standard textbooks in convex analysis, but the proof is really simple: write down the subgradient inequality for $f_1$ and $f_2$, and add them up together. Apr 23 at 18:29

We are not supposed to use the definition that you stated as the function is not differentiable.

We can use this definition:

$$\forall t \in [0,1], f(tx_1+(1-t)x_2) \le tf(x_1) + (1-t)f(x_2) - \frac12 mt(1-t)\|x_1-x_2\|_2^2$$

for non-differentiable function.

Let $$f_1(x)=\|x\|_2$$ and $$f_2(x)=\lambda \|x-y\|^2$$.

Since $$\nabla^2 f_2 = 2\lambda I$$, $$f_2$$ is strongly convex with parameter $$2\lambda$$.

That is

$$\forall t \in [0,1], f_2(tx_1+(1-t)x_2) \le tf_2(x_1) + (1-t)f_2(x_2) - \lambda t(1-t)\|x_1-x_2\|_2^2$$

$$f_1$$ being the norm is convex, hence

$$\forall t \in [0,1], f_1(tx_1+(1-t)x_2) \le tf_1(x_1) + (1-t)f_1(x_2)$$

Summing the two inequalities prove that $$f$$ is strongly convex.