# A Novel Filled Function Method for Nonlinear Equations

Authors: Liuyang Yuan; Qiuhua Tang
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

A novel filled function method is suggested for solving box-constrained systems of nonlinear equations. Firstly, the original problem is converted into an equivalent global optimization problem. Subsequently, a novel filled function with one parameter is proposed for solving the converted global optimization problem. Some properties of the filled function are studied and discussed. Finally, an algorithm based on the proposed novel filled function for solving systems of nonlinear equations is presented. The objective function value can be reduced by quarter in each iteration of our algorithm. The implementation of the algorithm on several test problems is reported with satisfactory numerical results.


---

## Body

## 1. Introduction

Systems of nonlinear equations arise in myriad applications, for example, in engineering, physics, mechanics, applied mathematics and sciences; see [1] for a more detailed description.In this paper, we consider the following box-constrained systems of nonlinear equations (for short,(SNE)):
(SNE)F(x)=0,x∈X,
where the mapping F:Rn→Rm is continuous, x⊂Rn is a box.Generally, systems of nonlinear equations are very difficult to solve directly. The typical methods to solve(SNE) are optimization-based methods in which (SNE) is reformulated as an optimization problem. The most popular optimization-based methods involve solving the following optimization problem (for short (OP)):
(OP)min⁡f(x)=12F(x)TF(x)s.t.x∈X
to find solutions of (SNE). Note that the problem above is a box-constrained nonlinear least-squares problem. It is easy to see that the objective function satisfies f(x)≥0 and global optimal solutions of problem (OP) with the zero objective function value corresponding to solutions of (SNE).Generally speaking, the traditional optimization-based methods for solving(SNE) are often stuck at a stationary point or a local minimizer of the corresponding optimization problem, which is not necessarily a solution of the original system. Lately, great efforts have been made to overcome the difficulty caused by nonglobal minimizers. In Particular, some switching techniques [2–6] have been developed to escape from a stationary point or a local minimizer which is not a solution of (SNE).Kanzow [3] incorporated two well-known global optimization algorithms, namely, a tunneling [7] and a filled function method [8], into a standard nonsmooth Newton-type method for solving a nonsmooth system of equations which is a reformulation of the mixed complementarity problem. Wu et al. [9] and Lin et al. [10, 11] also gave some filled function methods to solve a nonlinear system with box constraints. Wang et al. [12] gave a filled function method to solve an unconstrained nonlinear system. In this paper, we will propose another kind of filled function method to solve box-constrained systems of nonlinear equations. Unlike [3], we do not use any Newton-type methods to solve (SNE), and, also unlike [9, 10], a better initial point of the primal optimization problem sometimes can not be obtained by minimizing the constructed filled function locally. Moreover, unlike [11, 12], the exponential term was used in the construct of the filled function, which may increase the computability when applied to numerical optimization. Instead, in this paper, we use an efficient filled function method to solve the corresponding optimization problem, and the local minimizer of the filled function is always obtained in the interior and is always good point. The objective function value can be reduced by quarter in each iteration of our algorithm.The existence of local minimizers other than global ones makes global optimization a great challenge. As one of the main methods to solve general unconstrained or box-constrained global optimization problems without special structural property, the filled function method has attracted extensive attention; see [8–15]. The main idea of the filled function method is to construct an auxiliary function called filled function via the current local minimizer of the original optimization problem, with the property that the current local minimizer is a local maximizer of the constructed filled function and a better initial point of the primal optimization problem can be obtained by minimizing the constructed filled function locally. However, generally speaking, the local minimizer of the filled function cannot ensure that it is a better point of the primal optimization problem. In the paper, we propose a new filled function method, which can ensure that the proposed function is an efficient filled function and the local minimizer of the new filled function on a given box set is a better point and the primal problem's objective value at this better point can be reduced by quarter in each iteration of our filled function algorithm.The numerical results obtained show that our method is applicable and efficient. The paper is organized as follows. Following this introduction, a novel filled function is proposed for the optimization problem in Section2. The corresponding algorithm is presented in Section 3. In Section 4, several numerical examples are reported. Finally, some conclusions are drawn in Section 5.


## 2. Filled Function for the Optimization Problem

Throughout this paper we make the following assumption.Assumption 1.
(
SNE
) has at least one solution in X and the number of solutions of (SNE) is finite.Suppose thatx* is a local miminizer of problem (OP), the definition of the filled function is as follows.Definition 2.
A continuously differentiable functionp(x,x*) is called a filled function of problem (OP) at x*, if it satisfies the following conditions: (1)
x* is a strict local maximizer of p(x,x*) on X;(2)
p(x,x*) has no stationary point in the region S1={x:f(x)>f(x*)/4,x∈X∖{x*}};(3)
Ifx* is not a global minimizer of problem (OP), then p(x,x*) does have a minimizer in the region S2={x:f(x)≤f(x*)/4,x∈X}.These conditions of the new filled function ensure that when a descent method, for example, the steepest descent method, is employed to minimize the constructed filled function, the sequence of iteration points will not terminate at any point at which the objective function value is large thanf(x*)/4; if x* is not a global minimizer of problem (OP), then there must exist a minimizer of the filled function at which the objective function value is less than or equal to f(x*)/4, namely, any local minimizer of p(x,x*) must belong to the set S2={x:f(x)≤f(x*)/4,x∈X}. Therefore, the present local minimizer of the objective function escapes and a better minimizer can be found by a local search algorithm starting from the minimizer of the filled function.LetL(P) denote the set of local minimizers of problem (OP) and let G(P) denote the set of global minimizers of problem (OP).In the following, a novel filled function with one parameter satisfying Definition2 is introduced. To begin with, we design a continuously differentiable function h(t) with the following properties: it is equal to 0 when t>0.More specifically, we constructh(t) as follows:
(1)h(t)={0,t>0,t2,t≤0.It is not difficult to check thath(t) is continuously differentiable and decreasing on R. Obviously, we have
(2)h′(t)={0,t>0,2t,t≤0.Givenx*∈L(P), the following filled function with one parameter is constructed:
(3)F(x,x*,q)=11+∥x-x*∥+qh(f(x)-f(x*)4),
where the only parameter q>0. Clearly, F(x,x*,q) is continuously differentiable on Rn.The following theorems show thatF(x,x*,q) satisfy Definition 2 when the positive parameter q is sufficiently large.Theorem 3.
Letx*∈L(P), q>0. Then, x* is a strict local maximizer of F(x,x*,q) on X.Proof.
Sincex*∈L(P), there exists a neighborhood N(x*,σ) of x* with σ>0 such that f(x)≥f(x*), for all x∈N(x*,σ), where N(x*,σ)={x∣∥x-x*∥<σ}. Then, for any x∈N(x*,σ), x≠x*, q>0, and h(t)≥0. We have
(4)F(x,x*,q)=11+∥x-x*∥<1=F(x*,x*,q).
Thus, x* is a strict local maximizer of F(x,x*,q) on X.Theorem3 reveals that the proposed new filled function satisfies condition (1) of Definition 2.Theorem 4.
Letx*∈L(P), q>0. Then, F(x,x*,q) has no stationary point in the region S1={x:f(x)>f(x*)/4,x∈X∖{x*}}.Proof.
Assume thatx-∈S1, namely, f(x-)>f(x*)/4 and x-≠x*.
Then, we have(5)∇F(x-,x*,q)=-(x--x*)(1+∥x--x*∥)2∥x--x*∥,∇F(x-,x*,q)(x--x*)∥x--x*∥=-1(1+∥x--x*∥)2<0.
It implies that the function F(x,x*,q) has no stationary point in the region S1={x:f(x)>f(x*)/4,x∈X∖{x*}}.Theorem4 reveals that the proposed new filled function satisfies condition (2) of Definition 2.Theorem 5.
Letx*∈L(P), but x*∉G(P). And (SNE) satisfies Assumption 1. Then, F(x,x*,q) does have a minimizer in the region S2={x:f(x)≤f(x*)/4,x∈X} when q>0 is sufficiently large.Proof.
Sincex*∈L(P), but x*∉G(P), and the global minimum of f(x) is zero, there exists an x-*∈L(OP) such that f(x-*)≤f(x*)/4. By the continuity of f(x) and Assumption 1, there exists σ>0 that is small enough and x-∈N(x-*,σ), and it holds f(x-*)≤f(x)≤f(x*)/4=f(x-), for all x∈N(x-*,σ), where N(x-*,σ)={x∈X:∥x-x-*∥<σ}.
Here, we just give the proof to the case when∥x--x*∥≤∥x-*-x*∥. For the other case when ∥x--x*∥>∥x-*-x*∥, the proof is similar.
Therefore, for eachx∈N(x-,σ)={x∈X:∥x-x-∥<σ}, there are two cases: (1)
f(x)>f(x-)=f(x*)/4;(2)
f(x)≤f(x-)=f(x*)/4.For case (1), by f(x)-f(x*)/4>f(x-)-f(x*)/4=0 and ∥x-x*∥<∥x--x*∥,
(6)F(x,x*,q)=11+∥x-x*∥>11+∥x--x*∥=F(x-,x*,q).
For case (2), by f(x)-f(x*)/4≤f(x-)-f(x*)/4=0 and ∥x--x*∥<∥x-x*∥, we have F(x-,x*,q)<F(x,x*,q) if and only if
(7)11+∥x--x*∥<11+∥x-x*∥+q(f(x)-f(x*)4)2,
which is equivalent to
(8)q>∥x-x*∥-∥x--x*∥(f(x)-f(x*)/4)2(1+∥x--x*∥)(1+∥x-x*∥)>0.
Let
(9)q0=∥x-x*∥-∥x--x*∥(f(x)-f(x*)/4)2(1+∥x--x*∥)(1+∥x-x*∥).
Thus, there exists sufficiently large q0>0 as function f(x) approaches f(x*)/4. Consequently, it must has that F(x-,x*,q)<F(x,x*,q) for all x∈N(x-,σ) when q>q0. Thus, x-∈S2 is a minimizer of F(x,x*,q) when q>0 is sufficiently large.Theorems5 show that, for all q≥q0, F(x,x*,q) satisfies Condition (3) of Definition 2. The following theorems show that function F(x,x*,q) has some interesting properties.Theorem 6.
Letx1,x2∈X and the following conditions hold: (i)
min⁡{f(x1),f(x2)}≥(1/4)f(x*);(ii)
∥x2-x*∥>∥x1-x*∥.Then, the inequality F(x1,x*,q)>F(x2,x*,q) holds for all q>0.Proof.
Sincemin⁡{f(x1),f(x2)}≥(1/4)f(x*), then
(10)F(x1,x*,q)=11+∥x1-x*∥,F(x2,x*,q)=11+∥x2-x*∥.
Therefore, for all q>0, F(x1,x*,q)>F(x2,x*,q) holds.Theorem 7.
F
(
x
,
x
*
,
q
)
>
0 for all x∈X.Proof.
By the form of the filled function (3) and since h(t)≥0, we have F(x,x*,q)>0 for all x∈X.Remark 8.
In the phase of minimizing the filled function, Theorems3–5 guarantee that the present local minimizer x* of the objective function is escaped and the minimum of the filled function will be always achieved at a point where the objective function value is not greater than the quarter of the current minimum of the objective function. Moreover, the proposed filled function does not include exponential terms. A continuously differentiable function is used in the constructed filled function, which possesses many good properties and is efficient in numerical implementation.


## 3. Filled Function Algorithm

The theoretical properties of the proposed filled functionF(x,x*,q) were discussed in the last section. In this section, a global optimization method for solving problem (OP) is presented based on the constructed filled function (3), which leads to a solution or an approximate solution to (SNE).Suppose that(SNE) has at least one solution and the number of solutions is finite. The general idea of the global optimization method is as follows.Letx0∈X be a given initial point. Starting from this initial point, a local minimizer x0* of problem (OP) is obtained with a local minimization method (Newton method, Quasi-Newton Method, or Conjugate Gradient method). If x0* is not a global minimizer, the main task is to find a better local minimizer of problem (OP).Consider the following filled function problem (for short(FFP)):
(FFP)min⁡x∈XF(x,xk*,q),
where F(x,xk*,q) is given by (3).Letx-0* be a obtained local minimizer of problem (FFP) on X, and then by Theorem 5, we have f(x-0*)≤f(x0*)/4. Starting from this initial point x-0*, we can obtain a local minimizer x1* of problem (OP). If x1* is a global minimizer (namely, f(x1*)=0), x1* is the solution of the system (SNE); otherwise, locally solve problem (FFP). Let x-1* be the obtained local minimizer, and then we have that f(x-1*)≤f(x0*)/42. Repeating this process, we can finally obtain a solution of the system (SNE) or a sequence {x-k*} with f(x-k*)<f(x0*)/4k, k=1,2,…. For such a sequence {x-k*}, k=1,2,…, when k is sufficiently large, x-k* can be regarded as an approximate solution of the system (SNE).Letx*∈X and ϵ>0, and x* is called a ϵ-approximate solution of the system (SNE) if x*∈X and f(x*)≤ϵ.The corresponding filled function algorithm for the global optimization problem(OP) is described as follows. The algorithm is referred as FFSNE (the filled function method for (SNE)).Algorithm FFSNEStep  0. Choose small positive numbers ϵ, λ, a large positive number qU, and an initial value q0 for the parameters q. (e.g., ϵ=10-8, λ=10-5, qU=1020, and q0=1010). Choose a positive integer number K (e.g., K=2n) and directions ei, i=1,…,K, are the coordinate directions. Choose an initial point x0∈X. Set k≔0.Iff(x0)≤ϵ, then let xk*≔x0 and go to Step 6. Otherwise, let q≔q0 and go to Step 1.Step 1.
Find a local minimizerxk* of the problem (OP) by local search methods starting from xk. If f(xk*)≤ϵ, go to Step 6.Step 2.
Let(11)F(x,xk*,q)=11+∥x-xk*∥+qh(f(x)-f(xk*)4),
where h(t) is defined by (1). Set l=1 and u=0.1.Step 3.
Consider(a)
Ifl>K, set q≔10q, and go to Step 5; otherwise, go to (b).(b)
Ifu≥λ, set ykl≔xk*+uel, and go to (c); otherwise, set l≔l+1, u=0.1, go to (a).(c)
Ifykl∈X, go to (d); otherwise, set u≔u/10, go to (b).(d)
Iff(ykl)≤f(xk*)/4, then set xk+1≔ykl, k≔k+1, and go to Step 1; otherwise, go to Step 4.Step 4.
Search for a local minimizer of the following filled function problem starting fromykl:
(12)min⁡x∈RnF(x,xk*,q).
Once a point yk*∈X with f(yk*)≤f(xk*)/4 is obtained in the process of searching, set xk+1≔yk*, k≔k+1 and go to Step 1; otherwise continue the process. Let x-k* be an obtained local minimizer of problem (12). If x-k* satisfies f(x-k*)≤f(xk*)/4, then set xk+1≔x-k*, k≔k+1 and go to Step 1; otherwise, set u≔u/10, and go to Step 3(b).Step 5.
Ifq≤qU, go to Step 2.Step 6.
Letxs=xk* and stop.In this algorithm, the termination criteria for minimization ofF(x,xk*,q) in Step 4 can be interpreted as follows. The purpose of minimizing F(x,xk*,q) is to find a “better” point yk* in set S2={x:f(x)≤f(x*)/4,x∈X}. If it is successful, that is, the solution obtained satisfies yk*∈S2, then we can turn to Step 1 and restart to minimize the objective function with yk* as a new starting point. If in the process of searching such point is not found, we can obtain the local minimizer x-k* of F(x,xk*,q). By Theorems 4 and 5, we know that there must exist a local minimizer of F(x,xk*,q) which belongs to the set S2={x:f(x)≤f(x*)/4,x∈X}. Then, we turn to Step 1 and minimizer f(x) starting from the local minimizer x-k*. Obviously, if λ is small enough, qU is large enough, and the direction set {e1,…,eK} is large enough and xs can be obtained from algorithm FFOP within finite steps.


## 4. Numerical Experiment

In this section, several sets of numerical experiments are presented to illustrate the efficiency of algorithm FFSNE. All the numerical experiments are implemented in Matlab2010b. In our programs, the local minimizers of problem(FFP) and problem (OP) are obtained by the SQP method. Note that ∥∇f(x)∥≤10-6 is used as the terminate condition.The symbols used in Table3 are given in Table 1.Table 1
Parameter
Description
k
The number of iterations in finding thekth local minimizer
x
0
The initial point which satisfiesx0∈X
x
k
*
Thekth local minimizer which we take as a solution or an approximate solution to (SNE)
f
(
x
k
*
)
The function value off(x) in finding the kth local minimizer
F
(
x
k
*
)
The function value ofF(x) in finding the kth local minimizerThroughout our computational experiments, the parameters in algorithm FFSNE are set as(13)ε=10-8,λ=10-5,qU≔1020,q0≔1010.Problem 9 (test problem14.1.1 in [16]).
Consider(14)4x13+4x1x2+2x22-42x1-14=0,4x23+2x12+4x1x2-26x2-22=0,-5≤xi≤5,i=1,2.
There are nine known solutions as shown in [16] (see Table 2).Table 2
Sol
1
2
3
4
5
6
7
8
9
x
1
*
-
3.7793
-
3.0730
-
2.8051
-
0.2709
-
0.1280
0.0867
3.0
3.3852
3.5844
x
2
*
-
3.2832
-
0.0814
3.1313
-
0.9230
-
1.9537
2.8843
2.0
0.0739
-
1.8481Table 3
Computational results for Problems9–16.
Prob. Number
x
0
k
x
k
*
f
(
x
k
*
)
F
(
x
k
*
)
9
(
-
5
-
3
)
1
(
3.3852
0.0738
)
3.2970
×
1
0
-
9
(
-
1.9488
×
1
0
-
5
7.8830
×
1
0
-
5
)
(
2
3
)
1
(
-
0.2708
-
0.9230
)
2.9217
×
1
0
-
9
(
4.8628
×
1
0
-
5
5.8981
×
1
0
-
5
)
10
(
26
1
×
10
-
4
6
10
10
)
2
(
3.4524
×
1
0
-
3
3.1121
×
1
0
1
6.8586
×
1
0
-
2
8.5953
×
1
0
-
1
3.6963
×
1
0
-
2
)
5.4171
×
1
0
-
9
(
5.5404
×
1
0
-
6
-
1.6118
×
1
0
-
5
9.2403
×
1
0
-
5
-
2.4911
×
1
0
-
5
3.7147
×
1
0
-
5
)
11
(
0
3
)
2
(
1.4529
×
1
0
-
5
6.8831
)
4.9269
×
1
0
-
9
(
-
5.1847
×
1
0
-
6
3.7377
×
1
0
-
5
)
(
0.8000
1.5000
)
1
(
0.2994
2.8369
)
4.0955
×
1
0
-
15
(
-
7.7216
×
1
0
-
8
-
4.7209
×
1
0
-
8
)
13
(
-
1
2
-
1
2
-
1
)
1
(
0.99999
0.99999
0.99999
0.99999
1.00010
)
8.2910
×
1
0
-
11
(
5.0000
×
1
0
-
5
5.0000
×
1
0
-
5
5.0000
×
1
0
-
5
5.0000
×
1
0
-
5
5.9997
×
1
0
-
5
)
14
(
1
0
1
0
1
0
1
0
)
1
(
6.7156
×
1
0
-
1
7.4093
×
1
0
1
9.5188
×
1
0
-
1
-
3.0643
×
1
0
-
1
-
1.00000
6.0044
×
1
0
-
1
4.0461
×
1
0
-
1
-
4.0580
×
1
0
-
1
)
9.8094
×
1
0
-
9
(
-
2.1344
×
1
0
-
6
7.6246
×
1
0
-
6
1.3096
×
1
0
-
4
-
1.0054
×
1
0
-
5
-
2.9901
×
1
0
-
5
-
2.5121
×
1
0
-
5
0
0
)
15
(
6.0000
-
2.0000
)
1
(
1.8784
-
0.3458
)
1.2341
×
1
0
-
14
(
9.5452
×
1
0
-
8
1.2478
×
1
0
-
7
)
16
(
0
1
)
4
(
5.2656
×
1
0
-
1
5.0791
×
1
0
-
1
)
8.8529
×
1
0
-
11
(
1.3812
×
1
0
-
5
1.7315
×
1
0
-
6
)Problem 10 (test problem14.1.2 in [16]).
Consider(15)x1x2+x1-3x5=0,2x1x2+x1+3R10x22+x2x32+R7x2x3+R9x2x4+R8x2-Rx5=0,2x2x32+R7x2x3+2R5x32+R6x3-8x5=0,R9x2x4+2x42-4Rx5=0,x1x2+x1+R10x22+x2x32+R7x2x3+R9x2x4+R8x2+R5x32+R6x3+x42-1=0,0.0001≤xi≤100,i=1,…,5,whereR=10, R5=0.193, R6=4.10622×10-4, R7=5.45177×10-4, R8=4.4975×10-7, R9=3.40735×10-5, and R10=9.615×10-7.The known solution in [16] is (0.003431,31.325636,0.068352,0.859530,0.036963)T.Problem 11 (test problem14.1.3 in [16]).
Consider(16)104x1x2-1=0,exp⁡(-x1)+exp⁡(-x2)-1.001=0,5.49×10-6≤x1≤4.553,2.196×10-3≤x2≤18.21.
The known solution is(0.0000145067,6.89335287)T.Problem 12 (test problem14.1.4 in [16]).
Consider(17)0.5sin(x1x2)-0.25x2π-0.5x1=0,(1-0.25π)(e2x1-e)+ex2π-2ex1=0,0.25≤x1≤1,1.5≤x2≤2π.
The known solution is(0.29945,2.83693)T and (0.5,3.14159)T.Problem 13 (test problem14.1.5 in [16]).
Consider(18)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,-2≤xi≤2,i=1,…,5.
The known solution is(1,1,1,1,1)T and (0.916,0.916,0.916,0.916,1.418)T.Problem 14 (test problem14.1.6 in [16]).
Consider(19)4.731×10-3x1x3-0.3578x2x3-0.1238x1+x7-1.637×10-3x2-0.9338x4-0.3571=0,0.2238x1x3+0.7623x2x3+0.2638x1-x7-0.07745x2-0.6734x4-0.6022=0,x6x8+0.3578x1+4.731×10-3x2=0,-0.7623x1+0.2238x2+0.3461=0,x12+x22-1=0,x32+x42-1=0,x52+x62-1=0,x72+x82-1=0,-1≤xi≤1,i=1,…,8.
The are sixteen known solutions of problem 6 are given in [16].Problem 15 (test problem 1 in [17]).
Consider(20)1-2x2+0.2sin(4πx2)-x1=0,x2-0.5sin(2πx1)=0,-10≤x1,x2≤10.
The known solution is(0.1025250,0.3005036)T.Problem 16 (test problem 7 in [18]).
Consider(21)x1-0.7sin(x1)-0.2cos⁡(x2)=0,x2-0.7cos⁡(x1)+0.2sin(x2)=0,-100≤x1,x2≤100.
The known solution is(0.5268,0.5084)T.The numerical results are listed in Table3. From Table 3, it is easy to see that all problems that we tested have been solved with a small number of iterations.


## 5. Conclusions

In this paper, the filled functionF(x,x*,q) with one parameter is constructed for solving nonlinear equations and it has been proved that it satisfies the basic characteristics of the filled function definition. Promising computation results have been observed from our numerical experiments. In the future, the filled function method can be used to solve other problems such as nonlinear systems of equalities and inequalities and nonlinear feasibility problems with expensive functions.



---

*Source: 247519-2014-06-12.xml*