# A Class of Inexact Secant Algorithms with Line Search Filter Method for Nonlinear Programming

Authors: Zhujun Wang; Li Cai
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

We propose a class of inexact secant methods in association with the line search filter technique for solving nonlinear equality constrained optimization. Compared with other filter methods that combine the line search method applied in most large-scale optimization problems, the inexact line search filter algorithm is more flexible and realizable. In this paper, we focus on the analysis of the local superlinear convergence rate of the algorithms, while their global convergence properties can be obtained by making an analogy with our previous work. These methods have been implemented in a Matlab code, and detailed numerical results indicate that the proposed algorithms are efficient for 43 problems from the CUTEr test set.


---

## Body

## 1. Introduction

This paper considers the following nonlinear equality constrained optimization problem:(1)minx∈ℝnfx,s.t.cx=0,where f:ℝn⟶ℝ and c:ℝn⟶ℝm are twice continuously differentiable.After more than 20 years of development, filter algorithm has become an important method to solve constrained optimization problems and has been successfully applied to various fields of optimization (see [1–5]). In [6, 7], a line search filter Newton method is presented for (1). Local and global convergence properties of this method are analyzed. In particular, motivated by a multiobjective restructuring of constrained optimization problems, Eichfelder et al. [3] proposed a new filter approach, which utilizes the restructuring to identify the trade-off between constraint satisfaction and objective value. It is foreseeable that the filter method will find application in more diverse fields.It is well known that the secant methods (two-step algorithms) are one of the most successful methods for solving problem (1) and have a main advantage which rests in the use of an orthogonal projection operator which is continuous. Fontecilla [8] showed that the six secant algorithms generate a sequence converging 2-step superlinearly under some suitable conditions.When solving large-scale nonlinear programming problems or system of nonlinear equations, it would take too much time to get an exact solution in each iteration. An inexact Newton method was proposed in [9] to solve large-scale system of nonlinear equations. Subsequently, an inexact SQP algorithm was presented in [2] to solve large-scale equality constrained optimization problems. Under suitable assumptions, the global convergence of inexact SQP steps was proved. These research results show that the use of inexact algorithm can save a lot of computing time.Inspired by these ideas above, we propose a class of inexact secant methods in association with the line search filter technique, which has both global convergence andq-superlinear local convergence rate. These methods are globalized by line search and filter methods. In this work, we use Lagrangian function ℒ as the objective function and cx2 as the constraint violation. The filter method can suffer from the Maratos effect. The reason that Maratos effect appears is that the merit function used to judge whether the iteration point is good or bad is nonsmooth. If the merit function is smooth, Maratos effect can be avoided. Hence, we do not need to compute the second-order correction step which was used to overcome the Maratos effect.The structure of this article is arranged as follows. Section2 develops the algorithms. In Section 3, we mainly analyze the local superlinear convergence rate. The results of numerical experiences with the three algorithms are discussed in Section 4. Final conclusions are provided in Section 5.


## 2. Algorithms

