A Dwindling Filter Algorithm with a Modified Subproblem for Nonlinear Inequality Constrained Optimization?

Chao GU Detong ZHU

1 Introduction

Consider the following nonlinear inequality constrained optimization:

wherex∈→R(j=1,···,m)are continuously differentiable.The problem has become highly important in recent years(see[6,9–10,12,14–15,20–21]).

It is well-known that the sequential quadratic programming(or SQP for short)method is one of the most effective methods to solve(1.1).Because of its superlinear convergence rate,it is a topic of much active research.However,the SQP algorithms have two serious shortcomings.First,in order to obtain a search direction,one must solve one or more quadratic programming subproblems per iteration,and the computation amount of this type is very large.Second,the SQP algorithms require the related quadratic programming subproblems to be solvable per iteration,but it is difficult to be satisfied.Moreover,the solutions of the sequential quadratic subproblem may be unbounded,which leads to that the sequence generated by the method is divergent.Based on the above reasons,Zhou[19]modified the quadratic subproblem to make it feasible and bounded.

The filter idea was first presented by Fletcher and Leyffer[3]for nonlinear programming(or NLP for short),offering an alternative to penalty functions,as a tool to guarantee global convergence of algorithms for nonlinear programming.Filter methods were successfully applied to solving various optimization problems,including complementarity and variational inequality problems(see[3–4,7–8,11,13–14,16–17]).Recently,Chen and Sun[1]proposed a dwindling multidimensional filter line search method for unconstrained optimization.The envelope of the dwindling filter becomes thinner and thinner as the step size approaches zero,which leads to more flexibility for the acceptance of the trial step.

In this paper,we propose a dwindling filter algorithm with Zhou’s modified quadratic subproblem for nonlinear inequality constrained optimization.The algorithm has the following merits:It requires to solve only one QP subproblem with only a subset of the constraints which are estimated as active;the initial point is arbitrary;the subproblem is feasible at each iterate point;the feasibility restoration phase,which is always used in the traditional filter methods,is not needed.This paper can be outlined as follows.In Section 2,we state the new algorithm.The global convergence of the new algorithm is proved in Section 3.The local Q-superlinear convergence rate is established in Section 4.Some numerical results are given in Section 5.

2 Description of the Algorithm

Define functions Φ(x)and Ψ(x)by

?x,d∈be the first order approximation to Ψ(x+d),namely

?σ>0,functions Ψ(x,σ)and→R are defined as follows:

(2.4)equals the following linear programming:

Denote

Definition 2.1Mangasarian-Fromotz constraint qualification(or MFCQ for short)is said to be satisfied by g(x)such that

Lemma 2.1?x∈Fc,if MFCQ is satisfied at x,then θ(x,σ)<0,?σ<0.

Lemma 2.2Ψ(x,σ),Ψ0(x,σ),θ(x,σ)and θ0(x,σ)are all continuous onRn×R+.

Lemma 2.3?x∈Fc,if θ(x,σ)<0,then θ0(x,σ)<0.

For the details of Lemmas 2.1–2.3,see[19].Givenx∈Rnandσ>0,D(x,σ)is defined by the following set:

Ifd?is the solution of LP(x,σ),then∈D(x,σ)and henceD(x,σ)is nonempty.We obtain the directionfrom the following convex programming problem

whereis the set of approximate active indices of the pointxk.Clearly,by the above statement,the convex programming is feasible.

Let us measure the inequality constraint violation atxby

where=max{0,gj(x)},j∈I.The basic idea of the filter method is to interpret the optimization problem as a bi-objective optimization problem with the two goals of minimizing the objective functionf(x)and the constraint violationh(x).In the traditional filter method,a trial pointis called acceptance to the filter if and only if

for all∈F.Different from the above idea,we call that a trial pointis acceptable to the dwindling filter if and only if

for all∈F,whereφ(α)is a dwindling function defined by Chen and Sun[1].

Definition 2.2φ(α):[0,1]→Ris a dwindling function if it is a monotonically increasing and continuous function such that

For example,φ(α)=satisfies(2.14)–(2.16).A decreasing sequence of step sizes∈(0,1](l=0,1,2,···)is tried until(2.13)is satisfied,in which the envelope of the dwindling filter becomes thinner and thinner as the step size approaches zero.Ifφ(α)=1,the dwindlingfi lter is reduced to the traditional fi lter.Later,ifh(xk)>0,the fi lter is augmented for a new iteration using the update formula

It is easy to see that

for allk.

Algorithm 2.1Given starting pointx0,Σ is a compact set which consists of symmetric positive definite matrices,

Step 1Compute

Step 2Compute an active constraint setLk.

(1)Leti=0 and

(2)Set

If det(≥and go to Step 3.

(3)Set=and go to Step 2(2)(inner loop A).

Step 3Computedkfrom the convex programming problem and setIf≤,stop.

Case 1??holds:If

holds,setand go to Step 5.

Case 2?is not satisfied:If

or

holds,setand go to Step 5.

Step 4Computation of directionqk.

Letbe the matrix whose rows arelinearly independent rows ofbe the matrix whose rows are the remainingn?rows of.We might denote=Likewe might as well let?f()=Compute

wheree=(1,1,···,

(1)Set=1 andl←0.

(2)ComputeIf∈Fk,go to Step 4(3).

Case 1holds:If

holds,setand go to Step 5.

Case 2is not satisfied:If

or

holds,setand go to Step 5.

(3)Choosesetl←l+1,and go back to Step 4(2)(inner loop B).

Step 5If either?oris not satisfied,augment the filter.Choosek←k+1,and go back to Step 1.

3 Global Convergence

Assumption 3.1(1)The functions(j∈{0,1,2,···,m})are twice continuously differentiable and bounded on Rn.

(2)The iterate{xk}remains in a compacted subset S?Rn.

(3)There exist two constantsaandbsuch thatfor allk,wherep∈Rn,0

(4)The Mangasarian-Fromovitz constraint qualification(MFCQ)holds.

Lemma 3.1(see[19])Suppose thatis a symmetric positive definite matrix.If MFCQ is satisfied at xk,then the convex programming problemhas a unique solution dkwhich satisfies KKT conditions,i.e.,there exist vectorssuch that

Lemma 3.2(see[15])For any iterate k,the index i defined in Step2in Algorithm2.1is fi nite,which means that the inner loop A terminates in a finite number of times.

Lemma 3.3(see[15])Ifthen it holds that

Lemma 3.4Suppose that Assumption3.1holds.Then trial pointcould not be rejected by ifis sufficiently small.

ProofSuppose thatis rejected by.From Lemma 3.3,we get0.The second-order Taylor expansion off(x)implies that

Sinceasl→∞,≤holds for sufficiently small.

Remark 3.1Without any assumption,we prove that the trial point could not be rejected by the current iterate.

Lemma 3.5The mechanisms of the filter ensure that for all k,

ProofThe proof is done by induction.Note that

where>h(x0).Sinceφ(α)=o(α)asl→∞,holds for sufficiently smallα.The claim is valid fork=0.

Suppose that the claim is true fork.Ifwithholds,the claim is true.Otherwise,we consider the trial pointIt is evident thatIn the following we need to prove thatThere are two cases.

Case 1h(xk)=0.

We have<0 from Lemma 3.3 andSo(2.21)must be satisfied,i.e.,and

Case 2h(xk)>0.

Ifholds,the proof is similar to Case 1.Otherwise,consider that the filter is augmented in iterationk,i.e.,

Byand(by the proof of Lemma 3.4),we obtain

Lemma 3.6Suppose that Assumption3.1holds.Then the inner loop B terminates in a fi nite number of iterations.

ProofThe proof is done by contradiction.Suppose that the inner loop does not terminate in a finite number of iterations.In this case,the algorithm will always reject the trial pointsandx(),which leads to→0.Therefore,we may consider two cases.

If?holds,the trial point is required to satisfy(2.21).Sinceqkis a descent direction,there exists a constantc1>0 such that,for(2.21)must be satisfied.If,on the other hand,does not hold,the trial point is required to satisfy(2.22).From Lemma 3.4,there exists a constant0 such that,for(2.22)must be satisfied.

From Lemma 3.5,we haveFk,i.e.,

or

for all(,)∈F.Ifholds,from Lemma 3.3 and→0,we obtain that there exists a constantc3>0,for

which contradicts(3.2a).Ifholds,from Lemma 3.3 and→0,we get that there exists a constantc4>0,such that

which contradicts(3.2b).Chooseand the inner loop B terminates in a finite number of iterations.

Lemma 3.7Suppose that infinite points are added to the filter.Then there exists a subsequence G in which the filter has been augmented such that

ProofThe proof is done by contradiction.Suppose that there exists an infinite subsequence{}ofGfor which

for some>0.At each iteration,(h(),f())is added to the filter,which means that no other(h,f)can be added to the filter at a later stage within the square

Now observe that the area of the each of these squares is at leastAs a consequence,if there exists an infinite subsequencesuch that≥asj→∞,the set[0,∞]∩{(h,f)|f≤κf}is completely covered by at most a finite number of such squares.This is in contradiction to the infinite subsequence→0 asi→∞,we get

Since=0,we have=0.Lemma 3.6 implies that there exists a constantc5such that foris accepted by Algorithm 2.1,which contradicts(3.4).

Lemma 3.8Suppose that finite points are added to the filter.Then

ProofFrom Assumption 3.1,there exists aK∈N so that for all iterationsk≥K,there is no point adding to the filter.Ifis accepted by Algorithm 2.1,we then have that for allk≥K,

Suppose thatis rejected by Algorithm 2.1.In this case,the trial point=is accepted.Sinceh()<(??fwe have

which is the same as(3.5).We conclude that

Sinceis bounded below asi→∞,we have=0.

Lemma 3.9Suppose that Assumptions3.1holds.Then

ProofThe proof is similar to that of Theorem 1 in[16].

Theorem 3.1Suppose that Assumptions3.1holds.Then

ProofSuppose that the claim is not true,i.e.,there exists a subsequence infinite index setKand a constant>0 so thatIt follows from Lemmas 3.1 and 3.3 that

If 1

Whenh(xk)

ChooseK1such that for allk≥≤ζ,and then the trail point must be accepted by(2.19)or(2.21).We denote the two sets of indices of those iterations in which(2.19)holds byK1?Kand in which(2.21)holds?K.There are three cases.

Case 1IfK1is infinite andis finite,there exists aK2,such that for all iterationsk≥K2andk∈K1,(2.19)holds,i.e.,

From the proof of Lemma 3.8,one can conclude that

=0 implies that=0,which is a contradiction.

Case 2Ifis infinite andK1is finite,there exists aK3,such that for all iterationsk≥K3andk∈K2,

From the proof of Lemma 3.8 and=0,we have=0,which contradicts the proof of Lemma 3.6.

Case 3 IfK1is infinite andK2is infinite,we have

which is a contradiction.

Remark 3.2The result of Theorem 3.1 is stronger than that in[16].The reason is that the feasibility restoration phase,which is always used in the traditional filter method,is not needed.

4 Local Convergence

In order to analyze the local convergence rate of the proposed algorithm more assumptions are needed.

Assumption 4.1(1)x?is a KKT point of(1.1).Strict complementarity slackness and linear independence of the gradients of the active constraints hold.

(2)The second-order sufficient condition holds atx?,i.e.,there exists a constant>0 such that

whereI?={j=0,j∈I}.

(3)xk→x?.

(4)

Algorithm 4.1Given starting pointx0,Σ is a compact set which consists of symmetric positive definite matrices,H0∈Σ,F0={(h,f)∈R2:h≥>h(x0),γf,γh∈(0,1),τ∈(2,3),

Step 1Compute

Step 2Compute an active constraint setLk.

(1)Leti=0 and

(2)Set

If det()≥and go to Step 3.

(3)Seti=i+1,=and go to Step 2(2)(inner loop A).

Step 3Computedkfrom the convex programming problem and set=If≤,stop.

Step 4Let=wherePkis a permutation matrix andis invertible.Solve linear equations:()=?whereF(xk+dk)=(gj(xk+dk),j∈Lk).Set

Case 1?holds.If

holds,setxk+1=and go to Step 5.

Case 2?is not satisfied.If

or

holds,setand go to Step 5.

Step 5Computation of directionqk.

LetA1kbe the matrix whose rows are|Lk|linearly independent rows ofAk,andbe the matrix whose rows are the remainingn?|Lk|rows ofAk.We might denoteAk=LikeAk,we might as well let?f(xk)=Compute

where=e=(1,1,···,1)

(1)Setαk,0=1 andl←0.

(2)Compute=xk+.If∈Fk,go to Step 5(3).

Case 1?>h(xk)holds.If

holds,setand go to Step 6.

Case 2>h(xk)is not satisfied.If

or

holds,set=xk(and go to Step 6.

(3)Choosesetl←l+1,and go back to Step 5(2)(inner loop B).

Step 6If either?or?is not satisfied,augment the filter.Choose∈Σ,∈[],k←k+1,and go back to Step 1.

Theorem 3.1 shows that0 ask→∞.So,it is natural thatsatisfiesfor sufficiently largek.(2.3)–(2.5)imply that=0 whenkis large enough.So the sequenceQ(xk,Hk,σk)is equivalent to the following quadratic programming subproblem whenkis sufficiently large

Lemma 4.1(see[15])It holds,for k→∞,that

where(dk,λk)is the KKT pair of the above quadratic programming subproblem.

Lemma 4.2Suppose that Assumption4.1holds.Then the full steporis acceptable to the current filter Fkfor sufficiently large k.

ProofSuppose that the full stepis rejected by the dwindling filter.According to(4.6)and the invertibility of

Forjand sufficiently largek,there exists a constantc7>0 such thatUsing Taylor’s theorem,we can write

where?kis betweenxkandxk+dk+Since→0 ask→∞,the right-hand side term is negative.As forj∈I?,using Taylor’s theorem and the definition of

whereτ∈(2,3),is betweenxkandxk+dkandξkis betweenxk+dkandFrom the two cases,we obtain that==max{0,gj(xk+}=0.From the update formula of the dwindling filter,we have

for allk.Therefore,is acceptable to the current filterFkfor sufficiently largek.

Theorem 4.1Suppose that Assumption4.1holds.Then the full steporis taken by the algorithm for sufficiently large k.Further,the sequence{xk}converges to x?Q-superlinearly.

ProofSuppose that the pointis not accepted by the filterFk.In that case,considerFrom Lemma 4.2,we have thatis acceptable to the current filterFkfor sufficiently largek.It is similar to the proof of Theorem 3.1 that?holds for sufficiently largek.Then we have

Combining with Lemma 3.1 andwe obtain that

By(4.8)and Taylor’s expansion,we have

Since→0 ask→∞,anda>0,we get

for sufficient largek.By Assumption 4.1(4),the sequence{xk}converges tox?Q-superlinearly.

5 Numerical Experiments

In this section,we present the numerical results of Algorithm 2.1 on an HP i5 personal computer with 2G memory.The selected parameter values are:=0.5,τ=2.5,ηf=0.5,====1.5.The computation terminates when the stopping criterionis satisfied.

Table 1 Numerical results.

All the forty nonlinear inequality constrained problems are numbered in the same way as in[5].NtandNfstand for the numbers of iterations and function evaluations,respectively.IPOPT is an interior-point filter line-search algorithm for nonlinear optimization(see[18]).To compare the performance of Algorithm 2.1 and IPOPT,we use the performance profiles as described in[2].Our profiles are based on function evaluations and the numbers of iterations.The benchmark results are generated by running a solver on a setPof problems and recording information of interest such as the number of function evaluations.LetSbe the set of solversin comparison.For each problempand solvers,we define

=the number of function evaluations required to solve problempby solvers.

Accordingly,setto be the number of gradient evaluations or iterations.The comparison is based on the performance ratio defined by

If we define

thenρs(τ)is the probability for the solvers∈S.The value ofρs(1)is the probability that the solver will win over the rest of the solvers.From Figures 1–2,it is clear that Algorithm 2.1 wins over IPOPT on the given problems.

Figure 1 Performance profile on the numbers of iterations.

Figure 2 Performance profile on function evaluations.

6 Conclusion

In this paper,we propose a dwindling filter algorithm with Zhou’s modified subproblem for nonlinear inequality constrained optimization,which requires less computational costs compared with the traditional filter algorithm(see[18])on the given problems.The feasibility restoration phase is not used in the algorithm.Under mild conditions,global convergence andlocal superlinear convergence rates are obtained.Moreover,the global convergence result of Theorem 3.1 is stronger than that in[16].How to choose the dwindling parametersφ(α)to get better numerical experience deserves further research.

AcknowledgementThe authors would like to thank the two anonymous referees for their comments and suggestions that helped to improve the presentation of this paper.

[1]Chen,Y.and Sun,W.,A dwindling filter line search method for unconstrained optimization,Technical Report of Optimization No.2010-09-01,School of Mathematical Science,Nanjing Normal University,Nanjing.

[2]Dolan,E.D.and Mor,J.J.,Benchmarking optimization software with performance profiles,Math.Program.,91,2002,201–213.

[3]Fletcher,R.and Leyffer,S.,Nonlinear programming without a penalty function,Math.Program.,91,2002,239–269.

[4]Gu,C.and Zhu,D.,A secant algorithm with line search filter method for nonlinear optimization,Appl.Math.Modell.,35,2011,879–894.

[5]Hock,W.and Schittkowski,K.,Test examples for nonlinear programming codes,Lecture Notes in Economics and Mathematics System,Vol.187,Springer-Verlag,New York,1981.

[6]Jian,J.B.and Liu,Y.,A superlinearly convergent method of quasi-strongly sub-feasible directions with active set identifying for constrained optimization,Nonlinear Anal.Real World Appl.,12,2011,2717–2729.

[7]Long,J.,Ma,C.F.and Nie,P.Y.,A new filter method for solving nonlinear complementarity problems,Appl.Math.Comput.,185,2007,705–718.

[8]Li,C.and Sun,W.,On filter-successive linearization methods for nonlinear semidefinite programming,Sci.China Ser.A,52,2009,2341–2361.

[9]Nie,P.Y.,Sequential penalty quadratic programming filter methods for nonlinear programming,Nonlinear Anal.Real World Appl.8,2007,118–129.

[10]Nie,P.Y.,A derivative-free method for the system of nonlinear equations,Nonlinear Anal.Real World Appl.,7,2006,378–384.

[11]Nie,P.Y.and Ma,C.F.,A trust region filter mehtod for general nonlinear programming,Appl.Math.Comput.,172,2006,1000-1017.

[12]Nocedal,J.and Wright,S.,Numerical Optimization,Springer-Verlag,New York,1999.

[13]Shen,C.G.,Xue,W.J.and Pu,D.G.,A filter SQP algorithm without a feasibility restoration phase,Comp.Appl.Math.,28,2009,167–194.

[14]Su,K.and Yu,Z.,A modified SQP method with nonmonotone technique and its global convergence,Comput.Math.Appl.,57,2009,240–247.

[15]Su,K.,A globally and superlinearly convergent modified SQP-filter method,J.Global Optim.,41,2008,203–217.

[16]Wchter,A.and Biegler,L.T.,Line search filter methods for nonlinear programming:Motivation and global convergence,SIAM J.Optim.,6,2005,1–31.

[17]Wchter,A.and Biegler,L.T.,Line search filter methods for nonlinear programming:Local convergence,SIAM J.Optim.,6,2005,32–48.

[18]Wchter,A.and Biegler,L.T.,On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming,Math.Program.,106,2006,25–57.

[19]Zhou,G.L.,A modified SQP method and its global convergence,J.Global Optim.,11,1997,193–205.

[20]Zhu,Z.B.and Wang,S.,A superlinearly convergent numerical algorithm for nonlinear programming,Nonlinear Anal.Real World Appl.,13,2012,2391–2402.

[21]Zhu,Z.B.and Jian,J.B.,An efficient feasible SQP algorithm for inequality constrained optimization,Nonlinear Anal.Real World Appl.,10,2009,1220–1228.