PaperlayerView exact revision on arXiv

Source-linked AI summary

Accelerated Safe Gradient Flow

Xuting Gao, Sonia Martínez

arXiv:2610.02433v1math.OCcs.SYeess.SY

TL;DR

Constrained optimization with safety requirements can disrupt nominal accelerated dynamics, and feasibility must be maintained throughout the trajectory. A-SGF filters a nominal accelerated flow through a second-order CBF quadratic program. It preserves anytime feasibility and the nominal rate under stated gain conditions, with the 2D example retaining s=0.1.

  • Problem

    When constraints become active, safety mechanisms can alter accelerated dynamics, so the nominal rate is not automatically retained.

    Source: §I · p. 1

  • Method

    A-SGF filters a nominal NAG-SC second-order flow through a second-order CBF quadratic program.

    Source: §I · p. 1

  • Results

    s=0.1 is retained in the numerical example; A-SGF also preserves anytime feasibility and converges to the unique constrained optimizer.

    Source: §V · p. 6, §VI · p. 6

  • Takeaways & Limitations

    Explicit HOCBF gain conditions ensure that A-SGF retains the nominal accelerated convergence-rate dependence despite its safety correction.

    Source: §IV · p. 3, B. Second-Order Gain Design · p. 6

Abstract

from arXiv · show

This letter introduces an accelerated safe gradient flow (A-SGF) for strongly convex constrained optimization problems. The A-SGF filters a nominal second-order accelerated flow through a second-order control barrier function quadratic program. We establish conditions for strict feasibility and local Lipschitz continuity of the resulting vector field, prove forward invariance of a lifted safe set, and show that its unique equilibrium is the constrained minimizer. A variational Lyapunov analysis isolates the effect of the safety correction and gives explicit conditions on the barrier gains under which A-SGF retains the same convergence rate as the unconstrained Nesterov accelerated method. A nonlinear 2D example demonstrate anytime feasibility and faster convergence of the algorithm.

I. INTRODUCTION

The introduction frames safe constrained optimization and accelerated convergence as complementary goals, then presents A-SGF as a way to combine them while addressing feasibility and rate-retention challenges.

I. INTRODUCTION

  • The SGF filters negative-gradient dynamics through control barrier functions to keep trajectories feasible while steering toward a constrained local minimizer.This is especially relevant when optimization is coupled to a physical system where intermediate infeasible solutions may be inadmissible.Source: §I · p. 1
  • For strongly convex, smooth objectives, Nesterov acceleration has 1/√κ rate dependence versus 1/κ for standard gradient flow.Here κ = L/µ.Source: §I · p. 1
  • Combining safety and acceleration is nontrivial: projection-based inertial dynamics can be nonsmooth, primal-dual flows may ensure feasibility only asymptotically, and active constraints can alter the nominal rate.The paper identifies integration of NAG-SC with SGFs as a possible route to addressing these issues.Source: §I · p. 1
  • A-SGF filters NAG-SC acceleration through a second-order CBF quadratic program, with stated conditions for well-posedness, safe-set invariance, and retention of the nominal 1/√κ rate.The paper also shows that its unique equilibrium is the constrained minimizer.Source: §I · p. 1

A. Constrained Optimization and Optimality Conditions

The paper formulates a convex constrained optimization problem and specifies assumptions that ensure a unique optimizer and support its optimality analysis.

A. Constrained Optimization and Optimality Conditions

  • The feasible set is C = {x ∈ R^n | h_i(x) ≥ 0}, and I(x) contains the constraints active at x.The problem has objective J and constraints h_i.Source: A. Constrained Optimization and… · p. 1
  • The objective is twice continuously differentiable, µ-strongly convex, and L-smooth; the constraints are three-times continuously differentiable, concave, and satisfy Slater’s condition.Slater’s condition requires a point strictly satisfying every constraint.Source: A. Constrained Optimization and… · p. 1
  • Under these assumptions, C is closed and convex with nonempty interior, and the optimization problem has a unique optimizer.Source: A. Constrained Optimization and… · p. 1
  • Slater’s condition gives strong duality and a KKT multiplier, while convexity makes the KKT conditions necessary and sufficient for global optimality.Source: A. Constrained Optimization and… · p. 2

