# Filter Trust Region Method for Nonlinear Semi-Infinite Programming Problem

Authors: Ke Su; Chun Xu; Lele Ren
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

We present a filter trust region method for nonlinear semi-infinite programming. Based on the discretization technique and motivated by the multiobjective programming, we transform the semi-infinite problem into a finite one. Together with the filter technique, we propose a modified method that avoids the merit function. Compared with the existing methods, our method is more flexible and easier to implement. Under some mild conditions, the convergent properties are proved. Moreover, the numerical results are reported in the end.


---

## Body

## 1. Introduction

Consider nonlinear semi-infinite programming problem (SIP) as follows:(1)SIP:minx∈D⊆Rn⁡fxs.t.gx,w≤0,w∈Ω,where D is a compact set, Ω is a closed set, f:Rn→R is a twice continuously differentiable function, and g:Rn×Ω→R is continuous and differentiable about variables x and w. For convenience, consider only the case of Ω=[a,b]; a and b are real numbers.The SIP problem arises in various applications such as approximation theory, optimal control, eigenvalue computation, mechanical stress of materials, pollution control, and statistical design. The research of SIP can be traced back to linear semi-infinite programming [1] and it was also proposed in researching Fritz-John conditions [2]. Then the SIP was formally proposed by Charnes, Coopper, and Kortanek in 1962 [3]. It is difficult to solve SIP because the constraints in SIP are infinite. Numerical methods for solving SIP may be divided into discretization methods and continuous methods. Discretization methods are based on nonlinear programming problems which are obtained by discretization of the original problem and incorporate some grid-refinement strategy [4, 5]. Our new method might be useful in the discretization context for semi-infinite programming since it drastically decreases the number of constraints.For continuous methods, Hettich and Honstede present an iterative method which attempts to find a solution satisfying optimality conditions of the original problem. However, this method is only locally convergent and is very restrictive for practical use [6]. Jian et al. present a Norm-Relaxed Method of Feasible Directions algorithm, in order to obtain global convergence [7]. Coope and Watson have proposed a Sequential Quadratic Programming (SQP) method that utilizes an exact L1 penalty function and global convergence obtained [8]. Then, a globally convergent SQP method for SIP is proposed which utilizes an exact L∞ penalty function and trust region methods [9]. For optimization problems with smooth inequality constraints, the penalty function method is, in general, recognized as an efficient method. In [10, 11], in order to solve SIP, the smooth approximate functions in integral form are appended to the objective function by using the concept of the penalty function, but the error caused by taking the smooth approximation of the continuous inequality constraints cannot be avoided. Moreover, it is difficult to find a suitable penalty parameter. If the penalty parameter is too large, then any monotonic method would be forced to follow the nonlinear constraint manifold very closely, resulting in much shortened Newton steps and slow convergence.To avoid using the above drawbacks, Fletcher and Leyyfer proposed a filter method in 2002 [12]. In their method, instead of combining the objective and constraint violation into a single function, they view the original problem as a biobjective optimization problem that minimizes objective function and constraint violation function. Consequently, filter technique has been employed in many approaches, for instance, SQP methods [13], interior point approaches [14], bundle techniques [15], and SIP [16]. But, in [16], the search direction is obtained in a linear equation. The structure of filter is complex.Motivated by the above ideas, we propose a filter trust region algorithm. We transform the SIP into a finite problem based on a modified discretion method. Then, the search direction is obtained by the modified trust region quadratic subproblem. Moreover, without the merit function, we adopt the filter technique to decide whether a new iteration point is acceptable or not. Compared with the existing methods, there are two main advantages in our presented algorithm: (1) the modified quadratic subproblem is always feasible; (2) unlike the continuous method, the penalty parameter is avoided in our presented method, and actually the algorithm has a certain nonmonotonicity property. Under some wild conditions, the convergent properties of the proposed method are proved. The numerical results show the effectiveness of our approach.The remainder of this paper is organized as follows. The algorithm is described in Section2. In Section 3, we analyze the convergent properties of proposed algorithm. Numerical results are reported in the final section.


## 2. Description of Algorithm

