# A Filled Function Approach for Nonsmooth Constrained Global Optimization

Authors: Weixiang Wang; Youlin Shang; Ying Zhang
Journal: Mathematical Problems in Engineering
 (2010)

---

## Abstract

A novel filled function is given in this paper to find a global minima for a nonsmooth
constrained optimization problem. First, a modified concept of the filled function for nonsmooth
constrained global optimization is introduced, and a filled function, which makes use of the idea of
the filled function for unconstrained optimization and penalty function for constrained optimization, is
proposed. Then, a solution algorithm based on the proposed filled function is developed. At
last, some preliminary numerical results are reported. The results show that the proposed approach
is promising.


---

## Body

## 1. Introduction

Recently, since more accurate precisions demanded by real-world problems, studies on global optimization have become a hot topic. Many theories and algorithms for global optimization have been proposed. Among these methods, filled function method is a particularly popular one. The filled function method was originally introduced in [1, 2] for smooth unconstrained global optimization. Its idea is to construct a filled function via it the objective function leaves the current local minimum to find a better one. The filled function method consists of two phase: local minimization and filling. The two phases are performed repeatedly until no better minimizer could be located. The filled function method was further developed in literature [3–9]. It should be noted that these filled function methods deal only with smooth unconstrained or box constrained optimization problem. However, many practical problems could only be modelled as nonsmooth constrained global optimization problems. To address this situation, in this paper, we generalize the filled function proposed in [10] and establish a novel filled function approach for nonsmooth constrained global optimization. The key idea of this approach is to combine the concept of filled function for unconstrained global optimization with the penalty function for constrained optimization.In general, there are two difficulties in global optimization: the first is how to leave the current local minimizer off(x) to go to a better one; the second is how to check whether the current minimizer is a global solution of the problem. Just like other GO methods, the filled function method has some weaknesses discussed in [11]. In particular, the filled function method cannot solve the second issue, so our paper focuses on the former issue.The rest of this paper is organized as follows. In Section2, some preliminaries about nonsmooth optimization and filled function are listed. In Section 3, the concept of modified filled function for nonsmooth constrained global optimization is introduced, a novel filled function is given, and its properties are investigated. In Section 4, an efficient algorithm based on the proposed filled function is developed for solving nonsmooth constrained global optimization problem. Section 5 presents some numerical results. Last, in Section 6, the conclusion is given.


## 2. Nonsmooth Preliminaries

Consider the following problem (P):(P)minx∈Sf(x),
where S={x∈X:gi(x)≤0},f,gi:X→R, i∈I={1,2,…,m}, and X⊂Rn is a box set.In this section, we first list some definitions and lemmas from [12], then we make some assumptions on f(x),gi(x),  i∈I, and finally we define filled function for problem (P).Definition 2.1.
Lettingf(x) be Lipschitz with constant L>0 at the point x, the generalized gradient of f at x is defined as
(2.1)∂f(x)={ξ∈X:〈ξ,d〉≤f0(x;d),∀d∈X},
where f0(x;d)=lim supy→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)
for alld∈X, f0(x;d)=max{〈ξ,d〉:ξ∈∂f(x)}, and to any ξ∈∂f(x), one has ∥ξ∥≤L;(c)
∂Σsifi(x)⊆Σsi∂fi(x), for all si∈R.Considering problem (P), throughout the paper, we need the following assumptions:(A1)
f(x) and gi(x), i∈I, are Lipschitz continuous with a common constant L>0.(A2)
the number of the different value of local minimizer of(P) is finite;(A3)
S∘≠∅,clS∘=S, where S∘ denotes the interior of S,clS∘ denotes the closure of S∘.Now, we give the definition of filled function for problem (P) below.Definition 2.3.
A functionP(x,x*) is called a filled function of [P] at x* if all the following conditions are met:(1)
x* is a strict local maximizer of P(x,x*) on X;(2)
P(x,x*) has no stationary points in the set S1∖x*∪(X∖S), that is, 0∉∂P(x,x*);(3)
Ifx* is not a global minimizer of problem (P), then there exists a point x1*∈S such that x1* is a local minimizer of P(x,x*) on X with f(x1*)<f(x*).


## 3. A New Filled Function and Its Properties

Consider the problem (P).Define(3.1)F(x,x*,r)=η(∥x-x*∥)+r1+[min(0,max(f(x)-f(x*),gi(x),i=1,…,m))]2,
where r>0 is a parameter, η() is a differentiable function such that η(0)=1 and η′(t)<0 for any t>0, and ∥·∥ indicates the Euclidean vector norm.Next, we will prove thatF(x,x*,r) is a filled function, where x* is the current local minimizer of problem (P).Theorem 3.1.
x* is a strict local maximizer of F(x,x*,r) on X.Proof.
Sincex* is a local minimizer of (P), there exists a neighborhood N(x*,σ*) of x* with σ*>0 such that f(x)≥f(x*) for any x∈S∩N(x*,σ*).  We consider the following two cases.Case 1 (x∈N(x*,σ*)∩S, and x≠x*).
In this case, note that(3.2)min[0,max(f(x)-f(x*),gi(x),i=1,…,m)]=0,
then
(3.3)F(x,x*,r)=η(∥x-x*∥)-1+F(x*,x*,r)<F(x*,x*,r).Case 2 (x∈N(x*,σ*)∩(X∖S)).
In this case,x≠x*; moreover, there exists at least one index i0∈1,…,n such that gi0(x)>0. It follows that
(3.4)min[0,max(f(x)-f(x*),gi(x),i=1,…,m)]=0,F(x,x*,r)=η(∥x-x*∥)+r<1+r=F(x*,x*,r).
Therefore, x* is a strict local maximizer of F(x,x*,r).Theorem 3.2.
For anyx∈(S1∖x*)∪(X∖S), one has 0∉∂F(x,x*,r).Proof.
For anyx∈(S1∖x*)∪(X∖S), similar to the proof of Theorem 3.1, we have
(3.5)min[0,max(f(x)-f(x*),gi(x),i=1,…,m)]=0.
Since x≠x*, it follows that
(3.6)∂(min[0,max(f(x)-f(x*),gi(x),i=1,…,m)])2⊂2min[0,max(f(x)-f(x*),gi(x),i=1,…,m)]×∂min[0,max(f(x)-f(x*),gi(x),i=1,…,m)]=0,∂F(x,x*,r)⊂∂η(∥x-x*∥)-∂(min[0,max(f(x)-f(x*),gi(x),i=1,…,m)])2×r(1+[min(0,max(f(x)-f(x*),gi(x),i=1,…,m))]2)2=η′(∥x-x*∥)x-x*∥x-x*∥.
Therefore, we have that
(3.7)〈∂F(x,x*,r),x-x*∥x-x*∥〉⊂〈η′(∥x-x*∥)x-x*∥x-x*∥,x-x*∥x-x*∥〉=η′(∥x-x*∥)<0.
So, to any ξ∈∂F(x,x*,r), one has ξT((x-x*)/∥x-x*∥)<0. Then 0∉∂F(x,x*,r).Theorem 3.3.
Suppose that Assumptions (1)–(3.8) are satisfied. If x* is not a global minimizer, and r>0 is appropriately large, then there exists a point xr*∈S2 such that xr* is a minimizer of F(x,x*,r).Proof.
Sincex* is not a global minimizer, there exists another local minimizer x1* of (P) such that f(x1*)<f(x*),g(x1*)≤0. By Assumption (3.1), there exists one point x2*∈intX such that f(x2*)<f(x*),g(x2*)<0. Thus, we have
(3.8)F(x2*,x*,r)=η(∥x2*-x*∥)+r1+(max(f(x2*)-f(x*),gi(x2*),i=1,…,m))2.
On the other hand, to any x∈∂S, where ∂S denotes the boundary of the set S, there exists at least one index i0∈{1,…,m} such that gi0(x)=0, which yields
(3.9)F(x,x*,r)=η(∥x-x*∥)+r.
Let M=maxx1,x2∈X∥x2-x1∥>0,N0=η(∥x2*-x*∥)-η(M)⩾0. To any x∈∂S, if r>0 is chosen to be appropriately large such that
(3.10)r>1+(max(f(x2*)-f(x*),gi(x2*),i=1,…,m))2(max(f(x2*)-f(x*),gi(x2*),i=1,…,m))2N0,
then, we have that
(3.11)F(x2*,x*,r)-F(x,x*,r)=η(∥x2*-x*∥)-η(∥x-x*∥)-r((max(f(x2*)-f(x*),gi(x2*),i=1,…,m))21+(max(f(x2*)-f(x*),gi(x2*),i=1,…,m))2)⩽η(∥x2*-x*∥)-η(M)-r((max(f(x2*)-f(x*),gi(x2*),i=1,…,m))21+(max(f(x2*)-f(x*),gi(x2*),i=1,…,m))2)⩽N0-r((max(f(x2*)-f(x*),gi(x2*),i=1,…,m))21+(max(f(x2*)-f(x*),gi(x2*),i=1,…,m))2)<0.
Denotesxr*=argminx∈SF(x,x*,r). Then, if r>0 is appropriately large such that (3.10) is met, one has
(3.12)F(xr*,x*,r)=minx∈SF(x,x*,r)=minx∈S∖∂SF(x,x*,r)≤F(x2*,x*,r).
Note that S∖∂S is an open bounded set, thus xr*∈S∖∂S and gi(xr*)<0, for i=1,…,m. Moreover, we can easily prove that f(x0*)<f(x*). In fact, if it is not true, then
(3.13)F(xr*,x*,r)=η(∥xr*-x*∥)+r>F(x2*,x*,r),
which contradicts with (3.12).
Therefore, one hasxr*∈S2. This completes the proof.