In this paper, we denote the Euclidean vector or matrix norm by⋅, Ax:=∇cx, and gx:=∇x. The inexact secant algorithms are given by the following iterative scheme:(2a)λk+1=Uxk,λk,Wk,(2b)Wku^k=−∇xℒxk,λk+1+rk,(2c)uk=Pku^k,(2d)vk=−Ak†ck,(2e)dk=uk+vk,(2f)yk=∇xℒxk+uk,λk+1−∇xℒxk,λk+1,(2g)Wk+1=Buk,yk,Wk,(2h)xk+1=xk+dk,where rk≤ηkck with ηk∈0,t and t∈0,1, ℒx,λ=fx+λTcx for λ∈ℝm, and B is the BFGS or the DFP secant update formula generating matrices Wk approximating the Hessian of the Lagrangian at each xk. There are many different multiplier updates; however, λk+1 in (2a) is chosen from the most commonly used multiplier updates: projection update, null-space update, and Newton update. Px in (2c) can be either the orthogonal projection or the oblique projection depending on the choice of the multiplier update λk+1. Ak† in (2d) is the pseudo-inverse of AkT. With different choices for λk+1 in (2a), Px in (2c), and Ak† in (2d), we get the following three algorithms:(i)
ALG 1:λk+1=−AkTWk−1Ak−1AkTWk−1gk (null-space update)Px=I (I is the identity matrix)Ak†=Wk−1AkAkTWk−1Ak−1(ii)
ALG 2:λk+1=−AkTAk−1AkTgk (projection update)Px=I−W−1AxAxTW−1Ax−1AxT (oblique projection)Ak†=AkAkTAk−1(iii)
ALG 3:λk+1=AkTWk−1Ak−1ck−AkTWk−1gk (Newton update)Px=I−AxAxTAx−1AxT (orthogonal projection)Ak†=Wk−1AkAkTWk−1Ak−1To get the next iterate, the line search filter method described in Section 4.1 of the literature [6] is used to determine a step size αk∈0,1. The Lagrangian function ℒx,λ measures optimality and the constraint violation hx measures feasibility, where hx=1/2cx2. The class of complete algorithms can be stated as follows.Algorithm 1: ISLSF.
(1)
Initialize: choose starting pointx0, λ0, and W0=I. Set constants β∈0,1/2, γh,γℒ∈0,1, t∈0,1−γh/1+γh, τ1,ν>0, sh>1, sℒ>2sh, γα∈0,1, ς∈0,1, and ε>0. Choose an initial filter ℱ0:=h,ℒ∈ℝ2:h≥ν and let k:=0.(2)
If∇xℒxk,λkck<ε, then stop.(3)
Evaluatefk, gk, ck, and Ak. Then, compute the multiplier λk+1=Uxk,λk,Wk from (2a). Find an inexact step dk from (2b)–(2e). Compute dkλ=λk+1−λk. If this system ((2a)–(2h)) is too ill-conditioned, go to Step 9.(4)
Setαk,0=1 and l=0.(5)
Ifαk,l<αkmin withαkmin:=γα⋅minγh,γℒhk/−gkTdk+λkTck−dkλTck,τ1hksh/−gkTdk+λkTck−dkλTcksℒifgkTdk−λkTck+dkλTck<0γh,otherwisego to Step 9. Otherwise, ifhxk+αk,ldk,ℒxk+αk,ldk,λk+αk,ldkλ∈ℱk, thengo to Step 7.(6)
Definemkα:=αgkTdk−αλkTck+α1−αckTdkλ. Ifmkαk,l<0,−mkαk,lsℒαk,l1−sℒ>τ1hxkshandℒxk+αk,ldk,λk+αk,ldkλ≤ℒxk,λk+βmkαk,lhold, setxk+1:=xk+αk,ldk and go to Step 8. If the first equation in Step 6 in Algorithm 1 does not hold, then ifhxk+αk,ldk≤1−γhhxkorℒxk+αk,ldk,λk+1≤ℒxk,λk−γℒhxkholds, setxk+1:=xk+αk,ldk and go to Step 8.(7)
Setαk,l+1=ςαk,l and l←l+1. Go to Step 5.(8)
Setαk:=αk,l. If the first equation in Step 6 in Algorithm 1 does not hold for αk, augment the filter byℱk+1=ℱk∪h,ℒ∈ℝ2:h≥1−γhhxkandℒ≥ℒxk,λk−γℒhxkotherwise, setℱk+1:=ℱk. Go to Step 10.(9)
Find a new pointxk+1 that satisfies the following conditions:(a)
hxkis greater thanhxk+1(b)
The third and fourth equations in Step 6 in Algorithm1 hold for xk+1(c)
hxk+1,ℒxk+1,λk+1∉ℱkAugment the filter by the equation in Step 8 in Algorithm1. Go to Step 10.(10)
Computeyk=Pk∇xℒxk+uk,λk−∇xℒxk,λk and update Wk by (2g). Set k:=k+1 and go to Step 2.


## 3. Convergence Analysis

