Source-linked AI summary
Accelerated primal--dual dynamics and algorithms for convex optimization with nonlinear inequality constraints
Xin He
TL;DR
The paper addresses whether Nesterov-type primal–dual multiplier methods can handle convex optimization with nonlinear inequality constraints across continuous and discrete time. It develops such a framework and establishes accelerated rates for both objective residual and nonlinear feasibility.
Problem
A Nesterov-type primal–dual multiplier framework with compatible continuous- and discrete-time formulations remains less developed for convex optimization with nonlinear inequality constraints.
Method
The paper develops a continuous-to-discrete accelerated primal–dual framework using tangent extrapolation for nonlinear constraints and a projected PHR multiplier.
Results
O(t^-2) continuous-time rates and O(k^-2) discrete-time rates hold simultaneously for the objective residual and nonlinear feasibility without strong convexity.
Takeaways & Limitations
The continuous and discrete results provide two realizations of the same multiplier-based acceleration mechanism for nonlinear inequality constraints.
Takeaways & Limitations
The discrete analysis addresses convergence over outer iterations but does not include computational cost.
Abstract
from arXiv · showhide
We consider convex optimization with nonlinear inequality constraints and develop a primal--dual multiplier framework that is consistent in continuous and discrete time. We first propose continuous-time dynamics with Nesterov-type vanishing damping $α/t$, together with suitable extrapolations of the dual variable and the nonlinear constraint mapping. Under convexity assumptions and $α\geq3$, we establish $\mathcal O(t^{-2})$ convergence rates for both nonlinear feasibility and the objective residual. We then derive an inexact accelerated primal--dual algorithm through a compatible discretization of a perturbed version of the dynamics. For composite convex objectives, a weighted summability condition on the primal inexactness yields the $\mathcal O(k^{-2})$ rates for feasibility and the objective residual, thereby matching the accelerated rates of their continuous-time counterparts. To the best of our knowledge, this is the first Nesterov-type primal--dual multiplier framework for convex optimization with nonlinear inequality constraints.
1 Introduction
The paper develops a Nesterov-type primal–dual multiplier framework for convex optimization with nonlinear inequality constraints, linking continuous-time dynamics and discrete algorithms. It addresses the difficulty that affine-constraint acceleration mechanisms do not directly extend to nonlinear mappings, while establishing matching accelerated rates for objective residual and feasibility.
- Problem formulation: The problem minimizes a convex objective over a feasible set defined by componentwise convex, continuously differentiable inequalities, under a standard constraint qualification.The feasible set is X := {x : g(x) ≤ 0}; Slater’s condition is given as an example of the assumed qualification.
- Main contributions: The paper gives an affirmative continuous-to-discrete framework for obtaining accelerated primal–dual rates without strong convexity.Its stated questions concern compatible formulations and O(t^-2), O(k^-2) rates for objective residual and constraint violation.
- Motivation: Nesterov-type primal–dual acceleration is difficult for nonlinear constraints because primal extrapolation and tangent constraint extrapolation generally differ.This breaks the direct transfer mechanism available for affine constraint mappings.
- Main contributions: The continuous-time dynamics use Nesterov-type inertial terms, an extrapolated dual variable, and tangent extrapolation of the nonlinear constraint mapping.The tangent constraint extrapolation is chosen to remain compatible with the inertial terms in the Lyapunov analysis.
- Main contributions: The resulting continuous dynamics achieve simultaneous O(t^-2) rates for nonlinear feasibility and objective residual.The framework couples the nonlinear constraint mapping to a second-order dual evolution through tangent extrapolation.
- Main contributions: A compatible discretization yields an inexact accelerated primal–dual algorithm for composite convex objectives, with weighted summability of primal errors and rates matching O(t^-2).The algorithm retains primal and dual inertial extrapolations, nonlinear constraint extrapolation, and projected multipliers while permitting inexact primal subproblem solves.
2 Accelerated primal-dual dynamics
The paper constructs a globally well-posed Nesterov-type primal–dual dynamical system for nonlinear inequality constraints and proves accelerated feasibility and objective-residual rates. Its analysis combines tangent constraint extrapolation, projected PHR multipliers, and a Lyapunov energy estimate.
- Construction of the dynamics: The system uses vanishing damping α/t, velocity extrapolations of primal and dual variables, a tangent constraint extrapolation, and a projected multiplier.The parameters satisfy β > 0, σ > 0, α ≥3, and 2 ≤γ ≤α −1.
- Construction of the dynamics: The dynamics combine Nesterov-type inertia with the PHR augmented-Lagrangian primal–dual structure and tangent extrapolation for nonlinear constraints.The tangent extrapolation is introduced because direct inertial extrapolation is not compatible with nonlinear constraint mappings.
- Well-posedness and energy estimates: A unique solution exists globally for every initial point under convexity, continuous differentiability, and locally Lipschitz continuous gradients.Global existence follows by extending any finite-time maximal solution after establishing boundedness through the Lyapunov estimate.
- Well-posedness and energy estimates: The energy function E is nonincreasing, while the primal and dual velocities satisfy ∥˙x(t)∥ + ∥˙λ(t)∥ = O(t−1).The energy remains nonnegative and bounded by its initial value, which yields bounded trajectories and supports the global analysis.
- Convergence rate analysis: O(t−2) convergence holds simultaneously for nonlinear feasibility and the objective residual without strong convexity.The feasibility estimate is derived from the dual projection structure and combined with the saddle-point property to control the objective residual.
- Convergence rate analysis: The convergence proof first bounds the positive-part constraint violation, then separately estimates the potentially signed objective residual using an auxiliary energy.Because trajectories need not be feasible, the objective residual requires separate upper and lower estimates.
3 Inexact accelerated primal–dual algorithms
The paper derives an inexact accelerated primal–dual algorithm by discretizing perturbed Nesterov-type dynamics for convex objectives with nonlinear inequality constraints. The scheme combines inertial extrapolations, nonlinear constraint handling, projected multiplier updates, and inexact primal solves while preserving accelerated convergence rates.
- Algorithm construction: The algorithm is obtained by discretizing perturbed continuous-time dynamics with Nesterov-type inertial extrapolations for both primal and dual variables.The nonlinear constraint mapping is extrapolated alongside the primal and dual variables.
- Algorithm construction: The smooth objective term is evaluated explicitly, while the nonsmooth term and projected PHR coupling are treated implicitly at the new primal iterate.This explicit–implicit splitting produces the discrete primal–dual system.
- Inexact primal updates: The primal subproblem is 1/τ-strongly convex, giving a unique exact minimizer and supporting inexact solutions controlled by ε_k.An inexact update corresponds to a τ ε_k+1^2/2-optimal solution, and ε_k+1=0 recovers the exact update.
- Inexact primal updates: Algorithm 1 uses α≥3, 2≤γ≤α−1, and 0<τ≤1/L_ϕ, with parameters inherited from the continuous dynamics.The discrete iterates satisfy the perturbed discrete dynamics for suitable primal perturbations.
- Convergence analysis: The convergence analysis uses a discrete energy sequence whose nonnegativity and boundedness imply bounded iterates and O(k^-1) successive differences.The auxiliary quantities U_k and V_k are uniformly bounded, leading to bounded primal and dual sequences.
- Convergence analysis: O(k^-2) rates hold for both nonlinear feasibility and the objective residual under the weighted summability condition on primal inexactness, without strong convexity.These discrete rates match the O(t^-2) rates of the continuous-time dynamics.
4 Conclusions
The paper presents a Nesterov-type primal–dual multiplier framework with compatible continuous- and discrete-time realizations for convex optimization with nonlinear inequality constraints. Both formulations achieve accelerated rates for objective residual and nonlinear feasibility, while the discrete analysis leaves inner primal-solve complexity unresolved.
- Conclusions: The continuous-time dynamics and the inexact discretized algorithm both achieve O(t^-2) or O(k^-2) rates for objective residual and nonlinear feasibility.The discrete guarantee requires a weighted summability condition on the inexactness sequence.
- Conclusions: The continuous and discrete results are described as two realizations of the same multiplier-based acceleration mechanism.
- Conclusions: The discrete analysis covers outer-iteration convergence but does not include the computational cost of solving the nonlinear primal subproblems.Future work is to connect an inner solver's stopping criterion to the inexactness sequence and derive overall oracle complexity.
A Technical Lemmas
The appendix collects technical lemmas supporting projection identities, boundedness arguments, and convergence estimates for continuous and discrete sequences. These results control iterates, increments, positive-part constraint quantities, and auxiliary weighted recurrences.
- Projection lemmas: Metric projection onto a closed convex set is characterized by a variational inequality involving the projected point and every point in the set.
- Continuous-time estimates: A continuous-time boundedness lemma shows that a weighted bound on a trajectory and its derivative yields boundedness of the trajectory and of the weighted derivative.
- Discrete estimates: The discrete analogue establishes bounded iterates and O(k^-1) successive differences for the primal sequence.
- Sequence estimates: A nonnegative-sequence lemma converts a weighted recursive inequality into a uniform supremum bound.
- Sequence estimates: A componentwise-monotone sequence lemma bounds positive parts of accumulated vector quantities when the driving sequence and correction terms satisfy uniform bounds.
- Sequence estimates: The discrete proof expands weighted recurrences using coefficients ω_j,k and monotonicity of the correction sequence before taking a supremum over k.