# The Levenberg-Marquardt-Type Methods for a Kind of Vertical Complementarity Problem

Authors: Shou-qiang Du; Yan Gao
Journal: Journal of Applied Mathematics
 (2011)

---

## Abstract

Two kinds of the Levenberg-Marquardt-type methods for the solution of vertical
complementarity problem are introduced. The methods are based on a nonsmooth equation
reformulation of the vertical complementarity problem for its solution. Local and
global convergence results and some remarks about the two kinds of the Levenberg-Marquardt-type methods are also given. Finally, numerical experiments are reported.


---

## Body

## 1. Introduction

In this paper, we consider the following kind of vertical complementarity problem:(1.1)Fi(x)≥0,i=1,…,m,Πi=1mFij(x)=0,j=1,…,n,
where the functions Fi(x):Rn→Rn are assumed to be continuously differentiable and Fij(x) denotes the jth component of the function Fi(x). The above vertical complementarity problem is of concrete background, for instance,  the Karush-Kuhn-Tucker system of nonlinear programs, complementarity problems, and many problems in mechanics and engineering. When m=2, (1.1) is the generalized complementarity problem, which has been considered in [1]. When x satisfied
(1.2)min⁡j∈J1{Fj1(x)}=0,⋮min⁡j∈Jn{Fjn(x)}=0,x solves (1.1), where “min” denotes the componentwise minimum operator, Fji:Rn→R, for, j∈Ji, i=1,2,…,n, are also continuously differentiable, and  Ji, for i=1,2,…,n, are finite index sets. Throughout this section, we denote (1.3)gi(x)=min⁡j∈JiFji(x),x∈Rn,i=1,2,…,n,G(x)=(g1(x),…,gn(x))T,x∈Rn,Ji={j∈Ji∣Fji(x)=gi(x)},x∈Rn,i=1,2,…,n.Thus, (1.2) can be briefly rewritten as (1.4)G(x)=(g1(x),…,gn(x))T=0,
which is nonsmooth equation. Nonsmooth equations are much more difficult than smooth equations. Solving the above equations is a classical problem of numerical analysis, see [1–11]. Many existing classical methods for smooth equations cannot be extended to nonsmooth equations directly. Those difficult motivate us to seek higher-quality methods for nonsmooth equations. One of the classical iterative methods for solving (1.4) is the Levenberg-Marquardt-type method, which is based on the generalized Jacobian. The Levenberg-Marquardt method and its variants are of particular importance also because of their locally fast convergent rates. Levenberg-Marquardt method is also a famous method for nonlinear equations, which can be regarded as a modification of Newton method [12–18]. In the smoothing-type methods, some conditions are needed to ensure that the Jacobian matrix is nonsingular; the Levenberg-Marquardt method does not need such conditions [12–19].By the above analysis, the purpose of this paper is to consider using the Levenberg-Marquardt-type methods for solving (1.1). We reformulate (1.1) as a system of nonsmooth equations and present two kinds of the Levenberg-Marquardt-type methods for solving it. The outline of the paper is as follows. In Section 2, we recall some background concepts and propositions which will play an important role in the subsequent analysis of convergence results. In Section 3, we give the two kinds of Levenberg-Marquardt-type methods and present their local and global convergence results and some remarks. Finally, numerical experiments and some final remarks about the numerical experiments are listed.Throughout this paper,Rn denotes the space of n-dimensional real column vectors and T denotes transpose. For any differentiable function f:Rn→R, ∇f(x) denotes the gradient of f at x.


## 2. Preliminaries