B. Accelerated Gradient Flow

The section presents accelerated optimization as a second-order continuous-time flow and relates its convergence rate to the objective’s condition number.

B. Accelerated Gradient Flow

  • Accelerated methods admit a continuous-time interpretation as second-order dissipative gradient systems.Source: B. Accelerated Gradient Flow · p. 2
  • The nominal second-order dynamics coincide with continuous-time Heavy-Ball and Nesterov accelerated gradient methods for particular coefficients.Source: B. Accelerated Gradient Flow · p. 2
  • For a µ-strongly convex and L-smooth objective, the nominal accelerated flow has exponential convergence-rate dependence 1/√κ.κ denotes the condition number in the surrounding setup.Source: B. Accelerated Gradient Flow · p. 2

C. Safe Gradient Flow and High-Order CBFs

The section reviews the SGF safety filter and high-order control barrier functions as foundations for enforcing constraints in second-order optimization dynamics.

C. Safe Gradient Flow and High-Order CBFs

D. Problem Formulation

The paper formulates the goal of constructing a second-order constrained system that retains nominal accelerated dynamics while enforcing constraints through relative-degree-2 CBFs.

Problem 1

  • The system must enforce constraints through relative-degree-2 CBFs while retaining the nominal acceleration.The paper also seeks conditions ensuring well-defined, locally Lipschitz dynamics, no undesired feasible-set equilibria, and nominal accelerated rate dependence.Source: D. Problem Formulation · p. 2
  • The formulation targets dynamics with the nominal acceleration specified by the paper’s second-order flow.The requested properties include well-definedness, local Lipschitz continuity, and no undesired equilibria in the feasible set.Source: D. Problem Formulation · p. 2

III. ACCELERATED SAFE GRADIENT FLOW

A-SGF filters nominal acceleration through relative-degree-2 CBF constraints, yielding a constrained flow with conditions for well-definedness, safety, and equilibrium at the constrained minimizer.

Construction

  • A-SGF defines the acceleration as a minimum-norm modification of nominal acceleration satisfying the second-order CBF constraints.The resulting acceleration defines the second-order dynamical system.Source: §III · p. 2

Well-posedness

  • The safe acceleration is locally Lipschitz when the SOCBF-QP is strictly feasible and CRC holds for its active constraints.This supplies the regularity condition for the resulting A-SGF vector field.Source: §III · p. 3
  • A common direction satisfying the constraint-gradient condition, together with CRC on C, ensures strict feasibility and local Lipschitz continuity for any positive CBF gains.Under the stated conditions, the SOCBF-QP is strictly feasible throughout the lifted safe set.Source: §III · p. 3
  • Assumption II.1 supplies MFCQ but does not guarantee CRC, so CRC remains an additional regularity condition.The strict-feasibility geometry alone does not establish the CRC needed for the regularity result.Source: §III · p. 3

Safety

  • If the safe acceleration is well defined and locally Lipschitz on the lifted set, that set is forward invariant from every initial point in it.Since the lifted set includes h_i(x) ≥ 0, its invariance keeps x in the feasible set.Source: §III · p. 3

Equilibrium characterization

  • Under Assumption II.1, the only equilibrium in the lifted safe set is the constrained optimizer paired with zero velocity.Thus, A-SGF has no undesired equilibria in that set.Source: §III · p. 3

IV. ACCELERATION-PRESERVING DESIGN

The section analyzes how the CBF safety correction affects acceleration and seeks sufficient gain conditions for A-SGF to retain the nominal accelerated rate.