The global convergence analysis of the algorithms in Section 3 of [10] still holds. The only point that needs special attention is the proof of Lemma 3.2 in [10]. This lemma proves that the search direction is a sufficient descent direction for ℒat the points that are sufficiently close to feasible and nonoptimal. The analysis of Lemma 3.2 in [10] then holds The analysis in Lemma 2 then holds with replacing “Steps 1 and 4” in Algorithm 1 by “ALG 1,” “Steps 2 and 5” in Algorithm 1 by “ALG 2,” and “Steps 3 and 6” in Algorithm 1 by “ALG 3” where appropriate.Next, we analyze the local convergence rate of the proposed algorithms. Assume thatxk and λk generated by the class of algorithms converge to local solution x∗ and λ∗, respectively. In addition, they are contained in a convex set Ω Furthermore, we give the following assumptions.


### 3.1. Assumptions L

L1. The functions f and c are twice continuously differentiable in a neighborhood Ω of x∗.L2. x∗ and λ∗ satisfy ∇xℒx∗,λ∗=0.L3. Ax∗ is full column rank.L4. There exists a constant κ>0 such that uTWku≥κu2 for AkTu=0 and W∗ is positive definite on the null space of Ax∗T. The sequence Wk is uniformly bounded.L5. Wk satisfies that(3)limk⟶∞Wk−∇xx2ℒxk,λk+1dkdk=0.For the sake of local convergence analysis, we define a penalty function(4)ϕωx,λ≔fx+λTcx+ωhx.The local linearized approximation of the penalty function is(5)qωxk,d,λk,dλ=fk+gkTd+λk+dλTck+AkTd+12uTWku+ω2ck+AkTd2.Lemma 1.
If Assumptions L hold andηk=Odk, then there exists a constant γ˜ω>0 such that when ω≥γ˜ω,(6)qωxk,0,λk,0−qωxk,dk,λk,dkλ≥0.Proof.
From (2d) and the assumption of global convergence, we can obtain that vk=Ock. (5) implies that(7)qωxk,0,λk,0−qωxk,dk,λk,dkλ=ω2ck2+λkTck−gkTdk−12ukTWkuk.
For ALG 1, we have that(8)ukTWkuk=ukT−gk+AkAkTWk−1Ak−1AkTWk−1gk+rk=−ukTgk+rkTWk−1AkAkTWk−1Ak−1AkTWk−1gk+ukTrk,and(9)gkTuk=−ukTWkuk+gkTWk−1AkAkTWk−1Ak−1AkTWk−1rk+rkTuk.
Sinceηk=Odk, we have rk=Oukck+Ock2. Hence, from (2a)–(2h), (7), (9), and L4, we can get that(10)qωxk,0,λk,0−qωxk,dk,λk,dkλ=ω2ck2+12ukTWkuk+Oukck+Ock2≥ω2−κ3ck2−κ4ukck+12κuk2,where κ3,κ4>0. It follows with θk:=uk/ck that(11)1ck2qωxk,0,λk,0−qωxk,dk,λk,dkλ≥ω2−κ3−κ4θk+12κθk2=12κθk−κ4κ2+ω2−κ3−κ422κ.
Letγ˜ω:=2κ3+κ42/κ. Then, (6) holds for ω≥γ˜ω.
For ALG 2, we obtain that(12)uk=Pku^k=−Wk−1gk+Wk−1AkAkTWk−1Ak−1AkTWk−1gk+PkWk−1rk,ukTWkuk=ukT−∇xℒ+rk−ukTAkAkTWk−1Ak−1AkTWk−1−∇xℒ+rk−ukTgk+ukTrk+ukTAkAkTWk−1Ak−1AkTWk−1gk−ukTAkAkTWk−1Ak−1AkTWk−1rk.
Hence,(13)gkTuk=−ukTWkuk+rkTuk−rkTWk−1AkAkTWk−1Ak−1AkTuk.
Using (7), (13), and L4, we have that(14)qωxk,0,λk,0−qωxk,dk,λk,dkλ=ω2ck2+12ukTWkuk+λkTck−rkTuk+rkTWk−1AkAkTWk−1Ak−1AkTuk−gkTvk=ω2ck2+12ukTWkuk+Oukck+Ock2≥ω2−κ^3ck2−κ^4ukck+12κuk2,where κ^3,κ^4>0. Define θk:=uk/ck, and (14) then implies that(15)1ck2qωxk,0,λk,0−qωxk,dk,λk,dkλ≥12κθk−κ^4κ2+ω2−κ^3−κ^422κ.
Letγ˜ω:=2κ^3+κ^42/κ. Then, (6) holds for ω≥γ˜ω.
For ALG 3, (2a)–(2h) imply that(16)uk=I−AkAkTAk−1AkTu^k=−Wk−1gk+Wk−1AkAkTWk−1Ak−1AkTWk−1gk−Wk−1AkAkTWk−1Ak−1ck+AkAkTAk−1ck+PkWk−1rk=u^k−Wk−1rk−vk+PkWk−1rk,ukTWkuk=ukTWku^k−ukTrk−ukTWkvk+ukTWkPkWk−1rk=−ukTgk−ukTWkvk+ukTWkPkWk−1rk,and(17)gkTuk=−ukTWkuk−ukTWkvk+ukTWkPkWk−1rk.
From (7), (17), and L4, we deduce that(18)qωxk,0,λk,0−qωxk,dk,λk,dkλ=ω2ck2+λkTck+12ukTWkuk+ukTWkvk−ukTWkPkWk−1rk−gkTvk=ω2ck2+12ukTWkuk+Oukck+Ock2.
Similarly, we can also prove that there existsγ˜ω such that (6) holds for ω≥γ˜ω.Lemma 2.
Suppose Assumptions L hold andηk=Odk. There exists a neighborhood ℬ1 of x∗ such that if the first equation in Step 6 in Algorithm 1 holds for αk,l=1, then the trial step is accepted by the Armijo condition (the second equation in Step 6 in Algorithm 1) for xk∈ℬ1.Proof.
If the first equation in Step 6 in Algorithm1 holds, sℒ>2sh implies that(19)12ck2=hxk<τ1−1/sh−mk1sℒ/sh<τ1−1/sh−gkTdk+λkTcksℒ/sh=τ1−1/sh−gkTuk+Ovk2sℒ/sh=ouk2.
By (9), (13), (17), and rk,vk=Ock, we can easily get(20)gkTdk=−ukTWkuk+Oukck+Ork=−ukTWkuk+ouk2.
Hence, by Assumption L5, (19), and (20), we see that(21)ℒxk,λk−ℒxk+dk,λk+dkλ+βgkTdk−λkTck=λkTck−gkTdk−12dkT∇2fxkdk−λk+dkλTcxk+dk+βgkTdk−λkTck+odk2=β−1gkTdk+1−βλkTck−12dkT∇2fxkdk−12dkT∑i=1mλk,i∇2cixkdk+odk2=1−βukTWkuk−12ukTWkuk+2ukTWkvk+vkTWkvk+ouk+odk2=12−βukTWkuk+Ock+ouk2=12−βukTWkuk+ouk2.
From Assumption L4,β∈0,1/2, and we can conclude that the Armijo condition (the second equation in Step 6 in Algorithm 1) holds for k sufficiently large.Next, we present a result which is necessary for the local convergence.Lemma 3.
Suppose Assumptions L hold. Chooseηk=Odk. There exist a neighborhood ℬ2⊆ℬ1 and a constant γω>0 such that for ω≥γω and xk∈ℬ2,(22)ϕωxk,λk−ϕωxk+dk,λk+dkλ≥1+γh2qωxk,0,λk,0−qωxk,dk,λk,dkλ.Proof.
From (20) and vk=Ock, we have that(23)ϕωxk,λk−ϕωxk+dk,λk+dkλ=fk+λkTck+ω2ck2−fxk+dk−λk+dkλTcxk+dk−ω2cxk+dk2=λkTck+ω2ck2−gkTdk−12dkT∇2fxkdk−λkTcxk+dk+odk2=ω2ck2−gkTdk+λkTck−12dkT∇2fxkdk−12dkT∑i=1mλk,i∇2cixkdk+odk2=ω2ck2+ukTWkuk−12dkTWkdk+Oukck+Ock2+odk2=ω2ck2+ukTWkuk−12ukTWkuk+2ukTWkvk+vkTWkvk+Oukck+Ock2+odk2=ω2ck2+12ukTWkuk+Oukck+Ock2+ouk2.
Hence, from Assumption L2, (10), (14), (18), (23), and γh∈0,1, we obtain that(24)ϕωxk,λk−ϕωxk+dk,λk+dkλ−1+γh2qωxk,0,λk,0−qωxk,dk,λk,dkλ=ω2ck2+12ukTWkuk+Oukck+Ock2+ouk2−1+γh2ω2ck2+12ukTWkuk+Oukck+Ock2=1−γh4ωck2+1−γh4ukTWkuk+Oukck+Ock2+ouk2≥1−γh4κuk2−κ5ukck+1−γh4ω−κ6ck2,where κ5,κ6>0. Set θk:=uk/ck. Therefore, we can get(25)1ck2ϕωxk,λk−ϕωxk+dk,λk+dkλ−1+γh2qωxk,0,λk,0−qωxk,dk,λk,dkλ≥1−γh4κθk2−κ5θk+1−γh4ω−κ6=1−γh4κθk−2κ51−γhκ2+1−γh4ω−κ6−κ521−γhκ.
Defineγω:=4κ6/1−γh+4κ52/1−γh2κ. We conclude that (22) holds for ω≥γω.From [7], we can easily prove that Lemma 3 is true for the next three choices of steps.(26a)d¯k=dk+dk+1,d¯kλ=dkλ+dk+1λ,(26b)d¯k=dk+dk+1+dk+2,d¯kλ=dkλ+dk+1λ+dk+2λ,(26c)ord¯k=dk+dk+1+dk+2+dk+3,d¯kλ=dkλ+dk+1λ+dk+2λ+dk+3λ.Using arguments similar to those in the proof of Lemma 4.5, Lemma 4.6, and Theorem 4.7 in [7], we are able to show the main local convergence theorem.Theorem 1.
Suppose Assumptions L hold. Fork sufficiently large, the sequence xk converges to x∗ with a superlinear rate.


