CS Paper Radar

Optimizing Lyapunov Certificates via Stability-Preserving Quadratization for Polynomial Systems

Yubo Cai, Gioele Zardini

cs.SC math.OCeess.SY ·submitted 2026-09-16 16:08 UTC · v1
benchmark

Abstract

Region-of-attraction (ROA) certificates for polynomial systems become expensive as state dimension and degree grow: direct sum-of-squares (SOS) formulations require combinatorially growing monomial bases. Quadratization represents a polynomial vector field exactly on an invariant manifold of a quadratic system, allowing a quadratic Lyapunov function to certify the ROA. For a fixed lift, stabilizer gains shape the off-manifold extension and transverse dynamics, while representation gauges change the matrix representation but not the vector field. Both affect the spectral-norm certificate, yet prior work fixes the gain by a feasibility heuristic before optimizing the gauge. We formulate optimal dissipative quadratization (ODQ), jointly designing gains and gauges for a fixed monomial lift, reference extension, stabilizer factorization, and Lyapunov weight $Q=I$. Gains lie in a prescribed compact Hurwitz box. At each gain, an exact semidefinite program globally minimizes the spectral-norm bound over the gauge. Residual-aware bounds yield a certified closed Lyapunov sublevel set, accounting for the floating-point Lyapunov residual. Under our stated assumptions, every accumulation point of the idealized outer search is box-Clarke stationary. A finite run returns the best independently verified candidate; global optimality of the gain search is not claimed. On a planar quintic, optimizing the gain increases the certified area by a factor of $2.238$ over a matched zero-gain gauge. Across 16 heterogeneous polynomial systems with stabilizer freedom, ODQ improves on both fixed-gain lifted baselines. All 36 ODQ runs on the relay benchmark complete, and all 27 repeat-level comparisons across nine fully paired cases favor ODQ over an SOS baseline with a fixed quadratic Lyapunov function in both the fixed-direction proxy and construction time. Broader comparisons with direct SOS methods remain mixed.

Comment
43 pages, 4 figures, 7 tables; includes appendices

Closest papers

Nearest neighbours by meaning across the whole index.

Tensor-Algebraic Framework for Nonlinear Control: Spectral Stability Analysis and Controller Design of Polynomial Systems

eess.SY ·2026-11-16 ·Shaoxuan Cui, Guofeng Zhang, Hildeberto Jardon-Kojakhmetov, Ming Cao
similarity 0.63
Abstract

Matrices provide an algebraic foundation for systems and control, whereas an analogous tensor-based framework for general nonhomogeneous polynomial dynamics is still lacking. This paper addresses this gap by developing a tensor-algebraic framework that connects tensor structure, spectral properties, Lyapunov stability, and controller synthesis. We first establish stability conditions based on positive-definite, copositive, and P-tensors for homogeneous and nonhomogeneous polynomial systems. We then introduce an extended tensor-eigenvalue problem (ETEP) for general multivariate polynomials, yielding a spectral-variational characterization of positivity through one interior and two boundary spectral quantities, and consequently a stability test for polynomial vector fields. For controller synthesis, we develop an unfolding-based U-eigenvalue relaxation that combines a positive-definite anchor with a near-positive-semidefinite higher-order part, leading to a convex semidefinite program. The conservatism of the relaxation is explicitly characterized, and an explicit guaranteed domain-of-attraction bound is derived. Numerical examples demonstrate positivity certification beyond direct SOS representations and substantially lower computation time than SOS-based synthesis in the considered example. These results establish a systematic tensor-spectral methodology for the analysis and control of polynomial systems with higher-order interactions.

0.19

Stability Transfer for Autonomous Systems via Higher-Order Taylor-Truncated Lyapunov Certificates

eess.SY math.OC ·2026-10-13 ·Jose D. Hoyos, Zehui Lu, Shaoshuai Mou
published similarity 0.62
Abstract

