1 2Due 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. 3 4 \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 5\begin{equation} 6 \label{eq:NL3} 7 \mathcal R (x_{k+1},r _{k+1}) =0 8\end{equation} 9with 10\begin{equation} 11\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 12- h(1-\gamma)r_k. 13\end{equation} 14The 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 15 \begin{equation} 16 \label{eq:NL7} 17 \begin{cases} 18 x^{0}_{k+1} = x_k \\ \\ 19 r^{0}_{k+1} = r_k \\ \\ 20 \mathcal R_L( x^{\alpha+1}_{k+1},r^{\alpha+1}_{k+1}) = \mathcal 21 R(x^{\alpha}_{k+1},r^{\alpha}_{k+1}) + \left[ \nabla_{x} \mathcal 22 R(x^{\alpha}_{k+1},r^{\alpha}_{k+1})\right] (x^{\alpha+1}_{k+1}-x^{\alpha}_{k+1} ) + 23 \left[ \nabla_{r} \mathcal R(x^{\alpha}_{k+1},r^{\alpha}_{k+1})\right] (r^{\alpha+1}_{k+1} - r^{\alpha}_{k+1} ) =0 24 \end{cases} 25\end{equation} 26\begin{ndrva} 27 What about $r^0_{k+1}$ ? 28\end{ndrva} 29 30The residu \free $\mathcal R _{\free}$ is also defined (useful for implementation only): 31\[\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),\] 32which yields 33\[\mathcal R (x,r) = \mathcal R _{\free}(x) - h\gamma r - h(1-\gamma)r_k.\] 34 35\begin{equation} 36 \mathcal R (x^{\alpha}_{k+1},r^{\alpha}_{k+1}) = \fbox{$\mathcal R^{\alpha}_{k+1} \stackrel{\Delta}{=} \mathcal R 37_{\free}(x^{\alpha}_{k+1}) - h\gamma r^{\alpha}_{k+1} - h(1-\gamma)r_k$}\label{eq:rfree-1} 38\end{equation} 39 40\[ \mathcal R 41_{\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)$}\] 42 43% The computation of the Jacobian of $\mathcal R$ with respect to $x$, denoted by $ W^{\alpha}_{k+1}$ leads to 44% \begin{equation} 45% \label{eq:NL9} 46% \begin{array}{l} 47% 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} ).\\ 48% \end{array} 49% \end{equation} 50At each time--step, we have to solve the following linearized problem, 51\begin{equation} 52 \label{eq:NL10} 53 \mathcal R^{\alpha}_{k+1} + (M-h\theta A ^{\alpha}_{k+1}) (x^{\alpha+1}_{k+1} - 54 x^{\alpha}_{k+1}) - h \gamma (r^{\alpha+1}_{k+1} - r^{\alpha}_{k+1} ) =0 , 55\end{equation} 56with 57\begin{equation} 58 \begin{array}{l} 59 A^{\alpha}_{k+1} = \nabla_x f(t_{k+1}, x^{\alpha}_{k+1}) 60 \end{array} 61\end{equation} 62 63By using (\ref{eq:rfree-1}), we get 64\begin{equation} 65 \label{eq:rfree-2} 66 \mathcal R 67_{\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} - 68 x^{\alpha}_{k+1}) =0 69\end{equation} 70 71% %\fbox 72% { 73% \begin{equation} 74% \label{eq:rfree-11} 75% \boxed{ x^{\alpha+1}_{k+1} = h\gamma (W^{\alpha}_{k+1})^{-1}r^{\alpha+1}_{k+1} +x^\alpha_{\free}} 76% \end{equation} 77% } 78% with : 79% \begin{equation} 80% \label{eq:rfree-12} 81% \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})} 82% \end{equation} 83 84The matrix $W$ is clearly non singular for small $h$. 85 86 87 88 89% that is 90 91% \begin{equation} 92% \begin{array}{l} 93% h \gamma r^{\alpha+1}_{k+1} = r_c + W^{\alpha}_{k+1} x^{\alpha+1}_{k+1} 94% .\label{eq:NL11} 95% \end{array} 96% \end{equation} 97% with 98% \begin{equation} 99% \begin{array}{l} 100% r_c \stackrel{\Delta}{=} h \gamma r^{\alpha}_{k+1} - W^{\alpha}_{k+1} x^{\alpha}_{k+1} + \mathcal R 101% ^{\alpha}_{k+1}=- W^{\alpha}_{k+1} x^{\alpha}_{k+1} + \mathcal R_{\free k+1} ^{\alpha} - h(1-\gamma)r_k\\ \\ 102% \end{array} 103% \end{equation} 104% \begin{equation} 105% \begin{array}{l} 106% \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) 107% - h \gamma r^{\alpha}_{k+1} -h(1- \gamma)r_k 108% \end{array} 109% \end{equation} 110% \[x^{\alpha+1}_{k+1} = h(W^{\alpha}_{k+1})^{-1}r^{\alpha+1}_{k+1} +(W^{\alpha}_{k+1})^{-1}(\mathcal 111% R_{\free k+1} ^{\alpha})+x^{\alpha}_{k+1}\] 112 113 \paragraph{Newton's linearization of the second line of~(\ref{eq:toto1})} 114The same operation is performed with the second equation of (\ref{eq:toto1}) 115\begin{equation} 116 \begin{array}{l} 117 \mathcal R_y(x,y,\lambda)=y-h(t_{k+1},x,\lambda) =0\\ \\ 118 \end{array} 119\end{equation} 120which is linearized as 121\begin{equation} 122 \label{eq:NL9} 123 \begin{array}{l} 124 \mathcal R_{Ly}(x^{\alpha+1}_{k+1},y^{\alpha+1}_{k+1},\lambda^{\alpha+1}_{k+1}) = \mathcal 125 R_{y}(x^{\alpha}_{k+1},y^{\alpha}_{k+1},\lambda^{\alpha}_{k+1}) + 126 (y^{\alpha+1}_{k+1}-y^{\alpha}_{k+1})- \\[2mm] \qquad \qquad \qquad \qquad \qquad \qquad 127 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 128 \end{array} 129\end{equation} 130 131This leads to the following linear equation 132\begin{equation} 133 \boxed{y^{\alpha+1}_{k+1} = y^{\alpha}_{k+1} 134 -\mathcal R^{\alpha}_{yk+1}+ \\ 135 C^{\alpha}_{k+1}(x^{\alpha+1}_{k+1}-x^{\alpha}_{k+1}) + 136 D^{\alpha}_{k+1}(\lambda^{\alpha+1}_{k+1}-\lambda^{\alpha}_{k+1})}. \label{eq:NL11y} 137\end{equation} 138with, 139\begin{equation} 140 \begin{array}{l} 141 C^{\alpha}_{k+1} = \nabla_xh(t_{k+1}, x^{\alpha}_{k+1},\lambda^{\alpha}_{k+1} ) \\ \\ 142 D^{\alpha}_{k+1} = \nabla_{\lambda}h(t_{k+1}, x^{\alpha}_{k+1},\lambda^{\alpha}_{k+1}) 143 \end{array} 144\end{equation} 145and 146\begin{equation}\fbox{$ 147\mathcal R^{\alpha}_{yk+1} \stackrel{\Delta}{=} y^{\alpha}_{k+1} - h(x^{\alpha}_{k+1},\lambda^{\alpha}_{k+1})$} 148 \end{equation} 149 \paragraph{Newton's linearization of the third line of~(\ref{eq:toto1})} 150The same operation is performed with the third equation of (\ref{eq:toto1}) 151\begin{equation} 152 \begin{array}{l} 153 \mathcal R_r(r,x,\lambda)=r-g(t_{k+1},x,\lambda) =0\\ \\ \end{array} 154\end{equation} 155which is linearized as 156\begin{equation} 157 \label{eq:NL9} 158 \begin{array}{l} 159 \mathcal R_{Lr}(r^{\alpha+1}_{k+1},x^{\alpha+1}_{k+1},\lambda^{\alpha+1}_{k+1}) = \mathcal 160 R_{rk+1}^{\alpha} + (r^{\alpha+1}_{k+1} - r^{\alpha}_{k+1}) - 161 K^{\alpha}_{k+1}(x^{\alpha+1}_{k+1} - x^{\alpha}_{k+1})- B^{\alpha}_{k+1}(\lambda^{\alpha+1}_{k+1} - 162 \lambda^{\alpha}_{k+1})=0 163 \end{array} 164 \end{equation} 165\begin{equation} 166 \label{eq:rrL} 167 \begin{array}{l} 168 \boxed{r^{\alpha+1}_{k+1} = g(t_{k+1},x ^{\alpha}_{k+1},\lambda ^{\alpha}_{k+1}) + 169 K^{\alpha}_{k+1}(x^{\alpha+1}_{k+1} - x^{\alpha}_{k+1}) 170 + B^{\alpha}_{k+1}(\lambda^{\alpha+1}_{k+1} - \lambda^{\alpha}_{k+1}) 171 } 172 \end{array} 173\end{equation} 174with, 175\begin{equation} 176 \begin{array}{l} 177 K^{\alpha}_{k+1} = \nabla_xg(t_{k+1},x^{\alpha}_{k+1},\lambda ^{\alpha}_{k+1}) \\ \\ 178 B^{\alpha}_{k+1} = \nabla_{\lambda}g(t_{k+1},x^{\alpha}_{k+1},\lambda ^{\alpha}_{k+1}) 179 \end{array} 180\end{equation} 181and the residue for $r$: 182\begin{equation} 183\boxed{\mathcal 184 R_{rk+1}^{\alpha} = r^{\alpha}_{k+1} - g(t_{k+1},x^{\alpha}_{k+1},\lambda ^{\alpha}_{k+1})} 185 \end{equation} 186 187 188\paragraph{Reduction to a linear relation between $x^{\alpha+1}_{k+1}$ and $\lambda^{\alpha+1}_{k+1}$} 189 190Inserting (\ref{eq:rrL}) into~(\ref{eq:rfree-2}), we get the following linear relation between $x^{\alpha+1}_{k+1}$ and 191$\lambda^{\alpha+1}_{k+1}$, 192\begin{equation} 193 \label{eq:rfree-3} 194 \begin{array}{l} 195 \mathcal R^{\alpha}_{\free, k+1} - h\gamma\left[ g(t_{k+1},x^{\alpha}_{k+1},\lambda^{\alpha}_{k+1}) + 196 B^{\alpha}_{k+1} (\lambda^{\alpha+1}_{k+1} - \lambda^{\alpha}_{k+1})+K^{\alpha}_{k+1} 197 (x^{\alpha+1}_{k+1} - x^{\alpha}_{k+1}) \right] \\ 198 \quad\quad - h(1-\gamma)r_k + (M-h\theta A^{\alpha}_{k+1}) (x^{\alpha+1}_{k+1} - 199 x^{\alpha}_{k+1}) =0 200 \end{array} 201\end{equation} 202that is 203\begin{equation} 204 \label{eq:rfree-4} 205 \begin{array}[l]{lcl} 206 (M-h\theta A^{\alpha}_{k+1}-h\gamma K^{\alpha}_{k+1}) (x^{\alpha+1}_{k+1} - x^{\alpha}_{k+1}) &=& 207 - \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}) + 208 B^{\alpha}_{k+1} (\lambda^{\alpha+1}_{k+1} - \lambda^{\alpha}_{k+1}) \right] 209\end{array} 210\end{equation} 211 212Let us introduce some intermediate notation: 213\begin{equation} 214 \label{eq:NL9} 215 \begin{array}{l} 216 W^{\alpha}_{k+1} \stackrel{\Delta}{=} M-h\theta A^{\alpha}_{k+1}-h\gamma K^{\alpha}_{k+1})\\ 217 \end{array} 218 \end{equation} 219 \begin{equation} 220 \label{eq:rfree-12} 221 \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})} 222 \end{equation} 223and 224\begin{equation} 225 \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}) 226 -B^{\alpha}_{k+1} (\lambda^{\alpha}_{k+1}) \right ] +x^\alpha_{\free}}. 227\end{equation} 228 229The relation (\ref{eq:rfree-4}) can be written as 230\begin{equation} 231 \label{eq:rfree-13} 232 \begin{array}{l} 233 \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]} 234 \end{array} 235\end{equation} 236 237 238 239\paragraph{Reduction to a linear relation between $y^{\alpha+1}_{k+1}$ and 240$\lambda^{\alpha+1}_{k+1}$.} 241 242Inserting (\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}$, 243\begin{equation} 244 \begin{array}{l} 245 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} 246 \end{array} 247\end{equation} 248with 249\begin{equation}\boxed{ 250 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} } 251\end{equation} 252\textcolor{red}{ 253 \begin{equation} 254 \boxed{ x_q=x^\alpha_p -x^{\alpha}_{k+1}\label{eq:xqq}} 255 \end{equation} 256} 257 258 259 260 261 262 263 264% \paragraph{With $\gamma =1$:} 265% \[(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}\] 266% \[x^{\alpha+1}_{k+1}= h( W^{\alpha}_{k+1})^{-1}r^{\alpha+1}_{k+1}- 267% ( W^{\alpha}_{k+1})^{-1} \mathcal R_{\free k+1} ^{\alpha}+x^{\alpha}_{k+1}\] 268% \[x^{\alpha+1}_{k+1}= h( W^{\alpha}_{k+1})^{-1}r^{\alpha+1}_{k+1}+x_{\free}\] 269% with, using \ref{} 270% \begin{equation} 271% x_p-x^{\alpha}_{k+1}=h( 272% W^{\alpha}_{k+1})^{-1}(g(x^{\alpha}_{k+1},\lambda^{\alpha}_{k+1},t_{k+1})-B^{\alpha}_{k+1} 273% \lambda^{\alpha}_{k+1}-K^{\alpha}_{k+1} x^{\alpha}_{k}))+\tilde x_{\free} 274% \end{equation} 275% \[ \tilde x_{\free}= -( W^{\alpha}_{k+1})^{-1} \mathcal R _{\free k+1} ^{\alpha} \] 276% \[x_{\free} = \tilde x_{\free} + x^{\alpha}_{k+1}=\fbox{$- W^{-1}R_{\free k+1} ^{\alpha} + x^{\alpha}_{k+1}$}\] 277% \[ \fbox{$x_p = x_{\free} + h ( W^{\alpha}_{k+1})^{-1}( g(x ^{\alpha}_{k+1},\lambda ^{\alpha}_{k+1},t_{k+1}) - 278% B^{\alpha}_{k+1} \lambda^{\alpha}_{k+1}-K^{\alpha}_{k+1} x^{\alpha}_{k+1} )$} \] 279 280 281 282 283\paragraph{Mixed linear complementarity problem (MLCP)}To summarize, the problem to be solved in each Newton iteration is:\\{ 284 \begin{minipage}[l]{1.0\linewidth} 285 \begin{equation} 286 \begin{cases} 287 \begin{array}[l]{l} 288 y^{\alpha+1}_{k+1} = W_{mlcpk+1}^{\alpha} \lambda^{\alpha+1}_{k+1} + b^{\alpha}_{k+1} 289 \\ \\ 290 -y^{\alpha+1}_{k+1} \in N_{[l,u]}(\lambda^{\alpha+1}_{k+1} ). 291 \end{array} 292 \label{eq:NL14} 293 \end{cases} 294 \end{equation} 295 \end{minipage} 296} 297with $W_{mlcpk+1}\in \RR^{m\times m}$ and $b\in\RR^{m}$ defined by 298\begin{equation} 299 \label{eq:NL15} 300 \begin{array}[l]{l} 301 W_{mlcpk+1}^{\alpha} = h \gamma C^{\alpha}_{k+1} (W^{\alpha}_{k+1})^{-1} B^{\alpha}_{k+1} + D^{\alpha}_{k+1} \\ 302 b^{\alpha}_{k+1} = y_p 303\end{array} 304\end{equation} 305 306The 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, 307 \begin{equation} 308 \begin{array}[l]{l} 309 y^{\alpha+1}_{k+1} = - W^{\alpha}_{k+1} \lambda^{\alpha+1}_{k+1} + b^{\alpha}_{k+1} 310 \\ \\ 311 (y^{\alpha+1}_{k+1})_i = 0 \qquad \textrm{ for } i \in \{ 1..n\}\\[2mm] 312 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\}\\ 313 \end{array} 314 \label{eq:MLCP1} 315 \end{equation} 316 317 318 319 320%%% Local Variables: 321%%% mode: latex 322%%% TeX-master: "DevNotes" 323%%% End: