The R-linear convergence rate of an algorithm arising from the semi-smooth Newton method applied to 2D contact problems with friction

Abstract

The goal is to analyze the semi-smooth Newton method applied to the solution of contact problems with friction in two space dimensions. The primal-dual algorithm for problems with the Tresca friction law is reformulated by eliminating primal variables. The resulting dual algorithm uses the conjugate gradient method for inexact solving of inner linear systems. The globally convergent algorithm based on computing a monotonously decreasing sequence is proposed and its R-linear convergence rate is proved. Numerical experiments illustrate the performance of different implementations including the Coulomb friction law.

Appendix

(A1) Let $\mathcal {A}, \mathcal {I}$ be index sets such that $\mathcal {A}\cup \mathcal {I}= \{1,2,\dots ,2m\}$ and $\mathcal {A}\cap \mathcal {I}=\emptyset$. We consider the problem

$$\begin{aligned} \bar{\lambda } = \arg \min q(\lambda ) \ \ \ \hbox {subject to } \lambda _\mathcal {I}= \lambda ^{k+1,0}_\mathcal {I}, \end{aligned}$$

(7.1)

where $q(\lambda )=\frac{1}{2}\lambda ^\top A \lambda -\lambda ^\top b$ is given by $A\in {\mathbb {R}}^{2m\times 2m}$ being symmetric, positive definite, $b\in {\mathbb {R}}^{2m}$, and $\lambda ^{k+1,0}\in \varLambda$. Recall that $\varLambda =\{\lambda \in {\mathbb {R}}^{2m}: 0\le \lambda _i, \ |\lambda _{i+m}|\le g_i, \ i\in \mathcal {M}\}$ and $r=r(\lambda )=A\lambda -b$. We introduce the $\hbox {CGM}_{ feas}$ with the stopping tolerance tol $=$ tol $^{k+1}>0$.

$\underline{\hbox {CGM}_{\textit{feas}} (A,b,\mathcal {A},\lambda ^{k+1,0}, { tol})}$

• (1) $r=A\lambda ^{k+1,0}-b$, $p_\mathcal {A}=r_\mathcal {A}$, $p_\mathcal {I}=0$, $j=0$

• (2) while $\Vert r_\mathcal {A}\Vert >\textit{tol} \, \Vert b\Vert$ and $\lambda ^{k+1,j}\in \varLambda$

• (3)       $w=Ap$, $\alpha _{ cg}=r^\top p/p^\top w$

• (4)       $\lambda ^{k+1,j+1}=\lambda ^{k+1,j}-\alpha _{ cg} p$, $j=j+1$

• (5)       $r=r-\alpha _{ cg} w$, $\gamma =r_\mathcal {A}^\top w_\mathcal {A}/p^\top w$, $p_\mathcal {A}=r_\mathcal {A}-\gamma p_\mathcal {A}$

• (6) endwhile

• (7) if $\lambda ^{k+1,j} \in \varLambda$

• (8)       return $\lambda ^{k+1}=\lambda ^{k+1,j}$

• (9) elseif $\lambda ^{k+1,j} \not \in \varLambda$

• (10)       $\alpha _f=\max \{\alpha \in [0,1): \ \alpha \lambda ^{k+1,j}-(1-\alpha ) \lambda ^{k+1,j-1}\in \varLambda \}$

• (11)       return $\lambda ^{k+1}=\alpha _f \lambda ^{k+1,j}-(1-\alpha _f) \lambda ^{k+1,j-1}$

• (12) endif

Steps (2)–(6) represent the standard CGM loop with added the feasibility test $\lambda ^{k+1,j}\in \varLambda$ in step (2). Steps (7)–(12) define the result $\lambda ^{k+1}\in \varLambda$ returned by the $\hbox {CGM}_{ feas}$. If $\lambda ^{k+1,j} \not \in \varLambda$, $\lambda ^{k+1}$ is determined by the largest feasible steplength $\alpha _f$ in the last conjugate gradient direction. This is called the half step in [5, 7, 9, 10, 18]. Note that the $\hbox {CGM}_{ feas}$ performs typically few CGM iterations.

(A2) The CGM for solving (7.1) differs from the $\hbox {CGM}_{ feas}$ as follows: the feasibility test is omitted from step (2) and steps (7)–(12) are replaced by one return step $\lambda ^{k+1}=\lambda ^{k+1,j}$.

(A3) Let us replace the initial CGM iteration in Step 3.2 of Algorithm GISSNM so that

$$\begin{aligned} \lambda _\mathcal {A}^{k+1,0}=\lambda _\mathcal {A}^k, \ \ \ \lambda _\mathcal {I}^{k+1,0}=P_{\varLambda ,\mathcal {I}}(\lambda ^{k}-\rho r(\lambda ^{k})). \end{aligned}$$

