# A Globally Convergent Line Search Filter SQP Method for Inequality Constrained Optimization

Authors: Zhong Jin
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

A line search filter SQP method for inequality constrained optimization is presented. This method makes use of a backtracking line search procedure to generate step size and the efficiency of the filter technique to determine step acceptance. At each iteration, the subproblem is always consistent, and it only needs to solve one QP subproblem. Under some mild conditions, the global convergence property can be guaranteed. In the end, numerical experiments show that the method in this paper is effective.


---

## Body

## 1. Introduction

In this paper, we consider the following nonlinear inequality constrained optimization problem:(P)mins.t.f(x)s.t.mingj(x)≤0,j∈I={1,2,…,m},
where x∈Rn,f:Rn→R, and gj(j∈I):Rn→R1 are assumed to be continuously differentiable.It is well known that the sequential quadratic programming (SQP) method is one of the most efficient methods to solve problem(P). Because of its superlinear convergence rate, it has been widely studied. See Boggs and Tolle [1] for an excellent literature survey. In SQP methods, at each iteration the search direction is generally obtained by solving the subproblem as follows:
(1)mins.t.∇f(xk)Td+12dTBkds.t.mingj(xk)+∇gj(xk)Td≤0,j∈I={1,2,…,m},
where Bk∈Rn×n is a symmetric positive definite matrix.However, the previous QP subproblem has a serious shortcoming that constraints in (1) may be inconsistent. To overcome this disadvantage, much attention has been paid [2–7]. Burke and Han [2], Zhou [3], and J.-L. Zhang and X.-S. Zhang [4] modified the constraints in subproblem (1) to ensure that a revised QP subproblem is consistent, and their methods are globally convergent. Burke and Han's method is just a conceptual method and cannot be implementable practically, Zhou's method is based on the exact line search, and Zhang's method focuses on the inexact line search. Furthermore, Pantoja and Mayne [5] presented a modification of SQP algorithm by modifying both constraints and objective function in (1), and the search direction is obtained by solving a new QP subproblem which always has an optimal solution. In addition, Liu and Li [6] and Liu and Zeng [7] proposed SQP algorithms with cautious update criteria, which can be considered as modifications of the SQP algorithm given in [5].In the previous methods [2–7], a penalty function is always used as a merit function to test the acceptability of the iterate points. However, as we all know, there are several difficulties associated with the use of penalty function and in particular with the choice of the penalty parameter. Too low a choice may result in the loss of an optimal solution; on the other hand, too large a choice damps out the effect of the objective function. Therefore, filter method was first introduced in trust region SQP method for constrained nonlinear optimization problems by Fletcher and Leyffer [8], offering an alternative to merit functions, as a tool to guarantee global convergence. Subsequently, global convergences of filter SQP methods were established by Fletcher et al. [9, 10]. Furthermore, Wächter and Biegler [11, 12] presented line search filter methods for nonlinear equality constrained programming, and the global convergence and local convergence were given. The promising numerical results of filter methods have led to a growing interest in filter methods in recent years [13–26], in which trust region strategy is used in [15, 26], and line search technique is taken in others. It is noteworthy that, based on [2–4] and line search filter technique, Su and Che [13] and Su [14] presented modified SQP filter methods for inequality constrained optimization. In Su's methods, the subproblem is always consistent, and the global convergence property is obtained.In this paper, derived from [5–7] and the filter technique, especially the filter line search technique provided by Wächter and Biegler [11, 12], we propose a line search filter SQP method for inequality constrained optimization. This method has the following merits: it avoids using the penalty function to guarantee global convergence and has no requirement on initial point; at each iterate point the subproblem is always consistent, and it only needs to solve one QP subproblem; under some mild conditions, we prove that the algorithm either terminates at a Karush-Kuhn-Tucker (KKT) point within finite steps or generates an infinite sequence whose at least one cluster is a KKT point; in the end, numerical experiments show that our method is effective.This paper is organized as follows. In the next section, the structure of line search filter technique is discussed. The algorithm is put forward in Section3, and the global convergence theory of the algorithm is presented in Section 4. The numerical results for some typical examples are listed in Section 5. Finally in Section 6, a brief discussion on the proposed algorithm is given.


## 2. The Structure of Line Search Filter Technique

In this section, we will present the structure of line search filter technique and some related strategies. Instead of combing the objective function and constraint violation into a single function, filter methods view nonlinear optimization as a biobjective optimization problem that minimizes the objective function and the constraint violation. Now we give the structure of line search filter technique.In the line search filter technique, after a search directiondk has been computed, a step size αk,l∈(0,1] is determined in order to obtain the trial iteration xk(αk,l)=xk+αk,ldk. More precisely, for fixed constants γf,γθ∈(0,1), a trial step size αk,l provides sufficient reduction with respect to the current point xk if
(2)θ(xk(αk,l))≤(1-γθ)θ(xk)orf(xk(αk,l))≤f(xk)-γfθ(xk),
where θ(x) is a constraint violation function. Similar to [18], let θ(xk)=max1≤i≤m[gi(xk)]+ and [·]+=max{·,0}.For the sake of a simplified notation, the filter is defined in this paper not as a list but as a setℱk⊆[0,∞]×[-∞,∞] containing all (θ,f) pairs that are prohibited in iteration k. We say that a trial point xk(αk,l) is acceptable to the filter if its (θ,f) pair does not lie in the taboo region, that is, if
(3)(θ(xk(αk,l)),f(xk(αk,l)))∉ℱk.
At the beginning of the algorithm, the filter is initialized by ℱ0={(θ,f)∈R2:θ≥u}, where u is a large positive number. Throughout the optimization the filter is then augmented in some iterations after the new iterate point xk+1 has been accepted. For this, the following updating formula is used:
(4)ℱk+1=ℱk⋃{f≥f(xk)-γfθ(xk)(θ,f)∈R2:θ≥(1-γθ)θ(xk),k+1k1f≥f(xk)-γfθ(xk)}.Similar to the traditional strategy of the filter method, to avoid the convergence to a feasible point but not an optimal solution, we consider the followingf-type switching condition:
(5)mk(αk,l)<0,-mk(αk,l)>δ[θ(xk)]sθ,
where mk(αk,l)=αk,l∇f(xk)Tdk, δ>0, and sθ∈(0,1).When condition (5) holds, the step dk is a descent direction for current objective function. Then, instead of insisting on (2), the Armijo-type reduction condition is employed as follows:
(6)f(xk(αk,l))≤f(xk)+ηmk(αk,l),
where η∈(0,(1/2)) is a fixed constant. If (5) and (6) hold for the accepted trial step size, we may call it an f-type point, and accordingly this iteration is called an f-type iteration. An f-type point should be accepted as xk+1 without updating of the filter; that is, ℱk+1=ℱk, while if a trial point xk(αk,l) does not satisfy the switching condition (5) but satisfies (2), we call it an h-type point (or accordingly an h-type iteration). An h-type point should be accepted as xk+1 with updating of the filter, and we denote the set of indices of those iterations where filter has been augmented by 𝒜⊂ℕ.In our method, when∇f(xk)Tdk<0, the line search is performed. In the situation where no admissible step size can be found, the method switches to a feasibility restoration phrase, whose purpose is to find a new iterate point that satisfies (2) and is also acceptable to the current filter by trying to decrease the constraint violation. In order to detect the situation where no admissible step size can be found and the restoration phase has to be invoked, we approximate a minimum desired step size using linear models of involved functions. For this, we define that
(7)αkmin=min{γθ,-γfθ(xk)∇f(xk)Tdk,-δ[θ(xk)]sθ∇f(xk)Tdk}.


## 3. Description of the Algorithm

We will now proceed to propose a line search filter SQP method for inequality constrained optimization and formally describe the algorithmic details in this section. The proposed algorithm consists of inner loops, and in the next section we show that there is no endless loop and the method is implementable and globally convergent.In our algorithm, motivated by [5–7], the quadratic subproblem (1) is replaced by the following problem:
(8)mins.t.∇f(xk)Td+12dTBkd+bkts.t.mingj(xk)+∇gj(xk)Td≤tj∈I,s.t.mintttttttttttttttttttttt10≤t≤θ(xk),
where bk is a positive parameter. Clearly, this subproblem is always consistent and is a convex programming if Bk is positive semidefinite.Let(dk,tk)∈(Rn,R1) be the solution of subproblem (8). Then there exists a Lagrange multiplier (λk,υk,hk)∈(Rm,R1,R1) satisfying the following KKT system:
(9)gj(xk)+∇gj(xk)Tdk≤tk(j∈I),2222222222211220≤tk≤θ(xk),∇f(xk)+Bkdk+∑j∈I‍∇gj(xk)(λk)j=0,bk-∥λk∥1-υk+hk=0,(λk)j(gj(xk)+∇gj(xk)Tdk-tk)=0(j∈I),υktk=0,hk(tk-θ(xk))=0,222212λk≥0,υk≥0,hk≥0.Now, the algorithm for solving the problem(P) can be stated as follows.Algorithm 1.
Consider the following.Step  1. Initialization: choose an initial point x1∈Rn, an initial filter ℱ1, an initial parameter b1>0, a symmetric and positive definite matrix B1∈Rn×n, δ>0, and sθ∈(0,1). Choose ρ∈(0,(1/2)),δ1,δ2>0, and γf,γθ∈(0,1). Set k=1.Step  2.  Solve subproblem (8) with xk, Bk, and bk to obtain the solution (dk,tk), and let (λk,vk,hk) be the Lagrange multiplier. Stop if dk=0 and tk=0.Step  3.  If dk=0 but tk≠0, set xk+1=xk and ℱk+1=ℱk; go to Step  6.Step  4.  If dk≠0 and ∇f(xk)Tdk≥0, go to Step  8. If dk≠0 and ∇f(xk)Tdk<0, using backtracking line search consider the following.Step  4.1. Initial line search: set l=1 and αk,l=1.Step  4.2. Compute a new trial point. If the trial step size αk,l<αkmin, go to Step  8. Otherwise, compute new trial point xk(αk,l)=xk+αk,ldk. Check acceptability to the filter; if (θ(xk(αk,l)),f(xk(αk,l)))∈ℱk, reject the trial step size and go to Step  4.4.Step  4.3. Check sufficient decrease with respect to current iterate point.
4.3.1. Case I: condition (5) holds. If the Armijo condition (6) holds, accept the trial step (that is, an f-type iteration), and go to Step  4.5; otherwise, go to Step  4.4.4.3.2. Case II: condition (5) does not hold. If (2) holds, accept the trial step (that is, an h-type iteration), and go to Step  4.5; otherwise, go to Step  4.4.Step  4.4. Choose a new trial size αk,l+1=ραk,l. Set l=l+1, and go to Step  4.2.Step  4.5. Accept trial point. Set αk=αk,l and xk+1=xk(αk).Step  5.  Augment filter if it is necessary. If k is not an f-type iteration, augment the filter using (4); otherwise leave the filter unchanged; that is, set ℱk+1=ℱk.Step  6.  Update parameters. Compute ak by
(10)ak=min{∥dk∥-1,∥λk∥1+δ1}.Set(11)bk+1={bk,ifbk≥ak,bk+δ2,otherwise.Step  7.  Update Bk to Bk+1. Go to Step  2 with k replaced by k+1.Step  8.  Obtain a new point xk+1 from a feasible restoration phrase. Set k=k+1, and go to Step  2.Remark 2.
The mechanisms of the filter could ensure that(θ(xk),f(xk))∉ℱk.Remark 3.
The feasibility restoration phrase in Step  8 could be any iterative algorithm with the goal of finding a less infeasible point; for example, a nonlinear optimization algorithm is applied to minimiseθ such as Algorithm B in [14].


## 4. Global Convergence of Algorithm

In this section, we will show the proposed algorithm is well defined and globally convergent under some mild conditions. Then throughout this paper, we always assume that the following assumptions hold.Assumptions
(A1)
The sequence{xk} remains in compacted subset X∈Rn.
(A2)
The functionsf and gj, j=1,2,…m, are twice continuously differentiable.
(A3)
For anyx∈X, the vectors {∇gj(x),j∈I(x)} are linearly independent, where I(x)={j∈I∣gj(x)=θ(x)}.
(A4)
There exist two constantsq≥p>0 such that the matrices sequence {Bk} satisfy p∥d∥2≤dTBkd≤q∥d∥2 for all k and d∈Rn.The first lemma shows that there is no cycle between Step  3 and Step  6 in Algorithm1.Lemma 4.
Let{xk} and {dk} be generated by Algorithm 1. If dk=0 and tk>0, then there exists a finite positive integer r such that dk+r≠0.Proof.
Suppose by contradiction thatdk+r=0 and tk+r>0 for all r≥1 and some k∈ℕ. Then, we have xk+r=xk, and hence tk+r=θ(xk+r)=θ(xk)=tk>0 and vk+r=0. It follows from (9) and (10) that
(12)bk+r=∥λk+r∥1-hk+r<∥λk+r∥1+δ1=ak+r.
This together with (11) implies that bk+r+1=bk+r+δ2 for all r≥1. As a result, we have
(13)bk+r⟶+∞,∥λk+r∥1=bk+r+hk+r⟶+∞asr⟶+∞.
Because xk+r=xk for all r≥1, we denote xk+r=x¯. So, we get
(14)0<tk=limr→+∞tk+r=limr→+∞θ(xk+r)=θ(x¯),limr→+∞(gi(xk+r)+∇gi(xk+r)Tdk+r)=limr→+∞gi(xk+r)=gi(x¯)<θ(x¯)=tk,gigigigigigigigigigigigigigigigi1∀i∉I(x¯).
Therefore, we claim that for all r≥1,
(15)gi(xk+r)+∇gi(xk+r)Tdk+r<tk+r,∀i∉I(x¯).
We also have by (9) and (15) that for all r≥1, (λk+r)i=0, for all i∉I(x¯). This yields
(16)∇f(xk+r)+∑j∈I(x¯)‍∇gj(xk+r)(λk+r)j=0.
Without loss of generality, we assume that limr→+∞λk+r/∥λk+r∥1=λ^. Dividing by ∥λk+r∥1 in both sides of the last equality and taking limits as r→+∞, we obtain
(17)∑j∈I(x¯)‍λ^j∇gj(x¯)=0,λ^j≥0,j∈I(x¯).
Moreover, there exists at least one j∈I(x¯) satisfying λ^j>0. This contradicts Assumption (A3).The next lemma shows that the value of the parameterbk increased only a finite number of times.Lemma 5.
Let{xk} be an infinite sequence generated by Algorithm 1; then there exists an integer k0 such that bk=bmax for all k≥k0. In addition, bmax=max{bk}.Proof.
The proof is by contradiction. Suppose thatbk→+∞, as k→+∞. The step  6 of Algorithm 1 implies that inequality
(18)bk<ak=min{∥dk∥-1,∥λk∥1+δ1}
holds for infinitely many k. In addition, there exists a subsequence satisfying
(19)limki→∞∥dki∥=0,limki→∞∥λki∥1=+∞.
Without loss of generality, using Assumption (A1), we suppose that xki→x¯ as ki→∞. In a way similar to the proof of Lemma 4, we can derive, for all sufficiently large ki,
(20)gj(xki)+∇gj(xki)Tdki<tki,∀j∉I(x¯).
By (9) we have that for all ki sufficiently large, (λki)j=0,forallj∉I(x¯), which yields
(21)∇f(xki)+Bkidki+∑j∈I(x¯)‍∇gj(xki)(λki)j=0.
We can also assume that limki→+∞λki/∥λki∥1=λ^. Dividing by ∥λki-∥1 in both sides of the last equality and taking limits as ki→+∞, then
(22)∑j∈I(x¯)‍λ^j∇gj(x¯)=0,λ^j≥0,j∈I(x¯).
Furthermore, there exists at least one j∈I(x¯) satisfying λ^j>0. This contradicts Assumption (A3).
Becausebk is increased only finitely many times, it is easy to see that bmax=max{bk}.Lemma 6.
The line search is actually performed; that is, our method can generatedk such that ∇f(xk)Tdk<0 at some iteration.Proof.
The proof is by contradiction. Suppose thatdk satisfying ∇f(xk)Tdk<0 cannot be generated and the current iterate point cannot be changed as Step  3; then the iterate points cannot be escaped from the feasibility restoration phrase. Therefore, all points of {xk} are generated by the the feasibility restoration phrase, which follows |𝒜|=∞. Now we first prove that
(23)limk→∞θ(xk)=0.
Consider an infinite subsequence{ki} of 𝒜 with θ(xki)≥ɛ for some ɛ>0. At each iteration ki, (θ(xki),f(xki)) is added to the filter which means that no other (θ,f) can be added to the filter at a later stage within the area [θ(xki)-γθθ(xki),θ(xki)]×[f(xki)-γfθ(xki),f(xki)], and the area of each square is at least γθγfɛ2. By Assumption (A1), we have 0≤θ(x)≤θmax and fmin≤f(x)≤fmax, and then (θ,f) associated with the filter are restricted to ℬ=[0,θmax]×[fmin,fmax]. Hence, ℬ is completely covered by at most a finite number of such areas, which forms contradiction with the infinite subsequence {ki} satisfying (3). This means that (23) is true.
We can see that(0,…,0,θ(xk))T∈Rn+1 is a feasible point of QP subproblem (8); then we get
(24)∇f(xk)Tdk+12(dk)TBkdk+bktk<bkθ(xk).
Because our method does not stop at Step  2, it holds that (dk,tk)↛(0,0). By 0≤tk≤θ(xk), (23) implies that limk→∞tk=0. With the facts (dk,tk)↛(0,0) and limk→∞tk=0, we can assume that ∥dk∥>ϵ0 for some ϵ0>0. Let ϵ1=pϵ02/4bmax; (23) implies that for k sufficiently large enough it holds that θ(xk)<ϵ1, and then bkθ(xk)≤(pbkϵ02/4bmax)≤(1/4)(dk)TBkdk; thus,
(25)∇f(xk)Tdk<-12(dk)TBkdk-bktk+bkθ(xk)<-12(dk)TBkdk+bkθ(xk)≤-14(dk)TBkdk≤-pϵ024<0,
which is a contradiction.Lemma 7.
Ifθ(xk)=0, then mk(α)<0 for all α∈(0,1]. In addition, Θk=min{θ:(θ,f)∈ℱk}>0 for all k.Proof.
Ifθ(xk)=0, then (0,…,0)T∈Rn+1 is a feasible point of subproblem (8), so we get
(26)mk(α)α=∇f(xk)Tdk≤-12(dk)TBkdk-bktk<0.
For proof of second statement please see [11, Lemma  4].Theorem 8.
Suppose all stated assumptions hold. Then(27)limk→∞θ(xk)=0.Proof.
Please see [11, Theorem  1].Lemma 9.
If Algorithm1 generates an infinite sequence {xk}, then the sequence {dk} is bounded; that is to say, there exists a constant Md>0, such that for all k≥0,
(28)∥dk∥≤Md.Proof.
We can see that(0,…,0,θ(xk))T∈Rn+1 is a feasible point of QP subproblem (8), so we get
(29)∇f(xk)Tdk+12(dk)TBkdk+bktk≤bkθ(xk).
From Theorem 8, there exists a constant Mθ such that θ(xk)≤Mθ; thus,
(30)-∥∇f(xk)∥·∥dk∥+12p∥dk∥2≤∇f(xk)Tdk+12(dk)TBkdk+bktk≤bkθ(xk)≤bmaxMθ,
which implies that {dk} is bounded; then, there exists a constant Md>0 such that
(31)∥dk∥≤Md.Lemma 10.
If{xki} is a subsequence of iterate points for which ∥dki∥≥ϵ with some constant ϵ>0 independent of i, then there exist constants ϵ1,ϵ2>0, such that
(32)θ(xki)≤ϵ1⟹mki(α)≤-ϵ2α
for all i and α∈(0,1].Proof.
We can see that(0,…,0,θ(xki))T∈Rn+1 is a feasible point of QP subproblem (8); then we get
(33)∇f(xki)Tdki+12(dki)TBkidki+bkitki<bkiθ(xki).
Let ϵ1=pϵ2/4bmax; then bkiθ(xki)≤(pbkiϵ2/4bmax)≤(1/4)(dki)TBkidki; thus,
(34)mki(α)α=∇f(xki)Tdki<-12(dki)TBkidki-bkitki+bkiθ(xki)<-12(dki)TBkidki+bkiθ(xki)≤-14(dki)TBkidki≤-pϵ24.
Define ϵ2=pϵ2/4; then it implies that mki(α)≤-ϵ2α.Lemma 11.
Suppose that the filter is augmented only a finite number of times; that is,|𝒜|<∞. Then
(35)limk→∞dk=0.Proof.
The proof of this lemma can be found in [11, Lemma  8]. There the proof is stated for slightly different circumstances, but it is easy to verify that it is still valid in our context.Lemma 12.
There exists some constantCf>0, such that
(36)f(xk+αdk)-f(xk)-mk(α)≤Cfα2∥dk∥2,
for α∈(0,1].Proof.
The inequality follows directly from the second order Taylor expansion.Lemma 13.
Let{xki} be a subsequence with mki(α)≤-αϵ2 for some constant ϵ2>0 independent of ki and for all α∈(0,1]. Then there exists some constant α¯>0 such that
(37)f(xki+αdki)-f(xki)≤ηmki(α),
for all ki and α≤α¯.Proof.
LetMd and Cf be the constants from Lemmas 9 and 12. It then follows from Lemma 12 for all α≤α¯ with α¯=(1-η)ϵ2/CfMd2 that
(38)f(xki+αdki)-f(xki)-mki(α)≤Cfα2∥dki∥2≤α(1-η)ϵ2≤-(1-η)mki(α).
That is,
(39)f(xki+αdki)-f(xki)≤ηmki(α).Lemma 14.
Let{xki} be a subsequence with mki(α)≤-αϵ2 for some constant ϵ2>0 independent of ki and for all α∈(0,1]. Then there exist constants C1,C(xki)>0 so that
(40)(θ(xki+αdki),f(xki+αdki))∉ℱki,
for all ki and α≤min{C1,C(xki)}.Proof.
LetMd,Cf be the constants from Lemmas 9 and 12. The mechanisms of Algorithm 1 ensure that
(41)(θ(xki),f(xki))∉ℱki.
Defineℱki(1)={(θ,f)∈ℱki∣f>f(xki)}, ℱki(2)=ℱki∖ℱki(1), and C1=min{1,ϵ2/(Md2Cf)}. For α≤C1 we have α2≤(αϵ2/Md2Cf)≤(-mki(α)/Cf∥dki∥2), or equivalently
(42)mki(α)+Cfα2∥dki∥≤0,
and it follows with (36) that
(43)f(xki+αdki)≤f(xki).
So for α≤C1 we have (θ(xki+αdki),f(xki+αdki))∉ℱki(1).
Letθmin=min{θ∣θ∈ℱki(2)}; from (41) we know that θ(xki)<θmin. Therefore, there exists some constant C(xki) such that for α≤C(xki), it holds that θ(xki+αdki)<θmin. So for α≤C(xki) we have (θ(xki+αdki),f(xki+αdki))∉ℱki(2). Thereby for α<min{C1,C(xki)}, we have
(44)(θ(xki+αdki),f(xki+αdki))∉ℱki(1)∪ℱki(2)=ℱki.Lemma 15.
Let{xki} be a subsequence with ∥dki∥≥ϵ for some constant ϵ>0 independent of ki. Then there exists K∈ℕ such that the filter is not augmented in iteration K; that is, K∉𝒜.Proof.
Since we havelimi→∞θ(xki)=0 by Theorem 8, it follows from Lemma 10 that there exist constants ϵ1,ϵ2>0 such that
(45)θ(xki)≤ϵ1,mki(α)≤-αϵ2,
for ki sufficiently large and α∈(0,1]. Without loss of generality we can assume that (45) is valid for all ki.
We can now apply Lemmas13 and 14 to obtain the constants α¯,C1,C(xki)>0. As limi→∞θ(xki)=0, choose a constant C2 and a sufficiently large K∈{ki} such that C(xK)>C2θ(xK)>0 and
(46)θ(xK)<min{α¯C2,C1C2,[ρC2ϵ2δ]1/(sθ-1)}.
We note that (46) implies that
(47)δ[θ(xK)]sθϵ2<ρC2θ(xK),
as well as
(48)C2θ(xK)<min{α¯,C1}.
Now define
(49)βK=C2θ(xK)=min{α¯,C1,C2θ(xK)}.
Lemmas 13 and 14 then imply that a trial step size αK,l≤βK satisfies
(50)f(xK(αK,l))≤f(xK)+ηmK(αK,l),(θ(xK(αK,l)),f(xK(αK,l)))∉ℱK.
If we now denote with αK,L the first step size satisfying (50), the backtracking line search procedure in Step  4 then implies that for α≥αK,l(51)α≥ρβK=ρC2θ(xK)>δ[θ(xK)]sθϵ2,
and therefore for α≥αK,l(52)δ[θ(xK)]sθ<αϵ2≤-mK(α).
This means that αK,l and all previous trial step sizes are f-step sizes. Hence the method does not switch to feasibility restoration phrase in Step  4 for those trial step sizes. Therefore, αK,l is the accepted step size αK indeed. Since it satisfies both the f-type switching conditions (5) and (6), the filter is not augmented in iteration K.Lemma 16.
Suppose that the filter is augmented infinite number of times; that is,|𝒜|=∞. Then
(53)limk→∞,k∈𝒜dk=0.Proof.
Suppose thatlimk→∞,k∈𝒜sup∥dk∥>0. Then there exist a subsequence {xkj} of {xk,k∈𝒜} and a constant ϵ>0, such that limj→∞θ(xkj)=0 and ∥dkj∥≥ϵ for all kj. Applying Lemma 15 to {xkj}, we see that there is an iteration kj, in which the filter is not augmented; that is to say, kj∉𝒜. This contradicts the choice of {xkj}, and then the claim follows.Although0≤tk≤θ(xk) and Theorem 8 can imply that limk→∞tk=0, the next lemma shows better result.Lemma 17.
Let{xki} be a subsequence with dki→0; then tki=0 for ki sufficiently large.Proof.
Consider thatdki→0 together with Lemma 5 implies for k sufficiently large
(54)bki≥aki=min{∥dki∥-1,∥λki∥1+δ1}=∥λki∥1+δ1.
On the other hand, we have from (9) that
(55)bki=∥λki∥1+vki-hki.
Thereby, it holds that vki>hki+δ1>0 for ki sufficiently large. So we get tki=0 for ki sufficiently large.Theorem 18.
Suppose that all stated assumptions hold; the outcome of applying Algorithm1 is one of the following.(A)
A KKT point of problem(P) is found (Algorithm 1 stops at Step  2).(B)
All limit points are feasible, and there exists at least one limit pointx* of {xk} which is a KKT point for the inequality constrained NLP (1); that is to say,
(56)limk→∞θ(xk)=0,and there exists at least one subsequence𝒦 such that
(57)limk→∞,k∈𝒦dk=limk→∞,k∈𝒦tk=0.Proof.
(A) It is obviously true.
(B) Equation (56) follows from Theorem 8. In order to show (57), we now distinguish it into two cases:(i)
if the filter is augmented only a finite number of times, from Lemmas11 and 17 we know every limit point is a KKT point for the inequality constrained NLP (1), so the claim is true,(ii)
if the filter is augmented infinite number of times, from Lemmas16 and 17 it holds that
(58)limk→∞,k∈𝒜dk=limk→∞,k∈𝒜tk=0.Let𝒦=𝒜; the claim is also true.
In a word, if Algorithm1 generates an infinite sequence of iterate {xk}, all limit points are feasible, and there exists at least one limit point x* of {xk} which is a KKT point for the inequality constrained NLP (1).


## 5. Numerical Experiments

In this section, we carry out some typical numerical experiments based on Algorithm1. In the whole process, the program is coded in MATLAB 7.0, and we use its optimization toolbox to solve the QP subproblem (8).(1)
During the numerical experiments, updating ofBk is done by the following damped BFGS formula (see [27, Chapter 18]):
(59)Bk+1=Bk-Bksk(sk)TBk(sk)TBksk+rk(rk)T(sk)Trk,wheresk=xk+1-xk, rk=θ^kyk+(1-θ^k)Bksk, yk=∇xL(xk+1,λk)-∇xL(xk,λk) and
(60)θ^k={1if(sk)Tyk≥0.2(sk)TBksk,0.8(sk)TBksk(sk)TBksk-(sk)Tykotherwise.(2)
The algorithm parameters are set as follows:(61)B1=En,b1=111,sθ=0.75,δ=1,δ1=10,δ2=11,η=0.25,ρ=0.5,γf=γθ=0.01,u=1000.(3)
The stop criteria are∥d0k∥ sufficiently small, where d0k=(dkT,tk)T. In particular, the stop criteria of Step  2 are changed to
(62)if∥d0k∥≤10-7,stop.(4)
Now we report the numerical results over a set of problems from [28], where no equality constraints are contained and an initial point is provided for each problem. In addition, we tested our algorithm in two cases: a feasible initial point is provided for each problem or an infeasible initial point is given. These results are listed in Tables 1 and 2, respectively. Because the quadratic subproblem (1) is modified but the filter technique is not used in [5, 7] and the filter technique is used but the quadratic subproblem (1) is not modified in [18, 23], for the sake of comparing equally, under the same initial points, we select examples tested both in [5, 7] and examples tested both in [18, 23] to do the comparisons. The comparison numerical results among our algorithm and two groups of methods are listed in Tables 3 and 4, respectively.Table 1
The detail information of the numerical results for feasible initial point.
No.
n
m
NIT
NOF
NOG
FV
hs001
2
1
35
88
65
2.394473
e
-
014
hs003
2
1
4
12
10
-
4.440892
e
-
016
hs004
2
2
2
2
2
2.666667
e
+
000
hs005
2
4
6
14
12
-
1.913222
e
+
000
hs012
2
1
5
12
11
-
3.000000
e
+
001
hs033
3
6
3
4
3
-
4.585786
e
+
000
hs035
3
4
7
15
13
1.111111
e
-
001
hs037
3
8
9
23
20
-
3.456000
e
+
003
hs043
4
3
10
14
13
-
4.399999
e
+
001
hs044
4
10
5
10
10
-
1.500000
e
+
001
hs076
4
7
6
7
7
-
4.681818
e
+
000
hs086
5
15
4
10
9
-
3.234868
e
+
001
hs100
7
4
6
22
20
6.806301
e
+
002
hs110
10
20
5
12
12
-
4.577847
e
+
001
hs113
10
8
12
16
15
2.430621
e
+
001
hs117
15
20
17
35
25
3.234868
e
+
001
hs118
15
59
21
42
36
6.648204
e
+
002Table 2
The detail information of the numerical results for infeasible initial point.
No.
n
m
NIT
NOF
NOG
FV
hs002
2
1
9
34
30
5.042618
e
-
002
hs010
2
1
4
14
12
-
1.000000
e
+
000
hs011
2
1
12
17
16
-
8.498464
e
+
000
hs013
2
3
16
30
26
1.000021
e
+
000
hs015
2
3
3
15
13
3.065000
e
+
002
hs016
2
5
12
27
24
2.500000
e
-
001
hs017
2
5
11
26
23
1.000000
e
+
000
hs021
2
5
3
6
6
-
9.995999
e
+
001
hs022
2
2
4
4
4
9.999999
e
-
001
hs023
2
9
6
12
11
2.000000
e
+
000
hs059
2
7
14
34
32
-
6.749505
e
+
000
hs065
3
7
8
12
10
9.535282
e
-
001
hs096
6
16
34
113
104
1.561953
e
-
002
hs108
9
14
12
26
22
-
8.660256
e
+
001Table 3
Comparison of our algorithm with two methods in [5, 7].
No.
Pro.
(n, m)
FilterSQP1
CSQP
JSQP
(NIT; NOF)
(NIT; NOF)
(NIT; NOF)
hs001
PBRT11
(2, 1)
(35; 88)
(332; 442)
(627; 700)
hs002
PBRT12
(2, 1)
(9; 34)
(11; 119)
F
hs003
QBRT11
(2, 1)
(4; 12)
(3; 3)
(3; 3)
hs004
PBRT13
(2, 2)
(2; 2)
(2; 2)
(2; 2)
hs005
GBRT11
(2, 4)
(6; 14)
(15; 32)
(17; 35)
hs010
LQRT11
(2, 1)
(4; 14)
(2; 2)
(2; 2)
hs011
QQRT12
(2, 1)
(12; 17)
F
F
hs012
QQRT13
(2, 1)
(5; 12)
(2; 9)
(3; 338)
hs013
QPRT11
(2, 3)
(16; 30)
(20; 20)
F
hs015
PQRT11
(2, 3)
(3; 15)
(3; 33)
(7; 498)
hs022
QQRT16
(2, 2)
(3; 4)
(7; 8)
(7; 8)
hs100
PPRP17
(7, 4)
(6, 22)
(7; 120)
(7; 7128)
hs108
QQRP16
(9, 14)
(12; 26)
(12; 12)
(12; 28)Table 4
Comparison of our algorithm with two methods in [18, 23].
No.
The initial point
Method
NIT
NOF
NOG
hs012
(0, 0)
FilterSQP1
5
12
11
FilterSQP2
7
10
8
FilterSQP3
8
9
9
hs033
(0, 0, 3)
FilterSQP1
3
4
3
FilterSQP2
3
4
4
FilterSQP3
4
5
5
hs043
(0, 0, 0, 0)
FilterSQP1
10
14
13
FilterSQP2
11
19
12
FilterSQP3
13
15
14
hs065
(−5, 5, 0)
FilterSQP1
8
12
10
FilterSQP2
15
11
10
FilterSQP3
9
10
10
hs076
(0.5, 0.5, 0.5, 0.5)
FilterSQP1
6
7
7
FilterSQP2
6
7
7
FilterSQP3
6
7
7
hs113
(2, 3, 5, 5, 1, 2, 7, 3, 6, 10)
FilterSQP1
12
16
15
FilterSQP2
14
25
15
FilterSQP3
16
18
17In Tables1, 2, 3, and 4, the notations mean as follows:(i)
No.: the number of problems in [28],(ii)
Pro.: the name of problems in [28],(iii)
n: the number of variables,(iv)
m: the number of inequality constraints,(v)
NIT: the number of iterations,(vi)
NOF: the number of evaluations of objective functions,(vii)
NOG: the number of evaluations of objective function gradient,(viii)
FV: the final value of the objective function,(ix)
F: it indicates the algorithm's failure on the problem,(x)
FilterSQP1: our algorithm in this paper,(xi)
JSQP: the algorithm proposed in [5],(xii)
CSQP: the algorithm proposed in [7],(xiii)
FilterSQP2: the algorithm proposed in [18],(xiv)
FilterSQP3: the algorithm proposed in [23].From Tables1 and 2, we can see that our algorithm executes well for these problems taken from [28]. Whenever the initial point is feasible or not, the results are promising. From the computation efficiency in Tables 3 and 4, we should point out that our algorithm is competitive with some existed SQP methods in terms of the number of iterations, for example, [5, 7, 18, 23].According to the forms of examples listed in these two groups of papers, we show the numerical results by two different representations in Tables3 and 4. From Table 3, our algorithm is competitive with the first group of methods, that is, two methods in [5, 7]. Especially utilizing the algorithm in this paper, the number of iterations for problem hs001 (i.e., PBRT11) is much smaller than ones in other two algorithms. And the problem hs011 (i.e., QQRT12) converges to a good approximate optimal solution with small iterations, while algorithms CSQP and JSQP both fail on it. From Table 4, our algorithm is also competitive with the second group of methods, that is, two methods in [18, 23]. Although the filter technique is taken in these three algorithms, the quadratic subproblem (1) in [18, 23] may be inconsistent, while the subproblem is always consistent, and it only needs to solve one QP subproblem at each iteration in our algorithm, which is simpler and can be applied much more conveniently.All results summarized in Tables1–4 show that our algorithm is practical and effective.


## 6. Conclusion

In this paper, combining a modification strategy of QP subproblem and the filter technique, we present a line search filter SQP method for inequality constrained optimization. This method can start with any arbitrary initial point rather than a feasible initial point; it makes use of a backtracking line search procedure to generate step size and the efficiency of the filter technique to determine step acceptance; it only needs to solve one QP subproblem at each iteration, and the subproblem is always consistent. Under some mild conditions, the method is well defined, and the global convergence property is obtained. Many numerical experiments in Section5 show that our algorithm is effective.



---

*Source: 524539-2013-09-11.xml*