arXiv:1711.05812v2 [math.OC] 25 Mar 2018

Iteration complexity of inexact augmented Lagrangian methods for constrained
convex programming
Yangyang Xu

Abstract Augmented Lagrangian method (ALM) has been popularly used for solving constrained optimization problems. Practically, subproblems for updating primal variables in the framework of ALM usually
can only be solved inexactly. The convergence and local convergence speed of ALM have been extensively
studied. However, the global convergence rate of inexact ALM is still open for problems with nonlinear inequality constraints. In this paper, we work on general convex programs with both equality and inequality
constraints. For these problems, we establish the global convergence rate of inexact ALM and estimate its
iteration complexity in terms of the number of gradient evaluations to produce a solution with a specified
accuracy.
We first establish an ergodic convergence rate result of inexact ALM that uses constant penalty parameters or geometrically increasing penalty parameters. Based on the convergence rate result, we apply
Nesterov’s optimal first-order method on each primal subproblem and estimate the iteration complexity of
the inexact ALM. We show that if the objective is convex, then O(ε−1 ) gradient evaluations are sufficient to
guarantee an ε-optimal solution in terms of both primal objective and feasibility violation. If the objective
1
is strongly convex, the result can be improved to O(ε− 2 | log ε|). Finally, by relating to the inexact proximal
point algorithm, we establish a nonergodic convergence rate result of inexact ALM that uses geometrically
increasing penalty parameters. We show that the nonergodic iteration complexity result is in the same order
as that for the ergodic result. Numerical experiments on quadratically constrained quadratic programming
are conducted to compare the performance of the inexact ALM with different settings.
Keywords: augmented Lagrangian method (ALM), nonlinearly constrained problem, first-order method,
global convergence rate, iteration complexity
Mathematics Subject Classification: 90C06, 90C25, 68W40, 49M27.
1 Introduction
In this paper, we consider the constrained convex programming
minimize f0 (x), s.t. Ax = b, fi (x) ≤ 0, i = 1, . . . , m,
x∈X

Y. Xu
Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY 12180
E-mail: xuy21@rpi.edu

(1)

2

Yangyang Xu

where X ⊆ Rn is a closed convex set, A and b are respectively given matrix and vector, and fi is a convex
function for every i = 0, 1, . . . , m. Any convex optimization problem can be written in the standard form
of (1). It appears in many areas including statistics, machine learning, data mining, engineering, signal
processing, finance, operations research, and so on.
Note that the constraint x ∈ X can be equivalently represented by using an inequality constraint ιX (x) ≤
0 or adding ιX (x) to the objective, where ιX denotes the indicator function on X . However, we explicitly
use it for technical reason. In addition, every affine constraint a⊤
j x = bj can be equivalently represented by
⊤
x
+
b
≤
0.
That
way does not change theoretical results
x
−
b
≤
0
and
−a
two inequality constraints: a⊤
j
j
j
j
of an algorithm but will make the problem computationally more difficult.
One popular method for solving (1) is the augmented Lagrangian method (ALM), which first appeared
in [16, 29]. ALM alternatingly updates the primal variable and the Lagrangian multipliers. At each update,
the primal variable is renewed by minimizing the augmented Lagrangian (AL) function and the multipliers
by a dual gradient ascent. The global convergence and local convergence rate of ALM have been extensively
studied; see the books [4,5]. Several recent works (e.g., [14,15]) establish the global convergence rate of ALM
and/or its variants for affinely constrained problems. In the framework of ALM, the primal subproblem
usually can only be solved inexactly, and thus practically inexact ALM (iALM) is often used. However,
to the best of our knowledge, the global convergence rate of iALM for problems with nonlinear inequality
constraints still remains open1 . We address this open question in this work and also establish the iteration
complexity of iALM in terms of the number of gradient evaluations. The iteration complexity result appears
to be optimal.
We will assume composite convex structure on (1). More specifically, we assume
f0 (x) = g(x) + h(x),

(2)

where g is a Lipschitz differentiable convex function, and h is a simple2 (possibly nondifferentiable) convex
function. Also, fi is convex and Lipschitz differentiable for every i ∈ [m], namely, there are constants
L0 , L1 , . . . , Lm such that
k∇g(x̂) − ∇g(x̃)k ≤ L0 kx̂ − x̃k, ∀ x̂, x̃ ∈ dom(h) ∩ X ,

k∇fi (x̂) − ∇fi (x̃)k ≤ Li kx̂ − x̃k, ∀ x̂, x̃ ∈ dom(h) ∩ X , ∀i ∈ [m].

(3a)
(3b)

In addition, we assume the boundedness of dom(h) ∩ X and denote its diameter as
D = maximize kx̂ − x̃k.
x̂,x̃∈dom(h)∩X

1.1 Augmented Lagrangian function
In the literature, there are several different penalty terms used in an augmented Lagrangian (AL) function,
such as the classic one [30,31], the quadratic penalty on constraint violation [3], and the exponential penalty
[34]. The work [2] gives a general class of augmented penalty functions that satisfy certain properties. In
1 Although the global convergence rate in terms of augmented dual objective can be easily shown from existing works (e.g.,
see our discussion in section 5), that does not indicate the convergence speed from the perspective of the primal objective and
feasibility.
2 By “simple”, we mean the proximal mapping of h is easy to evaluate, i.e., it is easy to find a solution to min
x∈X h(x) +
1
kx − x̂k2 for any x̂ and γ > 0.
2γ

Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming

3

this paper, we use the classic one. As discussed below, it can be derived from a quadratic penalty on an
equivalent equality constrained problem.
Introducing nonnegative slack variable si ’s, one can write (1) to an equivalent form:
minimize f0 (x), s.t. Ax = b, fi (x) + si = 0, i = 1, . . . , m.
x∈X ,s≥0

(4)

With quadratic penalty on the equality constraints, the AL function of (4) is
L̃β (x, s, y, z) = f0 (x) + y⊤ (Ax − b) +

m
2
 β
βX
fi (x) + si ,
zi fi (x) + si + kAx − bk2 +
2
2 i=1
i=1

m
X

where y and z are multipliers, and β is the augmented penalty parameter. Minimizing L̃β with respect to
s ≥ 0 while fixing x, y and z, we have the optimal s given by


zi
si = − − fi (x) , i = 1, . . . , m.
β
+
Plugging the above s into L̃β gives
m

L̃β (x, s, y, z) = f0 (x) + y⊤ (Ax − b) +
where
ψβ (u, v) =


 uv + β2 u2 , if βu + v ≥ 0,
 − v2 ,
2β

Let

X
β
ψβ (fi (x), zi ),
kAx − bk2 +
2
i=1

Ψβ (x, z) =

m
X

if βu + v < 0.

(5)

ψβ (fi (x), zi ),

i=1

and we obtain the classical AL function of (1):

Lβ (x, y, z) = f0 (x) + y⊤ (Ax − b) +

β
kAx − bk2 + Ψβ (x, z).
2

(6)

1.2 Inexact augmented Lagrangian method
The augmented Lagrangian method (ALM) was proposed in [16,29]. Within each iteration, ALM first updates
the x variable by minimizing the AL function with respect to x while fixing y and z, and then it performs a
dual gradient ascent update to y and z. In general, it is difficult to exactly minimize the AL function about
x. A more realistic way is to solve the x-subproblem within a tolerance error, which leads to the inexact
ALM. Its pseudocode is given in Algorithm 1 below. If εk = 0, ∀k, it reduces to the ALM.
It is shown in [30] that the augmented dual function3 dβ (y, z) = minx∈X Lβ (x, y, z) is continuously
differentiable, and ∇dβ is Lipschitz continuous with constant β1 . In addition, it turns out that the (inexact)
3

Although [30] only considers the inequality constrained case, the results derived there apply to the case with both equality
and inequality constraints.

4

Yangyang Xu

Algorithm 1: Inexact augmented Lagrangian method for (1)
1
2
3

Initialization: choose x0 , y0 , z0 and {βk , ρk }
for k = 0, 1, . . . do
Find xk+1 ∈ X such that
Lβk (xk+1 , yk , zk ) ≤ min Lβk (x, yk , zk ) + εk .

(7)

x∈X

4

Update y and z by
yk+1 = yk + ρk (Axk+1 − b),
zik+1 = zik + ρk · max

(8)

!
zik
k+1
− , fi (x
) , i = 1, . . . , m.
βk

(9)

ALM is an (inexact) augmented dual gradient ascent [31], and thus convergence rate of the (inexact) ALM
in term of dβ can be shown from existing results about (inexact) gradient method [33]. However, it is unclear
from there how to get convergence rate result from the perspective of the primal problem, especially as β
varies at different updates. Our analysis will be different from this line, and our results will be based on the
primal problem. In addition, our requirement on the tolerance errors is weaker than that in [31].
The main results we establish in this paper are summarized as follows. Both ergodic and nonergodic
convergence rate results are established.
Theorem 1 (Summary of main results) For a given ε > 0, choose a positive integer K and numbers Cβ > 0, Cε > 0. Let {(xk , yk , zk )}K
k=0 be the iterates generated from Algorithm 1 with parameters set
according to one of the follows:
1. ρk = βk =

Cβ
ε Cε
Kε , εk = 2 Cβ , ∀k.
βg σ k , ∀k for certain

C

PK−1

Cε
βk = εβ , and εk = 2ε C
, ∀k.
β
P
Cβ
K−1
k
3. ρk = βk = βg σ , ∀k for certain βg > 0 and σ > 1 such that
k=0 βk = ε . If f0 is convex, let
Cε
Cε
1
1
,
∀k,
and
if
f
is
strongly
convex,
let
ε
=
εk = 1 P
1 P
2
1 , ∀k
0
k

2. ρk = βk =

2βk3

K−1
t=0

βg > 0 and σ > 1 such that

βt3

Then the averaged point x̄K =

k=0

2βk2

ρk xk+1
k=0 PK−1 ρt

PK−1

K−1
t=0

βt2

is an O(ε)-optimal solution (see Definition 1), where the

t=0

hidden constant depends on Cβ , Cε and dual solution (y∗ , z∗ ), and for the second and third settings, the
actual point xK is also an O(ε)-optimal solution. In addition, the total number of evaluations on ∇g and
1
∇fi , i = 1, . . . , m is O(ε−1 ) if f0 is convex and O(ε− 2 | log ε|) if f0 is strongly convex.
The formal statement and the hidden constants are shown in Theorem 5 for the first setting, in Theorems
6 and 9 for the second setting, and in Theorems 7 and 9 for the third setting.

1.3 Contributions
The contributions of this paper are mainly on establishing global convergence rate and estimating iteration
complexity of iALM for solving (1), in both ergodic and nonergodic sense. They are listed as follows.

Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming

5