We develop analytical sufficient conditions for certifying the local asymptotic stability of nonlinear autonomous systems based on Lyapunov functions derived from their finite-order Taylor polynomial approximations. This approach translates the stability analysis problem from the original nonlinear dynamics to a more computationally tractable polynomial domain. The derived conditions allow for the explicit calculation of a guaranteed inner approximation of the region of attraction ($\mathrm{ROA}$). We show how sum-of-squares (SOS) programming and grid search can be used to systematically search for polynomial Lyapunov functions that yield a large certified threshold radius and extract a certified invariant set inner approximation of the $\mathrm{ROA}$ of the nonpolynomial original system. The framework is then applied to a control tuning problem: finding reduced-effort Linear Quadratic Regulator (LQR) controllers that ensure that a given initial state of interest belongs to the certified $\mathrm{ROA}$ of the nonpolynomial closed loop system. The effectiveness of the overall methodology is demonstrated using a pendulum with nonlinear damping and a nonlinear control system.

0.29

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.57
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.28

Succinct Infinite-Horizon Lyapunov and LQR Value Problems Are BQP-Complete

cs.CC quant-pheess.SYmath.OC ·2026-11-09 ·Mohamed Serry, Jun Liu
theory similarity 0.56
Abstract

Fundamental tasks in linear systems analysis and control require evaluating infinite-horizon output energies for autonomous systems and optimal value functions for controlled systems. These quantities are characterized by Lyapunov and algebraic Riccati equations, respectively. In this work, we study promise problems for their evaluation when the system matrices are sparse and represented succinctly by Boolean circuits specifying their nonzero entries, with input length polynomial in the logarithm of the system dimension. For dissipative autonomous systems with coordinate-vector initial states, we define the succinct Lyapunov value problem (SLV). Its extension to linear-quadratic optimal control is the succinct LQR value problem (SLQRV). We prove that SLV is $\BQP$-hard: every problem in bounded-error quantum polynomial time ($\BQP$) reduces to it in polynomial time. We then establish that the more general SLQRV problem admits a quantum algorithm running in time polynomial in the succinct input length. Since SLV is a special case of SLQRV, both problems are $\BQP$-complete. Consequently, unless bounded-error probabilistic polynomial time coincides with $\BQP$, no classical randomized algorithm can solve either problem on all promised instances in time polynomial in the succinct input length.

0.28

Safe Stabilising Full-Order Affine Control Barrier Functions for Linear Systems (Extended)

eess.SY ·2026-09-11 ·Faisal Lawan, Joaquin Carrasco, Lanlan Su
theory similarity 0.55
Abstract · 9 pages, 3 figures

Control barrier function safety filters enforce constraints by modifying a nominal input, but the resulting switching can destabilise the closed loop even when the nominal and filtered modes are individually stable. This paper presents a design framework for safe and globally exponentially stabilising controllers for linear systems with a single full-relative-degree affine constraint. We show that the filtered-mode spectrum is fixed by the barrier tuning and is independent of the plant, nominal controller, and quadratic-program weighting. This structure yields an explicit nominal controller for which the safety filter remains inactive everywhere. For a prescribed nominal controller, we prove that the nominal and filtered modes admit a strong common quadratic Lyapunov function if and only if the ratio of the nominal characteristic polynomial to the barrier polynomial is strongly strictly positive real. This equivalence characterises the existence of a common quadratic Lyapunov and provides a scalar frequency-domain test, along with an explicit interval of admissible gains. Building on these results, the extended analysis derives an explicit common storage function and reduces an existing LMI synthesis condition to a feasibility test in a single matrix variable. A flexible two-mass example explains a known instability mechanism and demonstrates how the proposed design restores safety and global exponential stability.

0.58

LLM2Cert: LLM Synthesis of Certificates with SMT/Lean Verification

eess.SY cs.AIcs.LGmath.OC ·2026-10-21 ·Zhipeng Cao, Peiyang Song, Nikolaus Vertovec, Weiru Cui, Zhihao Yang +4 more
benchmarkcode/data similarity 0.55
Abstract · 59 pages, 3 figures. Equal contribution: Zhipeng Cao and Peiyang Song. Equal advising: Bai Xue and Alessandro Abate

