# A New Augmented Lagrangian Method for Equality Constrained Optimization with Simple Unconstrained Subproblem

Authors: Hao Zhang; Qin Ni
Journal: Discrete Dynamics in Nature and Society
 (2017)

---

## Abstract

We propose a new method for equality constrained optimization based on augmented Lagrangian method. We construct an unconstrained subproblem by adding an adaptive quadratic term to the quadratic model of augmented Lagrangian function. In each iteration, we solve this unconstrained subproblem to obtain the trial step. The main feature of this work is that the subproblem can be more easily solved. Numerical results show that this method is effective.


---

## Body

## 1. Introduction

In this paper, we consider the following equality constrained optimization:(1)minfxs.t.cix=0,i=1,…,m,where x∈Rn, fx:Rn→R, and cix:Rn→Ri=1,…,m are twice continuously differentiable.The method presented in this paper is a variant of the augmented Lagrangian method (denoted by AL). In the late 1960s, AL method was proposed by Hestenes [1] and Powell [2]. Later Conn et al. [3, 4] presented a practical AL method and proved the global convergence under the LICQ condition. Since then, AL method attracted the attentions of many scholars and many variants were presented (see [5–11]). Up to now, there are many computer packages based on AL method, such as LANCELOT [4] and ALGENCAN [5, 6]. In the past decades, AL method was fully developed. Attracted by its well performance, there are still many scholars devoted to research AL method and its applications in recent years (see [7, 8, 11–15]).For (1), we define the Lagrangian function(2)lx,λ=fx-λTcxand the augmented Lagrangian function(3)Lx,λ,σ=lx,λ+σ2cx2,where λ is called the Lagrangian multiplier and σ is called the penalty parameter. In this paper, · refers to the Euclidean norm.In a typical AL method, at thekth step, for given multiplier λk and penalty parameter σk, an unconstrained subproblem(4)minx∈RnLx,λk,σk is solved to find the next iteration point. Then, the multiplier and penalty parameter are updated by some rules. For convenience, for given λk and σk, we define(5)Φkx=Lx,λk,σk=lx,λk+σk2cx2.Motivated by the regularized Newton method for unconstrained optimization (see [16–19]), we construct a new subproblem of (1). At the kth iteration point xk, Φkxk+s is approximated by the following quadratic model: (6)m¯ks=lxk,λk+∇xlxk,λkTs+12sTBks+σk2cxk+Axks2=lxk,λk+∇xfxk-AxkTλkTs+12sTBks+σk2cxk+Axks2=Φkxk+∇xfxk-AxkTλk+σkAxkTcxkTs+12sTBk+σkAxkTAxks,where Axk=∇xc1xk,…,∇xcmxkT and Bk is a positive semidefinite approximation of ∇xx2lxk,λk. Let(7)g~k=∇Φkxk=∇xfxk-AxkTλk+σkAxkTcxk;B~k=Bk+σkAxkTAxk,thus we have(8)m¯ks=Φkxk+g~kTs+12sTB~ks.In [14, 15], m¯ks is minimized within a trust region to find the next iteration point. Motivated by the regularized Newton method, we add a regularization term to the quadratic model m¯ks and define(9)mks=m¯ks+12μks2=Φkxk+g~kTs+12sTB~ks+12μks2,where μk is called regularized parameter. At the kth step of our algorithm, we solve the following convex unconstrained quadratic subproblem:(10)mins∈Rn⁡mks=Φkxk+g~kTs+12sTB~ks+12μks2for finding the trial step sk. Then, we compute the ratio between the actual reduction and predicted reduction(11)ρk=AredkPredk=Φkxk-Φkxk+skΦkxk-mkxk+sk.When ρk is close to 1, we accept xk+sk as the next iteration point. At the same time, we think the quadratic model mks is a sufficiently “good” approximation of Φkxk+s and reduce the value of μk. Conversely, when ρk is close to zero, we set xk+1=xk and increase the value of μk, by which we wish to reduce the length of the next trial step. This technique is similar to the update rule of trust region radius. Actually, sufficiently large μk indeed reduces the length of the trial step sk. However, the regularized parameter is different from trust region radius. In [14, 15], the authors construct a trust region subproblem(12)mins∈Δk⁡m¯ks=Φxk+g~kTs+12sTB~ks.The exact solution sk of (12) satisfies the first-order critical conditions if there exists some μ¯k≥0 such that B~k+μ¯kI is positive semidefinite and(13)g~k+B~k+μ¯kIsk=0sk≤Δkμ¯ksk-Δk=0,while the first-order critical condition of (10) is(14)g~k+B~k+μksk=0.Equations (13) and (15) can show the similarities and differences between regularized subproblem (10) and trust region subproblem (12). It seems that the parameter μk plays a role similar to the multiplier μ¯k in the trust region subproblem. But, actually, the update rule of μk (see (26)) shows that μk is not the approximation of μ¯k. The update of μk depends on the quality of last trial step sk-1 and has no direct relation with system (13).To establish the global convergence of an algorithm, some kind of constraint qualification is required. There are many well-known constraint qualifications, such as LICQ, MFCQ, CRCQ, RCR, CPLD, and RCPLD. In case there are only equality constraints, LICQ is equivalent to MFCQ in which∇cix∣i=1,…,m has full rank; CRCQ is equivalent to CPLD in which any subset of ∇cix∣i=1,…,m maintains constant rank in a neighborhood of x; RCR is equivalent to RCPLD in which ∇cix∣i=1,…,m maintains constant rank in a neighborhood of x. RCPLD is weaker than CRCQ, and CRCQ is weaker than LICQ. In this paper, we use RCPLD which is defined in the following.Definition 1.
One says that RCPLD holds at a feasible pointx∗ of (1), if there exists a neighborhood Ux∗ of x∗ such that ∇cix∣i=1,…,m maintains constant rank for all x∈Ux∗.The rest of this paper is organized as follows. In Section2, we give a detailed description of the presented algorithm. The global convergence is proved in Section 3. In Section 4, we present the numerical experiments. Some conclusions are given in Section 5.Notations. For convenience, we abbreviate ∇xfxk to gk, fxk to fk, cxk to ck, and Axk to Ak. In this paper, λi denotes the ith component of the vector λ.


