1
$\begingroup$

Consider a function $f(x, y): \mathbb{R}^2 \rightarrow \mathbb{R}$ where $f(x, y) = \frac{5}{2}x^2 + xy + \frac{5}{2}y^2$.

By definition the gradient of a function $f$ is Lipschitz continuous with parameter $\beta > 0$ if:

\begin{align} \tag 1 \|\nabla f(x) - \nabla f(y)\| \leq \beta\|x- y\| \end{align}

Here $x$ and $y$ denote any two points in the domain of function $f$. The function $f$ with this property is also $\beta$-smooth. Here the norm $\| \|$ denotes a euclidean norm.

I tried looking at this post for hints on how to find $\beta$ but it didn't give me any insights to apply them for my function in question.

Here is what I have tried so far: \begin{align} \nabla f &= \begin{bmatrix} 5x+ y \\ x + 5y \end{bmatrix} \end{align} Now lets consider two points $a = (a_1, a_2)$ and $b = (b_1, b_2)$ for our function $f$. Now the left hand-side of equation ($1$) without the norm becomes \begin{align} \nabla f(a) - \nabla f(b) &= \begin{bmatrix} 5a_1 + a_2 - 5b_1 - b_2\\ a_1 + 5a_2 - b_1 - 5b_2 \end{bmatrix} \end{align} Applying the euclidean norms of equation (1) leaving $\beta$ alone on the right hand side we have:

\begin{align} \frac{\|\nabla f(a) - \nabla f(b)\|}{\|a- b\|} = \frac{\sqrt{(5a_1 + a_2 - 5b_1 - b_2)^2 + (a_1 + 5a_2 - b_1 - 5b_2)^2}}{\sqrt{(a_1 - b_1)^2 + (a_2- b_2)^2}} \leq \beta \end{align}

So the smallest $\beta$ value will occur when we have equality. I tried expanding the above expression but it only gets more messy. I think my approach is wrong. What form would $\beta$ be? Is it a constant? From the above expression it seems to depend on the coordinates of the selected two points but according to the definition it should be independent of the chosen points.

What would be the right way to calculate $\beta$? Any help building up the intuition with this simple example would be greatly appreciated!

Thanks!

$\endgroup$
1
  • $\begingroup$ Look at the norm of the Hessian. $\endgroup$
    – copper.hat
    Dec 4, 2019 at 5:24

1 Answer 1

1
$\begingroup$

Hint: the derivative $\nabla f$ is a linear map; indeed, the matrix for the map is $A = \begin{pmatrix} 5 & 1 \\ 1 & 5 \end{pmatrix}$. Thus $$\| \nabla f(x) - \nabla f(y)\| = \| A(x-y)\| \le \|A\| \| x-y\|.$$ Now you just need to bound (or explicitly find) the matrix norm of $A$.

$\endgroup$
3
  • $\begingroup$ Thanks! @User8128. So with a quick search on wikipedia en.wikipedia.org/wiki/Matrix_norm#Special_cases the matrix euclidean norm of $A$ is the maximum singular value. $\|A\|_{2}$ in this case happens to be $6$. I was wondering what would be the right norm in the expression as it would affect the bound. Is it always euclidean? $\endgroup$ Dec 4, 2019 at 3:42
  • $\begingroup$ Also does the inequality above provide the tightest bound? i.e. does solving for $\|A\|_{2}$ guarantee the best/smallest value of $\beta$ $\endgroup$ Dec 4, 2019 at 3:57
  • $\begingroup$ The matrix norm is essentially defined to be the smallest (i.e. best) $\beta > 0$ such that $\| A x\| \le \beta \|x \|$ for all $x$, so yes, this gives the best $\beta$. If you are considering the Euclidean norm on $\mathbb R^2$, then here $\| A \|$ denotes the matrix $2$-norm. If you are considering some other norm, that will change, but it seems you are considering the Euclidean norm here. $\endgroup$
    – User8128
    Dec 4, 2019 at 4:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .