# New Convergence Properties of the Primal Augmented Lagrangian Method

Authors: Jinchuan Zhou; Xunzhi Zhu; Lili Pan; Wenling Zhao
Journal: Abstract and Applied Analysis
 (2011)

---

## Abstract

New convergence properties of the proximal augmented Lagrangian method is established for continuous nonconvex optimization problem with both equality and inequality constrains. In particular, the multiplier sequences are not required to be bounded. Different convergence results are discussed dependent on whether the iterative sequence{xk} generated by algorithm is convergent or divergent. Furthermore, under certain convexity assumption, we show that every accumulation point of {xk} is either a degenerate point or a KKT point of the primal problem. Numerical experiments are presented finally.


---

## Body

## 1. Introduction

In this paper, we consider the following nonlinear programming problem:(P)min⁡f(x)s.t.gi(x)≤0,i=1,…,m;hj(x)=0,j=1,…,l;x∈Ω,
where f,gi:ℝn→ℝ for each i=1,…,m and hj:ℝn→ℝ for each j=1,…,l are all continuously differentiable functions, Ω is a nonempty and closed set in ℝn. Denoted by X the feasible region and by X* the solution set.Augmented Lagrangian algorithms are very popular tools for solving nonlinear programming problems. At each outer iteration of these methods, a simpler optimization problem is solved, for which efficient algorithms can be used, especially when the problems are large. The most famous augmented Lagrangian algorithm based on the Powell-Hestenes-Rockafellar [1–3] formula has been successfully used for defining practical nonlinear programming algorithms [4–7]. At each iteration, a minimization problem with simple constraints is approximately solved whereas Lagrange multipliers and penalty parameters are updated in the master routine. The advantage of the Augmented Lagrangian approach over other methods is that the subproblems can be solved using algorithms that can deal with a very large number of variables without making use of factorization of matrices of any kind.An indispensable assumption in the most existing global convergence analysis for augmented Lagrangian methods is that the multiplier sequence generated by the algorithms is bounded. This restrictive assumption confines applications of augmented Lagrangian methods in many practical situation. The important work on this direction includes [8], where global convergence of modified augmented Lagrangian methods for nonconvex optimization with equality constraints was established; and Andreani et al. [4] and Birgin et al. [9] investigated the augmented Lagrangian methods using safeguarding strategies for nonconvex constrained problems. Recently, for inequality-constrained global optimization, Luo et al. [10] established the convergence properties of the primal-dual method based on four types of augmented Lagrangian functions without the boundedness assumption of the multiplier sequence. More information can be found in [5, 11, 12].In this paper, for the optimization problem (P) with both equality and inequality constraints, we further study the convergence property of the proximal Lagrangian method without requiring the boundedness of multiplier sequences. The main contribution of this paper lies in the following three aspects. First, more general constraints are considered, without restricting only inequality constraints as in [10, 13] and requiring boundedness of X as in [9]. Second, an essential assumption on the global convergence properties given in [4–7, 9, 10] is that the iterative sequence {xk} must be convergent in advance; here, we further discuss the case when {xk} is divergent and develop a necessary and sufficient condition for {f(xk)} converging to the optimal value of primal problem. Third, the definition of degeneration in [9, 10] is extended from inequality constraint to both inequality and equality constraints.This paper is organized as follows. In Section2, we propose the multiplier algorithm and study its global convergence properties. Preliminary numerical results are reported in Section 3. The conclusion is drawn in Section 4.


## 2. Multiplier Algorithms

