Adv Syst Sci Appl 2024; 01:29–39

Published online at https://ijassa.ipu.ru.

The Piecewise Levenberg–Marquardt Method

Alexey F. Izmailov1*, Evgeniy I. Uskov2, Yan Zhibai1

1Lomonosov Moscow State University, Moscow, Russia
2Derzhavin Tambov State University, Tambov, Russia

Abstract: We develop sharp local superlinear convergence results for the Levenberg–Marquardt
method applied to constrained piecewise smooth equations, under the local Lipschitzian error
bound condition for active selections, allowing for nonisolated solutions. We also characterize
the level of inexactness allowed when solving subproblems, such that it does not interfere with
superlinear convergence rate. Applications to constrained reformulations of complementarity
systems, using the “min” complementarity function are also discussed.

Keywords: nonlinear equation, constrained equation, piecewise smooth equation, nonisolated
solution, local error bound, Levenberg–Marquardt method

1. INTRODUCTION

We consider the constrained equation

Φ(u) = 0, u ∈ P, (1.1)

where Φ : Rp → Rq is a given mapping, and P ⊂ Rp is a given nonempty closed convex set.
Let U stand for the solution set of (1.1).

The case of P = Rp and p = q is the classical setting of an unconstrained nonlinear
equation, and assuming that Φ is smooth, the fundamental approach for solving such
problems is the Newton method; see, e.g., [12]. Local superlinear convergence of the basic
form of the Newton method requires a solution in question to be nonsingular, and in particular
isolated. The Levenberg–Marquardt (LM) method for unconstrained nonlinear equations
[17,19] (see also [20, Section 10.3]) is a classical regularization technique for handling cases
when a solution can be singular, and possibly nonisolated, and possibly with p ̸= q.

A natural way to approach the LM method is to consider first the (constrained) Gauss–
Newton (GN) method. For the current iterate u ∈ P , the GN method defines the next iterate
as u+ v, where v minimizes the (squared) residual of the linearized equation from (1.1) over
P − u, i.e., v is a solution of the optimization problem

minimize
1

2
∥Φ(u) + Φ′(u)v∥2 subject to u+ v ∈ P. (1.2)

Due to the Frank–Wolfe Theorem [10], this subproblem is always solvable when P is
polyhedral, but a solution need not be unique.

The potential lack of uniqueness of solutions in the subproblem (1.2) is one of the reasons
regularize it. This results in the constrained LM method [2, 15] for (1.1), defining the next

∗Corresponding author: izmaf@cs.msu.ru



30 A. F. IZMAILOV, E. I. USKOV, Y. ZHIBAI

iterate as u+ v, where v solves the optimization problem

minimize
1

2
∥Φ(u) +G(u)v∥2 + 1

2
σ(u)∥v∥2 subject to u+ v ∈ P, (1.3)

with a function σ : P → R+ defining the values of the regularization parameter, and with
G(u) being Φ′(u), or its suitable substitute when the derivative does not exist or is not
available. Observe that if σ(u) > 0, and if Euclidean norms are used, the objective function
of (1.3) is strongly convex quadratic, and hence, this subproblem has the unique solution.
Moreover, if P is a polyhedral set, then (1.3) is a strongly convex quadratic programming
problem.

When P = Rp, the constrained LM method reduces to the classical (sometimes called
unconstrained) LM method with its origins in [17, 19].

For the convergence properties for P = Rp in the case of smooth Φ and isolated solutions,
as well as related references, see [3, Theorem 10.2.6]. The cases of nonsmooth (semismooth)
Φ with isolated solutions was considered in [5]; see also [13, 14].

In this work we deal with local convergence analysis based on weaker assumptions of
the local Lipschitzian error bound type allowing, in particular, for nonisolated solutions,
and originating in the context of LM methods from [21]. Moreover, we concentrate on the
peculiarities of the case when Φ in (1.1) is piecewise smooth, but need not be smooth. As
argued in [4], the combination of nonisolated solutions with nonsmoothness is an especially
challenging situation.

For a recent survey of modern local convergence theories for the LM method, including
some applications, the issues of convergence globalization, etc., see [8].

Some comments on our notation are in order. The Euclidean inner product for u, v ∈
Rp is denoted by ⟨u, v⟩, and to avoid any confusion, let ∥ · ∥ stand for the Euclidean
norm throughout. For a set U ⊂ Rp and a point u ∈ Rp, dist(x, U) = infv∈U ∥v − u∥, and
B(u, δ) = {v ∈ Rp | ∥v − u∥ ≤ δ} is the closed ball of radius δ ≥ 0 centered at u. For a
given index set H ⊂ {1, . . . , p}, by uJ we denote the subvector of u ∈ Rp, with components
uj , j ∈ J .