– We first establish an ergodic convergence rate result of iALM through a novel analysis. With penalty
parameters fixed to constant or increased geometrically, we choose the tolerance errors accordingly. By
applying Nesterov’s optimal first-order method to each x-subproblem, we show that to reach an ε-optimal
solution, O(ε−1 ) gradient evaluations are sufficient if the objective is convex, and the order is improved
1
to O(ε− 2 | log ε|) if the objective is strongly convex. For the convex case, the result is optimal, and for
the strongly convex, the result also appears the best compared to existing ones in the literature; see the
discussions in Remark 2.
– We note that if iALM only runs to one iteration, i.e., a single x-subproblem (7) is solved, then the algorithm reduces to the penalty method by setting initial multipliers to zero vectors. Hence, as a byproduct,
we establish the iteration complexity result of the penalty method for solving (1). The work [19] analyzes first-order penalty method for solving affinely constrained problems. To have an ε-optimal solution,
O(ε−2 ) gradient evaluations are required, if the penalty method is applied to the original problem, and
O(ε−1 | log ε|) gradient evaluations are required if the penalty method is applied to a carefully perturbed
problem. Hence, our result is better than the former case by an order O(ε−1 ) and the latter case by
O(| log ε|).
– By relating to inexact proximal point algorithm (iPPA), we then establish a nonergodic convergence rate
result of iALM through applying existing results in [32] about iALM. We show that with geometrically
increasing penalty parameters, the nonergodic convergence of iALM enjoys the same order as that of
the ergodic convergence, and the constant is just a few times larger. Compared to one recent nonergodic
convergence result [21] for solving affinely constrained problem, our result is better by an order O(ε−3 ).
1.4 Notation
For simplicity, throughout the paper, we focus on a finite-dimensional Euclidean space, but our analysis can
be directly extended to a general Hilbert space.
We use italic letters a, c, B, L, . . . , for scalars, bold lower-case letters x, y, z, . . . for vectors, and bold
upper-case letters A, B, . . . for matrices. zi denotes the i-th entry of a vector z. We use 0 to denote a vector
of all zeros, and its size is clear from the context. [m] denotes the set {1, 2, . . . , m} for any positive integer
m. Given a real number a, we let [a]+ = max(0, a) and ⌈a⌉ be the smallest integer that is no less than a. For
a vector a, [a]+ takes the positive part of a in a component-wise manner. kak denotes the Euclidean norm
of a vector a and kAk the spectral norm of a matrix A.
We denote ℓ as the vector consisting of Li , i ∈ [m], where Li is the Lipschitz constant of ∇fi in (3b).
Also we let f be the vector function with fi as the i-th component scalar function. That is
ℓ = [L1 , . . . , Lm ],

f (x) = [f1 (x), . . . , fm (x)].

(10)

˜ (x) represents one subgradient of f at x, namely,
Given a convex function f , ∇f
˜ (x), x̂ − xi, ∀ x̂,
f (x̂) ≥ f (x) + h∇f
and ∂f (x) denotes its subdifferential, i.e., the set of all subgradients. When f is differentiable, we simply
write its subgradient as ∇f (x). For a convex set X , we use ιX as its indicator function, i.e.,

0,
if x ∈ X ,
ιX (x) =
+∞, if x 6∈ X ,
and NX (x) = ∂ιX (x) as its normal cone at x ∈ X .
Given an ε > 0, the ε-optimal solution of (1) is defined as follows.

6

Yangyang Xu

Definition 1 (ε-optimal solution) Let f0∗ be the optimal value of (1). Given ε ≥ 0, a point x ∈ X is
called an ε-optimal solution to (1) if
|f0 (x) − f0∗ | ≤ ε, and kAx − bk + [f (x)]+ ≤ ε.
1.5 Outline
The rest of the paper is organized as follows. In section 2, we give a few preparatory results and review
Nesterov’s optimal first-order method for solving a composite convex program. An ergodic convergence rate
result of iALM is given in section 3, and a nonergodic convergence rate result is shown in section 4. Iteration
complexity results in terms of the number of gradient evaluations are established for both ergodic and
nonergodic cases. Related works are reviewed and compared in section 5, and numerical results are provided
in section 6. Finally section 7 concludes the paper.
2 Preliminary results and Nesterov’s optimal first-order method
In this section, we give a few preliminary results and also review Nesterov’s optimal first-order method for
composite convex programs.
2.1 Basic facts
A point (x, y, z) satisfies the Karush-Kuhn-Tucker (KKT) conditions for (1) if
0 ∈ ∂f0 (x) + NX (x) + A⊤ y +

m
X

zi ∇fi (x),

(11a)

x ∈ X,

(11b)

zi∗ fi (x) ≥ 0, ∀ x ∈ X .

(12)

i=1

Ax = b,
zi ≥ 0,

fi (x) ≤ 0,

zi fi (x) = 0, ∀i ∈ [m].

(11c)

From the convexity of fi ’s, if (x∗ , y∗ , z∗ ) is a KKT point, then
f0 (x) − f0 (x∗ ) + hy∗ , Ax − bi +

m
X
i=1

The result below will be used to establish convergence rate of Algorithm 1.
Lemma 1 Assume (x∗ , y∗ , z∗ ) satisfies the KKT conditions in (11). Let x̄ be a point such that for any y
and any z ≥ 0,
m
X
zi fi (x̄) ≤ α + c1 kyk2 + c2 kzk2 ,
(13)
f0 (x̄) − f0 (x∗ ) + y⊤ (Ax̄ − b) +
i=1

where α and c1 , c2 are nonnegative constants independent of y and z. Then

− α + 4c1 ky∗ k2 + 4c2 kz∗ k2 ≤ f0 (x̄) − f0 (x∗ ) ≤ α,
2
2
kAx̄ − bk + [f (x̄)]+ ≤ α + c1 1 + ky∗ k + c2 1 + kz∗ k .

(14)
(15)

Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming

7

Proof. Letting y = 0 and z = 0 in (13) gives the second inequality in (14). For any nonnegative γy and γz ,
we let
Ax̄ − b
[f (x̄)]+
y = γy
, z = γz
kAx̄ − bk
[f (x̄)]+
and have from (13) by using the convention

0
0

= 0 that

f0 (x̄) − f0 (x∗ ) + γy kAx̄ − bk + γz [f (x̄)]+ ≤ α + c1 γy2 + c2 γz2 .
Noting
− hy∗ , Ax̄ − bi ≥ −ky∗ k · kAx̄ − bk,
we have from (12) and (16) that

−

m
X
i=1

zi∗ fi (x̄) ≥ −kz∗ k · [f (x̄)]+ ,

(16)

(17)

(γy − ky∗ k)kAx̄ − bk + (γz − kz∗ k)k[f (x̄)]+ ≤ α + c1 γy2 + c2 γz2
In the above inequality, letting γy = 1 + ky∗ k and γz = 1 + kz∗ k gives (15), and letting γy = 2ky∗ k and
γz = 2kz∗ k gives the first inequality in (14) by (12) and (17).

2.2 Nesterov’s optimal first-order method
In this subsection, we review Nesterov’s optimal first-order method for composite convex programs. The
method will be used to approximately solve x-subproblems in Algorithm 1. It aims at finding a solution of
the following problem
minimize φ(x) + ψ(x),
(18)
x

where φ is a Lipschitz differentiable and strongly convex function with gradient Lipschitz constant Lφ and
strong convexity modulus µ ≥ 0, and ψ is a simple (possibly nondifferentiable) closed convex function.
Algorithm 2 summarizes the method. Here, for simplicity, we assume Lφ and µ are known. The method does
not require the value of Lφ but can estimate it by backtracking. In addition, it only requires a lower estimate
of µ; see [27] for example.
The theorem below gives the convergence rate of Algorithm 2 for both convex (i.e., µ = 0) and strongly
convex (i.e., µ > 0) cases; see [1, 26, 27]. We will use the results to estimate iteration complexity of iALM.
Theorem 2 Let {xk } be the sequence generated from Algorithm 2. Assume x∗ to be a minimizer of (18).
The following results holds:
1. If µ = 0 and α0 = 1, then
φ(xk ) + ψ(xk ) − φ(x∗ ) − ψ(x∗ ) ≤
2. If µ > 0 and α0 =

q

µ
Lφ ,

2Lφ kx0 − x∗ k2
, ∀k ≥ 1.
k2

(19)

then

φ(xk ) − φ(x∗ ) ≤

(Lφ + µ)kx0 − x∗ k2
2


r k
µ
1−
, ∀k ≥ 1.
Lφ

(20)

8

Yangyang Xu

Algorithm 2: Nesterov’s optimal first-order method for (18)
1
2
3

Initialization: choose x̂0 = x0 , α0 ∈ (0, 1], and let q =

µ
Lφ

;

for k = 0, 1, . . . , do
Let
xk+1 = arg minh∇φ(x̂k ), xi +
x

4

Lφ
kx − x̂k k2 + ψ(x).
2

Set
αk+1 =

q − α2k +

and
x̂k+1 = xk+1 +

q

(q − α2k )2 + 4α2k
2

,

αk (1 − αk ) k+1
(x
− xk ).
α2k + αk+1

3 Ergodic convergence rate and iteration complexity results
In this section, we first establish an ergodic convergence rate result of Algorithm 1. From that result, we then
specify algorithm parameters and estimate the total number of gradient evaluations in order to produce an εoptimal solution. Two different settings of the penalty parameters are studied: one with constant penalty and
another with geometrically increasing penalty parameters. For each setting, the tolerance error parameter
εk is chosen in an “optimal” way so that the total number of gradient evaluation is minimized.
Throughout this section, we make the following assumptions.
Assumption 1 There exists a point (x∗ , y∗ , z∗ ) satisfying the KKT conditions in (11).
Assumption 2 For every k, there is xk+1 satisfying (7).
The first assumption holds if a certain regularity condition is satisfied, such as the Slater condition
(namely, there is an interior point x of X such that Ax = b and fi (x) < 0, ∀i ∈ [m]). The second assumption
is for the well-definedness of the algorithm. It holds if X is compact and fi ’s are continuous.
3.1 Convergence rate analysis of iALM
To show the convergence results of Algorithm 1, we first establish a few lemmas.
Lemma 2 Let y and z be updated by (8) and (9) respectively. Then for any k, it holds

1  k+1
ky
− yk2 − kyk − yk2 + kyk+1 − yk k2 − hyk+1 − y, rk+1 i = 0,
2ρk
m


 X
zk
1
(zik+1 − zi ) · max − i , fi (xk+1 ) = 0,
kzk+1 − zk2 − kzk − zk2 + kzk+1 − zk k2 −
2ρk
βk
i=1

(21)
(22)

where rk = Axk − b.
Proof. Using the equality 2u⊤ v = kuk2 − ku − vk2 + kvk2 , we have the results from the updates (8) and (9).


Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming

9

Lemma 3 For any z ≥ 0, we have
m
X
i=1

≥

m
X


zk
(zik+1 − zi ) · max − i , fi (xk+1 )
[zik + βk fi (xk+1 )]+ − zi fi (xk+1 ) −
β
k
i=1

1
(βk − ρk )kzk+1 − zk k2 .
ρ2k

(23)

Proof. Denote
k
I+
= {i ∈ [m] : zik + βk fi (xk+1 ) ≥ 0},

Then

k
k
I−
= [m]\I+
.

(24)

the left hand side of (23)
X


(zik − zi )fi (xk+1 ) + βk [fi (xk+1 )]2 − zik + ρk fi (xk+1 ) − zi fi (xk+1 )
=
k
i∈I+

+

X

k
i∈I−

−zi fi (x

=(βk − ρk )
≥(βk − ρk )
=

k+1

)−

zik

X

[fi (xk+1 )]2 +

X

[fi (xk+1 )]2 +

k
i∈I+



ρk zik
zik 
−
− zi −
βk
βk
X

k
i∈I−

k
i∈I+

−zi fi (xk+1 ) +

X
1
(βk − ρk )
(zik )2
2
βk
k

zik 
1
+ 2 (βk − ρk )(zik )2
βk
βk



i∈I−

1
(βk − ρk )kzk+1 − zk k2 ,
ρ2k

where the inequality follows from zi ≥ 0 and fi (xk+1 ) +
the update (9).

zik
βk

k
≤ 0, ∀i ∈ I−
, and the last equality holds due to


The next theorem is a fundamental result by running one iteration of Algorithm 1.
Theorem 3 (One-iteration progress of iALM) Let {(xk , yk , zk )} be the sequence generated from Algorithm 1. Then for any x ∈ X such that Ax = b and fi (x) ≤ 0, ∀i ∈ [m], any y, and any z ≥ 0, it holds
that
f0 (xk+1 ) − f0 (x) + y⊤ rk+1 +

