# A New Smoothing Nonlinear Conjugate Gradient Method for Nonsmooth Equations with Finitely Many Maximum Functions

Authors: Yuan-yuan Chen; Shou-qiang Du
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

The nonlinear conjugate gradient method is of particular importance for solving unconstrained optimization. Finitely many maximum functions is a kind of very useful nonsmooth equations, which is very useful in the study of complementarity problems, constrained nonlinear programming problems, and many problems in engineering and mechanics. Smoothing methods for solving nonsmooth equations, complementarity problems, and stochastic complementarity problems have been studied for decades. In this paper, we present a new smoothing nonlinear conjugate gradient method for nonsmooth equations with finitely many maximum functions. The new method also guarantees that any accumulation point of the iterative points sequence, which is generated by the new method, is a Clarke stationary point of the merit function for nonsmooth equations with finitely many
maximum functions.


---

## Body

## 1. Introduction

In this paper, we consider the following nonsmooth equations with finitely many maximum functions:(1)maxj∈J1{h1j(x)}=0,⋮maxj∈Jn{hnj(x)}=0,
where hij:Rn→R for i=1,…,n and j∈Ji,  i=1,…,n are continuously differentiable functions, and Ji are finite index sets. Denote that
(2)hi(x)=maxj∈Ji{hij(x)},i=1,…,n,H(x)=(h1(x),…,hn(x))T,
then (1) can be reformulated as
(3)H(x)=0,
where H:Rn→Rn is nonsmooth equations and Ji(x)={ji∈N∣hij(x)=hi(x)},  i=1,…,n. Nonsmooth equations have been studied for decades, which is proposed in the study of the optimal control, the variational inequality and complementarity problems, equilibrium problems, and engineering mechanics [1–3], because many practical problems, such as stochastic complementarity problems, variational inequality problems, KKT systems of constrained nonlinear programming problems, and many problems in equilibrium problems, can be reformulated into (1). In the past few years, there has been a growing interest in the study of (1) (such as [4, 5]). Due to its simplicity and global convergence, the iterative methods, such as nonsmooth Levenberg-Marquardt method, general Newton method, and smoothing methods for solving nonsmooth equations, have been widely studied [4–11].In this paper, we give a new smoothing nonlinear conjugate gradient method for (1). In the following section, we will recall some definitions and some background of nonlinear conjugate gradient methods. And we also give the new smoothing nonlinear conjugate gradient method for (1), which guarantees that any accumulation point of the iterative points sequence is a Clarke stationary point of the merit function for (1). In the last section, some discussions are also given.Notation. In the following, a quantity with a subscript k denotes that quantity is evaluated at  xk, the norm is the 2 norm, and R++={t∣t>0}.


## 2. Preliminaries and New Method

In this section, firstly, we give some definitions and some backgrounds of nonlinear conjugate gradient method. Secondly, we propose the new methods for (1) and give the convergence analysis.In the following, we give two definitions, which will be used in this paper.Definition 1.
LetF:Rn→R be a locally Lipschitz function. Then, F is almost everywhere differentiable. Denote DF be the set of points where F is differentiable, then the general gradient of F at x in the sense of Clark is
(4)∂F(x)=conv{limxk→x,xk∈DF∇F(xk)},
where conv denotes the convex set.Definition 2.
Letr:Rn→R be a locally Lipschitz continuous function. We call r~:Rn×R++→R a smoothing function of  r, if  r~(·,μ)  is continuously differentiable for any fixed μ∈R++ and
(5)limx→x^,μ↓0r~(x,μ)=r(x^).In the following, we will give the new method for (1). In order to describe the method clearly, we divide this section into two parts. In Case 1, we give the new nonlinear conjugate gradient method for smooth objective function. In Case 2, we give the new smoothing nonlinear conjugate gradient method for nonsmooth objective function.Denote that(6)f(x)=12∥H(x)∥2,
where H is defined in (3). Then (1) is equivalent to the following unconstrained minimization problem with zero optimal value
(7)minx∈Rnf(x).Case 1.
In this section, we assume thatf is a continuously differentiable function. Then (7) is a standard unconstrained optimization problem. There are many methods for solving the unconstrained optimization problem, such as Newton method, nonlinear conjugate gradient method, and quasi-Newton method [12–16]. Here, based on [13, 14], we will give a new nonlinear conjugate gradient method to solve (7). The iterates for solving (7) is given by
(8)xk+1=xk+αkdk,
where dk is the direction and αk>0 is a step size; in this paper, we use the Wolfe type line search [14]. Compute αk>0, such that
(9)f(xk+αkdk)-f(xk)≤-ραk2∥dk∥2,g(xk+αkdk)Tdk≥-2σαk∥dk∥2,
where ρ,σ∈(0,1),  ρ<σ, and g is the gradient of f. The direction is defined by
(10)dk={-gk,ifk=1,-gk+βkdk-1,ifk≥2,
where
(11)βk=gkTyk-1dk-1Tzk-1-δ∥yk-1∥2(dk-1Tzk-1)2gkTdk-1,zk-1=yk-1+tk-1sk-1,  tk-1=ϵ0+max{0,-sk-1Tyk-1/sk-1Tsk-1},  ϵ0>0,  δ>1/4,  yk-1=gk-gk-1,  sk-1=xk-xk-1.Now we give the new method for (7) as follows.Method 1.
Consider the following steps.
Step  0.  Given x0∈Rn,  d0=-g0, and k:=0, if  ∥g0∥=0, then stop.
Step  1. Find αk>0 satisfying (9), and xk+1 is given by (8).
Step  2. Compute dk by (10). Set k:=k+1,  and go to Step 1.We also need the following assumptions.Assumption 3.
Consider the following:(i)
L-={x∈Rn∣f(x)≤f(x0)} is level bounded;(ii)
in the neighborhood ofL-, there exists L>0, such that
(12)∥g(x)-g(y)∥≤L∥x-y∥,
where x,y∈U,  U  is a neighborhood of L-.In the following, we will give the global convergence analysis about Method1. Firstly, we give some lemmas.Lemma 4.
Let{xk} be generated by Method 1, then
(13)gkTdk≤-(1-14μ)∥gk∥2,
where μ>1/4.By [13, Theorem  2.1], we have Lemma 4.Lemma 5 (see [14]).
Suppose that Assumption3 holds, αk is computed by (9), and we have
(14)∑k=1∞‍(gkTdk)2∥dk∥2<+∞.By Lemmas4 and 5, we have Lemma 6.Lemma 6.
Suppose that Assumption3 holds, αk is determined by (9), and we get
(15)∑k=1∞∥gk∥4∥dk∥2<+∞.Now, we give the global convergence theorem for Method1.Theorem 7.
Suppose that Assumption3 holds and {xk} is generated by Method 1, then
(16)liminfk→∞∥gk∥=0.Proof.
Suppose by contradiction that there existsϵ>0, such that
(17)∥gk∥≥ϵ,
holds for k≥1. By
(18)dk-1Tzk-1≥ϵ0dk-1Tsk-1,
and (11), we have
(19)|βk|≤(Lϵ0+μL2ϵ02)∥gk∥∥dk-1∥,∥dk∥≤∥gk∥+(Lϵ0+μL2ϵ02)∥gk∥.
Denoting that m=(1+((Lϵ0+μL2)/ϵ02)), we get ∥dk∥2≤m2∥gk∥2. Then we have
(20)∑k=1∞‍∥gk∥4∥dk∥2≥∑k=1∞‍ϵ2m2=+∞,
which contradicts (15). So we get the theorem.Case 2.
In this section, we assume thatf is a nonsmooth function. Equation (7) is the nonsmooth unstrained optimization problem. Denote that f~(x,μ) is the smoothing function for f(x), g~k=∇xf~(xk,μk), then αk>0 is computed by
(21)f~(xk+αkdk,μk)≤f~(xk,μk)-ραk2∥dk∥2,g~k+1Tdk≥-2σαk∥dk∥2,
where 0<ρ<σ<1. The direction is defined by
(22)dk={-g~k,ifk=1,-g~k+βkdk-1,ifk≥2,
where
(23)βk=g~kTy~k-1dk-1Tz~k-1-δ∥y~k-1∥2(dk-1Tz~k-1)2g~kTdk-1,z~k-1=y~k-1+tk-1sk-1,  tk-1=ϵ0+max{0,-sk-1Ty~k-1/sk-1Tsk-1},  ϵ0>0,  δ>1/4, y~k-1=g~k-g~k-1,  sk-1=xk-xk-1.
We give the following smoothing nonlinear conjugate gradient method.Method 2.
Givex0∈Rn, μ0>0,  γ>0,  and  γ1∈(0,1).
Step  1. Find αk>0 satisfying (21), and xk+1 is given by (8).
Step  2. If ∥∇xf~(xk+1,μk)∥≥γμk, then set μk+1=μk; otherwise, let  μk+1≤γ1μk.
Step  3. Compute dk by (22). Set k:=k+1, and  go to Step 1.Theorem 8.
Suppose thatf~(·,μ) satisfies Assumption 3, for fixed μ>0. Then the sequence {xk} generated by Method 2 satisfies
(24)limk→∞μk=0,liminfk→∞∥∇xf~(xk,μk-1)∥=0.Proof.
If the set{k∣μk+1≤γ1μk} is finite, then for a fixed K, ∥∇f~(xk,μk-1)∥≥γμk-1, for all k>K. Denoteing that μ-=μk,  k>K, because f~(·,μ-) is a smooth function, the previous method reduces to Method 1, where f(x)=f~(x,μ-). By Theorem 7, we get
(25)liminfk→∞∥∇xf~(xk,μ-)∥=0.
So we know that ∥∇f~(xk,μk-1)∥≥γμk-1 for k>K is impossible. Then we can assume that the set {k∣μk+1≤γ1μk} is infinite, then
(26)limk→∞μk=0.
By the infinity of {k∣μk+1≤γ1μk}, we can assume that the set is {k0,k1,…∣k0<k1<⋯}. Then we have
(27)liminfi→∞∥∇f~(xki+1,μki)∥≤γ1limi→∞μki.
By
(28)limi→∞μki=0,
we have
(29)liminfk→∞∥∇xf~(xk,μk-1)∥=0.
So we complete the proof.Remark 9.
From the result of Theorem8, we know that for some kinds of smoothing functions [9, 10], any accumulation point x⋆ of {xk} generated by Method 2 is a Clarke stationary point of f; that is,0∈∂f(x⋆).


## 3. Some Discussions

In this paper, we give a new smoothing nonlinear conjugate gradient method for (1). The new method also guarantees that any accumulation point is a Clarke stationary point of the merit function for (1).Discussion 1.
In our Methods1 and 2, we can use any line search, which is well defined under the condition that the search directions are descent directions.Discussion 2.
There are some kinds of smoothing functions, which satisfied Assumption3 for fixed μ>0 (see [9, 10]). When the smoothing function of f has gradient consistent property, then any accumulation point of the sequence {xk} generated by Method 2 is a Clarke stationary point. Under some assumptions, we can also use the methods in [15] to solve nonsmooth equations with finitely many maximum functions (1).Discussion 3.
The new method can also be used for solving nonlinear complementarity problem (NCP). By F-B function(30)φ(a,b)=a2+b2-(a+b),
we know that NCP is equivalent to ψ(x)=0, where ψ is a continuously differentiable function, so we can use the smooth version Method 1 to solve it. Method 2 can also be used to solve the vertical complementarity problems
(31)Hi(x)≥0,i=1,…,m,∏i=1m‍Hij(x)=0,j=1,…,n,
where Hi(x):Rn→Rn are continuously differentiable functions.Discussion 4.
The new method can also be used for solving Hamilton-Jacobi-Bellman equations (HJB) (see [17]). The Hamilton-Jacobi-Bellman equations (HJB) is used to find x∈Rn, such that
(32)max1≤i≤k{Lix-li}=0,inΘ,x=0,on∂Θ,
where  Θ  is a bounded domain in Rd,  Li  and  i=1,…,k are elliptic operators of second order. HJB arise in stochastic control problems and often are used to solve finance and control problems. By finite element method, we can obtain the following discrete HJB equation; find x∈Rn, such that
(33)max1≤j≤k{Ajx-ζj}=0,
where Aj∈Rn×n,  ζj∈Rn,  j=1,…,k.Discussion 5.
We also can consider to use the new method to solve the general variational inequality problem (see [18]). The general variational inequality problem is to compute x∈Rn, such that
(34)q(x)∈X,(y-q(x))Tp(x)≥0,foranyy∈X,
where p,q:Rn→Rn are two continuously differentiable functions and X⊆Rn is a closed convex set. Equation (34) is denoted by  GVI(X,p,q)  in [18].  GVI(X,p,q)  is a generalization of complementarity problems, nonlinear variational inequalities problems, and general nonlinear complementarity problems. The variational inequalities problems are to compute
(35)(y-x)Tp(x)≥0,foranyy∈X,
where x∈X. The general nonlinear complementarity problems are to compute x∈Rn, such that
(36)q(x)≥0,p(x)≥0,q(x)Tp(x)=0.
We can rewrite (34) as the following nonsmooth equation:
(37)q(x)-PX[q(x)-p(x)]=0,
where PX is the projection operator onto X under the Euclidean norm. The general nonlinear complementarity problems are widely used in solving engineering problems and economic problems; such that, under some conditions, the n-person noncooperative game problem can be reformulated as (37) (see [19]). Therefore, how to use our new method to solve the general nonlinear complementarity problems and the n-person noncooperative game problem would be an interesting topic and deserves further investigation.



---

*Source: 780107-2013-04-10.xml*