Lipschitz Hessian implies Lipschitz Hessian diagonal?

127 Views Asked by At

I am working with an optimization problem where the Hessian is assumed Lipschitz, i.e.,

$$\| \nabla^2 f(x) - \nabla^2 f(y)\| \leq L\|x-y \|\tag{1}$$ and positive semi-definite. i.e., $\nabla^2 f(x) \succeq 0$. Let $\text{diag}\:\nabla^2 f(x)$ be the diagonal matrix whose elements are the diagonal elements of the Hessian $\nabla^2 f(x)$. That is,

$$\nabla^2 f(x) = \widehat{\nabla^2 f(x)} + \text{diag}\:\nabla^2 f(x)\tag{2}.$$

My goal is to prove that $\text{diag}\:\nabla^2 f(x)$ is also Lipschitz continuous.

To do so I have started by this post to get

$$\begin{aligned}z^T \nabla^2 f z \leq L z^Tz &\Leftrightarrow\\ z^T\widehat{\nabla^2 f} z + z^T\text{diag}\:\nabla^2 f z \leq L z^Tz &\Leftrightarrow \\ z^T\widehat{\nabla^2 f} z \leq z^T (L\:I -\text{diag}\:\nabla^2 f)z& \end{aligned}\tag{3}$$ Then by this post and the $\nabla^2 f\succeq 0$, we have $\text{diag}\:\nabla^2 f \succeq 0$. Combining the above we have $$z^T\widehat{\nabla^2 f} z \leq z^T (L\:I -\text{diag}\:\nabla^2 f)z \leq L z^Tz\tag{4}$$ which by setting $z=x-y$ and using again this post, we get

$$\| \widehat{\nabla^2 f(x)} - \widehat{\nabla^2 f(y)}\| \leq L\|x-y \|\tag{5}$$

Finally, using triangle inequality in $(1)$ and by applying $(5)$ we get

$$\begin{aligned} -\|\widehat{\nabla^2 f(x)} -\widehat{\nabla^2 f(y)} \| + \|\text{diag}\:\nabla^2 f(x) - \text{diag}\:\nabla^2 f(y) \|\leq L \|x -y \| &\Leftrightarrow \\ \|\text{diag}\:\nabla^2 f(x) - \text{diag}\:\nabla^2 f(y) \| \leq L \|x-y \| + \|\widehat{\nabla^2 f(x)} -\widehat{\nabla^2 f(y)} \| & \Leftrightarrow \\ \|\text{diag}\:\nabla^2 f(x) - \text{diag}\:\nabla^2 f(y) \| \leq 2 L \|x-y \|. \end{aligned}\tag{6}$$

Could you please someone verify if this procedure is correct? If it is correct can we make it tighter? Generally, in this case are we interested for a smaller Lipschitz constant or something that maximizes the upper bound? Any help is highly appreciated.