PaperlayerView exact revision on arXiv

Source-linked AI summary

Complexity of first order inexact Lagrangian and penalty methods for conic convex programming

Ion Necoara, Andrei Patrascu, Francois Glineur

arXiv:1506.05320v3math.OC

TL;DR

The paper addresses the overall iteration complexity of inexact first-order methods for conic convex problems, including cases where optimal Lagrange multipliers may not exist. It analyzes Lagrangian smoothing and penalty approaches, reporting complexity results across these settings and limitations for the more general conic case.

  • Problem

    Existing analyses often report outer-iteration rates, leave overall costs and smoothing comparisons incomplete, and assume optimal multipliers that may be difficult to verify or absent.

    Source: §1 · p. 2

  • Method

    The paper analyzes inexact first-order Lagrangian methods using augmented-Lagrangian or Nesterov smoothing, and fast-gradient penalty methods when optimal multipliers may not exist.

    Source: §1 · pp. 2–3

  • Results

    The analysis covers both multiplier regimes, compares smoothing approaches, and reports improvements over prior nonsmooth penalty complexity results.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    The results extend first-order complexity analysis to conic convex problems that may lack optimal multipliers, including cases where a Slater condition does not hold or is difficult to check.

    Source: §1 · p. 3

    For the more general conic problem, the authors report additional computational effort and only a lower approximation of the optimal value, unlike a setting where suboptimality estimates can be made arbitrarily accurate on both sides.

    Source: §5 · p. 29

Abstract

from arXiv · show

In this paper we present a complete iteration complexity analysis of inexact first order Lagrangian and penalty methods for solving cone constrained convex problems that have or may not have optimal Lagrange multipliers that close the duality gap. We first assume the existence of optimal Lagrange multipliers and study primal-dual first order methods based on inexact information and augmented Lagrangian smoothing or Nesterov type smoothing. For inexact (fast) gradient augmented Lagrangian methods we derive a total computational complexity of $\mathcal{O}\left(\frac{1}{\epsilon}\right)$ projections onto a simple primal set in order to attain an $\epsilon-$optimal solution of the conic convex problem. For the inexact fast gradient method combined with Nesterov type smoothing we derive computational complexity $\mathcal{O}\left(\frac{1}{\epsilon^{3/2}}\right)$ projections onto the same set. Then, we assume that optimal Lagrange multipliers for the cone constrained convex problem might not exist, and analyze the fast gradient method for solving penalty reformulations of the problem. For the fast gradient method combined with penalty framework we also derive a total computational complexity of $\mathcal{O}\left(\frac{1}{\epsilon^{3/2}}\right)$ projections onto a simple primal set to attain an $\epsilon-$optimal solution for the original problem.

1. Introduction

The introduction motivates overall iteration complexity analysis for inexact first-order Lagrangian and penalty methods, covering conic convex problems with and without optimal Lagrange multipliers. It compares smoothing approaches and extends complexity analysis to penalty methods when such multipliers may not exist.

Motivation

  • The literature review identifies three gaps: incomplete overall-cost analysis, limited comparison of smoothing approaches, and reliance on optimal multipliers that may be difficult to verify or absent.The authors note that outer-iteration rates may not reflect total work, including inner iterations such as projections.Source: §1 · p. 2

Contributions

  • The paper analyzes inexact first-order Lagrangian and penalty methods for conic convex problems both with and without optimal Lagrange multipliers that close the duality gap.Its stated contribution is a complete iteration-complexity analysis.Source: §1 · pp. 2–3
  • The analysis covers dual first-order augmented-Lagrangian methods under the assumption of optimal multipliers that close the duality gap.The stated scope includes problems with simple or smooth objective functions.Source: §1 · p. 3
  • The authors combine Nesterov smoothing with an inexact fast gradient method and report worse overall complexity than with augmented-Lagrangian smoothing.The comparison concerns projections onto the simple primal feasible set and feasible cone, though the supplied passage does not preserve the complete bounds.Source: §1 · p. 3
  • For problems that may lack optimal multipliers, the paper analyzes fast-gradient penalty methods and states that an example demonstrates tightness of its bounds.The contribution also says the smooth-objective case has a projection-complexity bound, but its order is not preserved in the supplied passage.Source: §1 · p. 3

2. Problem formulation

The paper formulates a cone-constrained convex optimization problem and specifies assumptions for its feasible sets and objective. It defines approximate solutions and introduces an inexact first-order framework for solving composite convex problems.

2. Problem formulation

  • The target is a cone-constrained convex problem with a proper, closed, convex objective, a nonempty closed convex primal set, and a nonempty closed convex constraint cone.The formulation also defines the cone's polar and notes that results extend to general normed vector spaces.Source: §2 · p. 4
  • The stated assumptions require the primal set and cones to be closed, convex, and simple, with the primal set bounded.The objective is assumed either simple or to have a Lipschitz continuous gradient on its domain.Source: §2 · p. 4
  • An ε-optimal solution must have objective-value error at most ε and constraint-cone distance at most ε.The point must also belong to the primal feasible set.Source: §2 · p. 4