For solving SIP, discretization of the original problem SIP, consider the following problem:(2)SIPq:minx∈Rn⁡fxs.t.gx,w≤0,w∈Ωq,where Ωq={w∈Ω∣w=a+i·(b-a)/q,i=0,1,2,…,q} is the discrete subset of Ω that appeared in SIP problem (1). q is a positive integer (in general, q≥100) that represents the discrete level. In practice, depending on the length of [a, b], a and b are real numbers, suppose q≥100b-a.For anyx∈Rn, denote φ(x)=max⁡{0,g(x,w),w∈Ωq},Ω - ( x ) = { w ∈ Ω q ∣ g ( x , w ) ≤ 0 }, Ω+(x)={w∈Ωq∣g(x,w)>0},Ω 0 - ( x ) = { w ∈ Ω - ( x ) ∣ g ( x , w ) = 0 }, Ω0+(x)={w∈Ω+(x)∣g(x,w)=φ(x)}, Ω0(x)=Ω0-(x)∪Ω0+(x), X={xk∣g(xk,w)≤0,w∈Ωq}.Suppose the current iteration point isxk∈Rn, Ωk-(x)={w∈Ωq∣g(xk,w)≤0}, Ωk+(x)={w∈Ωq∣g(xk,w)>0}, φk=max⁡{0,g(xk,w),w∈Ωq}. Ωk=Ωk-(x)∪Ωk+.In order to improve the degree of accuracy of optimal solution of SIP, we observed that trust region method is exceedingly important for ensuring global convergence while retaining fast local convergence in optimization algorithms, so the trust region condition is added to the quadratic subproblem of (2).For the current k-th iteration,dk is obtained by the following modified trust region quadratic subproblem (QP):(3)QPminγ0z+12dTHkds.t.∇fxkTd≤γ0z,gxk,w+∇xgxk,wTd≤γwz,∀w∈Ωk-,gxk,w+∇xgxk,wTd≤γwz+φk,∀w∈Ωk+,d≤Δk,where γ0,γw>0 are positive constants, Hk is a symmetric positive definite matrix, and Δk≥0 is the k-th trust region radius.Denote(4)qkz,d=γ0z+12dTHkd.Define the actual reduction of f(x) as(5)fxk-fxk+dk.The predict reduction of f(x) as(6)qk0,0-qkzk,dk.Here qk(zk,dk)=γ0zk+(1/2)dkTHkdk.Define(7)ρk=AredkPredk=fxk-fxk+dkqk0,0-qkzk,dk.The parameter ρk is used to decide whether the predicted reduction of f(x) is close to the actual reduction of f(x) or not.In the proposed algorithm, the filter technique is used to decide whether a trial point is acceptable or not.Definition 1.
A pair(hk,fk) is dominated by (hj,fj) if and only if hk≤hj and fk≤fj for each j≠k.Definition 2.
A filter setF is a set of pairs (h,f) such that no pair dominates any other.To ensure the convergence, some additional conditions are required to decide whether to accept a trial point to the filter or not. The traditional acceptable criterion is as follows.Definition 3.
A trial pointx is called acceptable to the filter F if and only if either(8)hx≤hjorfx≤fj,∀hj,fj∈F.To avoid convergence to infeasible limit points, we add an envelope around the current filter. So criterion (8) can be changed to the following criterion.Definition 4.
A trial pointx is called acceptable to the filter F if and only if either(9)hx≤βhjorfx≤fj-γhx,∀hj,fj∈Fwhere 0<γ<β<1 are constants. In practice, β is close to 1 and γ is close to 0.In the current k-th iteration, lethk=max⁡{0,g(xk,w),w∈Ωq},fk=f(xk). Then our algorithm (FTR) is presented as follows.FTR AlgorithmStep 1 (initialization).
Givenx0∈Rn, Δ0, and ε>0 set k=0, F=Φ, q≥100b-a, γ>0, β>0, 0≤ε<1, ρ0>0, γ0>0, and γw>0.Step 2.
Solve (3) to obtain dk,zk. If zk≤ε, stop; otherwise, set xk+=xk+dk, and go to Step 2.Step 3.
Calculateρk=Aredk/Predk=(fxk-fxk+dk)/qk0,0-qkzk,dk, where qk(zk,dk)=γ0zk+(1/2)dkTHkdk.Step 4  3.
Ifρk≥ρ0, set k:=k+1, Δk=2Δk and update parameter H and go to Step 1; otherwise go to Step 4.Step 5  4.
If(hk,fk) is acceptable for current filter, add the (hk,fk) to filter, set k:=k+1, Δk=2Δk, update parameter H, and go to Step 1; otherwise, set k:=k, Δk=(1/2)Δk and go to Step 1.Suppose that QP has local optimal solution(dk,zk); i.e., (dk,zk) is a Karush-Kuhn-Tucker (KKT) point of QP. So there exists multiplier μk∈Rn and μwk∈Rq+1,w∈Ωq, satisfy:(10)Hkdk+μk∇fxk+∑w∈Ωqμwk∇xgxk,w+μdd=0,(11)μkγ0+∑w∈Ωqμwkγw=γ0,(12)∇fxkTd-γ0z≤0,(13)gxk,w+∇xgxk,wTd-γwz≤0,∀w∈Ωk-,(14)gxk,w+∇xgxk,wTd-γwz-φk≤0,∀w∈Ωk+,(15)d≤△k,(16)μk∇fxkTd-γ0z=0,(17)μwkgxk,w+∇xgxk,wTd-γwz=0,∀w∈Ωk-,(18)μwkgxk,w+∇xgxk,wTd-γwz-φk=0,∀w∈Ωk+,(19)μdd-△k=0,(20)μk,μwk,μd≥0.Similarly, ifxk is a KKT point for problem SIPq, then there exists a multiplier vector μk∈Rn and λk∈Rq+1 such that the following formulas hold:(21)μk∇fxk+∑w∈Ωλk∇xgxk,w=0,(22)gxk,w≤0,w∈Ω,(23)λkgxk,w=0,(24)λk≥0.The following lemma shows that our algorithm is well defined.Assumption A1. f:Rn→R and g:Rn×Ωq→R are continuous and differentiable.Lemma 5.
Assume Assumption A1 holds andxk∈Rn; then (i) subproblem (QP) has a unique solution; (ii) (zk,dk) is an optimal solution of subproblem (QP) if and only if (zk,dk) is a Karush-Kuhn-Tucker (KKT) point of it.Proof.
(i) Obviously,(zk,dk)=(0,0) is a feasible solution of subproblem (QP) since g(xk,w)≤0 for all w∈Ωk- as well as g(xk,w)≤φk for all w∈Ωk+; beside (zk,dk)=(0,0) also satisfy ∇f(xk)Td≤γ0z and d≤Δk, so the feasible set of subproblem (QP) is not empty. On the other hand, for each feasible solution (z,d) of subproblem (QP), in view of the first constraint ∇f(xk)Td≤γ0z of subproblem (QP), we know that the value of objective function of subproblem (QP) satisfies the following inequality:(25)γ0zk+12dkTHkdk≥∇fxkTdk+12dkTHkdk.Therefore, the value of objective function of subproblem (QP) is bounded from below because of the symmetric positive definite property of Bk; that is, there exists a constant a such that(26)inf⁡γ0zk+12dkTHkdk:zk,dk∈Xk=a∈-∞,+∞.Here the feasible set(27)Xk=zk,dk:∇fxkTdk≤γ0zk;gxk,w+∇xgxk,wTdk≤γwzk,w∈Ωk-;gxk,w+∇xgxk,wTdk≤γwzk+φk,w∈Ωk+;dk≤ΔkAccording to Bolzano-Weierstrass theorem, bounded series must have a convergent subsequence. Therefore, there exists a sequence {zkj,dkj}⊆Xk such that(28)γ0zkj+12dkjTHkdkj⟶a,j⟶∞.Moreover, for j large enough, we have(29)a+12≥γ0zkj+12dkjTHkdkj≥∇fxkTdk+12dkjTHkdkj.Note that the matrix Bk is positive definite, as well as the boundedness of {dkj}j, so the sequence {zkj}j is bounded. Therefore, there exists a subset K such that(30)limj∈K⁡zkj,dkj=zk,dk∈Xk,a=γ0zk+12dkTHkdk.Hence (zk,dk) is an optimal solution of subproblem (QP). In addition, the subproblem (QP) is equal to the following constrained optimization:(31)mindk∈Rn12dkTHkdk+max⁡∇fxkTdk;γ0γwgxk,w+∇xgxk,wTdk,w∈Ωk-;γ0γwgxk,w+∇xgxk,wTdk-φk,w∈Ωk+s.t.dk≤Δk.Obviously, the first term of the objective function is strictly convex about variable dk and the second term is convex about variable dk; thus the objective function of the problem above is strictly convex [18]. Besides, the constrained function of (31) is a convex function. Combining the convexity of Rn, we obtain problem (31) which is a convex programming and its optimal solution dk is unique. Therefore, the optimal solution of subproblem (QP) is unique.
(ii) If(zk,dk) is a KKT point for subproblem (QP), then it is an optimal solution of subproblem (QP) since subproblem (QP) is a convex programming. Conversely, if (zk,dk) is an optimal solution of subproblem (QP), note that Abadie’s Constraint Qualification [19] holds automatically since the constraints of subproblem (QP) are linear; then (zk,dk) is a KKT point for subproblem (QP). The proof is completed.From Lemma5, we know QP has only optimal solution (zk,dk); i.e., QP has only KKT point. So there exists multiplier μk∈Rn and μwk∈Rq+1,w∈Ωq, satisfy (10)-(20).Similarly, ifxk is a KKT point for problem SIPq, then there exists a multiplier vector μk∈Rn and λk∈Rq+1 satisfy (21)-(24).Assumption A2. Assume the Mangasarian-Fromovitz Constraint Qualification (MFCQ) holds at any x∈Rn; i.e., there exists a vector d such that {d∣∇xg(x,w)Td<0,∀w∈Ω0(x)}≠Ø.Lemma 6.
Assume Assumptions A1 and A2 hold,(zk,dk) is an optimal solution of subproblem (QP); then (i) γ0zk+(1/2)dkTHkdk≤0,zk≤0; (ii) zk=0 if and only if dk=0 if and only if xk is a KKT point for subproblem (QP).Proof.
(i) From the fact that(zk,dk)=(0,0) is a feasible solution of subproblem (QP) and (zk,dk) is an optimal solution of subproblem, then γ0zk+(1/2)dkTHkdk≤0. Besides Bk is positive definite, and γ0>0; one has zk≤-(1/2γ0)dkTHkdk≤0.
(ii) From (i), we haveγ0zk+(1/2)dkTHkdk≤0. If zk=0, then (1/2)dkTHkdk≤0; taking into account the positive definite property of Bk, one has dk=0. Conversely, if dk=0, we denote the feasible set of problem SIPq:(32)X=xk∣gxk,w≤0,w∈Ωq,and two cases xk∈X and xk∉X are considered, respectively. Firstly, suppose that xk∈X, i.e., φk=0, from the first constraint of subproblem ∇f(xk)Td≤γ0z, we have 0=∇f(xk)Tdk≤γ0zk. Combining with the result that zk≤0 and γ0>0, we know that the conclusion zk=0 holds. Now suppose that xk∉X, i.e., φk>0, then the set Ωk+(xk)≠Ø and let w0∈Ωq such that g(x,w0)=φk. So from the constraints g(xk,w)+∇xg(xk,w)Tdk≤γwzk+φk of subproblem (QP) one gets (33)zk≥gxk,w-φk+∇xgxk,wTdkγw=∇xgxk,wTdkγw=0.Together with zk≤0, one gets zk=0. Conclusion (ii) is obtained.Lemma 7.
Assumezk=0 and xk∉X, and X is defined as (32); then the set {d∣∇xg(x,w)Td<0,∀w∈Ω0(x)}=Ø.Proof.
In view of the definition ofX and xk∉X, it follows that Ωk+≠Ø. Now we prove by contradiction that the first conclusion of Lemma 7 holds. Suppose that there exists a vector d¯∈Rn such that(34)∇xgx,wTd¯<0,∀w∈Ω0x.the following result holds if the positive parameter λ is small enough(35)z¯λ=max1γ0∇fxkTλd¯;1γwgxk,w+∇xgxk,wTλd¯,w∈Ωk-;1γwgxk,w+∇xgxk,wTλd¯-φk,w∈Ωk+Obviously, for λ>0 small enough, (z¯,λd¯) is a feasible solution of (3); furthermore, γ0z¯+(1/2)(λd¯)TBK(λd¯)<0. Therefore(36)zk≤zk+12dkTHkdk≤z¯+12γ0λd¯TBKλd¯<0.This is a contradiction to zk=0. Hence Lemma 7 follows. The proof is completed.Lemma 8.
Assume Assumptions A1 and A2 hold; ifxk∉X, X is defined as (32), then zk<0.Proof.
By contradiction, suppose thatzk<0 does not hold; then zk=0, and we have {d∣∇xg(x,w)Td<0,∀w∈Ω0(x)}=Ø from Lemma 7; this conclusion contradicts to Assumption A2. The proof is completed.Lemma 9.
Assume Assumptions A1 and A2 hold. Then the multiplier sequence{μk} and μwk(w∈Ωq) are both bounded.Proof.
In view of the formulaγ0=μkγ0+∑w∈Ωqμwkγw and the nonnegative properties of multipliers μwk,γw and parameter γ0>0, we can obtain the boundedness of sequences {μk} and {μwk}.Lemma 10.
Assume Assumptions A1 and A2 hold and(zk,dk) is an optimal solution of subproblem (QP); then zk=0 if and only if xk is a KKT point of SIPq.Proof.
Suppose thatzk=0, we can get dk=0,xk∈X, φk=0 by Lemma 6, so Ωk+(xk)=Ø, Ωk-(xk)=Ωq, and the KKT conditions (10)-(20) can be rewritten as(37)μk∇fxk+∑w∈Ωqμwk∇xgxk,w=0,(38)μkγ0+∑w∈Ωqμwkγw=γ0,(39)gxk,w≤0,∀w∈Ωq,(40)μwkgxk,w=0,∀w∈Ωq,(41)μk,μwk≥0.In view of the formula γ0=μkγ0+∑w∈Ωqμwkγw and the nonnegative properties of multipliers μwk,γw and parameter γ0>0, we can obtain the boundedness of sequences {μk} and {μwk}. We prove that μk≠0. By contradiction, suppose that μk=0, then in view of the equation γ0=μkγ0+∑w∈Ωqμwkγw one can get μwk≠0; i.e., g(xk,w)<0, one knows that μwk=0 from μwkg(xk,w)=0,∀w∈Ωq. Therefore, μk∇f(xk)+∑w∈Ωqμwk∇xg(xk,w)=0 becomes(42)∑w∈Ωqμwk∇xgxk,w=0.Choosing a vector d∗ satisfying MFCQ at the point xk and multiplying the equality above and the constraints of subproblem for w∈Ω0(x) by d∗, we obtain(43)∑w∈Ωqμwk∇xgxk,wd∗=0,∇xgxk,wd∗<0.This is a contradiction and the conclusion that μk≠0 is true.
Let(44)λk=μwkμk,w∈Ωqxk,and then the KKT condition of SIPq holds at xk with the multiplier vector λk, so xk is a KKT point for SIPq.
Now, to prove the necessity of theorem, note that ifxk is a KKT point for SIPq, namely, (37)-(41) holds, then (0,0) satisfies KKT conditions (37)-(41) of SIPq with multipliers(45)μk=γ0-∑w∈Ωqμwkγwγ0,(46)μwk=λkμk.From Lemma 5 we obtain the uniqueness of the KKT point. So the uniqueness of the KKT point shows that zk=0. The whole proof is completed.From Lemma10, zk=0 can be used as terminating condition.Lemma 11.
FTR algorithm cannot cycle infinitely many times among the inner cycle (Step 1→ Step 2→ Step 4→ Step 1).Proof.
Suppose the contrary, then it follows from the rules of FTR algorithm that one hasΔk→0,dk→0, while ρk≤ρ0 is maintained. Consequently, we have(47)ρk-1=Aredk-PredkPredk≤odk2∇fxkTdk+12dkTHkdk.so(48)0≤ρk-1=Aredk-PredkPredk≤odk2∇fxkTdk+12dkTHkdk⟶0,asΔk⟶0.This indicates that we eventually have ρk>ρ0. This is a contradiction and the desired conclusion follows. This proof is completed.


