PaperlayerView exact revision on arXiv

Source-linked AI summary

The proximal augmented Lagrangian method for nonsmooth composite optimization

Neil K. Dhingra, Sei Zhen Khong, Mihailo R. Jovanović

arXiv:1610.04514v4math.OCeess.SYmath.DS

TL;DR

The paper studies composite optimization with a differentiable, possibly nonconvex term and a convex nondifferentiable regularizer. It uses an auxiliary variable, proximal operators, and the Moreau envelope to construct a continuously differentiable proximal augmented Lagrangian, enabling method-of-multipliers and primal-dual algorithms. The resulting framework is broader than proximal gradient methods, offers stronger guarantees and parameter updates than ADMM, and proves global or exponential asymptotic stability under convexity assumptions.

  • Problem

    Composite objectives combine a possibly nonconvex differentiable term with a nondifferentiable convex regularizer, limiting standard smooth descent and sometimes proximal-gradient applicability.

  • Method

    The paper introduces an auxiliary variable and uses the regularizer’s proximal operator and Moreau envelope to form a continuously differentiable proximal augmented Lagrangian for MM and primal-dual gradient methods.

  • Results

    The framework applies to a broader problem class than proximal gradient, provides stronger convergence guarantees and more refined parameter updates than ADMM, and establishes global or exponential asymptotic stability under convexity assumptions.

  • Takeaways & Limitations

    The methods provide differentiable optimization and distributed primal-dual dynamics for structured optimization and control problems.

Abstract

from arXiv · show

We study a class of optimization problems in which the objective function is given by the sum of a differentiable but possibly nonconvex component and a nondifferentiable convex regularization term. We introduce an auxiliary variable to separate the objective function components and utilize the Moreau envelope of the regularization term to derive the proximal augmented Lagrangian $-$ a continuously differentiable function obtained by constraining the augmented Lagrangian to the manifold that corresponds to the explicit minimization over the variable in the nonsmooth term. The continuous differentiability of this function with respect to both primal and dual variables allows us to leverage the method of multipliers (MM) to compute optimal primal-dual pairs by solving a sequence of differentiable problems. The MM algorithm is applicable to a broader class of problems than proximal gradient methods and it has stronger convergence guarantees and a more refined step-size update rules than the alternating direction method of multipliers. These features make it an attractive option for solving structured optimal control problems. We also develop an algorithm based on the primal-descent dual-ascent gradient method and prove global (exponential) asymptotic stability when the differentiable component of the objective function is (strongly) convex and the regularization term is convex. Finally, we identify classes of problems for which the primal-dual gradient flow dynamics are convenient for distributed implementation and compare/contrast our framework to the existing approaches.

I. INTRODUCTION

The paper addresses composite objectives combining a differentiable, possibly nonconvex term with a convex nondifferentiable regularizer. It develops proximal augmented-Lagrangian and gradient-flow tools to handle these problems, including structured control applications.

  • Composite objectives combine a differentiable but possibly nonconvex function with a convex nondifferentiable regularizer.
  • Such formulations arise in compressive sensing, machine learning, statistics, image processing, control, and structured controller design.
  • Proximal gradient methods require favorable proximal structure and can struggle with nondiagonal operators or difficult constraint projections.
  • Splitting the smooth and nonsmooth terms enables ADMM and broader regularizers, but nonconvex convergence guarantees are limited and parameter tuning affects convergence.
  • The proximal augmented Lagrangian uses proximal operators and the Moreau envelope to produce a continuously differentiable formulation for method-of-multipliers and primal-dual methods.
  • The framework supports regularizers promoting sparsity, low rank, or membership in a convex set, including ℓ1, nuclear-norm, and indicator regularization.

B. Existing algorithms