## 2. Algorithm

In this section, we give a detailed description of the proposed algorithm.As mentioned in Section1, we solve the unconstrained subproblem (10) to obtain the trial step sk. Since Bk is at least positive semidefinite and B~k=Bk+σkAkTAk, B~k+μkI is positive definite as μk>0. Therefore, (10) is a strictly convex quadratic unconstrained optimization. sk solves (10) if and only if(15)g~k+B~k+μkIsk=0holds. Global convergence does not depend on the exact solution of (15), although the linear system (15) is easy to be solved. For minimizer of (10) along the direction -g~k, specifically, we consider the following subproblem:(16)minα≥0⁡mk-αg~k=Φkxk-αg~k2+12α2g~kTB~kg~k+12α2μkg~k2.If g~k>0, then the minimizer of (16) is αk∗=g~k2/g~kTB~kg~k+μkg~k2. Therefore, at the kth step, it follows that(17)Predk≥Φkxk-mk-αk∗g~k=g~k42g~kTB~kg~k+μkg~k2.By direct calculation, we have that(18)Predk≥g~k24min⁡1B~k,1μk.In Section 3, we always suppose that (18) holds.In a typical AL algorithm, the update rule ofσk depends on the improvement of constraint violation. A commonly used update rule is that if ck+1<τkck, where 0<τk<1, one may think that the constraint violation is reduced sufficiently and thus σk+1=σk is a good choice. Otherwise, if ck+1≥τkck, one thinks that current penalty parameter can not sufficiently reduce the constraint violation and increase it in the next iteration. In [20], Yuan proposed a different update rule of σk for trust region algorithm. Specifically, if(19)Predk<δkσkmin⁡Δkck,ck2,σk is increased. In (19), δk is an auxiliary parameter such that δkσk tends to zero. We slightly modify (19) in our algorithm. Specifically, if(20)Predk<δkσkmin⁡ckmax⁡1,g~kμk,ck2,σk is increased.In typical AL method, next iteration pointxk+1 is obtained by minimizing Lx,λk,σk. In most AL methods, xk+1 satisfies that ∇xLxk+1,λk,σk<εk, where εk is controlling parameter which tends to zero. As (21)∇xLxk+1,λk,σk=gk+1-Ak+1Tλk-σkck,when εk is sufficiently small, λk-σkck is a good estimate of the next multiplier λk+1. As we obtain xx+1 by minimizing mks, the critical point of mks has no direct relation to ∇xLxk+1,λk,σk. Therefore, the update rule λk+1=λk-σkck does not suit our algorithm. We obtain λk+1 by approximately solving the following least squares problem:(22)minλ∈Rm⁡12gk+1-Ak+1Tλ2.Most AL algorithms require thatλk is bounded to ensure the global convergence. Hence, all components of λk are restricted to certain interval λ¯,λ_. This technique is also used in our algorithm.Now, we give the detailed algorithm in the following.Algorithm 2.
Step  0 (initialization). Choose the parameters 0<γ1<γ2<1, 0<θ1<1≤θ2<θ3, λ¯>λ_. Determine x0∈Rn, λ0∈Rm, σ0>0, δ0>0, B0∈Rn×n. Let R0=max⁡cx0,1.Set k≔0.
Step  1 (termination test). If g~k=0 and ck=0, return xk as a KKT point. If g~k=0, ck>0, and AkTck=0, return xk as an infeasible KKT point.
Step  2 (determine the trial step). Evaluate the trial step sk by solving(23)mins∈Rn⁡mks=Φkxk+g~kTs+12sTB~ks+12μks2such that (18) holds. Compute the ratio between the actual reduction to the predicted reduction(24)ρk=AredkPredk,where Aredk=Φkxk-Φkxk+sk, Predk=Φkxk-mkxk+sk. Set(25)xk+1=xk+sk,ρk≥γ1,xk,ρk<γ1,(26)μk+1=θ1μk,ρk≥γ2,θ2μk,γ1≤ρk<γ2,θ3μk,ρk<γ1.
Step  3 (update the penalty parameter). If(27)Predk<δkσkmin⁡ckmax⁡1,g~kμk,ck2,set(28)σk+1=2σk,δk+1=14δk.Otherwise, set(29)σk+1=σk,δk+1=δk.
Step  4 (update the multiplier). If ck+1≤Rk, set Rk+1=1/2Rk. Evaluate λ^k+1 by(30)minλ∈Rm⁡gk-AkTλ,and let(31)λk+1i=min⁡max⁡λ^k+1i,λ_,λ¯,i=1,…,m.
Ifck+1>Rk, set Rk+1=Rk and λk+1=λk.
Setk≔k+1 and go to Step  1.Remark 3.
In practical calculation, it is not required to solve (30) exactly to find λ^k+1. In our implementation of Algorithm 2, we use the Matlab subroutineminres to find an approximate solution of the linear system AkAkTλ=Akgk and take it as an approximation of λ^k+1.


## 3. Global Convergence

In this section, we discuss the global convergence of Algorithm2. We assume that Algorithm 2 can find an infinite set {xk} and give some assumptions in the following.Assumptions 1.
(A1)fx and cx are twice continuously differentiable.
(A2)xk and Bk are bounded, where Bk is positive semidefinite approximation of ∇xx2lxk,λk.
Firstly, we give a result on the upper bound of the trial step.Lemma 4.
Ifsk solves subproblem (23), then one has(32)sk≤4g~kμkorμk≤2B~khold∀k≥0.Proof.
Any approximate solutionsk of (23) satisfies Predk=Φkxk-mksk≥0. Clearly,(33)0≤Φkxk-mksk=-g~kTsk-12skTB~ksk-12μksk2≤g~ksk+12B~ksk2-12μksk2=g~k-14μksksk+12B~k-12μksk2.If sk=0, then (32) holds. If sk>0, g~k-1/4μksksk+1/2B~k-1/2μksk2≥0 implies that g~k-1/4μksk≥0 or B~k-1/2μk≥0. Thus we can obtain (32).Now, we discuss convergence properties in two cases. One is that the penalty parameterσk tends to ∞ and the other is that σk is bounded.


### 3.1. The Case ofσk→∞

Lemma 5.
Suppose that (A1)-(A2) hold andσk→∞; then there exists a constant c∗ such that ck→c∗.Proof.
See Lemma  3.1 in Wang and Yuan [15].In Lemma5, if c∗>0, then any accumulation point of xk is infeasible. Sometimes (1) is naturally infeasible; in other words, the feasible set x∣cx=0 is empty. In this case, we wish to find a minimizer of constraint violation. Specifically, we wish to solve(34)minx∈Rn⁡cx2.The solution of this problem is characterized by(35)Ax∗Tcx∗=0.In the next theorem, we show that if {ck} is not convergent to zero, at least one of the accumulation points of xk satisfies (35).Theorem 6.
Suppose that (A1)-(A2) hold andσk→∞. If ck→c>0, then(36)liminfk→∞⁡AkTck=0.Proof.
We prove this result by contradiction. Suppose that there exists someτ>0 such that(37)AkTck>2τ,∀k≥0.By the definition of g~k in (7), we know that(38)g~k≥σkAkTck-gk-AkTλk.As xk and λk are bounded, we can deduce the boundedness of gk-AkTλk by (A2); that is, there exists some τ¯>0 such that(39)gk-AkTλk<τ¯.By (37), (38), and (39), we can conclude that(40)g~k≥2τσk-τ¯>τσkholds for all sufficiently large k. By the boundedness of Bk and Ak, we can conclude that there exists M>0, such that(41)B~k<Mσkholds for all sufficiently large k, where B~k is defined by (7). By (18), (40), and (41),(42)Predk≥g~k24min⁡1B~k,1μk=g~k4min⁡g~kB~k,g~kμk≥τσk4min⁡τM,g~kμkholds for all sufficiently large k. By the update rule of σk and the fact that σk→∞, we have that(43)Predk<δkσkminckmax⁡1,g~kμk,ck2holds for infinitely many k. As g~k>1 holds for all sufficiently k by (40), it is easy to see that (42) contradicts to (43) as δkσk→0 and ck is convergent. Thus we can prove the desired result.Lemma 7.
Suppose that (A1)-(A2) hold,σk→∞, and ck→0; then (44)liminfk→∞⁡g~k=0.Proof.
Assume that there existsτ>0 such that(45)g~k>τ>0,∀k≥0.Then, by (18) and (41), we know that, for all sufficiently large k,(46)Predk≥τ4min⁡τMσk,g~kμk.By the update rule of σk and σk→∞,(47)Predk<δkσkmin⁡ckmax⁡1,g~kμk,ck2holds for infinitely many k. We will prove that (47) contradicts to (46). Let K be the index set containing all k such that (47) holds. Therefore, for all k∈K,(48)Predk<δkσkckmax⁡1,g~kμk,(49)Predk<δkσkck2.If there exists an infinite subset K1⊆K such that g~k≤1 holds for all k∈K1, then, by (48), it holds that(50)Predk<δkσkckμk,∀k∈K1.As δkσk→0, ck→0, and g~k>τ, (50) implies that(51)Predk<τ4g~kμkholds for all sufficiently large k∈K1. If there exists an infinite subset K2⊆K such that g~k>1 holds for all k∈K2, then by (48) we have that(52)Predk<δkσkckg~kμkfor all k∈K2. Equation (52) also implies (51) as δkσk→0 and ck→0. From (28) and (29), it follows that δkσk2=δ0σ02 holds for all k≥0. Therefore, by (49) we know that, for all k∈K,(53)Predk<δkσkck2=δkσk2ck21σk=δ0σ02ck21σk.As ck→0, (53) implies that(54)Predk<τ4τMσkholds for all sufficiently large k∈K. Thus from (47), we obtain (51) and (54) which contradict to (46). Thus we can complete the proof.Theorem 8.
Suppose that (A1)-(A2) hold. Ifck→0 and σk→∞, then there exists one cluster point x∗ of xk such that x∗ is a KKT point of (1) or the RCPLD condition does not hold at x∗.Proof.
Under the assumptions of this theorem, Lemma7 implies that there exists an index set K such that xk∣k∈K converge to some x∗,(55)limk→∞,k∈K⁡ck=0,limk→∞,k∈K⁡g~k=limk→∞,k∈K⁡gk-AkTλk-σkck=0,where g~k is defined in (7). With the help of Theorem  2 in Andreani et al. [21], (55) imply that x∗ is a KKT point or the RCPLD condition does not hold at x∗.