## 3.1. Assumptions L

L1. The functions f and c are twice continuously differentiable in a neighborhood Ω of x∗.L2. x∗ and λ∗ satisfy ∇xℒx∗,λ∗=0.L3. Ax∗ is full column rank.L4. There exists a constant κ>0 such that uTWku≥κu2 for AkTu=0 and W∗ is positive definite on the null space of Ax∗T. The sequence Wk is uniformly bounded.L5. Wk satisfies that(3)limk⟶∞Wk−∇xx2ℒxk,λk+1dkdk=0.For the sake of local convergence analysis, we define a penalty function(4)ϕωx,λ≔fx+λTcx+ωhx.The local linearized approximation of the penalty function is(5)qωxk,d,λk,dλ=fk+gkTd+λk+dλTck+AkTd+12uTWku+ω2ck+AkTd2.Lemma 1.
If Assumptions L hold andηk=Odk, then there exists a constant γ˜ω>0 such that when ω≥γ˜ω,(6)qωxk,0,λk,0−qωxk,dk,λk,dkλ≥0.Proof.
From (2d) and the assumption of global convergence, we can obtain that vk=Ock. (5) implies that(7)qωxk,0,λk,0−qωxk,dk,λk,dkλ=ω2ck2+λkTck−gkTdk−12ukTWkuk.
For ALG 1, we have that(8)ukTWkuk=ukT−gk+AkAkTWk−1Ak−1AkTWk−1gk+rk=−ukTgk+rkTWk−1AkAkTWk−1Ak−1AkTWk−1gk+ukTrk,and(9)gkTuk=−ukTWkuk+gkTWk−1AkAkTWk−1Ak−1AkTWk−1rk+rkTuk.
Sinceηk=Odk, we have rk=Oukck+Ock2. Hence, from (2a)–(2h), (7), (9), and L4, we can get that(10)qωxk,0,λk,0−qωxk,dk,λk,dkλ=ω2ck2+12ukTWkuk+Oukck+Ock2≥ω2−κ3ck2−κ4ukck+12κuk2,where κ3,κ4>0. It follows with θk:=uk/ck that(11)1ck2qωxk,0,λk,0−qωxk,dk,λk,dkλ≥ω2−κ3−κ4θk+12κθk2=12κθk−κ4κ2+ω2−κ3−κ422κ.
Letγ˜ω:=2κ3+κ42/κ. Then, (6) holds for ω≥γ˜ω.
For ALG 2, we obtain that(12)uk=Pku^k=−Wk−1gk+Wk−1AkAkTWk−1Ak−1AkTWk−1gk+PkWk−1rk,ukTWkuk=ukT−∇xℒ+rk−ukTAkAkTWk−1Ak−1AkTWk−1−∇xℒ+rk−ukTgk+ukTrk+ukTAkAkTWk−1Ak−1AkTWk−1gk−ukTAkAkTWk−1Ak−1AkTWk−1rk.
Hence,(13)gkTuk=−ukTWkuk+rkTuk−rkTWk−1AkAkTWk−1Ak−1AkTuk.
Using (7), (13), and L4, we have that(14)qωxk,0,λk,0−qωxk,dk,λk,dkλ=ω2ck2+12ukTWkuk+λkTck−rkTuk+rkTWk−1AkAkTWk−1Ak−1AkTuk−gkTvk=ω2ck2+12ukTWkuk+Oukck+Ock2≥ω2−κ^3ck2−κ^4ukck+12κuk2,where κ^3,κ^4>0. Define θk:=uk/ck, and (14) then implies that(15)1ck2qωxk,0,λk,0−qωxk,dk,λk,dkλ≥12κθk−κ^4κ2+ω2−κ^3−κ^422κ.
Letγ˜ω:=2κ^3+κ^42/κ. Then, (6) holds for ω≥γ˜ω.
For ALG 3, (2a)–(2h) imply that(16)uk=I−AkAkTAk−1AkTu^k=−Wk−1gk+Wk−1AkAkTWk−1Ak−1AkTWk−1gk−Wk−1AkAkTWk−1Ak−1ck+AkAkTAk−1ck+PkWk−1rk=u^k−Wk−1rk−vk+PkWk−1rk,ukTWkuk=ukTWku^k−ukTrk−ukTWkvk+ukTWkPkWk−1rk=−ukTgk−ukTWkvk+ukTWkPkWk−1rk,and(17)gkTuk=−ukTWkuk−ukTWkvk+ukTWkPkWk−1rk.
From (7), (17), and L4, we deduce that(18)qωxk,0,λk,0−qωxk,dk,λk,dkλ=ω2ck2+λkTck+12ukTWkuk+ukTWkvk−ukTWkPkWk−1rk−gkTvk=ω2ck2+12ukTWkuk+Oukck+Ock2.
Similarly, we can also prove that there existsγ˜ω such that (6) holds for ω≥γ˜ω.Lemma 2.
Suppose Assumptions L hold andηk=Odk. There exists a neighborhood ℬ1 of x∗ such that if the first equation in Step 6 in Algorithm 1 holds for αk,l=1, then the trial step is accepted by the Armijo condition (the second equation in Step 6 in Algorithm 1) for xk∈ℬ1.Proof.
If the first equation in Step 6 in Algorithm1 holds, sℒ>2sh implies that(19)12ck2=hxk<τ1−1/sh−mk1sℒ/sh<τ1−1/sh−gkTdk+λkTcksℒ/sh=τ1−1/sh−gkTuk+Ovk2sℒ/sh=ouk2.
By (9), (13), (17), and rk,vk=Ock, we can easily get(20)gkTdk=−ukTWkuk+Oukck+Ork=−ukTWkuk+ouk2.
Hence, by Assumption L5, (19), and (20), we see that(21)ℒxk,λk−ℒxk+dk,λk+dkλ+βgkTdk−λkTck=λkTck−gkTdk−12dkT∇2fxkdk−λk+dkλTcxk+dk+βgkTdk−λkTck+odk2=β−1gkTdk+1−βλkTck−12dkT∇2fxkdk−12dkT∑i=1mλk,i∇2cixkdk+odk2=1−βukTWkuk−12ukTWkuk+2ukTWkvk+vkTWkvk+ouk+odk2=12−βukTWkuk+Ock+ouk2=12−βukTWkuk+ouk2.
From Assumption L4,β∈0,1/2, and we can conclude that the Armijo condition (the second equation in Step 6 in Algorithm 1) holds for k sufficiently large.Next, we present a result which is necessary for the local convergence.Lemma 3.
Suppose Assumptions L hold. Chooseηk=Odk. There exist a neighborhood ℬ2⊆ℬ1 and a constant γω>0 such that for ω≥γω and xk∈ℬ2,(22)ϕωxk,λk−ϕωxk+dk,λk+dkλ≥1+γh2qωxk,0,λk,0−qωxk,dk,λk,dkλ.Proof.
From (20) and vk=Ock, we have that(23)ϕωxk,λk−ϕωxk+dk,λk+dkλ=fk+λkTck+ω2ck2−fxk+dk−λk+dkλTcxk+dk−ω2cxk+dk2=λkTck+ω2ck2−gkTdk−12dkT∇2fxkdk−λkTcxk+dk+odk2=ω2ck2−gkTdk+λkTck−12dkT∇2fxkdk−12dkT∑i=1mλk,i∇2cixkdk+odk2=ω2ck2+ukTWkuk−12dkTWkdk+Oukck+Ock2+odk2=ω2ck2+ukTWkuk−12ukTWkuk+2ukTWkvk+vkTWkvk+Oukck+Ock2+odk2=ω2ck2+12ukTWkuk+Oukck+Ock2+ouk2.
Hence, from Assumption L2, (10), (14), (18), (23), and γh∈0,1, we obtain that(24)ϕωxk,λk−ϕωxk+dk,λk+dkλ−1+γh2qωxk,0,λk,0−qωxk,dk,λk,dkλ=ω2ck2+12ukTWkuk+Oukck+Ock2+ouk2−1+γh2ω2ck2+12ukTWkuk+Oukck+Ock2=1−γh4ωck2+1−γh4ukTWkuk+Oukck+Ock2+ouk2≥1−γh4κuk2−κ5ukck+1−γh4ω−κ6ck2,where κ5,κ6>0. Set θk:=uk/ck. Therefore, we can get(25)1ck2ϕωxk,λk−ϕωxk+dk,λk+dkλ−1+γh2qωxk,0,λk,0−qωxk,dk,λk,dkλ≥1−γh4κθk2−κ5θk+1−γh4ω−κ6=1−γh4κθk−2κ51−γhκ2+1−γh4ω−κ6−κ521−γhκ.
Defineγω:=4κ6/1−γh+4κ52/1−γh2κ. We conclude that (22) holds for ω≥γω.From [7], we can easily prove that Lemma 3 is true for the next three choices of steps.(26a)d¯k=dk+dk+1,d¯kλ=dkλ+dk+1λ,(26b)d¯k=dk+dk+1+dk+2,d¯kλ=dkλ+dk+1λ+dk+2λ,(26c)ord¯k=dk+dk+1+dk+2+dk+3,d¯kλ=dkλ+dk+1λ+dk+2λ+dk+3λ.Using arguments similar to those in the proof of Lemma 4.5, Lemma 4.6, and Theorem 4.7 in [7], we are able to show the main local convergence theorem.Theorem 1.
Suppose Assumptions L hold. Fork sufficiently large, the sequence xk converges to x∗ with a superlinear rate.