A locally Lipschitz functionH:Rn→Rn is said to be semismooth at x provided that the following limit (2.1)lim⁡V∈∂H(x+th′)h′→h,t→0+Vh′exists for anyh∈Rn. The class of semismooth functions is very broad; it includes smooth functions, convex functions, and piecewise smooth functions. Moreover, the sums, differences, products, and composites of semismooth functions are also semismooth. Maximum of a finite number of smooth functions are semismooth too.Proposition 2.1.
FunctionG in (1.4) is semismooth.Proposition 2.2.
The following statements are equivalent:(i)
H(x) is semismooth at x.(ii)
ForV∈∂H(x+h), h→0.(2.2)Vh-H′(x;h)=o(‖h‖).(iii)
One has(2.3)lim⁡x+h∈DH,h→0H′(x+h;h)-H′(x;h)‖h‖=0.
If for any V∈∂H(x+h), h→0,
(2.4)Vh-H′(x;h)=o(‖h‖1+p),
where 0<p≤1, then one says H(x) is p-order semismooth at x. Obviously, p-order semismoothness implies semismoothness. From [8], one knows that if H(x) is semismooth at x, then, for any h→0(2.5)H(x+h)-H(x)-H′(x;h)=o(‖h‖).In [6], Gao considered a system of equations of max-type functions, which is the system of equations of smooth compositions of max-type functions. For solving the systems of equations, Gao take ∂⋆ as a tool instead of the Clarke generalized Jacobian, B-differential, and b-differential. Based on [6], we give the following ∂⋆G(x) for G in (1.4): (2.6)∂⋆G(x)={(∇Fj11(x),…,∇Fjnn(x))T∣j1∈J1(x),…,jn∈Jn(x),x∈Rn}.
Obviously, ∂⋆G(x) is a finite set of points and can be easily calculated by determining Ji(x), i=1,…,n, and ∇Fjii(x), ji∈Ji(x), i=1,…,n. In what follows, we use (2.6) as a tool instead of the Clarke generalized Jacobian and b-differential in the Levenberg-Marquardt method (I).Proposition 2.3.
The∂⋆G(x) defined as (2.6) is nonempty and compact set for any x, and the point to set map is also upper semicontinuous.Proposition 2.4.
Suppose thatG(x) and ∂⋆G(x) are defined by (1.4) and by (2.6), and all V∈∂⋆G(x) are nonsingular. Then there exists a scalar β>0 such that
(2.7)‖V-1‖≤β,∀V∈∂⋆G(x),‖V‖≤γ,∀V∈∂⋆G(x),x∈N(x,ϵ),
holds for some constants γ>0, ϵ>0, and N(x,ϵ) is a neighbor of x.By the continuously differentiable property ofG in (1.1), the above Proposition 2.4 can be easily obtained.Definition 2.5.
One says thatG is BD-regular at x if all elements in ∂G(x) are nonsingular.Definition 2.6.
M∈Rn×n is a P0 matrix if and only if there exists an index i∈{1,2,…,n} such that xi≠0 and xi[Mx]i≥0, for all x∈Rn, x≠0.


## 3. The Levenberg-Marquardt-type Methods and Their Convergence Results

In this section, we present two kinds of the Levenberg-Marquardt-type methods for solving vertical complementarity problem (1.1). Firstly, we briefly recall some results on the Levenberg-Marquardt-type method for the solution of nonsmooth equations and their convergence results, see, for example, [7] and also [9, 10]. And we also give the new kinds of the Levenberg-Marquardt methods for solving vertical complementarity problem (1.1) and analyze their convergence results. We are now in the position to consider exact and inexact versions of the Levenberg-Marquardt-type method.Given a starting vectorx0∈Rn, let (3.1)xk+1=xk+dk,wheredk is the solution of the system (3.2)((Vk)TVk+σkI)d=-(Vk)TG(xk),Vk∈∂⋆G(xk),σk≥0.In the inexact versions of this method,dk can be given by the solution of the system (3.3)((Vk)TVk+σkI)d=-(Vk)TG(xk)+rk,Vk∈∂⋆G(xk),σk≥0,whererk is the vector of residuals, and we can assume ∥rk∥≤αk∥(Vk)TG(xk)∥ for some αk≥0.We now give a local convergence Levenberg-Marquardt-type method (I) for (1.1) as follows.


### 3.1. The Levenberg-Marquardt Method (I)