The primal augmented Lagrangian function for (P) is(2.1)L(x,λ,μ,c):=f(x)+c2[∑j=1l(hj(x)+μjc)2+∑i=1mmax⁡{0,gi(x)+λic}2],
where (x,λ,μ,c)∈ℝn×ℝm×ℝl×ℝ++, and ℝ++ denotes the all positive real scalars, that is, ℝ++={a∈ℝ∣a>0}.Given(x,λ,μ,c), the augmented Lagrangian relaxation problem associated with the augmented Lagrangian L is defined by(Lλ,μ,c)min⁡L(x,λ,μ,c)s.t.x∈Ω.
Given ɛ≥0, then the ɛ-optimal solution set of (Lλ,μ,c), denoted by S*(λ,μ,c,ɛ), is defined as(2.2){x∈Ω∣L(x,λ,μ,c)≤inf⁡x∈ΩL(x,λ,μ,c)+ɛ}.IfΩ is closed and bounded, then the global optimal solution of (Lλ,μ,c) exists. However, if Ω is unbounded, then (Lλ,μ,c) maybe unsolvable. To overcome this difficultly, we assume throughout this paper that f is bounded on Ω from below, that is,(2.3)f*:=inf⁡x∈Ωf(x)>-∞.
This assumption is rather mild in optimization programming, because otherwise the objective function f can be replaced by ef(x). It ensures that the ɛ-optimal solution set with ɛ>0 always exists, since L(x,λ,μ,c) is bounded from below by (2.1) and (2.3).Recall that a vectorx* is said to be a KKT point of (P) if there exist λi*≥0 for each i=1,…,m and μj* for each j=1,…,l such that(2.4)0∈∇f(x)+∑i=1mλi∇gi(x)+∑j=1lμj∇hj(x)+NΩ(x*),λi*gi(x*)=0,∀i=1,…,m,
where 𝒩Ω(x*) denotes the normal cone of Ω at x*. The collection set of all λ* and μ* satisfying (2.4) is denoted by Λ(x*).The multiplier algorithm based on the primal augmented LagrangianL is proposed below. One of its main features is that the Lagrangian multipliers associated with equality and inequality constraints are not restricted to be bounded, which makes the algorithm applicable for many problems in practice.Algorithm 2.1 (Multiplier algorithm based onL).
Step 1.
Select an initial pointx0∈ℝn, λ0≥0, μ0∈ℝ, c0>0, and ɛ0≥0. Set k:=0.Step 2.
Compute(2.5)λik+1=max⁡{0,ckgi(xk)+λik},∀i=1,…,m,(2.6)μjk+1=μjk+ckhj(xk),∀j=1,…,l,(2.7)ɛk+1=ɛkk+1,(2.8)ck+1≥(k+1)max⁡{1,∑i=1m(λik+1)2,∑j=1l(μjk+1)2}.Step 3.
Findxk+1∈S*(λk+1,μk+1,ck+1,ɛk+1);Step 4.
Ifxk+1∈X and (λk+1,μk+1)∈Λ(xk+1), then STOP; otherwise, let k:=k+1 and go back to Step 2.The iterative formula forɛk+1 given in (2.7) is just used to guarantee its convergence to zero. In fact, in the practical numerical experiment, we can choose ɛk+1=ɛk/ck to improve the convergence of the algorithm. The following lemma gives the relationship between the penalty parameter ck and the multipliers λk and μk.Lemma 2.2.
Let(λk,μk,ck) be given as in Algorithm 2.1, then the following terms
(2.9)λkck,μkck,(λk)2ck,(μk)2ck
all approach to zero as k→∞.Proof.
This follows immediately from (2.8).For establishing the convergence property of Algorithm2.1, we first consider the perturbation analysis of (P). Given α≥0, define the perturbation of feasible region as(2.10)X(α)={x∈Ω∣gi(x)≤α,|hj(x)|≤α,i=1,…,m,j=1,…,l},
and the perturbation of level set as(2.11)L(α)={x∈Ω∣f(x)≤v(0)+α}.
It is clear that X(0) coincides with the feasible set of (P). The corresponding perturbation function is given as(2.12)v(α)=inf⁡{f(x)∣x∈X(α)}.The following result shows that the perturbation value function is upper semicontinuous at zero.Lemma 2.3.
The perturbation functionv is upper semicontinuous at zero from right.Proof.
SinceX(0)⊂X(α) for any α≥0, then v(α)≤v(0) by definition (2.12). This implies that limsupα→0+v(α)≤v(0).Lemma 2.4.
Let(λk,μk,ck,ɛk) be given as in Algorithm 2.1. For any ɛ>0, one has
(2.13)S*(λk,μk,ck,ɛk)⊆{x∈Ω∣L(x,λk,μk,ck)≤v(0)+ɛ},
whenever k is sufficiently large.Proof.
For any givenɛ, it follows from (2.7) and Lemma 2.4 that when k is large enough, we have
(2.14)12ck∑i=1m(λikck)2+12ck∑i=1l(μikck)2+ɛk≤ɛ.
Therefore, for x¯∈S*(λk,μk,ck,ɛk),
(2.15)L(x¯,λk,μk,ck)≤inf⁡{L(x,λk,μk,ck)∣x∈Ω}+ɛk≤inf⁡{L(x,λk,μk,ck)∣x∈X(0)}+ɛk≤inf⁡{f(x)∣x∈X(0)}+12ck∑i=1m(λikck)2+12ck∑i=1l(μikck)2+ɛk≤v(0)+ɛ.Lemma 2.5.
Let(λk,μk,ck) be given as in Algorithm 2.1. For any ɛ>0, one has
(2.16){x∈Ω∣L(x,λk,μk,ck)≤v(0)+ɛ}⊆X(ɛ).
whenever k is sufficiently large.Proof.
We prove this result by the way of contradiction. Suppose that we can find anɛ0>0 and an infinite subsequence K⊆{1,2,…} such that
(2.17)zk∈{x∈Ω∣L(x,λk,μk,ck)≤v(0)+ɛ},∀k∈K,
but
(2.18)zk∉X(ε0),∀k∈K.
It follows from (2.17) that
(2.19)v(0)+ε≥L(zk,λk,μk,ck)=f(zk)+ck2[∑j=1l(hj(zk)+μjkck)2+∑i=1mmax⁡{0,gi(zk)+λikck}2].
Sincezk∉X(ɛ0), it needs to consider the following two cases.
Case 1.
There exist an indexj0 and an infinite subsequence K0⊆K such that |hj0(zk)|>ɛ0. It then follows from (2.19) that
(2.20)v(0)+ɛ≥f*+ck2[∑j=1l(hj(zk)+μjkck)2+∑i=1mmax⁡{0,gi(zk)+λikck}2]≥f*+ck2(hj0(zk)+μj0kck)2.
Using Lemma2.2 and the fact that |hj0(zk)|≥ɛ0 gives us
(2.21)(hj0(zk)+μj0kck)2≥12ɛ0,
whenever k is sufficiently large. This, together with (2.20), yields v(0)=+∞ by taking k∈K0 approaching to ∞, which leads to a contradiction.Case 2.
There exist an indexi0 and an infinite subsequence K0⊆K such that gi0(zk)>ɛ0. It follows from (2.19) that
(2.22)v(0)+ɛ≥f*+ck2[∑j=1l(hj(zk)+μjkck)2+∑i=1mmax⁡{0,gi(zk)+λikck}2]≥f*+ck2[∑i≠i0max⁡{0,gi(zk)+λikck}2+max⁡{0,gi0(zk)+λi0kck}2]≥f*+ck2max⁡{0,gi0(zk)+λi0kck}2≥f*+ɛ0ck4,
where the last step is due to Lemma 2.2, since gi0(zk)>ɛ0 and λi0k/ck→0. Taking limits in the above inequality yields v(0)=+∞, which is a contradiction. This completes the proof.Lemma 2.6.
Let(λk,μk,ck) be given as in Algorithm 2.1. For any ɛ>0, one has
(2.23){x∈Ω∣L(x,λk,μk,ck)≤v(0)+ɛ}⊆L(ɛ),∀k=1,2,….Proof.
For an arbitrarilyx¯∈{x∈Ω∣L(x,λk,μk,ck)≤v(0)+ɛ}, we have
(2.24)f(x¯)=L(x¯,λk,μk,ck)-ck2[∑j=1l(hj(x¯)+μjkck)2+∑i=1mmax⁡{0,gi(x¯)+λikck}2]≤v(0)+ɛ.
The proof is complete.With these preparation, the global convergence property of Algorithm2.1 can be given, which shows that if the algorithm terminates in finite steps, then we obtain a KKT point of (P); otherwise, every limit point of {xk} would be the optimal solution of (P).Theorem 2.7.
Let{xk} be the iterative sequence generated by Algorithm 2.1. Then if {xk} is terminated in finite steps, then one gets a KKT point of (P); otherwise, every limit point of {xk} belongs to X*.Proof.
According to the construction of Algorithm2.1, the first part is clear. It remains to prove the second part. Let ɛ>0 be given. It follows from Lemmas 2.4–2.6 that when k is large enough, we have
(2.25)S*(λk,μk,ck,ɛk)⊆{x∈Ω∣L(x,λk,μk,ck)≤v(0)+ɛ}⊆X(ɛ)∩L(ɛ).
Thus,
(2.26)xk∈X(ɛ)∩L(ɛ).
Note that X(ɛ) and L(ɛ) are closed, due to the continuity of f, gi for all i=1,…,m and hj for all j=1,…,l and the closeness of Ω. Taking the limit in (2.26) yields x*∈X(ɛ)∩L(ɛ), which further shows that x*∈X(0)∩L(0), since ɛ>0 is arbitrary, that is, x*∈X*. The proof is complete.The foregoing result is applicable to the case when{xk} at least has an accumulation point. However, a natural question arises: how does the algorithm perform as {xk} is divergent? The following theorem gives an answer.Theorem 2.8.
Let{xk} be an iterative sequence generated by Algorithm 2.1. Then,
(2.27)lim⁡k→∞f(xk)=v(0)
if and only if v(α) is lower semicontinuous at α=0 from right.Proof.
We first show the sufficiency. According to the proof of Theorem2.7 (recall (2.26)), we know that
(2.28)v(ɛ)≤f(xk)≤v(0)+ɛ,
whenever k is sufficiently large. Since v(α) is lower semicontinuous at α=0 from right, taking the lower limitation in (2.28) yields
(2.29)v(0)≤lim⁡inf⁡ɛ→0+v(ɛ)≤lim⁡inf⁡k→∞f(xk)≤limsup⁡k→∞f(xk)≤v(0),
that is,
(2.30)lim⁡k→∞f(xk)=v(0).
We now show the necessity. Suppose on the contrary that v is not lower semicontinuous at zero from right, then there exist δ0>0 and ɛj→0+(asj→∞) such that
(2.31)v(ɛj)≤v(0)-δ0,∀j=1,2,…,m.
For any given k, since ɛj→0 we can choose a subsequence jk satisfying
(2.32)ɛjkck⟶0ask⟶∞.
In addition, let zk∈X(ɛjk) with f(zk)≤v(ɛjk)+δ0/2, which further implies f(zk)≤v(0)-δ0/2 by (2.31). Therefore,
(2.33)f(xk)=L(xk,λk,μk,ck)-ck2[∑j=1l(hj(xk)+μjkck)2+∑i=1mmax⁡{0,gi(xk)+λikck}2]≤inf⁡x∈ΩL(x,λk,μk,ck)+ɛk≤f(zk)+ck2[∑j=1l(hj(zk)+μjkck)2+∑i=1mmax⁡{0,gi(zk)+λikck}2]+ɛk≤v(0)-δ02+ck2[∑j=1l(ɛjk+|μjk|ck)2+∑i=1mmax⁡{0,ɛjk+λikck}2]+ɛk,
where the last step is due to the fact |hj(zk)|≤ɛjk and gi(zk)≤ɛjk since zk∈X(ɛjk). Taking limits in both sides of (2.33) and using (2.7), (2.27), and Lemma 2.2, we get
(2.34)v(0)=lim⁡k→∞f(xk)≤v(0)-δ02,
which leads to a contradiction. The proof is complete.Note that in many practical cases, the setΩ typically stands for a more simple constraint, for example, a box or a bounded polytope [7]. Hence, we conclude this paper by considering the case of Ω is a bounded, closed, and convex subset of ℝn. In this case, the global optimal solution of the augmented Lagrangian relaxation problem always exists. Hence, we choose ɛ0=0 in Step 1 of Algorithm 2.1, which in turn implies that ɛk=0 for all k by (2.7). First, however, we need to extend the definition of degenerate from inequality constraint as in [10] to both inequality and equality constraints.Definition 2.9.
A pointx*∈X is said to be degenerate if there exists λ*∈ℝ+m and μ*∈ℝl such that
(2.35)∑i∈I(x*)λi*+∑j=1l|μj*|>0,PΩ[x*-∑j=1lμj*∇hj(x*)-∑i∈I(x*)λi*∇gi(x*)]=x*,
where 𝒫Ω(x) denotes the projection of x onto Ω and I(x*)={i∣gi(x*)=0,i=1,…,m}.Theorem 2.10.
Suppose thatΩ is a bounded, closed, and convex set of ℝn. Let ɛ0=0 and {xk} be the iterative sequence generated by Algorithm 2.1. Then, every accumulation point of {xk}, say x*, is either a degenerate or a KKT point of (P).Proof.
Noting thatɛk=0 for all k by ɛ0=0 and (2.7), then {xk} is a global optimal solution of L(x,λk,μk,ck) by Step 3 in Algorithm 2.1. Applying the well-known optimality condition of optimization problem to the augmented Lagrangian relaxation problem (Lλ,μ,c) yields
(2.36)-∇xL(x,λk,μk,ck)∈NΩ(xk),
where 𝒩Ω(xk) is the normal cone of Ω at xk. This together with (2.5) and (2.6) means that
(2.37)PΩ[xk-∇f(xk)-∑j=1lμjk+1∇hj(xk)-∑i=1mλik+1∇gi(xk)]=xk,
where we have used the basic property of normal cone of convex set. Let 𝒦 be an infinite subsequence in {1,2,…} such that {xk}𝒦→x*∈Ω. Consider now the following two cases.Case 1.
Either{λk+1}𝒦 or {μk+1}𝒦 is unbounded. In this case, we must have
(2.38)Tk:=∑i=1mλik+1+∑j=1l|μjk+1|⟶∞,k⟶∞,k∈K.
Since 0≤λik+1/Tk≤1 and 0≤μik+1/Tk≤1 are bounded, we can assume by passing a subsequence if necessary that
(2.39)λik+1Tk⟶λi*,μjk+1Tk⟶μj*,i=1,…,m,j=1,…,l.
Clearly, λi* and μj* are not all zeros. On the other hand, since 𝒩Ω(x*) is cone, then it follows from (2.36) that
(2.40)-1Tk∇xL(x,λk,μk,ck)∈NΩ(xk),
from which and using the basic property of normal cone of convex set, we further have
(2.41)PΩ[xk-1Tk(∇f(xk)+∑j=1lμjk+1∇hj(xk)+∑i=1mλik+1∇gi(xk))]=xk.
Since xk→x* and Tk→∞ as k∈𝒦→∞, we obtain from (2.39) and (2.41)
(2.42)PΩ[x*-∑j=1lμj*∇hj(x*)-∑i=1mλi*∇gi(x*)]-x*=0,
where we have used the continuity of the projection operator.
Ifi∉I(x*), then gi(x*)<0. Since ck→∞, we have ckgi(xk)→-∞ as k∈𝒦→∞. Using (2.5) and Lemma 2.2, we obtain
(2.43)lim⁡k→∞,k∈Kλik+1=lim⁡k→∞,k∈Kmax⁡{0,gi(xk)+λikck}ck=0,∀i∉I(x*),
which, together with (2.39), implies that λi*=0 for all i∉I(x*). Therefore, we obtain from (2.42) that
(2.44)PΩ[x*-∑j=1lμj*∇hj(x*)-∑i∈I(x*)λi*∇gi(x*)]-x*=0.
So x* is degenerate.Case 2.
Both{λk+1}𝒦 and {μk+1}𝒦 are bounded. In this case, we can assume without loss of generality that
(2.45)lim⁡k→∞,k∈Kλik=λi*≥0,lim⁡k→∞,k∈Kμik=μi*.
Taking limits in (2.37) gives rise to
(2.46)PΩ[x*-∇f(x*)-∑j=1lμj*∇hj(x*)-∑i=1mλi*∇gi(x*)]=x*,
which is equivalent to
(2.47)-∇f(x*)-∑j=1lμj*∇hj(x*)-∑i=1mλi*∇gi(x*)∈NΩ(x*).
We claim thatx* is a feasible point. In fact, if gi(x*)>0 for some i, then ckgi(xk)→∞ as k∈𝒦1→∞. From (2.5), we must have λik+1→∞, contradicting the boundedness of {λik+1}k∈𝒦. Note that (2.6) can be rewritten as
(2.48)μjk+1ck=μjkck+hj(xk).
Taking limits in both sides and using the boundedness of {μik+1}k∈𝒦, we obtain that hj(x*)=0 for all j=1,2,…,l. Thus, x* is a feasible solution of (P) as claimed.
Ifi∉I(x*), that is, gi(x*)<0, then following almost the same argument as in Case 1, we can show that λi*=0 (cf. (2.43)). Therefore,
(2.49)gi(x*)≤0,λi*gi(x*)=0,i=1,…,m;hj(x*)=0,j=1,2,…,l.
This together with (2.47) implies that x* is a KKT point of (P) and λ*, μ* are the corresponding Lagrangian multipliers.