## 3. Convergent Properties

In this section, under appropriate conditions, we establish the convergence of FTR algorithm. For this purpose, the following basic assumption is necessary.Assumptions A3. Assume the sequence {xk} generated by FTR algorithm is bounded.Assumptions A4. Assume there exists a,b>0, and a,b∈N+, such that ad2≤dTHkd≤bd2.To analyze the convergence property of FTR algorithm, we need the following lemma.Lemma 12.
Assume Assumptions A3 and A4 hold; then, sequences{dk} and {zk} generated by FTR algorithm are bounded.Proof.
Firstly, prove{dk} is bounded. By the contradiction, suppose {dk} is unbounded, there exists infinite index set K, such that dk→+∞ as k∈K,k→+∞. Together with zk≤0, this is a contradiction with ∇f(xk)Tdk≤γ0z, so {dk} is bounded.
Now, because of{dk} is bounded and f(x) is continuous and differentiable, thus {∇f(xk)Tdk} is bounded. According to ∇f(xk)Tdk≤γ0z and γ0>0 one has (49)∇fxkTdkγ0≤zk;furthermore, together with zk≤0, {zk} is bounded. This proof is completed.The following result is obtained.Theorem 13.
Assume Assumptions A3 and A4 hold,K is an infinite iterative index set; if dk→0,k∈K, then any accumulation point of {xk},k∈K, generated by FTR algorithm is the KKT point of SIPq.Proof.
Supposex∗ is the accumulation point of {xk},k∈K. Denote (50)L0-xk=w∈Ωq-∣gxk,w+∇gxk,wTdk=γwzkL0+xk=w∈Ωq+∣gxk,w+∇gxk,wTdk=γwzk+φkL0xk=L0-xk∪L0+xkL0(xk) is the subset of Ωq.
First, we provezk→0,k∈K as dk→0,k∈K.
Ifφk=0, then xk∈Xq; besides, ∇f(xk)Tdk≤γ0zk, zk≤0, so ∇f(xk)Tdk/γ0≤zk≤0; thus zk→0 as dk→0,k∈K.
Ifφk>0, then Ωq+≠Ø; there exists w0∈Ωq+ such that ∇g(xk,w0)Tdk≤γw0zk≤0,k∈K. Thus zk→0,k∈K as dk→0,k∈K.
Then, from Lemmas9 and 10, the conclusion is obtained.Because we use the filter technique in FTR algorithm, the following lemma is necessary.Lemma 14.
Assume there are infinitely many points added to the filter. Then(51)limi→∞⁡hxi=0.Proof.
If the theorem is not true, there would have infinite components inK1, which is defined as follows:(52)K1=k∣hk>ε.We assume that fk≤M for all k without loss of generality, where M is a positive constant. The following two cases are considered, respectively.
( i ) If mini∈K1{fi(x)} exists, let fmin=mini∈K1{fi(x)}, hmin=mini∈K1h(x)=mini∈K1g+, and g+=max⁡{0,g(xk,w)}. Then, according to the definition of the filter, the other components, which lie behind xmin in the filter, satisfy(53)hk≤βhmin,fk≥fmin.Then, all the filter points, which enter the filter behind xmin can be covered with a square, whose area is no more than 2Mhmin. We consider the area lies to the southwest of the filter in this square. When a new point xnp enters the filter, the next point xnp+1 should lie to the southwest of the points in the filter Fnp and the area which lies to the southwest of Fnp in the square is smaller than that of Fnp+1. Therefore, we think that the area is reduced if a new point enters the filter. When a point is added to the filter, its h is less than every point, which lies to the left of this point, to more than (1-β)ε. Its f is less than every point, which lies to the right of this point, to more than γε. Therefore, the area of this square, more than (1-β)γε2, will be reduced. Thus, the area will be reduced to 0 after finite times. When the area is zero, it means that a point does not enter K1, which is contradicted with the infiniteness of K1.
(ii) Ifmini∈K1{fi(x)} does not exist, because f(x) and g(x,w) are continuous and differentiable, let(54)fmin=infi∈K1⁡fix.From the definition of inff(x), there exists fnp such that fnp≥fmin and fnp≤fmin+γε. Then, according to the definition of the filter, the other components, which lie behind xnp in the filter, satisfy(55)hk≤βhnp,fk≥fnp-γε.Using the same techniques as that in (i), the conclusion can also obtained which is contradicted with the infiniteness of K1. So K1 is infinity; the result is gotten.
Thus, the conclusion is obtained.As for the case of finitely many points added to the filter, it is apparent that the following result is true.Lemma 15.
Assume there are finitely many points added to the filter. Thenh(xk)=0, where k is the number of points added to the filter.Proof.
From the terminating condition of Step 2 in FTR algorithm, one haszk=0 and also dk=0; furthermore h(xk)=0. Thus, if there are finitely many points added to the filter, the index of the last point is the number of points added to the filter. The proof is completed.The following result is obtained.Theorem 16.
Assume Assumptions A3 and A4 hold; if{xk} generated by FTR algorithm is a bounded sequence, then {xk} has an accumulation point satisfying the KKT conditions of SIPq.Proof.
Supposex∗ is an accumulation point of sequence {xk}, by Lemma 14, limi→∞h(xi)=0, so there exists K such that h(xi)→0,i→∞,i∈K. Taking the limits about KKT conditions (10)-(20) of subproblem and h(xi), together with Lemma 9, we have φ(x∗)=0, h(x∗)=0 so x∗∈Xq; thus x∗ is the KKT point of SIPq. The proof is completed.


## 4. Numerical Results

In this section, we report our preliminary numerical test results. FTR algorithm described in Section2 was then implemented in Matlab R2016a. We compared the performance of the FTR algorithm with [17]. The following four problems were tested. Throughout the computational experiments, the parameters used in algorithm were q=100, γ=0.95, β=0.05, ε=10-4, ρ0=0.75, γ0=1, and γw=1.Problem 1.
(56)minx∈Rnfx=1.21ex1+ex2s.t.gx,w=w-ex1+x2≤0,w∈Ω=0,1.x0=0.8,0.9T.Problem 2.
(57)minx∈Rnfx=x1-2x2+5x22-x23-132+x1-14x2+x22+x23-292s.t.gx,w=x12+2x2w2+ex1+x2-ew≤0,w∈Ω=0,50.x0=1,1T.Problem 3.
(58)minx∈Rnfx=13x12+12x1+x22s.t.gx,w=1-x12w22-x1w2-x22+x2≤0,w∈Ω=0,1.x0=-2,-2T.Problem 4.
(59)minx∈Rnfx=∑i=1nexis.t.gx,w=11+w2-∑i=1nxiwi-1≤0,w∈Ω=-1,1.x0=1,0···0,···,0T.In Table1, the problem is denoted by Pro; e.g., Problem 1 is denoted by Pro1, the dimension of x is denoted by n, the number of iterations is denoted by Iter, the optimal solution is denoted by x∗, and the optimal value is denoted by f(x∗).Table 1
The comparison between FTR algorithm and algorithm in [17] with same conditions.
FTR Algorithm Algorithm in [17] n I t e r x ∗ f ( x ∗ ) Iter f ( x ∗ )  Pro1 2 2 ( - 0.0952,0.0953 ) T 2.200132 3 2.200142  Pro2 2 4 ( 0.7199 , - 1.1504 ) T 97.159372 9 97.16956  Pro3 2 2 ( 0.7500 , - 0.6181 ) T 0.194599 17 0.194726  Pro4 15 2 ( 1.0001 , - 0.0193 , - 0.0366 , - 0.0370 , ⋅ ⋅ ⋅ - 0.0370 ) T 16.22755 9 16.22757  Pro4 20 2 ( 1.0001 , - 0.0193 , - 0.0266 , - 0.0267 , ⋅ ⋅ ⋅ - . 00267 ) T 21.22514 7 21.22519In Table1, the limited numerical results show that the proposed algorithm can give an accurate solution quickly (the iterate number is less than that in [17]), which indicates that the algorithm herein is effective. Moreover, it has been observed that the computational results are not very sensitive to the choice of the initial point and the parameter n, showing that the proposed algorithm is stable.


## 5. Conclusion

In this paper, we present a filter trust region method. Based on the discrete technique, we transform nonlinear semi-infinite programming into a finite problem. And the search direction is obtained by a modified trust region quadratic subproblem which is always feasible. Besides, we adopt the filter technique to decide whether a new iteration point is acceptable or not, so the penalty parameter which is always used in most of the existing methods is avoided. Under some wild conditions, the global convergence of the proposed method was obtained. The main advantage of the presented method is that our method is more flexible and easier to implement, the modified trust region quadratic subproblem is always feasible, and penalty parameter is avoided. The numerical results show that our presented method is effective and stable.



---

*Source: 3921592-2018-07-08.xml*