### 3.2. The Case of{σk} Being Bounded

In this subsection, without loss of generality, we assume thatσk=σ0 for all k≥0. Thus by the update rule (29), we have that δk=δ0 and(56)Predk≥δ0σ0min⁡ckmax⁡1,g~kμk,ck2holds for all k≥0. As σk remains constant, it follows from (A1) and (A2) that g~k and B~k are all bounded. If we define the index set(57)S≜k∣ρk≥γ1,then xk+1=xk for k∉S.Lemma 9.
Suppose that (A1)-(A2) hold andσk=σ0 for all k≥0. If 1/μk→0, as k→∞, and there exists some constant c>0 such that(58)Predk>cg~kμkholds∀sufficientlylargek,then ∑k∈Sg~k/μk is divergent.Proof.
We prove this lemma by contradiction. We will show that if∑k∈Sg~k/μk is convergent, then μk+1<μk holds for all sufficiently large k which contradicts to the fact that 1/μk→0, as k→∞.
Suppose that(59)∑k∈Sg~kμk=s.limk→∞⁡1/μk=0 and (32) imply that(60)sk≤4g~kμkholds for all sufficiently large k. By the definition of S,(61)∑k=0∞xk+1-xk=∑k∈Ssk.Equations (59)–(61) imply that xk is convergent. Let(62)rk=ρk-γ2Predk=1-γ2Predk+Aredk-Predk.It is clear that rk>0⇔ρk>γ2. By Taylor’s theorem, it holds that(63)Aredk-Predk=mksk-Φkxk+sk=-∇Φkxk+ξk-g~kTsk+12skTB~ksk+12μksk2≥-∇Φkxk+ξk-g~ksk,where ξk is a convex combination of xk and xk+sk. According to (60), we have that(64)Aredk-Predk≥-4∇Φkxk+ξk-g~kg~kμkholds for all sufficiently large k and thus(65)rk≥c1-γ2-4∇Φkxk+ξk-g~kg~kμk.The convergence of {xk} and the boundedness of {λk} imply that ∇Φkxk+ξk-g~k→0. Therefore, for all sufficiently large k,rk>0. This implies that ρk>γ2 and μk+1<μk.Lemma 10.
Suppose that (A1)-(A2) hold andσk=σ0 for all k≥0; then we have that(66)limk→∞⁡ck=0.Proof.
Firstly, we prove that the sum ofAredk is bounded. Define the indices set(67)K=k∣ck+1≤Rk,where Rk is defined by Steps 0 and 4 in Algorithm 2. From Step  4 of Algorithm 2, we know that if k∉K, then ck+1>Rk and λk+1=λk. Hence we have(68)∑k=0∞-λkTck+λkTck+1=-λ0Tc0+∑k=0∞λk-λk+1Tck+1=-λ0Tc0+∑k∈Kλk-λk+1Tck+1≤-λ0Tc0+2λmax∑k∈Kck+1≤-λ0Tc0+2λmax∑k∈KRk,where λmax is the upper bound of λk. From Step  4 and (67), we have(69)∑k∈KRk≤R01+12+14+⋯=2R0,which implies(70)∑k=0∞-λkTck+λkTck+1≤-λ0Tc0+4R0λmax.Then, we have(71)∑k=0∞Aredk=∑k=0∞Φkxk-Φkxk+1=∑k=0∞fk-fk+1+∑k=0∞-λkTck+λkTck+1+σ02∑k=0∞ck2-ck+12≤f0+-λ0Tc0+4R0λmax+σ02c02≜A¯,where Φkx is defined by (5).
Secondly, we prove(72)liminfk→∞⁡ck=0by contradiction. Suppose that there exists some τ>0 such that(73)ck>τ>0,∀k≥0.Equations (56) and (73) imply that(74)Predk≥δ0σ0min⁡max⁡1,g~kμkτ,τ2.Considering the sum of Predk on the index set S (see (57)), we have by (71) that(75)∑k∈SPredk≤1γ1∑k∈SAredk=1γ1∑k=0∞Aredk≤1γ1A¯.It can be deduced by (74) and (75) that (76)∑k∈Smax⁡1,g~kμk<+∞and thus(77)∑k∈Sg~kμk<+∞,∑k∈S1μk<+∞.If S is a finite set, then it follows from (57) and Step  2 that ρk≥γ1 and μk+1=θ3μkθ3>1 hold for all sufficiently large k. Therefore, 1/μk→0, as k→∞. If S is an infinite set, the second inequality in (77) implies that 1/μk→0, as k→∞ and k∈S. From Step  2, we know that if k∉S, then μk+1≥μk. Hence, we have 1/μk→0, as k→∞. The fact that 1/μk→0 and (74) imply that (78)Predk≥δ0σ0τg~kμkholds for all sufficiently large k. Hence it can be deduced by Lemma 9 that ∑k∈Sg~k/μk is divergent which contradicts the first part in (77).
Finally, we prove (66). If S is a finite set, then xk is convergent. Thus, (72) implies (66). From now on we assume that S is an infinite set. Suppose that (66) does not hold; then there exist an infinite index set K~=ki (K~⊂S) and a constant c>0 such that(79)cki>2cholds∀ki∈K~.By (72), there also exists an infinite index set K^=li (K^⊂S) such that ki<li,(80)ck≥cholds,∀ksuch  thatki≤k<li,(81)cli<cholds∀li∈K^.Let K¯=k∣k∈S,ck≥c; then K~⊂K¯ and K¯ is an infinite index set,(82)∑k∈K¯Predk≤∑k∈SPredk.Therefore, by (75), we have that(83)∑k∈K¯Predk≤1γ1A¯.With the help of (56), (80), and (83), we obtain that(84)∑k∈K¯max⁡1,g~kμk<+∞.A direct conclusion which can be drawn by (84) is(85)1μk⟶0,ask∈K¯,k⟶∞.Thus by Lemma 4, we have that, for all sufficiently large k∈K¯,(86)sk≤4g~kμk.Therefore, for sufficiently large j,(87)xli-xki≤∑ki≤k<li,k∈K¯sk≤4∑ki≤k<li,k∈K¯g~kμk.Equations (84) and (87) imply that xli-xki→0, as i→∞. Therefore (79) contradicts (81). Thus we complete the proof.Lemma 11.
Suppose that (A1)-(A2) hold andσk=σ0 for all k≥0; then we have(88)liminfk→∞⁡g~k=0.Proof.
Suppose that (88) does not hold. Then there exists τ>0, such that(89)g~k>τholds,∀k.By (18), we have that(90)Predk≥τ24min⁡1B~k,1μkholds∀k.As B~k is bounded above, similar to the second part in the proof of Lemma 10, we can conclude that(91)1μk⟶0,ask⟶∞,and thus(92)Predk≥τ241μkholdsfor  all  sufficientlylargek.By (75) and (92), we have that ∑k∈S1/μk is convergent and thus ∑k∈Sg~k/μk is also convergent as g~k is bounded. However, Lemma 9, (91), (92), and the boundedness of {g~k} deduce the divergence of ∑k∈Sg~k/μk. This contradiction completes the proof.With the help of Lemmas10 and 11, we can easily obtain the following result.Theorem 12.
Suppose that (A1)-(A2) hold andσk=σ0 for all k≥0; there exists an accumulation point of xk at which the KKT condition holds.Note that, in Theorem12, we do not suppose that RCPLD holds.


## 3.1. The Case ofσk→∞

Lemma 5.
Suppose that (A1)-(A2) hold andσk→∞; then there exists a constant c∗ such that ck→c∗.Proof.
See Lemma  3.1 in Wang and Yuan [15].In Lemma5, if c∗>0, then any accumulation point of xk is infeasible. Sometimes (1) is naturally infeasible; in other words, the feasible set x∣cx=0 is empty. In this case, we wish to find a minimizer of constraint violation. Specifically, we wish to solve(34)minx∈Rn⁡cx2.The solution of this problem is characterized by(35)Ax∗Tcx∗=0.In the next theorem, we show that if {ck} is not convergent to zero, at least one of the accumulation points of xk satisfies (35).Theorem 6.
Suppose that (A1)-(A2) hold andσk→∞. If ck→c>0, then(36)liminfk→∞⁡AkTck=0.Proof.
We prove this result by contradiction. Suppose that there exists someτ>0 such that(37)AkTck>2τ,∀k≥0.By the definition of g~k in (7), we know that(38)g~k≥σkAkTck-gk-AkTλk.As xk and λk are bounded, we can deduce the boundedness of gk-AkTλk by (A2); that is, there exists some τ¯>0 such that(39)gk-AkTλk<τ¯.By (37), (38), and (39), we can conclude that(40)g~k≥2τσk-τ¯>τσkholds for all sufficiently large k. By the boundedness of Bk and Ak, we can conclude that there exists M>0, such that(41)B~k<Mσkholds for all sufficiently large k, where B~k is defined by (7). By (18), (40), and (41),(42)Predk≥g~k24min⁡1B~k,1μk=g~k4min⁡g~kB~k,g~kμk≥τσk4min⁡τM,g~kμkholds for all sufficiently large k. By the update rule of σk and the fact that σk→∞, we have that(43)Predk<δkσkminckmax⁡1,g~kμk,ck2holds for infinitely many k. As g~k>1 holds for all sufficiently k by (40), it is easy to see that (42) contradicts to (43) as δkσk→0 and ck is convergent. Thus we can prove the desired result.Lemma 7.
Suppose that (A1)-(A2) hold,σk→∞, and ck→0; then (44)liminfk→∞⁡g~k=0.Proof.
Assume that there existsτ>0 such that(45)g~k>τ>0,∀k≥0.Then, by (18) and (41), we know that, for all sufficiently large k,(46)Predk≥τ4min⁡τMσk,g~kμk.By the update rule of σk and σk→∞,(47)Predk<δkσkmin⁡ckmax⁡1,g~kμk,ck2holds for infinitely many k. We will prove that (47) contradicts to (46). Let K be the index set containing all k such that (47) holds. Therefore, for all k∈K,(48)Predk<δkσkckmax⁡1,g~kμk,(49)Predk<δkσkck2.If there exists an infinite subset K1⊆K such that g~k≤1 holds for all k∈K1, then, by (48), it holds that(50)Predk<δkσkckμk,∀k∈K1.As δkσk→0, ck→0, and g~k>τ, (50) implies that(51)Predk<τ4g~kμkholds for all sufficiently large k∈K1. If there exists an infinite subset K2⊆K such that g~k>1 holds for all k∈K2, then by (48) we have that(52)Predk<δkσkckg~kμkfor all k∈K2. Equation (52) also implies (51) as δkσk→0 and ck→0. From (28) and (29), it follows that δkσk2=δ0σ02 holds for all k≥0. Therefore, by (49) we know that, for all k∈K,(53)Predk<δkσkck2=δkσk2ck21σk=δ0σ02ck21σk.As ck→0, (53) implies that(54)Predk<τ4τMσkholds for all sufficiently large k∈K. Thus from (47), we obtain (51) and (54) which contradict to (46). Thus we can complete the proof.Theorem 8.
Suppose that (A1)-(A2) hold. Ifck→0 and σk→∞, then there exists one cluster point x∗ of xk such that x∗ is a KKT point of (1) or the RCPLD condition does not hold at x∗.Proof.
Under the assumptions of this theorem, Lemma7 implies that there exists an index set K such that xk∣k∈K converge to some x∗,(55)limk→∞,k∈K⁡ck=0,limk→∞,k∈K⁡g~k=limk→∞,k∈K⁡gk-AkTλk-σkck=0,where g~k is defined in (7). With the help of Theorem  2 in Andreani et al. [21], (55) imply that x∗ is a KKT point or the RCPLD condition does not hold at x∗.


## 3.2. The Case of{σk} Being Bounded

In this subsection, without loss of generality, we assume thatσk=σ0 for all k≥0. Thus by the update rule (29), we have that δk=δ0 and(56)Predk≥δ0σ0min⁡ckmax⁡1,g~kμk,ck2holds for all k≥0. As σk remains constant, it follows from (A1) and (A2) that g~k and B~k are all bounded. If we define the index set(57)S≜k∣ρk≥γ1,then xk+1=xk for k∉S.Lemma 9.
Suppose that (A1)-(A2) hold andσk=σ0 for all k≥0. If 1/μk→0, as k→∞, and there exists some constant c>0 such that(58)Predk>cg~kμkholds∀sufficientlylargek,then ∑k∈Sg~k/μk is divergent.Proof.
We prove this lemma by contradiction. We will show that if∑k∈Sg~k/μk is convergent, then μk+1<μk holds for all sufficiently large k which contradicts to the fact that 1/μk→0, as k→∞.
Suppose that(59)∑k∈Sg~kμk=s.limk→∞⁡1/μk=0 and (32) imply that(60)sk≤4g~kμkholds for all sufficiently large k. By the definition of S,(61)∑k=0∞xk+1-xk=∑k∈Ssk.Equations (59)–(61) imply that xk is convergent. Let(62)rk=ρk-γ2Predk=1-γ2Predk+Aredk-Predk.It is clear that rk>0⇔ρk>γ2. By Taylor’s theorem, it holds that(63)Aredk-Predk=mksk-Φkxk+sk=-∇Φkxk+ξk-g~kTsk+12skTB~ksk+12μksk2≥-∇Φkxk+ξk-g~ksk,where ξk is a convex combination of xk and xk+sk. According to (60), we have that(64)Aredk-Predk≥-4∇Φkxk+ξk-g~kg~kμkholds for all sufficiently large k and thus(65)rk≥c1-γ2-4∇Φkxk+ξk-g~kg~kμk.The convergence of {xk} and the boundedness of {λk} imply that ∇Φkxk+ξk-g~k→0. Therefore, for all sufficiently large k,rk>0. This implies that ρk>γ2 and μk+1<μk.Lemma 10.
Suppose that (A1)-(A2) hold andσk=σ0 for all k≥0; then we have that(66)limk→∞⁡ck=0.Proof.
Firstly, we prove that the sum ofAredk is bounded. Define the indices set(67)K=k∣ck+1≤Rk,where Rk is defined by Steps 0 and 4 in Algorithm 2. From Step  4 of Algorithm 2, we know that if k∉K, then ck+1>Rk and λk+1=λk. Hence we have(68)∑k=0∞-λkTck+λkTck+1=-λ0Tc0+∑k=0∞λk-λk+1Tck+1=-λ0Tc0+∑k∈Kλk-λk+1Tck+1≤-λ0Tc0+2λmax∑k∈Kck+1≤-λ0Tc0+2λmax∑k∈KRk,where λmax is the upper bound of λk. From Step  4 and (67), we have(69)∑k∈KRk≤R01+12+14+⋯=2R0,which implies(70)∑k=0∞-λkTck+λkTck+1≤-λ0Tc0+4R0λmax.Then, we have(71)∑k=0∞Aredk=∑k=0∞Φkxk-Φkxk+1=∑k=0∞fk-fk+1+∑k=0∞-λkTck+λkTck+1+σ02∑k=0∞ck2-ck+12≤f0+-λ0Tc0+4R0λmax+σ02c02≜A¯,where Φkx is defined by (5).
Secondly, we prove(72)liminfk→∞⁡ck=0by contradiction. Suppose that there exists some τ>0 such that(73)ck>τ>0,∀k≥0.Equations (56) and (73) imply that(74)Predk≥δ0σ0min⁡max⁡1,g~kμkτ,τ2.Considering the sum of Predk on the index set S (see (57)), we have by (71) that(75)∑k∈SPredk≤1γ1∑k∈SAredk=1γ1∑k=0∞Aredk≤1γ1A¯.It can be deduced by (74) and (75) that (76)∑k∈Smax⁡1,g~kμk<+∞and thus(77)∑k∈Sg~kμk<+∞,∑k∈S1μk<+∞.If S is a finite set, then it follows from (57) and Step  2 that ρk≥γ1 and μk+1=θ3μkθ3>1 hold for all sufficiently large k. Therefore, 1/μk→0, as k→∞. If S is an infinite set, the second inequality in (77) implies that 1/μk→0, as k→∞ and k∈S. From Step  2, we know that if k∉S, then μk+1≥μk. Hence, we have 1/μk→0, as k→∞. The fact that 1/μk→0 and (74) imply that (78)Predk≥δ0σ0τg~kμkholds for all sufficiently large k. Hence it can be deduced by Lemma 9 that ∑k∈Sg~k/μk is divergent which contradicts the first part in (77).
Finally, we prove (66). If S is a finite set, then xk is convergent. Thus, (72) implies (66). From now on we assume that S is an infinite set. Suppose that (66) does not hold; then there exist an infinite index set K~=ki (K~⊂S) and a constant c>0 such that(79)cki>2cholds∀ki∈K~.By (72), there also exists an infinite index set K^=li (K^⊂S) such that ki<li,(80)ck≥cholds,∀ksuch  thatki≤k<li,(81)cli<cholds∀li∈K^.Let K¯=k∣k∈S,ck≥c; then K~⊂K¯ and K¯ is an infinite index set,(82)∑k∈K¯Predk≤∑k∈SPredk.Therefore, by (75), we have that(83)∑k∈K¯Predk≤1γ1A¯.With the help of (56), (80), and (83), we obtain that(84)∑k∈K¯max⁡1,g~kμk<+∞.A direct conclusion which can be drawn by (84) is(85)1μk⟶0,ask∈K¯,k⟶∞.Thus by Lemma 4, we have that, for all sufficiently large k∈K¯,(86)sk≤4g~kμk.Therefore, for sufficiently large j,(87)xli-xki≤∑ki≤k<li,k∈K¯sk≤4∑ki≤k<li,k∈K¯g~kμk.Equations (84) and (87) imply that xli-xki→0, as i→∞. Therefore (79) contradicts (81). Thus we complete the proof.Lemma 11.
Suppose that (A1)-(A2) hold andσk=σ0 for all k≥0; then we have(88)liminfk→∞⁡g~k=0.Proof.
Suppose that (88) does not hold. Then there exists τ>0, such that(89)g~k>τholds,∀k.By (18), we have that(90)Predk≥τ24min⁡1B~k,1μkholds∀k.As B~k is bounded above, similar to the second part in the proof of Lemma 10, we can conclude that(91)1μk⟶0,ask⟶∞,and thus(92)Predk≥τ241μkholdsfor  all  sufficientlylargek.By (75) and (92), we have that ∑k∈S1/μk is convergent and thus ∑k∈Sg~k/μk is also convergent as g~k is bounded. However, Lemma 9, (91), (92), and the boundedness of {g~k} deduce the divergence of ∑k∈Sg~k/μk. This contradiction completes the proof.With the help of Lemmas10 and 11, we can easily obtain the following result.Theorem 12.
Suppose that (A1)-(A2) hold andσk=σ0 for all k≥0; there exists an accumulation point of xk at which the KKT condition holds.Note that, in Theorem12, we do not suppose that RCPLD holds.


## 4. Numerical Experiment

In this Section, we investigate the performance of Algorithm2. We compare Algorithm 2 with the famous Fortran package ALGENCAN. In our computer program, the parameters in Algorithm 2 are chosen as follows:(93)θ1=0.1,θ2=1,θ3=4,γ1=0.1,γ2=0.9,σ0=1,δ0=1,λ¯=1020,λ_=10-20.We set Bk to be the exact Hessian of the Lagrangian fx-λTcx at the point xk. The Matlab subroutineminres is used to solve (15). All algorithms are terminated when one of the following conditions holds: (1)gk+AkTλk≤10-8 and ck≤10-8; (2)gk+AkTλk≤10-8 and AkTck≤10-8; (3)sk≤10-8. All test problems are chosen from CUTEst collection [22].The numerical results are listed in Table1 where the name of problem is denoted by Name, the number of its variables is denoted by n, the number of constraints is denoted by m, the number of function evaluations is denoted by nf, and the number of gradient evaluations is denoted by ng. In Table 1, we list the results of 38 test problems. Considering the numbers of function evaluations (nf), Algorithm 2 is better thanALGENCAN for 30 cases (78.9%). Considering the numbers of gradient evaluations (ng), Algorithm 2 is better thanALGENCAN for 31 cases (81.6%).Table 1
Results of Algorithm2 and ALGENCAN.
Name
n
m
Algorithm2
ALGENCAN
n
f
n
g
n
f
n
g
AIRCRFTA
8
5
5
5
20
21
ARGTRIG
200
200
69
69
15
16
BOOTH
2
2
6
6
5
6
BROWNALE
200
200
8
8
21
22
BROYDN3D
5000
5000
23
23
22
23
BYRDSPHR
3
2
42
21
80
78
BT1
2
1
17
17
67
45
BT2
3
1
40
37
74
71
BT4
3
2
17
17
34
34
BT5
3
1
12
11
28
28
BT7
5
3
5
5
97
98
BT8
5
2
19
15
76
51
BT9
4
2
18
15
106
100
BT10
2
2
15
15
95
95
BT11
5
3
15
15
75
75
BT12
5
3
10
10
20
21
CHNRSNBE
50
98
100
37
19
20
CLUSTER
2
2
11
11
26
27
CUBENE
2
2
8
6
17
18
DECONVNE
63
40
6
6
3982
1195
EIGENB
7
7
2550
2550
2451
608
GOTTFR
2
2
6
6
24
24
HATFLDF
3
3
5
5
55
45
HEART6
6
6
122
61
387
216
HEART8
8
8
29
10
87
43
HS39
4
2
65
61
106
100
HS48
5
2
46
19
6
7
HYDCAR6
29
29
267
85
212
154
INTEGREQ
502
500
6
6
14
15
MARATOS
2
1
13
11
42
43
MWRIGHT
5
3
14
14
29
29
ORTHREGB
27
6
6
6
23
24
RECIPE
3
3
6
6
39
40
RSNBRNE
2
2
6
6
16
17
SINVALNE
2
2
6
6
8
8
TRIGGER
7
6
481
290
757
270
YFITNE
3
17
11
11
805
520
ZANGWIL3
3
3
6
6
5
6


## 5. Conclusions

In this paper, we present a new algorithm for equality constrained optimization. We add an adaptive quadratic term to the quadratic model of the augmented Lagrangian function. In each iteration, we solve a simple unconstrained subproblem to obtain the trail step. The global convergence is established under reasonable assumptions.From the numerical results and the theoretical analysis, we believe that the new algorithm can efficiently solve equality constrained optimization problems.



---

*Source: 6406514-2017-10-19.xml*