Exact certification for conic optimization over quadratic modules: partitions of unity and recession directions
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.
Related
- Optimal Convergence of Quadratic Not-a-Knot Spline Interpolation on Arbitrary Partitions
- SOVER: Formal Certification of Optimization Reformulations via LLM-Assisted SMT Verification
- Exact Risk-Complexity Laws for Projective Boundaries in Scenario Optimization and Distribution-Free Certification
- Discrete Phase-Shift Optimization of Reconfigurable Intelligent Surfaces using Uniform Reference Directions
- A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model
BibTeX
@misc{henrion2026exact,
title = {{Exact certification for conic optimization over quadratic modules: partitions of unity and recession directions}},
author = {Didier Henrion and Alaa Ibrahim and Victor Magron},
howpublished = {HAL},
year = {2026},
month = nov,
url = {https://hal.science/hal-05850754v1},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Exact certification for conic optimization over quadratic modules: partitions of unity and recession directions
AU - Didier Henrion
AU - Alaa Ibrahim
AU - Victor Magron
PY - 2026
DA - 2026/11/03
PB - HAL
UR - https://hal.science/hal-05850754v1
AB - 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.
ER -