# Finding the Roots of System of Nonlinear Equations by a Novel Filled Function Method

Authors: Wei-Xiang Wang; You-Lin Shang; Wei-Gang Sun; Ying Zhang
Journal: Abstract and Applied Analysis
 (2011)

---

## Abstract

We present a novel filled function approach to solve box-constrained system of nonlinear equations. The system is first transformed into an equivalent nonsmooth global minimization problem, and then a new filled function method is proposed to solve this global optimization problem. Numerical experiments on several test problems are conducted and the computational results are also reported.


---

## Body

## 1. Introduction

Consider the system of nonlinear equations of the form:(SNE):F(x)=0,x∈X, where the mappingF:Rn→Rm is continuous, and X⊂Rn is a box set.DenoteF(x)=(f1(x),f2(x),…,fm(x))T, and let f(x)=Σk=1m|fk(x)|. To obtain the roots of (SNE), we may solve the following global optimization problem: (P):minx∈Xf(x). Obviously, if (SNE), has at least one root, then the global optimizers of the problem (P) with the zero function value correspond to the roots of (SNE).There are many theories and algorithms devoted to global optimization. Among of them, filled function method is a particularly useful tool (see [1–7]). The filled function method is originally introduced to solve smooth global optimization problem. In this paper, it is extended to solve nonsmooth global optimization problem (P). The filled function method for nonsmooth global optimization contains two phases: local minimization and filling. The local minimization phase is intended to search for a local optimizer x* of the problem (P), and the filling phase aims to identify an improved initial point by minimizing the following filled function constructed at x*:(FFP)minx∈XF(x,x*). The two phases are performed alternatively until no better optimizer can be found, and then the current optimizer is regarded as a global minimizer.Comparing with the filled functions proposed in [1–7], our filled function has the following features.(1)
Since the functionsfi(i=1,…,m) in this paper are assumed to be Lipschitz continuous only, and not necessarily to be continuous differentiable, so the problem (P) is a nonsmooth global optimization problem. Our filled function approach is proposed to tackle this kind of nonsmooth global optimization problem. Whereas these filled function methods proposed in the literature are mainly used for solving smooth global optimization problem.(2)
Although the filled function presented in [2] can be extended to solve nonsmooth global optimization problem, it has some disadvantages, such as it has two dependent parameters which are difficult to determine and hence make its algorithmic realization be fairly complicated. However, our proposed filled function contains only one parameter, which is easier to be appropriately chosen, and thus overcomes the disadvantages mentioned above in a certain extent.(3)
If eachfi is continuous differentiable and f(x)=Σk=1mfk2(x), then problem (P) is a smooth optimization problem. In this case, our proposed filled function method can also be used to solve this smooth problem, just as the above-mentioned filled function methods can do. Therefore, our filled function method is a natural extension of these filled function methods in the literature, and it has more scope of applications in the field of global optimization.The paper is organized as follows: in Section2, we make several assumptions on the problem. In Section 3, we present a novel filled function and investigate its properties. In Section 4, we describe the filled function algorithm. In Section 5, we make a numerical test. And, at last, in Section 6, we give our conclusion.


## 2. Basic Knowledge

In this section, we give a summary of main results on nonsmooth analysis, and define filled function for the problem(P). For more details, we refer the reader to [8].Definition 2.1.
Letf be Lipschitz with constant L at the point x, the generalized gradient of f at x is defined as
(2.1)∂f(x)={ξ∈Rn:〈ξ,d〉≤f0(x;d),∀d∈Rn},
where f0(x;d)=limsupy→x,t↓0(f(y+td)-f(y))/t is the generalized directional derivative of f(x) in the direction d at x.Lemma 2.2.
Letf be Lipschitz with constant L at the point x, then(a)
f0(x;d) is finite, sublinear and satisfies |f0(x;d)|≤L∥d∥,(b)
as a function of(x,d),f0(x;d) is super-semicontinuous; as a function of d, it is Lipschitz with constant L,(c)
∂Σsifi(x)⊆Σsi∂fi(x), ∀si∈R,(d)
∂f(x)is a nonempty compact convex set, and to any ξ∈∂f(x), one has ∥ξ∥≤L,(e)
∀d∈X, f0(x;d)=max{〈ξ,d〉:ξ∈∂f(x)}.Consider the problem(P). To extend the filled function for smooth global optimization to nonsmooth case, throughout this paper, we make the following assumptions.Assumption 1.
The functionfi(x)(i=1,2,…,m) is Lipschitz continuous on X with a rank Li>0. Then f(x) is Lipschitz continuous with a rank L=∑i=1mLi.Assumption 2.
The value off(x) for x on the boundary of X is greater than that of f(x) for any x within X.Note that Assumption2 implies that all optimizers of (P) lie in the interior of X.Assumption 3.
The problem(SNE) has at least one root.Definition 2.3.
A functionP(x,x*) is called a filled function of f(x) at a local minimizer x*, if it has the following properties:  (1)
f(x) is a strictly maximizer of P(x,x*),(2)
for anyx∈S1={x∈X∖x*:f(x)≥f(x*)}, one has 0∉∂P(x,x*),(3)
ifx* is not a global minimizer of (P), then P(x,x*) has at least one minimizer in the region S2={x∈X:f(x)<f(x*)}.


## 3. A New Filled Function and Its Properties

Letx* be a local minimizer of (P), L the Lipschitz rank of f(x), and D=maxx1,x2∈X∥x1-x2∥. Define (3.1)F(x,x*,r)=(arctanf(x)-15arctanf(x*))exp⁡(r‖x-x*‖+1),
where r>0 is a parameter.Next, we will prove thatF(x,x*,r) is a filled function under mild conditions.Lemma 3.1.
Letg(t)=(Lt+(4/5)arctanf(x*))exp(r/(t+1)), where  0≤t≤D. If  r is an appropriately large such that  r>(5L(D+1)2/4arctanf(x*)), then  g(t) is strictly monotone decreasing on  [0,D].Proof.
Sincer>(5L(D+1)2/4arctanf(x*)), then we have
(3.2)g′(t)=exp⁡(rt+1)[L-(Lt+45arctanf(x*))r(t+1)2]≤exp⁡(rt+1)[L-45arctanf(x*)r(t+1)2]≤exp⁡(rt+1)[L-45arctanf(x*)r(D+1)2]<0,
which implies that g′(t)<0, and g(t) is strictly monotone decreasing on [0,D].Theorem 3.2.
Letx* be a local minimizer of f(x) with f(x*)>0. Suppose that Assumption 2 holds and r>0 is appropriately large such that r>(5L(D+1)2/4arctanf(x*)), then x* is a strict local maximizer of F(x,x*,r).Proof.
Sincex* is a local minimizer of f(x) over X, there exists a neighborhood O(x*,δ) of x* with δ>0 such that f(x)≥f(x*) for all x∈O(x*,δ)⋂X.
For anyx∈O(x*,δ)⋂X with x≠x*, if r>0 is appropriately large such that r>(5L(D+1)2/4arctanf(x*)), then, by Lemma 3.1 and the fact that the following inequality holds for b≥a,
(3.3)arctanb-arctana≤b-a,
we have that
(3.4)F(x,x*,r)=exp⁡(r‖x-x*‖+1)(arctanf(x)-15arctanf(x*))≤exp⁡(r‖x-x*‖+1)(f(x)-f(x*)+45arctanf(x*))≤exp⁡(r‖x-x*‖+1)(L‖x-x*‖+45arctanf(x*))<exp⁡(r)45arctanf(x*)=F(x,x*,r).
Therefore, x* is a strict local maximizer of F(x,x*,r).Theorem 3.3.
Letx* be a local minimizer of f(x) with f(x*)>0. Suppose that r>0 is suitably large such that r>(5L(D+1)2/4arctanf(x*)), then 0∉∂F(x,x*,r), for all x∈S1.Proof.
For anyx∈S1, that is, f(x)≥f(x*) and x≠x*, we have
(3.5)∂F(x,x*,r)⊂exp⁡(r‖x-x*‖+1)[11+f2(x)∂f(x)-arctanf(x)-(1/5)arctanf(x*)(‖x-x*‖+1)2r(x-x*)‖x-x*‖],〈∂F(x,x*,r),x-x*‖x-x*‖〉⊂exp⁡(r‖x-x*‖+1)[〈11+f2(x)∂f(x),x-x*‖x-x*‖〉-rarctanf(x)-(1/5)arctanf(x*)(‖x-x*‖+1)2]≤exp⁡(r‖x-x*‖+1)[L-r(4/5)arctanf(x*)(D+1)2]<0,
since ∥∂f(x)∥≤L, and r>(5L(D+1)2/4arctanf(x*)).
It follows that0∉∂F(x,x*,r) for all x∈S1.Theorem 3.4.
Assume that Assumptions2 and 3 hold, x* is a local optimizer with f(x*)>0 and is not a global optimizer of f(x) over X. Then there exists a point x0∈S2 such that x0 is a minimizer of F(x,x*,r) over X.Proof.
Since Assumption3 holds and x* is not a global minimizer of f(x), there exists one point x1* with f(x1*)=0 such that f(x*)>f(x1*). Denote the boundary of X by ∂X. Then, by Assumption 2, for any x∈∂X, it holds F(x,x*,r)>F(x1*,x*,r). Suppose that F(x,x*,r) attains its minimum at the point x0∈X, then we have
(3.6)min⁡x∈XF(x,x*,r)=min⁡x∈X∖∂XF(x,x*,r)=F(x0,x*,r)≤F(x1*,x*,r)<0.
Since X∖∂X is an open set, we have x0∈S2. This completes the proof.