(7.2)

The first CGM iteration (given by step (4) of the $\hbox {CGM}_{ feas}$ with $j=0$) satisfies:

$$\begin{aligned} \lambda _\mathcal {I}^{k+1,1}= \lambda _\mathcal {I}^{k+1,0} = P_{\varLambda ,\mathcal {I}}( \lambda ^{k}-\rho r ( \lambda ^{k})) \end{aligned}$$

and

$$\begin{aligned} \lambda _\mathcal {A}^{k+1,1}&= \lambda ^{k+1,0}_\mathcal {A}-\alpha _{ cg} r_\mathcal {A}( \lambda ^{k+1,0}) \\&= \lambda ^{k+1,0}_\mathcal {A}-\alpha _{ cg} ( A_{\mathcal {A}\mathcal {A}}\lambda ^{k+1,0}_\mathcal {A}+ A_{\mathcal {A}\mathcal {I}}\lambda ^{k+1,0}_\mathcal {I}- b_\mathcal {A})\\&= \lambda ^{k}_\mathcal {A}-\alpha _{ cg} ( A_{\mathcal {A}\mathcal {A}}\lambda ^{k}_\mathcal {A}+ A_{\mathcal {A}\mathcal {I}}P_{\varLambda ,\mathcal {I}}(\lambda ^{k}-\rho r(\lambda ^{k}) ) - b_\mathcal {A})\\&= \lambda ^{k}_\mathcal {A}-\alpha _{ cg} (r_\mathcal {A}(\lambda ^{k}) + A_{\mathcal {A}\mathcal {I}} ( P_{\varLambda ,\mathcal {I}}(\lambda ^{k}-\rho r(\lambda ^{k}))-\lambda _\mathcal {I}^k))\\&= \lambda ^{k}_\mathcal {A}-\alpha _{ cg} r_\mathcal {A}(\lambda ^{k})+\alpha _{ cg}\rho A_{\mathcal {A}\mathcal {I}}\widetilde{r}_{\rho ,\mathcal {I}}(\lambda ^{k})\\&= \lambda ^{k}_\mathcal {A}-\rho r_\mathcal {A}(\lambda ^{k}) - (\alpha _{ cg}-\rho ) r_\mathcal {A}(\lambda ^{k}) + \alpha _{ cg} \rho A_{\mathcal {A}\mathcal {I}} \widetilde{r}_{\rho ,\mathcal {I}}(\lambda ^{k})\!, \end{aligned}$$

where $\widetilde{r}_\rho ,$ denotes the reduced gradient (2.14) with $\alpha =\rho$. Due to the definition of the active/inactive sets (3.8)-(3.12), we have $P_{\varLambda ,\mathcal {A}} \left( \lambda ^{k} -\rho r\left( \lambda ^{k}\right) \right) = \lambda ^{k}_\mathcal {A}-\rho r_\mathcal {A}\left( \lambda ^{k}\right)$ so that

$$\begin{aligned} \lambda ^{k+1,1}= P_{\varLambda } (\lambda ^{k}-\rho r ( \lambda ^{k} )) - s(\lambda ^{k}) \end{aligned}$$

(7.3)

with $s_\mathcal {I}(\lambda ^{k})=0$ and $s_\mathcal {A}(\lambda ^{k})=(\alpha _{ cg}-\rho ) r_\mathcal {A}\left( \lambda ^{k}\right) - \alpha _{ cg} \rho A_{\mathcal {A}\mathcal {I}} \widetilde{r}_{\rho ,\mathcal {I}}\left( \lambda ^{k}\right)$. The following inequalities follows from the CGM:

$$\begin{aligned} q(\lambda ^k) \ge q(\lambda ^{k+1,0}) \ge q(\lambda ^{k+1,1}). \end{aligned}$$

Under assumptions that $\rho \le \alpha _{ cg}$ and $\widetilde{r}_{\rho ,\mathcal {I}}\left( \lambda ^{k}\right)$ is sufficiently small, one can prove:

$$\begin{aligned} q(\lambda ^{k+1,0}) \ge q ( P_{\varLambda } ( \lambda ^{k}-\rho r ( \lambda ^{k} ))) \ge q(\lambda ^{k+1,1}). \end{aligned}$$

(7.4)

The following interpretation yields from (7.3) and (7.4): if the initial CGM iteration is given by (7.2), the full projection $P_{\varLambda } \left( \lambda ^{k}-\rho r \left( \lambda ^{k} \right) \right)$ is inherently included in the SSNM after the first CGM iteration.