For a closed convex set U ⊂ Rp, by NU(u) we denote the normal cone to U at u, i.e.,
NU(u) = {v ∈ Rp | ⟨v, ũ− u⟩ ≤ 0, ∀ ũ ∈ U} if u ∈ U , and NU(u) = ∅ otherwise.

For a sequence {uk} ⊂ Rp convergent to some ū ∈ Rp, we say that convergence is of Q-
order θ > 1 if there exists c > 0 such that ∥uk+1 − ū∥ ≤ c∥uk − ū∥θ for all k large enough.
Such rate of convergence is superlinear, and it is at least quadratic if θ ≥ 2. We say that {uk}
converges to ū with R-order θ if there exist c > 0 and a sequence {tk} ⊂ R+ converging to 0
with Q-order θ, such that ∥uk+1 − ū∥ ≤ ctk for all k large enough.

The rest of this paper is organized as follows. In Section 2, we recall the local convergence
framework from [9], that will serve as a main tool in our analysis. Section 3 contains our new
local convergence result for the piecewise smooth case, and Section 4 is devoted to the effect
of approximate solution of subproblems. Finally, in Section 5, we discuss applications of the
results obtained to constrained reformulations of complementarity systems, using the “min”
complementarity function.

2. LOCAL CONVERGENCE FRAMEWORK

We start with a discussion of the abstract local convergence framework recently proposed
in [9]. For that purpose, it is convenient to consider a problem setting with a single scalar
equation:

φ(u) = 0, u ∈ P, (2.4)
with φ : Rp → R+ being a given scalar-valued function, and P ⊂ Rp being a given nonempty
closed set. Obviously, the constrained equation (1.1) can be stated in the form (2.4) with, say,

Copyright © 2024 ASSA. Adv Syst Sci Appl (2024)



THE PIECEWISE LEVENBERG–MARQUARDT METHOD 31

φ(u) = ∥Φ(u)∥. To that end, there will be no confusion if in this section we will use U for
the solution set of (2.4).

Let Ψ : P → P be a given mapping, and consider an abstract iterative process updating
the current iterate u ∈ P to the new one of the form Ψ(u). The following is a version of [9,
Theorem 2.1], somehow simplified for our purposes.
Theorem 2.1:
Let φ : Rp → R+ be a continuous function, P ⊂ Rp be a nonempty closed set, ū ∈ U , and
assume that

φ(u) = O(dist(u, U)) (2.5)
as u ∈ P tends to ū.

Moreover, let Ψ : P → P be a mapping such that, with some τ > 1,

Ψ(u)− u = O(φ(u)) (2.6)

and
φ(Ψ(u)) = O((φ(u))τ ) (2.7)

as u ∈ P tends to ū.
Then, for every δ > 0, and every u0 ∈ P close enough to ū, the sequence {uk} defined by

uk+1 = Ψ(uk) for all k is contained in B(ū, δ) and converges to some u∗ ∈ U , and the rate
of convergence is superlinear with the Q-order τ .

3. THE PIECEWISE SMOOTH CASE: LOCAL CONVERGENCE

Our main focus in this work is on the case when Φ in (1.1) is piecewise smooth near a solution
ū in question: for a finite collection of selection mappings Φ1, . . . , Φs : Rp → Rq which are
continuously differentiable near ū, it holds that

Φ(u) ∈ {Φ1(u), . . . , Φs(u)} ∀u ∈ Rp,

and Φ is continuous near ū. Taking s = 1 recovers the smooth case, i.e. the case when Φ
is continuously differentiable near ū. According to [11, Theorem 2.1], any mapping that is
piecewise smooth near some point is necessarily Lipschitz-continuous near that point.

For every u ∈ Rp, define the set

A(u) = {j ∈ {1, . . . , s} | Φ(u) = Φj(u)} (3.8)

of indices of all selection mappings active at u. Let G be any mapping such that

G(u) ∈ {(Φj)′(u) | j ∈ A(u)} (3.9)

for u ∈ Rp close enough to ū. The algorithm with the subproblem (1.3) employing G defined
by (3.8) and (3.9), is naturally referred to as the constrained piecewise LM method. Observe
that with this definition of G, for any u ∈ Rp close enough to ū, the subproblem (1.3) can be
written in the form

minimize
1

2
∥Φj(u) + (Φj)′(u)v∥2 + 1