Step 1.
Givenx0, ϵ>0, λik∈Rn, 0<|λik|<+∞.Step 2.
Solve the system to getdk,
(3.4)((Vk)TVk+diag⁡(λi(k)gi(xk)))d=-(Vk)TG(xk)+rk,Vk∈∂⋆G(x),
for i=1,⋯n, and rk is the vector of residuals
(3.5)‖rk‖≤αk‖(Vk)TG(xk)‖,αk≥0.Step 3.
Setxk+1=xk+dk; if ∥G(xk)∥≤ϵ, terminate. Otherwise, let k:=k+1, and go to Step 2.Based upon the above analysis, we give the following local convergence result. Similar results have also been mentioned in [9].Theorem 3.1.
Suppose that{xk} is a sequence generated by the above method and there exist constants a>0, αk≤a for all k, and there exist constant M>0, ∥diag(λi(k)gi(x))∥≤M<+∞. Let x⋆ be a BD-regular solution of G(x)=0. Then the sequence {xk}  converge Q-linearly to x⋆ for ∥x0-x⋆∥≤ϵ.Theorem 3.2.
Suppose that{xk} is a sequence generated by the above method and there exist constants a>0, αk≤a for all k. ∥rk∥≤αk∥G(xk)∥, αk≥0. And suppose that there exist constants M>0, ∥diag(λi(k)gi(x))∥≤M<+∞. Then the sequence {xk} converge Q-linearly to x⋆ for ∥x0-x⋆∥≤ϵ.By Propositions2.2, 2.3, and 2.4, we can get the proof of Theorem 3.2 similarly to [9, Theorem 3.1], so we omit it.Remark 3.3.
Theorems3.1 and 3.2 hold with ∥rk∥=0.Remark 3.4.
In the Levenberg-Marquardt method (I), ifdk is computed by (3.3), Theorems 3.1, 3.2, and Remark 3.3 can also be obtained.Whenm=2 in (1.1), the vertical complementarity problem reduces to the well-known generalized complementarity problem(GCP) in [1]. The GCP is to find x⋆∈Rn satisfying (3.6)F1(x)≥0,F2≥0,F1(x)TF2(x)=0,whereFi:Rn→Rn, i=1,2 and are continuously differentiable functions. If F1(x)=x, then the generalized complementarity problem (GCP) is the nonlinear complementarity problem (NCP). In the following, we give the Levenberg-Marquardt-type method (II) for the generalized complementarity problem  (GCP). The different merit function is based on the well-known F-B function(3.7)φ(a,b)=a2+b2-a-b.ThenG(x)=φ(F1,F2), and we denote the corresponding merit function as (3.8)Ψ(x)=12‖G(x)‖2,whereΨ is a continuously differentiable function. Now, we give the following Levenberg-Marquardt-type method (II).


### 3.2. The Levenberg-Marquardt Method (II)

Step 1.
Given a staring vectorx0∈Rn, ρ>0, p>2, β∈(0,1/2), ϵ≥0, λik∈Rn, 0<|λik|<+∞.Step 2.
IfΨ(xk)≤ϵ, stop.Step 3.
Select an elementVk∈∂G(xk), and find an approximate solution dk∈Rn of the system
(3.9)((Vk)TVk+diag⁡(λi(k)gi(xk)))d=-(Vk)TG(xk),Vk∈∂G(x),
where λi(k) are the Levenberg-Marquardt parameters. If the condition
(3.10)∇Ψ(xk)Tdk≤-ρ‖dk‖p
is not satisfied, set dk=-(Vk)TG(xk).Step 4.
Find the smallestik∈{0,1,2,⋯} such that
(3.11)Ψ(xk+2-ikdk)≤Ψ(xk)+β2-ik∇Ψ(xk)Tdk.
Set xk+1=xk+2-ikdk, let k:=k+1, and go to  Step 2.Notice that ifVk is nonsingular in (3.9), the choice of λik=0, at each step, is allowed by the above algorithm. Then (3.9) is equivalent to the generalized Newton equation in [4]. In what follows, as usual in analyzing the behavior of algorithms, we also assume that the above Levenberg-Marquardt method (II) produces an infinite sequence of points. Based upon the above analysis, we can get the following global convergence results about vertical complementarity problem (1.1). The main proof of the following theorem is similar to [7, Theorem 12]. But the system (3.9), which is used for the solution of dk, is different from [7, Theorem 12].Theorem 3.5.
Suppose that there exist constantsM>0, ∥diag(λi(k)gi(x))∥≤M<+∞. Then each accumulation point of the sequence {xk} generated by the above Levenberg-Marquardt method (II) is a stationary point of Ψ.Proof.
Assume that{xk}K→x⋆. If there are infinitely many k∈K such that dk=-∇Ψ(xk), then the assertion follows immediately from [5, Proposition 1.16]. Hence we can assume without loss of generality that if {xk}K is a convergent subsequence of {xk}, then dk is always given by (3.9). We show that for every convergent subsequence {xk}K for which
(3.12)lim⁡k∈K,k→∞∇Ψ(xk)≠0,
there   holds
(3.13)limsup⁡k∈K,k→∞‖dk‖<∞,limsup⁡k∈K,k→∞|∇Ψ(xk)Tdk|>0
In the following, we assume that xk→x⋆. Suppose that x⋆ is not a stationary point of Ψ. By (3.9), we have
(3.14)‖∇Ψ(xk)‖=‖((Vk)TVk+diag⁡(λi(k)gi(xk)))dk‖≤‖(Vk)TVk+diag⁡(λi(k)gi(xk))‖‖dk‖,
so
(3.15)‖dk‖≥‖∇Ψ(xk)‖‖(Vk)TVk+diag⁡(λi(k)gi(xk))‖.
Note that the denominator in the above inequality is nonzero; otherwise by (3.14), we have ∥∇Ψ(xk)∥=0. xk would be a stationary point and the algorithm would have stopped. By assumption ∥diag(λi(k)gi(x))∥≤M<+∞ and Proposition 2.4, there exists a constant k1>0 such that
(3.16)‖(Vk)TVk+diag⁡(λi(k)gi(xk))‖≤k1.
From the above inequality and (3.13), we get
(3.17)‖dk‖≥1-αkk1‖∇Ψ(xk)‖≥1-ak1‖∇Ψ(xk)‖.
Formula (3.13) now readily follows from the fact that we are assuming that the direction satisfies (3.10) with p>2, while the gradient ∇Ψ(xk) is bounded on the convergent sequence {xk}. If (12) is not satisfied, there exists a subsequence {xk}K′ of {xk}K(3.18)lim⁡k∈K′,k→∞|∇Ψ(xk)Tdk|=0.
This implies, by (3.10), that limk∈K′,k→∞∥dk∥=0. Together with (3.17) one implies
(3.19)lim⁡k∈K′,k→∞‖∇Ψ(xk)‖=0
contradicting (3.12). The sequence {dk} is uniformly gradient related to {xk} according to the definition given in [5], and the assertion of the theorem also follows from [5, Proposition 1.16]. We completed the proof.Remark 3.6.
In the Levenberg-Marquardt method (II), (3.11) can be replaced by the following nonmonotone line search:
(3.20)Ψ(xk+2-ikdk)-max⁡0≤j≤m(k)Ψ(xk-j)≤β2-ik∇Ψ(xk)Tdk,
where m(0)=0, m(k)=min{m(k-1)+1,M0}, and M0 is a nonnegative integer.Remark 3.7.
Let the assumptions of Theorem3.5 hold. Equation (3.9) is replaced by (3.3). Then each accumulation point of the sequence {xk} generated by the above Levenberg-Marquardt method (II) is a stationary point of Ψ.Remark 3.8.
The assumption that there exist constantsM>0, ∥diag(λi(k)gi(x))∥≤M<+∞ in Theorems 3.1, 3.5, and Remark 3.7 can be easily obtained, for the continuously differentiable of F in (1.1).Remark 3.9.
Letx⋆ be a stationary point of Ψ, F2′(x⋆) nonsingular, and F1′(x⋆)F2′(x⋆)-1 a P0 matrix. Then x⋆ is a solution of GCP(F1,F2).Remark 3.10.
We can useφMS in [20] to construct merit function Ψ in the Levenberg-Marquardt method (II).Remark 3.11.
We can use a family of new NCP functions based on the Fischer-Burmeister function to construct merit function in the Levenberg-Marquardt method (II), which is defined by(3.21)ϕp(a,b)=‖(a,b)‖p-(a+b),
where p is any fixed real number in the interval (1,+∞) and ∥(a,b)∥p denotes the p-norm of (a,b). Numerical results based on the function ϕp for the test problems from MCPLIB indicated that the algorithm has better performance in practice [21].


## 3.1. The Levenberg-Marquardt Method (I)

Step 1.
Givenx0, ϵ>0, λik∈Rn, 0<|λik|<+∞.Step 2.
Solve the system to getdk,
(3.4)((Vk)TVk+diag⁡(λi(k)gi(xk)))d=-(Vk)TG(xk)+rk,Vk∈∂⋆G(x),
for i=1,⋯n, and rk is the vector of residuals
(3.5)‖rk‖≤αk‖(Vk)TG(xk)‖,αk≥0.Step 3.
Setxk+1=xk+dk; if ∥G(xk)∥≤ϵ, terminate. Otherwise, let k:=k+1, and go to Step 2.Based upon the above analysis, we give the following local convergence result. Similar results have also been mentioned in [9].Theorem 3.1.
Suppose that{xk} is a sequence generated by the above method and there exist constants a>0, αk≤a for all k, and there exist constant M>0, ∥diag(λi(k)gi(x))∥≤M<+∞. Let x⋆ be a BD-regular solution of G(x)=0. Then the sequence {xk}  converge Q-linearly to x⋆ for ∥x0-x⋆∥≤ϵ.Theorem 3.2.
Suppose that{xk} is a sequence generated by the above method and there exist constants a>0, αk≤a for all k. ∥rk∥≤αk∥G(xk)∥, αk≥0. And suppose that there exist constants M>0, ∥diag(λi(k)gi(x))∥≤M<+∞. Then the sequence {xk} converge Q-linearly to x⋆ for ∥x0-x⋆∥≤ϵ.By Propositions2.2, 2.3, and 2.4, we can get the proof of Theorem 3.2 similarly to [9, Theorem 3.1], so we omit it.Remark 3.3.
Theorems3.1 and 3.2 hold with ∥rk∥=0.Remark 3.4.
In the Levenberg-Marquardt method (I), ifdk is computed by (3.3), Theorems 3.1, 3.2, and Remark 3.3 can also be obtained.Whenm=2 in (1.1), the vertical complementarity problem reduces to the well-known generalized complementarity problem(GCP) in [1]. The GCP is to find x⋆∈Rn satisfying (3.6)F1(x)≥0,F2≥0,F1(x)TF2(x)=0,whereFi:Rn→Rn, i=1,2 and are continuously differentiable functions. If F1(x)=x, then the generalized complementarity problem (GCP) is the nonlinear complementarity problem (NCP). In the following, we give the Levenberg-Marquardt-type method (II) for the generalized complementarity problem  (GCP). The different merit function is based on the well-known F-B function(3.7)φ(a,b)=a2+b2-a-b.ThenG(x)=φ(F1,F2), and we denote the corresponding merit function as (3.8)Ψ(x)=12‖G(x)‖2,whereΨ is a continuously differentiable function. Now, we give the following Levenberg-Marquardt-type method (II).


## 3.2. The Levenberg-Marquardt Method (II)

Step 1.
Given a staring vectorx0∈Rn, ρ>0, p>2, β∈(0,1/2), ϵ≥0, λik∈Rn, 0<|λik|<+∞.Step 2.
IfΨ(xk)≤ϵ, stop.Step 3.
Select an elementVk∈∂G(xk), and find an approximate solution dk∈Rn of the system
(3.9)((Vk)TVk+diag⁡(λi(k)gi(xk)))d=-(Vk)TG(xk),Vk∈∂G(x),
where λi(k) are the Levenberg-Marquardt parameters. If the condition
(3.10)∇Ψ(xk)Tdk≤-ρ‖dk‖p
is not satisfied, set dk=-(Vk)TG(xk).Step 4.
Find the smallestik∈{0,1,2,⋯} such that
(3.11)Ψ(xk+2-ikdk)≤Ψ(xk)+β2-ik∇Ψ(xk)Tdk.
Set xk+1=xk+2-ikdk, let k:=k+1, and go to  Step 2.Notice that ifVk is nonsingular in (3.9), the choice of λik=0, at each step, is allowed by the above algorithm. Then (3.9) is equivalent to the generalized Newton equation in [4]. In what follows, as usual in analyzing the behavior of algorithms, we also assume that the above Levenberg-Marquardt method (II) produces an infinite sequence of points. Based upon the above analysis, we can get the following global convergence results about vertical complementarity problem (1.1). The main proof of the following theorem is similar to [7, Theorem 12]. But the system (3.9), which is used for the solution of dk, is different from [7, Theorem 12].Theorem 3.5.
Suppose that there exist constantsM>0, ∥diag(λi(k)gi(x))∥≤M<+∞. Then each accumulation point of the sequence {xk} generated by the above Levenberg-Marquardt method (II) is a stationary point of Ψ.Proof.
Assume that{xk}K→x⋆. If there are infinitely many k∈K such that dk=-∇Ψ(xk), then the assertion follows immediately from [5, Proposition 1.16]. Hence we can assume without loss of generality that if {xk}K is a convergent subsequence of {xk}, then dk is always given by (3.9). We show that for every convergent subsequence {xk}K for which
(3.12)lim⁡k∈K,k→∞∇Ψ(xk)≠0,
there   holds
(3.13)limsup⁡k∈K,k→∞‖dk‖<∞,limsup⁡k∈K,k→∞|∇Ψ(xk)Tdk|>0
In the following, we assume that xk→x⋆. Suppose that x⋆ is not a stationary point of Ψ. By (3.9), we have
(3.14)‖∇Ψ(xk)‖=‖((Vk)TVk+diag⁡(λi(k)gi(xk)))dk‖≤‖(Vk)TVk+diag⁡(λi(k)gi(xk))‖‖dk‖,
so
(3.15)‖dk‖≥‖∇Ψ(xk)‖‖(Vk)TVk+diag⁡(λi(k)gi(xk))‖.
Note that the denominator in the above inequality is nonzero; otherwise by (3.14), we have ∥∇Ψ(xk)∥=0. xk would be a stationary point and the algorithm would have stopped. By assumption ∥diag(λi(k)gi(x))∥≤M<+∞ and Proposition 2.4, there exists a constant k1>0 such that
(3.16)‖(Vk)TVk+diag⁡(λi(k)gi(xk))‖≤k1.
From the above inequality and (3.13), we get
(3.17)‖dk‖≥1-αkk1‖∇Ψ(xk)‖≥1-ak1‖∇Ψ(xk)‖.
Formula (3.13) now readily follows from the fact that we are assuming that the direction satisfies (3.10) with p>2, while the gradient ∇Ψ(xk) is bounded on the convergent sequence {xk}. If (12) is not satisfied, there exists a subsequence {xk}K′ of {xk}K(3.18)lim⁡k∈K′,k→∞|∇Ψ(xk)Tdk|=0.
This implies, by (3.10), that limk∈K′,k→∞∥dk∥=0. Together with (3.17) one implies
(3.19)lim⁡k∈K′,k→∞‖∇Ψ(xk)‖=0
contradicting (3.12). The sequence {dk} is uniformly gradient related to {xk} according to the definition given in [5], and the assertion of the theorem also follows from [5, Proposition 1.16]. We completed the proof.Remark 3.6.
In the Levenberg-Marquardt method (II), (3.11) can be replaced by the following nonmonotone line search:
(3.20)Ψ(xk+2-ikdk)-max⁡0≤j≤m(k)Ψ(xk-j)≤β2-ik∇Ψ(xk)Tdk,
where m(0)=0, m(k)=min{m(k-1)+1,M0}, and M0 is a nonnegative integer.Remark 3.7.
Let the assumptions of Theorem3.5 hold. Equation (3.9) is replaced by (3.3). Then each accumulation point of the sequence {xk} generated by the above Levenberg-Marquardt method (II) is a stationary point of Ψ.Remark 3.8.
The assumption that there exist constantsM>0, ∥diag(λi(k)gi(x))∥≤M<+∞ in Theorems 3.1, 3.5, and Remark 3.7 can be easily obtained, for the continuously differentiable of F in (1.1).Remark 3.9.
Letx⋆ be a stationary point of Ψ, F2′(x⋆) nonsingular, and F1′(x⋆)F2′(x⋆)-1 a P0 matrix. Then x⋆ is a solution of GCP(F1,F2).Remark 3.10.
We can useφMS in [20] to construct merit function Ψ in the Levenberg-Marquardt method (II).Remark 3.11.
We can use a family of new NCP functions based on the Fischer-Burmeister function to construct merit function in the Levenberg-Marquardt method (II), which is defined by(3.21)ϕp(a,b)=‖(a,b)‖p-(a+b),
where p is any fixed real number in the interval (1,+∞) and ∥(a,b)∥p denotes the p-norm of (a,b). Numerical results based on the function ϕp for the test problems from MCPLIB indicated that the algorithm has better performance in practice [21].


## 4. Numerical Tests and Final Remarks

In this section, in order to show the performance of the above Levenberg-Marquardt type methods, we present some numerical results for the Levenberg-Marquardt method (I) and the Levenberg-Marquardt method (II). The results indicate that the Levenberg-Marquardt algorithms work quite well in practice. We coded the algorithms in Matlab 7.0. Some remarks are also attached.Example 4.1.
We consider the following vertical complementarity problem:(4.1)Fi(x)≥0,i=1,…,m,Πi=1mFij(x)=0,j=1,…,n,
where the functions
(4.2)F1(x1,x2)=(x12,x12+x22)T,F2(x1,x2)=(2x12+6,12x12)T.
Both F1 and F2 are R2→R2 continuously differentiable functions.We use the Levenberg-Marquardt method (I) to compute Example4.1. Results for Example 4.1 with initial point x0=(0.1,0.7)T, αk≡1 and λ1=0.01, λ2=0.01 are presented in Table 1.Table 1StepxkG(x)1(0.1000000,0.7000000)T(0.0100000,0.0050000)T2(0.0500998,0.7000000)T(0.0025099,0.0012549)T3(0.0250999,0.7000000)T1.0e-003*(0.630004,0.315002)T4(0.0125749,0.7000000)T1.0e-003*(0.158130,0.079065)T5(0.0063000,0.7000000)T1.0e-004*(0.396906,0.198453)T6(0.0031563,0.7000000)T1.0e-005*(0.996230,0.498115)T7(0.0015813,0.7000000)T1.0e-005*(0.250052,0.125026)T8(0.0007922,0.7000000)T1.0e-006*(0.627630,0.313815)T9(0.0003969,0.7000000)T1.0e-006*(0.157534,0.078767)T10(0.0001988,0.7000000)T1.0e-007*(0.395410,0.197705)T11(0.0000996,0.7000000)T1.0e-008*(0.992475,0.496237)TWe use the Levenberg-Marquardt method (I) to compute Example4.1. Results for Example 4.1 with initial point x0=(10,10)T, and x0=(100,100)T, αk≡1 and λ1=0.01, λ2=0.01 are presented in Table 2.Table 2StepxkG(x)x0=(10,10)T1(10.000000,10.0000000)T(100.000000,25.000000)T2(5.009980,10.0000000)T(25.099900,12.549950)T3(2.509990,10.0000000)T(6.300049;3.150024)T4(1.257499,10.0000000)T(1.581306,0.7906530)T5(0.630004;10.0000000)T(0.396906,0.198453)T6(0.315631,10.0000000)T(0.099623,0.049811)T7(0.158130,10.0000000)T(0.025005,0.012502)T8(0.079223,10.0000000)T(0.006276,0.003138)T9(0.039690,10.0000000)T(0.001575,0.000787)T10(0.019884,10.0000000)T1.0e-003*(0.395410,0.197705)T11(0.009962,10.0000000)T1.0e-004*(0.992475,0.496237)T12(0.004991,10.0000000)T1.0e-004*(0.249110,0.124555)T13(0.002500,10.0000000)T1.0e-005*(0.625264,0.312632)T14(0.001252,10.0000000)T1.0e-005*(0.156940,0.078470)T15(0.000627,10.0000000)T1.0e-006*(0.393919,0.196959)T16(0.000314,10.0000000)T1.0e-007*(0.988734,0.494367)T17(0.000157,10.0000000)T1.0e-007*(0.248171,0.124085)T18(0.0000789,10.0000000)T1.0e-008*(0.6229079,0.3114539)Tx0=(100,100)T211.0e+002*(0.0000009,1.0000000)T1.0e-008*(0.985008,0.492504)TWhen we  computedk by (3.3) in the Levenberg-Marquardt method (I) to compute Example 4.1. Results for Example 4.1 with initial point x0=(0.1,0.7)T, x0=(10,10)T, and x0=(100,100)T, αk≡1 and λ1=0.01, λ2=0.01 are presented in Table 3.Table 3StepxkG(x)x0=(0.1,0.7)T40(0.007326,0.700000)T1.0e-004*(0.536774,0.268387)Tx0=(10,10)T47(0.007301,10.000000)T1.0e-004*(0.533144,0.266572)Tx0=(100,100)T501.0e+002*(0.000073,1.000000)T1.0e-004*(0.537728,0.268864)TRemark 4.2.
From the numerical results for the Levenberg-Marquardt method (I) in Table1, Table 2, and Table 3, we can see that the modification of (3.4) in the Levenberg-Marquardt method (I) works quite better in practice than (3.3) which has been used in [7].Example 4.3.
We consider the following vertical complementarity problem:(4.3)Fi(x)≥0,i=1,…,m,Πi=1mFij(x)=0,j=1,…,n,
where the functions
(4.4)F1(x1,x2)=(x12+x22,x22)T,F2(x1,x2)=(x12,x12+12x22+1)T.
Both F1 and F2 are R2→R2 continuously differentiable functions.
Now, we use the Levenberg-Marquardt method (II) to compute Example4.3. For the special construction of Example 4.3, we can use (2.6) to get the Clarke generalized Jacobian in the Levenberg-Marquardt method (II). Results for Example 4.3 with initial point x0=(1,1)T, x0=(10,0.1)T, and x0=(100,10)T and λ1=0.01, λ2=1 are presented in Table 4.Table 4StepxkG(x)x0=(1,1)T3(-0.001250,1.000000)T1.0e-005*(0.156444,0.156444)Tx0=(10,0.1)T15(0.099976,0.100000)T(0.009995,0.009995)Tx0=(100,10)T17(0.096868,10.000000)T(0.009383,0.009383)TThen we computedk by (3.3) in the Levenberg-Marquardt method (II) to compute Example 4.3. Results for Example 4.3 with initial point x0=(1,1)T, x0=(10,0.1)T, and x0=(100,10)T and λ1=0.01, λ2=1 are presented in Table 5.Table 5StepxkG(x)x0=(1,1)T3(-0.001250,1.000000)T1.0e-005*(0.156444,0.156444)Tx0=(10,0.1)T15(0.099989,0.100000)T(0.009997,0.009997)Tx0=(100,10)T17(0.097467,10.000000)T(0.009499,0.009499)TRemark 4.4.
From the numerical results for in the Levenberg-Marquardt method (II) in Table4 and Table 5, we can see that the modification of (3.9) in the Levenberg-Marquardt method (II) works quite as well as (3.3) which has been used in [7].



---

*Source: 161853-2011-12-01.xml*