# A Filter Algorithm with Inexact Line Search

Authors: Meiling Liu; Xueqian Li; Qinmin Wu
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

A filter algorithm with inexact line search is proposed
for solving nonlinear programming problems. The filter is constructed by employing
the norm of the gradient of the Lagrangian function to the infeasibility
measure. Transition to superlinear local convergence is showed for the proposed
filter algorithm without second-order correction. Under mild conditions, the
global convergence can also be derived. Numerical experiments show the efficiency
of the algorithm.


---

## Body

## 1. Introduction

Fletcher and Leyffer [1] proposed filter methods in 2002 offering an alternative to traditional merit functions in solving nonlinear programming problems (NLPs). The underlying concept is that a trial point is accepted provided that there is a sufficient decrease of the objective function or the constraint violation. Filter methods avoid the difficulty of determining a suitable value of the penalty parameter in the merit function. The promising numerical results in [1] led to a growing interest in filter methods in recent years. Two variants of trust-region filter sequential quadratic programming (SQP) method were proposed by Fletcher et al. [2, 3]. Chin and Fletcher [4] developed filter  method to sequential linear programming strategy that takes equality-constrained quadratic programming steps. Ribeiro et al. [5] proposed a general filter algorithm that does not depend on the particular method used for the step of computation. Ulbrich [6] argued superlinear local convergence of a filter SQP method. Ulbrich et al. [7] and Wächter and Biegler [8] applied filter technique to interior method and achieved the global convergence to first-order critical point. Wächter and Biegler [9, 10] proposed a line-search filter method and applied it to different algorithm framework. Gould et al. [11] and Shen et al. [12] developed new multidimensional filter technique. Su and Pu [13] extended the monotonicity of the filter technique. Nie [14] applied filter method to solve nonlinear complementarity problems. In this paper, the global convergence is analyzed widely. However, it has been noted by Fletcher and Leyffer [1] that the filter approach can suffer from the Maratos effect as that of a penalty function approach. By the Maratos effect, a full step can lead to an increase of both infeasibility measure and objective function in filter components even if arbitrarily close to a regular minimizer. This makes the full step unacceptable for the filter and can prohibit fast local convergence.In this paper, we propose a filter algorithm with inexact line-search for nonlinear programming problems that ensures superlinear local convergence without second-order correction steps. We use the norm of the gradient of the Lagrangian function in the infeasibility measure in the filter components. Moreover, the new filter algorithm has the same global convergence properties as that of the previous works [2, 3, 9]. In addition, since the sufficient decrease conditions in an SQP framework can usually make the algorithm complex and time-consuming, the presented method is a line-search method without using SQP steps. An inexact line-search criterion is used as the sufficient reduction conditions. In the end, numerical experiences also show the efficiency of the new filter algorithm.This paper is organized as follows. For the main part of the paper, the presented techniques will be applied to general NLP. In Section2, we state the algorithm mechanism. The convergent properties are shown in Section 3. The global and superlinear convergence are proved. Furthermore, the Maratos effect is avoided. Finally, Section 4 shows the effectiveness of our method under some numerical experiences.


## 2. Inexact Line-Search Filter Approach

### 2.1. The Algorithm Mechanism

We describe and analyze the line-search filter method for NLP with equality constraints. State it as(2.1)min⁡x∈Rnf(x)subjecttoci(x)=0,i∈E,
where the objective function f:ℝn→ℝ and the constraints ci are assumed to be continuously differentiable, and E={i∣i=1,2,…,m}.The corresponding Lagrangian function is(2.2)L(x,λ)=f(x)+λTc(x),
where the vector λ corresponds to the Lagrange multiplier. The Karush-Kuhn-Tucker (KKT) conditions for (2.1) are(2.3)∇f(x)+λT∇c(x)=0,c(x)=0.For a given initial estimatex0, the line-search algorithm generates a sequence of iterates xk by xk+1=xk+αkdk as the estimates of the solution for (2.1). Here, the search direction dk is computed from the linearization at xk of the KKT conditions (2.3):(2.4)(Wk∇c(xk)∇c(xk)0)(dkλ+)=-(∇f(xk)c(xk)),
where the symmetric matrix Wk denotes the Hessian ∇xx2L(xk,λk) of (2.2) or a positive definite approximation to it.After a search directiondk has been computed, the step size αk∈(0,1] is determined by a backtracking line-search procedure, where a decreasing sequence of step size αk is tried until some acceptable criteria are satisfied. Generally, the acceptable criteria are constructed by a condition that if the current trial point xk can provide sufficient reduction of a merit function. The filter method proposed by Fletcher and Leyffer [1] offers an alternative to merit functions. In this paper, the filter notion is defined as follows.Definition 2.1.
A pair(Vk,fk) is said to dominate another pair (Vl,fl) if and only if both Vk≤Vl and fk≤fl.Here, we defineV(x):=∥c(x)∥2+∥∇L(x)∥2 as the l2 norm of the infeasibility measure. That is, we modify the infeasibility measure in filter, with this modification, the superlinear convergence is possibly derived. Strictly, it is a stationarity measure. However, we still call it infeasibility measure according to its function. In the rest of paper, the norm is always computed by l2 norm excepting special noting.Definition 2.2.
A filter is a list of pairs(Vl,fl) such that no pair dominates any other. A point (Vk,fk) is said to be acceptable for inclusion in the filter if it is not dominated by any point in the filter.When a pair(Vk,fk) is said to be acceptable to the filter, we also say the iterate xk is acceptable to the filter. In filter notion, a trial point xk+1 is accepted if it improves feasibility or improves the objective function. So, it is noted that filter criteria is less demanding than traditional penalty function. When improving optimality, the norm of the gradient of the Lagrangian function will tend to zero, so it offers a more precise analysis for the objective function.However, this simple filter concept is not sufficient to guarantee global convergence. Fletcher et al. [3] replace this condition by requiring that the next iterate provides at least as much progress in one of the measure V or f that corresponds to a small fraction of the current infeasibility measure. Here, we use the similar technique to our filter. Formally, we say that a trial point can be accepted to the current iterate xk or the filter if(2.5a)V(xk)≤βV(xl)
or(2.5b)f(xk)≤f(xl)-γV(xk),for some fixed constants β,γ∈(0,1), and (V(xl),f(xl)) are points in current filter. In practical implementation, the constants β close to 1 and γ close to 0. However, the criteria (2.5a) and (2.5b) may make a trial point always provides sufficient reduction of the infeasibility measure alone, and not the objective function. To prevent this, we apply a technique proposed in Wächter and Biegler [10] to a different sufficient reduction criteria. The switching condition is(2.6)∇fkTdk<0,-αk[∇fkTdk]e1>δ[V(xk)]e2,
where δ>0, e2>1, e1≥2e2. If the condition (2.6) holds, we replace the filter condition (2.5b) as an inexact line-search condition, that is, the Armijo type condition(2.7)f(xk+1)≤f(xk)+ηαk∇fkTdk,
where η∈(0,1/2) is a constant. If (2.6) holds but not (2.7), the trial points are still determined by (2.5a) and (2.5b).If a trial pointxk can be accepted at a step size by (2.7), we refer to xk as an f type iterate and the corresponding αk as an f step size.


### 2.2. The Algorithm Analysis

By the right part of switching condition (2.6), it ensures that the improvement to the objective function by the Armijo condition (2.7) is sufficiently large compared to the current infeasibility measure V(xk). Thus, if iterate points remote from the feasible region, the decrease of the objective function can be sufficient. By setting e2>1, the progress predicted by the line model -αk[∇fkTdk]e1 of f can be a power of the infeasibility measure V(x). The choice of e1≥2e2 makes it possible that a full step can be accepted by (2.7) when it closes to a local solution.In this paper, we denote the filter as a setℱk containing all iterates accepted by (2.5a) and (2.5b). During the optimization, if the f type switching condition (2.6) holds and the Armijo condition (2.7) is satisfied, the trial point is determined by (2.7) not by (2.5a) and (2.5b), and the value of the objective function is strictly decreased. This can prevents cycling of the algorithm (see [10]).If the linear system (2.4) is incompatible, no search direction dk can be found and the algorithm switches to a feasibility restoration phase. In it, we try to decrease the infeasibility measure to find a new iterate xk+1 that satisfies (2.4) and is acceptable to the current filter. Similarly, in case ∇fkTdk<0, the sufficient decrease criteria for the objective function in (2.5b) may not be satisfied. To inspect where no admissible step size α can be found and the feasibility restoration phase has to be invoked, we can consider reducing α and define(2.8)αkmin⁡={min⁡{1-β,-γV(xk)-∇fkTdk,δ[V(xk)]e2[-∇fkTdk]e1},if∇fkTdk<0,1-β,otherwise.
If the trial step size α<αkmin, the algorithm turns to the feasibility restoration phase.Byαkmin, it is ensured that the algorithm does not switch to the feasibility restoration phase as long as (2.6) holds for a step size α<αk and that the backtracking line-search procedure is finite. Thus, for a trial point xk, the algorithm eventually either delivers a new iterate xk+1 or reverts to the feasibility restoration phase. Once finding a feasible direction, the algorithm still implements the normal algorithm.Of course, the feasibility restoration phase may not always be possible to find a point satisfying the filter-accepted criteria and the compatible condition. It may converge to a nonzero local minimizer of the infeasibility measure and indicate that the algorithm fails. In this paper, we do not specify the particular procedure for the feasibility restoration phase. Any method for dealing with a nonlinear algebraic system can be used to implement a feasibility restoration phase.


### 2.3. The Algorithm

We are now in the place to state the overall algorithm.Algorithm 2.3.
Step 1.
Given: starting pointx0, constants Vmax=max{104,1.2V(x0)}, β,γ∈(0,1), η∈(0,1/2), δ>0, e1≥2e2, e2>1, τ∈(0,1).Step 2.
Initialize:ℱ0={(Vmax,f(x0))}, the iteration counter k←0.Step 3.
Fork=0,1,2,…, stop if xk satisfies the KKT conditions (2.3).Step 4.
Compute the search directiondk from (2.4). If the system (2.4) is incompatible, go to the feasibility restoration phase in Step 7.Step 5.
Setα0=1, compute αkmin.(1)
Ifαk<αkmin, go to Step 7. Otherwise, compute the new trial point xk+1=xk+αkdk.(2)
If the conditions (2.6) and (2.7) hold, accept the trial step and go to Step 6, otherwise set xk=xk+1, go to Step 5(3).(3)
In case where noαk make (2.7) hold, if xk+1 can be accepted to the filter, augment the filter by ℱk+1=ℱk∪{(V(xk+1),f(xk+1))}, go to Step 6; Otherwise set xk=xk+1, go to Step 5(4).(4)
Computeαk+1=ταk, go back to Step 5(1).Step 6.
Increase the iteration counterk←k+1 and go back to Step 4.Step 7.
Feasibility restoration phase: by decreasing the infeasibility ofV to find a new iterate xk+1 such that (2.4) is compatible. And if (2.7) holds at xk+1, continue with the normal algorithm in Step 6; if (2.5a) and (2.5b) hold at xk+1, augment the filter by ℱk+1=ℱk∪{(V(xk+1),f(xk+1))}, and then continue with the normal algorithm in Step 6; if the feasibility restoration phase cannot find such a point, stop with insuccess.Remark 2.4.
In contrast to SQP method with trust-region technique, the actual step does not necessarily satisfy the linearization of the constraints.Remark 2.5.
Practical experience shows that the filter allows a large degree of nonmonotonicity and this can be advantageous to some problems.Remark 2.6.
To prevent the situation in which a sequence of points for which aref type iterative point with Vk→∞ is accepted, we set an upper bound Vmax on the infeasibility measure function V.For further specific implementation details of Algorithm2.3, see Section 4.


## 2.1. The Algorithm Mechanism

We describe and analyze the line-search filter method for NLP with equality constraints. State it as(2.1)min⁡x∈Rnf(x)subjecttoci(x)=0,i∈E,
where the objective function f:ℝn→ℝ and the constraints ci are assumed to be continuously differentiable, and E={i∣i=1,2,…,m}.The corresponding Lagrangian function is(2.2)L(x,λ)=f(x)+λTc(x),
where the vector λ corresponds to the Lagrange multiplier. The Karush-Kuhn-Tucker (KKT) conditions for (2.1) are(2.3)∇f(x)+λT∇c(x)=0,c(x)=0.For a given initial estimatex0, the line-search algorithm generates a sequence of iterates xk by xk+1=xk+αkdk as the estimates of the solution for (2.1). Here, the search direction dk is computed from the linearization at xk of the KKT conditions (2.3):(2.4)(Wk∇c(xk)∇c(xk)0)(dkλ+)=-(∇f(xk)c(xk)),
where the symmetric matrix Wk denotes the Hessian ∇xx2L(xk,λk) of (2.2) or a positive definite approximation to it.After a search directiondk has been computed, the step size αk∈(0,1] is determined by a backtracking line-search procedure, where a decreasing sequence of step size αk is tried until some acceptable criteria are satisfied. Generally, the acceptable criteria are constructed by a condition that if the current trial point xk can provide sufficient reduction of a merit function. The filter method proposed by Fletcher and Leyffer [1] offers an alternative to merit functions. In this paper, the filter notion is defined as follows.Definition 2.1.
A pair(Vk,fk) is said to dominate another pair (Vl,fl) if and only if both Vk≤Vl and fk≤fl.Here, we defineV(x):=∥c(x)∥2+∥∇L(x)∥2 as the l2 norm of the infeasibility measure. That is, we modify the infeasibility measure in filter, with this modification, the superlinear convergence is possibly derived. Strictly, it is a stationarity measure. However, we still call it infeasibility measure according to its function. In the rest of paper, the norm is always computed by l2 norm excepting special noting.Definition 2.2.
A filter is a list of pairs(Vl,fl) such that no pair dominates any other. A point (Vk,fk) is said to be acceptable for inclusion in the filter if it is not dominated by any point in the filter.When a pair(Vk,fk) is said to be acceptable to the filter, we also say the iterate xk is acceptable to the filter. In filter notion, a trial point xk+1 is accepted if it improves feasibility or improves the objective function. So, it is noted that filter criteria is less demanding than traditional penalty function. When improving optimality, the norm of the gradient of the Lagrangian function will tend to zero, so it offers a more precise analysis for the objective function.However, this simple filter concept is not sufficient to guarantee global convergence. Fletcher et al. [3] replace this condition by requiring that the next iterate provides at least as much progress in one of the measure V or f that corresponds to a small fraction of the current infeasibility measure. Here, we use the similar technique to our filter. Formally, we say that a trial point can be accepted to the current iterate xk or the filter if(2.5a)V(xk)≤βV(xl)
or(2.5b)f(xk)≤f(xl)-γV(xk),for some fixed constants β,γ∈(0,1), and (V(xl),f(xl)) are points in current filter. In practical implementation, the constants β close to 1 and γ close to 0. However, the criteria (2.5a) and (2.5b) may make a trial point always provides sufficient reduction of the infeasibility measure alone, and not the objective function. To prevent this, we apply a technique proposed in Wächter and Biegler [10] to a different sufficient reduction criteria. The switching condition is(2.6)∇fkTdk<0,-αk[∇fkTdk]e1>δ[V(xk)]e2,
where δ>0, e2>1, e1≥2e2. If the condition (2.6) holds, we replace the filter condition (2.5b) as an inexact line-search condition, that is, the Armijo type condition(2.7)f(xk+1)≤f(xk)+ηαk∇fkTdk,
where η∈(0,1/2) is a constant. If (2.6) holds but not (2.7), the trial points are still determined by (2.5a) and (2.5b).If a trial pointxk can be accepted at a step size by (2.7), we refer to xk as an f type iterate and the corresponding αk as an f step size.


## 2.2. The Algorithm Analysis

By the right part of switching condition (2.6), it ensures that the improvement to the objective function by the Armijo condition (2.7) is sufficiently large compared to the current infeasibility measure V(xk). Thus, if iterate points remote from the feasible region, the decrease of the objective function can be sufficient. By setting e2>1, the progress predicted by the line model -αk[∇fkTdk]e1 of f can be a power of the infeasibility measure V(x). The choice of e1≥2e2 makes it possible that a full step can be accepted by (2.7) when it closes to a local solution.In this paper, we denote the filter as a setℱk containing all iterates accepted by (2.5a) and (2.5b). During the optimization, if the f type switching condition (2.6) holds and the Armijo condition (2.7) is satisfied, the trial point is determined by (2.7) not by (2.5a) and (2.5b), and the value of the objective function is strictly decreased. This can prevents cycling of the algorithm (see [10]).If the linear system (2.4) is incompatible, no search direction dk can be found and the algorithm switches to a feasibility restoration phase. In it, we try to decrease the infeasibility measure to find a new iterate xk+1 that satisfies (2.4) and is acceptable to the current filter. Similarly, in case ∇fkTdk<0, the sufficient decrease criteria for the objective function in (2.5b) may not be satisfied. To inspect where no admissible step size α can be found and the feasibility restoration phase has to be invoked, we can consider reducing α and define(2.8)αkmin⁡={min⁡{1-β,-γV(xk)-∇fkTdk,δ[V(xk)]e2[-∇fkTdk]e1},if∇fkTdk<0,1-β,otherwise.
If the trial step size α<αkmin, the algorithm turns to the feasibility restoration phase.Byαkmin, it is ensured that the algorithm does not switch to the feasibility restoration phase as long as (2.6) holds for a step size α<αk and that the backtracking line-search procedure is finite. Thus, for a trial point xk, the algorithm eventually either delivers a new iterate xk+1 or reverts to the feasibility restoration phase. Once finding a feasible direction, the algorithm still implements the normal algorithm.Of course, the feasibility restoration phase may not always be possible to find a point satisfying the filter-accepted criteria and the compatible condition. It may converge to a nonzero local minimizer of the infeasibility measure and indicate that the algorithm fails. In this paper, we do not specify the particular procedure for the feasibility restoration phase. Any method for dealing with a nonlinear algebraic system can be used to implement a feasibility restoration phase.


## 2.3. The Algorithm

We are now in the place to state the overall algorithm.Algorithm 2.3.
Step 1.
Given: starting pointx0, constants Vmax=max{104,1.2V(x0)}, β,γ∈(0,1), η∈(0,1/2), δ>0, e1≥2e2, e2>1, τ∈(0,1).Step 2.
Initialize:ℱ0={(Vmax,f(x0))}, the iteration counter k←0.Step 3.
Fork=0,1,2,…, stop if xk satisfies the KKT conditions (2.3).Step 4.
Compute the search directiondk from (2.4). If the system (2.4) is incompatible, go to the feasibility restoration phase in Step 7.Step 5.
Setα0=1, compute αkmin.(1)
Ifαk<αkmin, go to Step 7. Otherwise, compute the new trial point xk+1=xk+αkdk.(2)
If the conditions (2.6) and (2.7) hold, accept the trial step and go to Step 6, otherwise set xk=xk+1, go to Step 5(3).(3)
In case where noαk make (2.7) hold, if xk+1 can be accepted to the filter, augment the filter by ℱk+1=ℱk∪{(V(xk+1),f(xk+1))}, go to Step 6; Otherwise set xk=xk+1, go to Step 5(4).(4)
Computeαk+1=ταk, go back to Step 5(1).Step 6.
Increase the iteration counterk←k+1 and go back to Step 4.Step 7.
Feasibility restoration phase: by decreasing the infeasibility ofV to find a new iterate xk+1 such that (2.4) is compatible. And if (2.7) holds at xk+1, continue with the normal algorithm in Step 6; if (2.5a) and (2.5b) hold at xk+1, augment the filter by ℱk+1=ℱk∪{(V(xk+1),f(xk+1))}, and then continue with the normal algorithm in Step 6; if the feasibility restoration phase cannot find such a point, stop with insuccess.Remark 2.4.
In contrast to SQP method with trust-region technique, the actual step does not necessarily satisfy the linearization of the constraints.Remark 2.5.
Practical experience shows that the filter allows a large degree of nonmonotonicity and this can be advantageous to some problems.Remark 2.6.
To prevent the situation in which a sequence of points for which aref type iterative point with Vk→∞ is accepted, we set an upper bound Vmax on the infeasibility measure function V.For further specific implementation details of Algorithm2.3, see Section 4.


## 3. Convergence Analysis

### 3.1. Global Convergence

In this section, we give a global convergence analysis of Algorithm2.3. We refer to the global convergence analysis of Wächter and Biegler [10] in some places. First, state the necessary assumptions.Assumption A1.
Let all iteratesxk are in a nonempty closed and bounded set S of ℝn.Assumption A2.
The functionsf and c are twice continuously differentiable on an open set containing S.Assumption A3.
The matrixWk is positive definite on the null space of the Jacobian ∇c(xk) and uniformly bounded for all k, and the Lagrange multiply λ is bounded for all k.AssumptionsA1 and A2 are the standard assumptions. Assumption A3 plays an important role to obtain the convergence result and ensures that the algorithm is implementable.For stating conveniently, we define a setJ={i∣xiisacceptedtothefilter}. In addition, sometimes, it is need to revise Wk to keep it positive definite by some updating methods such as damped BFGS formula [15] or revised Broyden’s method [16].From AssumptionsA1–A3, we can get(3.1)‖dk‖≤Md,mW‖dk‖2≤dkTWkdk≤MW‖dk‖2,‖λk‖≤Mλ,
where Md, Mλ, MW, and mW are constants.Lemma 3.1.
Suppose AssumptionsA1–A3 hold, if {xki} is a subsequence of iterates for which ∥dki∥>ϵ1 with a constant ϵ1>0 independent of ki, then for constant ϵ2=(mW/2)ϵ1, if V(xki)≤(mW/2Mλ)ϵ1, then
(3.2)∇f(xki)Tdki≤-ϵ2.Proof.
By the linear system (2.4) and (3.1),
(3.3)∇fkiTdki=-λkiT∇c(xki)dki-dkiTWkidki=λkiTc(xki)-dkiTWkidki≤MλV(xki)-mW‖dki‖2≤MλmW2Mλϵ1-mWϵ1=-ϵ2.Lemma3.1 shows that the search direction is a descent direction for the objective function when the trial points are sufficiently close to feasible region.Lemma 3.2.
Suppose AssumptionsA1–A3 hold, and that there exists an infinite subsequence {xki} of {xk} such that conditions (2.6) and (2.7) hold. Then
(3.4)lim⁡k→∞V(xki)=0.Proof.
From AssumptionsA1 and A2, we know that ∇f is bounded. Hence, it has with (3.1) that there exists a constant Mm>0 such that
(3.5)|∇fkTdk|≤Mm.
By (2.6) it has
(3.6)δ[V(xki)]e2<-αki[∇fkiTdki]e1≤Mme1αki.
As 1-1/e1>0, we have
(3.7)(δMme1)1-1/e1[V(xki)]e2-e2/e1<αki1-1/e1.
Then by (2.7) and (3.7),
(3.8)f(xki+1)-f(xki)≤ηαki∇fkiTdki<-ηδ1/e1αki1-1/e1[V(xki)]e2/e1<-ηδ1/e1(δMme1)1-1/e1[V(xki)]e2.
Hence, for c1:=ηδ1/e1(δ/Mme1)1-1/e1, an integer K and all j=1,2,…,
(3.9)f(xK+j)=f(xK)+∑ki=KK+j-1(f(xki+1)-f(xki))<f(xK)-c1∑ki=KK+j-1[V(xki)]e2.
Since f(xK+j) is bounded below as j→∞, the series on the right hand side in the last line of (3.8) is bounded, then implies the conclusion.Lemma 3.3.
Let{xki}⊂{xk} be an infinite subsequence of iterates so that (V(xki),f(xki)) is entered into the filter. Then
(3.10)lim⁡i→∞V(xki)=0.Proof.
Here, we refer to the proof of [2, Lemma  3.3]. If the conclusion is not true, there exists an infinite subsequence {kj}⊂{ki}⊂J such that
(3.11)V(xkj)≥ϵ,
for all j and for some ϵ>0. This means that no other (V,f) pair can be added to the filter at a later stage within the region
(3.12)[Vkj-(1-β)ϵ,Vkj]×[fkj-γϵ,fkj],
or with the intersection of this region with
(3.13)S0=[0,Vmax⁡]×[fmin⁡,∞]
for some constants fmin≤f(xk). Now, the area of each of these regions is (1-β)γϵ2. Hence, the set S0∪{(V,f)∣f≤Mf} is completely covered by at most a finite number of such regions, for any Mf≥fmin. Since the pairs (Vkj,fkj) keep on being added to the filter, fkj tends to infinity when i tends to infinity. Without loss of generality, assume that fkj+1≥fkj for all j is sufficiently large. But (2.5a) and (3.11) imply that
(3.14)Vkj+1≤βVkj,
so Vkj→0, which contradicts (3.11). Then, this latter assumption is not true and the conclusion follows.Next, we show that if{xk} is bounded, there exists at least one limit point of the iterative points is a first-order optimal point for (2.1).Lemma 3.4.
Suppose AssumptionsA1–A3 hold. Let {xki} be a subsequence with ∇fkiTdki<-ϵ2 for a constant ϵ2>0 independent of ki. Then, there exists a constant α¯>0 so that for all ki and αki<α¯,(3.15)f(xki+αkidki)-f(xki)≤ηαki∇fkiTdki.Proof.
From AssumptionsA1 and A2, dT∇2f(x)d≤cf∥d∥2 for some constant cf>0. Thus, it follows from the Taylor Theorem and (3.1) that(3.16)f(xki+αkidki)-f(xki)-αki∇fkiTdki=αki2dkiT∇2f(y1)dki≤cfαki2‖dki‖2≤αki(1-η)ϵ2≤-(1-η)αki∇fkiTdki,
if αki≤αki̅:=(1-η)ϵ2/cfMd2, where y1 denotes some point on the line segment from xki to xki+αkidki. Then the conclusion follows.Lemma 3.5.
Suppose AssumptionsA1–A3 hold, and the filter is augmented only a finite number of times, then(3.17)lim⁡k→∞‖dk‖=0.Proof.
Since the filter is augmented only a finite number of times, there exists an integerK1 so that for all iterates {xk}k>K1 the filter is not augmented. If the claim is not true, there must exist a subsequence {xki} and a constant ϵ>0 so that ∥dki∥≥ϵ for all i. Then by Lemma 3.1, it has ∇fkiTdki≤-ϵ2 for all ki≥K2, K2 is some integer and K2>K1. And from Lemmas 3.2 and 3.4, it has V(xki)≤ϵ and
(3.18)f(xki+1)-f(xki)≤ηαki∇fkiTdki≤-αkiηϵ2.
Since f(xki) is bounded below and monotonically decreasing for all k≥K2, one can conclude that limi→∞αki=0. This means that for ki>K2 the step size α=1 has not been accepted. So, we can get a αki<1 such that a trial point xki+1=xki+αkidki satisfies
(3.19)(V(xki+1),f(xki+1))∉Fki
or
(3.20)f(xki+1)-f(xki)>ηαki∇fkiTdki.
Let Vmin=min{Vk∣(Vk,fk)∈ℱk}. From Lagrange’s Theorem, it has
(3.21)V(xki+1)=V(xki)+αki∇V(y2)Tdki≤V(xki)+αki‖∇V(y2)‖‖dki‖≤V(xki)+cVαkiMd,
for some constant cV, where y2 denotes some point on the line segment from xki to xki+αdki. Since limi→∞αki=0 and limi→∞V(xki)=0 by Lemmas 3.2 and 3.3, it has V(xki+1)<Vmin for ki sufficiently large, so (3.19) is not true. In case (3.20), since αki→0 for sufficiently large ki, we have αki≤α¯ with α¯ from Lemma 3.4, that is, (3.20) can not be satisfied. Then the conclusion follows.Lemma 3.6.
Suppose AssumptionsA1–A3 hold. Let {xki} be a subsequence of {xk} with ∇fkiTdki≤-ϵ2 for a constant ϵ2>0 independent of ki. Then, there exists trial points can be accepted to the filter.Proof.
The mechanisms of Algorithm2.3 ensure that the first iterate can be accepted to the filter. Next, we can assume that (V(xk),f(xk)) is acceptable to the kth filter and (V(xl),f(xl))∈ℱk,l<k. If αki≤c2:=ϵ2/Md2cf, it has
(3.22)αki2≤αkiϵ2Md2cf≤-αki∇fkiTdkicf‖dki‖2,
that is, αki∇fkiTdki+cfαki2∥dki∥2≤0, so by (3.16)
(3.23)f(xki+αkidki)≤f(xki).
Similarly, if αki≤c3V(xki)≤V(xki)/∥d∥2cV, with c3:=1/Md2cV and cV from Lemma 3.5, it has
(3.24)-αkiV(xki)+cVαki2‖dki‖2≤0,V(xki+αkidki)≤V(xki).
Hence, we have
(3.25)f(xki+1)=f(xki+αkidki)≤f(xki)≤f(xl)-γV(xl),V(xki+1)=V(xki+αkidki)≤V(xki)≤βV(xl).
The claim then follows from (3.25).The last Lemma3.6 shows, for case V(xk)>0, Algorithm 2.3 either accepts a new iterate to the filter or switches to the feasibility restoration phase. For case V(xk)=0 and the algorithm does not stop at a KKT point, then ∇fkTdk<0, αkmin=0, and the Armijo condition (2.7) is satisfied for sufficiently small step size αk, so an f type iterate is accepted. Hence, the inner loop in Step 5 always terminates in a finite number of trial steps, and Algorithm 2.3 is well defined.Lemma 3.7.
Suppose AssumptionsA1–A3 hold. Let {xki} be a subsequence with ∥dki∥≥ϵ for a constant ϵ>0 independent of ki. Then, there exists an sufficient large integer K such that for all ki>K the algorithm can generate some trial points either be accepted to the filter or be f type steps.Proof.
By Lemmas3.1, 3.2, and 3.3, there exist constants ϵ1,ϵ2>0 so that
(3.26)V(xki)≤ϵ1,∇fkiTdki<-ϵ2
for all ki>K.
IfV(xki)=0, the f type switching condition (2.6) is true, there must exist iterates for which are f type iterates. For the remaining iterates with V(xki)>0, if(3.27)V(xki)<min⁡{α¯c3,c2c3,[τc3ϵ2e1δ]1/e2-1},
with α¯ from Lemma 3.4 and c2,c3 from Lemma 3.6, it implies with e2>1(3.28)δ[V(xki)]e2ϵ2e1<τc3V(xki),
as well as
(3.29)c3V(xki)<min⁡{α¯,c2}.
Now choose an arbitrary ki≥K with V(xki)>0 and define
(3.30)c4:=c3V(xki)=min⁡{α¯,c2,c3V(xki)}.
Lemmas 3.4 and 3.6 then imply that a trial step size αki≤c4 satisfies both
(3.31)f(xki+αkidki)≤f(xki)+ηαki∇fkiTdki,(V(xki+αkidki),f(xki+αkidki))∈Fki.
Sinceα>ταk>ταkmin by the definition of αkmin, the method does not switch to the feasibility restoration phase for those trial step sizes. Then the claim follows.Based on the above lemmas, we can give the main global convergence result.Theorem 3.8.
Suppose AssumptionsA1–A3 hold, then
(3.32)lim⁡k→∞V(xk)=0,(3.33)lim⁡k→∞‖dk‖=0,
that is, there exits a limit point x¯ of {xk} which is a first-order optimal point for (2.1).Proof.
(3.32) follows from Lemmas 3.2 and 3.3.
If the filter is augmented a finite number of times, then the claim (3.33) holds from Lemma 3.5. For either case, there exists a subsequence {xki} so that ki∈J for all i. Suppose the conclusion (3.33) is not true, there must exist a subsequence {xkj} of {xki} such that ∥dkj∥≥ϵ for some constant ϵ>0. Hence by Lemmas 3.1 and 3.3, it has ∇fkjTdkj<-ϵ2 and limi→∞V(xkj)=0 for all kj. Then by Lemma 3.7, when α<min{α¯,c2,c3V(xkj)}, the algorithm can generate a f type iterate, that is, the filter is not augmented, this contradicts the choice of {xkj}, so that (3.33) holds.


### 3.2. Local Convergence

In this section, we show the local convergence of Algorithm2.3.Assumption A4.
The iteratesxk converge to a point x¯ that satisfies(3.34)V(x¯)=0,∇xL(x¯,λ¯)=0,∇xxL(x¯,λ¯)ispositivedefiniteon⁡{d:∇c(x¯)Td=0},∇c(x¯)hasfull-rowrank⁡.Assumption A5.
There is a neighborhoodN(x¯) of x¯ such that Wk=∇xxL(xk,λk), for all xk∈N(x¯).Remark 3.9.
Under AssumptionA4, the point x¯ is a strict local minimum of (2.1).Remark 3.10.
Under AssumptionsA4 and A5, it is well known that with the choice xk+1=xk+dk, the sequence {xk} converges q-superlinearly to x¯ and that the convergence is q-quadratic if ∇xxf and ∇xxci are lipschitz continuous in a neighborhood of x¯. That is, for any given ζ∈[0,1], xj∈N(x¯), j=k,k+1,…, and xj+1=xj+dj, it has
(3.35)‖dj+1‖≤ζ‖dj‖,‖xj+1-x¯‖≤ζ‖xj-x¯‖.
We use the proof techniques of local convergence in [6]. In proof, define lρ(x,λ)=L(x,λ)+(ρ/2)∥c(x)∥22 and l̂ρ(x,λ)=f(x)+(ρ/2)V(x) with ρ is a parameter.Lemma 3.11.
Suppose AssumptionsA1–A3 hold. Let x¯ satisfy the Assumption A4. Then, there exist constants 0<r<t, ρ0>0 and a neighborhood Nσ(x¯)={x:∥x-x¯∥<σ}⊂N(x¯) such that
(3.36)r2‖x-x¯‖2+ρ-ρ02‖c(x)‖2≤lρ(x,λ)-lρ(x¯,λ¯)≤t(1+ρ)‖x-x¯‖2,
for all ρ≥ρ0 and all x∈Nσ(x¯).
Moreover, possibly after increasingt>0,ρ0>0 and reducing σ>0, we have that for all ρ≥ρ0 and all x∈Nσ(x¯)(3.37)r2‖x-x¯‖2+ρ-ρ02V(x)≤l̂ρ(x,λ)-l̂ρ(x¯,λ¯)≤t(1+ρ)‖x-x¯‖2.Proof.
Letx∈N(x¯). Using Taylor’s Theorem and ∇xlρ(x¯,λ¯)=0,∇λlρ(x¯,λ¯)=0, we have with some (x′,λ′) on the line segment between (x¯,λ¯) and (x,λ)(3.38)lρ(x,λ)-lρ(x¯,λ¯)=12(x-x¯)T∇xxlρ(x′,λ′)(x-x¯)+(x-x¯)T∇xλlρ(x′,λ′)(λ-λ¯).
Obviously, it has
(3.39)∇xxlρ(x′,λ′)=∇xxlρ/2(x′,λ′+ρ2c(x′))+ρ2∇c(x′)T∇c(x′).
Under Assumption A4, there exists ρ¯>0 such that for all ρ≥ρ¯,
(3.40)dT∇xxlρ/2(x¯,λ¯)d≥4r‖d‖2,∀d∈Rn,
with a constant r>0, see [15, Theorem  17.5].
Supposeλ(x) is Lipschitz continuous and Ly is the Lipschitz constant of λ, and ρ¯>0 is a constant. Let ρ0:=max{ρ¯,4Ly2/r} for all x with ∥x-x¯∥≤σ, it has by continuity(3.41)dT∇xxlρ0/2(x,λ+ρ02c(x))d≥2r‖d‖2,∀d∈Rn.
Thus, we obtain for all x∈Nσ(x¯) by (3.38), (3.39), and (3.41)
(3.42)lρ0(x,λ)-lρ0(x¯,λ¯)≥r‖x-x¯‖2+ρ04‖∇c(x′)(x-x¯)‖2+(λ-λ¯)T∇c(x′)(x-x¯).
It is obvious for all s>0 that
(3.43)2(λ-λ¯)T∇c(x′)(x-x¯)≥-1s‖∇c(x′)(x-x¯)‖2-s‖λ-λ¯‖2≥-1s‖∇c(x′)(x-x¯)‖2-sLy2‖λ-λ¯‖2.
If s=r/Ly2, 1/s=Ly2/r≤ρ0/4, then it has
(3.44)lρ0(x,λ)-lρ0(x¯,λ¯)≥r2‖x-x¯‖2+ρ08‖∇c(x′)(x-x¯)‖2.
Since c(x¯)=0, lρ(x¯,λ¯)=lρ0(x¯,λ¯)=f(x¯), and by (3.44) it has
(3.45)lρ(x,λ)-lρ(x¯,λ¯)=lρ0(x,λ)-lρ0(x¯,λ¯)+ρ-ρ02‖c(x)‖2≥r2‖x-x¯‖2+ρ-ρ02‖c(x)‖2,
that is the left inequality in (3.36). For the right inequality in (3.36), it is obvious from (3.38) that for all x∈N(x¯),
(3.46)lρ(x,λ)-lρ(x¯,λ¯)≤t(1+ρ)‖x-x¯‖2,
with a constant t>0. This proves the inequality (3.36).
ChooseK large enough such that for j≥k≥K, c(xj)→0. We can assume ∥c(x)∥<1. Then, if ρ0 is large enough, it has from (3.44) and l̂ρ(x¯,λ¯)=lρ0(x¯,λ¯)=f(x¯) that(3.47)l̂ρ0(x,λ)-l̂ρ0(x¯,λ¯)≥lρ0(x,λ)-lρ0(x¯,λ¯)≥r2‖x-x¯‖2.
By an analogue of (3.45) holds for l̂ρ, this proves the left inequality in (3.37).
On the other hand, it has(3.48)l̂ρ(x,λ)-l̂ρ(x¯,λ¯)=f(x)+ρ2V(x)-f(x¯).
Since f(x) and c(x) are twice continuously differentiable on closed set S, we have f(x)-f(x¯)=O(∥x-x¯∥2) and V(x)=O(∥x-x¯∥2). This shows the right inequality in (3.37) possibly after increasing t.Lemma 3.12.
Letx¯ satisfy Assumptions A4 and A5. Then for any ζ∈[0,1] and M≥1, there is an index K such that for all k≥K, with
(3.49)‖xk-x¯‖≤Mmin⁡(Vl,fl)∈Fk‖xl-x¯‖,
the points xj+1, j=k,k+1,…, with αk=1 are acceptable to
(3.50)Fj:=Fk∪(Vk,fk)∪(Vk+1,fk+1)∪⋯∪(Vj,fj).Proof.
LetN(x¯) as in Assumption A5,ζ=1/2,ρ0 and Nσ(x¯)⊂N(x¯) be given by Lemma 3.11. For all k≥K1, K1 is a sufficient large integer, and choose ρ≥ρ0 so large that
(3.51)β(ρ2-γ)≥βρ4,ρ-ρ02≥(1-β4)ρ2.
Then, it has from (3.37) in Lemma 3.11(3.52)r2‖x-x¯‖2+(1-β4)ρ2V(x)=l̂ρ(x,λ)-l̂ρ(x¯,λ¯)≤t(1+ρ)‖x-x¯‖2.
Let
(3.53)V′:=min⁡(Vj,fj)∈FK1⁡Vj.
By V′>0 and continuity there exists 0<σ1<σ such that V(x)≤βV′ for all x∈Nσ1(x¯), so the point x is acceptable to ℱK1. Since xk→x¯, xk∈Nσ1(x¯) for all k≥K2>K1, K2 is an integer. By (3.35), we can choose σ1 so small that for all k≥K2, the sequence {xj}j≥k with αk=1 converges linearly with a contraction factor of at least
(3.54)‖xj+1-x¯‖≤12(1-1-β/21-β/4)r2M2t(1+ρ)‖xj-x¯‖≤12‖xj-x¯‖.
Suppose an arbitrary k2≥K2 such that (3.49) holds, and set σ2:=∥xk-x¯∥. By (3.54), it has xk+1∈Nσ2(x¯) and xk+1 is acceptable to ℱK1. Next, it is a need to show that xk is acceptable with respect to (Vl,fl)∈ℱk∪(Vk,fk) for K1≤l≤k. By (3.49), it has xl∈Nσ(x¯)∖Nσ2/M(x¯), so by (3.52)
(3.55)l̂ρ(xl,λl)-l̂ρ(x¯,λ¯)≥r2M2σ22+(1-β4)ρ2Vl.
And, by (3.52) and (3.54)
(3.56)l̂ρ(xk+1,λk+1)-l̂ρ(x¯,λ¯)≤t(1+ρ)‖xk+1-x¯‖2≤12(1-1-β/21-β/4)r2M2σ22.
Next, suppose (x,λ) with x∈Nσ2(x¯) is not acceptable to (Vl,fl) then
(3.57)V(x)>βVl,f(x)+γV(x)>fl.
Thus, it has with (3.51) and (3.52)
(3.58)l̂ρ(x,λ)=f(x)+ρ2V(x)>fl+(ρ2-γ)V(x)>fl+β(ρ2-γ)Vl≥fl+β(ρ4)Vl=l̂ρ(xl,λl)-(1-β2)ρ2Vl≥l̂ρ(xl,λl)-1-β/21-β/4(l̂ρ(xl,λl)-l̂ρ(x¯,λ¯)).
This shows with (3.55) that
(3.59)l̂ρ(x,λ)-l̂ρ(x¯,λ¯)>(1-1-β/21-β/4)(l̂ρ(xl,λl)-l̂ρ(x¯,λ¯))≥(1-1-β/21-β/4)r2M2σ22.
This produces a contradiction to (3.56), so xk+1 is acceptable to ℱk∪(Vk,fk). Then, the acceptability of (Vj+1,fj+1) for ℱl follows by induction.Next, we show that the sequence{xj}j≥k with αk=1 can make the sufficient decreasing condition (2.7) hold.Lemma 3.13.
Suppose AssumptionsA1–A3 hold. Let x¯ satisfy Assumptions A4 and A5 and let K be as in Lemma 3.11. Then for all k>K the sequence {xj}j≥K with αj=1 satisfies
(3.60)f(xj+1)≤f(xj)+ηαj∇fjTdj.Proof.
Supposeαj∇fjTdj<0 and αj[∇fjTdj]e1<-δ[V(xj)]e2 hold. By αj=1, thus
(3.61)∇fjTdj<-(δ)1/e1[V(xj)]e2/e1.
On the other hand, withαj=1 the assertion f(xj+1)≤f(xj)+η∇fjTdj yields(3.62)η∇fjTdj≥∇fjTdj+12djT∇xx2f(x′)dj.
Thus,
(3.63)∇fjTdj≤-12(1-η)djT∇xx2f(x′)dj,
where x′ on the line segment between xj and xj+1.
Obviously, we can prove the conclusion if withK>0 large enough and for all j≥k≥K the following holds(3.64)-(δ)1/e1[V(xj)]e2/e1≤-12(1-η)djT∇xx2f(x′)dj.
Sincecj+∇cjTdj=0, dj=-∇cjT(∇cj∇cjT)-1cj. By Assumption A4, ∇cj has full-row rank, there exists cd>0 such that(3.65)‖dj‖≤cdV(xj),
thus,
(3.66)‖dj‖2≤cd2[V(xj)]2.
ChooseK large enough such that V(xj)≤1 for all j≥k≥K. By e1>2e2 and (3.66) it has(3.67)‖dj‖2≤cd2c5[V(xj)]e2/e1,
for a constant c5:=2δ1/e1(1-η)/cfcd2, we can choose suitable parameters such that the last inequality holds. Thus,
(3.68)δ1/e1[V(xj)]e2/e1≥12(1-η)cf‖dj‖2≥12(1-η)djT∇xx2f(x′)dj.
This completes the proof.Theorem 3.14.
Suppose AssumptionsA1–A5 hold. Then, there exists K>0 such that Algorithm 2.3 takes steps with αk=1 for all k≥K, that is,
(3.69)xk+1=xk+dk.
In particular, xk converges q-superlinearly to x¯. If ∇xxf and ∇xxci are Lipschitz continuous in a neighborhood of x¯ then xk converges q-quadratically.Proof.
Since AssumptionsA4 and A5 hold, xk→x¯ with x¯ satisfying A4. By Lemmas 3.12 and 3.13, the iterate (xk+1,λk+1)=(xk+dk,λ(xk+dk)) is acceptable to the filter ℱk∪(Vk,fk) and satisfies the sufficient decreasing condition (2.7). Thus, the trial iterate (xk+dk,λ(xk+dk)) is accepted by the algorithm and it has
(3.70)xk+1=xk+dk,λk+1=λ(xk+dk).
That is in both cases the algorithm takes the steps with αk=1. And according to Remark 3.10, {xk} converges q-superlinearly to x¯.


## 3.1. Global Convergence

In this section, we give a global convergence analysis of Algorithm2.3. We refer to the global convergence analysis of Wächter and Biegler [10] in some places. First, state the necessary assumptions.Assumption A1.
Let all iteratesxk are in a nonempty closed and bounded set S of ℝn.Assumption A2.
The functionsf and c are twice continuously differentiable on an open set containing S.Assumption A3.
The matrixWk is positive definite on the null space of the Jacobian ∇c(xk) and uniformly bounded for all k, and the Lagrange multiply λ is bounded for all k.AssumptionsA1 and A2 are the standard assumptions. Assumption A3 plays an important role to obtain the convergence result and ensures that the algorithm is implementable.For stating conveniently, we define a setJ={i∣xiisacceptedtothefilter}. In addition, sometimes, it is need to revise Wk to keep it positive definite by some updating methods such as damped BFGS formula [15] or revised Broyden’s method [16].From AssumptionsA1–A3, we can get(3.1)‖dk‖≤Md,mW‖dk‖2≤dkTWkdk≤MW‖dk‖2,‖λk‖≤Mλ,
where Md, Mλ, MW, and mW are constants.Lemma 3.1.
Suppose AssumptionsA1–A3 hold, if {xki} is a subsequence of iterates for which ∥dki∥>ϵ1 with a constant ϵ1>0 independent of ki, then for constant ϵ2=(mW/2)ϵ1, if V(xki)≤(mW/2Mλ)ϵ1, then
(3.2)∇f(xki)Tdki≤-ϵ2.Proof.
By the linear system (2.4) and (3.1),
(3.3)∇fkiTdki=-λkiT∇c(xki)dki-dkiTWkidki=λkiTc(xki)-dkiTWkidki≤MλV(xki)-mW‖dki‖2≤MλmW2Mλϵ1-mWϵ1=-ϵ2.Lemma3.1 shows that the search direction is a descent direction for the objective function when the trial points are sufficiently close to feasible region.Lemma 3.2.
Suppose AssumptionsA1–A3 hold, and that there exists an infinite subsequence {xki} of {xk} such that conditions (2.6) and (2.7) hold. Then
(3.4)lim⁡k→∞V(xki)=0.Proof.
From AssumptionsA1 and A2, we know that ∇f is bounded. Hence, it has with (3.1) that there exists a constant Mm>0 such that
(3.5)|∇fkTdk|≤Mm.
By (2.6) it has
(3.6)δ[V(xki)]e2<-αki[∇fkiTdki]e1≤Mme1αki.
As 1-1/e1>0, we have
(3.7)(δMme1)1-1/e1[V(xki)]e2-e2/e1<αki1-1/e1.
Then by (2.7) and (3.7),
(3.8)f(xki+1)-f(xki)≤ηαki∇fkiTdki<-ηδ1/e1αki1-1/e1[V(xki)]e2/e1<-ηδ1/e1(δMme1)1-1/e1[V(xki)]e2.
Hence, for c1:=ηδ1/e1(δ/Mme1)1-1/e1, an integer K and all j=1,2,…,
(3.9)f(xK+j)=f(xK)+∑ki=KK+j-1(f(xki+1)-f(xki))<f(xK)-c1∑ki=KK+j-1[V(xki)]e2.
Since f(xK+j) is bounded below as j→∞, the series on the right hand side in the last line of (3.8) is bounded, then implies the conclusion.Lemma 3.3.
Let{xki}⊂{xk} be an infinite subsequence of iterates so that (V(xki),f(xki)) is entered into the filter. Then
(3.10)lim⁡i→∞V(xki)=0.Proof.
Here, we refer to the proof of [2, Lemma  3.3]. If the conclusion is not true, there exists an infinite subsequence {kj}⊂{ki}⊂J such that
(3.11)V(xkj)≥ϵ,
for all j and for some ϵ>0. This means that no other (V,f) pair can be added to the filter at a later stage within the region
(3.12)[Vkj-(1-β)ϵ,Vkj]×[fkj-γϵ,fkj],
or with the intersection of this region with
(3.13)S0=[0,Vmax⁡]×[fmin⁡,∞]
for some constants fmin≤f(xk). Now, the area of each of these regions is (1-β)γϵ2. Hence, the set S0∪{(V,f)∣f≤Mf} is completely covered by at most a finite number of such regions, for any Mf≥fmin. Since the pairs (Vkj,fkj) keep on being added to the filter, fkj tends to infinity when i tends to infinity. Without loss of generality, assume that fkj+1≥fkj for all j is sufficiently large. But (2.5a) and (3.11) imply that
(3.14)Vkj+1≤βVkj,
so Vkj→0, which contradicts (3.11). Then, this latter assumption is not true and the conclusion follows.Next, we show that if{xk} is bounded, there exists at least one limit point of the iterative points is a first-order optimal point for (2.1).Lemma 3.4.
Suppose AssumptionsA1–A3 hold. Let {xki} be a subsequence with ∇fkiTdki<-ϵ2 for a constant ϵ2>0 independent of ki. Then, there exists a constant α¯>0 so that for all ki and αki<α¯,(3.15)f(xki+αkidki)-f(xki)≤ηαki∇fkiTdki.Proof.
From AssumptionsA1 and A2, dT∇2f(x)d≤cf∥d∥2 for some constant cf>0. Thus, it follows from the Taylor Theorem and (3.1) that(3.16)f(xki+αkidki)-f(xki)-αki∇fkiTdki=αki2dkiT∇2f(y1)dki≤cfαki2‖dki‖2≤αki(1-η)ϵ2≤-(1-η)αki∇fkiTdki,
if αki≤αki̅:=(1-η)ϵ2/cfMd2, where y1 denotes some point on the line segment from xki to xki+αkidki. Then the conclusion follows.Lemma 3.5.
Suppose AssumptionsA1–A3 hold, and the filter is augmented only a finite number of times, then(3.17)lim⁡k→∞‖dk‖=0.Proof.
Since the filter is augmented only a finite number of times, there exists an integerK1 so that for all iterates {xk}k>K1 the filter is not augmented. If the claim is not true, there must exist a subsequence {xki} and a constant ϵ>0 so that ∥dki∥≥ϵ for all i. Then by Lemma 3.1, it has ∇fkiTdki≤-ϵ2 for all ki≥K2, K2 is some integer and K2>K1. And from Lemmas 3.2 and 3.4, it has V(xki)≤ϵ and
(3.18)f(xki+1)-f(xki)≤ηαki∇fkiTdki≤-αkiηϵ2.
Since f(xki) is bounded below and monotonically decreasing for all k≥K2, one can conclude that limi→∞αki=0. This means that for ki>K2 the step size α=1 has not been accepted. So, we can get a αki<1 such that a trial point xki+1=xki+αkidki satisfies
(3.19)(V(xki+1),f(xki+1))∉Fki
or
(3.20)f(xki+1)-f(xki)>ηαki∇fkiTdki.
Let Vmin=min{Vk∣(Vk,fk)∈ℱk}. From Lagrange’s Theorem, it has
(3.21)V(xki+1)=V(xki)+αki∇V(y2)Tdki≤V(xki)+αki‖∇V(y2)‖‖dki‖≤V(xki)+cVαkiMd,
for some constant cV, where y2 denotes some point on the line segment from xki to xki+αdki. Since limi→∞αki=0 and limi→∞V(xki)=0 by Lemmas 3.2 and 3.3, it has V(xki+1)<Vmin for ki sufficiently large, so (3.19) is not true. In case (3.20), since αki→0 for sufficiently large ki, we have αki≤α¯ with α¯ from Lemma 3.4, that is, (3.20) can not be satisfied. Then the conclusion follows.Lemma 3.6.
Suppose AssumptionsA1–A3 hold. Let {xki} be a subsequence of {xk} with ∇fkiTdki≤-ϵ2 for a constant ϵ2>0 independent of ki. Then, there exists trial points can be accepted to the filter.Proof.
The mechanisms of Algorithm2.3 ensure that the first iterate can be accepted to the filter. Next, we can assume that (V(xk),f(xk)) is acceptable to the kth filter and (V(xl),f(xl))∈ℱk,l<k. If αki≤c2:=ϵ2/Md2cf, it has
(3.22)αki2≤αkiϵ2Md2cf≤-αki∇fkiTdkicf‖dki‖2,
that is, αki∇fkiTdki+cfαki2∥dki∥2≤0, so by (3.16)
(3.23)f(xki+αkidki)≤f(xki).
Similarly, if αki≤c3V(xki)≤V(xki)/∥d∥2cV, with c3:=1/Md2cV and cV from Lemma 3.5, it has
(3.24)-αkiV(xki)+cVαki2‖dki‖2≤0,V(xki+αkidki)≤V(xki).
Hence, we have
(3.25)f(xki+1)=f(xki+αkidki)≤f(xki)≤f(xl)-γV(xl),V(xki+1)=V(xki+αkidki)≤V(xki)≤βV(xl).
The claim then follows from (3.25).The last Lemma3.6 shows, for case V(xk)>0, Algorithm 2.3 either accepts a new iterate to the filter or switches to the feasibility restoration phase. For case V(xk)=0 and the algorithm does not stop at a KKT point, then ∇fkTdk<0, αkmin=0, and the Armijo condition (2.7) is satisfied for sufficiently small step size αk, so an f type iterate is accepted. Hence, the inner loop in Step 5 always terminates in a finite number of trial steps, and Algorithm 2.3 is well defined.Lemma 3.7.
Suppose AssumptionsA1–A3 hold. Let {xki} be a subsequence with ∥dki∥≥ϵ for a constant ϵ>0 independent of ki. Then, there exists an sufficient large integer K such that for all ki>K the algorithm can generate some trial points either be accepted to the filter or be f type steps.Proof.
By Lemmas3.1, 3.2, and 3.3, there exist constants ϵ1,ϵ2>0 so that
(3.26)V(xki)≤ϵ1,∇fkiTdki<-ϵ2
for all ki>K.
IfV(xki)=0, the f type switching condition (2.6) is true, there must exist iterates for which are f type iterates. For the remaining iterates with V(xki)>0, if(3.27)V(xki)<min⁡{α¯c3,c2c3,[τc3ϵ2e1δ]1/e2-1},
with α¯ from Lemma 3.4 and c2,c3 from Lemma 3.6, it implies with e2>1(3.28)δ[V(xki)]e2ϵ2e1<τc3V(xki),
as well as
(3.29)c3V(xki)<min⁡{α¯,c2}.
Now choose an arbitrary ki≥K with V(xki)>0 and define
(3.30)c4:=c3V(xki)=min⁡{α¯,c2,c3V(xki)}.
Lemmas 3.4 and 3.6 then imply that a trial step size αki≤c4 satisfies both
(3.31)f(xki+αkidki)≤f(xki)+ηαki∇fkiTdki,(V(xki+αkidki),f(xki+αkidki))∈Fki.
Sinceα>ταk>ταkmin by the definition of αkmin, the method does not switch to the feasibility restoration phase for those trial step sizes. Then the claim follows.Based on the above lemmas, we can give the main global convergence result.Theorem 3.8.
Suppose AssumptionsA1–A3 hold, then
(3.32)lim⁡k→∞V(xk)=0,(3.33)lim⁡k→∞‖dk‖=0,
that is, there exits a limit point x¯ of {xk} which is a first-order optimal point for (2.1).Proof.
(3.32) follows from Lemmas 3.2 and 3.3.
If the filter is augmented a finite number of times, then the claim (3.33) holds from Lemma 3.5. For either case, there exists a subsequence {xki} so that ki∈J for all i. Suppose the conclusion (3.33) is not true, there must exist a subsequence {xkj} of {xki} such that ∥dkj∥≥ϵ for some constant ϵ>0. Hence by Lemmas 3.1 and 3.3, it has ∇fkjTdkj<-ϵ2 and limi→∞V(xkj)=0 for all kj. Then by Lemma 3.7, when α<min{α¯,c2,c3V(xkj)}, the algorithm can generate a f type iterate, that is, the filter is not augmented, this contradicts the choice of {xkj}, so that (3.33) holds.


## 3.2. Local Convergence

In this section, we show the local convergence of Algorithm2.3.Assumption A4.
The iteratesxk converge to a point x¯ that satisfies(3.34)V(x¯)=0,∇xL(x¯,λ¯)=0,∇xxL(x¯,λ¯)ispositivedefiniteon⁡{d:∇c(x¯)Td=0},∇c(x¯)hasfull-rowrank⁡.Assumption A5.
There is a neighborhoodN(x¯) of x¯ such that Wk=∇xxL(xk,λk), for all xk∈N(x¯).Remark 3.9.
Under AssumptionA4, the point x¯ is a strict local minimum of (2.1).Remark 3.10.
Under AssumptionsA4 and A5, it is well known that with the choice xk+1=xk+dk, the sequence {xk} converges q-superlinearly to x¯ and that the convergence is q-quadratic if ∇xxf and ∇xxci are lipschitz continuous in a neighborhood of x¯. That is, for any given ζ∈[0,1], xj∈N(x¯), j=k,k+1,…, and xj+1=xj+dj, it has
(3.35)‖dj+1‖≤ζ‖dj‖,‖xj+1-x¯‖≤ζ‖xj-x¯‖.
We use the proof techniques of local convergence in [6]. In proof, define lρ(x,λ)=L(x,λ)+(ρ/2)∥c(x)∥22 and l̂ρ(x,λ)=f(x)+(ρ/2)V(x) with ρ is a parameter.Lemma 3.11.
Suppose AssumptionsA1–A3 hold. Let x¯ satisfy the Assumption A4. Then, there exist constants 0<r<t, ρ0>0 and a neighborhood Nσ(x¯)={x:∥x-x¯∥<σ}⊂N(x¯) such that
(3.36)r2‖x-x¯‖2+ρ-ρ02‖c(x)‖2≤lρ(x,λ)-lρ(x¯,λ¯)≤t(1+ρ)‖x-x¯‖2,
for all ρ≥ρ0 and all x∈Nσ(x¯).
Moreover, possibly after increasingt>0,ρ0>0 and reducing σ>0, we have that for all ρ≥ρ0 and all x∈Nσ(x¯)(3.37)r2‖x-x¯‖2+ρ-ρ02V(x)≤l̂ρ(x,λ)-l̂ρ(x¯,λ¯)≤t(1+ρ)‖x-x¯‖2.Proof.
Letx∈N(x¯). Using Taylor’s Theorem and ∇xlρ(x¯,λ¯)=0,∇λlρ(x¯,λ¯)=0, we have with some (x′,λ′) on the line segment between (x¯,λ¯) and (x,λ)(3.38)lρ(x,λ)-lρ(x¯,λ¯)=12(x-x¯)T∇xxlρ(x′,λ′)(x-x¯)+(x-x¯)T∇xλlρ(x′,λ′)(λ-λ¯).
Obviously, it has
(3.39)∇xxlρ(x′,λ′)=∇xxlρ/2(x′,λ′+ρ2c(x′))+ρ2∇c(x′)T∇c(x′).
Under Assumption A4, there exists ρ¯>0 such that for all ρ≥ρ¯,
(3.40)dT∇xxlρ/2(x¯,λ¯)d≥4r‖d‖2,∀d∈Rn,
with a constant r>0, see [15, Theorem  17.5].
Supposeλ(x) is Lipschitz continuous and Ly is the Lipschitz constant of λ, and ρ¯>0 is a constant. Let ρ0:=max{ρ¯,4Ly2/r} for all x with ∥x-x¯∥≤σ, it has by continuity(3.41)dT∇xxlρ0/2(x,λ+ρ02c(x))d≥2r‖d‖2,∀d∈Rn.
Thus, we obtain for all x∈Nσ(x¯) by (3.38), (3.39), and (3.41)
(3.42)lρ0(x,λ)-lρ0(x¯,λ¯)≥r‖x-x¯‖2+ρ04‖∇c(x′)(x-x¯)‖2+(λ-λ¯)T∇c(x′)(x-x¯).
It is obvious for all s>0 that
(3.43)2(λ-λ¯)T∇c(x′)(x-x¯)≥-1s‖∇c(x′)(x-x¯)‖2-s‖λ-λ¯‖2≥-1s‖∇c(x′)(x-x¯)‖2-sLy2‖λ-λ¯‖2.
If s=r/Ly2, 1/s=Ly2/r≤ρ0/4, then it has
(3.44)lρ0(x,λ)-lρ0(x¯,λ¯)≥r2‖x-x¯‖2+ρ08‖∇c(x′)(x-x¯)‖2.
Since c(x¯)=0, lρ(x¯,λ¯)=lρ0(x¯,λ¯)=f(x¯), and by (3.44) it has
(3.45)lρ(x,λ)-lρ(x¯,λ¯)=lρ0(x,λ)-lρ0(x¯,λ¯)+ρ-ρ02‖c(x)‖2≥r2‖x-x¯‖2+ρ-ρ02‖c(x)‖2,
that is the left inequality in (3.36). For the right inequality in (3.36), it is obvious from (3.38) that for all x∈N(x¯),
(3.46)lρ(x,λ)-lρ(x¯,λ¯)≤t(1+ρ)‖x-x¯‖2,
with a constant t>0. This proves the inequality (3.36).
ChooseK large enough such that for j≥k≥K, c(xj)→0. We can assume ∥c(x)∥<1. Then, if ρ0 is large enough, it has from (3.44) and l̂ρ(x¯,λ¯)=lρ0(x¯,λ¯)=f(x¯) that(3.47)l̂ρ0(x,λ)-l̂ρ0(x¯,λ¯)≥lρ0(x,λ)-lρ0(x¯,λ¯)≥r2‖x-x¯‖2.
By an analogue of (3.45) holds for l̂ρ, this proves the left inequality in (3.37).
On the other hand, it has(3.48)l̂ρ(x,λ)-l̂ρ(x¯,λ¯)=f(x)+ρ2V(x)-f(x¯).
Since f(x) and c(x) are twice continuously differentiable on closed set S, we have f(x)-f(x¯)=O(∥x-x¯∥2) and V(x)=O(∥x-x¯∥2). This shows the right inequality in (3.37) possibly after increasing t.Lemma 3.12.
Letx¯ satisfy Assumptions A4 and A5. Then for any ζ∈[0,1] and M≥1, there is an index K such that for all k≥K, with
(3.49)‖xk-x¯‖≤Mmin⁡(Vl,fl)∈Fk‖xl-x¯‖,
the points xj+1, j=k,k+1,…, with αk=1 are acceptable to
(3.50)Fj:=Fk∪(Vk,fk)∪(Vk+1,fk+1)∪⋯∪(Vj,fj).Proof.
LetN(x¯) as in Assumption A5,ζ=1/2,ρ0 and Nσ(x¯)⊂N(x¯) be given by Lemma 3.11. For all k≥K1, K1 is a sufficient large integer, and choose ρ≥ρ0 so large that
(3.51)β(ρ2-γ)≥βρ4,ρ-ρ02≥(1-β4)ρ2.
Then, it has from (3.37) in Lemma 3.11(3.52)r2‖x-x¯‖2+(1-β4)ρ2V(x)=l̂ρ(x,λ)-l̂ρ(x¯,λ¯)≤t(1+ρ)‖x-x¯‖2.
Let
(3.53)V′:=min⁡(Vj,fj)∈FK1⁡Vj.
By V′>0 and continuity there exists 0<σ1<σ such that V(x)≤βV′ for all x∈Nσ1(x¯), so the point x is acceptable to ℱK1. Since xk→x¯, xk∈Nσ1(x¯) for all k≥K2>K1, K2 is an integer. By (3.35), we can choose σ1 so small that for all k≥K2, the sequence {xj}j≥k with αk=1 converges linearly with a contraction factor of at least
(3.54)‖xj+1-x¯‖≤12(1-1-β/21-β/4)r2M2t(1+ρ)‖xj-x¯‖≤12‖xj-x¯‖.
Suppose an arbitrary k2≥K2 such that (3.49) holds, and set σ2:=∥xk-x¯∥. By (3.54), it has xk+1∈Nσ2(x¯) and xk+1 is acceptable to ℱK1. Next, it is a need to show that xk is acceptable with respect to (Vl,fl)∈ℱk∪(Vk,fk) for K1≤l≤k. By (3.49), it has xl∈Nσ(x¯)∖Nσ2/M(x¯), so by (3.52)
(3.55)l̂ρ(xl,λl)-l̂ρ(x¯,λ¯)≥r2M2σ22+(1-β4)ρ2Vl.
And, by (3.52) and (3.54)
(3.56)l̂ρ(xk+1,λk+1)-l̂ρ(x¯,λ¯)≤t(1+ρ)‖xk+1-x¯‖2≤12(1-1-β/21-β/4)r2M2σ22.
Next, suppose (x,λ) with x∈Nσ2(x¯) is not acceptable to (Vl,fl) then
(3.57)V(x)>βVl,f(x)+γV(x)>fl.
Thus, it has with (3.51) and (3.52)
(3.58)l̂ρ(x,λ)=f(x)+ρ2V(x)>fl+(ρ2-γ)V(x)>fl+β(ρ2-γ)Vl≥fl+β(ρ4)Vl=l̂ρ(xl,λl)-(1-β2)ρ2Vl≥l̂ρ(xl,λl)-1-β/21-β/4(l̂ρ(xl,λl)-l̂ρ(x¯,λ¯)).
This shows with (3.55) that
(3.59)l̂ρ(x,λ)-l̂ρ(x¯,λ¯)>(1-1-β/21-β/4)(l̂ρ(xl,λl)-l̂ρ(x¯,λ¯))≥(1-1-β/21-β/4)r2M2σ22.
This produces a contradiction to (3.56), so xk+1 is acceptable to ℱk∪(Vk,fk). Then, the acceptability of (Vj+1,fj+1) for ℱl follows by induction.Next, we show that the sequence{xj}j≥k with αk=1 can make the sufficient decreasing condition (2.7) hold.Lemma 3.13.
Suppose AssumptionsA1–A3 hold. Let x¯ satisfy Assumptions A4 and A5 and let K be as in Lemma 3.11. Then for all k>K the sequence {xj}j≥K with αj=1 satisfies
(3.60)f(xj+1)≤f(xj)+ηαj∇fjTdj.Proof.
Supposeαj∇fjTdj<0 and αj[∇fjTdj]e1<-δ[V(xj)]e2 hold. By αj=1, thus
(3.61)∇fjTdj<-(δ)1/e1[V(xj)]e2/e1.
On the other hand, withαj=1 the assertion f(xj+1)≤f(xj)+η∇fjTdj yields(3.62)η∇fjTdj≥∇fjTdj+12djT∇xx2f(x′)dj.
Thus,
(3.63)∇fjTdj≤-12(1-η)djT∇xx2f(x′)dj,
where x′ on the line segment between xj and xj+1.
Obviously, we can prove the conclusion if withK>0 large enough and for all j≥k≥K the following holds(3.64)-(δ)1/e1[V(xj)]e2/e1≤-12(1-η)djT∇xx2f(x′)dj.
Sincecj+∇cjTdj=0, dj=-∇cjT(∇cj∇cjT)-1cj. By Assumption A4, ∇cj has full-row rank, there exists cd>0 such that(3.65)‖dj‖≤cdV(xj),
thus,
(3.66)‖dj‖2≤cd2[V(xj)]2.
ChooseK large enough such that V(xj)≤1 for all j≥k≥K. By e1>2e2 and (3.66) it has(3.67)‖dj‖2≤cd2c5[V(xj)]e2/e1,
for a constant c5:=2δ1/e1(1-η)/cfcd2, we can choose suitable parameters such that the last inequality holds. Thus,
(3.68)δ1/e1[V(xj)]e2/e1≥12(1-η)cf‖dj‖2≥12(1-η)djT∇xx2f(x′)dj.
This completes the proof.Theorem 3.14.
Suppose AssumptionsA1–A5 hold. Then, there exists K>0 such that Algorithm 2.3 takes steps with αk=1 for all k≥K, that is,
(3.69)xk+1=xk+dk.
In particular, xk converges q-superlinearly to x¯. If ∇xxf and ∇xxci are Lipschitz continuous in a neighborhood of x¯ then xk converges q-quadratically.Proof.
Since AssumptionsA4 and A5 hold, xk→x¯ with x¯ satisfying A4. By Lemmas 3.12 and 3.13, the iterate (xk+1,λk+1)=(xk+dk,λ(xk+dk)) is acceptable to the filter ℱk∪(Vk,fk) and satisfies the sufficient decreasing condition (2.7). Thus, the trial iterate (xk+dk,λ(xk+dk)) is accepted by the algorithm and it has
(3.70)xk+1=xk+dk,λk+1=λ(xk+dk).
That is in both cases the algorithm takes the steps with αk=1. And according to Remark 3.10, {xk} converges q-superlinearly to x¯.


## 4. Numerical Experience

In this section, we give some numerical results of Algorithm2.3. We take some CUTE problems [17], which are available freely on NEOS, to test our algorithm. The test codes are edited in MATLAB. The details about the implementation are described as follows.(a)
The parameters are set toβ=0.99, γ=0.0001, η=0.4, δ=1, τ=0.6, e1=2.3, e2=1.1, the termination tolerance ϵ=1E-6.(b)
The optimal residual is defined as(4.1)res=max⁡{‖∇f(xk)+∇c(xk)λ‖,V(xk)}.
That is, the algorithm terminates when res<ϵ.(c)
Wk is updated by damped BFGS formula [15].The detailed results of the numerical test on small-scale problems are summarized in Table2. For comparison purposes, we also give the numerical results of tridimensional line-search filter solver (Tri-filter) in Shen et al. [12] in Table 2. The row headers in Tables 2 and 3 are presented in Table 1.Table 1
Description on headers.
HeaderDescriptionProblemThe name of the CUTE problem being solvednNumber of variables of the problemmThe total number of constraintsmnlNumber of nonlinear constraintsNIT1Number of iterations of Algorithm2.3NIT2Number of iterations of algorithm Tri-filterNIT3Number of iterations of algorithm SNOPTNF1Number off evaluations of Algorithm 2.3NF2Number off evaluations of algorithm Tri-filterNF3Number off evaluations of algorithm SNOPTTable 2
Numerical results of small-scale problems.
ProblemnmmnlNIT1/NIT2NF1/NF2hs01725311/1414/20hs0192642/55/6hs0242421/42/5hs0373765/76/10hs0423546/78/10hs04343011/1412/16hs04654219/3041/102hs0475639/1928/70hs04954217/2327/26hs056715118/1816/41hs05927413/1625/20hs06337513/1530/44hs07141196/2812/103hs0764745/66/7hs07754215/2625/36hs0785638/618/29hs0795636/910/11hs09261125/1835/52hs098616126/66/7hs09919422815/1925/78hs1048221616/2333/60hs1068222132/3612/37hs1089141015/1213/13hs11110262342/4850/52hs11210161625/5225/30hs11310819/1315/19hs11410342325/2823/29hs11613413537/4430/54hs11715201515/1615/23hs11815595912/1822/19hs11916484013/1816/19Table 3
Numerical results of mid-scale problems.
ProblemnmmnlNIT1/NIT3NF1/NF3Ngone971371136916/7221/20Grouping1004503501/04/2Eigen a2110110558/115/6Eigen a11011011052/226158/208The results in Table2 indicate that Algorithm 2.3 has a good effect.In addition, we also test some mid-scale problems. And we compare the numerical results which are summarized in Table3 in Algorithm 2.3 and SNOPT solver in Gill et al. [18] since no mid-scale problems are given in trifilter solver.From Table3, we find the efficiency of Algorithm 2.3 is also improved significantly. From both Tables 2 and 3, in general, the behavior of the proposed algorithm is rather stable. Finally, we may conclude that, as far as our limited computational experience is concerned, the proposed algorithm is well comparable to trifilter solver and SNOPT solver.



---

*Source: 349178-2012-02-23.xml*