# An Adaptive Nonmonotone Line Search Technique for Solving Systems of Nonlinear Equations

Authors: Masoud Hatamian; Mahmoud Paripour; Farajollah Mohammadi Yaghoobi; Nasrin Karamikabir
Journal: Journal of Mathematics
 (2021)

---

## Abstract

In this article, a new nonmonotone line search technique is proposed for solving a system of nonlinear equations. We attempt to answer this question how to control the degree of the nonmonotonicity of line search rules in order to reach a more efficient algorithm? Therefore, we present a novel algorithm that can avoid the increase of unsuccessful iterations. For this purpose, we show the robust behavior of the proposed algorithm by solving a few numerical examples. Under some suitable assumptions, the global convergence of our strategy is proved.


---

## Body

## 1. Introduction

Different ranges of sciences such as economics, chemistry, robotics, and engineering can be formulated as systems of nonlinear equations. On the other hand, scientific advances in these areas are more dependent on the resolution of these systems.There are two kinds of system equations that are called linear and nonlinear systems and there are two primary methods for solving them called numerical solutions and optimization methods. Optimization-based methods are the most widely used ones for solving the nonlinear type.So, in this article, we discuss how to find solutions to a system of nonlinear equations as follows:(1)Fx=0,where F:ℝn⟶ℝm is continuously differentiable map and m≤n. Let the form of (1) be(2)F1x1,x2,…,xn=0,F2x1,x2,…,xn=0,⋮Fmx1,x2,…,xn=0.In recent years, several optimization-based methods have been developed to solve the nonlinear system of equation (1) such as Newton class and gradient class. The Newton class, for example, Newton and quasi-Newton methods, is more suitable for the small-scale systems of equations and gradient class; for example, the spectral gradient, and conjugate gradient methods, can suitably cope with large-scale systems. There are different approaches to converting the problem (1) to an optimization problem. For example, in the method proposed in [1], the authors transformed the system into an unconstrained optimization problem and then solved the new unconstrained problem instead by applying an optimization method that is formulated as follows:(3)f=F2x=F1F1T+F2F2T+⋯+FmFmT≥0,f=Fx=F1+F1+⋯+Fm≥0,and another forms exist [2, 3]. In this article, we consider the following form:(4)fx=12Fx2,where . stands for the Euclidean norm. So we replace the problem (1) by(5)minx∈ℝnfx,and set gx=∇fx. Indubitably, optimal solutions of problem (5) with the zero value of the objective function correspond to global solutions of system (1). Most of the optimization-based methods can be divided into two classes, namely, line search methods and trust-region methods [3, 4]. A line search method, at current iteration xk if gk=∇fxk≠0, defines a search direction dk in some way and finds a step-length by carrying some line search along dk. The most popular line search rules are the Armijo rule, the Goldstein rule, and the Wolfe rule [5–7]. For a given xk, the line search generates the next point by(6)xk+1=xk+αkdk,where αk>0 is a step size obtained by the line search and dk is a descent direction. The traditional line searches require the function value descent monotonically at every iteration, namely,(7)fxk+1≤fxk.The monotone rule may extremely decrease the rate of convergence when the iteration is ensnared near a narrow curved valley, which can cause very short steps or zigzagging. Grippo et al. [8] proposed the earliest nonmonotone line search. By combining forcing function with the nonmonotone line search techniques, Sun et al. [9] proposed a general nonmonotone line search rule, called nonmonotone F-rule, for unconstrained optimization. For solving systems of equations, Ataee Tarzanagh et al. in [4] and Reza Peyghami and Ataee Tarzanagh in [10] developed a new nonmonotone term according to(8)Tk=1+ηkRk=1+ηkεkflk+1−εkfk,where εk∈εmin,εmax⊂0,1 and fk=fxk. Moreover, flk is Grippo’s nonmonotone term which is defined by(9)flk=max0≤j≤lkfk−j,where l0=0, and for k≥1, 0≤lk≤mink,M, where M is a given positive integer, and ηk is a vanishing positive sequence satisfying the following condition:(10)∑k=1∞ηk=η<∞.Note that, for(11)Rk=εkflk+1−εkfk,they proved the weak convergence property(12)liminfk⟶∞gk=0.The main contribution of the proposed algorithm in this article is to use function derived value to improve the sequencing process. We introduce an adaptive nonmonotone technique which has a strong convergence property,(13)limk⟶∞gk=0,and can control the convex combination of function values better than previous methods. Numerical experiments will show the efficiency of the proposed line search technique. Numerical experiments indicate the efficiency and robustness of the new proposed technique.The remainder of this article is organized as follows: In Section2, we present our proposed adaptive nonmonotone rule and in Section 3, we present the convergence property it. The numerical results and conclusions are given in Sections 4 and 5, respectively.


## 2. Algorithmic Structure

The following assumption is imposed throughout the article.Assumption 1.
fx is bounded below on the level set ℒ=x∈ℝn|fx≤fx0 and ▽fx is continuous uniformly on an open set that contains the level set ℒ.
In order to attain global convergence, we need the search direction satisfying the following assumption.Assumption 2.
(14)−gkTdkdk≥σgk,k=1,2,…,where σ⋅ is a forcing function that we bring it later.Assumption 3.
The matrixJx is uniformly nonsingular on ℒ, i.e., there exists a constant M0>0 such that(15)M0FX≤JxTFx=gx,∀x∈ℒ.
In the following, we give forcing function definition as in [9].Definition 1.
The functionσ:0,+∞⟶0,+∞ is a forcing function (F-function) if for any sequence ti⊂0,+∞(16)limi⟶∞σti=0implieslimi⟶∞ti=0.
We define the new nonmonotone line search method as follows:(17)fxk+αkdk≤ℋk−σtk,set xk+1=xk+αkdk, that(18)ℋk=1+μkCk=1+μkgkkfℓk+1−gkkfk,gk≤1,1−gk−kfℓk+gk−kfk,gk>1,fℓk=∑r=0ℓk−1λkrfxk−r,where ℓk=mink,Mk,λkr≥λ,r=1,2,…,ℓk−1,λ∈0,1and∑r=0ℓk−1λkr=1, that(19)Mk=gk+c,gk<10,10,gk≥10,where [.] denotes the floor function and 0<c<1, and μk is a vanishing positive sequence satisfying the following condition:(20)∑k=1∞μk=μ<∞,and σtk is a forcing function and tk=gkTdk/dk. So(21)fα≤ℋk+αρgkTdk,where 0<ρ<1. By using Definition 2.3. and Proposition 2.4. in [9], the nonmonotone line search rules (21) easily satisfy the new nonmonotone rule (17). M is updated by (19) in each iteration. We present now a high-level description of our proposed algorithm called adaptive nonmonotone line search technique (ANLS).
With variableJ in Algorithm 1, we try to avoid the extra iteration.Algorithm 1: ANLS (adaptive nonmonotone line search).
Input:Givenx0∈ℝn, constantε>0, σ>0, ℓ0=1, ρ∈0,1, β∈0,1, J∈ℕ, N∈ℕ;Output:x∗; f∗;begink:=0;xk+1=x+;fk=fxk;gk=gxk;Hk=HxkHessian matrix offk;whilefk≥εandk≤NdoifHkis singularthendk=−gkelsedk=−Hk∖gk∖is matrix division;ifgkTdk<σdkgkthendk=−gk;elseifgkTdk>0thendk=−dkordk=−0.5dk+gk;endendendα=1; j=0; computefα=fxk+αdk, δ=ρgkTdkandℋkby (18);while 1 doj=j+1;iffα≤ℋk+αδorj==J,break;end; thenα:=βα; x+=xk+αdk;computefαx+;endendxk+1=x+;fk+1:=fαxk+1;ℓk:=mink+1,Mk;k:=k+1;endx∗:=xk; f∗:=fx∗;end


## 3. Global Convergence

In this section, we render the global convergence of our algorithm. In our proofs, we employ the method used in [11].Lemma 1.
Let sequencexkk≥0 be a sequence generated by Algorithm 1; then the following inequality holds:(22)fxk≤1+μ0kfx0−λ∑r=0k−1σtr.Proof.
Let us begin our proof by induction.
Ifk=1, from (17), we have from λ≤1 that(23)fx1≤1+μ0fx0−λσt0.
Suppose that (22) holds for all 1,2,…,k. To continue the proof, we consider two cases:Case 1:gk≤1By hypothesis of induction and−λ∑r=0k−2σtr−σtk−1≤−λ∑r=0k−1σtr for k≥2:(24)fxk+1=fxk+αkdk≤1+μkgkk∑r=0ℓk−1λkrfxk−r+1−gkkfk−σtk≤1+μkgkk∑p=0qλkpfxk−p+1−gkk1+μ0kfx0−λ∑r=0k−1σtr−σtk≤1+μkgkk∑p=0qλkp1+μ0k−pfx0−λ∑r=0k−p−2σtr−σtk−p−1+1−gkk1+μ0kfx0−λ∑r=0k−1σtr−σtk.By using0,1,2,…,q×0,1,2,…,k−q−2⊂p,r;0≤p≤q,0≤r≤k−q−2 and ∑p=0qλkp=1, λkp≥λ, we have(25)fxk+1≤1+μkgkk1+μ0k−pfx0−λ∑r=0k−q−2∑p=0qλkpσtr−∑p=0qλkpσtk−p−1+1−gkk1+μ0kfx0−λ∑r=0k−1σtr−σtk≤1+μkgkk1+μ0k−pfx0−λ∑r=0k−q−2σtr−λ∑r=k−q−1k−1σtr+1−gkk1+μ0kfx0−λ∑r=0k−1σtr−σtk=1+μkgkk1+μ0k−pfx0−λ∑r=0k−1σtr+1−gkk1+μ0kfx0−λ∑r=0k−1σtr−σtk≤1+μkgkk1+μ0kfx0−λ∑r=0k−1σtr+1−gkk1+μ0kfx0−λ∑r=0k−1σtr−σtk=1+μk1+μ0kfx0−λ∑r=0k−1σtr−σtk≤1+μk1+μ0kfx0−λ∑r=0kσtr≤1+μ0k+1fx0−λ∑r=0kσtr.Case 2:gk>1
Inasmuch asgk−1<1, the proof is the same as in the first case.Now by using Lemma1, we establish a strong global convergence theorem for our new nonmonotonte algorithm.Theorem 1.
Let assumptions1–3 are satisfied and xk be a the sequence generated by Algorithm 1. Then xk⊆ℒ and(26)limk⟶∞Fk=0.Proof.
From Lemma1, we know that xk∈ℒ for all k. Since fx is bounded below on ℒ, Lemma 1 means(27)λ∑r=0kσtr≤1+μ0k+1fx0−fxk+1.
Then ask⟶∞, we have(28)λ∑r=0∞σtr<∞,so that(29)limk⟶∞σtk=0.
From Definition1, we have(30)limk⟶∞tk=limk⟶∞−gkTdkdk=0.
Using Assumption2, we conclude(31)limk⟶∞σgk=0,which implies limk⟶∞gk=0. Thus, by Assumption 3, the proof is completed.


## 4. Numerical Experiments

In order to assess the computational efficiency of the presented method, we focus on providing some numerical results of our algorithm, denoted by ANLS, and compare the results with DFU-PRP in [4]. We tested algorithms by following a set of examples. Our algorithms stop if the termination condition fk≤10−11 is satisfied. All of the test problems are taken from [12] and the calculations were carried out using MATLAB.Problem a. Problem 8(32)x12+x22−25=0,x1x2−9=0,x0=1,12T.Problemb. Problem 26(33)1+x222x1+x34−3=0,x0=−10,−10,−10T.Problemc. Problem 39(34)x2−x13−x32=0,x12−x2−x42=0,x0=2,2,2,2T.Problemd. Problem 40(35)x13+x22−1=0,x12x4−x3=0,x42−x2=0,x0=1,12,13,14T.Probleme. Problem 61(36)3x1−2x22−7=0,4x1−x32−11=0,x0=0.1,0.1,0.1T.Problemf. Problem 81(37)x12+x22+x32+x42+x52−10=0,x2x3−5x4x5=0,x13+x23+1=0,x0=−1,−1,−1,−1,−1T.Problemg. Problem 111(38)ex1+2ex2+2ex3+ex6+ex10−2=0,ex4+2ex5+ex6+ex7−1=0,ex3+ex7+ex8+2ex9+ex10−1=0,x0=1,12,13,…,110T.Algorithm1 takes advantages parameters σ=10−5, ρ=10−3, β=0.6, ε=10−5, c=0.9, μk=gk/k!, λkr=1/ℓk, J=7, and r=0,1,…,ℓk−1. Let nf be the number of function evaluations and ni be the number of iterations as two cost measures to compare the proposed algorithms. Moreover, the sign F means that the total number of the number of function evaluations and gradient evaluations exceeds 10,000.In this table, the values of the DFU-PRP method are according to the numerical result in the appendix table in [4]. It is obvious from Table 1 that the ANLS algorithm shows better performance than the DFU-PRP algorithm.Table 1
Numerical results.
Problemsni/nf(DFU-PRP)fx∗ni/nf(ANLS)fx∗A14/177.63e − 107/103.4862e − 07B78/2107.77e − 1313/143.8652e − 07C250/7175.42e − 095/64.2731e − 06DF/F—3/41.0868e − 06EF/F—4/65.8224e − 07fF/F—8/121.5056e − 07g358/19104.99e − 0981/5464.8625e − 06


## 5. Conclusions

In this article, we propose a combined algorithm of the gradient and Newton’s methods for solving a system of nonlinear equations. We have considered a new combination and different from others in the literature. The numerical results demonstrate that the developed algorithm is more effective than the other similar ones. We will extend this algorithm to the trust region method in our future research.



---

*Source: 7134561-2021-08-27.xml*