# Variational Multiscale Nonparametric Regression: Algorithms and Implementation
## 3 Computational Methods
### Semismooth Newton Method  
Besides the optimality conditions (9), the problem (3) can also be solved by the so-called Karush-Kuhn-Tucker conditions, which are necessary and sufficient as well. Using the notation of this section, the original problem (3) is equivalent to  
\[\min_{v\in\mathbb{R}^{n}}R\left(v\right)\qquad\text{such that}\qquad q_{n}-Kv+KY \geq 0,q_{n}-KY+Kv\geq 0. \tag{12}\]  
This is a convex optimisation problem with linear inequality constraints, and if we introduce \(B:\mathbb{R}^{n}\rightarrow\mathbb{R}^{2\#\Lambda_{n}}\) as \(v\mapsto Bv\) with \(B=(K^{\top},-K^{\top})^{\top}\), then a vector \(v\) is a solution to (12) if and only if there exists a vector of Lagrange multipliers \(\lambda\in\mathbb{R}^{2\#\Lambda_{n}}_{\geq 0}\) such that  
\[\partial R\left(v\right) \
i-B^{\top}\lambda, \tag{13a}\] \[q_{n}-Bv+BY \geq 0,\] (13b) \[\lambda_{i}\left(q_{n}-Bv+BY\right)_{i} =0\quad\text{for all}\quad 1\leq i\leq 2\#\Lambda_{n}. \tag{13c}\]  
The latter two conditions can be reformulated as  
\[\lambda_{i}=\text{max}\left\{0,\lambda_{i}+c\left(Bv-BY-q_{n}\right)_{i} \right\}\quad\text{for all}\quad 1\leq i\leq 2\#\Lambda_{n}. \tag{14}\]  
The immediately visible advantage of this formulation over the original problem is that the inequality constraints have been transformed into equations. Now, suppose for a moment that the functional \(R\) is twice differentiable. Then, \(\partial R(v)\) is single valued and (13a) is a differentiable equation for \(v\) and \(\lambda\). It seems a natural approach to solve the corresponding system of Equations (13a) and (14) via an analog of [PERSON]'s method. On the other hand, even if \(R\) was twice differentiable, the max function in (14) is not differentiable in the classical sense. The application of [PERSON]'s method is however still possible, as the max function turns out to be semismooth (see Definition 2.5 in [42]). For a general operator \(B\), it is however not clear if the overall system (13a) and (14) can also be described as finding the root of a semismooth function. Therefore, one introduces a regularisation parameter \(\beta\in(0,1)\) and replaces (14) by the regularised equation \(\lambda_{i}=\beta\max\left\{0,\lambda_{i}+c\left(Bv-BY-q_{n}\right)_{i}\right\}\) for all \(1\leq i\leq 2\#\Lambda_{n}\), which is in turn equivalent to  
\[\lambda_{i}=\max\left\{0,\frac{\beta c}{1-\beta}\left(Bv-BY-q_{n}\right)_{i} \right\}\quad\text{for all}\quad 1\leq i\leq 2\#\Lambda_{n}. \tag{15}\]  
This system is now explicit in \(\lambda\) and yields in combination with (13a) the overall system  
\[\partial R\left(v\right)\
i-\frac{1}{\delta}B^{\top}\max\left\{0,\left(Bv-BY- q_{n}\right)\right\} \tag{16}\]  
with the new regularisation parameter \(\delta:=(1-\beta)/(\beta c)\in(0,\infty)\). This system can--for twice differentiable \(R\) and under appropriate assumptions on \(B\) satisfied in our example--now be shown to be semismooth (cf. [65]). Furthermore, for \(\delta\searrow 0\), the solution of the regularised system (16) converges towards a solution of the original system (13). This follows from the fact that (15) is in fact the Moreau-Yosida regularisation of the second optimality condition (9b). In practice, this limiting process is realised by a path-continuation scheme, sustaining the superlinear convergence behaviour. For differentiable \(R\), such as the Sobolev seminorm \(R(v)=|v|_{H^{n}}\), the implementation of the semismooth Newton method with path-continuation is now straightforward: the overall system to be solved can now be written as  
\[T_{\delta}(v)=0,\;\;\text{where}\;T_{\delta}=\partial|v|_{H^{n}}+\delta^{-1}B^ {T}\max\{0,Bv-BY-q_{n}\}. \tag{17}\]  
Denote by \(\mathcal{D}_{k}[T_{\delta}]\) the generalised derivative of the functional at the position \(u_{k}\).