An Interior Point Algorithm for Mixed Complementarity Nonlinear Problems

Abstract

Nonlinear complementarity and mixed complementarity problems arise in mathematical models describing several applications in Engineering, Economics and different branches of physics. Previously, robust and efficient feasible directions interior point algorithm was presented for nonlinear complementarity problems. In this paper, it is extended to mixed nonlinear complementarity problems. At each iteration, the algorithm finds a feasible direction with respect to the region defined by the inequality conditions, which is also monotonic descent direction for the potential function. Then, an approximate line search along this direction is performed in order to define the next iteration. Global and asymptotic convergence for the algorithm is investigated. The proposed algorithm is tested on several benchmark problems. The results are in good agreement with the asymptotic analysis. Finally, the algorithm is applied to the elastic–plastic torsion problem encountered in the field of Solid Mechanics.

1 Introduction

Mixed nonlinear complementarity problems (MNCP) appear in many mathematical models. For example, elastic–plastic torsion problems [1, 2] can be modeled as free boundary problems and can be written as mixed complementarity problem [3]. Another example involves an in situ combustion described by a system of two nonlinear differential equations. It can be modeled as a complementarity problem [4] or mixed complementarity problem [5]. Other examples can be found in [6].

A number of papers aim at providing a numerical solution of MNCP. These include works using the interior point methods [7], non-monotone stabilization scheme [8], a class of active set Newton’s methods [9, 10], fictitious time integration methods [11], hybrid smoothing method [12], among others [13].

The present method deals with inequality constraints and complementarity conditions in a way inspired by an algorithm for constrained optimization presented in [14,15,16]. This approach, as in primal dual algorithms, solves optimality conditions with Newton-like iterations. However, the iterations are perturbed in such way to have feasible descent directions. In this paper, feasible directions algorithm (FDA) is employed to solve MNCP. This method consists of an interior point algorithm based on a modification of Newton’s method characterized by fast convergence, easy computational implementation and robustness. At each iteration, one feasible descent search direction is computed following the ideas of FDA-NCP [17]. The presented algorithm is appropriate for practical applications since it brings together the classical numerical techniques for PDEs combined with a robust and efficient interior point algorithm for MNCP, which has a complete theoretical foundation and shows good numerical results. The first steps in this direction were given by Mazorche [18].

This paper is organized as follows. Section 2 presents MNCP and FDA-MNCP. In Sect. 3, theoretical results are proved including the properties on global and asymptotic convergence. In Sect. 4, we apply FDA-MNCP to solve benchmark problems found in the literature showing the convergence and robustness of the present approach. In Sect. 5 the elastic–plastic torsion problem is formulated as MNCP and solved numerically using FDA-MNCP. Finally, Sect. 6 presents conclusions and discussions.

2 The Nonlinear Mixed Complementarity Algorithm

Three different variations of presenting MNCP can be found in the literature.

Definition 2.1

([6,7,8]) Find $x \in {\mathbb {R}}^n;\, w, v \in {\mathbb {R}}^n_{+}$ satisfying $f(x) = w - v;$ $w^\mathrm{T}(x-l) = 0;$ $v^\mathrm{T}(u-x) = 0;$ $l \le x \le u$, where $l, u \in \bar{{\mathbb {R}}}^n = ({\mathbb {R}} \cup \{-\infty ,\infty \})^n$ with $l_i \ne u_i$ for all i and $f:{\mathbb {R}}^n \rightarrow {\mathbb {R}}^n$ is a continuously differentiable mapping.

Definition 2.2

([3, 12, 13, 19]) Let $f:{\mathbb {R}}^n \rightarrow {\mathbb {R}}^n$, $f \in C^1$ and

$l_i, u_i \in {\mathbb {R}}\cup \{-\infty ,\infty \},$ with $\, l_i < u_i$ for all $i = 1, \ldots ,n$. Find a vector $x \in {\mathbb {R}}^n$ such that if $x_i = u_i \Rightarrow f_i(x) \le 0$, if $l_i< x_i < u_i \Rightarrow f_i(x)=0$ and if $x_i = l_i \Rightarrow f_i(x) \ge 0$.

Definition 2.3

([18]) Find $(x,y) \in {\mathbb {R}}^n\times {\mathbb {R}}^m$ such that $x \ge 0,$ $F(x,y) \ge 0,$ $Q(x,y)=0$ and $x\bullet F(x,y)=0,$ where $F:{\mathbb {R}}^{n}\times {\mathbb {R}}^m \rightarrow {\mathbb {R}}^{n}$ and $Q:{\mathbb {R}}^{n}\times {\mathbb {R}}^m \rightarrow {\mathbb {R}}^{m}$ are continuously differentiable, $H(x,y)=x \bullet F(x,y)$ represents the Hadamard product $H(x,y) = (x_1F_1(x,y), \ldots , x_nF_n(x,y) )^\mathrm{T}$.

Definitions 2.1 and 2.2 can be rewritten to match Definition 2.3 if one considers

$$\begin{aligned} \begin{array}{l} F(w,v,x) = \left( \begin{array}{l} x_1 - l_1, \ldots , x_n - l_n, u_1 - x_1,\ldots , u_n - x_n \end{array}\right) ^\mathrm{T},\\ Q(w,v,x) = f(x) + v - w, \quad (w\quad v)^\mathrm{T} \bullet F(w,v,x) = 0, \end{array} \end{aligned}$$

(1)

where $(w,v) \in {\mathbb {R}}^n_{+}\times {\mathbb {R}}^n_{+}$ are auxiliary variables and $x \in {\mathbb {R}}^n$.

Many mathematical programming problems can be formulated as an MNCP. In particular, one can formulate algebraic systems of nonlinear equations by setting $u_i = +\,\infty$ and $l_i = -\infty$ [13, 19], nonlinear programming can be treated by applying KKT conditions [9, 20], nonlinear complementarity problems by setting $u_i = +\infty$ and $l_i = 0$ [6], Variational Inequalities can be similarly formulated [6, 12].

Considerable research effort was devoted by mathematicians and engineers to solve MNCP, looking for strong and efficient techniques for real engineering applications. Our approach to solve MNCP in the form given by Definition 2.3 is based on the iterative solution of the nonlinear system of equations:

$$\begin{aligned} S(x,y) = (x \bullet F(x,y),Q(x,y))^\mathrm{T} = 0. \end{aligned}$$

(2)

Given an initial point inside the domain, FDA-MNCP generates a sequence of points such that the potential function

$$\begin{aligned} f(x,y) \equiv \phi (x,y) + \Vert Q(x,y)\Vert ^2, \end{aligned}$$

(3)

decreases at each iteration, where $\phi (x,y)=x^\mathrm{T}F(x,y)$.

The set of feasible points of MNCP, following Definition 2.3, is

$$\begin{aligned} \varOmega := \{ (x,y) \in {\mathbb {R}}^{n}\times {\mathbb {R}}^{m} \,:\, x \ge 0,\; F(x,y) \ge 0 \}. \end{aligned}$$