2
σ(u)∥v∥2 subject to u+ v ∈ P, (3.10)

with some j ∈ A(u), and this can be seen as the subproblem of the LM method applied to a
smooth constrained equation

Φj(u) = 0, u ∈ P. (3.11)
Needless to say, the index j can vary from one iteration to another.

Copyright © 2024 ASSA. Adv Syst Sci Appl (2024)



32 A. F. IZMAILOV, E. I. USKOV, Y. ZHIBAI

We will need to assume the P -property at ū, introduced in [7, p. 434]. It consists of saying
that near ū the constraint set P excludes all zeroes of smooth selections active at ū, which are
not zeroes of Φ. Formally it means that Uj ⊂ U near ū for all j ∈ A(ū), where Uj stands for
the solution set of (3.11). The P -property at ū evidently implies that

dist(u, U) ≤ dist(u, Uj) (3.12)

for all u ∈ P close enough to ū. We note that the P -property can be easily guaranteed
for reformulations of complementarity systems by means of the “min” (natural residual)
complementarity function, see [7] and Section 5 below.

Another assumption employed in Theorem 3.1 below is the constrained error bound for
each active selection, that is

dist(u, Uj) = O(∥Φj(u)∥) ∀ j ∈ A(ū) (3.13)

as u ∈ P tends to ū. Under this assumption, the P -property at ū is equivalent to the condition

Φ(u) = O(∥Φj(u)∥) ∀ j ∈ A(ū)

as u ∈ P tends to ū. Observe also that, employing the inclusion A(u) ⊂ A(ū) for u ∈ Rp

close enough to ū, one can easily see that the P -property at ū, and the condition (3.13) as
u ∈ P tends to ū, imply the constrained error bound

dist(u, U) = O(∥Φ(u)∥) (3.14)

as u ∈ P tends to ū.
We proceed with the following characterization of local superlinear convergence of the

piecewise LM method, which is the main result of this section.
Theorem 3.1:
Let Φ : Rp → Rq be a given mapping, P ⊂ Rp a nonempty closed convex set, and ū ∈ U .
Assume that Φ is piecewise smooth near ū, and the derivatives of its smooth selection
mappings Φ1, . . . , Φs : Rp → Rq are Lipschitz-continuous near ū. Let the P -property at
ū and condition (3.13) be satisfied as u ∈ P tends to ū. Moreover, let G : Rp → Rq×p be
a fixed mapping satisfying (3.9), and assume that the function σ : P → R+ defining the
regularization parameter satisfies

∥Φ(u)∥θ = O(σ(u)), σ(u) = O(∥Φ(u)∥θ) (3.15)

as u ∈ P tends to ū, with some fixed θ ∈ (0, 2].
Then, for every u0 ∈ P , there exists the unique sequence {uk} such that for every k, the

displacement uk+1 − uk is a solution of (1.3) with u = uk, and with the additional convention
that uk+1 = uk if uk ∈ U . For any δ > 0, if u0 ∈ P is close enough to ū, then this sequence is
contained in B(ū, δ) and converges to some u∗ ∈ U , and the rate of convergence superlinear
with the Q-order min{θ + 1, 2}.

Proof
The first estimate in (3.15) implies that σ(u) > 0 for all u ∈ P \ U close enough to ū, and
hence, for such u, the LM subproblem (1.3) has the unique solution v(u). Furthermore, for
u ∈ Rp close to ū, and for j ∈ A(u) ⊂ A(ū) such that G(u) = (Φj)′(u) (see (3.9)), we have
that Φj(u) = Φ(u) (see (3.8)). For any such j, (3.15) implies the estimates

∥Φj(u)∥θ = O(σ(u)), σ(u) = O(∥Φj(u)∥θ) (3.16)

as u ∈ P tends to ū, and an iteration of the constrained piecewise LM method can be
interpreted as an iteration of the usual constrained LM method for the smooth constrained

Copyright © 2024 ASSA. Adv Syst Sci Appl (2024)



THE PIECEWISE LEVENBERG–MARQUARDT METHOD 33

equation (3.11), with the subproblem (3.10), and with the regularization parameter satisfying
(3.16).

Employing the restriction θ ∈ (0, 2], from (3.13) and from the first estimate in (3.16) it
follows that

(dist(u, Uj))
4

σ(u)
= (dist(u, Uj))

2O

(
∥Φj(u)∥2

σ(u)

)
= O((dist(u, Uj))

2) (3.17)

as u ∈ P \ U tends to ū.
Let ûj stand for a metric projection of u onto Uj:

