Generalized Newton’s Method for Solving Nonlinear and Nondifferentiable Algebraic Systems

Nicolae Pop$^\ast $

March 23, 2015.

$^\ast $Institute of Solid Mechanics of the Romanian Academy, C-tin Mille str. Nr. 15, Bucharest and Department of Mathematics and Computer Science, Faculty of Sciences, North University Center at Baia Mare, Technical University of Cluj-Napoca, e-mail: nicpop@gmail.com.

Dedicated to prof. I. Păvăloiu on the occasion of his 75th anniversary

In this paper a model based on non-smooth equations is proposed for solving a non-linear and non-differential equation obtained by discretization of a quasi-variational inequality that models the frictional contact problem. The main aim of this paper is to show that the Newton method based on the plenary hull of the Clarke generalized Jacobians (the non-smooth damped Newton method) can be implemented for solving Lipschitz non-smooth equation.

MSC. 90C30, 90C56, 90C53, 49J52.

Keywords. nonlinear programming, generalized derivatives, quasi-Newton methods, nonsmoots analysis.

1 Introduction

The solving of nonlinear equations is based on the concept of approximation. Perhaps the best known and used approximation method is the one of successive approximations, due to Emile Picard [ 14 ] . In the case of nonlinear equation systems, the most commonly used method is Newton-Raphson’s method. I. V. Kantorovici [ 7 ] , [ 8 ] , proves the convergence conditions of Newton-Raphson’s method.

First we recall two important results on the Newton-Raphson method, which consist in weakening the assumptions. Thus, on one hand Barthle’s result [ 5 ] , shows that we can apply Newton-Raphson’s method, without imposing conditions on the second order derivative, and on the other hand, Altman [ 3 ] , solves the problem, in certain conditions without imposing the existence of the inverse of the first order derivative in the initial point.

I. K. Argyros and S. George [ 4 ] , introduce a family of iterative methods that does not use derivatives, for solving the nonlinear and nondifferentiable system $F(x)=0$. Specifically, the authors use the classical Secant method and approximates the first derivative of $F$ from a divided difference of first order:$F'(x_n)\backsimeq [x_{n-1},x_n; F]$, where, $[x, y; F]$ is a divided difference of firs order for F at the point $x, y$. In the paper specified, the authors introduce the Chebyshev-Kurchakov-type method:
$ y_n=x_n-[2x_n-x_{n-1}, x_{n-1};F]^{-1}F(x_n),$
$ z_n=x_n+a(y_n-x_n),$
$ x_{n+1}=x_n-[2x_n-x_{n-1}, x_{n-1};F]^{-1}(bF(x_n)+cF(z_n)), n\geqq 0$,
where $x_{-1}, x_0$ are given and $a,b,c$ are non-negative parameters to be chosen so that the sequence ${x_n}$ is convergent.

I. Pavaloiu [ 11 ] – [ 12 ] , introduces and studies the convergence of Aitken-Steffensen-type methods for nonsmooth and nonlinear equations.

In recent years, Newton-Raphson method has been generalized to solve problems in mathematical programming. A treatment of such wide generalizations was made by S. M. Robinson in [ 18 ] and [ 19 ] .

The nonlinear systems from the discretization of contact problems are included in the category of problems with nondifferentiable terms. In this class lies the work of Pang [ 10 ] , who refers to Newton’s method for $B$-differential equations. The notion of $B$-differentiability (B from Buligand) is similar to the one of directional differentiability and it was introduced by Robinson [ 20 ] .

In general, a $B$-differentiable function is not $F$-differentiable, but can be approximated by a simplified function in the same way as a $F$-differentiable function by its $F$-derivative.

Pang showed that, for this type of equations, Newton’s method is quadratic convergent, if the pointwise solution is pointwise differentiable. Using a search technique through linear steps, one can prove also the global convergence.

A convergence theorem under the condition of semismoothness, was been given by L. Qi in [ 17 ] , for solving the nonlinear systems with Newton’s method.

As in [ 15 ] we will emphasize the equivalence between the proof of the generalized Newton method, for nonlinear and nondifferentiable equations, using the $B$-differentiability notion with the proof which involves the notion of generalized Jacobian.

2 Properties of the B-differentiable functions and the generalized Newton method

Definition 2.1

A function $F:\mathbb R^n\to \mathbb R^n$, is called $B$-differentiable at $z\in \mathbb R^n$ if there exists a function $BF(z):\mathbb R^n\to \mathbb R^n$, called the $B$-derivative of $F$ at $z$, which is positive homogenous of first degree, i.e. $BF(z)(\lambda v)=\lambda BF(z)v$, for all $ v\in \mathbb R^n$ and $\lambda {\gt}0$, such that

\[ \lim _{v\to 0}\tfrac {F(z+v)-F(z)-BF(z)v}{\| v\| }=0. \]