The interior of $\varOmega$ is denoted as ${\varOmega }^0$. For some fixed real number $c>0$, this work seeks the solution of MNCP in the following set

$$\begin{aligned} \varOmega _c := \left\{ (x,y) \in \varOmega ^{\circ } \; : \; f(x,y) \le c\right\} . \end{aligned}$$

(4)

Applying a Newton–Raphson iteration to (2) results in

$$\begin{aligned} \nabla S\left( x^k,y^k\right) \left( x^{k+1}-x^k \;\; y^{k+1}-y^k\right) ^\mathrm{T} = - S\left( x^k,y^k\right) . \end{aligned}$$

Notice that $(x^{k+1},y^{k+1})$ corresponds to a search direction $d_1^k= (x^{k+1}-x^k, y^{k+1}-y^k)^\mathrm{T}$, which is not necessarily feasible. This problem is circumvented by using the perturbed Newton’s iteration

$$\begin{aligned} \begin{array}{ccc} \nabla S(x^k,y^k)d^k = \begin{pmatrix} -x^k\bullet F(x^k,y^k) \\ -Q(x^k,y^k)\end{pmatrix} \end{array} + \rho ^k \left( \begin{array}{c} E_1 \\ E_0 \end{array}\right) , \end{aligned}$$

(5)

where

$$\begin{aligned} E_1= & {} [1,\ldots ,1]^\mathrm{T} \in {\mathbb {R}}^n,\, E_0 = [0,\ldots ,0]^\mathrm{T} \in {\mathbb {R}}^m; \nonumber \\ \rho _0= & {} \alpha \min \{1,{1}/(c^{\beta -1})\},\, \alpha \in \, ]0,1[,\,\, \,\, \beta \in ]1,2]; \nonumber \\ \rho _0\phi ^{\beta -1}(x^k,y^k)< & {} 1; \quad \rho ^k =\displaystyle \frac{\rho _0\phi ^{\beta }(x^k,y^k)}{n} \in ]0,1[; \end{aligned}$$

(6)

$$\begin{aligned} \nabla S(x^k,y^k)= & {} \left( \begin{array}{ccc} \nabla _x H(x^k,y^k) &{} \quad &{} \text {diag}(x^k)\nabla _{y}F(x^k,y^k) \\ \nabla _{x}Q(x^k,y^k) &{} \quad &{} \nabla _{y}Q(x^k,y^k) \end{array}\right) , \end{aligned}$$

(7)

for all $(x^k,y^k) \in \varOmega _c$, and $\text {diag}(x^k) \in {\mathbb {R}}^{n\times n}$ is a diagonal matrix such that ${(\text {diag}(x^k))_{ii}} \equiv (x^k)_{i}$. Sect. 3 shows that $d^k$ is a descent direction of the potential function f(x, y) and also is a feasible direction in $\varOmega$.

2.1 Description of the Algorithm

The present algorithm uses the following parameters $c>0$, $\alpha \in \,]0,1[$, $\eta \in \,]0,1[$, $\nu \in \,]0,1[$, $\beta \in \, ]1,2]$ and $\rho _0 < \alpha \min \{1,1/(c^{\beta -1})\}$.

• Initial Data: $(x^0,y^0) \in \varOmega ^{0}$, such that $f(x^0,y^0)< c$ and $k=0$.

• Step 1: Calculate the search direction $d^k$ by solving System (5).

• Step 2: Armijo’s linear search: consider $d^k=(d_x^k \,\,\, d_y^k)^\mathrm{T}$ and obtain $t^k$ as the first number of the sequence $\{1,\nu ,\nu ^2,\ldots \}$ satisfying

  $$\begin{aligned} x^{k}+t^kd_x^k\ge & {} 0, \qquad F\left( x^{k}+t^kd_x^k,y^k+t^kd_y^k\right) \ge 0, \end{aligned}$$

  (8)
  $$\begin{aligned} f\left( x^{k}+t^kd_x^k,y^k+t^kd_y^k\right)\le & {} f\left( x^{k},y^k\right) +t^k \eta \nabla f\left( x^k,y^k\right) ^t d^k. \end{aligned}$$

  (9)

• Step 3: Compute $(x^{k+1},y^{k+1})= (x^{k}+t^kd_x^k,y^k+t^kd_y^k)$. Go back to Step 1.

A new iteration is obtained by performing an inexact line search procedure that looks for a new feasible point with a sufficient reduction of the potential function f(x, y). We employ an extension of Armijo’s line search that deals with inequality constraints proposed in [15]. Line search procedures based on Wolfe’s or Goldstein’s inexact line search criteria can also be employed [21, 22].

This algorithm is a perturbation to Newton’s iterations. Below we prove that under standard assumptions the rate of convergence of the presented method is superlinear. Thus, a smaller $\rho ^k$ will result in faster convergence. That is why, when near a solution, the algorithm considers $\rho ^k = O(\phi ^{\beta }(x^k,y^k))$. The presented algorithm is easy to implement and requires computational resources similar to that of Newton’s method for a system of nonlinear equations.

One common difficulty concerning the interior point methods is checking if the chosen initial point is feasible. FDA-MNCP circumvents this difficulty by working inside the set $\varOmega _c$ given in (4), whose definition is simple to verify.

As far as we know, there are no other feasible direction methods addressing MNCP. However, in the literature there are methods addressing MNCP using variations of Newton’s method [3, 12, 23] and for Linear Complementarity Problems by interior point techniques [3].

There are important advantages in using feasible point techniques. From mathematical point of view, in some problems [18] the function F is not defined outside the feasible region, turning tricky application of other techniques. From the perspective of applications, the intermediate steps in the algorithm are in agreement with the physics of the problem. Moreover, the stop criteria are always approximated. When the iterates approximate the solution from the outside the feasible region, there is a possibility to stop at an unfeasible point. In this case, it may be possible to recover the feasibility at the price of increasing an error of the complementarity value.

3 Theoretical Results

This section provides theoretical background for the choice of the direction $d^k$ of System (5) as well as global and asymptotic convergence of FDA-MNCP. First steps in this direction were made by Mazorche [18].

3.1 The Search Direction

Proposition 3.1

(Feasible direction) Consider a point $(x^k,y^k) \in \varOmega _c$ and the direction $d^k$ obtained as a solution of System (5). Then, $d^k$ is a feasible direction in $\varOmega$ whenever $x^k \bullet F(x^k,y^k)\ne 0$.

Proof

Since $(x^k,y^k) \in \varOmega _c$ and $x^k \bullet F(x^k,y^k)\ne 0$, it follows that $\rho _0$ and $\rho ^k$ given in (6) are well defined. From (5), for each row $i = 1, 2,\ldots , n$, follows $[F_i(x^k,y^k)e_i + x_i \nabla F_i(x^k,y^k)]d^k = -x_i^k F_i(x^k,y^k) + \rho ^k$, where $e_i$ is the vector of the canonical base of ${\mathbb {R}}^n \times {\mathbb {R}}^m$. The two following cases are important: If $x_i^k = 0$ and $F_i(x^k,y^k) > 0$, then $d^k_i = \displaystyle {\rho ^k}/{F_i(x^k,y^k)} > 0$; If $x_i > 0$ and $F_i(x^k,y^k) = 0$, then $\nabla F_i(x^k,y^k) d^k = \displaystyle {\rho ^k}/{x_i} > 0$. It follows that $d^k$ is a feasible direction at $(x^k,y^k) \in \varOmega$ (see Proposition 2 [17] for details). $\square$

Proposition 3.2

(Descent direction) The search direction $d^k$ is a descent direction for $f(x^k,y^k)$ at any $(x^k,y^k) \in \varOmega _c$ whenever $x^k \bullet F(x^k,y^k)\ne 0$ is true and the conditions established in (6) are valid.

Proof

Since $x^k \bullet F(x^k,y^k)\ne 0$ and $(x^k,y^k) \in \varOmega _c$, then $c \ne 0$. From (3), it follows $\nabla f(x^k,y^k) = (E_1^\mathrm{T} \;\; 2Q(x^k,y^k))^\mathrm{T}\nabla S(x^k,y^k)$. Multiplying the last equation by $d^k$ and using (5) and (6) after some algebraic manipulations result in

$$\begin{aligned} \nabla f\left( x^k,y^k\right) \,d^k = -2 \left[ f\left( x^k,y^k\right) - \displaystyle \frac{1 + \rho _0 \phi ^{\beta -1}\left( x^k,y^k\right) }{2}\phi \left( x^k,y^k\right) \right] < 0. \end{aligned}$$

(10)

We conclude that $d^k$ is a feasible direction. $\square$

3.2 Global Convergence of FDA-MNCP

In order to prove global convergence, the following assumptions are necessary:

Assumption 3.1

The set $\varOmega _c$ given by (4) is a compact set, and it has an nonempty interior $\varOmega _c^0$. Each $(x,y) \in \varOmega _c^0$ satisfies $x > 0$ and $F(x,y)>0$.

Assumption 3.2

Functions F(x, y), Q(x, y) are of class $C^1({\mathbb {R}}^n \times {\mathbb {R}}^m)$, $\nabla F(x,y)$ and $\nabla Q(x,y)$ satisfy Lipschitz conditions $\Vert \nabla F(x_2,y_2) - \nabla F(x_1,y_1) \Vert \le \gamma \Vert (x_2,y_2) - (x_1,y_1) \Vert$ and $\Vert \nabla Q(x_2,y_2) - \nabla Q(x_1,y_1) \Vert \le L \Vert (x_2,y_2) - (x_1,y_1) \Vert ,$ for any $(x_1,y_1),(x_2,y_2) \in \varOmega _c$, where $\gamma$ and L are real positive numbers.

Assumption 3.3

The matrix $\nabla S(x,y)$ given in (7) is invertible in $\varOmega _c$.

Assumption 3.4

There is a real constant $\sigma > 0$, such that the subset $\varOmega ^* := \{(x,y)\in \varOmega _c: \;\; \sigma \Vert Q(x,y)\Vert \le \phi (x,y)\}$ is nonempty.

Assumptions 3.1–3.4 imply that x and F(x, y) are nonzero simultaneously for $(x,y) \in \varOmega _c$, which means that the linear system (5) always possesses a solution. Since $\nabla F(x^k,y^k)$ and $\nabla Q(x^k,y^k)$ are continuous, the matrix in Assumption 3.3 possesses a continuous inverse in $\varOmega _c$. Thus, there exists a scalar $\kappa >0$, such that $\Vert \nabla S(x^k,y^k)^{-1} \Vert \le \kappa$ for any $(x^k,y^k) \in \varOmega _c$.

The following results prove that the sequence of search direction $\{d^k\}$ of the present algorithm is bounded and constitutes a uniformly feasible directions field for $\beta \in (1,2]$ in $\varOmega _c$, i.e., there exists $\bar{\xi } > 0$ such that for any $(x^k,y^k) \in \varOmega _c$ it follows that $(x^k,y^k) + t d^k \in \varOmega _c$ for all $t \in [0,\bar{\xi }]$.

Lemma 3.1

Under Assumptions 3.3–3.4, for any $(x^k,y^k) \in \varOmega ^{*}$, there is a constant $\bar{\kappa }$ such that the search direction $d^k$ satisfies $\Vert d^k\Vert \le \bar{\kappa }\phi (x^k,y^k) \le \bar{\kappa } c$.

Proof

Let $E = \left( E_1 \;\; E_0 \right) ^\mathrm{T} \in {\mathbb {R}}^{n}\times {\mathbb {R}}^m$, where $E_1,\, E_0$ are given in (6). It follows that:

$$\begin{aligned} \Vert \rho ^k E -S(x^k,y^k) \Vert ^2\, = \,\Vert x^k \bullet F(x^k,y^k)\Vert ^2 -2\rho ^k\phi (x^k,y^k)+n(\rho ^k)^{2} + \Vert Q(x^k,y^k)\Vert ^{2}. \end{aligned}$$

(11)

Similarly to what was done by Herskovits and Mazorche in [17], it is possible to find a bound to the left side of Eq. (11). Define

$$\begin{aligned} T := \,\left\| x^k \bullet F\left( x^k,y^k\right) \right\| ^2 -2\rho ^k\phi \left( x^k,y^k\right) +n\left( \rho ^k\right) ^{2} \end{aligned}$$

and observe that from the definition of $\phi$ in (3) it follows that $\Vert x^k \bullet F(x^k,y^k)\Vert ^2 \le \phi ^2(x^k,y^k)$. Using it results in

$$\begin{aligned} T \le \left( \phi \left( x^k,y^k\right) - \rho ^k\right) ^2 + (n-1)\left( \rho ^k\right) ^2. \end{aligned}$$

Substituting $\rho ^k$ from (6), we obtain:

$$\begin{aligned} T \le \left[ \displaystyle \frac{\left( n - \rho _0 \phi ^{\beta - 1}\left( x^k,y^k\right) \right) ^2 + (n-1)\left( \rho _0 \phi ^{\beta - 1}\left( x^k,y^k\right) \right) ^2}{n^2}\right] \phi ^2\left( x^k,y^k\right) . \end{aligned}$$

(12)

The third condition in (6) results in $n - 1< n - \rho _0 \phi ^{\beta - 1}(x^k,y^k) < n$. Substituting it in (12) yields

$$\begin{aligned} T \le \left( n - \rho _0 \phi ^{\beta - 1}\left( x^k,y^k\right) \right) \phi ^2\left( x^k,y^k\right) /n < \phi ^2\left( x^k,y^k\right) . \end{aligned}$$

Using (11) and Assumption 3.4 yields

$$\begin{aligned} \left\| \rho ^k E-S\left( x^k,y^k\right) \right\| ^2 \le \phi ^2\left( x^k,y^k\right) + \left\| Q\left( x^k,y^k\right) \right\| \le \left( 1+1/\sigma ^2\right) \phi \left( x^k,y^k\right) ^2. \end{aligned}$$

Considering (5), we obtain

$$\begin{aligned} \left\| d^k\right\| \le \bar{\kappa }\left\| \rho ^k E-S\left( x^k,y^k\right) \right\| , \end{aligned}$$

where $\bar{\kappa } = \kappa \sqrt{1+1/\sigma ^2}$. As consequence $\left\| d^k\right\| \le \bar{\kappa } c$. $\square$

Lemma 3.2

Consider the sequence of search directions $\{d^k\}$ given by FDA-MNCP. Under Assumptions 3.2–3.3, there exists $\varTheta > 0$, such that for all $(x^k,y^k) \in \varOmega _c$ holds $(x^{k+1},y^{k+1}) = (x^k,y^k) + \tau d^k \in \varOmega$ for all $\tau \in [0,\varTheta ]$.

Proof

By Assumption 3.2, $\nabla S(x,y)$ is Lipschitz with some constant $\gamma$. Let $(x^k,y^k) \in \varOmega _c$, Proposition 3.1 implies that there exists $\theta >0$, such that $[(x^k,y^k),(x^k,y^k)+\tau d^k] \subset \varOmega$ for $\tau \in [0,\theta ]$. From the Mean Value Theorem, after some calculations it follows that for all $\tau \in [0,\theta ]$, $\tau \le \min \{1,{\rho ^k}/{\gamma \Vert d^k\Vert ^2}\}$:

$$\begin{aligned} S_i\left( \left( x^k,y^k\right) +\tau d^k\right) \ge 0 \quad \text{ for } \text{ all }\,\, i=1,2,\ldots ,n. \end{aligned}$$

(13)

Notice that $S_i((x^k,y^k)+\tau d^k)=x^{k+1} F_i(x^{k+1},y^{k+1})$ yielding $x^{k+1}\ge 0$ and $F_i(x^{k+1},y^{k+1})\ge 0$ (see Lemma 4.1.6 in [18] for details). It follows that $(x^k,y^k)+\tau d^k \in \varOmega$. Considering Lemma 3.1 and $\rho ^k$ defined in (6), Eq. (13) holds for $\tau \le \min \left\{ 1,{\rho _0}\phi (x^k,y^k)^{\beta -2}/{(\gamma n \bar{\kappa }^2)}\right\}$. Since $\beta \in \,]1,2]$, the present lemma is valid for $\varTheta = \min \left\{ 1,{\rho _0c^{\beta -2}}/{\gamma n \bar{\kappa }^2}\right\}$. $\square$

Lemma 3.3

Under Assumptions 3.3–3.4, there exists $\zeta > 0$ such that, for $(x^k,y^k)$ $\in \varOmega _c$, the Armijo’s line search given by (9) is satisfied for any $t^k \in [0,\zeta ]$.

Proof

Let $t^k \in \,]0,\varTheta ]$, where $\varTheta$ was obtained in the previous lemma. Applying the Mean Value Theorem for $i=1,2,\ldots ,n$ results in

$$\begin{aligned} S_i\left( x^{k+1},y^{k+1}\right) \le S_i\left( x^k,y^k\right) + t^k \nabla S_i\left( x^k,y^k\right) \,d^k+ \left( t^{k}\right) ^{2}\gamma \left\| d^k\right\| ^2. \end{aligned}$$

Adding the previous n inequalities and substituting the value of $\nabla S_i(x^k,y^k)\,d^k$ yield

$$\begin{aligned} \phi \left( x^{k+1},y^{k+1}\right) \le \left( 1-t^k\right) \phi \left( x^k,y^k\right) +t^k n\rho ^k + n t^{k^{2}}\gamma \left\| d^k\right\| ^2. \end{aligned}$$

(14)

Similarly, applying the Mean Value Theorem for $Q_i^2$ yields

$$\begin{aligned} \left\| Q\left( x^{k+1},y^{k+1}\right) \right\| ^2 \le \left( 1-t^k\right) \left\| Q\left( x^k,y^k\right) \right\| ^2+ m \left( t^{k}\right) ^{2}\gamma \left\| d^k\right\| ^2. \end{aligned}$$

(15)

Adding (14) and (15), the limitation for f is obtained

$$\begin{aligned} f\left( x^{k+1},y^{k+1}\right) \le \left( 1-t^k\right) f\left( x^k,y^k\right) +t^k \left[ \, n\rho ^k + (n+m) t^k\gamma \left\| d^k\right\| ^2 \,\right] . \end{aligned}$$

Definition of $\rho ^k$ in (6) and Assumption 3.1 imply $1/f(x^k,y^k) \le 1/\phi (x^k,y^k)$, yielding

$$\begin{aligned} f\left( x^{k+1},y^{k+1}\right) \le \left[ 1-\left( 1-\rho _0\phi ^{\beta -1}\left( x^k,y^k\right) - \displaystyle \frac{(n+m) \gamma \left\| d^k\right\| ^2t^k}{\phi \left( x^k,y^k\right) }\right) t^k\right] f\left( x^k,y^k\right) . \end{aligned}$$

In order for Armijo’s line search (9) to be satisfied, it is sufficient that

$$\begin{aligned} \left( 1-\rho _0\phi ^{\beta -1}\left( x^k,y^k\right) \right) -(n+m)\gamma \left\| d^k\right\| ^2t^k/\phi \left( x^k,y^k\right) \ge \eta \left( 1-\rho _0\phi ^{\beta -1}\left( x^k,y^k\right) \right) . \end{aligned}$$

As in the previous lemma, it follows

$$\begin{aligned} t^k \le \left( 1-\eta \right) \left( 1-\rho _0\phi ^{\beta -1}\left( x^k,y^k\right) \right) \phi \left( x^k,y^k\right) / \left( (n+m)\gamma \left\| d^k\right\| ^2\right) . \end{aligned}$$

Considering $\varTheta$ from Lemma 3.2, from Lemma 3.1 the result follows for $\displaystyle \zeta = \min \left\{ \frac{(1-\eta )(1-\rho _0c^{\beta -1})}{ (n+m)\gamma \bar{\kappa }^2 c^3}, \varTheta \right\} .$ $\square$

Lemma 3.4

Under Assumptions 3.3 and 3.4, there exists $\bar{\xi }>0$ such that, for $(x^k,y^k) \in \varOmega ^*$, the point $(x^{k+1},y^{k+1})=(x^k,y^k)+t^kd^k$ belongs to set $\varOmega ^*$ for any $t^k \in [0,\bar{\xi }]$.

Proof

By Lemmas 3.2 and 3.3, there exists $\zeta > 0$, such that $(x^{k+1},y^{k+1}) = (x^k,y^k) + t^k d^k \in \varOmega _c$ for all $(x^k,y^k) \in \varOmega ^{*}$, $d^k$ is generated by FDA-MNCP and $t^k \in [0,\zeta ]$. We are going to prove that $(x^{k+1},y^{k+1}) \in \varOmega ^{*}$. Similarly to Lemma 3.3, applying the Mean Value Theorem to $S_i$ ($i=1,2,\ldots ,n$) results in

$$\begin{aligned} \phi \left( x^{k+1},y^{k+1}\right) \ge \left( 1-t^k\right) \phi \left( x^k,y^k\right) +n t^k \rho ^k - n \left( t^{k}\right) ^{2} \gamma \left\| d^k\right\| ^2. \end{aligned}$$

(16)

Using the Second Fundamental Theorem of Calculus for each $Q_i\, (i=1,\ldots , m)$:

$$\begin{aligned} Q\left( x^{k+1},y^{k+1}\right) = Q\left( x^k,y^k\right) + t^k \left[ \displaystyle \int _{0}^{1}\nabla Q\left( \left( x^k,y^k\right) + \theta t^k d^k\right) \,d\theta \right] d^k. \end{aligned}$$

(17)

Substituting $\nabla Q(x^k,y^k)d^k = -Q(x^k,y^k)$ from (5) into (17), calculating $l_2$ norm, multiplying by $-\sigma$ and adding it to (16) yield

$$\begin{aligned}&\phi \left( x^{k+1},y^{k+1}\right) - \sigma \left\| Q\left( x^{k+1},y^{k+1}\right) \right\| \\&\quad \ge \left( 1 - t^k\right) \left[ \phi \left( x^{k},y^{k}\right) - \sigma \,\left\| Q\left( x^{k},y^{k}\right) \right\| \right] + t^k \left[ n \rho ^k - (n\gamma + \sigma L)\left\| d^k\right\| ^2 t^k\right] . \end{aligned}$$

In order to guarantee that the right side is positive, it is sufficient that $n \rho ^k - (n\gamma + \sigma L)\Vert d^k\Vert ^2 t^k > 0$. Using the definition of $\rho ^k$, we obtain that $t^k \le \delta \left( {\rho ^k}/{(\gamma \, \Vert d^k\Vert ^2)}\right)$, where $\delta = {n \gamma }/{(n \gamma + \sigma L)} \in \,]0,1]$. It follows that $(x^{k+1},y^{k+1}) \in \varOmega ^{*}$, for all $t^k \in \,]0,\bar{\xi })$ and $\bar{\xi } = \min \left\{ {\delta \rho _0 c^{\beta - 2}}/{(\gamma \, \bar{\kappa }^2 n)},\zeta \right\}$. $\square$

As a consequence of the three previous lemmas, the sequence $\{d^k\}$ generated by FDA-MNCP is a uniformly feasible directions field in $\varOmega _c$. Moreover, the number of steps required by Armijo’s line search described in Step 2 of the algorithm is finite and bounded from above. The following theorem addresses the global convergence of the presented algorithm.

Theorem 3.1

Under Assumptions 3.1–3.4, given the initial point $(x^0,y^0) \in \varOmega ^*$, there exists a subsequence of $\{(x^k,y^k)\}$ generated by FDA-MNCP converging to $(x^*,y^*)$, a solution of MNCP given by Definition 2.3.

Proof

From Lemmas 3.1–3.3, it follows that $(x^k,y^k) \in \varOmega _c$. This, jointly with Assumption 3.1, implies that there exists a subsequence $\{(x^{k_n},y^{k_n})\} \in \varOmega _c$ converging to $(x^*,y^*)\in \varOmega _c$. Using that f is a continuous function, Proposition 3.2 implies that $f(x^k,y^k)$ is a decreasing sequence converging to its infimum $f(x^*,y^*)$. If $f(x^{*},y^{*}) \ne 0$, from the definition of f results that $\phi (x^{*},y^{*}) \ne 0$ and the set of indexes $J := \{j \in [1,n]\, : \,x_jF_j(x^{*},y^{*}) \ne 0 \}$ is nonempty. On the other hand, $\Vert d^k\Vert \downarrow 0$ as $t^k$ is bounded from below. From System (5), it follows that

$$\begin{aligned} d^k = \nabla ^{-1}S\left( x^k,y^k\right) \left[ -S\left( x^k,y^k\right) + \rho ^k E\right] . \end{aligned}$$

Thus, $-x_i^{*}F_i(x^{*},y^{*}) + \rho ^0 \phi ^{\beta }(x^{*},y^{*})/n = 0$, for each row $i = 1,\ldots ,n$. Adding these equations, it follows that $\rho ^0\phi ^{\beta -1}(x^{*},y^{*}) = 1$, contradicting the third condition in (6). Thus, $(x^{*},y^{*})$ is the solution of MNCP. $\square$

3.3 Asymptotic Convergence

The present algorithm is a perturbation of Newton’s iteration, and it is natural to expect a rate of convergence close to quadratic for smaller values of $\rho ^k$. Unfortunately, a unitary step-length can not be always ensured. The present approach possesses asymptotic convergence as formulated next.

Theorem 3.2

Consider the sequence $\{(x^k,y^k)\}$ generated by FDA-MNCP that converges to a solution $(x^*,y^*)$ of MNCP given by Definition 2.3. Then, (i) taking $\beta \in \,]1,2[$ and $t^k = 1$ for k large enough, the rate of convergence of the present algorithm is at least superlinear; (ii) if $t^k = 1$ for large k and $\beta = 2$, then the rate of convergence is quadratic.

Proof

Considering $\varTheta$ from Lemma 3.2, $\bar{\xi }$ from Lemma 3.4 and $t^k \in \,]0,min \{\varTheta ,\bar{\xi }\}]$, it follows that

$$\begin{aligned}&\left\| \left( x^{k + 1},y^{k+1}\right) - \left( x^*,y^*\right) \right\| \nonumber \\&\quad \le \left( 1-t^k\right) \left\| \left( x^{k},y^k\right) - \left( x^*,y^*\right) \right\| \nonumber \\&\qquad +\,{\kappa \rho _0 \phi ^{\beta }\left( x^{k},y^k\right) }/{\sqrt{n}} + O\left( \left\| \left( x^{k},y^k\right) - \left( x^*,y^*\right) \right\| ^2\right) . \end{aligned}$$

(18)

From the Mean Value Theorem and the Lipschitz condition, it follows that

$$\begin{aligned} \phi ^{\beta }\left( x_1,y_1\right) \le \phi ^{\beta }\left( x_2,y_2\right) + \beta \phi ^{\beta -1}\left( \bar{x},\bar{y}\right) \sqrt{n}\,O\left( \left\| \left( x_1,y_1\right) -\left( x_2,y_2\right) \right\| \right) , \end{aligned}$$

where $(\bar{x},\bar{y})=(x_2,y_2)+\epsilon ((x_1,y_1)-(x_2,y_2))$ for some $\epsilon \in \,]0,1[$. Taking $(x_2,y_2)=(x^*,y^*)$, for all $(x_1,y_1)=(x^k,y^k)$ sufficiently near $(x^*,y^*)$ it is equivalent to

$$\begin{aligned} \phi ^{\beta }\left( x^k,y^k\right) \le \phi ^{\beta -1}\left( \bar{x},\bar{y}\right) \beta \sqrt{n}\,O\left( \left\| \left( x^k,y^k\right) -\left( x^*,y^*\right) \right\| \right) . \end{aligned}$$

(19)

• (i) Hypothesis $\beta \in \,]1,2[$ and $t^k=1$ for large k in (19) imply

  $$\begin{aligned} \phi ^{\beta }\left( x^k,y^k\right) = O\left( \left\| \left( x^k,y^k\right) -\left( x^*,y^*\right) \right\| \right) . \end{aligned}$$

  By substitution in (18), we obtain that $\lim _{k\rightarrow \infty }\frac{\Vert (x^{k + 1},y^{k+1}) - (x^*,y^*)\Vert }{\Vert (x^{k},y^{k}) - (x^*,y^*)\Vert }=0.$ Thus, the rate of convergence is superlinear.

• (ii) The result for $\beta =2$ is obtained in a similar way. $\square$

4 Benchmark Problems

To test the numerical behavior of the present algorithm, a number of problems presented in the literature are solved. The numerical implementation considers $\rho _0 = \alpha \min \{1, \phi ^{\beta -1}(x^k,y^k) \}$ in order to avoid extremely large deflections far from the solution and $\rho _0$ is constant when $\phi (x^k,y^k)$ is small. All the simulations were performed for two cases: $\beta =1.1$ and $\beta =2$. All problems were solved with the same parameters: $\alpha = 0.25$, $\eta = 0.4$, $\nu =0.8$ and the stop criteria $f(x^k,y^k)< 10^{-8}$. For each test problem, ten different starting points were considered. The complementarity condition used is $(w,\;v)^\mathrm{T} \bullet F(w,v,x) = 0$, where w, v have different dimensions for each test problem. The results are summarized in Table 1 for the values $\beta =1.1$ and $\beta =2$, where Min and Max represent the minimum and maximum numbers of iterations. As shown in Table 1 for different initial points, the number of iterations does not change significantly for both analyzed values of parameter $\beta$. The exception is $\beta =1.1$ for the problem 4.10, which presented bad convergence due to strong nonlinearity presented in this example. The present algorithm converged in all tested benchmark problems showing the robustness of FDA-MNCP.

Table 1 Number of iterations for the benchmark problems to converge

Problem 4.1

(Example 3.5 [9]) This problem is proposed as NCP and solved as MNCP using (1) with $l_i = 0, u_i = M = 10^5, \, i = 1, 2$. This problem consists in searching for $(w,v) \in {\mathbb {R}}^2_{+}\times {\mathbb {R}}^2{+}$ and $x \in {\mathbb {R}}^2$ such that $F(w,v,x) = (x_1,x_2,M - x_1,M-x_2)^\mathrm{T}$, $Q(w,v,x) = ((x_1 - 1)^2,x_1 + x_2 - 1)^\mathrm{T} + v - w$. The exact solution of this problem is (1, 0).

Problem 4.2

(Example 6.1 [9]) This problem is proposed as NCP. In order to solve this problem as MNCP, we use (1) with $l_i = 0$, $u_i = M = 10^5$, $i = 1, 2$. This problem consists in searching for $(w,v) \in {\mathbb {R}}^2_{+}\times {\mathbb {R}}^2_{+}$ and $x \in {\mathbb {R}}^2$, such that $F(w,v,x) = (x_1,x_2,M - x_1,M-x_2)^\mathrm{T}$, $Q(w,v,x) = ( (x_1 - 1)^2,x_1 + x_2 + x_2^2 - 1)^\mathrm{T} + v - w = 0$. The exact solution for this problem is (1, 0).

Problem 4.3

(Example 6.2 [9]) This is a minimization problem. Applying KKT conditions [20], this problem can be written as MNCP in the form of Definition 2.3. This problem consists in searching for $w \in {\mathbb {R}}^2_{+},\, x \in {\mathbb {R}}^2$, such that $F(w,x) = \left( x_1,x_2\right) ^\mathrm{T}$, $Q(w,z) = \left( 2 x_1 + 2 x_2 - w_1, 2 x_1 + 2 x_2 - w_2 \right) ^\mathrm{T}$, where $w = (w_1, w_2)$ are KKT multipliers, $x = (x_1,x_2)$ are the primal variables.

Problem 4.4

(Example 6.3 [9]) This is a minimization problem. It can be written as MNCP in the form of Definition 2.3 using KKT conditions from [20]. This problem consists in searching for $w \in {\mathbb {R}}_{+},\, x \in {\mathbb {R}}$, such that $F(w,x) = x$, $Q(w,x) = x^3 - w$. The exact solution for this problem is $x = 0$.

Problem 4.5

(Example 6.5 [9]) This is a minimization problem. Applying KKT conditions given in [20], this problem can be written as MNCP in the form of Definition 2.3. This problem consists in searching for $w \in {\mathbb {R}}^2_{+},\, x \in {\mathbb {R}}^2$ such that $F(w,x) = \left( x_1 - {x_2^2}/{2}, x_1 + {x_2^2}/{2} \right) ^\mathrm{T}$, $Q(w,x) = ( x_1 - w_1 - w_2, x_2^2 + w_1 x_2 - w_2 x_2 )^\mathrm{T}$. This problem has the exact solution $x = (0,0)^\mathrm{T}$ .

Problem 4.6

(Example 3.4 [10]) This is a minimization problem. Applying KKT conditions given in [20], this problem can be written as MNCP in the form of Definition 2.3. This problem consists in searching for $w \in {\mathbb {R}}^3_{+},\, x \in {\mathbb {R}}^2$, such that $F(w,x) = ( x_1, x_2, x_1 + x_2 )^\mathrm{T}$, $Q(w,x) = ( 1 + x_1 - w_1 - w_3, x_2 -w_2 - w_3 )$. The exact solution for this problem is $x = (0,0)^\mathrm{T}$.

Problem 4.7

(Powell’s badly scaled problem [24])

This problem consists of a system of nonlinear equations that can be written as MNCP [13, 19]. It can also be written as MNCP given by Definition 2.3 by using $l_i = - u_i = - M = -10^5$, $i = 1, 2$. It is symmetric under the transformation $x_1 \leftrightarrow x_2$, and it possesses two solutions $x^{*} = (9.106,1.098\times 10^{-5})^\mathrm{T}$; $\hat{x} = (1.098\times 10^{-5},9.106)^\mathrm{T}$. This problem consists in searching for $(w,v) \in {\mathbb {R}}^2_{+}\times {\mathbb {R}}^2_{+} \in {\mathbb {R}}^2$, such that $F(w,v,x) = ( x_1 + M, x_2 + M, M - x_1, M - x_2 )^\mathrm{T}$, $Q(w,v,x) = ( 10^4\, x_1 x_2 - 1, e^{-x_1} + e^{-x_2} - 1.0001 )^\mathrm{T} + v - w.$

Problem 4.8

(Powell’s singular function [24]) This problem consists of a system of nonlinear equations, and it possesses a singular Jacobian on the hyperplane $x_1 - x_4=0$, and thus, the Newton’s method is not applicable. The only solution of this problem is $x = (0,0,0,0)^\mathrm{T}$ [24]. It can also be written as MNCP given by Definition 2.3 by using $l_i = - u_i = - M = -10^5, \, i = 1, 2, 3, 4$. This problem consists in searching for $(w,v) \in {\mathbb {R}}^4_{+}\times {\mathbb {R}}^4_{+},\, x \in {\mathbb {R}}^4$, such that $F(w,v,x) = (x_1 + M,x_2 + M,x_3 + M,x_4 + M,M-x_1,M-x_2,M-x_3,M-x_4)^\mathrm{T}$, $Q(w,v,x) = ( x_1 + 10x_2, \sqrt{5}(x_3 - x_4), (x_2 - 2 x_3)^2, \sqrt{10}(x_1 - x_4)^2)^\mathrm{T} + v - w$.

Problem 4.9

(Walsarian equilibrium model [7]) The Walsarian equilibrium model, presented in as MNCP in the form Definition 2.1 [7], was rewritten as a minimization problem and solved applying the infeasible interior point algorithm. Depending on the values of the constants $b_2, b_3 > 0$ and $\alpha \in (0,1)$, this problem possesses different solutions. For numerical results is used $(\alpha , b_2, b_3) = (0.75,1,0.5)$ (4.9b in Table 1) and (0.75, 1, 2) (4.9a in Table 1) as in [7]. Considering $l_i = 0, u_i = M = 10^5, \, i = 1, 2, 3, 4$; this problem can be written as Definition 2.3. This problem consists in searching for $(w,v) \in {\mathbb {R}}^4_{+}\times {\mathbb {R}}^4_{+}$, $\bar{x}=(z,x_1,x_2,x_3)^\mathrm{T} \in {\mathbb {R}}^4$, such that

$$\begin{aligned} F(w,v,\bar{x})= & {} \left( z, \bar{x}_1, \bar{x}_2, \bar{x}_3, M - z, M - \bar{x}_1, M - \bar{x}_2, M - \bar{x}_3\right) ^\mathrm{T}, \\ Q(w,v,\bar{x})= & {} ( -x_1 + x_2 + x_3, z - \alpha {(b_2 x_2 + b_3 x_3)}/{x_1},\\&b_2 - z - (1 - \alpha ){(b_2 x_2 + b_3 x_3)}/{x_2}, b_3 - z)^\mathrm{T} + v - w. \end{aligned}$$

Problem 4.10

(Kojima–Shindo’s Problem [7, 25, 26]) This problem was proposed as NCP and solved by using Algorithms EN and EQN [26], by using quasi Newton’s methods [25] and by using NLCP algorithm [7]. The exact solutions are $\bar{x} = (\sqrt{6}/2,0,0,0.5)$ and $\bar{x} = (1,0,3,0)$. It is possible to write it in the form of Definition 2.3 using $l_i = 0, u_i = M = 10^5, \, i = 1, 2, 3, 4$. This problem consists in searching for $(w,v) \in {\mathbb {R}}^4_{+}\times {\mathbb {R}}^4_{+}$, $x \in {\mathbb {R}}^4$, such that

$$\begin{aligned} F(w,v,x)= & {} ( x_1, x_2, x_3, x_4, M - x_1, M - x_2, M - x_3, M - x_4)^\mathrm{T}, \\ Q(w,v,x)= & {} \left( 3x_1^2 + 2x_1x_2 + 2x_2^2 + x_3 + 3x_4 - 6, \right. \\&2x_1^2 + x_1 + x_2^2 + 10x_3 + 2x_4 - 2, \\&3x_1^2 + x_1x_2 + 2x_2^2 + 2x_3 + 9x_4 - 9, \\&\left. x_1^2 + 3x_2^2 + 2x_3 + 3x_4 - 3\right) ^\mathrm{T} + v - w. \end{aligned}$$

5 Elastic–Plastic Torsion Problem

The application of mathematical programming theory and methods, including complementarity, to analyze elastic–plastic structures dates back to the late 1960s and early 1970s. Torsion of a long, hollow bar made of an elastic–plastic material is a mathematically well-defined problem [27], and thus it can be used to test the proposed algorithm. Except for the circular cross section case, there are no analytical solutions available [27]. That is why in the present paper, the circular cross section corresponding to $w = 0$ is considered [28]. Following [2, 28], we consider a prismatic bar whose longitudinal axis is the Z-axis and whose cross sections $\varSigma \subset {\mathbb {R}}^2$ lie in the XY-plane and is a simply connected, bounded open domain, see Fig. 1. This elastic–plastic torsion problem is described by the system of equations in terms of a stress function $\phi$ [2],

$$\begin{aligned} \phi = 0\; \text {on} \; \partial \varSigma ; \; -\nabla \phi =\theta \; \text {in} \; \varSigma _e := \{x\in \varSigma :\, |\nabla \phi | < 1 \}; \; | \nabla \phi | = 1 \; \text {in} \; \varSigma _p, \end{aligned}$$

(20)

where $\varSigma _e$ is the elastic region, $\varSigma _p := \varSigma - \varSigma _e$ is the plastic region and $\theta$ is the twist angle per unit length. In order to write this problem using a weak formulation, the following Sobolev space is considered $H^1_0(\varSigma ) := \{v \in H^1(\varSigma ): v = 0 \,\, \text {on}\,\, \partial \varSigma \}$, which is a closed vector subspace of $H^1(\varSigma )$. We seek the solution in the closed and convex subset $\hat{K}$ of $H^1_0(\varSigma )$ given by $\hat{K} := \{v \in H^1_0(\varSigma ): |v(x)| \, \le \, 1 \}$. The System (20) can be rewritten as a variational inequality [2],

$$\begin{aligned} \displaystyle \int \int _{\varSigma } \nabla u\, .\, \nabla (v - u) \ge \displaystyle \int \int _{\varSigma }(v - u)\quad \forall \, v \in \hat{K}, u \in \hat{K}, \end{aligned}$$

(21)

which possesses a unique solution [29].

Fig. 1

Torsion of a prismatic bar with a circular cross section

The elastic–plastic torsion problem in the variational formulation (21) is especially appropriate for a numerical solution by using the Finite Element Method (FEM) by writing it as a mixed complementarity problem, which is solved by using FDA-MNCP. The equivalence between the elastic–plastic torsion problem given by variational inequality (21) and same inequality substituting the set $\hat{K}$ by $K := \{v \in H^1_0(\varSigma ): |v(x_1,x_2)| \, \le \, d(x_1,x_2) \}$ was proven in [30] using $d(x_1,x_2) = \text {distance}((x_1,x_2),\partial \varSigma )$, $\forall (x_1,x_2) \in \bar{\varSigma }$.

Table 2 Number of iterations solving the elastic–plastic torsion problem presented in [3]

FEM formulation used here follows [3] with a standard triangulation $T_h$ on $\bar{\varSigma } = \varSigma \cup \partial \varSigma$. The space $H^1(\varSigma )$ is substituted by a finite dimensional discrete space $V_h$ of piecewise polynomials $v_h$ of degree one. Inequality (21) is written in a discrete form, i.e., search $u_h \in K_h$ such that

$$\begin{aligned} \displaystyle \int \int _{\varSigma } \bigtriangledown u_h\, .\, \bigtriangledown (v_h - u_h) \ge \displaystyle \int \int _{\varSigma }(v_h - u_h)\quad \forall \, v_h \in K_h. \end{aligned}$$

(22)

Let $\{\varphi _1,\ldots ,\varphi _n\}$ a base of $V_h$, where n is the number of nodes, then

$$\begin{aligned} v_h(x_1,x_2) = \sum _{j=1}^{n}v_j \varphi _j(x_1,x_2), \, z_h(x_1,x_2) = \sum _{j=1}^{n}z_j \varphi _j(x_1,x_2), \end{aligned}$$

for each $(x_1,x_2) \in \varSigma \cup \partial \varSigma$. Replacing these expressions into (22) yields

$$\begin{aligned} (v - z)^\mathrm{T}(q + Mz) \, \ge \, 0\quad \text {for all} \,\, v \in K_h, \end{aligned}$$

(23)

where $K_h$, the matrix $M = (m_{ij}) \in {\mathbb {R}}^{n \times n}$ and the vector $q = (q_i) \in {\mathbb {R}}^{n}$ are given by $K_h := \{v \in {\mathbb {R}}^{n}\, : \, a_i \le v_i \le b_i,\, i = 1,\ldots ,n; v_i = g_i\,\, \text {in}\,\, \partial \varSigma \cup T_h \}$,

$$\begin{aligned} m_{ij} = \displaystyle \iint _{\varSigma } \left[ \displaystyle \frac{\partial \varphi _i}{\partial x_1}\displaystyle \frac{\partial \varphi _j}{\partial x_1} + \displaystyle \frac{\partial \varphi _i}{\partial x_2}\displaystyle \frac{\partial \varphi _j}{\partial x_2}\right] \mathrm{d}x_1 \mathrm{d}x_2, \;\; q_i = - \displaystyle \iint _{\varSigma }\theta \varphi (x_1,x_2) \mathrm{d}x_1 \mathrm{d}x_2. \end{aligned}$$

Table 3 Number of iterations solving the elastic–plastic torsion problem by FDA-MNCP

Fig. 2

Exact (a, c and e) and numerical (b, d and f) solutions obtained for different mesh sizes n. The numerical simulations using FDA-MNCP for $\theta = 5$ and $R = 1$. a $n=11$, b $n=11$, c $n=776$, d $n=776$, e $n=5358$, f $n=5358$

In [3] was established that (23) can be written as MNCP in the form of Definition 2.2 setting J as the set of interior nodes and N as the number of elements of J. The problem consists in searching $U,V \in {\mathbb {R}}^N_+$ and $z \in {\mathbb {R}}^N$ such that

$$\begin{aligned} F(w,v,z) \ge 0, \end{aligned}$$

where $F_i(w,v,z) = z_i - a_i$, $F_{i + N}(w,v,z) = b_i - z_i$ for all $i \in J$. Here, $Q(w,v,z) = q + Mz + v - w = 0$ and the complementarity condition is given by $(w \;\; v)^\mathrm{T} \bullet F(w,v,z) = 0$, which is solved applying FDA-MNCP with FEM. The results are presented in Table 3. They are similar to the results presented in [3] summarized in Table 2, where the same problem is solved in the form of Definition 2.2. Notice that the number of mesh nodes is different.

The exact solution of the elastic–plastic torsion problem of the cylindrical bar with cross section $\varSigma \subset {\mathbb {R}}^2$ is known [2]:

$$\begin{aligned} \begin{array}{ll} \text {If} \,\, \theta \le 2R &{} \quad \phi (x) = {\theta }(R^2 - r^2)/4, \\ \text {if}\,\, \theta \ge 2R &{} \quad \phi (x) = \left\{ \begin{array}{lcl} R - r, &{} \quad \text {if} &{} R^{\prime } \le r \le R, \\ -{\theta \, r^2}/{4} + (R - {1}/{\theta }), &{} \quad \text {if} &{} 0 \le r \le R^{\prime }, \end{array}\right. \end{array} \end{aligned}$$

(24)

where $\varSigma = \{(x_1,x_2) \in {\mathbb {R}}^2\,/\, x_1^2 + x_2^2 \le R^2\}$, $r = \sqrt{x_1^2 + x_2^2}$ and $R^{\prime } = 2/\theta$. Table 3 shows the $l_2$ error of FDA-MNCP when compared to the exact solution (24). It can be observed that it is decreasing according to theoretical predictions until the numerical precision is reached in the last four columns. Notice that in the last three columns the total number of iterations stabilizes for both values of the parameter $\beta$.

In Fig. 2, we show the comparison between the exact solution (24) and the numerical solution obtained by using FDA-MNCP with FEM. In agreement with the results presented in Table 3, the graphics are indistinguishable for big mesh numbers.

6 Conclusions

The feasible points algorithm for mixed nonlinear complementarity problems was presented. It generalizes the ideas of FDA-NCP [4, 17]. Global and asymptotic convergence was rigorously proven. For the parameter $\beta \in \,]1,2[$, the superlinear convergence was proved. On the other hand, if $\beta =2$, quadratic convergence was obtained. The presented algorithm is easy to implement numerically and is efficient as can be observed from the number of iterations required to solve the benchmark problems. Moreover, it is robust in the sense that it does not need parameters tuning. In our case, all the examples were solved using the same parameters $\mu$, $\nu$ and $\beta$ showing good results. The choice of the starting point should not be a problem for the algorithm as we proved the global convergence, i.e., for all starting points in the interior of the domain. This theoretical results were endorsed by numerical simulations with, at least, ten different initial values for each benchmark problem. The Maratos effect was rarely observed in the test problems.

The algorithm was applied to the elastic–plastic torsion problem with a circular cross section. The obtained results agree with the analytical solution and ones found in the literature. These results can also be extended to other problems, such as Mathematical Program with Equilibrium Constraints (MPEC).