Existing approaches trade off tractability, splitting, and convergence guarantees. Proximal gradient can be limited by operator structure, while ADMM splits subproblems but has parameter-sensitive nonconvex convergence; MM offers stronger guarantees but traditionally requires a difficult joint minimization.

  • 1) Proximal gradient:: Proximal gradient is effective when the proximal operator of g∘T is easy to evaluate, but this often fails for nondiagonal T and difficult constraints.
  • 2) Augmented Lagrangian methods:: The augmented Lagrangian adds a quadratic penalty to the constraint violation, with y as multiplier and µ as a positive parameter.
  • 2) Augmented Lagrangian methods:: ADMM splits minimization over x and z, making the z-step a proximal evaluation and the x-step smooth, but its convergence rate depends strongly on µ.
  • 2) Augmented Lagrangian methods:: MM guarantees convergence to a local minimum for constrained nonconvex problems but requires joint minimization over x and z.
  • 2) Augmented Lagrangian methods:: Before the proposed reformulation, MM’s joint subproblem remained nonconvex and nondifferentiable, making it as difficult as the original problem.

III. THE PROXIMAL AUGMENTED LAGRANGIAN

The proximal augmented Lagrangian eliminates the nonsmooth auxiliary variable through the proximal operator and Moreau envelope. Under convexity of g, this converts joint augmented-Lagrangian minimization into a continuously differentiable problem while retaining multiplier-method applicability.

  • A. Derivation of the proximal augmented Lagrangian: The proximal augmented Lagrangian explicitly minimizes the augmented Lagrangian over z, yielding a differentiable function of x and y.
  • A. Derivation of the proximal augmented Lagrangian: Theorem 1 states that minimizing the augmented Lagrangian over (x,z) is equivalent to minimizing the proximal augmented Lagrangian over x.
  • A. Derivation of the proximal augmented Lagrangian: If f is continuously differentiable, the proximal augmented Lagrangian is continuously differentiable in x and y; if ∇f is Lipschitz, its gradient is Lipschitz.
  • B. MM using the proximal augmented Lagrangian: The resulting MM implementation inherits local-minimum convergence and supports standard differentiable optimization tools and systematic penalty updates.
  • A. Derivation of the proximal augmented Lagrangian: The construction extends to multiple primal variables and linear constraints by introducing an auxiliary z and eliminating it through explicit minimization.

B. MM using the proximal augmented Lagrangian

The proximal augmented Lagrangian makes method-of-multipliers minimization continuously differentiable while retaining broader operator flexibility than proximal gradient and more principled updates than ADMM.

  • B. MM using the proximal augmented Lagrangian: The proximal augmented Lagrangian enables MM by making the x-minimization subproblem continuously differentiable and no more difficult than ADMM's corresponding update.It is formed by constraining the augmented Lagrangian to the manifold obtained from explicit minimization over the nonsmooth variable.
  • B. MM using the proximal augmented Lagrangian: MM supports a general bounded linear operator T and can incorporate second-order information about f, unlike the stated proximal-gradient restrictions.
  • B. MM using the proximal augmented Lagrangian: MM updates the dual variable by gradient ascent with step-size 1/µ after minimizing the proximal augmented Lagrangian over x.The update uses the primal residual T(xk+1) − proxµg(T(xk+1) + µyk).
  • B. MM using the proximal augmented Lagrangian: Unlike ADMM, MM's dual update is a gradient-ascent step on the relevant Lagrange dual, whereas ADMM solves separate x and z subproblems.
  • B. MM using the proximal augmented Lagrangian: For LASSO, first-order solution costs for the MM and ADMM x-subproblems scale at the same rate, although MM is not generally reducible to matrix inversion.

1) Algorithm:

Algorithm 1 applies method of multipliers to the proximal augmented Lagrangian through iterative primal minimization, dual ascent, and adaptive parameter updates.

  • 1) Algorithm:: Each iteration approximately minimizes Lµ(x; y) over x and updates the dual variable and penalty parameter according to method-of-multipliers refinements.The minimization subproblem may be inexact, with tolerances controlling primal and dual conditions.
  • 1) Algorithm:: Gradient descent can solve the differentiable x-subproblem, with backtracking conditions such as Armijo used for step-size selection.
  • 1) Algorithm:: Proximal gradient can exploit the Moreau-envelope structure, including a proximal operator for the envelope when T = I.
  • 1) Algorithm:: Algorithm 1 initializes x0, y0, µ0 = 10^-1, µmin = 10^-5, ω0 = µ0, and η0 = µ0.1 before iterating.
  • 1) Algorithm:: L-BFGS is used to estimate the Hessian from first-order information and is guaranteed to converge for convex functions with Lipschitz continuous gradients.

Quasi-Newton method:

