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: