Find gradient and Hessian for optimization problem Given $$S_\mu(u) := \sum_{i=1}^n \sqrt{u_i^2+\mu^2}-\mu$$ a smoothed $1$-norm. Using Newton's method, calculate $$\min_{u\in \mathbb{R}^n}\frac{1}{2} \|u-u_0\|_2^2 + \alpha S_\mu(\nabla u)$$
where $$(\nabla u)_i = \begin{cases} u_{i+1} - u_i & 1 \leq i < n\\0 & i = n\end{cases}$$

In order to do that, I will need the gradient and Hessian for the expression. I tried representing $\nabla$ as follows
$$\nabla = \begin{pmatrix}
           -1 &  1 & \dots & \dots & 0 \\
            0 & -1 &  1    & \dots & 0 \\
            0 &  0 & -1    & \dots & 0 \\
       \vdots & \vdots & \ddots & \ddots & 0\\
            0 & \dots & 0 & -1 & 1\\
            0 & \dots & 0 &  0 & 0
           \end{pmatrix}$$
and I know that the first parts derivative is just $u$ itself but am confused about $\frac{\partial}{\partial u_i} S_\mu(\nabla u)$.
 A: The cost function writes
$$
\phi(\mathbf{u})
=
\frac12 \|\mathbf{u}-\mathbf{u}_0 \|_2^2
+\alpha \mathbf{1}_N^Tf(\mathbf{Du})
+c
$$
where $f(\mathbf{y})$ is applied elementwise on each element of $\mathbf{y}$
and thus is a column vector of the same size as $\mathbf{y}$.
Here $f(x)=\sqrt{x^2+\mu^2}$.
Taking the differential
\begin{eqnarray}
d\phi 
&=&
(\mathbf{u}-\mathbf{u}_0):d\mathbf{u}
+ \alpha \mathbf{1}_N: f'(\mathbf{Du}) \odot d(\mathbf{Du})\\
&=& (\mathbf{u}-\mathbf{u}_0)
+ \alpha \mathbf{D}^T f'(\mathbf{Du}) :   d\mathbf{u} \\
\end{eqnarray}
where $f'(x)=\frac{x}{\sqrt{x^2+\mu^2}}$
and the colon denotes the inner product vector.
The gradient is the vector
$$\mathbf{g}
= (\mathbf{u}-\mathbf{u}_0) 
+ \alpha \mathbf{D}^T f'(\mathbf{Du})$$
It follows
\begin{eqnarray}
d\mathbf{g}
&=& d\mathbf{u} 
+ \alpha \mathbf{D}^T \left[ f''(\mathbf{Du}) \odot d(\mathbf{Du}) \right] \\
&=& 
\left[ 
\mathbf{I} + 
\mathbf{D}^T \mathrm{Diag}(f''(\mathbf{Du})) \mathbf{D}
\right]
d\mathbf{u} 
\end{eqnarray}
The bracket term is the Hessian.