If $F$ is $B$-differentiable at each point of a certain set $S\subset \mathbb R^n$, then we say that $F$ is $B$-differentiable on $S$.

In the original definition of the $B$-differentiability, Robinson [ 20 ] , expressed the positive homogeneity of the $B$-derivative of the function $F$ in terms of the cone of the graph of function $F.$ A fundamental distinction between a $B$-differentiable function and a $F$-differentiable one is that the $B$-derivative is nonlinear.

The main properties of a $B$-differentiable function are summarized in the following proposition.

Proposition 2.2

Let the function $F:\mathbb R^n\to \mathbb R^n$ be locally Lipschitz at $z$.

$(i)$ If $F$ is $F$-differentiable at the point $z,$ then it is also $B$-differentiable and the expression of $BF(z)$ is given by $BF(z)=\nabla F(z)$. Conversely, if $F$ is $B$-differentiable at the point $z$ and its $B$-derivative, $BF(z)v$ is linear in $v$, then $F$ is $F$-differentiable at $z$;

$(ii)$ If $F$ is $B$-differentiable at $z$, then its $B$-derivative is unique. Furthermore, $BF(z)$ is Lipschitz and has the same modulus as $F;$

$(iii)$ If $F$ is $B$-differentiable at the point $z$, then $F$ is directionally differentiable at $z$ with respect to each direction $d$ and $F'_d(z)=BF(z)d$.

In the paper [ 21 ] , Shapiro showed that if $F$ is locally Lipschitz at $z$, the converse of the third statement(iii), also holds. Namely, if $F$ is directionally differentiable at the point $z$, then F is $B$-differentiable.

Let $F:\mathbb R^n\to \mathbb R^n$ be a $B$-differentiable function. Further on, our purpose is to solve the following nonlinear system

\begin{equation} \label{6.1} F(z)=0. \end{equation}

2.1

Extending Newton’s classical method for solving the $F$-differentiable systems, we will define an iterative method.

Let $z^k$, be a given iteration, we intend to solve the following system with respect to $d^k$

\begin{equation} \label{6.2} F(z^k)+BF(z^k)d^k=0 \end{equation}

2.2

where $z^{k+1}=z^k+d^k$. The algorithm continues until the stopping conditions are satisfied. In general, (2.2) is a nonlinear equation system (because $BF$ is nonlinear) and we call it generalized Newton system.

Definition 2.3

We say that $F$ has a strong $F$-derivative, and we denote it by $\nabla F(z)$, if

\[ \lim _{(x,y)\to (z,z)}\tfrac {F(x)-F(y)-\nabla F(z)(x-y)}{\| x-y\| }=0. \]

It is natural to wonder wether (2.2) has a solution or not? Furthermore if this solution exists, is it unique or not? Is the sequence $\{ z^{k}\} $ convergent to the solution of $F$?

In general, under the hypothesis that the starting point $ z^0 $ is arbitrary chosen, it is difficult to suppose that the sequence $ \{ z ^k \} $ is convergent. Hence, the global convergence is unlikely to happen. This dead end can be overcome by introducing a norm function (called pseudo-potential), which provides the search direction of the solution, as shown in

Lemma 2.4

Let the function $F:\mathbb R^n\to \mathbb R^n$ be $B$-differentiable and let $G:\mathbb R^n\to \mathbb R$ be a function defined as

\[ G(z)=(1/2)F(z)^T F(z), \]

then, $G$ is also $B$-differentiable with

\[ BG(z)d=F(z)^T BF(z). \]

Furthermore, if $(\ref{6.2})$ holds, then

\begin{equation} \label{6.3} G'_{d^k}(z^k)=-F(z^k)^T F(z^k). \end{equation}

2.3

Proof. The proof results easily from $G'_d(z)=BG(z)d$, because the relation (2.3) holds from the expression of the $G's$ $B$-derivative and from the relation (2.2).

An important consequence of the relation (2.3) is that if the iteration $ z^k $ of $F$ is not a solution of $F$, i.e. $ F(z^k)\neq 0 $, then each solution $ z ^k $, of the generalized Newton equation (2.2) provides a descent search direction (for the norm function $ G $). Thus, we can establish a linear search algorithm in order to find the next iteration (see ( [ 10 ] ), where we use (2.3)). The main convergence result is

Theorem 2.5

[ 10 ] Let $F:\mathbb R^n\to \mathbb R^n$ be a $B$-differentiable function at an arbitrary point $z_{0}$ and $G(z)=(1/2)F(z)^T F(z)$.

We assume that the following statements hold:

$a)$The level set $\{ z\in \mathbb R^n|\| F(z)\| \leq \| F(z^0)\| \} $ is bounded;

