A Modified Slanting Filter Method forNonlinear Programming?

LIU mei-ling,LIXue-qian

(1-Departm ent of mathem atics and Physics,Shanghai D ian ji University,Shanghai 201306;2-Business School,University of Shanghai for Science and Technology,Shanghai 200093)

1 Introduction

In this paper,we consider the follow ing nonlinear programm ing problem

where x ∈ Rn,E={i|i=1,2,···,me},I={i|i=me+1,···,m},the functions f:Rn→R and c:Rn→Rmare assumed to be tw ice continuously differentiable.

The corresponding Lagrangian function of(1)is

whereλ,μ are Lagrangemu ltip liers.

Nonlinear programm ingmodel(1)arising often in science,engineering and many fields in the society,is extremely im portant.There aremanymethods to dealw ith(1),for instance,sequential linear programm ing methods,interior point methods,penalty approaches and trust region techniques.

The filter technique isproposed in 2002 for solving non linear programm ing prob lem[1].The underlying concept is that a trial point can be accepted if and only if the ob jective function f or the constraint violation h has a suffi cient reduction at it.That is,the filter method consider op timality and feasibility separately.Now,the filter method has been extensively applied and developed in many aspects[2-7].In these papers,it is shown that the structure of the filter is im portant to convergence speed.

To improve the accepting chance of a trial point and also the convergence,Chin and Fletcher[8]modified the original filter technique proposed in[1]to a slanting filter technique.In it,they set a slanting envelope to the filter in the fdirection.Then the convergence proof of the slanting filter technique is presented by Fletcher et al[9].In their work,the slanting filter shows a better structure to solve non linear programm ing problem s.Later,some diff erent slanting filter structure are constructed in recent years.Shen et al[10]proposed a tri-dimensional slanting filter technique which considers the violations of equality and inequality constraints separately.Gould et al[2]proposed a multi-dimensional slanting filter approach which includes each com ponent ob jective function in the filter.Gu and Zhu[11]and Shen et al[12]proposed separately the nonmonotone slanting filter technique in which the reduction of the ob jective function is considered nonmonotonely.Peri?caro et al[13]proposed a general filter algorithm which depends neither on the definition of the forbidden region nor on the way in which the step is com puted.Thesemodifications of the filter structure can improve the accepting chance of a trial point aswell as the optimality.But,it is not obvious to improve the feasibility.

Motivated by the above slanting filter notions,we improve further the filter structure.We proposed a modified filter method.A small envelop is set around the filter in the fdirection in classic filter method in[8].We develop a new slanting filter by setting slanting envelopes in both the fdirection and the h direction.The slanting envelope in the h direction is set to a stronger reduction condition.Thismodification providesamechanism whereby iterates are forced towards im proving not on ly the optimality but also the feasibility.Though filtermethods consider optimality and feasibility separately,the feasibility has priority.That is,it is critical to reduce the constraint violation h.The new strategy adm itsmore flexibility in accepting steps as com pared with the classic filter.It can improve eff ectively the accepted chance of a trial point.Then the feasibility induced by the reduction of the constraint violation is im proved.

Further,the algorithm shows that the ob jective function must be reduced at some trial point if the constraint violation h is reduced successively.It iseff ective to promote the optimality and then the convergence.And,themodified filter takes advantages of the“inclusion property” which w ill be described in section 3 in detail.In addition,the modified slanting filter criterion is involved in restoration phase.Then,as suffi cient reduction conditions,themodified slanting filter technique is combined with SQP approach in the algorithm.Under somem ild conditions,it can derive global convergence.

Thispaper isorganized as follows.In section 2,we introduce the basic filter notion.In section 3,we present themodified slanting filter notion.Subsequently,it is used in a SQP framework.And,themodified filter is also used in feasibility restoration phase.In section 4,we analyze the convergence.Finally,some numerical results are given in section 5.

2 The basic filter notion

To com pare conveniently themodified slanting filter notion and the previous filter notion,we introduce the basic filter notion as follows.

Fletcher and Leyffer proposed in[1]the original filter notion by referring the dominance idea in multi-ob jective optim ization.They defined the constraint violation of(1)as

where=max(0,ci),i∈I.It is easy to see that h(x)=0 if and only if x isa feasible point.Then the basic filter notion can be described as the follow ing definitions.

Defi n ition 1 A pair(hk,fk)is said to dom inate another pair(hl,fl)if and only if both hk≤hland fk≤fl.

Here,for convenience,f(xk)is abbreviated as fk.Sim ilar to h(xk)and other variables.

In a nonlinear programm ing problem,Definition 1means the point xkis better to xl,or as good as xlat least.

Defi n ition 2 A filter is a list of pairs(hl,fl)such that no pair dom inates any other.

In practical implementation,a point(hk,fk)is said to be acceptable for inclusion in the filter if it is not dom inated by any point in the filter.Hence,a trial step is acceptable if it reduces either the constraint violation h or the ob jective function f.For convenience,we also say the iterate xkisacceptable to the filterwhen a pair(hk,fk)is said to be accep table to the filter.In[1],it is that a trial point xkcan be accepted by the filter if

see Figure 1 for a sketch.β,γare preset parameters such that 1>β>γ>0.But we stress that on ly two scalars are stored for each entry in the filter.No vectors such as xlare stored.Subsequently,Chin and Fletcher proposed in[8]the slanting filter criterion which is combined with SLP as suffi cient reduction conditions and used with SQP by Fletcher et al[9]to solve nonlinear programm ing.They defined that a pair(hk,fk)can be accepted by the filter if it satisfies

for all(hl,fl)∈Fk,see Figure 2.Here,Fkdenotes the current filter.

Figure 1: original filter

Figure 2: slanting filter

3 The mod ifi ed slanting filter and the algorithm

Based on the above slanting filter,we present themodified slanting filter in this section.As it allows points to accumulate in the neighborhood of a filter entry,the definition of the slanting filter is not adequate for im proving convergence.So,it is corrected by defining a small envelope around the current filter in h direction,in which points are not accep ted.Specifi cally,a trial point xkcan be accepted to the current filter if its pair(hk,fk)satisfies

for all(hl,fl)∈ Fk.The value ofβ,γ is set sim ilarly to the previous filter.The new added slanting envelope ensures that the pairs with the same h value have the same envelope in h direction.This is illustrated in Figure 3,using the valuesγ=0.1 and β=1?γ.In practice,wemake usuallyβclose to 1 andγclose to 0.The right hand inequality in(2)is amore su ffi cient reduction in h than that in[9].So,it promotes the feasibility.To com pare themodified slanting filter with previous one intuitively,it is depicted in Figure 3.As the algorithm progresses,wemay want to add a(hk,fk)pair to the filter.If a new trial point xkis acceptable to Fk,the pair(hk,fk)is added to the current filter Fkand the old pairs dom inated by(hk,fk)are removed.This keeps the filter a range of points in which no point dom inates each other.

Figure 3:modified slanting filter

As a criterion for accepting or rejecting a step,we use the filter technique in an SQP framework to get a new iterate xk+1.

Let xkbe the current solution at iteration k.The search direction dkis obtained by solving the follow ing quad ratic programm ing(QP)subproblem

where Wk∈ Rn×nis the Hessian of the Lagrangian or its symmetric positive definite approximatematrix andρdenotes the trust-region radius.

An undesirab le eff ect of using a trust region based approach is that reducing the trust region radiusmay cause the QP subproblem to become inconsistent.Sometimes,the linearizations of the nonlinear constraints may them selves be inconsistent.Our strategy for dealing with this situation is to enter a feasibility restoration phase in which we aim to get closer to the feasib le region by minim izing h.

Any method for solving a nonlinear equality and inequality constrained system can be used to im plement the feasibility restoration phase,for instance,SLP method and Least-squares method.A more fundamental disadvantage of them turns out to be the lack of second order information,leading in some cases to slow convergence.In this paper,we still use SQP-likemethod combined with themodified slanting filter technique to finish it,sim ilar to that in[1].First,if an inconsistent QP is detected,the solver exitsw ith a solution of the problem

to get a solution d,where the set J ? {1,2,···,m}contains infeasible constraints(?cj(xk)Td+cj(xk)>0)whose l1sum ism inim ized at the solution to(4),sub ject to the constraints in J⊥={1,2,···,m}J being satisfied.Then,the feasibility restoration phase is to solve NLP problem

The restoration phase consists of a sequence of iterations that continue whilst(3)is infeasible.Each iteration first checks feasibility of the system

then determine the sets J and J⊥to solve(4).Specifically,SQP strategy is applied to problem(5)with d from(4)

where

λjis derived from(4).

As in solving(1),there are two com peting aim s for(5),that is the need tomaintain feasibility of the constraints in J⊥and the need to minim ize the sum of constraint violations in J.So we have found it preferable to use a filter in the restoration phase aswell.This filter is referred to as the restoration filter.Define

The restoration filter is defined sim ilarly to the abovemodified slanting filter notion.Use FRkdenotes the current restoration filter.A trial point can be accepted by the restoration filter if it satisfies

or

