PaperlayerView exact revision on arXiv

Source-linked AI summary

Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming

Yangyang Xu

arXiv:1711.05812v2math.OCcs.DScs.NAmath.NA

TL;DR

The paper addresses the open question of global convergence rates for inexact ALM on convex problems with nonlinear inequality constraints. It analyzes inexact primal updates and establishes gradient-evaluation bounds, including O(ε^-1) for convex objectives and O(ε^-1/2 |log ε|) for strongly convex objectives.

  • Problem

    The global convergence rate of inexact ALM for problems with nonlinear inequality constraints remained open, despite extensive study of ALM’s convergence and local rates.

    Source: General convex problems · p. 27

  • Method

    The paper analyzes inexact ALM through its primal problem, where each iteration approximately minimizes the augmented Lagrangian before updating the multipliers.

    Source: §1.2 · p. 3

  • Results

    O(ε^-1) gradient evaluations suffice for convex objectives, while O(ε^-1/2 |log ε|) suffice for strongly convex objectives.

    Source: §7 · p. 29

  • Takeaways & Limitations

    For K > 1, geometrically increasing penalties can require fewer iterations than constant penalties when σ is large.

    Source: Theorem 6 (Iteration complexity with… · p. 19

    The related-work discussion notes that the quality of primal iterates is unclear for the cited dual-subgradient approaches to nonlinearly constrained convex problems.

    Source: Iteration complexity from existing… · p. 27

Abstract

from arXiv · show

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(\varepsilon^{-1})$ gradient evaluations are sufficient to guarantee an $\varepsilon$-optimal solution in terms of both primal objective and feasibility violation. If the objective is strongly convex, the result can be improved to $O(\varepsilon^{-\frac{1}{2}}|\log\varepsilon|)$. 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.

1 Introduction

The paper studies inexact augmented Lagrangian methods for composite convex programs with equality and nonlinear inequality constraints, where the primal subproblems are solved approximately. It establishes convergence rates and gradient-evaluation complexity results for this setting.

1 Introduction

  • The problem class uses a closed convex set X, affine equality constraints, convex inequalities, and a composite objective with a smooth part and a possibly nonsmooth simple part.The paper assumes the smooth objective and inequality functions are Lipschitz differentiable.Source: §1 · p. 2

1.1 Augmented Lagrangian function

  • The paper derives the classic augmented Lagrangian by adding nonnegative slack variables to the inequalities and applying a quadratic penalty to the resulting equality constraints.The multipliers y and z correspond to equality and inequality constraints, and β is the augmented penalty parameter.Source: §1.1 · p. 3

1.2 Inexact augmented Lagrangian method

  • Inexact ALM alternates approximate minimization of the augmented Lagrangian over the primal variable with dual gradient-ascent updates, and its global rate for nonlinear inequality constraints was open.The paper distinguishes primal-objective and feasibility guarantees from convergence rates measured only through the augmented dual objective.Source: §1 · p. 2, §1.2 · pp. 3–4

1.3 Contributions

  • With constant or geometrically increasing penalties, the paper establishes ergodic and nonergodic convergence rates and obtains O(ε^-1) gradient evaluations for convex objectives and O(ε^-1/2 |log ε|) for strongly convex objectives.The analysis applies Nesterov’s optimal first-order method to each primal subproblem; the nonergodic result uses geometrically increasing penalties.Source: §1.3 · p. 5

1.4 Notation

  • The notation section restricts the presentation to finite-dimensional Euclidean space, while stating that the analysis extends directly to a general Hilbert space.It also sets conventions for vectors, matrices, positive parts, and norms.Source: §1.4 · p. 5

1.5 Outline

  • The paper proceeds from preliminary results and convergence analyses to complexity results, related-work comparisons, numerical experiments, and conclusions.The outline places ergodic analysis in Section 3 and nonergodic analysis in Section 4.Source: §1.5 · p. 6

2 Preliminary results and Nesterov’s optimal first-order method

This section provides facts used in the convergence analysis and reviews Nesterov’s first-order method for solving the primal subproblems. It presents the method for composite convex objectives and notes its convex and strongly convex convergence regimes.

2 Preliminary results and Nesterov’s optimal first-order method

  • The preliminary section reviews results used for the analysis and states that the first-order method’s convergence rates cover both convex and strongly convex cases.The method assumes known smoothness and strong-convexity parameters for simplicity, though it can estimate the smoothness constant by backtracking and needs only a lower estimate of strong convexity.Source: §2 · p. 6, §2.2 · p. 7

2.1 Basic facts

  • The section introduces KKT conditions and a lemma that will be used to establish the convergence rate of Algorithm 1.The lemma’s stated premise is that a point satisfies the KKT conditions.Source: §2.1 · p. 6

2.2 Nesterov’s optimal first-order method

  • The section reviews Nesterov’s optimal first-order method for approximately solving the inexact ALM’s primal subproblems, which are composite convex programs.The smooth component has a Lipschitz gradient, while the other component is simple, closed, convex, and may be nondifferentiable.Source: §2.2 · p. 7

3 Ergodic convergence rate and iteration complexity results

This section establishes ergodic convergence for inexact ALM and derives gradient-evaluation complexity bounds using Nesterov’s method on primal subproblems, including settings with constant or geometrically increasing penalties. It compares geometric-penalty complexities for constant and adaptive inner errors, states an adaptive-error gradient-evaluation guarantee, and notes that for strongly convex objectives with K > 1 the constant-error bound is better.

3.1 Convergence rate analysis of iALM

  • Under Assumptions 1 and 2, iALM has a one-iteration progress bound and an ergodic convergence-rate result when initialized with zero multipliers and 0 < ρk ≤ βk.Assumption 1 requires a KKT point, and Assumption 2 requires each primal subproblem to have a point satisfying its condition.Source: §3 · p. 8, §3.1 · pp. 9–10

3.2 Iteration complexity of iALM

  • Nesterov’s optimal first-order method solves each primal subproblem, while subproblem tolerances are chosen to minimize total gradient evaluations under either penalty schedule.The analysis uses convexity; richer problem structure may allow more efficient subproblem methods.Source: §3 · p. 8, §3.2 · pp. 12, 15
  • In Theorem 5’s constant-penalty, constant-error setting, Algorithm 1 produces x̄K using gradients of g and fi (i∈[m]) at most TK times.Source: §3.2 · p. 16
  • Although K = 1 minimizes the stated bound, using K > 1 can reduce total evaluations in practice as dist(xk, X*) decreases.The paper points to its numerical results for this practical possibility.Source: §3.2 · p. 18

Theorem 6 (Iteration complexity with geometrically increasing penalty and constant error)

  • With geometrically increasing penalties, the iteration complexity is in the same order as for the ergodic result; the stated theorem assumes µ ≤ L0/4.The theorem bounds gradient evaluations while guaranteeing the same error bounds as (47).Source: §3.2 · p. 17, Theorem 6 (Iteration complexity with… · p. 18
  • For K = 1, both penalty settings yield the same TK as σ → ∞; for K > 1, geometric penalty increases can reduce TK when σ is large.With K = 1, either setting reduces to the penalty method.Source: Theorem 6 (Iteration complexity with… · p. 19

Theorem 7 (Iteration complexity with geometrically increasing penalty and adaptive error)

4 Nonergodic convergence rate and iteration complexity

This section derives nonergodic convergence and gradient-evaluation complexity for iALM by relating it to iPPA and applying a first-order method to primal subproblems. Its nonergodic iteration complexity is in the same order as the ergodic result.

4.1 Relation between iALM and iPPA

  • The analysis relates iALM to iPPA and excludes affine equality constraints to apply existing iPPA results, noting equalities can be encoded as two affine inequalities.The section considers the inequality-constrained formulation and describes iPPA updates for the Lagrangian dual.Source: §4 · p. 21, §4.1 · pp. 21–22

4.2 Nonergodic convergence rate of iALM

  • With geometrically increasing penalties, the nonergodic convergence result requires β_k to increase and ε_k to decrease; a constant penalty sequence is not valid for a minimizing sequence.The analysis establishes a bound on successive dual iterates to obtain the nonergodic rate for inexact ALM.Source: §4.2 · pp. 22, 24

4.3 Iteration complexity

  • For iteration complexity, the authors apply Nesterov’s optimal first-order method to each primal subproblem and select penalty and error sequences under Setting 2.Theorem 9 states that the total gradient-evaluation count follows the bounds for the specified error choices.Source: §4.3 · pp. 24–25
  • The nonergodic iteration complexity is in the same order as the ergodic result.The theorem gives total gradient-evaluation counts for prescribed error choices.Source: §4.3 · p. 25

5 Related works and comparison with existing results

Prior global-rate results largely address affinely constrained problems, while the global convergence rate of inexact ALM with nonlinear inequality constraints had not been established. The paper compares its complexity results with several related ALM, dual-gradient, and proximal-point approaches.

Affinely constrained convex problems

  • For affinely constrained problems, prior ALM analyses establish O(1/k) or accelerated O(1/k^2) rates, with some methods requiring exact x-subproblem solutions.For strongly convex problems, establishes O(1/k^2) convergence but does not estimate total gradient evaluations.Source: Affinely constrained convex problems · p. 26
  • For smooth linearly constrained convex problems, ’s iALM needs O(ε^-7/4) gradient evaluations for ε-optimality; its perturbed variant needs O(ε^-1|log ε|^4), while this paper’s convex-case results are better by O(ε^-3/4).Source: Affinely constrained convex problems · p. 26

Other related methods

  • Other related approaches analyze iDGM/iALM complexity or use blockwise Gauss-Seidel or randomly selected updates, with global sublinear convergence established for the latter methods [9] [36].The review notes that these block-structure works are outside its scope.Source: Affinely constrained convex problems · p. 26

Nonergodic results

Nonlinearly constrained convex problems

  • With nonlinear inequality constraints, prior work had not shown a global convergence rate for iALM, while dual-subgradient methods for general convex problems give O(1/k) convergence.The cited methods’ iteration complexity is reported as worse than this paper’s by O(ε^-1) for convex problems and O(ε^-1/2) for strongly convex problems.Source: General convex problems · p. 27

6 Numerical results

The experiments compare quadratic penalty and three iALM parameter settings on three QCQP instances, measuring objective error, feasibility violation, and evaluation counts. Across the tests, geometrically increasing penalties generally use fewer evaluations than constant penalties, with the best error schedule varying by instance.

Experimental setup

  • The tests use three QCQP instances with n = 100 and m = 5; two are convex and one is strongly convex.The first two instances differ only in Q0, whose scale is 100 times larger in the second; the third uses full-rank Q0.Source: §6 · p. 28
  • Performance is assessed by objective-value difference and feasibility violation at both the actual iterate and weighted average, alongside gradient and function evaluation counts.The reported comparisons use ε = 10^-3 and K = 10; Table 1 includes the K = 1 quadratic penalty baseline.Source: §6 · p. 28

Results

  • Geometrically increasing penalty settings generally require fewer gradient and function evaluations than constant penalty, while the best error schedule varies by instance.Geometrically increasing penalty with constant error is best on instances one and three; adaptive error is best on instance two, whose objective has a significantly larger gradient Lipschitz constant.Source: §6 · p. 28, Table 1 · p. 29
  • The quadratic penalty method performs significantly worse than multiple iALM steps with smaller penalty parameters.Table 1 compares the quadratic penalty method, equivalent to iALM with K = 1, against three iALM settings on a QCQP instance with singular Q0.Source: §6 · p. 28, Table 1 · p. 29

7 Concluding remarks

The paper establishes ergodic and nonergodic convergence rates for iALM on general constrained convex programs and gives gradient-evaluation complexity bounds. The convex-case complexity is stated to be optimal, while the strongly convex result appears best among existing results.

Concluding remarks

  • The paper establishes ergodic and nonergodic convergence rates for iALM on general constrained convex programs.The concluding remarks report sufficient gradient evaluations of O(ε^-1) for convex objectives and O(ε^-1/2|log ε|) for strongly convex objectives.Source: §7 · p. 29
  • The O(ε^-1) convex-case iteration complexity is optimal, and the strongly convex result appears best in the literature.The paper presents the strongly convex comparison as an appearance rather than a proof of optimality.Source: §7 · p. 30

Related papers

Loading 1711.05812v2…