## 4. Solution Algorithm

Based on the discussion of the theoretical properties of the above-proposed filled function, we describe a filled function algorithm for solving(SNE) as follows.Filled function algorithm:Initialization Step
LetrU=105 be a termination scalar. Choose an initial point x1. Let e1,e2,…,e2n be the coordinate directions. Set k=1, and go to the main step.Main Step
(1)
Start fromx1, solve the problem (P) by using any nonsmooth local minimization procedure. Denote x1* the obtained optimizer, and go to (2).(2)
Letr=1, construct the filled function F(x,x*,r) and go to (3).(3)
Ifk≤2n, then set x=x1*+0.1ek, and use x as an initial point for a nonsmooth local minimization method to find a local minimizer xk of the following problem: minx∈XF(x,x*,r). If x attains the boundary of X during minimization, then set k=k+1, and repeat (3); otherwise, go to (4).(4)
If all the following conditions hold, then setx=xk,k=1, use x as an initial point to get another local solution x2* of problem (P), and go to (5); otherwise go to (6),
(a)
f(xk)<f(x1*);(b)
F(xk,x1*,r)>F(xk-1,x1*,r);(c)
(xk-x1*)Tξ≥0,∀ξ∈∂F(xk,x1*,r);(d)
∥ξ∥<10-4,ξ∈∂F(xk,x1*,r).(5)
Iff(x)<f(x1*), then set x1*=x2*, and go to (2); otherwise, go to (6).(6)
Increaser by setting r=10r. If r≤rU, then set k=1, and go to (2); otherwise, the algorithm is incapable of finding a better local minimizer, the algorithm stops, and x1* is taken as a global minimizer.Remarks 4.
The above filled function algorithm consists of two phases: local minimization and filling. The local minimization phase is intended to minimize problem(P) by applying non-smooth local optimization algorithms, such as hybrid Hooke and Jeeves-Direct method for nonsmooth Optimization [9], mesh adaptive direct search algorithms for constrained optimization [10], bundle methods, and Powell's method. The filling phase aims to search for a point xk with f(xk)<f(x1*) by minimizing the filled function F(x,x*,r) over X. Once such kind of point is found in the process of minimization, the filling phase stops and the algorithm returns to the phase of local minimization. The two phases perform repeatedly until the certain conditions are satisfied.


## 5. Numerical Experiment

In this section, we perform the numerical experiments for four test problems by using the proposed filled function algorithm. All the numerical experiments are implemented in the FORTARN 95 environment. The hybrid Hooke and Jeeves-Direct method is used to search for the local minimizers of both the objective function and the filled function. Numerical results demonstrate that the proposed filled function approach is promising.Problem 1.
It holds that(5.1)4x13+4x1x2+2x22-42x1-14=0,4x23+4x1x2+2x12-26x2-22=0,s.t.-5≤x1,x2≤5.There are nine known roots as shown in [11]. Table 1 records the numerical results obtained by our algorithm for Problem 1.Table 1
Computational results for Problem1.
kxk0xk*f(xk*)F(xk*)1(4.00004.0000)(3.00001.9999)5.3020×10-3(-2.0006×10-3-3.3013×10-3)2(0.08662.8843)(0.08662.8842)2.7777×10-3(2.6285×10-31.4689×10-4)3(3.38520.0738)(0.08662.8843)3.7337×10-3(2.9451×10-42.4391×10-3)Problem 2.
It holds that(5.2)104x1x2-1=0,e-x1+e-x2-1.001=0,s.t.5.49×10-6≤x1≤4.553,2.196×10-3≤x2≤18.21.The algorithm successfully finds a root of the Problem2: (1.4564×10-5,6.8753). Table 2 records its numerical results.Table 2
Computational results for Problem2.
kxk0xk*f(xk*)F(xk*)1(2.00006.0000)(0.00006.8753)3.4105×10-4(-1.0000-3.3252)2(9.9999×10-66.9667)(1.4354×10-56.9667)7.1718×10-5(1.1803×10-7-7.1597×10-5)Problem 3.
It holds that(5.3)1-2x2+0.2sin⁡(4πx2)-x1=0,x2-0.5sin⁡(2πx1)=0,s.t.-10≤x1,x2≤10.The solution is(1.8784,-0.3458). Table 3 records the numerical results of Problem 3.Table 3
Computational results for Problem3.
kxk0xk*f(xk*)F(xk*)1(5.0000-3.0000)(4.7386-1.7417)1.5191(-0.2762-1.2428)2(2.5975-0.3301)(2.5762-0.4315)0.7627(-0.5615-0.2012)3(1.7394-0.4335)(1.8784-0.3458)2.2341×10-4(-1.1137×10-41.1203×10-4)Problem 4.
It holds that(5.4)2x1+x2+x3+x4+x5-6=0,x1+2x2+x3+x4+x5-6=0,x1+x2+2x3+x4+x5-6=0,x1+x2+x3+2x4+x5-6=0,x1x2x3x4x5-1=0,s.t.|xi|≤2,i=1,2,…,5.The known solutions of Problem4 in [11] are (1,1,1,1,1) and (0.916,0.916,0.916,0.916,0.916). Table 4 records the numerical results of Problem 4.Table 4
Computational results for Problem4.
kxk0xk*f(xk*)F(xk*)1(-1.00001.0000-1.000001.0000-1.0000)(1.00541.00551.00531.00550.9739)8.8951×10-3(1.0008×10-31.1007×10-39.0007×10-41.1003×10-3-4.7932×10-3)2(0.99350.99331.00161.01331.0127)(0.99900.99890.99910.99961.0042)1.7952×10-3(-2.0011×10-4-3.0009×10-4-1.0004×10-44.0007×10-47.9011×10-4)The symbols used in the tables are given below:k:
the iteration number in finding thekth local minimizer,xk:
thekth initial point to find the kth local minimizer,xk*:
thekth local minimizer,f(xk*):
the function value off(x) at the kth local minimizer,F(xk*):
the function value ofF(x) at the kth local minimizer.


## 6. Conclusions

In this paper, we developed a global minimization method based on filled function to identify the roots of the system of nonlinear equations. By converting a system nonlinear equations into an equivalent nonsmooth global minimization problem, we manage to search for a root or an appropriate root of the system of nonlinear equations by solving the formulated global minimization problem. A new filled function algorithm is proposed to solve the formulated global minimization problem. Numerical experiments for several test problems verify that our proposed algorithm is promising.



---

*Source: 209083-2011-11-17.xml*