∥u− ûj∥ = dist(u, Uj). (3.18)

Since v(u) is a global solution of (3.10), it holds that

∥Φj(u) + (Φj)′(u)v(u)∥2 + σ(u)∥v(u)∥2 ≤ ∥Φj(u) + (Φj)′(u)(ûj − u)∥2

+σ(u)∥ûj − u∥2. (3.19)

Since j ∈ A(ū), it holds that ū ∈ Uj . Therefore, evidently, ûj → ū as u→ ū, and from
(3.18)–(3.19), applying again the Mean-Value Theorem [12, Theorem A.10], we derive that

∥v(u)∥2 ≤ 1

σ(u)

(
∥Φj(u) + (Φj)′(u)(ûj − u)∥2 + σ(u)∥ûj − u∥2

)
=

1

σ(u)
∥Φj(u)− Φj(ûj)− (Φj)′(u)(u− ûj)∥2 + ∥u− ûj∥2

≤ 1

σ(u)
sup

τ∈[0, 1]
∥(Φj)′(τu+ (1− τ)ûj)− (Φj)′(u)∥2∥u− ûj∥2 + ∥u− ûj∥2

= ∥u− ûj∥2 +O

(
∥u− ûj∥4

σ(u)

)
= O((dist(u, Uj))

2), (3.20)

where the last estimate is by (3.17). Hence, employing again (3.13),

v(u) = O(dist(u, Uj)) = O(∥Φj(u)∥) = O(∥Φ(u)∥) (3.21)

as u ∈ P \ U tends to ū.
Furthermore, any u ∈ Uj is a (global) solution of the optimization problem

minimize
1

2
∥Φj(u)∥2 subject to u ∈ P,

and the objective function of this problem is differentiable at u, with the gradient being
((Φj)′(u))⊤Φj(u). Therefore, any such u must satisfy the first-order necessary optimality
condition

((Φj)′(u))⊤Φj(u) +NP (u) ∋ 0. (3.22)
Employing now [2, Lemma 1] demonstrating that the constrained error bound implies the
upper Lipschitzian property of the solutions set of the generalized equation (3.22) subject
to the right-hand side perturbations, we obtain that under (3.13), for any solution u of the
perturbed generalized equation

((Φj)′(u))⊤Φj(u) +NP (u) ∋ ω, (3.23)

Copyright © 2024 ASSA. Adv Syst Sci Appl (2024)



34 A. F. IZMAILOV, E. I. USKOV, Y. ZHIBAI

close enough to ū, it holds that

dist(u, Uj) = O(∥ω∥)

as ω → 0.
The first-order necessary optimality condition for the subproblem (3.10) has the form

((Φj)′(u))⊤(Φj(u) + (Φj)′(u)v) + σ(u)v +NP (u+ v) ∋ 0. (3.24)

For any given u ∈ Rp, (3.22) is equivalent to saying that

((Φj)′(u+ v))⊤Φj(u+ v) +NP (u+ v) ∋ 0 (3.25)

holds with v = 0. Then (3.24) can be regarded as a perturbation of the generalized equation
(3.25). Specifically, if we set

ω(u, v) = ((Φj)′(u+ v))⊤Φj(u+ v)− ((Φj)′(u))⊤(Φj(u) + (Φj)′(u)v)− σ(u)v

=
(
((Φj)′(u+ v))⊤ − ((Φj)′(u))⊤

)
Φj(u+ v)

+((Φj)′(u))⊤(Φj(u+ v)− Φj(u)− (Φj)′(u)v)
−σ(u)v, (3.26)

then (3.24) can be written in the form

((Φj)′(u+ v))⊤Φj(u+ v) +NP (u+ v) ∋ ω(u, v).

From Lipschitz-continuity of (Φj)′ near ū, and from the second estimate in (3.15) and (3.21),
employing again the Mean-Value Theorem [12, Theorem A.10], one can readily derive the
estimates

ω(u, v(u)) = O(σ(u)∥v(u)∥) +O(∥v(u)∥2)
= O(∥Φ(u)∥θ+1) +O(∥Φj(u)∥2)
= O(∥Φ(u)∥min{θ+1, 2}) (3.27)

as u ∈ P \ U tends to ū.
Summarizing the considerations above, u+ v(u) is a solution of the generalized equation

(3.23) with ω = ω(u, v(u)), and it holds that u+ v(u) → ū and ω(u, v(u)) → 0 as u ∈
P \ U tends to ū. Therefore, [2, Lemma 1] allows to conclude that

dist(u+ v(u), Uj) = O(ω(u, v(u))) = O(∥Φ(u)∥min{θ+1, 2}),

where the second estimate is by (3.27). Therefore, since Φ is Lipschitz-continuous near ū,
employing the inequality (3.12) (following from the P -property) we derive

Φ(u+ v(u)) = O(dist(u+ v(u), U)) = O(dist(u+ v(u), Uj)) = O(∥Φ(u)∥min{θ+1, 2})
(3.28)

as u ∈ P \ U tends to ū.
Estimates (3.21) and (3.28) yield (2.6) and (2.7) in Theorem 2.1 with Ψ(u) = u+ v(u),

φ(u) = ∥Φ(u)∥, and τ = min{θ + 1, 2}, while (2.5) is satisfied again because of Lipschitz
continuity of Φ. The needed conclusion now follows by application of Theorem 2.1.

For the case when θ = 2, the result of Theorem 3.1 was essentially obtained in [7,
Theorems 1, 2]; see also [8, Theorem 4.1], where it is emphasized that the convexity
assumption on P is actually not needed in that case. On the other hand, in the smooth case,
Theorem 3.1 is a particular case of [2, Theorem 1].

Copyright © 2024 ASSA. Adv Syst Sci Appl (2024)



THE PIECEWISE LEVENBERG–MARQUARDT METHOD 35

As demonstrated in [8, Example 3.2], the convergence rate estimate in Theorem 3.1 is
sharp even in the smooth unconstrained case, and even when the solution ū in question
is isolated. This example also shows that the constrained error bound condition (3.14),
corresponding to (3.13) in the smooth case, is essential for this analysis.

Regarding the restriction θ ∈ (0, 2] in Theorem 3.1 on the exponent in the regularization
parameter, [8, Example 3.2] demonstrates that at least the requirement θ < 4 cannot be
avoided, even in the smooth case. The possibility to obtain a counterpart of Theorem 3.1 for
the values θ ∈ (2, 4) seems to remain an open question. The lack of quadratic convergence is
claimed in [1, Example 4.2] for θ > 3, but this claim relies on some numerical observations
only. In the smooth case, superlinear convergence to 0 of the sequence {dist(uk, U)} for
θ ∈ (2, 3) was established in [6], with some similar results and extensions in the recent
work [22].

4. THE PIECEWISE SMOOTH CASE: EFFECT OF INEXACTNESS

Since solving the constrained LM subproblems exactly can be too expensive, or even
impossible, a natural issue consists of characterization of the “level” of controllable
inexactness when solving subproblems that does not interfere with local convergence and
rate of convergence properties of the LM method established in Section 3.

Yet again, for u ∈ Rp close to ū, let j ∈ A(u) ⊂ A(ū) be such that G(u) = (Φj)′(u) (see
(3.9)); it also necessarily holds that Φj(u) = Φ(u) (see (3.8)). Recall that an iteration of the
constrained piecewise LM method can be interpreted as an iteration of the usual constrained
LM method for the smooth constrained equation (3.11), with the subproblem (3.10), and with
the regularization parameter satisfying (3.16).

The first-order necessary optimality condition for (3.10) has the form (3.24), and it is
natural to consider the version of the inexact constrained LM method, with inexactness
measured by the violation of (3.24). Specifically, the process of solving the subproblem (3.10)
is terminated once

((Φj)′(u))⊤(Φj(u) + (Φj)′(u)v) + σ(u)v +NP (u+ v) ∋ w (4.29)

is satisfied with some w ∈ Rp smaller than the given tolerance that conforms with the
exponent θ in (3.15) (and in (3.16)) as follows:

w = O(∥Φj(u)∥θ+1) (4.30)

as u ∈ P tends to ū.
The analysis in [2] relies on the observation that (4.29) is a necessary and sufficient

optimality condition for the following convex optimization problem, which is a perturbation
of (3.10):

minimize
1

2
∥Φj(u) + (Φj)′(u)v∥2 + 1

2
σ(u)∥v∥2 − ⟨w, v⟩ subject to u+ v ∈ P.

(4.31)
Then we follow the argument used above to prove (3.21), but taking into account that now
the objective function of (4.31) has an extra term involving w.

Employing again a metric projection ûj of u ∈ P \ U onto Uj , for the unique global
solution v(u) of (4.31), similarly to (3.19) we obtain that

∥Φj(u) + (Φj)′(u)v∥2 + σ(u)∥v(u)∥2 − 2⟨w, v(u)⟩ ≤ ∥Φj(u) + (Φj)′(u)(ûj − u)∥2

+σ(u)∥ûj − u∥2 − 2⟨w, ûj − u⟩.

Copyright © 2024 ASSA. Adv Syst Sci Appl (2024)



36 A. F. IZMAILOV, E. I. USKOV, Y. ZHIBAI

Then, similarly to (3.20) (and in particular, making use of (3.18)), we derive the estimate

∥v(u)∥2 ≤ 1

σ(u)

(
∥Φj(u) + (Φj)′(u)(ûj − u)∥2 + σ(u)∥ûj − u∥2

+2⟨w, v(u)⟩ − 2⟨w, ûj − u⟩
)

≤ 2∥w∥
σ(u)

(∥v(u)∥+ dist(u, Uj)) +O((dist(u, Uj))
2)

≤ O(∥Φj(u)∥(∥v(u)∥+ dist(u, Uj))) +O((dist(u, Uj))
2)

= O(dist(u, Uj)∥v(u)∥) +O((dist(u, Uj))
2) (4.32)

as u ∈ P \ U tends to ū, where the next-to-the-last estimate is by (4.30) and the first relation
in (3.16), and the last one is the Lipschitz continuity of Φj near ū. Evidently, (4.32) implies
(3.21) as u ∈ P \ U tends to ū.

The remaining part of the argument consists of the reasoning used above to prove
Theorem 3.1, but with ω(u, v) defined in (3.26) replaced by ω(u, v) + w: taking again into
account (4.30), one can see that this modification does not affect (3.27) and the subsequent
analysis. This yields

Theorem 4.1:
Under the assumptions of Theorem 3.1, let the function ψ : P → R+ satisfy ψ(u) =
O(∥Φ(u)∥θ+1) as u ∈ P tends to ū.

Then, for every u0 ∈ P , there exists a sequence {uk} such that for every k, the
displacement uk+1 − uk is the solution of (4.29) with u = uk, with some w ∈ Rp satisfying
∥w∥ ≤ ψ(uk), and with the additional convention that uk+1 = uk if uk ∈ U . For any δ > 0,
if u0 ∈ P is close enough to ū, any such sequence is contained in B(ū, δ) and converges to
some u∗ ∈ U , and the rate of convergence is superlinear with the Q-order min{θ + 1, 2}.

For the case when θ = 2, a result related to Theorem 4.1 was obtained in [4, Theorems 3],
but for a somewhat different kind of inexactness. See also [8, Section 5] for a discussion of
these issues in the smooth case, including establishing the relations between these two kinds
of inexactness.

The requirement (4.30) on allowed inexactness in Theorem 4.1 cannot be relaxed even in
the smooth case, as demonstrated by an example in [2, Section 5].

5. APPLICATION TO REFORMULATIONS OF COMPLEMENTARITY SYSTEMS

In this section we deal with a nonlinear complementarity system of the form

a(x) = 0, b(x) ≥ 0, c(x) ≥ 0, d(x) ≥ 0, ⟨c(x), d(x)⟩ = 0, (5.33)

with given smooth mappings a : Rn → Rl, b : Rn → Rm, c : Rn → Rr, d : Rn → Rr, i.e.,
possessing Lipschitz-continuous derivatives near a solution x̄ of (5.33). Various important
problem classes can be modeled as (5.33), including the so-called (mixed) complementarity
problems, and in particular, Karush–Kuhn–Tucker optimality systems, to mention some.

One of the most successful approaches to (5.33) consists of reformulating it as a system
of equations by means of the so-called complementarity functions, perhaps the simples
(but at the same time prominent) one being the “min” (natural residual) complementarity
function: using auxiliary slack variables, system (5.33) can be equivalently written as (1.1)
with p = n+ 2r +m, q = l + 3r +m,

Φ(u) = (a(x), min{y, z}, c(x)− y, d(x)− z, b(x)− µ), u = (x, y, z, µ), (5.34)

Copyright © 2024 ASSA. Adv Syst Sci Appl (2024)



THE PIECEWISE LEVENBERG–MARQUARDT METHOD 37

P = Rn × Rr
+ × Rr

+ × Rm
+ . (5.35)

The mapping Φ defined in (5.34) is evidently piecewise smooth. More precisely, for a
current iterate uk = (xk, yk, zk, µk) ∈ Rp, the smooth selections active at uk have the form

ΦJ(u) = (a(x), yIc(uk)∩J , zId(uk)∩(I0(uk)\J), c(x)− y, d(x)− z, b(x)− µ), (5.36)

where
Ic(u

k) = {i ∈ {1, . . . , r} | yki < zki },
Id(u

k) = {i ∈ {1, . . . , r} | yki > zki },
I0(u

k) = {i ∈ {1, . . . , r} | yki = zki },

and J ⊂ I0(u
k). Therefore, the iteration of the piecewise LM method consists of choosing

such J , setting G(uk) = (ΦJ)′(uk), and solving (1.3) with u = uk for the displacement
vk = uk+1 − uk.

According to (5.36), for any solution x̄ of system (5.33), and for the corresponding
solution ū = (x̄, ȳ, z̄, µ̄) of problem (1.1) with Φ and P defined in (5.34) and (5.35),
respectively, with ȳ = c(x̄), z̄ = d(x̄), and µ̄ = b(x̄), the smooth selections of Φ active at
ū have the form

ΦJ(u) = (a(x), yIc∩J , zId∩(I0\J), c(x)− y, d(x)− z, b(x)− µ), (5.37)

where
Ic = Ic(ū) = {i ∈ {1, . . . , r} | ci(x̄) = 0 < di(x̄)},
Id = Ib(ū) = {i ∈ {1, . . . , r} | ci(x̄) > 0 = di(x̄)},
I0 = I0(ū) = {i ∈ {1, . . . , r} | ci(x̄) = 0 = di(x̄)},

and J ⊂ I0.
Observe that the nonnegativity conditions on y and z in the definition of P in (5.35) may

seem extraneus for this reformulation as they are guaranteed by the equality min{y, z} = 0.
However, these constraints appear essential for guaranteing the P property to hold at ū.
Indeed, if for a given J ⊂ I0, it holds that ΦJ(u) = 0 for some u ∈ P , then according to
(5.35), yId∩(I0\J) ≥ 0 and zIc∩J ≥ 0, and hence, according to (5.34) and (5.37), it holds that
Φ(u) = 0. At the same time, if u ∈ Rp \ P , then some components of, say, zIc∩J can be
negative, and then min{yIc∩J , zIc∩J} = min{0, zIc∩J} need not be equal to 0.

The remaining ingredient for applicability of Theorems 3.1 and 4.1 is the constrained
local Lipschitzian error bound (3.13) for selections active at ū. For every J ⊂ I0, let

XJ =

{
x ∈ Rn

∣∣∣∣∣ a(x) = 0, cIc∩J(x) = 0, dId∩(I0\J)(x) = 0,

b(x) ≥ 0, c(x) ≥ 0, d(x) ≥ 0

}
.

Then according to the discussion in [7, Section 5] (see, in particular, [7, Figure 3]), condition
(3.13) is implied by the following: for every J ⊂ I0, it holds that

dist(x, XJ) = O(∥a(x)∥+ ∥cIc∩J(x)∥+ ∥dId∩(I0\J)(x)∥+ ∥min{0, b(x)}∥
+∥min{0, cId∩(I0\J)(x)}∥+ ∥min{0, dIc∩J(x)}∥) (5.38)

as x ∈ Rn tends to x̄. Condition (5.38) is nothing else but the local Lipschitzian error bound
for the constraint system

a(x) = 0, cIc∩J(x) = 0, dId∩(I0\J)(x) = 0, b(x) ≥ 0, cId∩(I0\J)(x) ≥ 0, dIc∩J(x) ≥ 0,
(5.39)

Copyright © 2024 ASSA. Adv Syst Sci Appl (2024)



38 A. F. IZMAILOV, E. I. USKOV, Y. ZHIBAI

characterizing a branch of the solution set of the complementarity system (5.33) near a given
solution x̄. Therefore, (3.13) is impled by the so-called piecewise error bound condition for
(5.33), that is, the local Lipschitzian error bound at x̄ for every branch of the solution set,
containing x̄, i.e., for the constraint system (5.39) with every J ⊂ I0. The latter property
is implied by the so-called piecewise constrained qualifications at x̄, such as the classical
Mangasarian–Fromovits constraint qualification [18], or the relaxed constant rank constraint
qualification [16], for (5.39) with every J ⊂ I0.

ACKNOWLEDGEMENTS

This work was funded by the Russian Science Foundation Grant 24-21-00015 (https:
//rscf.ru/en/project/24-21-00015/).

REFERENCES

1. Behling, R. (2011) The method and the trajectory of Levenberg–Marquardt. PhD
thesis. IMPA - Instituto Nacional de Matemática Pura e Aplicada, Rio de Janeiro.
https://impa.br/wp-content/uploads/2017/08/tese dout roger behling.pdf

2. Behling, R. & Fischer, A. (2012) A unified local convergence analysis of inexact
constrained Levenberg–Marquardt methods, Optim. Lett., 6, 927–940.

3. Dennis, J.E. & Schnabel, R.B. (1983) Numerical Methods for Unconstrained
Optimization and Nonlinear Equations. Englewood Cliffs, NJ: Prentice-Hall, Inc.

4. Facchinei, F., Fischer, A. & Herrich, M. (2013) A family of Newton methods for
nonsmooth constrained systems with nonisolated solutions, Math. Methods Oper. Res.,
77, 433–443.

5. Facchinei F. & Kanzow, C. (1997) A nonsmooth inexact Newton method for the
solution of large-scale nonlinear complementarity problems, Math. Program., 76,
493–512.

6. Fan, J.-Y. & Pan, J.-Y. (2011) On the convergence rate of the inexact Levenberg–
Marquardt method, J. Ind. Manag. Optim., 7, 199–210.

7. Fischer, A., Herrich, M., Izmailov, A.F. & Solodov, M.V. (2016) Convergence
conditions for Newton-type methods applied to complementarity systems with
nonisolated solutions, Comput. Optim. Appl., 63, 425–459.

8. Fischer, A., Izmailov, A.F. & Solodov, M.V. (2023) The Levenberg–Marquardt
method: an overview of modern convergence theories and more. (Submitted).

9. Fischer, A. & Strasdat, N. (2023) An extended convergence framework applied to
complementarity systems with degenerate and nonisolated solutions, Pure Appl. Func.
Analys., 8, 1039–1054.

10. Frank, M. & Wolfe, P. (1956) An algorithm for quadratic programming, Naval
Research Logistics Quarterly, 3, 95–110.

11. Hager, W.W. (1979) Lipschitz continuity for constrained processes, SIAM J. Control
Optim., 17, 321–338.

12. Izmailov, A.F. & Solodov, M.V. (2014) Newton-Type Methods for Optimization and
Variational Problems. Cham, Germany: Springer.

13. Kanzow, C. & Petra, S. (2004) On a semismooth least squares formulation of
complementarity problems with gap reduction, Optim. Meth. Software, 19, 507–525.

14. Kanzow, C. & Petra, S. (2007) Projected filter trust region methods for a semismooth
least squares formulation of mixed complementarity problems, Optim. Meth. Software,
22, 713–735.

15. Kanzow, C., Yamashita, N. & Fukushima, M. (2004) Levenberg–Marquardt methods
with strong local convergence properties for solving nonlinear equations with convex

Copyright © 2024 ASSA. Adv Syst Sci Appl (2024)

https://rscf.ru/en/project/24-21-00015/
https://rscf.ru/en/project/24-21-00015/
https://impa.br/wp-content/uploads/2017/08/tese_dout_roger_behling.pdf


THE PIECEWISE LEVENBERG–MARQUARDT METHOD 39

constraints, J. Comput. Appl. Math., 172, 375–397.
16. Kyparisis, J. (1990) Sensitivity analysis for nonlinear programs and variational

inequalities with nonunique multipliers, Math. Oper. Res., 15, 286–298.
17. Levenberg, K. (1944) A method for the solution of certain non-linear problems in least

squares, Quarterly of Appl. Math., 2, 164–168.
18. Mangasarian, O.L. & Fromovitz, S. (1967) The Fritz John necessary optimality

conditions in the presence of equality and inequality constraints, J. Math. Anal. Appl.,
17, 37–47.

19. Marquardt, D.W. (1963) An algorithm for least squares estimation of non-linear
parameters, SIAM J., 11, 431–441.

20. Nocedal, J. & Wright, S.J. (2006) Numerical Optimization. 2nd edition. New York,
NY: Springer New York.

21. Yamashita, N. & Fukushima, M. (2001) On the rate of convergence of the Levenberg–
Marquardt method. In: Alefeld, G., Chen, X. (Eds.), Topics in Numerical Analysis.
Computing Supplementa, vol. 15 (pp. 239–249). Vienna, Austria: Springer.

22. Yin, J., Jian, J. & Ma, G. (2023) A modified inexact Levenberg–Marquardt method
with the descent property for solving nonlinear equations, Comput. Optim. Appl.
https://doi.org/10.1007/s10589-023-00513-z.

Copyright © 2024 ASSA. Adv Syst Sci Appl (2024)

https://doi.org/10.1007/s10589-023-00513-z

	Introduction
	Local convergence framework
	The piecewise smooth case: local convergence
	The piecewise smooth case: effect of inexactness
	Application to reformulations of complementarity systems