## 4. Numerical Results

We have performed numerical experiments on a personal computer with Intel CORE i5-6200U/4GB/1TB. The numerical results have been obtained by running our algorithms on the set of 43 equality constrained problems. These problems were taken from the following web page:https://www.gamsworld.org/performance/princetonlib/htm/group5stat.htm.In Table1, Name, N, and M stand for the name of the chosen test problem, the number of variable, and the number of constraint, respectively.Table 1
Numerical comparisons.
NameNMeigena211055eigencco3014fccu198hs00721hs03942hs07762hs0822hs04652hs05052hs05674bt231bt652hs100lnp72bt1253mwright53eigenaco11055hatfldg2524genhs28108hs02731hs04043hs07853hs02631hs04852hs05153hs06132bt353bt753bt1022bt532eigenbco11055robot149hs111lnp103hs02831hs04753hs07953hs04242hs04952hs05253hs00921bt432bt942bt1153maratos21We used the starting point supplied with these problems, wrote all codes in the Matlab code, and limited all attempts to solve these test problems to a maximum of 1000 iterations. The parameters in these algorithms were chosen as follows:β=0.3, γh=0.01, γℒ=0.5, τ1=1, ν=104, sh=1.5, sℒ=3.2, γα=0.5, and ς=0.5, which seemed to work reasonably well for a broad class of problems. Update the Hessian matrix approximation Wk by the BFGS secant update formula(27)Wk+1=Buk,yk,Wk=Wk+ykykTykTuk−WkukWkukTukTWkuk.The computation terminated if the following stopping criterion was satisfied:(28)∇xℒxk,λkck≤10−5.We summarize the numerical results in Figures1(a)–1(d) in terms of the performance profiles as outlined in [11]. Our profiles are based on the number of iterations, that of evaluating function, that of augment of the filter set, and the CPU times (seconds). The value of ρτ for τ=1 represents the probability that the algorithm will win over the others. Function values ρτ on the rightmost values illustrate the robustness of the approach.Figure 1
Performance profile on [1, 10].
(a)(b)(c)(d)Figures1(a) and 1(b) show the performance profiles for the number of iterations and that of evaluating function required to solve the problems, by the three different algorithms. We can observe from the two figures that ALG 1, which solves 98% of the problems, is superior to the next two. Because of solving 83% of those, ALG 2 is inferior to ALG 3, which solves 92% of those. From this figure, it is clear that ALG 1 has the most wins (has the highest probability of being the optimal algorithm) and that the probability that ALG 1 is the winner on a given problem is about 0.7.As is known to all, the fewer number the filter set augments, the better performance the algorithm achieves. From Figure1(c), we may analyze that ALG 1 is the most efficient on almost 70% of the problems when the number of the filter expansions is under comparison. Observing the right side of the plots in the figure, we conclude that ALG 1 solves most problems to optimality (approximately 97.5%).A CPU-time performance profile is presented in Figure1(d) for the given test problems and these 3 algorithms. An observation that emerges from the figure is that ALG 3 clearly outperforms the other algorithms. The second conclusion is that ALG 1 is by far the worst with τ≤6. Another point of interest is that ALG 1 and ALG 3 have the best probability ρτ for τ in the interval τ≥8, with similar performance.These performance profiles can indicate that the proposed three algorithms are effective and robust.


## 5. Conclusions

In this paper, we propose a class of inexact secant line search filter methods for solving nonlinear equality constrained optimization. The local convergence properties and numerical performance of the class of algorithms are presented. A simple modification of these methods proposed in a companion paper [7] avoiding second-order correction steps is given. Our methods do not suffer from the Maratos effect by using Lagrangian function ℒ as the objective function and cx2 as the constraint violation. We compare these three methods, and detailed numerical results indicate that the proposed algorithms are robust and effective, while ALG 1 is superior to the next two.



---

*Source: 6253424-2021-11-10.xml*