CS Paper Radar

Accelerated Safe Gradient Flow

Xuting Gao, Sonia Martínez

eess.SY math.OC ·submitted 2026-10-01 19:59 UTC · v1

Abstract

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.

Comment
Submitted to IEEE Control Systems Letters

Closest papers

Nearest neighbours by meaning across the whole index.

Safe Output-Regulation Flows for Constrained Optimization via Control Barrier Functions

eess.SY ·2026-11-05 ·Zihao Ren, Bingqi Liu, Lei Wang, Hongye Su, Guodong Shi
similarity 0.70
Abstract

Control-theoretic approaches to constrained optimization have been widely studied by interpreting optimization algorithms as dynamical systems. This paper formulates constrained optimization as an output-regulation problem with state constraints, where equality-constraint residuals are treated as regulated outputs and inequality constraints as state constraints. Proportional--integral feedback is employed to drive the equality-constraint residuals asymptotically to zero, while a control barrier function (CBF) safety filter is used to ensure inequality safety throughout the optimization process. We establish feasibility of the CBF filtering program throughout the inequality-feasible set and local exponential convergence of the resulting flow. Under stronger global conditions, we further prove convergence from an entire connected component of the inequality-feasible set. Since exact implementation of the flow requires solving a CBF quadratic program at each state, we further develop a flow that approximates the CBF solution through multiplier updates. Moreover, we provide a unified formulation encompassing the two proposed flows and projected primal--dual dynamics. Numerical examples demonstrate convergence, safety, and computational tradeoffs of the proposed flows.

0.13

Incremental Stability of Gradient Flows under Generalized Polyak-Łojasiewicz Inequalities and Its Implications for General Systems

eess.SY math.OC ·2026-10-29 ·Andreas Oliveira, Arthur C. B. de Oliveira, Mario Sznaier, Eduardo Sontag
similarity 0.60
Abstract

Gradient flows of twice continuously differentiable strongly convex and convex objectives are, respectively, incrementally exponentially stable and non-expansive in the Euclidean metric. In this work, we investigate to what extent these properties extend to nonconvex objectives satisfying generalized Polyak-Łojasiewicz inequalities. For objectives with a unique minimizer, we establish conditions under which the gradient flow is contracting in a state-dependent Riemannian metric and incrementally exponentially stable. For objectives with nonunique minimizers, we generalize the non-expansivity of convex objectives to incremental stability for more general nonconvex objectives. We focus on incremental stability due to its implication to convergence to equilibrium points; when paired with a Lyapunov function it implies pointwise convergence to a minimizer and continuity of the endpoint map. Along the way, we derive new structural results for incrementally stable nonlinear systems and extend the analysis to Heavy-Ball and Dynamical Inertial Newton flows.

0.28

Vector Lyapunov functions for nonconvex constrained optimization

eess.SY math.OC ·2026-11-05 ·Torbjørn Cunis, Ilya Kolmanovsky
similarity 0.60
Abstract · Extended version of submission to the 2027 European Control Conference

Nonconvex constrained optimization problems are commonly solved by a Newton method for necessary conditions (sequential linear/quadratic programming) or a barrier reformulation (interior-point methods). We present a vector Lyapunov analysis for Newton-type algorithms based on constraint violation and optimality of the primal solutions to a sequence of approximate optimization problems. We thus prove local stability and convergence by constructing a strict Lyapunov function for the primal solution.

0.33

Reciprocal-Manifold Annealed KKT Flows for Constrained Optimization: Application to the Nonconvex AC Optimal Power Flow

eess.SY math.OC ·2026-08-30 ·M Parimi, Aditi Ramteke, Rachit Mehra, Arun Mahindrakar, Navdeep Singh
benchmark similarity 0.59
Abstract