m
X

zi fi (xk+1 ) +

i=1

βk − ρk k+1 2
kr
k
2

βk − ρk k+1
1
1
+
kyk+1 − yk2 +
kzk+1 − zk2
kz
− zk k2 +
2
2ρk
2ρk
2ρk
1
1
kyk − yk2 +
kzk − zk2 + εk .
≤
2ρk
2ρk

(25)

Proof. From (7), it follows that for any x such that Ax = b,
f0 (xk+1 ) + hyk , rk+1 i +

βk k+1 2
kr
k + Ψβk (xk+1 , zk ) − f0 (x) − Ψβk (x, zk ) ≤ εk .
2

(26)

10

Yangyang Xu

Since hyk , rk+1 i = hyk+1 − y, rk+1 i + hy, rk+1 i − ρk krk+1 k2 , by adding (21) and (22) to the above inequality,
we have
f0 (xk+1 ) − f0 (x) + y⊤ rk+1 +

m
X

zi fi (xk+1 ) +

m
X
i=1

i=1

m


[zik + βk fi (xk+1 )]+ − zi fi (xk+1 )

X

βk
+
[zik + βk fi (xk+1 )]+ fi (xk+1 ) − Ψβk (x, zk )
− ρk krk+1 k2 + Ψβk (xk+1 , zk ) −
2
i=1


1  k+1
ky
− yk2 − kyk − yk2 + kyk+1 − yk k2
2ρk
m

 X
zk
1  k+1
(zik+1 − zi ) · max − i , fi (xk+1 )
kz
− zk2 − kzk − zk2 + kzk+1 − zk k2 −
+
2ρk
βk
i=1
+

≤εk .

(27)

Note that
Ψβk (xk+1 , zk ) −
=

X

m
X
i=1

zik fi (xk+1 )

k
i∈I+

[zik + βk fi (xk+1 )]+ fi (xk+1 )


 X
βk
(zik )2
k+1 2
k
k+1
k+1
+
[fi (x
)] − [zi + βk fi (x
)]fi (x
) +
−
2
2βk
k
i∈I−

X (z k )2
X βk
i
[fi (xk+1 )]2 −
=−
2
2βk
k
k
i∈I+

=−

i∈I−

βk k+1
kz
− zk k2 ,
2ρ2z

(28)

k
k
where the sets I+
and I−
are defined in (24). In addition, if fi (x) ≤ 0, ∀i ∈ [m], then Ψβk (x, zk ) ≤ 0. Hence,
plugging (23) and (28) into (27) yields (25).


By Lemma 1 and Theorem 3, we have the following convergence rate estimate of Algorithm 1.
Theorem 4 (Ergodic convergence rate of iALM) Under Assumptions 1 and 2, let {(xk , yk , zk )} be
the sequence generated from Algorithm 1 with y0 = 0, z0 = 0 and 0 < ρk ≤ βk , ∀k. Then
!
K−1
X
1
K
∗
∗ 2
∗ 2
f0 (x̄ ) − f0 (x ) ≤ PK−1
(29a)
2ky k + 2kz k +
ρk ε k ,
t=0 ρt
k=0
!
K−1
X
(1 + ky∗ k)2
1
(k1 + kz∗ k)2
K
K
(29b)
kAx̄ − bk + [f (x̄ )]+ ≤ PK−1
ρk ε k ,
+
+
2
2
t=0 ρt
k=0

where

K

x̄

=

PK−1

t+1
t=0 ρt x
.
PK−1
t=0 ρt

(30)

Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming
k
Proof. Since ρk ≤ βk , the two terms βk −ρ
krk+1 k2 and
2
and multiplying ρk to both sides of (25) yields

"

k+1

ρk f0 (x

⊤ k+1

) − f0 (x) + y r

+

m
X

βk −ρk
kzk+1
2ρ2k

k+1

zi fi (x

i=1

1
1
≤ kyk − yk2 + kzk − zk2 + ρk εk .
2
2

11

− zk k2 are nonnegative. Dropping them

#

1
1
) + kyk+1 − yk2 + kzk+1 − zk2
2
2
(31)

Summing up (25) with x = x∗ gives
K−1
X
k=0

"

k+1

ρk f0 (x

∗

⊤ k+1

) − f0 (x ) + y r

1
1
≤ ky0 − yk2 + kz0 − zk2 +
2
2

K−1
X

+

m
X

k+1

zi fi (x

i=1

#

1
1
) + kyK − yk2 + kzK − zk2
2
2

ρk ε k .

(32)

k=0

By the convexity of fi ’s and the nonnegativity of z, we have
K

∗

⊤

K

f0 (x̄ ) − f0 (x ) + y (Ax̄ − b) +
1

≤ PK−1
t=0

ρt

K−1
X
k=0

"

k+1

ρk f0 (x

∗

m
X

zi fi (x̄K )

i=1

⊤ k+1

) − f0 (x ) + y r

+

m
X

k+1

zi fi (x

i=1

#

) ,

which together with (32) implies

K

∗

⊤

K

f0 (x̄ ) − f0 (x ) + y (Ax̄ − b) +

m
X
i=1

The results thus follow from Lemma 1 with

K

1

zi fi (x̄ ) ≤ PK−1
t=0

ρt

K−1
X
1
1
kyk2 + kzk2 +
ρk ε k
2
2

PK−1
ρk ε k
1
1
, c1 = PK−1 , c2 = PK−1 ,
α = Pk=0
K−1
ρ
2
ρ
2
k=0 k
k=0 k
k=0 ρk

and we complete the proof.

k=0

!

.



Remark 1 Note that if ρk ≡ ρ > 0, ∀k and {εk } is summable, then a sublinear convergence result follows from
the convergence of Algorithm 1 through the augmented
(29). The work [31] has also
P∞analyzed
P∞ dual function
√
dβ . However, it requires k=1 εk < ∞, which is strictly stronger than the condition k=1 εk < ∞.

12

Yangyang Xu

3.2 Iteration complexity of iALM
In this subsection, we apply Nesterov’s optimal first-order method to each x-subproblem (7) and estimate
the total number of gradient evaluations to produce an ε-optimal solution of (1). Note that the convergence
rate results in Theorem 4 do not assume specific structures of (1) except convexity. If the problem (1) has
richer structures than those in (3), more efficient methods can be applied to the subproblems in (7).
The following results are easy to show from the Lipschitz differentiability of g and fi , i ∈ [m].
Proposition 1 Assume (3a), (3b), and the boundedness of dom(h)∩X . Then there exist constants B1 , . . . , Bm
such that

max |fi (x)|, k∇fi (x)k ≤ Bi , ∀x ∈ dom(h) ∩ X , ∀i ∈ [m],
|fi (x̂) − fi (x̃)| ≤ Bi kx̂ − x̃k, ∀x̂, x̃ ∈ dom(h) ∩ X , ∀i ∈ [m].

(33a)
(33b)

Let the smooth part of Lβ be denoted as
Fβ (x, y, z) = Lβ (x, y, z) − h(x).
Based on (33), we are able to show Lipschitz continuity of ∇x Fβ (x, y, z) with respect to x for every (y, z).
Lemma 4 Assume (3a), (3b), and the boundedness of dom(h) ∩ X . Let Bi ’s be given in Proposition 1. Then
∇x Fβk (x, yk , zk ) is Lipschitz continuous on dom(h) ∩ X in terms of x with constant
L(zk ) = L0 + βk kA⊤ Ak +

m
X
i=1


βk Bi (Bi + Li ) + Li |zik | .

(34)

Proof. For ease of description, we let β = βk and (y, z) = (yk , zk ) in the proof. First we notice that
∂
∂u ψβ (u, v) = [βu + v]+ , and thus for any v,
∂
∂
ψβ (û, v) −
ψβ (ũ, v) ≤ β|û − ũ|, ∀û, ũ.
∂u
∂u
Let hi (x, zi ) = ψβ (fi (x), zi ), i = 1, . . . , m. Then
k∇x hi (x̂, zi ) − ∇x hi (x̃, zi )k
∂
∂
=
ψβ (fi (x̂), zi )∇fi (x̂) −
ψβ (fi (x̃), zi )∇fi (x̃)
∂u
∂u
∂
∂
ψβ (fi (x̂), zi )∇fi (x̂) −
ψβ (fi (x̃), zi )∇fi (x̂)
≤
∂u
∂u
∂
∂
ψβ (fi (x̃), zi )∇fi (x̂) −
ψβ (fi (x̃), zi )∇fi (x̃)
+
∂u
∂u
∂
ψβ (fi (x̃), zi ) · k∇fi (x̂) − ∇fi (x̃)k
≤β|fi (x̂) − fi (x̃)| · k∇fi (x̂)k +
∂u
≤βBi2 kx̂ − x̃k + Li (βBi + |zi |)kx̂ − x̃k.

Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming

13

Hence,
k∇x Fβ (x̂, y, z) − ∇x Fβ (x̃, y, z)k
≤k∇g(x̂) − ∇g(x̃)k + βkA⊤ A(x̂ − x̃)k +
⊤

≤ L0 + βkA Ak +

m
X

i=1

βBi2

m
X
i=1

k∇x hi (x̂, zi ) − ∇x hi (x̃, zi )k

!

+ Li (βBi + |zi |) kx̂ − x̃k,


which completes the proof.

Therefore, letting φ(x) = Fβk (x, yk , zk ) and ψ(x) = h(x) + ιX (x), we can apply Nesterov’s optimal
first-order method in Algorithm 2 to find xk+1 in (7). From Theorem 2, we have the following results. Note
that if the strong convexity constant µ = 0, the problem is just convex.
Lemma 5 Assume that g is strongly convex with modulus µ ≥ 0. Given εk > 0, if we start from xk and run
Algorithm 2, then at most tk iterations are needed to produce xk+1 such that (7) holds, where
'
&
p
k
∗
k)

dist(x
,
X
)
2L(z


,
if µ = 0,
√k


εk


 k

tk = 
L(z )+µ
k
∗ 2

log
[dist(x
,
X
)]

k
2εk

 , if µ > 0,


q




µ



log 1/ 1 −
k

(35)

L(z )

and Xk∗ denotes the set of optimal solutions to minx∈X Lβk (x, yk , zk ).

Below we specify the sequences {βk }, {ρk } and {εk } for a given ε > 0, and through combining Theorem 4
and Lemma 5, we give the iteration complexity results of iALM for producing an ε-optimal solution. We study
two cases. In the first case, a constant penalty parameter is used, and in the second case, we geometrically
increase βk and ρk .
Given ε > 0, we set {βk } and {ρk } according to one of the follows:
Setting 1 (constant penalty) Let K be a positive integer number and Cβ a positive real number. Set
ρk = βk =

Cβ
, ∀ 0 ≤ k < K.
Kε

Setting 2 (geometrically increasing penalty) Let K be a positive integer number, Cβ a positive real
number, and σ > 1. Set
Cβ σ − 1
,
(36)
βg =
ε σK − 1

and

ρk = βk = βg σ k , ∀ 0 ≤ k < K.

14

Yangyang Xu

Note that if K = 1, the above two settings are the same, and in this case, P
Algorithm 1 simply reduces to
C
K−1
the quadratic penalty method. For either of the above two settings, we have k=0 ρk = εβ .
k
From (34), we see that the Lipschitz constant depends on z . Hence, from (35), to solve the x-subproblem
to the accuracy εk , the number of gradient evaluations will depend on zk . Below we show that if εk is
sufficiently small, zk can be bounded and thus so is L(zk ).
Lemma 6 Let {(xk , yk , zk )}K
k=0 be the sequence generated from Algorithm 1 with {βk } and {ρk } set according to either Setting 1 or Setting 2. If y0 = 0, z0 = 0, and εk ’s are chosen such that
K−1
X
k=0

ρk ε k ≤

Cε
,
2

(37)

then
L(zk ) ≤ L∗ + βk H, ∀ 0 ≤ k ≤ K,
where
H = kA⊤ Ak +
and ℓ is given in (10).

m
X
i=1

(38)


p 
Bi (Bi + Li ), L∗ = L0 + kℓk ky∗ k + 2kz∗ k + Cε

Proof. Letting (x, y, z) = (x∗ , y∗ , z∗ ) in (31) and using (12), we have
1
1
1
1 k+1
ky
− y∗ k2 + kzk+1 − z∗ k2 ≤ kyk − y∗ k2 + kzk − z∗ k2 + ρk εk .
2
2
2
2
Summing the above inequality yields
k−1
X
1 k
1
1
1
ky − y∗ k2 + kzk − z∗ k2 ≤ ky0 − y∗ k2 + kz0 − z∗ k2 +
ρt εt , ∀ 0 ≤ k ≤ K,
2
2
2
2
t=0

which implies
v
u
k−1
u
X
k
∗
kz k ≤ kz k + tky0 − y∗ k2 + kz0 − z∗ k2 + 2
ρt ε t .
t=0

Since kuk ≤ kuk1 for any vector u, we have from the above inequality that
v
u K−1
u X
k
∗
0
∗
0
∗
kz k ≤ kz k + ky − y k + kz − z k + t2
ρt εt , ∀ 0 ≤ k ≤ K.

(39)

t=0

Hence, if y0 = 0 and z0 = 0, and (37) holds, it follows from the above inequality that
p
kzk k ≤ ky∗ k + 2kz∗ k + Cε , ∀ 0 ≤ k ≤ K,

By the Cauchy-Schwartz inequality, we have from (34) that for any 0 ≤ k ≤ K,
L(zk ) ≤ L0 + βk H + kzk k · kℓk

(40)

Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming

15

which together with (40) gives the result in (38).



“Optimal” subproblem accuracy parameters. If tk gradient
PK−1 evaluations are required to produce
xk+1 , then the total number of gradient evaluations is TK = k=0 tk to generate {xk }K
k=1 . Given ε > 0,
and {βk },{ρk } set according to either Setting 1 or Setting 2, we can choose {εk } to minimize TK subject to
the condition in (37).
When µ = 0, we solve the following problem:
p
K−1
K−1
X
X dist(xk , X ∗ ) L(zk )
Cε
k
, s.t.
βk ε k ≤
,
minimize
√
ε>0
εk
2
k=0

k=0

where ε = [ε0 , . . . , εK−1 ]. Through formulating the KKT system of the above problem, one can easily find
the optimal ε given by
1

2

εk =

Cε
[dist(xk , Xk∗ )] 3 [L(zk )] 3
, ∀ 0 ≤ k < K.
2 P
2 β 3 K−1 β 13 [dist(xt , X ∗ )] 32 [L(zt )] 13
k

t=0

t

(41)

t

When µ > 0, we solve the problem below:
s


K−1
K−1
X
X L(zk )
Cε
L(zk ) + µ
k
∗ 2
βk ε k ≤
[dist(x , Xk )] , s.t.
log
,
minimize
ε>0
µ
2εk
2

(42)

k=0

k=0

whose optimal solution is given by
p
L(zk )
Cε
εk =
, ∀ 0 ≤ k < K.
PK−1 p
2 βk t=0
L(zt )

(43)

Note that the summand in the objective of (42) is not exactly the same as that in the second inequality of
(35). They are close if µ ≪ L(zk ) since log(1 + a) = a + o(a).
The optimal εk given in (41) and (43) depends on dist(xk , Xk∗ ) and the future points zk+1 , . . . , zK−1 ,
which are unknown at iteration k. We do not assume these unknowns. Instead, we set εk in two different
ways. One way is to simply set
ε Cε
, ∀ 0 ≤ k < K,
(44)
εk =
2 Cβ
for both cases of µ = 0 and µ > 0. Another way is to let
εk =

1
Cε
2 , ∀ 0 ≤ k < K,
1 P
K−1
2 β3
β3
k

for the case of µ = 0, and
εk =

t=0

(45)

t

Cε
1
√ , ∀ 0 ≤ k < K,
√ P
2 βk K−1
βt
t=0

(46)

for the case of µ > 0. We see that if βk H dominates L∗ and dist(xk , Xk∗ ) is roughly the same for all k’s, then
{εk } in (45) and (46) well approximate those in (41) and (43). If {βk } and {ρk } are set according to Setting
1, i.e., constant parameters, then the {εk } in both (45) and (46) is constant as in (44).
Plugging these parameters into (35), we have the following estimates on the total number of gradient
evaluations.

16

Yangyang Xu

Theorem 5 (Iteration complexity with constant penalty and constant error) For any given ε > 0,
let K be a positive integer number and Cβ , Cε two positive real numbers. Set {βk } and {ρk } according to
Setting 1 and {εk } by (44). Let x̄K be given in (30). Then

ε 2ky∗ k2 + 2kz∗ k2
ε Cε
K
∗
+
,
(47a)
f0 (x̄ ) − f0 (x ) ≤
Cβ
2 Cβ


ε (1 + ky∗ k)2 + (1 + kz∗ k)2
ε Cε
K
K
kAx̄ − bk + [f (x̄ )]+ ≤
+
.
(47b)
2Cβ
2 Cβ
Assume µ ≤
times, where

L0
4 .

Then Algorithm 1 can produce x̄K by evaluating gradients of g, fi , i ∈ [m] in at most TK
&

TK ≤ 2DK

r

Cβ
Cε

r

1
L∗
+
ε
ε

log



r

Cβ H
K

!

'

+ K , if µ = 0,

(48)

and
&

TK ≤ 2K

s

L∗
+
µ

s

Cβ H
µKε

!

'

D2 Cβ L∗ + µ Cβ H 
+
+ K , if µ > 0.
Cε
ε
Kε2

(49)

Proof. The results in (47) directly follows from Theorem 4 and the settings of {βk }, {ρk }, and {εk }. For the
total number of gradient evaluations, we use the inequalities in (35). First, for the case of µ = 0, from the
first inequality of (35) and the parameter setting, it follows that the total number of gradient evaluations
q
βH
K−1
X dist(xk , Xk∗ ) 2(L∗ + CKε
)
p p
TK ≤
+ K.
(50)
ε/2 Cε /Cβ
k=0

√
√
√
Since a + b ≤ a + b for any two nonnegative numbers a, b, we have from the above inequality and by
noting dist(xk , Xk∗ ) ≤ D that
q
!
√
r
r
r
r
Cβ H
K−1
X
+
L
∗
1 Cβ H
Cβ
Cβ
L∗
Kε
√
TK ≤ 2D
+ K,
+
+ K = 2DK
Cε
Cε
ε
ε
K
ε
k=0

which gives (48).
For the case of µ > 0, we first note that for any 0 < a ≤ 1, it holds log(1 + a) ≥ a −
√
µ/L(zk )
L(zk )
L0
µ ≤ 4 , we have µ ≤ 4 and √
≤ 1. Therefore,
k
1−

a2
2

≥ a2 . Hence, if

µ/L(z )

!
p
p
µ/L(zk )
µ/L(zk )
1
p
p
p
= log 1 +
≥
,
log
2 1 − µ/L(zk )
1 − µ/L(zk )
1 − µ/L(zk )
1

and thus

log

1−

1
√1

µ/L(zk )

≤2

s

L(zk )
µ

s


q
L(zk )
1 − µ/L(zk ) ≤ 2
.
µ

(51)

Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming

17

Using the above inequality and the second inequality of (35), we have that the total number of gradient
evaluations
s
!
K−1
Cβ H
Cβ H
X
+µ
L∗ + Kε
L∗ + Kε
k
∗ 2
TK ≤
2
[dist(x , Xk )] + K.
(52)
log
µ
εCε /Cβ
k=0
q
q
√
Cβ H
Cβ H
k
∗
Since L∗ + Kε
≤ L∗ +
Kε and dist(x , Xk ) ≤ D, the above inequality implies (49). This completes
the proof.

We make two observations below about the results in Theorem 5.
Remark 2 From the error bounds in (47), we see that if

2Cβ ≥ max 4ky∗ k2 + 4kz∗ k2 , (1 + ky∗ k)2 + (1 + kz∗ k)2 + Cε ,

(53)

then x̄K is an ε-optimal solution. Otherwise, the errors in (47) are multiples of ε. If we represent ε by the
total number t of gradient evaluations, we can obtain the convergence rate result interms of t. Let Cβ= Cε
q
p
L∗
1
and K = 1 in (48). Then the total number of gradient evaluations is about t = 2D
Cβ H . By
ε + ε

quadratic formula, one can easily show that

ε=

q
 √
2
p
D L∗ + L∗ D2 + 2Dt Cβ H
t2

p
4D Cβ H
4L∗ D2
≤
+
.
t2
t

Let x̂t = x̄K to specify the dependence of the iterate on the number of gradient evaluations. Plugging the
above ε into (47), we have
!
p


4D Cβ H
2ky∗ k2 + 2kz∗ k2
4L∗ D2
1
t
∗
f0 (x̂ ) − f0 (x ) ≤
,
(54a)
+
+
Cβ
2
t2
t
!
p


4D Cβ H
4L∗ D2
1
(1 + ky∗ k)2 + (1 + kz∗ k)2
t
t
.
(54b)
+
+
kAx̂ − bk + [f (x̂ )]+ ≤
2Cβ
2
t2
t
If there are no equality or inequality constraints, then H = 0, y∗ = 0, z∗ = 0, and the rate of convergence in
(54a) matches with the optimal one in (19); if the objective f0 (x) ≡ 0 and there are no inequality constraints,
then H = kA⊤ Ak, y∗ = 0, z∗ = 0, L∗ = 0, and the rate of convergence with Cβ = 2 in (54b) roughly becomes
√
8 2D2 kA⊤ Ak
t
2
kAx̂ − bk ≤
,
t2
whose order is also optimal. Therefore, the order of convergence rate in (54) is optimal, and so is the iteration
complexity result in (48).
For the strongly convex case, if there are no equality or inequality constraints, the iteration complexity
result in (49) is optimal by√comparing it to (20). With the existence of constraints and nonsmooth term in
the objective, the order 1/ ε also appears to be optimal and is the best we can find in the literature; see
the discussion in section 5.

18

Yangyang Xu

Remark 3 From both (48) and (49), we see that T1 ≤ TK , ∀K ≥ 1, i.e., K = 1 is the best. Note that if
y0 = 0, z0 = 0, and K = 1, Algorithm 1 reduces to the quadratic penalty method by solving a single penalty
problem. However, practically K > 1 could be better since dist(xk , Xk∗ ) usually decreases as k increases.
Hence, from (50) or (52), TK can be smaller than T1 if K > 1; see our numerical results in Table 1.
Theorem 6 (Iteration complexity with geometrically increasing penalty and constant error)
For any given ε > 0, let K be a positive integer number and Cβ , Cε two positive real numbers. Set {βk } and
{ρk } according to Setting 2 and {εk } to (44). Assume µ ≤ L40 . Let x̄K be given in (30). Then the inequalities
in (47) hold, and Algorithm 1 can produce x̄K by evaluating gradients of g, fi , i ∈ [m] in at most TK times,
where
!
'
& r
r
p
Cβ H(σ − 1)
Cβ
L∗
√
K
+
TK ≤ 2D
+ K , if µ = 0,
(55)
Cε
ε
ε( σ − 1)
and

&

TK ≤ 2Gε

K

s

L∗
+
µ

s

!
'
p
H Cβ (σ − 1)
√ √
+ K , if µ > 0.
µ ε( σ − 1)

where
H Cβ (σ − 1) + βg ε
Cβ D2
+ log L∗ + µ +
Gε = log
εCε
σε

!

(56)

.

Proof. When µ = 0, we have from the first inequality in (35) that the total number of gradient evaluations
satisfies
p
K−1
X dist(xk , X ∗ ) 2(L∗ + βk H)
k
TK ≤
+ K.
(57)
√
εk
k=0

Plugging into (57) the εk given in (44) and noting dist(xk , Xk∗ ) ≤ D yields
TK ≤ 2D

Note that

K−1 √
Cβ X L∗ + βk H
√
+ K.
Cε
ε

r

K
p
PK−1 √
−1
βk = βg σ√2σ−1
. From (36), it holds
k=0

Cβ (σ − 1)
+ 1,
βg ε

(59)

p
Cβ (σ − 1)
βk ≤ √ √
,
ε( σ − 1)

(60)

σK =

K

and thus σ 2 − 1 ≤

q

Cβ (σ−1)
.
βg ε

Therefore,
K−1
Xp
k=0

and using

(58)

k=0

√
√
√
L∗ + βk H ≤ L∗ + βk H, we have
K−1
Xp
k=0

L ∗ + βk H ≤

K−1
X p
k=0

L∗ +

p

p
p
Cβ H(σ − 1)
,
βk H ≤ K L ∗ + √ √
ε( σ − 1)

(61)

Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming

19

which together with (58) gives (55).
For the strongly convex case, we use (51) and the second inequality of (35) to have

TK ≤ 2

K−1
X
k=0

s

L ∗ + βk H
log
µ



L ∗ + βk H + µ
[dist(xk , Xk∗ )]2
2εk



+ K.

(62)

Since dist(xk , Xk∗ ) ≤ D and εk ’s are set to those in (44), the above inequality indicates
TK ≤ 2

K−1
X
k=0

s

L ∗ + βk H
Cβ D2 (L∗ + βk H + µ)
+ K.
log
µ
εCε

(63)

For 0 ≤ k < K,
βk ≤ βK−1 = βg σ

K−1

βg K (59) βg
σ =
=
σ
σ



Cβ (σ − 1)
+1
βg ε



=

Cβ (σ − 1) + βg ε
.
σε

(64)

Plugging into (63) the second inequality in (61) and the above bound on βk , we have (56) and thus complete
the proof.

Remark 4 Comparing the iteration complexity results in Theorems 5 and 6, we see that if K = 1, the number
TK in either case of µ = 0 or µ > 0 is the same for both penalty parameter settings as σ → ∞. That is
because when K = 1, iALM with either of the two settings reduces to the penalty method. If K > 1, the
number TK for the setting of geometrically increasing penalty can be smaller than that for the constant
parameter setting as σ is big; see numerical results in section 6.
Theorem 7 (Iteration complexity with geometrically increasing penalty and adaptive error)
For any given ε > 0, let K be a positive integer number and Cβ , Cε two positive real numbers. Set {βk } and
{ρk } according to Setting 2. Assume µ ≤ L40 . If µ = 0, set {εk } as in (45), and if µ > 0, set {εk } as in (46).
Let x̄K be given in (30). Then the inequalities in (47) hold, and Algorithm 1 can produce x̄K by evaluating
gradients of g, fi , i ∈ [m] in at most TK times, where
&

TK ≤ 2D

r

Cβ
Cε

r

1

(σ − 1) 2
L∗
+
1
ε (σ 6 − 1)(σ 23 − 1) 21

!
p
HCβ (σ − 1)
2

3

ε(σ 3 − 1) 2

'

+ K , if µ = 0,

(65)

and
&

TK ≤ 2Gε

K

s

L∗
+
µ

s

!
'
p
H Cβ (σ − 1)
√ √
+ K , if µ > 0.
µ ε( σ − 1)

where
H Cβ (σ − 1) + βg ε
Cβ D2
Gε = log
+ log L∗ + µ +
εCε
σε

!

p
(σ − 1)2 + βg ε(σ − 1)/Cβ
√
+ log
.
σ− σ

(66)

20

Yangyang Xu

Proof. For the case of µ = 0, we have (57), plugging into which the εk given in (45) yields
v
uK−1
X
X 2 K−1
1
1
2 u
TK ≤ √ t
dist(xk , Xk∗ )βk6 (L∗ + βk H) 2 + K.
βt3
Cε t=0
k=0
Since dist(xk , Xk∗ ) ≤ D, the above inequality implies
v
uK−1
K−1
1
2D u X 23 X 61
βk (L∗ + βk H) 2 + K.
βt
TK ≤ √ t
Cε t=0
k=0

Note that

(67)

v
v
s
uK−1
uK−1
2K
uX 2
u X 2 2t
1
σ 3 −1
t
,
βt3 = t
βg3 σ 3 = βg3
2
σ3 − 1
t=0
t=0

and
K−1
X
k=0

1

1

βk6 (L∗ + βk H) 2 ≤

K−1
X

1

βk6

k=0

p
 p K−1
X 2
X 1 √ K−1
p
L ∗ + βk H = L ∗
βk3
βk6 + H

Hence, it follows from (67) that
TK
From (59) and the fact

2D 1
≤ √ βg3
Cε

s

σ

k=0

k=0

K
2K
p
√
1 σ 6 − 1
2 σ 3 − 1
6
3
= L ∗ βg 1
+ Hβg 2
.
σ6 − 1
σ3 − 1

2K
3
2

−1

σ3 − 1

K
2K
p
√
2 σ 3 − 1
1 σ 6 − 1
L∗ βg6 1
+ Hβg3 2
σ6 − 1
σ3 − 1

!

+ K.

(68)

√
√
√
a + b ≤ a + b, ∀a, b ≥ 0, it follows that
σ

2K
3

−1≤



Cβ (σ − 1)
βg ε

 32

,

σ

K
6

−1≤



Cβ (σ − 1)
βg ε

 61

.

(69)

Therefore, plugging the two inequalities in (69) into (68) yields (65).
For the case of µ > 0, we have (62). Since dist(xk , Xk∗ ) ≤ D and εk ’s are set to those in (46), the inequality
in (62) indicates
s
!
K−1
X L ∗ + βk H
X p L ∗ + βk H + µ
p K−1
2
TK ≤ 2
βk
βt
D +K
log
µ
Cε
t=0
k=0
s
!
√
P
√
K−1
X L ∗ + βk H

βk D2 K−1
βt
t=0
log
(70)
+ log L∗ + βk H + µ + K.
=2
µ
Cε
k=0

Therefore, plugging into (70) the inequality in (60), the upper bounds of
and (64) respectively, we obtain (66) and complete the proof.

PK−1 √
L∗ + βk H and βk in (61)
k=0


Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming

21

Remark 5 Let us compare the iteration
in Theorems 6 and 7. We see that for the case
√
q complexity results
HCβ
L∗
of µ = 0, as K > 1 and σ is big, if
, the iteration complexity result in Theorem 7 is
ε dominates
ε
√
q
HCβ
L∗
better than that in Theorem 6 (see the numerical results in Table 2), and if
dominates
ε
ε , the two
results are similar. For the case of µ > 0, as K > 1, the iteration complexity result in Theorem 6 is better
than that in Theorem 7.

4 Nonergodic convergence rate and iteration complexity
In this section, we show a nonergodic convergence rate result of Algorithm 1, by employing the relation
between iALM and the inexact proximal point algorithm (iPPA). Throughout this section, we assume there
is no affine equality constraint in (1), i.e., we consider the problem
minimize f0 (x), s.t. fi (x) ≤ 0, ∀i ∈ [m],
x∈X

(71)

where fi , i = 0, 1, . . . , m, satisfy the assumptions through (2)–(3b). We do not include affine equality constraints for the purpose of directly applying existing results in [30, 32]. Although results similar to those
in [30, 32] can possibly be shown for the equality and inequality constrained problem (1), we do not extend our discussion but instead formulate any affine equality constraint a⊤ x = b by two affine inequality
constraints a⊤ x − b ≤ 0 and −a⊤ x + b ≤ 0 if there is any.
4.1 Relation between iALM and iPPA
Let L0 (x, z) be the Lagrangian function of (71), namely,
L0 (x, z) = f0 (x) +

m
X

zi fi (x),

i=1

and let Lβ (x, z) be the augmented Lagrangian function of (71), defined in the same way as that in (6). In
addition, let d0 (z) be the Lagrangian dual function, defined as
(
minx∈X L0 (x, z), if z ≥ 0,
d0 (z) =
−∞,
otherwise,
and let dβ (z) , minx∈X Lβ (x, z) be the augmented Lagrangian dual function.
Applying Algorithm 1 with ρk = βk to (71), we have iterates {(xk , zk )} that satisfy:
Lβk (xk+1 , zk ) ≤ dβ (zk ) + εk ,

(72a)

zk+1 = zk + βk ∇z Lβk (xk+1 , zk ).

(72b)

The iPPA applied to the Lagrangian dual problem maxz d0 (z) iteratively performs the updates:
zk+1 ≈ Mβk (zk ),

(73)

22

Yangyang Xu

where the operator Mβ is the proximal mapping of −βd0 , defined as
Mβ (z) = arg max d0 (u) −
u

1
ku − zk2 .
2β

In (73), the approximation could be measured by the objective error as in (72a) or by the gradient norm at
the returned point zk+1 ; see [13] for example.
It was noted in [30] that
1
ku − zk2 ,
(74)
dβ (z) = max d0 (u) −
u
2β
q
and in addition, if x̂ ∈ X satisfies Lβ (x̂, z) ≤ dβ (z) + ε, then kz + β∇z Lβ (x̂, z) − M(z)k ≤ βε
2 . Therefore,
iALM with updates in (72) reduces to iPPA in (73) with approximation error
k+1

kz

k

− Mβk (z )k ≤

r

βk ε k
.
2

(75)

4.2 Nonergodic convergence rate of iALM
For iALM with updates in (72) on solving (71), [32, Theorem 4] establishes the following bounds on the
objective error and feasibility violation:
f0 (xk+1 ) − f0 (x∗ ) ≤ εk +
fi (xk+1 ) ≤

kzk k2 − kzk+1 k2
,
2βk

|zik − zik+1 |
, ∀ i ∈ [m].
βk

(76a)
(76b)

If in (72a), εk = 0, ∀k, [12, Theorem 2.2] shows that
kz0 − z∗ k
kzk − zk+1 k
≤ Pk
.
βk
t=0 βt

(77)

Therefore, combining the results in (76) with εk = 0, ∀k and (77), and also noting the boundedness of zk
from (40), one can easily obtain a nonergodic convergence rate result of exact ALM on solving (71). However,
k
k+1
k
if εk > 0, we do not notice any existing result on estimating kz −z
. In the following, we establish a bound
βk
on this quantity and thus show a nonergodic convergence rate result of iALM.
Lemma 7 Given a positive integer K and a nonnegative number Cε , choose positive sequences {βk } and
PK−1
{εk } such that k=0 βk εk ≤ C2ε . Let {(xk , zk )}K
k=0 be the sequence generated from the updates in (72) with
z0 = 0 on solving (71). Then
7p
Cε ,
(78)
kzk − zk+1 k ≤ 5kz∗ k +
2
where we have assumed that (71) has a primal-dual solution (x∗ , z∗ ).

Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming

23

Proof. Let z̃k+1 = Mβk (zk ). Then from (74), it follows that
1
kz̃k+1 − zk k2 = d0 (z̃k+1 ) − dβk (zk ).
2βk

(79)

By the weak duality, it holds d0 (z̃k+1 ) ≤ f0 (x∗ ). From (72a), we have
dβk (zk ) ≥ Lβk (xk+1 , zk ) − εk .

(80)

2

v
Recall the definition of ψβ (u, v) in (5) and note ψβ (u, v) ≥ − 2β
. Hence,

Lβk (xk+1 , zk ) = f0 (xk+1 ) +

m
X
i=1

ψβk (fi (xk+1 , zik ) ≥ f0 (xk+1 ) −

kzk k2
.
2βk

Thus by (80), it holds that
dβk (zk ) ≥ f0 (xk+1 ) −

kzk k2
− εk ,
2βk

and

kzk k2
+ εk .
2βk
Since (x∗ , z∗ ) is a primal-dual solution of (71), similar to (12), it holds that
d0 (z̃k+1 ) − dβk (zk ) ≤ f0 (x∗ ) − f0 (xk+1 ) +

f0 (x) − f0 (x∗ ) +
Hence,
f0 (x∗ ) − f0 (xk+1 ) ≤

m
X
i=1

m
X
i=1

zi∗ fi (x) ≥ 0, ∀x ∈ X .
(76b)

zi∗ fi (xk+1 ) ≤

(81)

(82)

kzk − zk+1 k ∗
kz k.
βk

Therefore, from (81) and the above inequality, it follows that
d0 (z̃k+1 ) − dβk (zk ) ≤

kzk − zk+1 k ∗
kzk k2
kz k +
+ εk ,
βk
2βk

and noting (79), we have
q

2βk d0 (z̃k+1 ) − dβk (zk )
q
≤ 2kzk − zk+1 k · kz∗ k + kzk k2 + 2βk εk .

kz̃k+1 − zk k =

By the triangle inequality, we have from (75) and the above inequality that
k

k+1

kz − z

r
q
βk ε k
k ≤ 2kzk − zk+1 k · kz∗ k + kzk k2 + 2βk εk +
2
√
q
p
3 2
≤ 2(kzk k + kzk+1 k)kz∗ k + kzk k +
βk ε k
2
3p
kzk k + kzk+1 k
+ kz∗ k + kzk k +
≤
Cε ,
2
2

(83)

24

Yangyang Xu

where the last inequality uses the Young’s inequality and the fact βk εk ≤
as those in Lemma 6, one can show
p
kzk k ≤ 2kz∗ k + Cε , ∀ 0 ≤ k ≤ K,

Cε
2 .

Through the same arguments

(84)

i.e., the inequality in (40) with y∗ = 0. Plugging the above bound on kzk k into (83) gives the desired result
in (78).

Combining (76) and (78), we are able to establish the nonergodic convergence rate result of iALM on
solving (71).
Theorem 8 (nonergodic convergence rate) Under the same assumptions of Lemma 7, it holds that for
any 0 ≤ k < K,
√ 

2kz∗ k + Cε
7p
∗
f0 (x
) − f0 (x ) ≤ εk +
Cε ,
5kz k +
βk
2


7p
1
Cε .
5kz∗ k +
[f (xk+1 )]+ ≤
βk
2
k+1

∗

(85a)
(85b)

Proof. Directly from (76), (78), and (84), we obtain (85b) and
f0 (xk+1 ) − f0 (x∗ ) ≤ εk +

2kz∗ k +
βk

√ 

7p
Cε
5kz∗ k +
Cε .
2

(86)

Using (82), we have from (85b) that
k+1

f0 (x

which together with (86) gives (85a).

kz∗ k
) − f0 (x ) ≥ −
βk
∗



7p
∗
5kz k +
Cε ,
2


Remark 6 From the results in (85), we see that to have {xk } to be a minimizing sequence of (71), we need
βk → ∞ and εk → 0 as k → ∞. Hence, setting {βk } to a constant sequence will not be a valid option.
4.3 Iteration complexity
In this subsection, we set parameters according to Setting 2, and we estimate the iteration complexity of
iALM on solving (71) by applying Nesterov’s optimal first-order method to (72a). Again, note that the
results in Theorem 8 do not need specific structure of (71) except convexity. Hence, if the problem has richer
structures, one can apply more efficient methods to find xk+1 that satisfies (72a).
Theorem 9 (Nonergodic iteration complexity) Given a positive integer K and positive numbers Cβ , Cε ,
choose positive sequences {ρk } and {βk } according to Setting 2. In addition, choose {εk } according to (44)
for both cases of µ = 0 and µ > 0, or choose {εk } according to (45) for the case of µ = 0 and (46) for µ > 0.

Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming

25

k
0
Let {(xk , zk )}K
k=0 be the sequence generated from Algorithm 1 with y = 0, ∀k, and z = 0 on solving (71).
Then

p 
ε Cε
εσ
7p
f0 (xK ) − f0 (x∗ ) ≤
Cε ,
2kz∗ k + Cε 5kz∗ k +
+
(87a)
2 Cβ
Cβ (σ − 1)
2


7p
εσ
(87b)
Cε .
5kz∗ k +
[f (xK )]+ ≤
Cβ (σ − 1)
2

If {εk } is chosen according to (44) for both cases of µ = 0 and µ > 0, the total number TK of gradient
evaluations is given in (55) and (56) respectively; if {εk } is set according to (45) for the case of µ = 0 and
(46) for µ > 0, then TK is given in (65) for µ = 0 and (66) for µ > 0.
Proof. Note that βk is increasing with respect to k. Hence, the εk given in both (45) and (46) is decreasing,
and thus
PK−1
βt ε t
ε Cε
.
εK−1 ≤ Pt=0
≤
K−1
2
Cβ
t=0 βt
If {εk } is chosen according to (44) for both cases of µ = 0 and µ > 0, then the above bound on εK−1
obviously holds. In addition, from (64), we have
βK−1 ≥

Cβ (σ − 1)
.
εσ

Therefore, plugging into (85) the bounds on εK−1 and βK−1 gives the desired results in (87).
The bounds on the total number TK of gradient evaluations follow from the same arguments as in the

proofs of Theorems 6 and 7. Hence, we complete the proof.
Remark 7 From the results in (87), we see that if
2Cβ ≥ Cε +


p 
2σ
7p
Cε ,
2kz∗ k + Cε 5kz∗ k +
(σ − 1)
2

(88)

σ
≈ 1 (e.g., σ = 10 is often used),
then xK is an ε-optimal solution to (71). If kz∗ k ≥ 1, Cε = kz∗ k2 , and σ−1
then the Cβ inq(88) is roughly 10 times of that in (53) by assuming no affine constraint. For the iteration
√
√
∗
k
complexity, if Lε∗ dominates Hkz
, then the nonergodic result is roughly 10 times of the ergodic result
ε
√

∗

k
for both convex and strongly convex cases. If Hkz
ε√ dominates, then the former would be roughly 10 times
of the latter for the convex case, but still roughly 10 times for the strongly convex case. However, in either
case, both ergodic and nonergodic results have the same order of complexity.

5 Related works and comparison with existing results
In this section, we review related works and compare them to our results. Our review and comparison focus
on convex optimization, but note that ALM has also been popularly applied to nonconvex optimization
problems; see [4–6] and the references therein.

26

Yangyang Xu

Affinely constrained convex problems
Several recent works have established the convergence rate of ALM and its inexact version for affinely
constrained convex problems:
minimize f0 (x), s.t. Ax = b.
(89)
x∈X

Assuming exact solution to every x-subproblem, [14] first shows O(1/k) convergence of ALM for smooth
problems in terms of dual objective and then accelerates the rate to O(1/k 2 ) by applying Nesterov’s extrapolation technique to the multiplier update. The results are extended to nonsmooth problems in [18] that
uses similar technique. By adapting parameters, [35] establishes O(1/k 2 ) convergence of a linearized ALM in
terms of primal objective and feasibility violation. The linearized ALM allows linearization to smooth part
in the objective but still assumes exact solvability of x-subproblems.
When the objective is strongly convex, [17] proves O(1/k 2 ) convergence of iALM with extrapolation
technique applied to the multiplier update. It requires summable error and subproblems to be solved more
and more accurately. However, it does not give an estimate on the total number of gradient evaluations on
solving all subproblems to the required accuracies.
For smooth linearly constrained convex problems, [20] analyzes the iteration complexity of the iALM.
7
It applies Nesterov’s optimal first-order method to every x-subproblem and shows that O(ε− 4 ) gradient
evaluations are required to reach an ε-optimal solution. Compared to this complexity, our results for the
3
convex case are better by an order O(ε− 4 ). In addition, [20] modifies the iALM by solving a perturbed
3
problem. The modified iALM requires O(ε−1 | log ε| 4 ) gradient evaluations to produce an ε-optimal solution,
3
and this order is worse than our results by an order O(| log ε| 4 ). Motivated by the model predictive control,
[23] also analyzes the iteration complexity of inexact dual gradient methods (iDGM) that are essentially
iALMs. It shows that to reach an ε-optimal solution4 , a nonaccelerated iDGM requires O(ε−1 ) outer iterations
1
and every x-subproblem solved to an accuracy O(ε2 ), and an accelerated iDGM requires O(ε− 2 ) outer
3
iterations and every x-subproblem solved to an accuracy O(ε ). While the iteration complexity in [20] is
estimated based on the best iterate, and that in [23] is ergodic, the recent work [21] establishes non-ergodic
convergence of iALM. It requires O(ε−2 ) gradient evaluations to reach an ε-optimal primal-dual solution
(x̄, ȳ) in the sense that
√
kAx̄ − bk ≤ ε,
∇g(x̄) + A⊤ ȳ, x̄ − x + h(x̄) − h(x) ≤ ε, ∀x,
(90)
where it is assumed that f0 = g + h in (89) and g is Lipschitz differentiable. From the convexity of g, it
follows from (90) that
√
f0 (x̄) − f0 (x∗ ) ≤ h∇g(x̄), x̄ − x∗ i + h(x̄) − h(x) ≤ ε − hȳ, Ax̄ − bi ≤ ε + kȳk ε.
Hence, if ȳ 6= 0, to have an ε-optimal solution by our Definition 1, the iteration complexity result in [21]
would be O(ε−4 ), which is O(ε−3 ) worse than our nonergodic iteration complexity result in Theorem 9.
Another line of existing works on iALM assume two or multiple block structure on the problem and
simply perform one cycle of Gauss-Seidel update to the block variables or update one randomly selected
block. Global sublinear convergence of these methods has also been established. Exhausting all such works is
impossible and out of scope of this paper. We refer interested readers to [7–10,15,28,36,37] and the references
therein.
˜ β (xk+1 , yk ), x − xk+1 i ≥ −O(ε), ∀x ∈ X , which is implied by
[23] assumes every subproblem solved to the condition h∇L
k+1
k
k
2
Lβ (x
, y ) − minx∈X Lβ (x, y ) ≤ O(ε ) if Lβ is Lipschitz differentiable with respect to x.
4

Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming

27

General convex problems
As there are nonlinear inequality constraints, we do not find any work in the literature showing the global
convergence rate of iALM, though its local convergence rate has been extensively studied (e.g., [3, 30, 32]).
Many existing works on nonlinearly constrained convex problems employ Lagrangian function instead of the
augmented one and establish global convergence rate through
dual subgradient approach (e.g., [22, 24, 25]).
√
For general convex problems, these methods enjoy O(1/ k) convergence, and for strongly convex case, the
rate can be improved to O(1/k). To achieve an ε-optimal solution, compared to our results, their iteration
1
complexity is O(ε−1 ) times worse for the convex problems and O(ε− 2 ) worse for the strongly convex problems.
Assuming Lipschitz continuity of ∇fi for every i ∈ [m], [39] proposes a new primal-dual type algorithm for
nonlinearly constrained convex programs. Every iteration, it minimizes a proximal Lagrangian function and
updates the multiplier in a novel way. With sufficiently large proximal parameter that depends on the
Lipschitz constants of fi ’s, the algorithm converges in O(1/k) ergodic rate. The follow-up paper [38] focuses
on smooth constrained convex problems and proposes a linearized variant of the algorithm in [39]. Assuming
compactness of the set X , it also establishes O(1/k) ergodic convergence of the linearized method.
Iteration complexity from existing results on iPPA
Through relating iALM and iPPA, iteration complexity result can be obtained from existing results about
iPPA to produce near-optimal dual solution. On solving problem minz φ(z), [13] analyzes the iPPA with
iterative update:
1
kz − ẑk k2 .
zk+1 ≈ arg min φ(z) +
2βk
z
If the above approximation error satisfies
kzk+1 − proxβk φ (ẑk )k = O(1/k a ),

(91)

for a certain number a > 12 , and the parameter βk is increasing, then by choosing specifically designed ẑk , [13]
shows that
φ(zk ) − φ(z∗ ) = O(1/k 2 ) + O(1/k 2a−1 ).

From our discussion in section 4.1, if εk = O( k2a1βk ) in (72a), then we have (91) holds with φ = −d0 , and
thus obtain the convergence rate in terms of dual function:
d0 (z∗ ) − d0 (zk ) = O(1/k 2 ) + O(1/k 2a−1 ).
Note that zk is bounded from the summability of βk εk and the proof of Lemma 6. Hence, setting βk to a
constant for all k and applying Nesterov’s optimal first-order method to each subproblem in (72a), we need
O(k a ) gradient evaluations.
√
Let a = 32 . Then K = O(1/ ε) iPPA iterations are required to obtain an ε-optimal dual solution, i.e.,
d0 (zK ) ≥ d0 (z∗ ) − ε, and the total number of gradient evaluations is
TK =

K
X

3

5

5

O(k 2 ) = O(K 2 ) = O(ε− 4 ).

k=1

However, it is not clear how to measure the quality of the primal iterates.

28

Yangyang Xu

6 Numerical results
In this section, we conduct numerical experiments on the quadratically constrained quadratic programming
(QCQP):
1 ⊤
x Q0 x + c⊤
0 x,
2
1
s.t. x⊤ Qj x + c⊤
j x + dj ≤ 0, j = 1, . . . , m,
2
xi ∈ [li , ui ], i = 1, . . . , n.

minimize
n
x∈R

(92)

The purpose of the tests is to verify the established theoretical results and compare the iALM with three
different settings of parameters.
Three QCQP instances are made. The first two instances are convex, and the third one is strongly convex.
For all three instances, we set n = 100, m = 5 and li = −1, ui = 1, ∀i. The vectors cj , j = 0, 1, . . . , m are
generated following Gaussian distribution, and the scalars dj , j = 1, . . . , m are made negative. This way,
all inequalities in (92) hold strictly at the origin x = 0, and thus the KKT conditions are satisfied at the
optimal solution. Qj , j = 0, 1, . . . , m are randomly generated and symmetric positive semidefinite. Q0 is
rank-deficient for the first two instances and full-rank for the third one. The data in the first two instances
are the same except Q0 , which is 100 times in the second instance as that in the first instance.
For all tests, we set ε = 10−3 , Cβ = 1, Cε = ku − lk, and K = 10, and the initial primal-dual point is set
to zero vector. The algorithm parameters {(βk , ρk , εk )}K−1
k=0 are set in three different ways corresponding to
Theorems 5, 6, and 7 respectively, where σ = 10 is used for the geometrically increasing penalty. On finding
xk+1 by applying Algorithm 2 to minx∈X Lβk (x, zk ), we terminate the algorithm if the iteration number
exceeds 106 or

εk
,
(93)
dist −∇x Lβk (xk+1 , zk ), NX (xk+1 ) ≤
ku − lk

where X = ×ni=1 [li , ui ]. Since Lβk (x, zk ) is convex about x, and ku − lk is the diameter of the feasible set X ,
the condition in (93) guarantees that xk+1 satisfies (7).
We report the difference of objective value and optimal
value,
Pk
Pk and the feasibility violation at both actual
iterate xk and the weighted averaged point x̄k = t=1 xt / t=1 βt . The optimal solution is computed by
CVX [11]. In addition, to compare the iteration complexity, we also report the number of gradient evaluations
and function evaluations for each outer iteration. The results are provided in Tables 1, 2, and 3 respectively for
the three instances. In Table 1, we also report the results from quadratic penalty method, which corresponds
to setting K = 1 (see the discussions in Remark 3).
From the results, we can clearly see that the quadratic penalty method is worse, namely, running a single
iALM step with a big penalty parameter is significantly worse than running multiple steps with smaller
penalty parameters. Also, we see that the iALM with three different settings yields the last actual iterate
xK and the averaged point x̄K of similar accuracy. For all three instances, to produce similarly accurate
solutions, the iALM with constant penalty requires more gradient and function evaluations than that with
geometrically increasing penalty. Furthermore, the iALM with geometrically increasing penalty and constant
error requires fewest gradient and function evaluations on the first and third instances. However, the setting
of geometrically increasing penalty and adaptive error is the best for iALM on the second instance. That is
because the gradient Lipschitz constant of the objective in the second instance is significantly bigger than
that in the first instance, in which case the bound on TK in (65) is smaller than that in (55).

Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming

29

Table 1 Results by quadratic penalty method (i.e., iALM with K = 1) and iALM with three different settings on solving an
instance of the QCQP problem (92). In this instance, Qj is symmetric positive semidefinite for each j = 0, 1, . . . , m, and Q0 is
singular. All Qj ’s have similarly large spectral norm.
#OutIter

#gradEval

0
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
10

|f0 (xk ) − f0∗ |

[f (xk )]+

|f0 (x̄k ) − f0∗ |

quadratic penalty method
2709547
7.4625e-06
8.6425e-05
7.4625e-06
constant penalty and constant error
1.9949e+01
0.0000e+00
1.9949e+01
116670
316150
7.4618e-05
8.6422e-04
7.4618e-05
25
69
6.8617e-08
1.3444e-08
3.7275e-05
1
2
7.0236e-08
2.0003e-09
2.4826e-05
18
50
6.9210e-08
6.3998e-09
1.8603e-05
1
2
6.9964e-08
5.1992e-09
1.4868e-05
15
42
6.9288e-08
5.5183e-09
1.2379e-05
1
2
6.9923e-08
1.9898e-09
1.0600e-05
1
2
6.8851e-08
1.1481e-08
9.2665e-06
11
31
6.9962e-08
3.5627e-09
8.2291e-06
15
42
6.9431e-08
1.6670e-09
7.3993e-06
geometrically increasing penalty and constant error
1.9949e+01
0.0000e+00
1.9949e+01
54
150
4.8272e+00
1.4965e+02
4.8272e+00
27
73
4.8244e+00
1.4619e+02
4.8249e+00
43
117
4.6109e+00
1.1371e+02
4.6448e+00
40
111
2.6482e+00
3.9785e+01
2.9364e+00
89
246
3.3958e-01
4.1057e+00
6.4687e-01
217
594
3.6558e-03
4.4944e-02
6.9536e-02
72
202
4.9778e-06
6.8024e-05
6.9757e-03
9
31
6.0090e-08
1.3942e-07
6.9770e-04
1
9
6.3775e-08
1.7150e-08
6.9714e-05
11
42
6.4092e-08
8.7057e-10
6.9137e-06
geometrically increasing penalty and adaptive error
1.9949e+01
0.0000e+00
1.9949e+01
9
28
4.7815e+00
1.4467e+02
4.7815e+00
1
2
4.8000e+00
1.4311e+02
4.7990e+00
6
16
4.6446e+00
1.1719e+02
4.6705e+00
12
33
2.6268e+00
3.9395e+01
2.9242e+00
25
72
3.4073e-01
4.1139e+00
6.4650e-01
61
172
3.4865e-03
4.3037e-02
6.9338e-02
70
198
3.5015e-06
1.2314e-04
6.9557e-03
251
687
1.2912e-06
3.2057e-06
6.9477e-04
861
2340
3.2891e-07
1.8655e-07
6.9220e-05
2798
7588
8.1672e-08
8.2282e-09
6.8563e-06

1000000
0
1
2
3
4
5
6
7
8
9
10

#funEval

[f (x̄k )]+
8.6425e-05
0.0000e+00
8.6422e-04
4.3212e-04
2.8807e-04
2.1606e-04
1.7285e-04
1.4404e-04
1.2346e-04
1.0803e-04
9.6026e-05
8.6423e-05
0.0000e+00
1.4965e+02
1.4650e+02
1.1675e+02
4.6129e+01
7.8390e+00
8.0931e-01
8.0847e-02
8.0834e-03
8.0833e-04
8.0832e-05
0.0000e+00
1.4467e+02
1.4325e+02
1.1968e+02
4.5842e+01
7.8356e+00
8.0737e-01
8.0705e-02
8.0709e-03
8.0697e-04
8.0640e-05

7 Concluding remarks
We have established ergodic and also nonergodic convergence rate results of iALM for general constrained
convex programs. Furthermore, we have shown that to reach an ε-optimal solution, it is sufficient to evaluate
gradients of smooth part in the objective and the functions in the inequality constraints for O(ε−1 ) times if
1
the objective is convex and O(ε− 2 | log ε|) times if the objective is strongly convex. For the convex case, the

30

Yangyang Xu

Table 2 Results by iALM with three different settings on solving an instance of the QCQP problem (92). In this instance, Qj
is symmetric positive semidefinite for each j = 0, 1, . . . , m. Q0 is singular, and its spectral norm is about 100 times of that of
every other Qj .
#OutIter
0
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
10

#gradEval

#funEval

|f0 (xk ) − f0∗ |

[f (xk )]+ ]

|f0 (x̄k ) − f0∗ |

constant penalty and constant error
2.4292e+00
0.0000e+00
2.4292e+00
1000000
2709541
1.9905e-03
3.5756e-03
1.9905e-03
534315
1447734
2.5923e-05
0.0000e+00
9.4283e-04
96
260
1.2144e-08
2.0371e-08
6.1404e-04
4
11
1.8289e-08
1.8936e-09
4.5509e-04
1
2
1.8757e-08
9.2594e-09
3.6146e-04
1
2
1.8790e-08
5.1559e-13
2.9977e-04
1
2
1.8601e-08
2.7707e-09
2.5606e-04
1
2
1.8639e-08
1.3276e-10
2.2347e-04
1
2
1.8617e-08
1.0515e-09
1.9824e-04
1
2
1.8643e-08
2.5039e-11
1.7813e-04
geometrically increasing penalty and constant error
2.4292e+00
0.0000e+00
2.4292e+00
1608
4372
8.7897e+00
9.3634e+01
8.7897e+00
176
477
8.7896e+00
9.3580e+01
8.7896e+00
9862
26722
8.7023e+00
7.5071e+01
8.7111e+00
5273
14288
8.3403e+00
5.7871e+01
8.3897e+00
3607
9773
3.2122e+00
1.3501e+01
3.7378e+00
2015
5460
4.9389e-01
1.5196e+00
8.2693e-01
2280
6183
1.5237e-02
4.4585e-02
9.7553e-02
1711
4643
5.4333e-05
1.5928e-04
9.8224e-03
29
84
6.2151e-08
2.2139e-07
9.8249e-04
4
17
9.9229e-09
3.9442e-09
9.8242e-05
geometrically increasing penalty and adaptive error
2.4292e+00
0.0000e+00
2.4292e+00
189
528
8.5613e+00
8.2337e+01
8.5613e+00
6
16
8.5659e+00
8.1843e+01
8.5656e+00
228
617
8.6240e+00
6.8449e+01
8.6188e+00
1074
2910
8.3440e+00
5.7951e+01
8.3836e+00
1529
4143
3.2289e+00
1.3596e+01
3.7525e+00
869
2355
4.9425e-01
1.5203e+00
8.2875e-01
1666
4518
1.5018e-02
4.3948e-02
9.7515e-02
1375
3731
5.5686e-05
1.6697e-04
9.8198e-03
139
383
5.9937e-08
1.0896e-06
9.8211e-04
967
2627
4.8356e-08
7.3292e-09
9.8168e-05

[f (x̄k )]+
0.0000e+00
3.5756e-03
0.0000e+00
0.0000e+00
0.0000e+00
0.0000e+00
0.0000e+00
0.0000e+00
0.0000e+00
0.0000e+00
0.0000e+00
0.0000e+00
9.3634e+01
9.3585e+01
7.6245e+01
5.9057e+01
1.6465e+01
2.6282e+00
2.8390e-01
2.8279e-02
2.8256e-03
2.8254e-04
0.0000e+00
8.2337e+01
8.1888e+01
6.8342e+01
5.8797e+01
1.6552e+01
2.6347e+00
2.8380e-01
2.8274e-02
2.8248e-03
2.8237e-04

iteration complexity result is optimal, and for the strongly convex case, the result is the best in the literature
and appears to be also optimal.
References
1. A. Beck and M. Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM journal on
imaging sciences, 2(1):183–202, 2009. 7
2. A. Ben-Tal and M. Zibulevsky. Penalty/barrier multiplier methods for convex programming problems. SIAM Journal on
Optimization, 7(2):347–366, 1997. 2

Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming

31

Table 3 Results by iALM with three different settings on solving a strongly convex instance of the QCQP problem (92).
#OutIter

#gradEval

0
1
2
3
4
5
6
7
8
9
10

4111
10
1
1
1
1
1
1
1
1

0
1
2
3
4
5
6
7
8
9
10

16
6
9
11
26
56
31
2
2
2

0
1
2
3
4
5
6
7
8
9
10

1
1
1
3
8
24
75
250
801
2603

#funEval

|f0 (xk ) − f0∗ |

[f (xk )]+

|f0 (x̄k ) − f0∗ |

constant penalty and constant error
1.3704e+01
0.0000e+00
1.3704e+01
11170
1.6951e-05
4.1227e-04
1.6951e-05
28
4.5144e-08
9.5417e-09
8.4530e-06
2
4.5496e-08
1.1679e-09
5.6202e-06
2
4.5470e-08
0.0000e+00
4.2038e-06
2
4.5410e-08
5.2874e-10
3.3539e-06
2
4.5423e-08
1.1857e-10
2.7874e-06
2
4.5417e-08
1.4938e-10
2.3827e-06
2
4.5420e-08
1.4935e-11
2.0792e-06
2
4.5417e-08
4.2566e-11
1.8431e-06
2
4.5417e-08
5.2216e-12
1.6543e-06
geometrically increasing penalty and constant error
1.3704e+01
0.0000e+00
1.3704e+01
47
7.7888e-01
4.0032e+01
7.7888e-01
18
7.7879e-01
3.9621e+01
7.7880e-01
26
7.7142e-01
3.5936e+01
7.7269e-01
31
5.6681e-01
1.8568e+01
6.0051e-01
75
8.2135e-02
2.0563e+00
1.4945e-01
158
1.1249e-03
2.7458e-02
1.6675e-02
91
1.5987e-06
4.0394e-05
1.6772e-03
12
4.9762e-08
0.0000e+00
1.6776e-04
11
3.6101e-08
3.0525e-08
1.6745e-05
10
3.6919e-08
1.0977e-09
1.6412e-06
geometrically increasing penalty and adaptive error
1.3704e+01
0.0000e+00
1.3704e+01
6
2.1524e+00
1.8206e+01
2.1524e+00
6
1.8807e-01
2.3036e+01
2.4599e-01
6
3.6907e-01
2.8225e+01
3.3200e-01
12
5.1655e-01
1.7712e+01
5.1962e-01
25
8.4506e-02
2.2023e+00
1.4307e-01
71
8.4618e-04
3.1440e-02
1.5993e-02
210
4.8570e-05
3.3014e-05
1.5905e-03
684
5.5023e-06
4.6695e-06
1.5741e-04
2178
5.7505e-07
1.2058e-07
1.5607e-05
7062
5.8030e-08
0.0000e+00
1.5503e-06

[f (x̄k )]+
0.0000e+00
4.1227e-04
2.0614e-04
1.3742e-04
1.0307e-04
8.2455e-05
6.8712e-05
5.8896e-05
5.1534e-05
4.5808e-05
4.1227e-05
0.0000e+00
4.0032e+01
3.9658e+01
3.6303e+01
2.0298e+01
3.8384e+00
4.0689e-01
4.0708e-02
4.0703e-03
4.0705e-04
4.0706e-05
0.0000e+00
1.8206e+01
2.2315e+01
2.7560e+01
1.8616e+01
3.8034e+00
4.0623e-01
4.0504e-02
4.0367e-03
4.0198e-04
4.0009e-05

3. D. P. Bertsekas. Convergence rate of penalty and multiplier methods. In Decision and Control including the 12th Symposium
on Adaptive Processes, 1973 IEEE Conference on, volume 12, pages 260–264. IEEE, 1973. 2, 27
4. D. P. Bertsekas. Nonlinear programming. Athena scientific Belmont, 1999. 2, 25
5. D. P. Bertsekas. Constrained optimization and Lagrange multiplier methods. Academic press, 2014. 2, 25
6. E. G. Birgin, R. Castillo, and J. M. Martı́nez. Numerical comparison of augmented lagrangian algorithms for nonconvex
problems. Computational Optimization and Applications, 31(1):31–55, 2005. 25
7. S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein. Distributed optimization and statistical learning via the alternating
direction method of multipliers. Foundations and Trends R in Machine Learning, 3(1):1–122, 2011. 26
8. W. Deng and W. Yin. On the global and linear convergence of the generalized alternating direction method of multipliers.
Journal of Scientific Computing, 66(3):889–916, 2016. 26
9. X. Gao, Y. Xu, and S. Zhang.
Randomized primal-dual proximal block coordinate updates.
arXiv preprint
arXiv:1605.05969, 2016. 26
10. R. Glowinski. On alternating direction methods of multipliers: a historical perspective. In Modeling, simulation and
optimization for science and technology, pages 59–82. Springer, 2014. 26

32

Yangyang Xu

11. M. Grant, S. Boyd, and Y. Ye. CVX: Matlab software for disciplined convex programming, 2008. 28
12. O. Güler. On the convergence of the proximal point algorithm for convex minimization. SIAM Journal on Control and
Optimization, 29(2):403–419, 1991. 22
13. O. Güler. New proximal point algorithms for convex minimization. SIAM Journal on Optimization, 2(4):649–664, 1992.
22, 27
14. B. He and X. Yuan. On the acceleration of augmented lagrangian method for linearly constrained optimization. Optimization
online, 2010. 2, 26
15. B. He and X. Yuan. On the O(1/n) convergence rate of the douglas–rachford alternating direction method. SIAM Journal
on Numerical Analysis, 50(2):700–709, 2012. 2, 26
16. M. R. Hestenes. Multiplier and gradient methods. Journal of optimization theory and applications, 4(5):303–320, 1969. 2,
3
17. M. Kang, M. Kang, and M. Jung. Inexact accelerated augmented lagrangian methods. Computational Optimization and
Applications, 62(2):373–404, 2015. 26
18. M. Kang, S. Yun, H. Woo, and M. Kang. Accelerated bregman method for linearly constrained ℓ1 –ℓ2 minimization. Journal
of Scientific Computing, 56(3):515–534, 2013. 26
19. G. Lan and R. D. Monteiro. Iteration-complexity of first-order penalty methods for convex programming. Mathematical
Programming, 138(1-2):115–139, 2013. 5
20. G. Lan, D. Renato, and C. Monteiro. Iteration-complexity of first-order augmented lagrangian methods for convex programming. Mathematical Programming, 155(1-2):511–547, 2016. 26
21. Y.-F. Liu, X. Liu, and S. Ma. On the non-ergodic convergence rate of an inexact augmented lagrangian framework for
composite convex programming. arXiv preprint arXiv:1603.05738, 2016. 5, 26
22. I. Necoara and V. Nedelcu. Rate analysis of inexact dual first-order methods application to dual decomposition. IEEE
Transactions on Automatic Control, 59(5):1232–1243, 2014. 27
23. V. Nedelcu, I. Necoara, and Q. Tran-Dinh. Computational complexity of inexact gradient augmented lagrangian methods:
application to constrained mpc. SIAM Journal on Control and Optimization, 52(5):3109–3134, 2014. 26
24. A. Nedić and A. Ozdaglar. Approximate primal solutions and rate analysis for dual subgradient methods. SIAM Journal
on Optimization, 19(4):1757–1780, 2009. 27
25. A. Nedić and A. Ozdaglar. Subgradient methods for saddle-point problems. Journal of optimization theory and applications,
142(1):205–228, 2009. 27
26. Y. Nesterov. Introductory lectures on convex optimization: A basic course. Kluwer Academic Publisher, 2004. 7
27. Y. Nesterov. Gradient methods for minimizing composite functions. Mathematical Programming, 140(1):125–161, 2013. 7
28. Y. Ouyang, Y. Chen, G. Lan, and E. Pasiliao Jr. An accelerated linearized alternating direction method of multipliers.
SIAM Journal on Imaging Sciences, 8(1):644–681, 2015. 26
29. M. J. Powell. A method for non-linear constraints in minimization problems. in Optimization, R. Fletcher Ed., Academic
Press, New York, NY, 1969. 2, 3
30. R. T. Rockafellar. A dual approach to solving nonlinear programming problems by unconstrained optimization. Mathematical programming, 5(1):354–373, 1973. 2, 3, 21, 22, 27
31. R. T. Rockafellar. The multiplier method of hestenes and powell applied to convex programming. Journal of Optimization
Theory and applications, 12(6):555–562, 1973. 2, 4, 11
32. R. T. Rockafellar. Augmented lagrangians and applications of the proximal point algorithm in convex programming.
Mathematics of operations research, 1(2):97–116, 1976. 5, 21, 22, 27
33. M. Schmidt, N. L. Roux, and F. R. Bach. Convergence rates of inexact proximal-gradient methods for convex optimization.
In Advances in neural information processing systems, pages 1458–1466, 2011. 4
34. P. Tseng and D. P. Bertsekas. On the convergence of the exponential multiplier method for convex programming. Mathematical Programming, 60(1):1–19, 1993. 2
35. Y. Xu. Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming.
SIAM Journal on Optimization, 27(3):1459–1484, 2017. 26
36. Y. Xu. Asynchronous parallel primal-dual block update methods. arXiv preprint arXiv:1705.06391, 2017. 26
37. Y. Xu and S. Zhang. Accelerated primal–dual proximal block coordinate updating methods for constrained convex optimization. Computational Optimization and Applications, pages 1–38, 2017. 26
38. H. Yu and M. J. Neely. A primal-dual type algorithm with the O(1/t) convergence rate for large scale constrained convex
programs. In Decision and Control (CDC), 2016 IEEE 55th Conference on, pages 1900–1905. IEEE, 2016. 27
39. H. Yu and M. J. Neely. A simple parallel algorithm with an O(1/t) convergence rate for general convex programs. SIAM
Journal on Optimization, 27(2):759–783, 2017. 27