## 3. Numerical Reports

To give some insight into the behavior of our proposed algorithm presented in this paper, we solve the following nonlinar programming problems. The test was done at a PC of Pentium 4 with 2.8 GHz CPU and 1.99 GB memory, and the computer codes were written in MATLAB 7.0. Numerical results are reported in Tables1–4, where k is the number of iterations, ck is the penalty parameter, xk is iterative point found by the algorithm, and f(xk) is the objective value.Table 1
Result of Example3.1.
kϵkckxkf(xk)11.00006.2500(0.2424, 0.2424, 0.4661)0.334830.166740.0541(0.2299, 0.2299, 0.4438)0.3027Table 2
Result of Example3.2.
kϵkckxkf(xk)116.2500(0.1643, 0.1643, 1.0000)0.158131.66742.6030(0.1350, 0.1350, 1.0000)0.1076Table 3
Result of Example3.3.
kϵkckxkf(xk)11576(3.1094, 3.5073, −1.4777)957.234920.50001.9679e + 008(2.9094, 3.606, −1.8787)956.9680Table 4
Result of Example3.4.
kϵkckxkf(xk)113025(0.7101, 2.8042, 1.5490)978.278120.50008.4469e + 007(0.7208, 2.8092, 1.5579)978.1236Example 3.1 (see [14]).
It holds that(3.1)min⁡0.5(x1+x2)2+50(x2-x1)2+x32+|x3-sin⁡(x1+x2)|s.t.(x1-1)2+(x2-1)2+(x3-1)2-1.5≤0.Example 3.2 (see [14]).
Consider(3.2)min⁡0.5(x1+x2)2+50(x2-x1)2+sin⁡2(x1+x2)s.t.(x1-1)2+(x2-1)2+(x3-1)2-1.5≤0.Example 3.3.
It holds that(3.3)min⁡1000-x12-2x22-x32-x1x2-x1x3s.t.x12+2x22+x32-25=0.Example 3.4.
Consider(3.4)min⁡1000-x12-2x22-x32-x1x2-x1x3s.t.8x1+14x2+7x3-56=0-xi≤0,i=1,2,3.


## 4. Conclusions

Augmented Lagrangian methods are useful tools for solving many practical nonconvex optimization problems. In this paper, new convergence property of proximal augmented Lagrangian algorithm is established without requiring the boundedness of multiplier sequences. It is proved that if the algorithm terminates in finite steps, then we obtain a KKT point of the primal problem; otherwise, the iterative sequence{xk} generalized by algorithm converges to optimal solution. Even if {xk} is divergent, we also present a necessary and sufficient condition for the convergence of {f(xk)} to the optimal value. Moreover, under suitable assumptions, we show that every accumulation point of the iterative sequence generated by the algorithm is either a degenerate or is a KKT point of the primal problem. As our future work, one of the interesting and important topics is whether these nice properties could be extended to more general cone programming, for example, nonlinear semidefinite programming or second-order cone programming.



---

*Source: 902131-2011-12-26.xml*