Safety-critical optimization applications, such as real-time power system operation, maintain feasibility at every intermediate step, not merely at convergence. Existing approaches either violate constraints mid-solve (interior-point methods) or enforce feasibility through per-instant quadratic programming subproblems with cubic computational cost and unbounded worst-case execution time. We propose a continuous-time optimization framework for smooth constrained nonlinear problems that preserves feasibility throughout the optimization process without requiring projection operators, quadratic programming subproblems, or other per-iteration optimization routines. The method is built around a reciprocal multiplier manifold, which establishes an explicit relationship between inequality constraints and their associated Lagrange multipliers. By designing a continuous multiplier update law, the manifold is shown to remain forward invariant, while the resulting dynamics are equivalent to continuous-time logarithmic barrier gradient descent. The proposed framework naturally extends to multiple inequality constraints, equality constraints, nonconvex feasible sets, and infeasible initial conditions. The method is further enhanced through an augmented Uzawa flow that eliminates oscillatory transients commonly observed in classical primal-dual saddle-point dynamics. The effectiveness of the proposed approach is applied to the AC Optimal Power Flow problem of IEEE 9-bus and IEEE 57-bus systems. Numerical results show convergence to solutions within 0.4\% of the benchmark optimum while maintaining strict feasibility of all constraints. A computational complexity analysis shows that the proposed dynamics reduce the per-step computational cost from cubic to linear complexity. Finally, dynamic tracking studies under time-varying operating conditions demonstrate reliable feasibility preservation.

0.24

Anytime-Feasible Gradient Descent for Constrained Optimization Under Gradient Uncertainty

eess.SY math.OC ·2026-09-20 ·Sina Sharifi, Jiarui Wang, Mahyar Fazlyab
theory similarity 0.57
Abstract

Constrained optimization is central to many engineering systems in which decisions must satisfy strict safety and operational requirements, especially in real-time settings with limited computational budgets. In such scenarios, optimization algorithms are often terminated before full convergence, making *anytime feasibility* essential for safe deployment. Existing methods that guarantee feasibility at every iterate typically rely on exact gradient information, an assumption that is often violated in practice due to measurement noise, stochastic approximations, or model mismatch. We develop an anytime-feasible first-order method for nonlinear constrained optimization under norm-bounded errors in the objective and constraint gradients. The method computes a robust search direction by solving a second-order cone program and selects a step size through safeguarded backtracking. Assuming exact function evaluations and a strictly feasible initialization, the method preserves strict feasibility and guarantees sufficient objective decrease whenever the computed search direction is nonzero. We establish a uniform positive lower bound on the accepted step sizes, an O(1/K) bound on the average squared search direction norm, and convergence of the search directions to zero. We also show that a zero search direction at a strictly feasible point certifies approximate first-order stationarity. We validate the proposed method on a multi-agent navigation task in cluttered environments and show that it maintains collision-free trajectories despite noisy gradient information.

0.21

First-order smoothed exact-penalty methods for equality-constrained regularized nonconvex optimization

cs.LG math.OC ·2026-11-15 ·Shiji Zuo, Qihang Lin, Wei Liu, Yangyang Xu
theory similarity 0.57
Abstract