Acceleration-preserving design

  • The analysis seeks sufficient HOCBF gain conditions under which A-SGF retains the nominal accelerated convergence rate.It defines s := µ/L = 1/√κ for the section’s analysis.Source: §IV · p. 3
  • The section examines how the CBF safety correction affects the accelerated convergence mechanism.The supplied passage states the analysis objective but does not give the resulting gain conditions.Source: §IV · p. 3

A. Variational Interpretation and First-Order CBF Gain

The variational analysis treats the safety correction as a generalized force and studies its contribution to a Lyapunov-function derivative. It motivates matching the first-order CBF gain to the nominal exponential scale while recognizing a second-order gain mismatch.

Variational interpretation

  • The safety correction q_CBF acts as a generalized constraint force in the forced Euler–Lagrange interpretation of A-SGF.The potential and dissipation are not altered directly by the safety filter.Source: A. Variational Interpretation and… · p. 4
  • The Lyapunov analysis expresses the safety correction’s contribution as the supply Δ_CBF(x, v) = [v + s(x − x⋆)]ᵀq_CBF(x, v).The gain design is framed as controlling the work done by this generalized safety force.Source: A. Variational Interpretation and… · p. 4

First-order CBF gain

  • Choosing c_i,1 ≥ s motivates matching the first-order CBF relaxation to the nominal exponential scale.The rate-matched choice eliminates terms in h_i(x), but second-order complementarity leaves a mismatch that the second-order gain must compensate for.Source: A. Variational Interpretation and… · p. 4

B. Second-Order Gain Design

The second-order gain design modifies a Lyapunov function to account for the safety correction, then gives gain conditions under which A-SGF retains the nominal accelerated rate. The analysis applies on a relevant compact set under stated smoothness and feasibility conditions.

B. Second-Order Gain Design

  • Choosing first-order CBF gains ci,1 = s gives the stated time-derivative relation for WF.WF is the optimal scaled-Lagrangian gap plus a quadratic velocity-position term.Source: B. Second-Order Gain Design · p. 4
  • The Hessian bounds used in the analysis are imposed on a compact forward-invariant set containing the initial state.On the considered region, F is convex and M-smooth.Source: B. Second-Order Gain Design · p. 4
  • Increasing c2 enlarges the SOCBF-QP feasible set, so its minimum-norm safety correction cannot increase.The comparison applies when the first-order barrier values are nonnegative on S.Source: B. Second-Order Gain Design · p. 5
  • The auxiliary term in W cancels the mixed safety-correction term, while the chosen gains ensure decay and positive definiteness.The design selects γ and c2 so that the Lyapunov derivative is nonpositive at the required rate and W is positive definite.Source: B. Second-Order Gain Design · p. 5
  • With the stated gains, W is a valid Lyapunov function on K0 and A-SGF retains the nominal exponential-rate dependence s = 1/√κ.The result assumes a well-defined flow on S and a compact set K0 specified through the initial Lyapunov value.Source: B. Second-Order Gain Design · p. 6

V. NUMERICAL EXAMPLES

The numerical example tests A-SGF on a nonlinear two-dimensional constrained problem initialized on the boundary. The reported convergence rate is s = 0.1.

V. NUMERICAL EXAMPLES

  • s = 0.1 is the reported convergence rate for A-SGF in the nonlinear 2D example.The example uses a 1-strongly convex, 100-smooth objective, concave smooth constraints, and an initial point on the boundary.Source: §V · p. 6

VI. CONCLUSION

A-SGF converges to the unique constrained optimizer while preserving anytime feasibility. Under explicit HOCBF gain conditions, it retains the nominal accelerated flow’s convergence rate.

  • A-SGF converges to the unique constrained optimizer while preserving anytime feasibility.Source: §VI · p. 6
  • Conditions for well-posedness are established for the A-SGF dynamics.Source: §VI · p. 6
  • Explicit HOCBF gain conditions ensure A-SGF retains the nominal accelerated flow’s convergence rate.Source: §VI · p. 6

Related papers

Loading 2610.02433v1…