# A Modified Levenberg-Marquardt Method

Authors: Shou-qiang Du; Yan Gao
Journal: Mathematical Problems in Engineering
 (2008)

---

## Abstract

For solving nonsmooth systems of equations, the Levenberg-Marquardt method
and its variants are of particular importance because of their locally fast convergent rates.
Finitely many maximum functions systems are very useful in the study of nonlinear complementarity
problems, variational inequality problems, Karush-Kuhn-Tucker systems of
nonlinear programming problems, and many problems in mechanics and engineering. In this
paper, we present a modified Levenberg-Marquardt method for nonsmooth equations with
finitely many maximum functions. Under mild assumptions, the present method is shown
to be convergent Q-linearly. Some numerical results comparing the proposed method with
classical reformulations indicate that the modified Levenberg-Marquardt algorithm works
quite well in practice.


---

## Body

## 1. Introduction

In the past few years, there has been a growing
interest in the study of nonlinear equations (see, e.g., [1, 2]) and nonsmooth
equations, which have been proposed in the study of the nonlinear
complementarity problem, the variational inequality problem, equilibrium
problem and engineering mechanics (see, e.g., [3–10]).Finitely many
maximum functions systems are very useful in the study of nonlinear
complementarity problems, variational inequality problems, Karush-Kuhn-Tucker
systems of nonlinear programming problems, and many problems in mechanics and
engineering. In the present paper, we study a new method for nonsmooth
equations with finitely many maximum functions system proposed in [11] (1.1)maxj∈J1f1j(x)=0,⋮maxj∈Jnfnj(x)=0, where fij:Rn→R for j∈Ji,i=1,…,n are continuously differentiable, Ji for i=1,…,n are finite index sets. Denote (1.2)H(x)=(f1(x),…,fn(x))T,x∈Rn,where(1.3)fi(x)=maxj∈Jifij(x),x∈Rn,i=1,…,n,Ji(x)={ji∈N∣fij(x)=fi(x)},x∈Rn,i=1,…,n.
Then (1.1) can be rewritten as
follows:(1.4)H(x)=0,where F:Rn→Rn is a nonsmooth function. By using the
following subdifferential for the function H(x) given in (1.2),(1.5)∂⋆H(x)={(∇f1j1,…,∇fnjn)T∣j1∈J1(x),…,jn∈Jn(x)},x∈Rn,Gao gave Newton method for (1.4)
with the superlinear convergence in [11].Based on [5, 11], we present a modification of the Levenberg-Marquardt method for
solving nonsmooth equations. In Section 2, we recall some results of
generalized Jacobian and semismoothness. In Section 3, we give the
Levenberg-Marquardt method which has been
proposed in [5] and the new modified Levenberg-Marquardt method for the system
of nonsmooth equations with finitely many maximum functions. The convergence of
the modified Levenberg-Marquardt algorithm is also given. In Section 4, some
numerical tests comparing the proposed modified Levenberg-Marquardt algorithm
with the original method show that our algorithm works quite well.


## 2. Preliminaries

We start with some notions and propositions, which can
be found in [8–11].LetF(x) be locally Lipschitzian. Then, F(x) is almost everywhere F-differentiable. Let the
set of points where F(x) is F-differentiable be denoted by DF.
Then for x∈Rn,(2.1)∂BF(x)={V∈Rn×n∣∃{xk}∈DF,xk→x,F′(xk)→V}.The general Jacobian of F(x):Rn→Rn at x in the sense of Clarke is defined as(2.2)∂F(x)=conv∂BF(x).Proposition 2.1.
∂BF(x) is a nonempty and compact set for any x; the point to set B-subdifferential map is
upper semicontinuous.Proposition 2.2.
∂⋆H(x) is a nonempty and compact set for any x and upper semicontinuous.Proof.
From the fact that∂⋆H(x) is a finite set of points in Rn×n and can be calculated by determining the index
sets Ji(x),i=1,…,n and evaluating the gradients ∇fiji(x), ji∈Ji(x),i=1,…,n.Definition 2.3.
F(x) is semismooth at x if F(x) is locally Lipschitz at x and(2.3)limV∈∂F(x+th′)h′→h,t↓0Vh′exists for all h∈Rn.
If F(x) is semismooth at x,   one knows Vh−F′(x;h)=o(∥h∥),∀V∈∂F(x+h),h→0.
If for  all V∈∂F(x+h),h→0, Vh−F′(x;h)=o(∥h∥2),
one calls the function F(x) is strongly semismooth at x.Proposition 2.4.
(I) IfF(x):Rn→Rn is locally Lipschitz continuous and semismooth
at x,
then(2.4)limV∈∂F(x+th)h→0∥F(x+h)−F(x)−Vh∥∥h∥=0.
(II) IfF(x):Rn→Rn is locally Lipschitz continuous, strongly
semismooth at x, and directionally differentiable in a
neighborhood of x, then(2.5)limsupV∈∂F(x+th)h→0∥F(x+h)−F(x)−Vh∥∥h∥2<∞.Lemma 2.5.
Equation of maximum
functions (1.4) is a system of semismooth equations.In the study of algorithms for the local
solution of semismooth systems of equations, similar to [11], one also has the
following lemmas.Lemma 2.6.
Suppose thatH(x) and ∂⋆H(x) are defined by (1.4) and by (1.5), respectively,
and all V∈∂⋆H(x) are nonsingular. Then there exists a constant c such that(2.6)∥V−1∥≤c,∀V∈∂⋆H(x).The proof is similar to [11, Lemma 2.1], from the fact that ∂⋆H(x) is a finite set of points.Lemma 2.7.
Suppose thatx⋆ is a solution of (1.1), then(2.7)∥diag(λi(k)fi(xk))∥≤M,for all x in some neighborhood of x⋆ and λi(k)∈R and 0<|λi(k)|<+∞ for i=1,…,n, k=0,1,2,….Since eachfij of (1.1) is continuous, one gets the lemma
immediately.


## 3. Modified Levenberg-Marquardt Method and Its Convergence

In this section, we briefly recall some results on the
Levenberg-Marquardt-type method for the solution of nonsmooth equations and
their local convergence (see, e.g., [5, 9]). We also give the modified
Levenberg-Marquardt method and analyze its local behavior. Now we consider
exact and inexact versions of Levenberg-Marquardt method.Given a
starting vectorx0∈Rn,
let(3.1)xk+1=xk+dk,where dk is the solution of the system(3.2)((Vk)TVk+σkI)d=−(Vk)TH(xk),Vk∈∂BH(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)TH(xk)+rk,Vk∈∂BH(xk),σk≥0,where rk is the vector of residuals and we can assume ∥rk∥≤αk∥(Vk)TH(xk)∥ for some αk≥0.We now give the
modified Levenberg-Marquardt method for (1.1) as follows.Modified Levenberg-Marquardt Method
Step 1.
Givenx0, ϵ>0,λik∈Rn,0<|λik|<+∞.
Step 2.
Solve the system to getdk,(3.4)((Vk)TVk+diag(λi(k)fi(xk)))dk=−(Vk)TH(xk)+rk,Vk∈∂⋆H(x),for i=1,…,n and rk is the vector of residuals(3.5)∥rk∥≤αk∥(Vk)TH(xk)∥,αk≥0.
Step 3.
Setxk+1=xk+dk,
if ∥H(xk)∥≤ϵ,
terminate. Otherwise, let k:=k+1,
and go to Step 2.
Based upon the above analysis, we give the
following local convergence result.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.
Let x⋆ be a solution of H(x)=0,
and let all V∈∂⋆H(x⋆)   be nonsingular.
Then the sequence {xk}
converges
Q-linearly to x⋆ for ∥x0−x⋆∥≤ϵ.
Proof.
By Lemma2.6 and the continuously
differentiable of fi(x),
there is a constant C>0 such that for all xk sufficiently close to x⋆(Vk)TVk+diag(λi(k)fi(xk)) are nonsingular with(3.6)∥[(Vk)TVk+diag(λi(k)fi(xk))]−1∥≤C.Furthermore, by Proposition 2.4,
there exists δ>0,
which can be taken arbitrarily small, such that(3.7)∥H(xk)−H(x⋆)−Vk(xk−x⋆)∥≤δ∥xk−x⋆∥for all xk in a sufficiently small neighborhood of x⋆ depending on δ.
By Proposition 2.2 the upper semicontinuity of the ∂⋆H(x),
we also know(3.8)∥(Vk)T∥≤c1,for all Vk∈∂⋆H(x) and all xk sufficiently close to x⋆,
with c1>0 being a suitable constant. From the locally
Lipschitz continuous of H(x),
we have(3.9)∥(Vk)TH(xk)∥≤∥(Vk)T∥∥H(xk)−H(x⋆)∥≤c1L∥xk−x⋆∥,for all xk in a sufficiently small neighborhood of x⋆ and a constant L>0.
From (3.4), we also know(3.10)[(Vk)TVk+diag(λi(k)fi(xk))](xk+1−x⋆)=[(Vk)TVk+diag(λi(k)fi(xk))](xk−x⋆)−(Vk)TH(xk)+rk=(Vk)T[H(x⋆)−H(xk)+Vk(xk−x⋆)]+diag(λi(k)fi(xk))(xk−x⋆)+rk.Multiply the above equation by [(Vk)TVk+diag(λi(k)fi(xk))]−1 and taken into account
Lemma 2.7, and (3.6), (3.7), (3.8), and
(3.9), we
get(3.11)∥xk+1−x⋆∥≤C(∥(Vk)T∥∥H(xk)−H(x⋆)−Vk(xk−x⋆)∥+∥diag(λi(k)fi(xk))∥∥xk−x⋆∥+a∥(Vk)TH(xk)∥)≤C(c1δ∥xk−x⋆∥+M∥xk−x⋆∥+ac1L∥xk−x⋆∥)=C(c1δ+M+ac1L)∥xk−x⋆∥.Let τ=C(c1δ+M+ac1L),
so(3.12)∥xk+1−x⋆∥≤τ∥xk−x⋆∥.Since δ can be chosen arbitrarily small, by taking xk sufficiently close to x⋆,
there exist M>0 and a>0 such that τ<1,
so that the Q-linear convergence of {xk} to x⋆ follows by taking ∥x0−x⋆∥≤ϵ for a small enough ϵ>0.
Thus we complete the proof of the theorem.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∥H(xk)∥,αk≥0. Then the sequence {xk}  converges
Q-linearly to x⋆ for ∥x0−x⋆∥≤ϵ.The proof is similar to that of Theorem3.1, so we omit it.Following the proof of Theorem3.1, the following
statement holds.Remark 3.3.
Theorems3.1 and 3.2 hold with ∥rk∥=0 in (3.4).


## 4. Numerical Test

In order to show the performance of the modified
Levenberg-Marquardt method, in this section, we present numerical results and
compare the Levenberg-Marquardt method and modified Levenberg-Marquardt method.
The results indicate that the modified Levenberg-Marquardt algorithm works
quite well in practice. All the experiments were implemented in Matlab 7.0.Example 4.1.
(4.1)max{f11(x1,x2),f12(x1,x2)}=0,max{f21(x1,x2),f22(x1,x2)}=0, where(4.2)f11=15x12,f12=x12,f21=13x12,f22=x12.From (1.1), we know(4.3)H(x)=(f1(x),f2(x))T,where f1(x)=x12,f2(x)=x12,x∈R2.Our subroutine
computesdk such that (3.3) and (3.4) hold with αk=0.
We also use the condition ∥xk−xk−1∥≤10−4 as the stopping criterion. We can see that our
method is good for Example 4.1.Results for Example4.1 with initial point x0=(1,1)Tλ1=0.01,λ2=1 and computes dk by (3.4) are listed in Table 1.Table 1
x0=(1,1)Tλ1=0.01,λ2=1 and computes dk by (3.4).
Step(x1,x2)TF(x)1(1.0000,1.0000)T(1.0000,1.0000)T2(0.5006,1.0000)T(0.2506,0.2506)T3(0.2506,1.0000)T(0.0628,0.0628)T4(0.1255,1.0000)T(0.0157,0.0157)T5(0.0628,1.0000)T(0.0039,0.0039)T6(0.0314,1.0000)T1.0e−003*(0.9888,0.9888)T7(0.0157,1.0000)T1.0e−003*(0.2478,0.2478)T8(0.0079,1.0000)T1.0e−004*(0.6211,0.6211)T9(0.0039,1.0000)T1.0e−004*(0.1557,0.1557)T10(0.0019,1.0000)T1.0e−005*(0.3901,0.3901)T11(0.00098,1.0000)T1.0e−006*(0.97777,0.97777)T12(0.000495,1.0000)T1.0e−006*(0.24505,0.24505)T13(0.00024,1.0000)T1.0e−007*(0.61416,0.61416)T14(0.00012,1.0000)T1.0e−007*(0.15392,0.15392)T15(0.000062,1.0000)T1.0e−008*(0.38577,0.38577)TResults for Example4.1 with initial point x0=(1,1)Tσ1=λ1=0.01,σ2=λ2=1 and computes dk by (3.3) are listed in Tables 2 and  3.Table 2
x0=(1,1)Tσ1=0.01,σ2=1 and computes dk by (3.3).
Step(x1,x2)TF(x)1(1.0000,1.0000)T(1.0000,1.0000)T2(0.5006,1.0000)T(0.2506,0.2506)T3(0.2516,1.0000)T(0.0633,0.0633)T4(0.1282,1.0000)T(0.0164,0.0164)T5(0.0686,1.0000)T(0.0047,0.0047)T6(0.0415,1.0000)T(0.0017,0.0017)T7(0.0295,1.0000)T1.0e−003*(0.8693,0.8693)T8(0.0234,1.0000)T1.0e−003*(0.5493,0.5493)T9(0.0199,1.0000)T1.0e−003*(0.3944,0.3944)T10(0.0175,1.0000)T1.0e−003*(0.3055,0.3055)T11(0.0158,1.0000)T1.0e−003*(0.2484,0.2484)T12(0.0145,1.0000)T1.0e−003*(0.2089,0.2089)T13(0.0134,1.0000)T1.0e−003*(0.1801,0.1801)T14(0.0126,1.0000)T1.0e−003*(0.1581,0.1581)T15(0.0119,1.0000)T1.0e−003*(0.1409,0.1409)T16(0.0112,1.0000)T1.0e−003*(0.12696,0.12696)T17(0.0107,1.0000)T1.0e−003*(0.1155,0.1155)T18(0.0103,1.0000)T1.0e−003*(0.10596,0.10596)TTable 3
x0=(1,1)Tσ1=0.01,σ2=1 and computes dk by (3.3).
Step(x1,x2)TF(x)19(0.00989,1.0000)T1.0e−004*(0.9784,0.9784)T20(0.0095,1.0000)T1.0e−004*(0.9087,0.9087)T21(0.0092,1.0000)T1.0e−004*(0.8481,0.8481)T22(0.0089,1.0000)T1.0e−004*(0.7951,0.7951)T23(0.0087,1.0000)T1.0e−004*(0.7483,0.7483)T24(0.0084,1.0000)T1.0e−004*(0.7066,0.7066)T25(0.0082,1.0000)T1.0e−004*(0.6693,0.6693)T26(0.00797,1.0000)T1.0e−004*(0.6357,0.6357)T27(0.0078,1.0000)T1.0e−004*(0.6053,0.6053)T28(0.0076,1.0000)T1.0e−004*(0.5777,0.5777)T29(0.0074,1.0000)T1.0e−004*(0.5525,0.5525)T30(0.0073,1.0000)T1.0e−004*(0.5293,0.5293)T31(0.0071,1.0000)T1.0e−004*(0.5080,0.5080)T32(0.00699,1.0000)T1.0e−004*(0.4884,0.4884)T33(0.0069,1.0000)T1.0e−004*(0.4702,0.4702)T34(0.0067,1.0000)T1.0e−004*(0.4533,0.4533)T35(0.0066,1.0000)T1.0e−004*(0.4376,0.4376)T36(0.0065,1.0000)T1.0e−004*(0.4229,0.4229)T37(0.0064,1.0000)T1.0e−004*(0.4092,0.4092)T38(0.0063,1.0000)T1.0e−004*(0.3963,0.3963)T39(0.0062,1.0000)T1.0e−004*(0.3842,0.3842)TResults for Example4.1 with initial point x0=(10,1)Tλ1=0.01,λ2=1 and computes dk by (3.4) are listed in Tables 4 and  5.Table 4
x0=(10,1)Tλ1=0.01,λ2=1 and computes dk by (3.4).
Step(x1,x2)TF(x)1(10.0000,1.0000)T(100.0000,100.0000)T2(5.0062,1.0000)T(25.0625,25.0625)T3(2.5062,1.0000)T(6.2813,6.2813)T4(1.2547,1.0000)T(1.5742,1.5742)T5(0.6281,1.0000)T(0.3945,0.3945)T6(0.3145,1.0000)T(0.0989,0.0989)T7(0.1574,1.0000)T(0.0248,0.0248)T8(0.0788,1.0000)T(0.0062,0.0062)T9(0.0395,1.0000)T(0.0016,0.0016)T10(0.0198,1.0000)T1.0e−003*(0.3901,0.3901)T11(0.0099,1.0000)T1.0e−004*(0.9778,0.9778)T12(0.00495,1.0000)T1.0e−004*(0.2451,0.2451)T13(0.0025,1.0000)T1.0e−005*(0.6142,0.6142)T14(0.0012,1.0000)T1.0e−005*(0.1539,0.1539)T15(0.0006,1.0000)T1.0e−006*(0.3858,0.3858)TTable 5
x0=(10,1)Tλ1=0.01,λ2=1 and computes dk by (3.4).
Step(x1,x2)TF(x)16(0.0003,1.0000)T1.0e−007*(0.9668,0.9668)T17(0.0002,1.0000)T1.0e−007*(0.2423,0.2423)T18(0.00008,1.0000)T1.0e−008*(0.6073,0.6073)TResults for Example4.1 with initial point x0=(10,1)Tσ1=λ1=0.01,σ2=λ2=1 and computes dk by (3.3) are listed in Tables 6 and  7.Table 6
x0=(10,1)Tλ1=0.01,λ2=1 and computes dk by (3.3).
Step(x1,x2)TF(x)1(10.0000,1.0000)T(100.0000,100.0000)T2(5.0001,1.0000)T(25.0006,25.0006)T3(2.5002,1.0000)T(6.2508,6.2508)T4(1.2503,1.0000)T(1.5633,1.5633)T5(0.6257,1.0000)T(0.3915,0.3915)T6(0.3138,1.0000)T(0.0985,0.0985)T7(0.1589,1.0000)T(0.0252,0.0252)T8(0.0832,1.0000)T(0.0069,0.0069)T9(0.0479,1.0000)T(0.0023,0.0023)T10(0.0324,1.0000)T(0.0011,0.0011)T11(0.0250,1.0000)T1.0e−003*(0.6258,0.6258)T12(0.0208,1.0000)T1.0e−003*(0.4345,0.4345)T13(0.0182,1.0000)T1.0e−003*(0.3296,0.3296)T14(0.0163,1.0000)T1.0e−003*(0.2644,0.2644)T15(0.0148,1.0000)T1.0e−003*(0.2203,0.2203)T16(0.0137,1.0000)T1.0e−003*(0.1885,0.1885)T17(0.0128,1.0000)T1.0e−003*(0.1646,0.1646)T18(0.0121,1.0000)T1.0e−003*(0.1460,0.1460)T19(0.0115,1.0000)T1.0e−003*(0.1311,0.1311)T20(0.0109,1.0000)T1.0e−003*(0.11899,0.11899)T21(0.0104,1.0000)T1.0e−003*(0.1089,0.1089)T22(0.0100,1.0000)T1.0e−003*(0.1003,0.1003)T23(0.0096,1.0000)T1.0e−004*(0.9301,0.9301)T24(0.0093,1.0000)T1.0e−004*(0.8668,0.8668)T25(0.0090,1.0000)T1.0e−004*(0.8115,0.8115)T26(0.0087,1.0000)T1.0e−004*(0.7628,0.7628)T27(0.0085,1.0000)T1.0e−004*(0.7195,0.7195)T28(0.0083,1.0000)T1.0e−004*(0.6809,0.6809)T29(0.0080,1.0000)T1.0e−004*(0.6462,0.6462)T30(0.0078,1.0000)T1.0e−004*(0.6148,0.6148)TTable 7
x0=(10,1)Tσ1=0.01,σ2=1 and computes dk by (3.3).
Step(x1,x2)TF(x)31(0.0077,1.0000)T1.0e−004*(0.5863,0.5863)T32(0.0075,1.0000)T1.0e−004*(0.5603,0.5603)T33(0.0073,1.0000)T1.0e−004*(0.5366,0.5366)T34(0.0072,1.0000)T1.0e−004*(0.5147,0.5147)T35(0.0070,1.0000)T1.0e−004*(0.4946,0.4946)T36(0.0069,1.0000)T1.0e−004*(0.4759,0.4759)T37(0.0068,1.0000)T1.0e−004*(0.4586,0.4586)T38(0.0067,1.0000)T1.0e−004*(0.4425,0.4425)T39(0.0065,1.0000)T1.0e−004*(0.4275,0.4275)T40(0.0064,1.0000)T1.0e−004*(0.4135,0.4135)T41(0.0063,1.0000)T1.0e−004*(0.4004,0.4004)T42(0.0062,1.0000)T1.0e−004*(0.3880,0.3880)TResults are
shown for Example4.1 with initial point x0=(100,1)T.
We also use the condition ∥xk−xk−1∥≤10−4 as the stopping criterion and  computes dk by (3.4) we get that by 21 steps F(x)=1.0e−008*(0.9560,0.9560)T.
When we compute dk by (3.3), we get that by 45 steps F(x)=1.0e−004*(0.3919,0.3919)T.
We can test the method with other examples and will think the global
convergence of the method in another paper.



---

*Source: 942391-2009-02-03.xml*