We consider regularized nonconvex optimization over a closed convex set $\mathcal{X} \subseteq \mathbb{R}^d$, which involves a convex nonsmooth regularizer $r$ in the objective and $n$ smooth equality constraints. To find a near-KKT point of the problem, we propose a prox-linear first-order method, named as SEPi-Prox, based on a smoothed exact-penalty formulation. At each outer iteration of SEPi-Prox, a strongly convex prox-linear subproblem is formed and solved inexactly to a sufficient accuracy. Under a local non-singularity condition that is weaker than some other commonly used regularity conditions or constraint qualifications, SEPi-Prox finds an $ε$-KKT point within $O(ε^{-2})$ first-order oracle calls, matching the lower bound for unconstrained smooth nonconvex optimization. We employ Nesterov's accelerated proximal-gradient method (APG) and a dual cutting-plane method (DCP) for the prox-linear subproblems. Let $\mathcal{C}_{\mathrm{FO}}$ and $\mathcal{C}_r$ denote the numbers of arithmetic operations of evaluating one first-order oracle and one proximal mapping of $r$ over $\mathcal{X}$, respectively. Then SEPi-Prox requires $\widetilde{O}(\mathcal{C}_{\mathrm{FO}}ε^{-2} + (dn + \mathcal{C}_r)ε^{-5/2})$ and $\widetilde{O}((\mathcal{C}_{\mathrm{FO}} + dn^2 + n\mathcal{C}_r + n^{3.373})ε^{-2})$ total arithmetic operations to produce an $ε$-KKT point, respectively by using APG and DCP as the subsolver. The latter result is preferable when $n$ is small and nearly matches the optimal dependence on $ε$. Numerical experiments on instances of the multi-class Neyman-Pearson classification demonstrate the efficiency of SEPi-Prox with both subsolvers.

0.06

Non-Euclidean Gradient Descent Has Many Edges of Stability

cs.LG math.OC ·2026-10-10 ·Peter Zaika, Zakhar Shumaylov
theory similarity 0.56
Abstract

Recent observations that deep learning models train at the edge of stability have renewed interest in understanding stability properties of classical optimization algorithms. For quadratic objectives, standard gradient descent has a sharp stability threshold: it converges from every initialization when $η<2/L$, diverges from almost every initialization when $η>2/L$, and diverges from every nonzero initialization when $η>2/μ$. For non-Euclidean gradient descent, the corresponding known guarantees are weaker: convergence holds for every initialization when $η<2/S$, where $S$ is the generalized sharpness, while every nonzero initialization diverges when $η>2/μ$. The behavior in the intermediate regime $2/S<η<2/μ$ is not fully characterized. We show that Hilbertian norms are the only ones for which $2/S$ is an almost-everywhere sharp threshold for every positive-definite quadratic objective. Using linear conjugacy between non-Euclidean and Euclidean gradient descent, we show that for general norms the intermediate regime can contain arbitrarily many edges of stability associated with distinct attracting directions. We identify a forward-invariant region of exponentially divergent directions beyond the generalized stability threshold. When the directions of minimum curvature are finite and nondegenerate, we prove that, sufficiently close to $2/μ$ from below, only their invariant directions remain convergent. We give smooth two-dimensional constructions with arbitrarily many distinct thresholds, arbitrarily large relative threshold separation and show these properties to be stable.

0.12

A Lifted Hessian-Riemannian Gradient Flow for LQR Synthesis under Passivity Constraints

eess.SY math.OC ·2026-11-16 ·Armin Gießler, Sören Hohmann
theory similarity 0.56
Abstract

The static state-feedback gain that renders a linear system passive at an external port and minimizes a linear quadratic regulator (LQR) cost cannot be computed by convex optimization, since the passivity certificate and the LQR cost are coupled bilinearly through the common gain. A previous indirect approach restricts the gain to a convex inner approximation of the passivity region, which is conservative and whose construction scales exponentially with the number of gain entries. This paper proposes a direct approach. The set of strictly passivating gains is the image of a convex lifted set of inverse storage matrices and transformed gains. We describe this set by a strict linear matrix inequality and an affine equality for every feedthrough matrix with positive semidefinite symmetric part, including feedthrough matrices with a singular symmetric part, and minimize the LQR cost over it by a gradient flow whose metric is the Hessian of a logarithmic barrier. For multi-input systems, this Hessian is singular along gain changes that preserve the storage function, and we complete the metric along these directions by the metric of the gain space. We prove that the flow exists for all times, that every gain along the flow is strictly passivating with an explicit storage function, and that the cost decreases monotonically while the gains remain in a compact set of stabilizing gains. Numerical examples show that the flow attains a lower cost than the indirect approach, that the completion is required for multi-input systems, and that the flow can converge to a local minimizer on nonconvex passivity regions.

0.25