$b)$ Each generalized Newton equation has a solution. Let $\{ z^k\} $ be a generalized sequence, using Newton’s method (following the pattern of the algorithm presented in [ 10 ] ), and let also $F(z^k)\neq 0$, then the below conclusions are fulfilled

$(i)$ $\| F(z^{k+1})\| {\lt}\| F(z^k)\| $;

$(ii)$ The sequence $\{ z^k\} $ is bounded;

$(iii)$ If $\overline z$ is an accumulation point of the sequence $\{ z^k\} $ such that, if the $F$-derivative $\nabla G(z)$ is strong and if there exists a neighborhood, $V$ of $\overline z$ and a positive scalar $c{\gt}0$, such that for each $x\in V$ and for each $v\in \mathbb R^n$ the inequality $\| BF(x)v\| \geq c\| v\| $, is satisfied, then $F(\overline z)=0$;

$(iv)$ If $\lim \limits _{k\to \infty }\inf \alpha _k{\gt}0$, then each accumulation point of $\{ z^k\} $ is a zero of $F,$ where $\alpha _k$ is given by $z^{k+1}=z^k+\alpha _k d^k$.

The proof can be found in [ 10 ] .

Remarks 2.6

$1^\circ $. The hypothesis $a)$ is equivalent with the property that $F$ is coercive, i.e. $\lim \limits _{\| z\| \to \infty }\| F(z)\| =\infty $.

$2^\circ $. The third statement, $iii)$ requires a strong $F$-propriety at the accumulation point on the norm function $G$ but not on $F$. In general, if $F$ has an $F$-derivative at $z$, then so does $G$. The converse result is not true, $F(z)=|z|$ is a contraexample.

$ 3^\circ $. From the above theorem we can not conclude that the generalized Newton equation (2.2) has a unique solution (in [ 10 ] it is shown that the local solution is unique because $BF$ is injective).

3 The generalized Jacobian for solving the nonlinear and nondifferentiable systems

In the idea of weakening the notion of differentiability, Clarke [ 6 ] , defines the generalized Jacobian following the subdifferentiability model.

Definition 3.1

Let $F:\mathbb R^n\to \mathbb R^n$ be a continuous, Lipschitz application.
Then the generalized Jacobian at $x$, denoted by $\partial F(x)$, is defined as the convex coverage of all matrices obtained as a limit of the sequences $JF(x_i)$, for $x_i\to x$ and $x_i\not\in \Omega _F$, where $\Omega _F$ is the set of points where $F$ is nondifferentiable, and $JF(x_i)$ is the Jacobian matrix of $F,$ i.e.

\[ \partial F(x)=co\, \{ \lim JF(x_i); x_i\to x,\; x_i\not\in \Omega _F\} . \]

Remark 3.2

The condition that $F$ is Lipschitz is important, because it ensures that measure of $ \Omega _F$ is not void and therefore the limit has sense.

The following result [ 1 ] leads us to a sufficient condition for the existence of solutions of a nonlinear and nondifferentiable algebraic system, solutions obtained with the generalized Newton method (using the notion of generalized gradient). This result is easily applicable for the contact problems.

Theorem 3.3

If the application $F:\mathbb R^n\to \mathbb R^n$ is continuous, Lipschitz, and affine on a finite number of open cones, pointed at $x_0$ and if $\det M\neq 0$, for all $ M\in \partial F(x_0)$, then $F$ is a global homeomorphism from $\mathbb R^n$ into $\mathbb R^n$.

Proof â–¼

The proof can be found in [ 1 ] . Due to this theorem one can easily verify the lack of injectivity of the application $F.$

Further on we shall apply Newton’s method in terms of the generalized Jacobian for the following nonlinear and non differential algebraic system

\begin{equation} \label{6.4} K u+ F(u)=Q, \end{equation}

3.1

where $u$ is the vector unknowns, $K$ is the matrix coefficients (differentiable components), $Q$ is the free term, and finally $F(u)$ is the undifferentiable components of the system.

Thus the generalized Newton algorithm is given by

\begin{align} \label{6.5} M^k \Delta u^k& =Q-K(u^k)-F(u^k),\; M^k\in K+\partial F(u^k),\quad k=0,1,\dots \\ \Leftrightarrow u^{k-1} & =u^k-M^{-1} G(u^k),\; M\in \partial G(u^k), \quad k=0,1,\dots \nonumber \end{align}

Next, we will verify the conditions of Theorem 3.3 for the equation (3.1). So, we denote by $H(u)\equiv Ku+F(u)-Q$. Because of $F(u)$, $H$ does not follows from a potential. This is the reason why, it is necessary for us to introduce a “pseudo-potential" (norm function) $G(u)=(1/2)H(u)^T H(u)$.

Using the above notations, Newton’s method is similarly to Gauss-Newton’s method and the equation $H(u)=0$ is equivalent with (2.1).

Proof â–¼

Proposition 3.4