Lyapunov functions and barrier certificates give state-space guarantees of stability and safety, but synthesizing and verifying them---especially for nonlinear, high-dimensional systems---remains an open challenge. Existing pipelines verify candidates with numerical solvers (sum-of-squares programs), interval methods, or satisfiability-modulo-theories (SMT) solvers, which often require relaxations, are conservative, or scale poorly with model dimension and nonlinearity. These limitations have also shaped benchmark design: standard test suites are dominated by low-dimensional polynomial systems chosen to suit what solvers can handle rather than what engineering applications require. We address both sides of this challenge. First, we introduce DynaCertBench, a benchmark of 105 instances: 80 non-redundant systems curated from the literature, extended with high-dimensional and control-constrained variants and new nonlinearly coupled systems, comprehensively spanning stability, region-of-attraction, forward-invariance, and safety tasks. Second, we present LLM2Cert, an LLM-driven framework that synthesizes candidate certificates and verifies them against their proof obligations: each obligation is routed to an SMT solver or directly to the Lean Proof-Repair agent. On DynaCertBench, LLM2Cert verifies 81 of 105 instances ($77.1\%$), a $17.1$ percentage point improvement over one-shot proposal without feedback. On the 81 fixed certificates, LLM2Cert verifies 22 that All-SMT leaves unresolved. Code and data are available at https://github.com/FormalCert-AI/llm2cert.

0.48

Exact certification for conic optimization over quadratic modules: partitions of unity and recession directions

cs.SC math.OC ·2026-11-04 ·Didier Henrion, Alaa Ibrahim, Victor Magron
similarity 0.55
Abstract

We consider linear conic problems whose cone is a product of truncated quadratic modules, the sum-of-squares (SOS) side of the moment-SOS hierarchy. A floating-point solution is turned into an exact rational certificate in three steps: rounding, repair of each block residual by a constant, and absorption of the constants along a recession direction of the problem. The repair relies on strict partitions of unity in the quadratic modules. We characterize their existence, relate the canonical one to the analytic center of the dual pseudo-moment cone, Christoffel-Darboux polynomials and Pell equations, and we derive closed-form rational partitions for balls and boxes. The loss incurred by the certification is the optimal value of a recession problem, equal to a support function of the masses of the dual feasible pseudomoments. The method is illustrated on polynomial optimization, volume computation and positivity of polynomials along D-finite trajectories.

0.26

Hardness of Approximation for Polynomial Optimization over Sphere for Linear Programming Relaxation Hierarchy

cs.CC ·2026-11-06 ·Mrinalkanti Ghosh
theory similarity 0.54
Abstract

Semidefinite programming (SDP), particularly the sum-of-squares (SoS) hierarchy, provides $n^{O(q)}$-time approximation and certification algorithms for optimizing degree-$d$ homogeneous polynomials on the unit sphere. For arbitrary inputs, degree-$q$ SoS gives a powered-objective approximation factor $O_d((n/q)^{d/2-1})$ [BGGLT17]. For random order-$d$ tensors, degree-$d$ SoS has an integrality-gap lower bound of $2^{-O(d)}(n/d)^{d/4-1/2}$ relative to the true spherical maximum; lower bounds also extend to growing SoS degree in tensor PCA [BGL17,HKP17]. We establish lower bounds for weaker linear-programming relaxation hierarchies. Our degree-$q$ moment LPs impose the sphere identities and any prescribed, instance-independent family $\mathcal{G}$ of valid polynomial inequalities of degree at most $q$. They include Sherali--Adams-type product hierarchies. For every even $d\ge2$, constant $C>0$, and $q$ satisfying $2d | q$ and $2d\le q\le n$, every such relaxation with at most $n^{Cq}$ tests has instances $P$ satisfying \[ \frac{\mathrm{PowLP}_{q,\mathcal{G}}(P)}{\|P\|_\infty}\ge \frac{c_{d,C}}{\sqrt{q\log n}}\left(\frac nq\right)^{d/2-1/2}.\] Here $\|P\|_\infty$ is the maximum absolute value of the polynomial over the sphere and $\mathrm{PowLP}_{q,\mathcal{G}}(P)$ is the relaxed objective. The exponent $d/2-1/2$ improves the leading dependence on $d$ relative to the $d/4$-type exponents in prior random-tensor SoS lower bounds. Our LP hierarchies impose weaker positivity conditions than semidefinite moment relaxations. It leaves open whether analogous degree dependence can be achieved in lower bounds for SDP hierarchies.

0.25