Does $f(x) = \frac{1}{2}x^TAx$ have an L-Lipschitz continuous gradient

Question

Does $f(x) = \frac{1}{2}x^TAx$ have an L-Lipschitz continuous gradient i.e there is a constant L>0 such that $$||\nabla f(x) - \nabla f(y)||_2 \le L||x-y||_2$$ for any $x,y$? I tried to derive it but could not go further than this: $$||(x^T-y^T)A||_2 \le L||x-y||_2$$ I would appreciate any help.

Answer 1

The function is $L$-Lipschitz, where $L$ is the operator norm of $A$. The operator norm is defined as $$\|A\|_{op} := \sup_{x \ne 0} \frac{\|A x\|_2}{\|x\|_2}.$$ Indeed, from your work we have $$\|\nabla f(x) - \nabla f(y)\|_2 = \|A(x-y)\|_2 \le \|A\|_{op} \|x-y\|_2$$ simply by the definition of operator norm.

One can show that the operator norm is equal to the largest singular value of $A$. Further, if $A$ is symmetric (and thus orthogonally diagonalizable), it is equal to the largest absolute eigenvalue, $\max_i |\lambda_i|$.