0

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$.

Rodrigo de Azevedo
  • 1
UsernameIsTaken
  • 11

3 Answers3

3

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.

VHarisop
  • 3,840
0

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.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
0

Assuming that $a$ and $y$ in your post denote the same object, you did not calculate the derivatives correctly (which you can see for example by the fact that in your expression for $\nabla^2 f$ you subtract the scalar 1 from the matrix $I$). The correct derivatives of the function from the beginning of your post are (for $x \notin \{0, y \}$ because otherwise $f$ is not differentiable) $$ \nabla f(x) = \frac{x}{\| x \|_2} + 2 \lambda (x - y) $$ and $$ \nabla^2 f(x) = \left( \frac{1}{\| x \|_2} + 2 \lambda \right) I - \frac{1}{\| x \|_2^3} x x^T. $$ Using that $$z^T x x^T z = \| z^T x \|_2^2 \le \| z \|_2^2 \| x \|_2^2$$ for any $x, z \in \mathbb R^n$ we get for any $z \in \mathbb R^n$ that $$z^T \nabla^2 f(x) z \ge (\| x\|_2^{-1} + 2 \lambda) \| z \|_2^2 - \frac{\| x \|_2^2}{\| x \|_2^3} \| z \|_2^2 = 2 \lambda \| z \|_2^2 = z^T (2 \lambda I) z,$$ so $\nabla^2 f(x) \ge 2 \lambda I$ for all $x \in \mathbb R^n \setminus \{ 0, y \}$.

ViktorStein
  • 4,838