Due to the fact that  two of the  studied classes of systems that are studied in this paper are affine functions in terms of $f$ and $g$, we propose to solve the "one--step nonsmooth problem'' (\ref{eq:toto1}) by performing an external Newton linearization.

 \paragraph{Newton's linearization of the first line of~(\ref{eq:toto1})} The first line of the  problem~(\ref{eq:toto1}) can be written under the form of a residue $\mathcal R$ depending only on $x_{k+1}$ and $r_{k+1}$ such that 
\begin{equation}
  \label{eq:NL3}
  \mathcal R (x_{k+1},r _{k+1}) =0
\end{equation}
with 
\begin{equation}
\mathcal R(x,r) = M(x - x_{k}) -h\theta f( x , t_{k+1}) - h(1-\theta)f(x_k,t_k) - h\gamma r
- h(1-\gamma)r_k.
\end{equation}
The solution of this system of nonlinear equations is sought as a limit of the sequence $\{ x^{\alpha}_{k+1},r^{\alpha}_{k+1} \}_{\alpha \in \NN}$ such that
 \begin{equation}
   \label{eq:NL7}
   \begin{cases}
     x^{0}_{k+1} = x_k \\ \\
     r^{0}_{k+1} = r_k \\ \\
     \mathcal R_L( x^{\alpha+1}_{k+1},r^{\alpha+1}_{k+1}) = \mathcal
     R(x^{\alpha}_{k+1},r^{\alpha}_{k+1})  + \left[ \nabla_{x} \mathcal
     R(x^{\alpha}_{k+1},r^{\alpha}_{k+1})\right] (x^{\alpha+1}_{k+1}-x^{\alpha}_{k+1} ) +
     \left[ \nabla_{r} \mathcal R(x^{\alpha}_{k+1},r^{\alpha}_{k+1})\right] (r^{\alpha+1}_{k+1} - r^{\alpha}_{k+1} ) =0
 \end{cases}
\end{equation}
\begin{ndrva}
  What about $r^0_{k+1}$ ?
\end{ndrva}

The residu \free $\mathcal R _{\free}$ is also defined (useful for implementation only):
\[\mathcal R _{\free}(x) \stackrel{\Delta}{=}  M(x - x_{k}) -h\theta f( x , t_{k+1}) - h(1-\theta)f(x_k,t_k),\]
which yields
\[\mathcal R (x,r) = \mathcal R _{\free}(x)   - h\gamma r - h(1-\gamma)r_k.\]

\begin{equation}
  \mathcal R (x^{\alpha}_{k+1},r^{\alpha}_{k+1}) = \fbox{$\mathcal R^{\alpha}_{k+1} \stackrel{\Delta}{=}  \mathcal R
_{\free}(x^{\alpha}_{k+1})  - h\gamma r^{\alpha}_{k+1} - h(1-\gamma)r_k$}\label{eq:rfree-1}
\end{equation}

\[  \mathcal R
_{\free}(x^{\alpha}_{k+1},r^{\alpha}_{k+1} )=\fbox{$ \mathcal R _{\free, k+1} ^{\alpha} \stackrel{\Delta}{=}  M(x^{\alpha}_{k+1} - x_{k}) -h\theta f( x^{\alpha}_{k+1} , t_{k+1}) - h(1-\theta)f(x_k,t_k)$}\]
 
% The computation of the Jacobian of $\mathcal R$ with respect to $x$, denoted by $   W^{\alpha}_{k+1}$ leads to 
% \begin{equation}
%    \label{eq:NL9}
%    \begin{array}{l}
%     W^{\alpha}_{k+1} \stackrel{\Delta}{=} \nabla_{x} \mathcal R (x^{\alpha}_{k+1},r^{\alpha}_{k+1})= M - h  \theta \nabla_{x} f(  x^{\alpha}_{k+1}, t_{k+1} ).\\
%  \end{array}
% \end{equation}
At each time--step, we have to solve the following linearized problem,
\begin{equation}
   \label{eq:NL10}
    \mathcal R^{\alpha}_{k+1} + (M-h\theta A ^{\alpha}_{k+1}) (x^{\alpha+1}_{k+1} -
    x^{\alpha}_{k+1}) - h \gamma (r^{\alpha+1}_{k+1} - r^{\alpha}_{k+1} )  =0 ,
\end{equation}
with 
\begin{equation}
     \begin{array}{l}
       A^{\alpha}_{k+1} = \nabla_x f(t_{k+1}, x^{\alpha}_{k+1}) 
 \end{array}
\end{equation}

By using (\ref{eq:rfree-1}), we get
\begin{equation}
  \label{eq:rfree-2}
  \mathcal R
_{\free}(x^{\alpha}_{k+1},r^{\alpha}_{k+1} )  - h\gamma r^{\alpha+1}_{k+1} - h(1-\gamma)r_k  + (M-h\theta A^{\alpha}_{k+1}) (x^{\alpha+1}_{k+1} -
    x^{\alpha}_{k+1})  =0 
\end{equation}

% %\fbox
% {
%   \begin{equation}
%     \label{eq:rfree-11}
%     \boxed{ x^{\alpha+1}_{k+1} = h\gamma (W^{\alpha}_{k+1})^{-1}r^{\alpha+1}_{k+1} +x^\alpha_{\free}}
%   \end{equation}
% }
% with :
% \begin{equation}
%   \label{eq:rfree-12}
%   \boxed{x^\alpha_{\free}\stackrel{\Delta}{=}x^{\alpha}_{k+1}-(W^{\alpha}_{k+1})^{-1}\mathcal (R_{\free,k+1}^{\alpha} \textcolor{red}{- h(1-\gamma) r_k})}
% \end{equation}

The matrix $W$ is clearly non singular for small $h$.




% that is

% \begin{equation}
%    \begin{array}{l}
%  h \gamma  r^{\alpha+1}_{k+1} = r_c + W^{\alpha}_{k+1} x^{\alpha+1}_{k+1}
%  .\label{eq:NL11} 
%  \end{array}
% \end{equation}
% with 
% \begin{equation}
%    \begin{array}{l}
% r_c \stackrel{\Delta}{=} h \gamma r^{\alpha}_{k+1} - W^{\alpha}_{k+1} x^{\alpha}_{k+1} + \mathcal R
% ^{\alpha}_{k+1}=- W^{\alpha}_{k+1} x^{\alpha}_{k+1} + \mathcal R_{\free k+1} ^{\alpha} - h(1-\gamma)r_k\\ \\
% \end{array}
% \end{equation}
% \begin{equation}
%    \begin{array}{l}
% \mathcal R ^{\alpha}_{k+1}=M( x^{\alpha}_{k+1} - x_k) -h \theta f(x^{\alpha}_{k+1})-h(1-\theta)f(x_k)
% - h \gamma r^{\alpha}_{k+1} -h(1- \gamma)r_k
%  \end{array}
%    \end{equation}
% \[x^{\alpha+1}_{k+1} = h(W^{\alpha}_{k+1})^{-1}r^{\alpha+1}_{k+1} +(W^{\alpha}_{k+1})^{-1}(\mathcal
% R_{\free k+1} ^{\alpha})+x^{\alpha}_{k+1}\]

 \paragraph{Newton's linearization of the second  line of~(\ref{eq:toto1})}
The same operation is performed with the second equation of (\ref{eq:toto1})
\begin{equation}
  \begin{array}{l}
    \mathcal R_y(x,y,\lambda)=y-h(t_{k+1},x,\lambda) =0\\ \\
  \end{array}
\end{equation}
which is linearized as
\begin{equation}
  \label{eq:NL9}
  \begin{array}{l}
    \mathcal R_{Ly}(x^{\alpha+1}_{k+1},y^{\alpha+1}_{k+1},\lambda^{\alpha+1}_{k+1}) = \mathcal
    R_{y}(x^{\alpha}_{k+1},y^{\alpha}_{k+1},\lambda^{\alpha}_{k+1}) +
    (y^{\alpha+1}_{k+1}-y^{\alpha}_{k+1})- \\[2mm] \qquad  \qquad \qquad \qquad  \qquad \qquad
    C^{\alpha}_{k+1}(x^{\alpha+1}_{k+1}-x^{\alpha}_{k+1}) - D^{\alpha}_{k+1}(\lambda^{\alpha+1}_{k+1}-\lambda^{\alpha}_{k+1})=0
  \end{array}
\end{equation}

This leads to the following linear equation
\begin{equation}
  \boxed{y^{\alpha+1}_{k+1} =  y^{\alpha}_{k+1}
  -\mathcal R^{\alpha}_{yk+1}+ \\
  C^{\alpha}_{k+1}(x^{\alpha+1}_{k+1}-x^{\alpha}_{k+1}) +
  D^{\alpha}_{k+1}(\lambda^{\alpha+1}_{k+1}-\lambda^{\alpha}_{k+1})}. \label{eq:NL11y}
\end{equation}
with,
\begin{equation}
     \begin{array}{l}
  C^{\alpha}_{k+1} = \nabla_xh(t_{k+1}, x^{\alpha}_{k+1},\lambda^{\alpha}_{k+1} ) \\ \\
  D^{\alpha}_{k+1} = \nabla_{\lambda}h(t_{k+1}, x^{\alpha}_{k+1},\lambda^{\alpha}_{k+1})
 \end{array}
\end{equation}
and
\begin{equation}\fbox{$
\mathcal R^{\alpha}_{yk+1} \stackrel{\Delta}{=} y^{\alpha}_{k+1} - h(x^{\alpha}_{k+1},\lambda^{\alpha}_{k+1})$}
 \end{equation}
 \paragraph{Newton's linearization of the third  line of~(\ref{eq:toto1})}
The same operation is performed with the third equation of (\ref{eq:toto1})
\begin{equation}
  \begin{array}{l}
    \mathcal R_r(r,x,\lambda)=r-g(t_{k+1},x,\lambda) =0\\ \\  \end{array}
\end{equation}
which is linearized as
\begin{equation}
  \label{eq:NL9}
  \begin{array}{l}
      \mathcal R_{Lr}(r^{\alpha+1}_{k+1},x^{\alpha+1}_{k+1},\lambda^{\alpha+1}_{k+1}) = \mathcal
      R_{rk+1}^{\alpha} + (r^{\alpha+1}_{k+1} - r^{\alpha}_{k+1}) -
      K^{\alpha}_{k+1}(x^{\alpha+1}_{k+1} - x^{\alpha}_{k+1})- B^{\alpha}_{k+1}(\lambda^{\alpha+1}_{k+1} -
      \lambda^{\alpha}_{k+1})=0
    \end{array}
  \end{equation}
\begin{equation}
  \label{eq:rrL}
  \begin{array}{l}
    \boxed{r^{\alpha+1}_{k+1} = g(t_{k+1},x ^{\alpha}_{k+1},\lambda ^{\alpha}_{k+1}) +
      K^{\alpha}_{k+1}(x^{\alpha+1}_{k+1} - x^{\alpha}_{k+1})
      + B^{\alpha}_{k+1}(\lambda^{\alpha+1}_{k+1} - \lambda^{\alpha}_{k+1})
    }       
  \end{array}
\end{equation}
with,
\begin{equation}
     \begin{array}{l}
  K^{\alpha}_{k+1} = \nabla_xg(t_{k+1},x^{\alpha}_{k+1},\lambda ^{\alpha}_{k+1})  \\ \\
  B^{\alpha}_{k+1} = \nabla_{\lambda}g(t_{k+1},x^{\alpha}_{k+1},\lambda ^{\alpha}_{k+1})
 \end{array}
\end{equation}
and the  residue for $r$:
\begin{equation}
\boxed{\mathcal
      R_{rk+1}^{\alpha} = r^{\alpha}_{k+1} - g(t_{k+1},x^{\alpha}_{k+1},\lambda ^{\alpha}_{k+1})}
  \end{equation}


\paragraph{Reduction to a linear relation between  $x^{\alpha+1}_{k+1}$ and $\lambda^{\alpha+1}_{k+1}$}

Inserting (\ref{eq:rrL}) into~(\ref{eq:rfree-2}), we get the following linear relation between $x^{\alpha+1}_{k+1}$ and
$\lambda^{\alpha+1}_{k+1}$, 
\begin{equation}
  \label{eq:rfree-3}
  \begin{array}{l}
  \mathcal R^{\alpha}_{\free, k+1}  - h\gamma\left[  g(t_{k+1},x^{\alpha}_{k+1},\lambda^{\alpha}_{k+1}) +
    B^{\alpha}_{k+1} (\lambda^{\alpha+1}_{k+1} - \lambda^{\alpha}_{k+1})+K^{\alpha}_{k+1}
    (x^{\alpha+1}_{k+1} - x^{\alpha}_{k+1})  \right] \\
  \quad\quad - h(1-\gamma)r_k  + (M-h\theta A^{\alpha}_{k+1}) (x^{\alpha+1}_{k+1} -
    x^{\alpha}_{k+1})  =0
  \end{array}
\end{equation}
that is
\begin{equation}
  \label{eq:rfree-4}
  \begin{array}[l]{lcl}
  (M-h\theta A^{\alpha}_{k+1}-h\gamma K^{\alpha}_{k+1}) (x^{\alpha+1}_{k+1}  -  x^{\alpha}_{k+1}) &=& 
  -  \mathcal R^{\alpha}_{\free, k+1} -h(1-\gamma) r_k \\ & & + h\gamma \left[  g(t_{k+1},x^{\alpha}_{k+1},\lambda^{\alpha}_{k+1}) +
    B^{\alpha}_{k+1} (\lambda^{\alpha+1}_{k+1} - \lambda^{\alpha}_{k+1})  \right]  
\end{array}
\end{equation}

Let us introduce some intermediate notation:
\begin{equation}
   \label{eq:NL9}
   \begin{array}{l}
     W^{\alpha}_{k+1} \stackrel{\Delta}{=} M-h\theta A^{\alpha}_{k+1}-h\gamma K^{\alpha}_{k+1})\\
   \end{array}
 \end{equation}
 \begin{equation}
   \label{eq:rfree-12}
   \boxed{x^\alpha_{\free}\stackrel{\Delta}{=}x^{\alpha}_{k+1}-(W^{\alpha}_{k+1})^{-1}\mathcal (R_{\free,k+1}^{\alpha} \textcolor{red}{- h(1-\gamma) r_k})}
 \end{equation}
and 
\begin{equation}
  \boxed{x^\alpha_p \stackrel{\Delta}{=}  h\gamma(W^{\alpha}_{k+1} )^{-1}\left[g(t_{k+1},x^{\alpha}_{k+1},\lambda^{\alpha}_{k+1}) 
    -B^{\alpha}_{k+1} (\lambda^{\alpha}_{k+1}) \right ] +x^\alpha_{\free}}.
\end{equation}

The relation (\ref{eq:rfree-4}) can be written as
\begin{equation}
  \label{eq:rfree-13}
  \begin{array}{l}
    \boxed{   x^{\alpha+1}_{k+1}\stackrel{\Delta}{=}  x^\alpha_p +  \left[ h \gamma (W^{\alpha}_{k+1})^{-1}    B^{\alpha}_{k+1} \lambda^{\alpha+1}_{k+1}\right]}
   \end{array}
\end{equation}



\paragraph{Reduction to a linear relation between  $y^{\alpha+1}_{k+1}$ and
$\lambda^{\alpha+1}_{k+1}$.}

Inserting (\ref{eq:rfree-13}) into (\ref{eq:NL11y}), we get the following linear relation between $y^{\alpha+1}_{k+1}$ and $\lambda^{\alpha+1}_{k+1}$, 
\begin{equation}
   \begin{array}{l}
     y^{\alpha+1}_{k+1} = y_p + \left[ h \gamma C^{\alpha}_{k+1} ( W^{\alpha}_{k+1})^{-1}  B^{\alpha}_{k+1} + D^{\alpha}_{k+1} \right]\lambda^{\alpha+1}_{k+1}
   \end{array}
\end{equation}
with 
\begin{equation}\boxed{
    y_p = y^{\alpha}_{k+1} -\mathcal R^{\alpha}_{yk+1} + C^{\alpha}_{k+1}(x_q) -   D^{\alpha}_{k+1} \lambda^{\alpha}_{k+1} }
\end{equation}
\textcolor{red}{
  \begin{equation}
   \boxed{ x_q=x^\alpha_p -x^{\alpha}_{k+1}\label{eq:xqq}}
  \end{equation}
}







% \paragraph{With $\gamma =1$:}
% \[(W^{\alpha}_{k+1} )x^{\alpha+1}_{k+1}= hr^{\alpha+1}_{k+1}- \mathcal R_{\free, k+1} ^{\alpha}+W^{\alpha}_{k+1}x^{\alpha}_{k+1}\]
% \[x^{\alpha+1}_{k+1}= h( W^{\alpha}_{k+1})^{-1}r^{\alpha+1}_{k+1}-
% ( W^{\alpha}_{k+1})^{-1} \mathcal R_{\free k+1} ^{\alpha}+x^{\alpha}_{k+1}\]
% \[x^{\alpha+1}_{k+1}= h( W^{\alpha}_{k+1})^{-1}r^{\alpha+1}_{k+1}+x_{\free}\]
% with, using \ref{}
% \begin{equation}
% x_p-x^{\alpha}_{k+1}=h(
% W^{\alpha}_{k+1})^{-1}(g(x^{\alpha}_{k+1},\lambda^{\alpha}_{k+1},t_{k+1})-B^{\alpha}_{k+1}
% \lambda^{\alpha}_{k+1}-K^{\alpha}_{k+1} x^{\alpha}_{k}))+\tilde x_{\free}
% \end{equation}
% \[    \tilde x_{\free}= -( W^{\alpha}_{k+1})^{-1} \mathcal R _{\free k+1} ^{\alpha} \]
%       \[x_{\free} = \tilde x_{\free} + x^{\alpha}_{k+1}=\fbox{$- W^{-1}R_{\free k+1} ^{\alpha} + x^{\alpha}_{k+1}$}\]
% \[ \fbox{$x_p  = x_{\free} + h ( W^{\alpha}_{k+1})^{-1}( g(x ^{\alpha}_{k+1},\lambda ^{\alpha}_{k+1},t_{k+1}) -
%       B^{\alpha}_{k+1} \lambda^{\alpha}_{k+1}-K^{\alpha}_{k+1} x^{\alpha}_{k+1} )$} \]




\paragraph{Mixed linear complementarity problem (MLCP)}To summarize, the problem to be solved in each Newton iteration is:\\{
  \begin{minipage}[l]{1.0\linewidth}
    \begin{equation}
      \begin{cases}
      \begin{array}[l]{l}
        y^{\alpha+1}_{k+1} =   W_{mlcpk+1}^{\alpha}  \lambda^{\alpha+1}_{k+1} + b^{\alpha}_{k+1}
        \\ \\
        -y^{\alpha+1}_{k+1} \in N_{[l,u]}(\lambda^{\alpha+1}_{k+1} ). 
      \end{array}
      \label{eq:NL14}
      \end{cases}
    \end{equation}
  \end{minipage}
}
with $W_{mlcpk+1}\in \RR^{m\times m}$ and $b\in\RR^{m}$ defined by
\begin{equation}
  \label{eq:NL15}
 \begin{array}[l]{l}
   W_{mlcpk+1}^{\alpha} = h \gamma C^{\alpha}_{k+1}  (W^{\alpha}_{k+1})^{-1}  B^{\alpha}_{k+1} + D^{\alpha}_{k+1} \\
   b^{\alpha}_{k+1} = y_p
\end{array}
\end{equation}

The problem~(\ref{eq:NL14}) is equivalent to a Mixed Linear Complementarity Problem (MLCP) which can be solved under suitable assumptions by many linear complementarity solvers such as pivoting techniques, interior point techniques and splitting/projection strategies. The  reformulation into a standard MLCP follows the same line as for the MCP in the previous section. One obtains,
    \begin{equation}
      \begin{array}[l]{l}
        y^{\alpha+1}_{k+1} =   - W^{\alpha}_{k+1}  \lambda^{\alpha+1}_{k+1} + b^{\alpha}_{k+1}
        \\ \\
        (y^{\alpha+1}_{k+1})_i  = 0 \qquad \textrm{ for } i \in \{ 1..n\}\\[2mm]
        0 \leq  (\lambda^{\alpha+1}_{k+1})_i\perp (y^{\alpha+1}_{k+1})_i \geq 0 \qquad \textrm{ for } i \in \{ n..n+m\}\\
      \end{array}
      \label{eq:MLCP1} 
    \end{equation}




%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "DevNotes"
%%% End: