Solution of Monotone Complementarity Problems with Locally Lipschitzian Functions

Andreas Fischer

Institute for Numerical Mathematics Technical University of Dresden D–01062 Dresden Germany e-mail: fischer@math.tu-dresden.de

May, 1995 (revised December, 1995)

Abstract: The paper deals with complementarity problems CP(F), where the underlying function F is assumed to be locally Lipschitzian. Based on a special equivalent reformulation of the problem CP(F) as a system of equations Φ(x) = 0 or as the problem of minimizing the Euclidean norm of Φ we extend different results which are known for sufficiently smooth functions F to the nonsmooth case.

In particular, if F is monotone in a neighbourhood of x it is proved that 0 ∈ ∂Ψ(x) is necessary and sufficient for x to be a solution of CP(F). Moreover, a simple derivative–free algorithm that reduces Ψ is shown to possess global convergence properties for monotone functions F. Finally, the local behaviour of a generalized Newton method is analyzed. To this end, the result by Mifflin that the composition of semismooth functions is again semismooth is extended to the case when p–order semismooth functions are considered. Under a suitable regularity condition and if F is p–order semismooth the generalized Newton method is shown to be locally well–defined and superlinearly convergent with the order of 1 + p.

Keywords: Complementarity problem, locally Lipschitzian function, monotone function, semismooth function, descent method, generalized Newton method

1 Introduction

In this paper we are interested in the solution of the complementarity problem CP(F)

F (x) ≥ 0, x ≥ 0, x^{T} F (x) = 0,

where F : R^{n} → R^{n} is a given function whose properties will be specified later. Different concepts have been developed to treat this problem. In the last few years growing attention has been paid to approaches which employ a reformulation of CP(F) as a nonlinear equation or a minimization problem, for instance, see [3, 7, 9, 13, 15, 16, 18, 19, 24, 26, 27, 34, 36, 38, 39, 51, 54, 56]. Theoretical results have been established that give conditions under which a stationary point of the minimzation problem is a solution of the complementarity problem CP(F). Moreover, algorithms with global and local superlinear convergence properties have been developed. However, the papers we referred to are based on a sufficiently smooth (at least differentiable) function F. In contrast to this, we are interested in obtaining corresponding results for locally Lipschitzian functions F.

Since the work by Mangasarian [33] it has been well–known that the system

a ≥ 0, b ≥ 0, ab = 0  (1)

can be transformed into an equivalent nonlinear equation

ϕ(a, b) = 0.  (2)

see, e.g., [12, 19, 26, 28, 33, 34, 38, 41, 55]. Frequently, the occuring function ϕ is not everywhere differentiable. Therefore, different approaches to overcome this kind of nonsmoothness (see [1, 8, 10, 38, 39]) or to handle with more general system of nonsmooth equations (see [11, 25, 37, 48, 49, 50]) were developed. Many of these references use the idea of replacing the nonsmooth system of equations by a sequence of simpler (but in general nonlinear) Newton subproblems. Moreover, ideas for globalizing Newton’s method were extended from the smooth to the nonsmooth case. Another way of dealing with nonsmooth problems are so-called smoothing techniques, see [2, 3, 44], for instance. Let us finally refer to an approach for solving nonsmooth equations which employs elements of Clarke’s Jacobian in order to define generalized (but linear) Newton subproblems, see [29, 30, 31, 40, 42, 47] for basic results. This approach is related to the theory presented in Section 5.

Throughout the paper we make use of the special nonsmooth function ϕ : R^{2} → R defined by

ϕ(a, b) = \sqrt{a^{2} + b^{2}} − a − b (a, b ∈ R)  (3)

which has recently attracted the attention of many researchers. This function ϕ was introduced in [12] and goes back to a discussion of W. Burmeister and the author. As one can easily verify, this function possesses the above–mentioned basic property that (1) and (2) are equivalent. Moreover, the function ϕ has been shown as a valuable tool to treat complementarity and related problems [7, 9, 12, 13, 14, 18, 21, 24, 26, 27, 46, 52]. For a review of properties and results connected with the use of this function see [15]. From now on and throughout the paper we will denote by ϕ the function given in (3). Obviously, the complementarity problem CP(F) can be written as the following system of equations:

Φ(x) = [ ϕ(x_{1}, F_{1}(x)) ; ⋮ ; ϕ(x_{n}, F_{n}(x)) ] = 0.

If CP(F) has at least one solution, any global minimizer of the function ∥Φ∥ (with an arbitrary norm ∥ . ∥) will solve the complementarity problem. In [14] we proposed a Newton– type method to reduce ∥Φ∥_{∞} for affine P_{0}–functions F. Geiger and Kanzow [18] as well as Facchinei and Soares [9] suggested minimizing the merit function Ψ : R^{n} → R with

Ψ(x) = \frac{1}{2}∥Φ(x)∥_{2}^{2} = \frac{1}{2} ∑_{i=1}^{n} ϕ(x_{i}, F_{i}(x))^{2} (x ∈ R^{n}),

where F is assumed to be continuously differentiable, see also [24]. It was shown that if F is additionally monotone [18] or a P_{0}–function [9], then any stationary point of Ψ will solve the complementarity problem CP(F) and vice versa. These conditions can further be weakend ([15, 7]) and seem comparable or better than those used in corresponding results [36, 39, 56] obtained for other reformulations of CP(F). Moreover, similar to a proposal in the latter paper by Yamashita and Fukushima [56] (made in connection with minimizing the implicit Lagrangian introduced by Mangasarian and Solodov [34]) Geiger and Kanzow [18] gave a simple and derivative–free method to reduce Ψ.

In this paper we will show how these results, given under the assumption that F is sufficiently smooth, can be generalized to the nonsmooth case. A first valuable contribution in this direction is the paper by Jiang [21]. His approach to handling nonsmooth functions is based on directional derivatives. In contrast to this, by using Clarke’s calculus [5] of generalized subdifferentials, we are able to prove more general and additional results (see Sections 3 and 4 for comparative remarks).

For a function F which is Lipschitzian and monotone on a neighbourhood of a vector x Section 3 shows in particular that if and only if Clarke’s generalized subdifferential ∂Ψ(x) contains the zero vector, then x is a solution of the complementarity problem CP(F). Section 4 presents a simple derivative–free algorithm for the solution of complementarity problems with a monotone locally Lipschitzian function F. Global convergence properties of the algorithm are proved. To show the significance of this kind of complementarity problems with monotone locally Lipschitzian functions we also describe some classes of such functions F that are not everywhere differentiable. However, the aforementioned result in Section 3 requiring F to be Lipschitzian and monotone only near a vector x which satisfies 0 ∈ ∂Ψ(x) does not depend on the method that will be used for computing the vector x.

Some of the papers we cited above deal with the local behaviour of a generalized Newton method for the solution of Φ(x) = 0. The reason why they don’t use the classical Newton method lies in the nonsmoothness of ϕ. In Section 5 of this paper we analyze the local convergence of a generalized Newton method with respect to the nonsmoothness of both ϕ and F, i.e., Φ is regarded as the composition of nonsmooth functions. Our considerations are based on results by Qi and Sun [42, 47] on the superlinear convergence of a generalized Newton method, in particular concerning the use of semismooth functions. By the way, we show a close relationship between Qi and Sun’s approach and the concept proposed by Kummer [30, 31].

After extending the b–regularity condition on F at the vector x to the case when the function F is nonsmooth and monotone in a neighbourhood of x, we can show that under this condition all matrices contained in Clarke’s generalized subdifferential ∂Φ(x) are nonsingular, if x is a solution of CP(F). Moreover, independently of a monotonicity assumption, we prove that the composition of p–order semismooth functions is again p– order semismooth. In this way, conditions on F ([7, 24, 46]) which were shown to imply the 1–order semismoothness of Φ can be weakened. At the end of Section 5 conditions on the function F that guarantee the local superlinear convergence (with the order 1 + p) of a generalized Newton method are given.

2 Mathematical Background and Notations

Let B(x, ϵ) = {y ∈ R^{n} | ∥x − y∥ ≤ ϵ} denote the ball around x with radius ϵ > 0. Furthermore, B_{ϵ} = B(0, ϵ) \ {0} will be used.

Definition 2.1 A function F : R^{n} → R^{m} is called Lipschitzian on a set S ⊆ R^{n} if there is a positive number L > 0 such that

∥F(y) − F(z)∥ ≤ L∥y − z∥ (y, z ∈ S).

If S = B(x, ϵ) for some ϵ > 0 the function F is said to be Lipschitzian near x. Moreover, F is called locally Lipschitzian on R^{n} if it is Lipschitzian on all compact sets S ⊂ R^{n}.

Definition 2.2 Let f : R^{n} → R.

a) The directional derivative of f at x in the direction h is

f′(x, h) = lim_{t↓0} \frac{f(x + th) − f(x)}{t}.

b) The generalized directional derivative of f at x in the direction h is

f∘(x, h) = lim sup_{y→x, t↓0} \frac{f(y + th) − f(y)}{t}.

In analogy to a) the directional derivative of a function F : R^{n} → R^{m} at x in the direction h is defined by F′(x, h) = [F′_{1}(x, h), …, F′_{m}(x, h)]^{T}.

Even if the function f is Lipschitzian near a point x, the directional derivative does not necessarily exist. In contrast to this, the generalized directional derivative introduced by Clarke [5] is well–defined under the Lipschitz condition mentioned above. For a function F : R^{n} → R^{m} which is Lipschitzian near x, Rademacher’s theorem asserts that F is differentiable (in the sense of Fréchet) almost everywhere near x. For the set D_{F} of points where F is differentiable, the usual m × n Jacobian of F exists and is denoted by ∇F(x)^{T}. If, in particular, a real–valued function f : R^{n} → R is considered, then ∇f(x) is an n × 1 column vector.

Definition 2.3 Let F : R^{n} → R^{m} be Lipschitzian near x. The generalized subdifferential of F at x in the sense of Clarke [5] is ∂F(x) = co ∂_{B}F(x), where

∂_{B}F(x) = {D | ∃{x^{ν}} ⊂ D_{F} : lim_{ν→∞} x^{ν} = x, lim_{ν→∞} ∇F(x^{ν})^{T} = D}

and co denotes the convex hull of a set. When m = n, the mapping F is said to be CD– regular (BD–regular) at x if all elements of ∂F(x) (∂_{B}F(x), respectively) are nonsingular.

Now, some common facts which are based on these definitions will be summarized. We refer the reader to the Chapters 2.1, 2.3 and 2.6 in the book by Clarke [5].

Lemma 2.4 Let f : R^{n} → R and F : R^{n} → R^{m} be Lipschitzian near x. Then the following holds:

a) ∂F(x) is nonempty, compact and convex.

b) ∂f(x) = {d^{T} | f∘(x, h) ≥ d^{T} h for all h ∈ R^{n}}.

c) f∘(x, h) = max{d^{T} h | d^{T} ∈ ∂f(x)} for all h ∈ R^{n}.

d) If f attains a (local) minimum at x, then 0 ∈ ∂f(x).

e) ∂F(x) ⊆ ∂F_{1}(x) × ∂F_{2}(x) × … × ∂F_{m}(x), where the right hand side denotes the set of all matrices whose i–th row belongs to ∂F_{i}(x) for each i.

Lemma 2.5 Let F : R^{n} → R^{m} be Lipschitzian near x and g : R^{m} → R be Lipschitzian near F(x). This implies that the composite function f = g ∘ F is Lipschitzian near x and one has ∂f(x) ⊆ co {∂g(F(x))∂F(x)}. Moreover, if in addition g is continuously differentiable at F(x), then ∂f(x) = ∂g(F(x))∂F(x).

By the way, the latter assertion actually holds under the weaker assumption that g is only strictly differentiable, see [5, Chapters 2.2 and 2.6].

Lemma 2.6 Let F : R^{n} → R^{m} be Lipschitzian near x and G : R^{m} → R^{ℓ} be Lipschitzian near F(x). Then, for any p ∈ R^{n}, one has ∂(G ∘ F)(x)p ⊆ co{∂G(F(x))∂F(x)p}.

Different concepts have been developed to extend Newton–type methods and its favourable properties to the case of nonsmooth equations, for instance, see [29, 30, 31, 37, 40, 42, 47, 50]. In this paper we make use of the approach given by Qi and Sun [42, 47] which is explicitly based on semismooth functions. Semismoothness was originally introduced by Mifflin [35] for real–valued functions. Then, Qi and Sun [47] introduced semismooth and p–order semismooth vector–valued functions. To have more consistency between p–order semismoothness and semismoothness, we will employ a nonstandard definition of the latter notion which is, however, equivalent to the original definition of semismooth functions, see [47, Theorem 2.3].

Definition 2.7 A function F : R^{n} → R^{m} is said to be semismooth at x if it is Lipschitzian near x, directionally differentiable at x and

sup_{V ∈∂F(x+h)} ∥V h − F′(x, h)∥ = o(∥h∥)  (h ∈ B_{ϵ})  (4)

for some ϵ > 0. A function F : R^{n} → R^{m} is said to be p–order semismooth at x if it is semismooth at x and

sup_{V ∈∂F(x+h)} ∥V h − F′(x, h)∥ = O(∥h∥^{1+p}) (h ∈ B_{ϵ}) (5)

for some ϵ > 0 and p ∈ (0, 1]. For the proof of the following see the remark at the end of Section 2 in [47]. Lemma 2.8 Let F be semismooth at x. Then, there is ϵ > 0 such that

∥F(x + h) − F(x) − F′(x, h)∥ = o(∥h∥) (h ∈ B_{ϵ}). (6)

If F is p–order semismooth at x, then there is ϵ > 0 such that

∥F(x + h) − F(x) − F′(x, h)∥ = O(∥h∥^{1+p}) (h ∈ B_{ϵ}). (7)

Now, we will recall some further basic definitions. Let I denote the index set {1, …, n}. Definition 2.9 A function F : R^{n} → R^{n} is called

a) monotone on S ⊆ R^{n} if (F (y) − F (z))^{T} (y − z) ≥ 0 (y, z ∈ S),

b) strongly monotone (with modulus μ > 0) on S ⊆ R^{n} if (F (y) − F (z))^{T} (y − z) ≥ μ∥y − z∥^{2} (y, z ∈ S),

c) a uniform P–function (with modulus μ > 0) if

max_{i∈I}{(F_{i}(y) − F_{i}(z))(y_{i} − z_{i})} ≥ μ∥y − z∥^{2} (y, z ∈ S),

d) an R_{0}–function if, for any sequence {x^{ν}} ⊂ R^{n} with lim_{ν→∞} ∥x^{ν}∥ = ∞ and

lim inf_{ν→∞} \frac{min\{x_{1}^{ν}, …, x_{n}^{ν}\}}{∥x^{ν}∥} ≥ 0,  lim inf_{ν→∞} \frac{min\{F_{1}(x^{ν}), …, F_{n}(x^{ν})\}}{∥x^{ν}∥} ≥ 0,

an index j exists such that lim_{ν→∞} x_{j}^{ν} = ∞ and lim_{ν→∞} F_{j}(x^{ν}) = ∞.

The definition of R_{0}–functions is taken from Chen and Harker [2] and is slightly different to the one introduced by Tseng [53].

Definition 2.10 Let M be an n × n matrix. Then M is called

a) a P_{0}–matrix if for all x ∈ R^{n} with x ≠ 0 there is an index i ∈ I such that x_{i} ≠ 0 and x_{i}(Mx)_{i} ≥ 0,

b) positive semi–definite if x^{T} Mx ≥ 0 for all x ∈ R^{n},

c) positive definite (with modulus μ > 0) if x^{T} Mx ≥ μ∥x∥^{2} for all x ∈ R^{n}.

Note that any positive semi–definite matrix is a P_{0}–matrix. For further details see the book by Cottle, Pang and Stone [6]. Finally, for an n × n matrix M = (m_{ij}) and index sets α, β ⊆ I the matrix M_{αβ} denotes the submatrix of M consisting of all m_{ij} with i ∈ α and j ∈ β. For a vector x ∈ R^{n} we denote by x_{α} the subvector with components x_{i}, i ∈ α.

3 Stationary Points of the Merit Function

Firstly, we will summarize some basic properties of the functions φ : R^{2} → R and g : R^{2n} → R which are defined by

φ(a, b) = \frac{1}{2}ϕ(a, b)^{2} (a, b ∈ R), g(x, y) = \frac{1}{2} ∑_{i=1}^{n} ϕ(x_{i}, y_{i})^{2} (x, y ∈ R^{n}).

Let ∇_{1}φ and ∇_{2}φ denote the derivative of φ with respect to the first and to the second argument, respectively. Accordingly, ∇_{1}g and ∇_{2}g will be used for the derivative of g with respect to x and y, respectively.

Lemma 3.1 The functions φ and g are continuously differentiable on R^{n}. Moreover, the following properties are valid for all a, b ∈ R:

a) ∇_{1}φ(a, b) = ∇_{2}φ(a, b) = 0 if and only if φ(a, b) = 0.

b) ∇_{1}φ(a, b) = ∇_{2}φ(a, b) = 0 if and only if ∇_{1}φ(a, b)∇_{2}φ(a, b) = 0.

c) ∇_{1}φ(a, b)∇_{2}φ(a, b) ≥ 0.

These properties can easily be verified, see Geiger and Kanzow [18]. The idea for stating the next lemma (which follows straightforward from the definition of a P_{0}–matrix) comes from the proof of Theorem 4.1 by Facchinei and Soares [9].

Lemma 3.2 Let M be a P_{0}–matrix. Furthermore, let the vectors u, v ∈ R^{n} such that u_{i}v_{i} ≥ 0 for all i ∈ I and u_{i}v_{i} = 0 implies u_{i} = v_{i} = 0 for all i ∈ I. Then

u + Mv = 0 if and only if u = v = 0.

Theorem 3.3 Let F be Lipschitzian near x. If all elements of ∂F (x) are P_{0}–matrices, then

0 ∈ ∂Ψ(x) if and only if Ψ(x) = 0.

Proof: Let the mapping F : R^{n} → R^{2n} be defined by

F(x) = [ \begin{matrix}x \\ F (x) \end{matrix} ] (x ∈ R^{n}).

Since, due to Lemma 3.1, the function g is continuously differentiable, the generalized gradient ∂g(x, y) is a singleton for all x, y ∈ R^{n}. In particular, we have

∂g(x, y) = {∇g(x, y)^{T} } = {∇_{1}g(x, y)^{T} , ∇_{2}g(x, y)^{T} }.

From the definition of Clarke’s generalized subdifferential we have

∂F(x) = \{[ \begin{matrix}I \\ D \end{matrix} ] |D ∈ ∂F (x)\} .  (8)

Furthermore, with regard to Lemma 2.5 it follows that

∂Ψ(x) = ∂g(F(x))∂F(x) = {∇g(x, F (x))^{T} }∂F(x).

From these facts we conclude that for an arbitrary d^{T} ∈ ∂Ψ(x) there is D ∈ ∂F (x) such that

d = ∇_{1}g(x, F (x)) + D^{T} ∇_{2}g(x, F (x)).  (9)

Now, in view of 0 ∈ ∂Ψ(x), let us consider d = 0. Setting u_{i} = ∇_{1}φ(x_{i}, F_{i}(x)) and v_{i} = ∇_{2}φ(x_{i}, F_{i}(x)) for i ∈ I and using Lemma 3.1 b), c), we see that u and v fulfill the assumptions of Lemma 3.2. Since all elements of ∂F (x) were assumed to be P_{0}–matrices, Lemma 3.2 yields u = v = 0, i.e., ∇_{1}φ(x_{i}, F_{i}(x)) = ∇_{2}φ(x_{i}, F_{i}(x)) = 0 for all i ∈ I. According to Lemma 3.1 a), we have g(x, F (x)) = Ψ(x) = 0. On the other hand, if Ψ(x) = 0, then x is a minimizer of the function Ψ over R^{n}. This implies 0 ∈ ∂Ψ(x), see Lemma 2.4 d). □

Lemma 3.4 Let F be Lipschitzian on an open set S ⊆ R^{n}. If the mapping F is monotone (strongly monotone with modulus μ > 0) on S, then all elements of the generalized Jacobian ∂F (x) are positive semi–definite (positive definite with modulus μ > 0) for all x ∈ S.

For the proof of this lemma we refer to [22, Proposition 2.3]. Since any positive semi– definite matrix is also a P_{0}–matrix, Theorem 3.3 and Lemma 3.4 lead to the next result.

Theorem 3.5 Let F be Lipschitzian and monotone on an open set S ⊆ R^{n} containing x. Then

0 ∈ ∂Ψ(x) if and only if Ψ(x) = 0.

Theorem 3.3 generalizes an approach in Facchinei and Soares [9] whereas Theorem 3.5 extends a result obtained by Geiger and Kanzow [18]. Both papers assume that F is at least continuously differentiable. We further note that Theorem 3.5, as well as Theorem 3.3, is more general than the following related result by Jiang [21, Proposition 7]. It was shown therein that

Ψ′(x, h) ≥ 0 for all h ∈ R^{n} if and only if Ψ(x) = 0,

if F is Lipschitzian, directionally differentiable and monotone near x. We will conclude this section with an example of a function which is Lipschitzian and monotone near x = 0 but not directionally differentiable at this point.

Example 3.6 Let the sequence {a_{ν}} ⊂ (0, 1] be defined by a_{ν} = 2^{−ν} for ν ∈ N. Then, consider the function f : [−1, 1] → R with

f(x) = \{ \begin{matrix}a_{ν} & if ν even \\ a_{ν−1} + 3(x − a_{ν}) & if ν odd \end{matrix} (x ∈ [a_{ν+1}, a_{ν}], ν ∈ N).

and f(x) = 0 for x ∈ [−1, 0]. As it can easily be seen this function is Lipschitzian and monotone near x = 0. However, it is not directionally differentiable at 0 because

lim_{l→∞} \frac{f(a_{2l})}{a_{2l}} = 1,  lim_{l→∞} \frac{f(a_{2l+1})}{a_{2l+1}} = lim_{l→∞} \frac{a_{2l}}{a_{2l+1}} = 2.

4 A Descent Method without Using Derivatives

Recently Yamashita and Fukushima [56] proposed a descent method for the differentiable implicit Lagrangian M_{α} of Mangasarian and Solodov [34] . To determine the search directions of this method, derivatives of F are not required. Moreover, under the assumption that F is continuously differentiable and strongly monotone it can be proved that the proposed search direction is a descent direction for M_{α}. Geiger and Kanzow [18] gave a related approach for the merit function Ψ and showed that a certain simple search direction turns out to be a descent direction for Ψ if the continuously differentiable function F is monotone. Both methods were proved to converge to the unique solution of CP(F) under the condition that F is strongly monotone. Then, Jiang [21] replaced this condition by monotonicity of F and showed that any accumulation point of the descent method [18] with a modified steplength procedure solves the complementarity problem. All these approaches are based on the assumption that F is continuously differentiable.

In contrast to this and to the conjecture expressed in [21] we will show that the idea of a descent method for the merit function Ψ can succesfully be generalized to the case when F is only locally Lipschitzian and monotone. At first, Example 4.1 will present some possible sources of complementarity problems CP(F) with such nonsmooth functions F.

Example 4.1 Consider the programming problem

f(x) → min subject to x ≥ 0,  (10)

where f : R^{n} → R is assumed to be a convex LC^{1} function. LC^{1} means that the derivative ∇f exists and is locally Lipschitzian. It is well-known that the Karush-Kuhn-Tucker conditions for problem (10) are equivalent to the complementarity problem CP(F) with F = ∇f. Moreover, each solution of CP(F) can be assigned to a solution of the programming problem (10), and vice versa. Obviously, F = ∇f is both monotone and locally Lipschitzian.

a) Now, we are going to describe a class of functions F = ∇f which are additionally nonsmooth, i.e., not everywhere differentiable. To this end, consider first the composite function f = c ∘ g, where c : R ⊆ R → R denotes any convex LC^{1} function whose derivative is nonsmooth. For example, c could be

c_{1}(a) = max{0, a}^{2}, c_{2}(a) = min{0, a}^{2} for a ∈ R = R

or

c_{3}(a) = ∫_{a_{0}}^{a} ζ(t)dt for a ∈ R = [a_{0}, ∞)

with a locally Lipschitzian and monotoneously increasing function ζ : [a_{0}, ∞) → R. Furthermore, g : R^{n} → R denotes any convex LC^{1} function.

Then, if c is additionally monotoneously increasing (like c_{1} or c_{3} for ζ ≥ 0) the composition of g and c is a convex LC^{1} function. In analogy to this, the composition of any concave LC^{1} function g with a function c which is additionally required to be monotoneously decreasing (like c_{2} or c_{3} with ζ ≤ 0) provides a convex LC^{1} function. Moreover, the composition of a linear function g with c yields a convex LC^{1} function f = c ∘ g. Now, any positive linear combination of (such composite or other) convex LC^{1} functions is possible for f. In particular, one of the functions in the linear combination could be strongly convex. In this case some other terms of the linear combination can be in some sense nonconvex, although the linear combination itself remains convex. Moreover, a twice differentiable strongly convex term within this linear combination ensures that F = ∇f is strongly monotone.

See also [20, Chapter IV.2] for some related convexity preserving operations.

b) If f_{0} : R^{n} → R denotes any (possibly nonsmooth) convex function, the Moreau-Yosida regularization f : R^{n} → R (see, e.g., [20, Chapter XI.3.4.4]) of f_{0} is given by

f(x) = min_{y∈R^{n}}\{f_{0}(y) + \frac{1}{2}(y − x)^{T} M(y − x)\}.

It turns out that f is (possibly in contrast to f_{0}) an LC^{1} function. Moreover, minimizing f and f_{0} are equivalent problems in the sense that each minimizer of f is a minimizer of f_{0} and vice versa. If we now consider the constrained minimization problem (10) it can easily be shown that an analogous property holds, namely that (10) and the problem

f_{0}(x) → min subject to x ≥ 0

have identical solution sets. With regard to recent results in [32, 17, 45, 4] that used the Moreau-Yosida regularization as a tool for unconstrained nonsmooth convex optimization, it seems interesting to consider minimization problems with (at least particular types of) constraints. Then, the algorithm we will present in this section can serve as a basis for developing a new method with global convergence properties for nonsmooth convex minimization problems. Additionally, a combination with the generalized Newton method (Section 5) can lead to a locally superlinearly convergent algorithm, where it has to be taken into account that the Moreau-Yosida regularization possesses a semismooth derivative under reasonable conditions, see [43].

c) Finally, we would like to mention a particular kind of stochastic programs, so-called Extended Linear-Quadratic Programs (first introduced by Rockafellar and Wets), see, e.g., [23] for more details and references. When applying the Karush-Kuhn-Tucker conditions to such a problem (which, in contrast to (10), has further linear inequality constraints) we can get a monotone complementarity problem CP(F), where F is locally Lipschitzian but nonsmooth.

Now, we define the search direction s(x) by means of a function s : R^{n} → R^{n} with

s(x) = −∇_{2}g(x, F (x)) (x ∈ R^{n}),

see [18, 21].

Lemma 4.2 Let F be Lipschitzian and monotone on an open set S ⊆ R^{n} containing x. If Ψ(x) > 0, then

s(x)^{T} d ≤ −θ(x) < 0 (d^{T} ∈ ∂Ψ(x)),

where the function θ : R^{n} → R is given by θ(x) = ∇_{2}g(x, F (x))^{T} ∇_{1}g(x, F (x)).

Proof: Let d^{T} ∈ ∂Ψ(x). Then, there is D ∈ ∂F (x) such that (9) holds. According to Lemma 3.4 the monotonicity of F near x ensures that any matrix D ∈ ∂F (x) is positive semi–definite. Consequently, (9) yields

s(x)^{T} d ≤ −θ(x).

Since 0 < Ψ(x) = g(x, F (x)) implies φ(x_{i}, F_{i}(x)) > 0 for at least one index i ∈ I, Lemma 3.1 yields ∇_{1}φ(x_{i}, F_{i}(x))∇_{2}φ(x_{i}, F_{i}(x)) > 0 and

θ(x) = ∇_{1}g(x, F (x))^{T} ∇_{2}g(x, F (x)) ≥ ∇_{1}φ(x_{i}, F_{i}(x))∇_{2}φ(x_{i}, F_{i}(x)) > 0.

□

The next lemma shows that s(x) is a descent direction for the merit function Ψ at x and guarantees a sufficient (locally linear) decrease along this direction.

Lemma 4.3 Let F be Lipschitzian and monotone on an open set S ⊆ R^{n} containing x. If Ψ(x) > 0 and σ ∈ (0, 1) is arbitrary but fixed, then there is a number t(x) > 0 such that

Ψ(x + ts(x)) ≤ Ψ(x) − σtθ(x)  (t ∈ [0, t(x)]).  (11)

Moreover, for any ϵ > 0, a bound t_{ϵ} > 0 exists such that t(x) ≥ t_{ϵ} is satisfied for all x ∈ W_{ϵ} = {x ∈ S̄ | Ψ(x) ≥ ϵ, ∥x∥ ≤ ϵ^{−1}}, where S̄ ⊆ S denotes any nonempty closed set.

Proof: Let x ∈ S and σ ∈ (0, 1) be arbitrary but fixed. Using Lemma 2.4 c), we get

lim sup_{t↓0} \frac{1}{t}(Ψ(x + ts(x)) − Ψ(x)) ≤ lim sup_{y→x,t↓0} \frac{1}{t}(Ψ(y + ts(x)) − Ψ(y))
= Ψ∘(x, s(x))
= max{s(x)^{T} d | d^{T} ∈ ∂Ψ(x)}
≤ −θ(x),

where the last inequality follows from Lemma 4.2. Since, according to the proof of the same lemma, Ψ(x) > 0 ensures θ(x) > 0, there must be a positive number t(x) such that (11) is satisfied.

Now, let ϵ > 0 be arbitrary but fixed. Furthermore, from now on t(x) denotes the largest number in [0, 1] that fulfills (11) with σ̄ = σ + (1 − σ)/2 instead of σ. Due to the continuity of Ψ, such a number exists. Suppose that there is a sequence {x^{ν}} ⊂ W_{ϵ} such that lim_{ν→∞} t(x^{ν}) = 0. Without loss of generality we can assume that x̄ = lim_{ν→∞} x^{ν} ∈ W_{ϵ} exists. Because of the continuity of ∇_{1}g, ∇_{2}g and F the mappings s and θ are continuous, too. Thus s̄ = lim_{ν→∞} s(x^{ν}) exists and satisfies s̄ = s(x̄). Moreover, with regard to Ψ(x̄) > 0 and Lemma 4.2, it follows that lim_{ν→∞} θ(x^{ν}) = θ(x̄) > 0. Since (11) holds in particular for x = x̄ with t(x̄) > 0 and with σ̄ instead of σ, we obtain, due to continuity arguments,

Ψ(x^{ν} + ts(x^{ν})) ≤ Ψ(x^{ν}) − σtθ(x^{ν}) (t ∈ [0, t(x̄)])

for sufficiently large ν. Consequently, t(x^{ν}) ≥ t(x̄) > 0. This contradicts lim_{ν→∞} t(x^{ν}) = 0. □

Algorithm 1

Step 0: Choose x^{0} ∈ R^{n}, ρ, σ ∈ (0, 1), set k = 0.
Step 1: If Ψ(x^{k}) = 0, stop.
Step 2: Set s^{k} = s(x^{k}) and determine t_{k} ∈ {ρ^{j} | j ∈ N} as large as possible such that
Ψ(x^{k} + t_{k}s^{k}) ≤ Ψ(x^{k}) − σt_{k}θ(x^{k}).  (12)
Step 3: Set x^{k+1} = x^{k} + t_{k}s^{k}, k = k + 1 and go to Step 1.

In comparison with [18, 21], Algorithm 1 employs another condition (12) to determine the steplength t_{k}. Throughout the remainder of this section we assume that the test in Step 1 of Algorithm 1 will never be fulfilled.

Theorem 4.4 Let F be locally Lipschitzian and monotone on R^{n}. Then, Algorithm 1 is well–defined. Furthermore, any accumulation point of the sequence {x^{k}} generated by Algorithm 1 solves the complementarity problem CP(F).

Proof: At first note that s(x) and θ(x) are well–defined for all x ∈ R^{n}. Furthermore, for any x^{k} generated by Algorithm 1, Lemma 4.3 ensures that Step 2 computes a steplength t_{k} > 0.

Since {Ψ(x^{k})} is a monotoneously decreasing sequence and bounded below, the limit Ψ^{∗} = lim_{k→∞} Ψ(x^{k}) must exist. Let us suppose Ψ^{∗} > 0. Further, let x^{∗} denote an accumulation

point of the sequence {x^{k}}. Then, there is an infinite set N^{∗} ⊆ N such that lim_{k∈N^{∗}} x^{k} = x^{∗}.

Setting ϵ = \frac{1}{2} min\{Ψ^{∗}, (∥x^{∗}∥ + 1)^{−1}\}, we obtain x^{k} ∈ W_{ϵ} for all sufficiently large k ∈ N^{∗}. For these iterates, Lemma 4.3 provides t(x^{k}) ≥ t_{ϵ} > 0. Moreover, by the continuity of θ we have lim_{k∈N^{∗}} θ(x^{k}) = θ(x^{∗}) and θ(x^{k}) ≥ \frac{1}{2}θ(x^{∗}) > 0 for all k ∈ N^{∗}. The inequality θ(x^{∗}) > 0 follows from Ψ(x^{∗}) ≥ ϵ > 0 and the proof of Lemma 4.2. With regard to these facts, condition (12) yields

Ψ(x^{k+1}) ≤ Ψ(x^{k}) − \frac{1}{2}σt_{ϵ}θ(x^{∗}) (k ∈ N^{∗}).

Therefore, one has lim_{k→∞} Ψ(x^{k}) = −∞. This contradicts Ψ^{∗} > 0. Hence, Ψ(x^{∗}) = 0 must be valid. □

To formulate the next result see the notion of R_{0}–functions in Definition 2.9 d). This class of functions generalizes the well–known concept of an R_{0}–matrix when F is affine [2, Proposition 10]. Moreover, it has been shown [2, Proposition 11] that any uniform P–function F is an R_{0}–function.

Theorem 4.5 Let F be an R_{0}–function. Then, the level set Ω(r) = {x ∈ R^{n} | ∥Φ(x)∥ ≤ r} is bounded for any r ≥ 0.

Proof: For an arbitrarily chosen r ≥ 0, suppose a sequence {x^{ν}} ⊂ Ω(r) satisfying lim_{ν→∞} ∥x^{ν}∥ = ∞ exists. According to Definition 2.9 d) there is an index j such that lim_{ν→∞} x_{j}^{ν} = ∞ and lim_{ν→∞} F_{j}(x^{ν}) = ∞. Since 2|ϕ(a, b)| ≥ | min{a, b}| is valid for all a, b ∈ R, it follows that lim_{ν→∞} |ϕ(x_{j}^{ν}, F_{j}(x^{ν}))| = ∞ and lim_{ν→∞} ∥Φ(x)∥ = ∞. This contradicts {x^{ν}} ⊆ Ω(r). □

Related results for special cases, in particular when F is affine, strongly monotone or a uniform P–function, can be found in [2, 13, 24, 27, 52].

Theorem 4.6 Let F be an R_{0}–function, locally Lipschitzian and monotone on R^{n}. Then, Algorithm 1 is well–defined and generates at least one accumulation point. Each of these accumulation points solves the complementarity problem CP(F).

Proof: Any sequence {x^{k}} generated by Algorithm 1 lies in the level set Ω(∥Φ(x^{0})∥). Therefore, the Theorems 4.4 and 4.5 yield the desired result. □

5 Generalized Newton Method

In what follows we study the local behaviour of a generalized Newton method applied to the system Φ(x) = 0. The function Φ is a composition of the nonsmooth function ϕ and of F. In this paper the latter function F is allowed to be nonsmooth, too.

Our first aim is to give sufficient conditions on F which ensure that all Newton subproblems of the subsequent algorithm can be solved uniquely near a solution x^{∗} of Φ(x) = 0. The algorithm uses elements of Clarke’s generalized subdifferential (generalized Jacobian) as a substitute for the classical Jacobian.

Algorithm 2

Step 0: Choose x^{0} ∈ R^{n}, set k = 0.
Step 1: If Φ(x^{k}) = 0, stop.
Step 2: Choose V_{k} ∈ ∂Φ(x^{k}) and compute x^{k+1} = x^{k} − V_{k}^{−1}Φ(x^{k}).

Set k = k + 1 and go to Step 1.

The following theorem is Theorem 3.2 in [47].

Theorem 5.1 Suppose that x^{∗} is a solution of Φ(x) = 0 and that the function Φ is semismooth and CD–regular at x^{∗}. Then, Algorithm 2 is well–defined and Q–superlinearly convergent to x^{∗} for any x^{0} in a sufficiently small neighbourhood of x^{∗}. If, in addition, Φ is p–order semismooth at x^{∗}, then the convergence is of the Q–order 1 + p.

To provide sufficient conditions for the CD–regularity of the mapping Φ at x^{∗} we first state a regularity condition. It can be viewed in some particular sense as an extension of a condition used for not necessarily monotone functions F in [9, 26, 34, 36] to the nonsmooth case.

Definition 5.2 Let F be monotone on an open set containing x. Moreover, let π denote the index set {i ∈ I | F_{i}(x) = 0}. The function F is said to be b–regular at x if the submatrix D_{ππ} is positive definite for all D ∈ ∂F (x).

The next lemma contains a sufficient condition for F to fulfill the b–regularity assumption.

Lemma 5.3 If the function F is Lipschitzian and strongly monotone on the open set S ⊆ R^{n}, then F is b–regular for all x ∈ S.

Proof: Since any principal submatrix of a positive definite matrix is again positive definite, the assertion follows with Lemma 3.4. □

Theorem 5.4 Let F be Lipschitzian and monotone on an open set containing x^{∗}. If F is b–regular at x^{∗} and Φ(x^{∗}) = 0, then Φ is CD–regular at x^{∗}, i.e., all elements of ∂Φ(x^{∗}) are nonsingular.

Proof: Let the function F : R^{n} → R^{2n} be defined as in the proof of Theorem 3.3. Furthermore, we define G : R^{2n} → R^{n} by G_{i}(x, y) = ϕ(x_{i}, y_{i}) for arbitrary x, y ∈ R^{n} and all i ∈ I. Obviously, Φ = G ∘ F follows. Using Lemma 2.4 e) and Lemma 2.6 we obtain for arbitrary x, p ∈ R^{n}

∂Φ(x)p ⊆ co{∂G(F(x))∂F(x)p} ⊆ co{W (x)p} = co{W (x)}p

with

W (x) = (∂G_{1}(x, F (x)) × ⋯ × ∂G_{n}(x, F (x)))∂F(x).

Having (8) in mind, any V ∈ W (x) can be written as follows:

V = [Λ, Γ] [ \begin{matrix}I \\ D \end{matrix} ] = Λ + ΓD,  (13)

where D ∈ ∂F (x) and Λ = diag(λ_{i}), Γ = diag(γ_{i}) with (λ_{i}, γ_{i}) ∈ ∂ϕ(x_{i}, F_{i}(x)) for all i ∈ I. If ϕ is differentiable at (a, b), we have

∂ϕ(a, b) = \{(\frac{a}{\sqrt{a^{2} + b^{2}}} − 1, \frac{b}{\sqrt{a^{2} + b^{2}}} − 1)\}.

In any case

λ_{i}, γ_{i} ∈ [−2, 0], λ_{i}^{2} + γ_{i}^{2} ≥ 3 − 2\sqrt{2} > 0 (i ∈ I)  (14)

is valid, see [12]. Moreover, Lemma 3.4 provides that all D ∈ ∂F (x) are positive semi– definite. It can easily be seen that any V̂ ∈ co{W (x)} has the structure (13). More precisely, V̂ = Λ̂ + Γ̂D with negative semi–definite diagonal matrices Λ̂, Γ̂ and a positive semi–definite matrix D ∈ ∂F (x). The latter is true because ∂F (x) is a convex set. To show the nonsingularity of all V̂ ∈ co{W (x)} we consider the system V̂ p = 0. Without loss of generality we can assume that the complementarity problem CP(F) is arranged in such a way that the following partition of the system V̂ p = 0 is possible.

Λ̂_{κκ}p_{κ} + Γ̂_{κκ}(D_{κα}p_{α} + D_{κβ}p_{β}) = 0 (κ ∈ {α, β})  (15)

with α = {i ∈ I|γ_{i} < 0}, β = I \ α. Note that the definition of these index sets differs from the usual meaning of α and β (compare [6]). Taking into account that λ_{i} ≤ 0 for all i ∈ I we get from the definition of β

Γ̂_{ββ} = 0.

From (14) we further have that Λ̂_{ββ} and Γ̂_{αα} are negative definite. Setting κ = β, equation (15) yields p_{β} = 0. Using this and setting κ = α, we obtain from (15)

(Γ̂_{αα}^{−1}Λ̂_{αα} + D_{αα})p_{α} = 0.

Considering x = x^{∗} with Φ(x^{∗}) = 0, we get α ⊆ π. Hence, the b–regularity assumption ensures that the matrix D_{αα} is positive definite. This, together with the positive semi– definiteness of Γ̂_{αα}^{−1}Λ̂_{αα}, implies p_{α} = 0. Consequently, V̂ p = 0 yields p = 0 and all V̂ ∈ co{W (x)} are nonsingular. □

The second aim of this section is to show that the composition of p–order semismooth functions is again p–order semismooth. Based on this we will be able to give relatively weak conditions on F which ensure that the iterates generated by Algorithm 2 converge with the local Q–order 1 + p .

Before treating these questions in detail we point out a close relationship between the convergence theory for generalized Newton–type methods given by Kummer [30, 31] and the independent approach by Qi and Sun [42, 47] which is based on (p–order) semismooth functions. For such functions F the first formula in the next lemma was given by Pang and Qi [40, Proposition 1] and follows from (4) and (6). If F is p–order semismooth, we can state an analogous result (formula (17)) which can be proved with regard to (5) and (7).

Lemma 5.5 Suppose that F : R^{n} → R^{m} is semismooth at x. Then, ϵ > 0 exists such that

sup_{V ∈∂F(x+h)} ∥F(x + h) − F(x) − V h∥ = o(∥h∥)  (h ∈ B_{ϵ}).  (16)

If F is p–order semismooth at x, then ϵ > 0 exists such that

sup_{V ∈∂F(x+h)} ∥F(x + h) − F(x) − V h∥ = O(∥h∥^{1+p})  (h ∈ B_{ϵ}).  (17)

Keeping this lemma in mind it turns out that condition (16) (with m = n) is equivalent to condition (2.1) in [30, Proposition 3], if in the latter the approximation of F by means of Clarke’s generalized subdifferential is considered. Moreover, (16) is a particular case of condition (CA) used in [31]. Together with an appropriate regularity assumption the results in [30, 31] imply the local superlinear convergence of generalized Newton methods. For a special mapping F, whose zeros are the Karush–Kuhn–Tucker points of a nonlinear inequality constrained optimization problem, we proved in [12] that condition (17) with p = 1 holds under reasonable assumptions and leads to the local Q–quadratic convergence of a generalized Newton–type method. This was done under the condition that the functions of the underlying optimization problem are twice differentiable with locally Lipschitzian Hessians. Then, under the weaker condition that the functions of the optimization problem are continuously differentiable with semismooth derivatives, Qi and Jiang [46] proved local superlinear convergence.

Now, we return to the complementarity problem CP(F) and to its equivalent reformulation Φ(x) = 0. Owing to Theorems 5.1 and 5.4 the question of which condition on F guarantees that Algorithm 2 is locally superlinearly convergent with a certain order of convergence reduces to the problem of finding conditions that imply the p–order semismoothness of Φ at x^{∗}. Up to now relatively strong conditions have been employed: The function F has been assumed to be at least twice continuously differentiable, see [24, Theorem 1], [7, Theorem 3.1], [46, Theorem 3.2].

To prove superlinear convergence under weaker conditions, we first note, that due to a well–known result of Mifflin [35, Theorem 5], the composition of semismooth functions is again semismooth. Consequently, keeping in mind that ϕ is semismooth, Algorithm 2 converges locally superlinearly to a zero x^{∗} of Φ if F itself is semismooth at x^{∗}. To show that this assertion can be suitably extended to the important case when F is 1– order (or p–order) semismooth, we will prove the subsequent theorem. It generalizes the already mentioned result of Mifflin to p–order semismooth functions. The following lemma is needed before. It provides a useful result on the directional derivative of composite semismooth functions.

Lemma 5.6 Suppose that the function F : R^{n} → R^{m} is semismooth at x and that the function g : R^{m} → R is semismooth at F(x). Then, the composite function f = g ∘ F is directionally differentiable at x and

f′(x, h) = g′(F(x), F′(x, h)) (h ∈ R^{n}).

Proof: Since f is the composition of two semismooth functions, it is again semismooth and thus directionally differentiable. Setting η(th) = F(x + th) − F(x) and taking into account that g′(F(x), .) is both Lipschitzian on R^{m} (see [47, Lemma 2.2]) and positive homogeneous with respect to the direction, we obtain with Lemma 2.8 (applied to g instead of F)

f′(x, h) = lim_{t↓0} \frac{1}{t} (g(F(x) + η(th)) − g(F(x))) = lim_{t↓0} g′(F(x), \frac{1}{t}η(th))  (18)

for all h ∈ B_{ϵ} and some ϵ > 0. Using Lemma 2.8 a second time, we get

∥η(th) − tF′(x, h)∥ = ∥F(x + th) − F(x) − F′(x, th)∥ = o(∥th∥)

for all t ∈ [0, 1], all h ∈ B_{ϵ} and some ϵ > 0. This together with (18) yields

f′(x, h) = lim_{t↓0} g′(F(x), F′(x, h) + \frac{1}{t}(η(th) − tF′(x, h))) = g′(F(x), F′(x, h)),

for all h ∈ B_{ϵ} and some ϵ > 0. Thus, recalling that each directional derivative is positive homogeneous with respect to the direction, the previous equation must be valid for all h ∈ R^{n}. □

Theorem 5.7 Suppose that the function F : R^{n} → R^{m} is p–order semismooth at x and that the function G : R^{m} → R^{n} is p–order semismooth at F(x). Then, the composite function H = G ∘ F is p–order semismooth at x.

Proof: Let g = G_{j} for some arbitrary but fixed j ∈ {1, …, m}. We will now show that f = H_{j} = g ∘ F is p–order semismooth at x. This means that each component of H and thus H itself is p–order semismooth, compare [47, Corollary 2.4].

Lemma 2.5 yields ∂f(x + h) ⊆ Ŝ(h) for all h ∈ B_{ϵ} and some ϵ > 0, where Ŝ(h) denotes the convex hull of the set S(h) = ∂g(F(x + h))∂F(x + h), and we obtain

sup_{v^{T} ∈∂f(x+h)} ∥v^{T} h − f′(x, h)∥ ≤ sup_{v^{T} ∈Ŝ(h)} ∥v^{T} h − f′(x, h)∥  (19)

for all h ∈ B_{ϵ}. Let us consider the function r : Ŝ(h) → [0, ∞) with

r(v) = ∥v^{T} h − f′(x, h)∥ (v^{T} ∈ Ŝ(h)),

where h ∈ B_{ϵ} is arbitrary but fixed. From Lemma 2.4 a) it follows that S(h) and Ŝ(h) as the convex hull of S(h) are compact. Thus, the continuous function r attains its maximum at a certain v̄^{T} ∈ Ŝ(h). If v̄^{T} ∉ S(h), then Carathéodory’s theorem ensures the existence of, at most, n + 1 vectors v_{1}^{T} , …, v_{n+1}^{T} ∈ S(h) and of a vector μ ∈ R^{n+1} such that

v̄ = ∑_{i=1}^{n+1} μ_{i}v_{i}, ∑_{i=1}^{n+1} μ_{i} = 1, μ_{i} ≥ 0 (i ∈ {1, …, n + 1}).

Therefore by the convexity of r, we have

r(v̄) = r( ∑_{i=1}^{n+1} μ_{i}v_{i}) ≤ ∑_{i=1}^{n+1} μ_{i}r(v_{i}).

Consequently, there must be at least one v̂^{T} ∈ S(h) at which r attains its maximum, i.e., r(v̂) = r(v̄). The vector v̂^{T} ∈ S(h) = ∂g(F(x + h))∂F(x + h) can be represented as v̂^{T} = v_{g}^{T} V_{F} with v_{g}^{T} ∈ ∂g(F(x + h)) and V_{F} ∈ ∂F(x + h), where we note that v_{g}, as well as V_{F}, depends on the direction h. Using (19) and Lemma 5.6, we obtain

sup_{v^{T} ∈∂f(x+h)} ∥v^{T} h − f′(x, h)∥ ≤ ∥v̂^{T} h − f′(x, h)∥ = ∥v_{g}^{T} V_{F}h − g′(F(x), F′(x, h))∥

for h ∈ B_{ϵ} and some ϵ > 0. To continue estimating the right hand side we set η̄ = F(x+h)− F(x) and use in succession formula (7), formula (17), v_{g} ∈ ∂g(F(x + h)) = ∂g(F(x) + η̄), the p–order semismoothness of g and the Lipschitz continuity of F near x. Moreover, we need the fact that, owing to [47, Lemma 2.2], g′(F(x), .) is Lipschitzian on R^{m} with respect to the second argument.

sup_{v^{T} ∈∂f(x+h)} ∥v^{T} h − f′(x, h)∥ ≤ ∥v_{g}^{T} V_{F}h − g′(F(x), η̄)∥ + O(∥h∥^{1+p})
≤ ∥v_{g}^{T} η̄ − g′(F(x), η̄)∥ + O(∥h∥^{1+p})
≤ sup_{v^{T} ∈∂g(F(x)+η̄)} ∥v^{T} η̄ − g′(F(x), η̄)∥ + O(∥h∥^{1+p})
≤ O(∥η̄∥^{1+p}) + O(∥h∥^{1+p}) ≤ O(∥h∥^{1+p})

for h ∈ B_{ϵ} and some ϵ > 0. Therefore, we see that g is indeed p–order semismooth at x. □

Lemma 5.8 The function ϕ is 1–order semismooth on R^{n}.

Proof: The function ϕ is arbitrarily many times differentiable for all arguments ξ ∈ R^{2} with ξ ≠ 0 and hence 1–order semismooth at these points. Therefore, only the case ξ = 0 ∈ R^{2} will be considered. Obviously, ξ + η = η ≠ 0 yields ∂ϕ(ξ + η) = {∇ϕ(η)^{T} }. Furthermore, since

∇ϕ(η)^{T} η = ϕ(η) = lim_{t↓0} \frac{ϕ(tη) − ϕ(0)}{t} = ϕ′(0, η),

the function ϕ is 1–order semismooth at ξ = 0. □

Now, with regard to Theorems 5.1, 5.4, 5.7 and to Lemma 5.8, the next result follows immediately. Theorem 5.9 Suppose that F is b–regular and semismooth at a solution x^{∗} of CP(F). Then, Algorithm 2 is well–defined and Q–superlinearly convergent to x^{∗} for any x^{0} in a sufficiently small neighbourhood of x^{∗}. If, in addition, F is p–order semismooth at x^{∗}, then the convergence is of the Q–order 1 + p.

The 1–order semismoothness condition used in this theorem is weaker than the requirement that F is at least twice continuously differentiable, compare [7, 24, 46]. With regard to these papers let us note that the differentiability of F at x with a Lipschitzian Jacobian near x implies the 1–order semismoothness of F at x.

Moreover, it is known [40, 42] that the CD–regularity in Theorem 5.1 can be replaced by the weaker BD–regularity which means that all elements of the B–subdifferential ∂_{B}Φ(x^{∗}) have to be nonsingular, see Definition 2.3. Therefore, although we did not give a sufficient condition for BD–regularity to hold at a solution x^{∗}, Theorem 5.9 remains valid if BD– regularity is used instead of b–regularity according to Definition 5.2.

Keeping the results presented in Sections 3 – 5 in mind, further research will be directed on algorithms with both global and local superlinear convergence for complementarity problems CP(F) with nonsmooth functions F. In particular, we are interested in descent directions for Ψ if F is not monotone.

Acknowledgement: I would like to thank both anonymous referees for their valuable comments and a thorough reading of the manuscript. Moreover, I am very grateful to Professor L. Qi for helpful discussions.

References

[1] S. C. Billups and M. C. Ferris, QPCOMP: A quadratic program based solver for mixed complementarity problems, Mathematical Programming Technical Report 95–09, University of Wisconsin, Madison, Wisconsin, USA, 1995.

[2] B. Chen and P. T. Harker, Smooth approximations to nonlinear complementarity problems, Technical Report, Department of Management and Systems, College of Business and Economics, Washington State University, Pullman, WA, USA, 1995.

[3] C. Chen and O. L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems, Computational Optimization and Applications, 1995, to appear.

[4] X. Chen and M. Fukushima, Proximal Quasi-Newton methods for nondifferentiable convex optimization, Applied Mathematics Report AMR 95/32, School of Mathematics, The University of New South Wales, Sydney, Australia, 1995.

[5] F. H. Clarke, Optimization and Nonsmooth Analysis, John Wiley & Sons, New York, 1983.

[6] R. W. Cottle, J.-S. Pang and R. E. Stone, The Linear Complementarity Problem, Academic Press, New York, 1992.

[7] T. De Luca, F. Facchinei and C. Kanzow, A semismooth equation approach to the solution of nonlinear complementarity problems, Preprint 93, Institute of Applied Mathematics, University of Hamburg, Hamburg, Germany, 1995.

[8] S. P. Dirkse and M. C. Ferris, The PATH solver: A non-monotone stabilization scheme for mixed complementarity problems, Optimization Methods and Software, 5 (1995), 123–156.

[9] F. Facchinei and J. Soares, A new merit function for nonlinear complementarity problems and a related algorithm, SIAM Journal on Optimization, to appear.

[10] M. C. Ferris and D. Ralph, Projected gradient methods for nonlinear complementarity problems via normal maps, in D.Z. Du, L. Qi, R. S. Womersley (eds.): Recent Advances in Nonsmooth Optimization, World Scientific, Singapore, 1995, pp. 57–87.

[11] M. C. Ferris and S. Lucidi, Nonmonotone stabilization methods for nonlinear equations, Journal of Optimization Theory and Applications, 81 (1994), pp. 53–71.

[12] A. Fischer, A special Newton-type optimization method, Optimization, 24 (1992), pp. 269–284.

[13] A. Fischer, A Newton-type method for positive semidefinite linear complementarity problems, Journal of Optimization Theory and Applications, 86 (1995), pp. 585–608.

[14] A. Fischer, On the superlinear convergence of a Newton-type method for LCP under weak conditions, Optimization Methods and Software, 6 (1995), pp. 83–107.

[15] A. Fischer, An NCP–function and its use for the solution of complementarity problems, in D.Z. Du, L. Qi, R. S. Womersley (eds.): Recent Advances in Nonsmooth Optimization, World Scientific, Singapore, 1995, pp. 88–105.

[16] A. Friedlander, J. M. Martìnez and S. A. Santos, Resolution of linear complementarity problems using minimization with simple bounds, Technical Report, Department of Applied Mathematics, University of Campinas, Campinas, Brazil, 1993.

[17] M. Fukushima and L. Qi, A globally and superlinearly convergent algorithm for nonsmooth convex minimization, SIAM Journal on Optimization, to appear.

[18] C. Geiger and C. Kanzow, On the resolution of monotone complementarity problems, Computational Optimization and Applications, to appear.

[19] P. T. Harker and B. Xiao, Newton’s method for the nonlinear complementarity problem: a B–differentiable equation approach, Mathematical Programming, 48 (1990), pp. 339– 357.

[20] J.–B. Hiriart–Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms, Springer Verlag, Heidelberg, 1993.

[21] H. Jiang, Unconstrained Minimization approaches to nonlinear complementarities, Applied Mathematics Report AMR94/33, School of Mathematics, The University of New South Wales, Sydney, Australia, 1994.

[22] H. Jiang and L. Qi, Local uniqueness and convergence of iterative methods for nonsmooth variational inequalities, Journal of Mathematical Analysis and Applications, to appear.

[23] H. Jiang and L. Qi, A globally and superlinearly convergent trust region algorithm for convex SC^{1} minimization problems and its application to stochastic programs, Journal of Optimization Theory and Applications, to appear.

[24] H. Jiang and L. Qi, A new nonsmooth equations approach to nonlinear complementarities, SIAM Journal on Control and Optimization, to appear.

[25] S.–P. Han, J.–S. Pang and N. Rangaraj, Globally convergent Newton methods for nonsmooth equations, Mathematics of Operations Research, 17 (1992), 586–607.

[26] C. Kanzow, Some equation-based methods for the nonlinear complementarity problem, Optimization Methods and Software, 3 (1994), pp. 327–340.

[27] C. Kanzow, Global convergence properties of some iterative methods for linear complementarity problems, SIAM Journal on Optimization, to appear.

[28] M. Kojima and R. Hirabayashi, Continuous deformations of nonlinear programs, Mathematical Programming Study 21 (1984), pp. 150–198.

[29] M. Kojima and S. Shindo, Extensions of Newton and quasi-Newton methods to systems of P C^{1} equations, Journal of Operations Research Society of Japan, 29 (1986), pp. 352–374.

[30] B. Kummer, Newton’s method for non-differentiable functions, in: J. Guddat et al. (eds.), Mathematical Research, Advances in Mathematical Optimization, Akademie Verlag, Berlin, Germany, 1988, pp. 114–125.

[31] B. Kummer, Newton’s method based on generalized derivatives for nonsmooth functions: Convergence analysis, in W. Oettli, D. Pallascke (eds.): Lecture Notes in Economics and Mathematical Systems 382, Advances in Optimization, Proceedings, Lamprecht, Germany 1991, Springer–Verlag, 1992.

[32] C. Lemaréchal and C. Sagastizábal, Practical aspects of the Moreau-Yosida regularization I: Theoretical Preliminaries, SIAM Journal on Optimization, to appear.

[33] O. L. Mangasarian, Equivalence of the complementarity problem to a system of nonlinear equations, SIAM Journal on Applied Mathematics, 31 (1976), pp. 89–92.

[34] O. L. Mangasarian and M. V. Solodov, Nonlinear Complementarity as Unconstrained and Constrained Minimization, Mathematical Programming, 62 (1993), 277–297.

[35] R. Mifflin, Semismooth and semiconvex functions in constrained optimization, SIAM Journal on Control and Optimization, 15 (1977), pp. 959–972.

[36] J. J. Moré, Global methods for nonlinear complementarity problems, Preprint MCS– P429–0494, Argonne National Laboratory, Argonne, IL, USA, 1994.

[37] J.–S. Pang, Newton’s method for B–differentiable equations, Mathematics of Operations Research, 15 (1990), pp. 311–341.

[38] J.–S. Pang, A B-differentiable equation-based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems, Mathematical Programming, 51 (1991), pp. 101–131.

[39] J.–S. Pang and S. A. Gabriel, NE/SQP: A robust algorithm for the nonlinear complementarity problem, Mathematical Programming, 60 (1993), pp. 295–337.

[40] J.–S. Pang and L. Qi, Nonsmooth equations: Motivation and algorithms, SIAM Journal on Optimization, 3 (1993), pp. 443–465.

[41] V. A. Purtov, Fast convergent nonlinear programming methods, in C. Richter, C. Hollatz and D. Pallaschke (eds.): Numerical Methods of Nonlinear Programming and their Implementations, Mathematical Research 60, Akademie–Verlag, Berlin, Germany, 1991, pp. 87–98.

[42] L. Qi, Convergence analysis of some algorithms for solving nonsmooth equations, Mathematics of Operations Research, 18 (1993), pp. 227–244.

[43] L. Qi, Second-order analysis of the Moreau-Yosida approximation of a convex function, Applied Mathematics Report AMR 94/20, School of Mathematics, The University of New South Wales, Sydney, Australia, 1994.

[44] L. Qi and X. Chen, A globally convergent successive approximation method for severely nonsmooth equations, SIAM Journal on Control and Optimization, 33 (1995), pp. 402 [45] L.Qi and X. Chen, A preconditioning proximal Newton method for nondifferentiable

convex optimization, Applied Mathematics Report AMR95/20, School of Mathematics, The University of New South Wales, Sydney, Australia, 1995.

[46] L. Qi and H. Jiang, Karush–Kuhn–Tucker equations and convergence analysis of Newton methods and Quasi–Newton methods for solving these equations, Applied Mathematics Report AMR94/5, School of Mathematics, The University of New South Wales, Sydney, Australia, 1994.

[47] L. Qi and J. Sun, A nonsmooth version of Newton’s method, Mathematical Programming, 58 (1993), pp. 353–367.

[48] D. Ralph, Global convergence of damped Newton’s method for nonsmooth equations via the path search, Mathematics of Operations Research, 19 (1994), 352–389.

[49] S. M. Robinson, Mathematical foundations of nonsmooth embedding methods, Mathematical Programming, 48 (1990), pp. 221–229.

[50] S. M. Robinson, Newton’s method for a class of nonsmooth functions, Set Valued Analysis, 2 (1994), pp. 291–305.

[51] P. K. Subramanian, Gauss-Newton methods for the complementarity problem, Journal of Optimization Theory and Applications, 77 (1993), pp. 467–482.

[52] P. Tseng, Growth behaviour of a class of merit functions for the nonlinear complementarity problem, Journal of Optimization Theory and Applications, 89 (1996), to appear.

[53] P. Tseng, An infeasible path–following method for monotone complementarity problem, Technical Report, Department of Mathematics, University of Washington, Seattle, WA, USA, 1994.

[54] P. Tseng, N. Yamashita and M. Fukushima, Equivalence of complementarity problems to differentiable minimization: A unified approach, SIAM Journal on Optimization, 6 (1996), to appear.

[55] A. P. Wierzbicki, Note on the equivalence of Kuhn–Tucker complementarity conditions to an equation, Journal of Optimization Theory and Applications, 37 (1982), pp. 401– 405.

[56] N. Yamashita and M. Fukushima, On stationary points of the implicit Lagrangian for nonlinear complementarity problems, Journal of Optimization Theory and Applications, 84 (1995), pp. 653–663.