The gradient-flow analysis establishes global asymptotic stability under convexity and connects the dynamics to feedback systems whose nonlinearities can support exponential-stability analysis.

  • Quasi-Newton method:: If proxµg is not simply computable, numerical evaluation is required, making the primal-descent dual-ascent alternative attractive because it needs one proximal evaluation per iteration.
  • Quasi-Newton method:: Under stronger convexity assumptions, IQCs characterize the nonlinearities in the feedback representation and an LMI is used to establish global exponential stability and estimate rates.
  • Quasi-Newton method:: For convex f with Lipschitz continuous gradient and proper lower-semicontinuous convex g, the optimal primal-dual pairs are globally asymptotically stable, and x⋆ solves the original problem.
  • Quasi-Newton method:: The analysis assumes f is continuously differentiable and convex with Lipschitz continuous gradient, while g is proper, lower semicontinuous, and convex.
  • Quasi-Newton method:: The proof uses a quadratic Lyapunov candidate in shifted primal and dual variables and the firm nonexpansiveness of proxµg.
  • Quasi-Newton method:: LaSalle's invariance principle shows that the largest invariant set of the Lyapunov analysis is globally asymptotically stable.

B. Global exponential stability for strongly convex f

Under strong convexity and smoothness assumptions, the primal-dual gradient-flow dynamics are established as globally exponentially stable, with explicit conditions and rate estimates. The proof models the dynamics as a feedback interconnection and uses IQCs and an LMI-based stability analysis.

  • Stability analysis: The gradient-flow system is represented as a linear system in feedback with nonlinearities given by ∇f and the Moreau-envelope gradient of g.The nonlinearities are characterized by IQCs, enabling an LMI-based exponential-stability certificate.
  • Stability analysis: The dynamics satisfy ∥w(t) − w⋆∥≤τe^−ρt∥w(0) − w⋆∥ for some τ,ρ>0 when a positive-definite matrix P satisfies the required inequality.This is the stated ρ-exponential convergence guarantee for the feedback system.
  • Global exponential stability: µ ≥ Lf − mf guarantees ρ-exponential convergence when f is strongly convex, ∇f is Lf-Lipschitz, g is convex, and TT T is full rank.Theorem 3 provides the condition and asserts convergence to the optimal point.
  • Rate estimates: The analysis reduces the frequency-domain conditions to scalar inequalities indexed by eigenvalues of TT T, with the smallest eigenvalue sufficient for rate estimation.Positivity of the constant and ω² coefficients yields sufficient quadratic inequalities in ρ.
  • Rate estimates: Explicit rate expressions identify admissible ρ ranges and can be used to select µ≥Lf−mf to maximize the decay rate.The paper distinguishes cases according to whether mf is at least µ and provides corresponding rate bounds.
  • Scope and novelty: The paper claims this is the first global exponential-stability result for primal-dual gradient-flow dynamics in nonsmooth composite optimization with strongly convex f.It contrasts the result with prior work covering a narrower class of strongly convex smooth objectives with affine constraints.

C. Distributed implementation

The gradient-flow formulation supports distributed implementation when the objective gradient and linear operator have suitable separable or sparse structure. It also provides continuous dynamics for nonsmooth regularizers and avoids the per-iteration x-minimization required by ADMM in the compared setting.

  • Distributed implementation: When f(x)=Σfi(xi) and TT is an incidence matrix, agents compute ∇fi locally, share neighboring states, and maintain edge-associated dual variables.The graph Laplacian is TT T, so communication follows the network topology.
  • Comparison with existing methods: The proximal augmented Lagrangian yields continuous-right-hand-side gradient flows even when g is nondifferentiable.This contrasts with subgradient methods and discontinuous projected dynamics.
  • Comparison with existing methods: For distributed problems with separable f and incidence-matrix T, the method avoids solving an x-minimization subproblem at each iteration and provides a guaranteed convergence rate relative to ADMM.The comparison is stated for the distributed implementation setting discussed in the paper.
  • Graph-based formulation: Networked optimization over a shared variable can be reformulated using local variables xi and an indicator regularizer enforcing Tx=0.For strongly connected, balanced graphs, this constraint enforces consensus among the agents.
  • Graph-based formulation: For the consensus specialization, the dynamics use the graph Laplacian L and differ from the cited methods by using −ỹ instead of −Lỹ in the primal equation.The dual-derived variable ỹ lies in the orthogonal complement of the all-ones vector.
  • Discrete-time connection: Forward Euler discretization of the consensus dynamics yields a discrete-time implementation connected in the paper to EXTRA.The discretization uses step-size α.

V. EXAMPLES

The examples study edge addition in directed consensus networks and optimal placement to demonstrate the proximal augmented Lagrangian method.

  • Examples: The examples address edge addition in directed consensus networks and optimal placement as applications of the proximal augmented Lagrangian method.

A. Edge addition in directed consensus networks

The edge-addition problem balances closed-loop H2 performance with sparsity while enforcing consensus-preserving graph constraints. The formulation uses controller edge weights, a balanced-graph constraint, and a regularized objective.

  • Performance objective: The H2 objective is evaluated on a reduced deviation-from-average system after discarding the marginal average mode.The reduced coordinates use φ=VTψ with VT1=0, and the deviation energy is the squared H2 norm of the reduced system.
  • Problem formulation: The optimization minimizes closed-loop H2 performance while adding only a few controller-network edges.The controller network is represented through its graph Laplacian Lx and edge weights.
  • Graph constraints: Consensus requires the closed-loop Laplacian L=Lp+Lx to be balanced, expressed through the linear constraint 1T Lx=0 on the added-edge weights.The plant network is assumed balanced and connected, so balancing the closed loop reduces to a constraint on Lx.
  • Graph constraints: Feasible edge-weight vectors can be parameterized as z=Tx, where the columns of T span the cycle space of balanced graphs.This converts the balanced-graph condition into the structured representation used by the optimization problem.
  • Regularization: The regularization parameter γ controls the trade-off between sparsity of added edges and closed-loop performance.The vector zγ=Txγ determines the attained sparsity pattern before optimal weights are recomputed on that pattern.
  • Regularization: The nonnegative orthant indicator I+ serves as the regularizer for enforcing nonnegative added-edge weights.Indicator functions encode feasibility constraints as proper regularizers.

1) Implementation:

The implementation specializes proximal operators and Moreau envelopes for the regularizers used in the optimization problems, enabling efficient gradient evaluation and algorithm execution.

  • The implementation uses L-BFGS for the x-minimization subproblem in the proximal augmented Lagrangian method.
  • The gradient of f(x) is computed using controllability and observability Gramians associated with the plant dynamics.
  • For gs(z) := γ1^Tz + I_+(z), the proximal operator applies nonnegative soft-thresholding, while its Moreau envelope and gradient are available in closed form.
  • For gp(z) := I_{Zγ}(z) + I_+(z), the proximal operator projects onto Zγ intersected with the nonnegative orthant.
  • The Moreau-envelope gradient for gp is determined by a vector pointing from the feasible set E to v.

2) Computational experiments:

The experiments apply the proposed methods to sparse edge addition and distributed agent placement. PAL reduces solve time relative to ADMM by requiring fewer outer iterations, while the gradient-flow formulation supports constrained agent motion and distributed updates.

  • Sparse edge addition: 23.91% performance loss results from adding 2 optimal edges at γ = 3.5 relative to using all controller edges.The edge set is obtained from the γ-parameterized homotopy path, with weights optimized in a subsequent problem.
  • Computational comparison: PAL reduces overall solve time relative to ADMM because it requires fewer outer iterations, while average time per outer iteration is roughly equivalent.This comparison is reported for cycle graphs with 5 to 50 nodes and 20 to 2450 potential added edges.
  • Optimal placement problem: The primal-descent dual-ascent dynamics perform path planning for first-order agents while keeping inter-agent distances within [-1, 1].The proximal operator for the interval constraint is projection onto the box.
  • Optimal placement problem: Each agent’s state update uses information from neighboring agents through the network Laplacian.
  • Optimal placement problem: Distributed ADMM can handle separable placement objectives but may require large discrete position jumps, and its x-minimization is not distributed when the objective is nonseparable.
  • Conclusions: The concluding experiments illustrate the algorithms on edge-addition and optimal-placement problems, while the gradient dynamics are suitable for distributed implementation.
Loading 1610.04514v4…