2.1 A framework for inexact first order methods

  • The paper introduces an inexact first-order framework based on approximate function values and gradients for composite convex optimization.The framework is presented as a basis for subsequent methods using the Nesterov fast gradient method.Source: §2.1 · pp. 4–5
  • The smooth component is equipped with an inexact (δ, L)-oracle that returns approximate values and gradients subject to stated inequalities.The composite problem combines that smooth component with a simple, closed, convex term over a simple convex set.Source: §2.1 · p. 5
  • The Inexact Composite Fast Gradient method solves the composite problem using the oracle's approximate function values and gradients.The method's output is described as having sublinear convergence in function values, with the supplied theorem passages not preserving the complete rate.Source: §2.1 · p. 5
  • With exact information, the framework recovers FISTA when its specified momentum sequence is used and ISTA when the sequence is set to one.The passage associates these schemes with prior analyses and extensions.Source: §2.1 · p. 5

3. Inexact first order Lagrangian methods

This section analyzes inexact first-order Lagrangian methods under the assumption that an optimal Lagrange multiplier closes the duality gap. It develops augmented-Lagrangian smoothing and modified Nesterov smoothing, including inexact oracles, implementable variants, and complexity guarantees.

3. Inexact first order Lagrangian methods

  • Assumption 3.1 requires an optimal multiplier that closes the duality gap, which implies a bounded optimal multiplier.The paper notes that this assumption holds when a Slater-type condition is valid.Source: §3 · p. 6

3.1 Preliminaries

  • The dual function is reformulated as a composite function, and the paper considers augmented-Lagrangian and Nesterov smoothing to enable dual first-order methods.Standard Nesterov smoothing requires a bounded primal feasible set; the modified technique is designed to handle linear conic constraints with an unbounded cone.Source: §3.1 · pp. 6–7

3.2 Inexact first order methods for augmented Lagrangian smoothing

  • The augmented Lagrangian dual function is smooth and has a first-order (3δ, 2Ld)-inexact oracle with inner accuracy δ, whereas many earlier methods require O(δ²) inner accuracy.Source: §3.2 · p. 9

3.2.1 Inexact gradient augmented Lagrangian method

  • The inexact gradient augmented-Lagrangian analysis bounds total projections onto the primal feasible set for both simple objectives and objectives with Lipschitz-continuous gradients.The analysis combines outer iterations with the projections needed to solve each inner subproblem.Source: §3.2.1 · pp. 11–12
  • With a known bound on the dual distance, the gradient augmented-Lagrangian method can obtain an ε-optimal solution after solving the inner subproblem once.The paper relates this case to the quadratic penalty method.Source: §3.2.1 · p. 12

3.2.2 Inexact fast gradient augmented Lagrangian method

  • The inexact fast gradient method is applied to the augmented dual problem, and its dual-suboptimality estimate concerns outer iterations rather than total inner-and-outer computational cost.The analysis also proceeds to primal infeasibility and suboptimality bounds.Source: §3.2.2 · pp. 12–13
  • The inexact fast gradient augmented Lagrangian method attains an ϵ-optimal average primal point with O(1/ϵ) projections onto the simple primal set.Its projection complexity is stated to match that of the classical inexact gradient augmented Lagrangian method.Source: §3.2.2 · pp. 13–14

3.3 Adaptive inexact augmented Lagrangian method

  • The adaptive augmented Lagrangian method approximates the unknown norm of the optimal multiplier by doubling its smoothing parameter, with only a logarithmic complexity factor.It has the same complexity order as the inexact gradient method and uses a checkable stopping criterion with computable parameters.Source: §3.3 · pp. 15–16

3.4 Inexact first order Lagrangian method for a modified Nesterov smoothing

  • Modified Nesterov smoothing smooths only the Lagrangian component of the dual function, leaving its nonsmooth component unchanged, and supports an inexact first-order oracle.The oracle is specified as a (3δ, 2Ld)-oracle for the smoothed dual function.Source: §3.4 · pp. 16–17
  • For simple f, setting an optimal smoothing parameter makes the average primal point ε-optimal, although the cited excerpt omits the bound.Source: §3.4 · p. 19
  • Modified Nesterov smoothing uses significantly more projections onto U than prior augmented Lagrangian smoothing, but its optimal μ is initialization-computable, unlike the adaptive μ required in the augmented Lagrangian framework.The augmented Lagrangian parameter cannot be fixed a priori because it depends on ∥x*∥ via Rd; the Nesterov choice follows from Theorem 3.13.Source: §3.4 · p. 20

4. First order penalty methods

The section analyzes fast-gradient penalty methods when a conic convex problem may lack an optimal Lagrange multiplier closing the duality gap. It develops differentiable, smoothed nondifferentiable, and adaptive variants with overall complexity bounds.

4. First order penalty methods

  • Without assuming a gap-closing optimal Lagrange multiplier, the section analyzes penalty strategies and establishes complexity results for this broader setting.The authors describe these as among the first such complexity results for first-order penalty methods on conic problems.Source: §4 · pp. 20–21

4.1 Fast gradient differentiable penalty method

  • As the penalty parameter ρ increases, minimizers of the differentiable penalty approach original solutions; the nonsmooth penalty has a finite exactness threshold when multipliers exist.The differentiable form has good smoothness properties, while the nondifferentiable form lacks them.Source: §4 · p. 21

4.2 Fast gradient nondifferentiable penalty method

  • The nondifferentiable penalty is smoothed before applying the fast gradient method, yielding a complexity bound in projections onto K × U.With the parameter conditions in the theorem, the resulting point is ε-optimal for the original problem.Source: §4.2 · pp. 24–26

4.3 Adaptive fast gradient penalty method

  • O(1/ε^3/2) projections are required in the worst case for fast-gradient penalty methods without gap-closing multipliers, and the bound is tight.The adaptive method increases the penalty parameter sequentially; the section reports bounds for smooth and nonsmooth penalties.Source: §4.3 · pp. 26–27

5. Comparisons with previous work

The comparison section evaluates the paper's complexity bounds against prior first-order methods under different optimality criteria. It highlights both improved bounds for augmented Lagrangian methods and the additional effort associated with handling problems without gap-closing multipliers.

Comparisons with previous work

  • The paper reports that its inexact-oracle analysis is simpler and more intuitive than analyses in, with parameters that are easy to compute.It also states that the approach opens possibilities for extensions to more complex optimization models.Source: §5 · p. 28
  • O(ε^-3/2) for the original I-AL method and O(ε^-4/3) for fast I-AL improve on the O(ε^-7/4) estimate in under optimality criteria (36).With regularization, the last-primal-point complexity is O(ε^-1) under criteria (36).Source: §5 · p. 29
  • An appropriate smoothing parameter can make the number of outer iterations one, so outer-iteration rates alone do not describe total complexity.For the paper's optimality criteria, classical and fast augmented Lagrangian methods have the same complexity with optimal smoothing.Source: §5 · p. 29
  • Handling conic problems without gap-closing multipliers raises complexity from O(1/ε) to O(1/ε^3/2), and only the right-hand suboptimality bound can be made arbitrarily small.The paper characterizes the function value as a lower approximation of the optimum.Source: §5 · p. 29

6. Appendix

The appendix provides proofs for Theorems 3.4 and 3.7.

6. Appendix

  • The appendix supplies proofs for Theorems 3.4 and 3.7.Its stated scope is proof material for those two results.Source: §6 · p. 29

Appendix A.1

Appendix A.1 derives estimates for primal infeasibility and suboptimality used in the proof of Theorem 3.4.

Appendix A.1

  • The proof derives bounds on primal infeasibility and primal suboptimality to establish Theorem 3.4.It obtains the infeasibility estimate, then combines intermediate relations to establish the stated suboptimality estimate.Source: Appendix A.1 · pp. 30–31

Appendix A.2

Appendix A.2 proves Theorem 3.7 by deriving sublinear estimates for primal infeasibility and suboptimality. The proof uses the augmented dual function and bounds involving both an optimal multiplier and the zero multiplier.

Appendix A.2

  • Theorem 3.7’s stated estimates bound primal infeasibility and suboptimality.The proof obtains them from intermediate bounds and the augmented dual function.Source: Appendix A.2 · pp. 31, 33
  • The proof uses the sequence l_k and a relation attributed to to derive its intermediate bounds.It defines l_k = x_{k−1} + θ_k(x_k − x_{k−1}) and sums over its history.Source: Appendix A.2 · pp. 31–32
  • The feasibility estimate is bounded for all k ≥ 0 using the preceding inequalities.The proof then uses the optimal multiplier x* and the zero multiplier in deriving feasibility and suboptimality bounds.Source: Appendix A.2 · pp. 32–33

Appendix A.3

Appendix A.3 derives bounds for primal infeasibility and suboptimality in the smoothing setting. It selects a smoothing parameter by minimizing an intermediate bound, then applies the resulting estimates.

Appendix A.3

  • Lemma 6.1 gives an iteration-wise bound for sequences generated by Algorithm 2, for any Lagrange multiplier.The proof invokes the lemma and defines Δ(x, y) using the smoothed Lagrangian and its gradient.Source: Appendix A.3 · p. 33
  • The proof also derives a sublinear estimate for primal suboptimality.It sums inequalities using the convexity of L_µ(·, x).Source: Appendix A.3 · p. 33
  • The proof uses the zero multiplier to relate the smoothed Lagrangian to f and bound d_µ(x).It combines these observations with the feasibility-gap bound before optimizing µ.Source: Appendix A.3 · p. 34
  • Theorem 3.13’s proof derives an estimate on infeasibility after selecting the smoothing parameter.The parameter is chosen by minimizing an expression over µ, and the resulting value is substituted into the estimates.Source: Appendix A.3 · p. 34
  • The theorem’s statements are concluded from the infeasibility and suboptimality estimates.The proof compares f* with the objective and constraint expression evaluated at the averaged iterate.Source: Appendix A.3 · p. 34
Loading 1506.05320v3…