for all(hJ⊥(xl),hJ(xl))∈ FRk.Therefore,the restoration filter is a list of iterate points such that no point dom inates any other under condition(7).

Iterations in the restoration phase are continued until either a consistent QP is encountered(in which case the algorithm can return to the basic SQP algorithm)or an infeasible K rush-Kuhn-Tucker(KKT)point of(5)is found for some sets J and J⊥,in which case the algorithm term inates with the indication that the NLP problem(1)is infeasible.

A detailed description of the basic SQP-filter algorithm and the restoration phase algorithm can now be given(see A lgorithm s 1 and 2).In A lgorithm 1,define

as the actual reduction in f(x)and

as the predicted reduction in f(x).If??k>0 and d is accepted and become dk,then an f?type iteration is said to have occurred;if??k<0 or if the current QP subproblem is incom patible,we refer to the resulting iteration as an h-type iteration.

Now,we present thewhole algorithm(see A lgorithm 1 and A lgorithm 2)as follows.

A lgorithm 1:The basic SQP-filter algorithm Given:x0∈R n.Choose constantβ∈(0,1),γ∈(0,1),W 0=I0,ρ0>0,η∈(0,1).Initialize h m ax,F0=(h m ax,?∞).Let k=0,ρ= ρ0 w h ile d?=0 do rep eat Solve(3)for a step d,λk,μk if QP-subproblem(3)is inconsistent then enter feasibility restoration phase(A lgorithm 2)to find a feasible point such that(3)is feasible forρ> ρ0 else set?x=x k+d,and com pute h(?x),f(?x)if?x is acceptable to F k then if?f k<η??k,??k>0 then x k=?x,ρ=ρ/2 else ?x is accepted else x k=?x,ρ=ρ/2 un til?x is accepted Add(h(?x),f(?x))to F k if h(x k)>0.Update W k as W k+1 by dam ped BFGSmethod.Setρk=ρ,x k+1=?x,d k=d,??k=??(d),ρ=max(ρ0,2ρ)Set k:=k+1

Rem ark 1 To prevent the situation in which a sequence of points for which is f-type iterative point with hk→∞is accepted,and to avoid cycling,we set an upper bound hmaxon the constraint violation function h.

Further specific im plementation details of the algorithm see section 5.

A lgorithm 2:Feasibility restoration phase Given x k,ρk,h m ax from A lgorithm 1.Setρ=ρk w h ile(3)is infeasible or d k?=0 do rep eat Solve(4)to obtain index sets J and J⊥.if(3)is feasible then turn to the A lgorithm 1 else Solve(6)for a step d k.Set?x=x k+d k.Com pute h J(?x),h J⊥(?x)if?x is acceptable to F Rk then ?x is accepted else x k=?x,ρ=ρ/2 un til?x is accepted Add(h J(?x),h J⊥(?x))to F Rk if h J⊥(x k)>0 Setρk=ρ,x k+1=?x,ρ=max(ρ0,2ρ)Set k:=k+1

4 Convergence analysis

In this section,we give a convergence analysis for A lgorithm 1.We refer to the convergence analysis of[9]some places.First,some assum ptions are given.

A 1 A ll iterates xkare in a nonem pty closed and bounded set S of Rn;

A 2 The functions f(x)and c(x)are tw ice continuously diff erentiable on an open set containing S;

A 3 Thematrix sequence Wk,multipliersλk,μkare bounded for all k.

A 1 and A 2 are standard assum ptions.A 3 plays an im portant role to obtain the convergence result and ensure the algorithm is im plementab le.

W ithout loss of generality,we assume that there are two constantsˉm,M>0 such that

for all x,k and dk∈Rn.

Lemm a 1 Suppose fkismonotonically decreasing and bounded below.If for all k,

holds,then hk→0.

proo f Suppose K is a suffi cient large positive integer.If hk+1≤ (β ? γ2)hk+γ(fk?fk+1)holds for all k>K,then two conditions follows.

1) If fk?fk+1≥ γhk+∑1holds on an in finite subsequence whose index set is marked as T1,it follows thatis bounded since fkismonotonically decreasing and bounded below.And h>0,hence hk+1→0,k∈T1.

2)If fk?fk+1<γhk+1holds,k/∈T1,then

that is

holds on k/∈T1,k>K.Then byβ∈(0,1),closes to 1,γ∈(0,1),closes to 0,hence hk+1→0,k>K,k/∈T1.

For other case,there exists an infinite subsequence whose index set is marked as T2,for k∈T2on which fk?fk+1≥γhk+1.Sim ilar to the above proof,it has hk+1→0,k∈T2.For k/∈T2,hk+1≤(β?γ2)hk+γ(fk?fk+1)holds,hence hk→0 holds on themain sequence.

Lemm a 2 Suppose assum ptions A 1–A 3 hold,{xk}is an in finite sequence of iterative points accepted to Fkproduced by A lgorithm 1,then

proof Here we use themethodology of([14],Lemma 3.3).If the conclusion is not true,theremust exist an in finite subsequence{xki} ? {xk}and a constant ˉ?>0 such that

holds.Since{xk}is a sequence iterations accepted to Fk,and by assum ptions A 1 and A2,we know that f(xk)>fminfor some constant fmin,any pair(h,f)can not be added to Fkat a later stage w ithin the square

or with the intersection of this square withNow observe that the area of each of these squares is(β ? γ2+ γ)γˉ?2.From this we can get the set S0∩{(h(x),f(x))|f(xki)

therefore hki→0,which contradicts(10).Hence this latter assum ption is im possible and the conclusion follows.

Lemm a 3 Suppose assump tions A 1-A 3 hold,and let dkbe a feasible point of QP subproblem(3).It then follows that

proof By the definition of h(x)and([9],Lemma 3),the conclusion follows.

Lemm a 4 Suppose assum ptions A1–A 3 hold,then the inner iteration term inates finitely.

proof If xkis a KKT point of problem(1),then dk=0 and the algorithm term inates.Otherwise,if the inner iteration does not term inate finitely,thenρ→0 by the algorithm mechanism.We consider two cases.

(a) hk>0.For all dksuch thatit follows that

if either ∥?ci(xk)∥ =0 or ∥?ci(xk)∥ ?=0 with ρ 0.

(b) hk=0.Because xkis not a KKT point,there exists a vector s, ∥s∥2=1,constantξ>0 such that

with Akdenotes the active constraint set at xk.Considering the QP-feasible line segment dω0= ω0ρs forω0∈ [0,1],then

It follows that

Therefore,by the global optimality of the solution dkto(3),the predicted reduction??kalso satisfies

and ifρ≤2ξ/(1+2n+γnˉm)M,it follows from Lemma 3 that

that is,a f-type iteration is satisfied.Then the inner iteration term inates finitely,the conclusion follows.

The global convergence theorem concerns KKT necessary conditions under Mangasarian Fromow itz constraint qualification(MFCQ).This is essentially an extended form of the Fritz John conditions for a problem that includes equality constraints.

Theorem 1 Suppose assum ptions A 1–A 3 hold,then the sequence(xk,dk)generated by A lgorithm 1meets one of the two cases:

(A)A KKT point of problem(1)is found;

(B) There exists an accumu lation point of the sequence(xk,dk)that is a KKT point.

proo f If the algorithm generated finite iterations,then by the algorithm mechanism we know that the last iterate is the optimal point satisfied the preset precision.So,next we consider the case of infinite iterations.We discuss two cases.

(i) The filter is augmented by an in finite number of h-type iterations.According Lemma 2,it has h(xki)→0 when ki>K,K is a su ffi cient large integer.So,by assum ptions A1-A3 there exists at least one accumulation pointˉx of the sequence{xki}.It is easy to knowˉx is a feasib le point.Hence if

thenˉx is a KKT point.O therw ise,by A lgorithm 1,while ki>K,?fki<γh(xki)<γ′? for arbitrary ′?>0.Then the trust region radius ρ w ill decrease successively.Further,by Lemma 4,ifρ≤2ξ/(1+2n+γnˉm)M,it follows that

So an f-type iteration w ill result.This contradicts the fact that the sequence is composed of infinite number of h-type iterations.

(ii) The filter is augmented on ly a finite number of h-type iterations.Hence,when k>K for some integer K>0,all iterations are f-type iterations.So the sequence{fk}is strictly monotonically decreasing for k>K.Therefore by Lemma 1 that hk→0,∑k→ ∞and any accumu lation pointxˉ is feasible.Because f(x)is bounded on S,is convergent,that is,?fk→0,k>K,k→∞.Hence if

thenˉx is a KKT point.O therw ise,w ithout loss of generality,suppose that∥dk∥∞>? for k>K.By hk→0 and(8),it holds

Thus for k>K,by(12)and the KKT conditions of QP-subprob lem(3)

it has

From Taylor expansion theorem,(14)and(8),it has

which contradicts the fact that?fk→0.Thusˉx is a KKT point.

5 N um erical experience

In this section,we give some numerical results of A lgorithm 1.We take some CUTE problem s[15]for test exam ples,which are available freely on NEOS,to test our algorithm.The test code isedited in Matlab 7.0.The details about the im plementation are described as follows:

(a) The term ination tolerance?=1E?6;hmax=max{104,1.2h(x0)},η=0.1;

(b) The Kuhn-Tucker residual is defined as

and I0is the identity matrix;

(c) As introduced above,Wkis Hessian of the Lagrangian or its approximation.If it is not positive definite,the QP-subproblm is not prom ised to find a globaloptimal point.So,an updating formula suggested by Powell in[16]can be used to keep it positive definite

where

The row headers are presented in Tab le 1.We present the numerical com parison with a tri-dimensional filter solver(TF SOLVER)[10]in Table 2,and with the algorithm in[1]in Table 3.In NIT1,the constants for the filter envelopes are set asβ=0.99 and γ=0.01 for the first column,β=0.999 andγ=0.001 for the second column,β=0.8 andγ=0.2 for the third column.W hen we develop filter SQP,we found that the filter algorithm is not very sensitive to these parameters.

From Table 2 and Tab le 3,we observe that in general,A lgorithm 1 outperform s the tri-dimensional filter solver and the basic filter solver in[1].Our numerical experimentation shows robustness and effi ciency of our approach.

Table 1:Description on headers

Table 2:Num erical results 1

Table 3:Num erical results 2

6 Conclusion and d iscussion

We have presented a modified slanting filter method for nonlinear programm ing problem sand have shown itsglobal convergenceunderm ild conditions.We set slanting envelopes in both the ob jective function direction and the constraint violation direction.It is eff ective to promote faster convergence than the algorithm in[10].On somem idscale problem s,the proposed algorithm outperform s that in[1].But the large-scale problem s are not involved.Thisw ill be our further work.

Referen ces:

[1]Fletcher R,Leyff er S.Non linear programm ing w ithou t a penalty function[J].mathem atical Programm ing,2002,91(2):239-269

[2]Gou ld N IM,Sainvitu C,Toint pL.A filter-trust-region method for unconstrained op tim ization[J].SIAM Journal on Optim ization,2006,16(2):341-357

[3]Nie pY,Lai mY,Zhu S J,et al.A line search filter app roach for the system of non linear equations[J].Com puter and mathem atics with App lications,2008,55(9):2134-2141

[4]U lbrich S.On the superlinear local convergence of a filter-SQP method[J].mathem atical Programm ing,2004,100(1):217-245

[5]U lbrich M,U lbrich S,V icente L N.A globally convergent prim al-dual interior-point filter method for nonconvex non linear programm ing[J].mathem atical Programm ing,2003,100(2):379-410

[6]W¨achter A,Biegler L T.Line search filter methods for non linear programm ing:motivation and global convergence[J].SIAM Journal on Op tim ization,2005,16(1):1-31

[7]W¨achter A,Biegler L T.Line search filterm ethods for non linear programm ing:local convergence[J].SIAM Jou rnal on Op tim ization,2005,16(1):32-48

[8]Chin C M,Fletcher R.On the global convergence of an SLP-filter algorithm that takes EQP steps[J].mathem atical Programm ing,2003,96(1):161-177

[9]Fletcher R,Ley ff er S,Toint pL.On the global convergence of a filter-SQP algorithm[J].SIAM Jou rnal on Op tim ization,2002,13(1):44-59

[10]Shen C G,Xue W J,Pu D G.G lobal convergence of a tri-dim ensional filter SQP algorithm based on the line search method[J].App lication Num erical mathem atics,2009,59(2):235-250

[11]Gu C,Zhu D T.A nonm onotone SQP-filterm ethod for equality constrained op tim ization[J].International Jou rnal of Com puter mathem atics,2010,87(15):3489-3506

[12]Shen C G,Ley ff er S,Fletcher R.A nonm onotone filterm ethod for non linear op tim ization[J].Com putational Op tim ization and App lication,2012,52(3):583-607

[13]Peri?caro G S,Ribeiro A A,Karas E W.G lobal convergence of a general filter algorithm based on an effi ciency condition of the step[J].App lied mathem atics and Com putation,2013,219(17):9581-9597

[14]Fletcher R,Gou ld N I M,Leyff er S,et al.G lobal convergence of trust-region SQP-filter algorithm for general non linear programm ing[J].SIAM Journal on Op tim ization,2002,13(3):635-659

[15]Bongartz I,Conn A R,Gou ld N IM,et al.CUTE:constrained and unconstrained testing environm ent[J].ACM Transactions on mathem atical Software,1995,21(1):123-160

[16]Powell mJ D.A fast algorithm for non linearly constrained op tim ization calcu lations[C]//Num erical Analysis:Lecture Notes in mathem atics,Berlin,Springer-Verlag,1977:144-157