## 4. Solution Algorithm

In the previous section, several properties of the proposed filled function are discussed. Now a solution algorithm based on these properties is described as follows.Initialization Step
(1)
Choose a disturbance constantδ; for example, set δ:=0.1.(2)
Choose an upper bound ofr such that rU>0; for example, set rU:=108.(3)
Choose a constantr̂>0; for example, r̂=10.(4)
Choose directionek,k=1,2,…,k0 with integer k0≥2n, where n is the number of variable.(5)
Setk:=1.Main Step
(1)
Start from an initial pointx, minimize the primal problem (P) by implementing a nonsmooth local search procedure, and obtain the first local minimizer x1* of f(x).(2)
Letr=1.(3)
Construct the filled function:F(x,x1*,r)=η(∥x-x1*∥)+(r/1+[min(0,max(f(x)-f(x1*),gi(x),i=1,…,m))]2).(4)
If  k>k0, then go to (7). Else set x:=x1*+δek as an initial point, minimize the filled function problem by implementing a nonsmooth local search procedure, and obtain a local minimizer denoted xk.(5)
If  xk∈¯X, then set k:=k+1, go to (4). Else go to next step.(6)
If  xk satisfies f(xk)<f(x1*), then set x:=xk and k:=1, start from x as a new initial point, minimize the primal problem (P) by implementing a local search procedure, and obtain another local minimizer x2* of f(x) such that f(x2*)<f(x1*), set x1*:=x2*, go to (2). Else go to next step.(7)
Increaser by setting r:=r̂r.(8)
If  r≤rU, then set k:=1, go to (3). Else the algorithm is incapable of finding a better local minimizer. The algorithm stops and x1* is taken as a global minimizer.The motivation and mechanism behind the algorithm are explained as below.A set ofm=2n initial points is chosen in Step (4) of the Initialization step to minimize the filled function. We set the initial points symmetric about the current local minimizer. For example, when n=2, the initial points are: For example, when n=2, the directions can be chosen as (1,0),(0,1),(-1,0),(0,-1).In Step(1) and Step (6) of the Main step, we minimize the primal problem (P) by nonsmooth constrained local optimization algorithms such as penalty function method, bundle method, quasi-newton method and composite optimal method. In Step 4 of the Main step, we minimize the filled function problem by nonsmooth unconstrained local optimization algorithms such as cutting-planes method, powell method, and Hooke-Jeeve method. They are all effective methods.Recall from Theorem3.3 that the value of r should be selected large enough. Otherwise, there could be no minimizer of F(x,x1*,r) in set S2. Thus, r is increased successively in Step (7) of the solution process if no better solution is found when minimizing the filled function. If all the initial points have been used and r reaches its upper bound rU, but no better solution is found, then the current local minimizer is taken as a global one.The proposed filled function method can also apply to smooth constrained global optimization.


## 5. Numerical Experiment

In this section, we perform a numerical test to give an initial feeling of the potential application of the proposed function approach in real-world problems. In our programs, the filled function is of the form(5.1)F(x,x*,r)=exp(-∥x-x*∥)+r1+[min(0,max(f(x)-f(x*),gi(x),i=1,…,m))]2.
The proposed algorithm is programmed in Fortran 95. The composite optimal method is used to find local minimizers of the original constrained problem, and the Hooke-Jeeve method is used to search for local minimizers of the filled function problems.The main iterative results of Algorithm NFFA applying on four test examples are listed in Tables1–4. The symbols used in the tables are given as follows:k:
the iteration number in finding the kth local minimize;r:
the parameter to find the (k+1)th local minimize;xk:
thekth initial point to find the kth local minimize;xk*:
thekth local minimize;f(xk):
the function value of thekth initial point;f(xk*):
the function value of thekth local minimizer.Table 1
Numerical results for Problem 1.
krxkf(xk)xk*f(xk*)1—(-15,-2)6.1184(-15.0000,0.0000)5.716421(-1.0585,0.5165)2.1433(0.0001,-0.2094)-0.3690310(0.0007,-0.0435)-0.7470(0.0000,0.0000)-2.7183Table 2
Numerical results for Problem 2.
krxkf(xk)xk*f(xk*)1—(-1.5,1.0,-0.75)0.8125(-1.9802,-0.0130,-0.0006)-1.941021(1.1931,0.6332,-1.1931)-3.9140(1.9889,-0.0001,-0.0111)-5.9446Table 3
Numerical results for Problem 3.
krxkf(xk)xk*f(xk*)1—(2,2,2,2)42.0000(0.0000,1.0000,0.0000,2.0000)-6.000021(0.6078,2.0003,0.0003,0.0319)-22.9117(0.9289,0.8620,0.2453,0.0803)-35.99393100(0.4012,0.2524,0.2288,0.0000)-49.4733(0.0000,1.0000,1.0000,1.0000)-65.0000Table 4
Numerical results for Problem 4.
krxkf(xk)xk*f(xk*)1—(2,2,2,2,2,2)-10.0000(5,1,5,6,5,4)-262.000021(5,1,5,1.7581,5,4)-263.0269(5,1,5,0,5,4)-274.000031000(5,1,5,1.7579,5,10)-299.0286(5,1,5,0,5,10)-310.0000Problem 1.
We have(5.2)minf(x)=-20exp(-0.2|x1|+|x2|2)-exp(cos(2πx1)+cos(2πx2)2)+20s.t.x12+x22≤300,2x1+x2≤4,-30≤xi≤30,i=1,2.Algorithm NFFA succeeds in finding a global minimizerx*=(0,0)T with f(x*)=-2.7183. The numerical results are listed in Table 1.Problem 2.
We have(5.3)minf(x)=-x12+x22+x32-x1s.t.x12+x22+x32-4≤0,min{x2-x3,x3}≤0.Algorithm NFFA successfully finds an approximate global solutionx*=(1.9889,-0.0001,-0.0111)T with f(x*)=-5.9446. Table 2 records the numerical results of Problem 2.Problem 3.
We have(5.4)minf(x)=max{f1(x),f2(x),f3(x)}s.t.x12-x2-x42≤0,0≤xi≤3,i=1,…,4,
where
(5.5)fi(x)=f0(x)+10·gi(x),i=1,2,3,f0(x)=x12+x22+2x32+x42-5x1-5x2-21x3+7x4,g1(x)=x12+x22+2x32+x42+x1-x2+x3-x4-8,g2(x)=x12+2x22+x32+2x42-x1-x4-10,g3(x)=x12+x22+x32+2x1-x2-x4-5.Algorithm NFFA successfully finds a global solutionx*=(0,1,1,1)T with f(x*)=-65. The computational results are listed in Table 3.Problem 4.
We have(5.6)minf(x)=-25(x1-2)2-(x2-2)2-(x3-1)2-(x4-4)2-(x5-1)2-(x6-4)2s.t.(x3-3)2+x4≥300,(x5-3)2+x6≥4,x1-3x2≤2,-x1+x2≤2,2≤x1+x2≤6,0≤x1≤6,0≤x2≤8,1≤x3≤5,0≤x4≤6,1≤x5≤5,0≤x6≤10.The proposed algorithm successfully finds a global solutionx*=(5,1,5,0,5,10)T with f(x*)=-310. The main iterative results are listed in Table 4.


## 6. Conclusions

In this paper, we extend the concept of the filled function for unconstrained global optimization to nonsmooth constrained global optimization. Firstly, we give the definition of the filled function for constrained optimization and construct a new filled function with one parameter. Then, we design a solution algorithm based on this filled function. Finally, we perform some numerical experiments. The preliminary numerical results show that the new algorithm is promising.



---

*Source: 310391-2010-11-02.xml*