If $H:\mathbb R^n\to \mathbb R^n$ is $B$-differentiable at an arbitrary point, $z_0$, and $G(u)=(1/2)H(u)^T H(u)$ and the above hypotheses hold then Theorem $\ref{theorem6.1.1}$ is equivalent with Theorem $\ref{theorem6.2.1}$.

The generalized Newton method for solving nonlinear and nondifferentiable systems which uses the notion of B-differentiability is equivalent with the generalized Newton method which uses the notion of generalized gradient.

Now, let us see under what conditions a discrete concrete problem of elastic contact in two dimensions, is included in the assumptions of Theorem 3.3, which ensures the uniqueness of solution with Newton-Raphson’s method (see [ 16 ] ).

Remarks 3.5

$1^\circ $. Theorem 3.3 can be easily applied in practice and is equivalent with Theorem 2.5.

$2^\circ $. The pseudopotential, $G(u)=\tfrac {1}{2}\, (Ku+F(u)-Q)^T(Ku+F(u)-Q)$, which appears in the algorithm (3.2), corresponds to the norm function

\[ G(z)=\tfrac {1}{2}\, F(z)^T\cdot F(z), \]

from Theorem 3.3.

$3^\circ $. The condition $\det M\neq 0$, with $M\in \partial F(x_0)$, from Theorem 3.3 is equivalent with the fact that the level set $\{ z\in \mathbb R^n|\| F(z)\| \leq \| F(z^0)\| \} $ is bounded.

Bibliography

1: Alar, P. and Curnier, A., A generalized Newton method for contact problems with friction, J. Theor. Appl. Mech., 7 (1) (1988), pp. 67–82.
2: Alar, P. and Curnier, A., A mixed formulation for frictional contact problems prone to Newton like solution methods, Comput. Meth. Appl. Mech. Engrg., 92 (93) (1991), pp. 353–375.
3: Altman, M., Concerning approximate solutions of nonlinear functional equations, Bull. Acad. Polon, Sci. Ser. Math., Astronom. Phys., 5, 1957.
4: Argyros, I.K. and George, S., Chebyshev-Kurchatov-type methods for solving equations with non-differentiable operators, Nonlinear Functional Analysis and Applications, 18, No. 3, (2013), pp. 421–432.
5: Barthle, R. G., Newton’s method in $B$-space, Proc. AMS. 6 (1955), pp. 27–31.
6: Clarke, F. H., Optimization and nonsmooth analysis, Wiley and Sons, 1983.
7: Kantorovici, L. V. and Akilov, G. P., Analiză funcţională, Ed. Ştiinţifică şi Enciclopedică, 1986.
8: Kantorovich, L. V., Metoda Newton dlea functionalnîh uravnenii, D. A. N., C.C.C.R., 1948.
9: Klarbring, A., Contact problems in linear elasticity, Linköping Studies in Science and Technology, Disertation No. 133, Linköping University, 1985.
10: Pang, J. S., Newton’s method for B-diferentiable equations, Mathematics of Operations Research, 15 (2) (1980).
11: Păvăloiu, I., Aitken-Steffensen-type methods for nonsmooth functions (I), Rev. Anal. Numér. Théor. Approx., 31 (2002), no. 1, pp. 111–116. $\includegraphics[scale=0.1]{ext-link.png}$
12: Păvăloiu, I., Aitken-Steffensen-type methods for nonsmooth functions (II), Rev. Anal. Numér. Théor. Approx., 31 (2002), no. 2, pp. 191–196. $\includegraphics[scale=0.1]{ext-link.png}$
13: Petrila, T. and Gheorghiu, C. I., Metode element finit şi aplicaţii, Editura Academiei, 1987.
14: Picard, E., Traité d’analyse, tom 2, 1883.
15: Pop, N., A generalized concept of a differentiability in Newton’s method for contact problems, Bul. St. Univ. Baia Mare, ser. B, Mat.-Inf., 16 (2000), pp. 307–314.
16: Pop, N., An algorithm for solving nonsmooth variational inequalities arising in frictional quasistatic contact problems, Carpathian J. Math., 24 (2008) no. 2, 110–119.
17: Qi, L. and Sun J., A nonsmooth version of Newton’s method, Mathematical Programming, 58 (1993), 353–367.
18: Robinson, S. M., Generalized equations and their solutions, Part.1, Basic Theory, Math. Programming Study, 10, 1979.
19: Robinson, S. M., Strongly regular generalized equations, Math. Oper. Res., 5, 1980.
20: Robinson, S. M., Local structure of fiable sets in nonlinear programming, Part.3, Stability and Sensitivity, Math. Programming Study, 1987.
21: Shapiro, A., On conceps of directional differentiability, Applied Mathematics and Astronomy, 1988.

This work is licensed under a Creative Commons Attribution 4.0 International License.