pith. sign in

arxiv: 2507.17572 · v3 · pith:6DXQVWSVnew · submitted 2025-07-23 · 💻 cs.RO

Sampling-Based Global Optimal Control and Estimation via Semidefinite Programming

Antoine Groudiev , Fabian Schramm , \'Elo\"ise Berthier , Justin Carpentier , Frederike D\"umbgen This is my paper

Pith reviewed 2026-05-21 23:46 UTC · model grok-4.3

classification 💻 cs.RO
keywords Kernel Sum of Squaresglobal optimizationsemidefinite programmingrobot localizationtrajectory optimizationrobotics controlestimation
0
0 comments X

The pith

Kernel Sum of Squares optimization solves global control and estimation problems in robotics after practical fixes turn non-polynomial tasks into semidefinite programs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper brings the Kernel Sum of Squares framework out of theory and into robotics by solving the concrete problems that arise when the method meets real control and estimation tasks. It details restarting strategies, systematic hyperparameter calibration, ways to recover actual minimizers from the relaxed solution, and hybrid combinations with fast local solvers. These steps let the approach compete with existing sums-of-squares methods on robot localization without requiring handcrafted polynomial reformulations. In high-dimensional trajectory optimization where simulators act as black boxes, the same practical toolkit finds higher-quality solutions while keeping overall runtimes comparable to purely local methods.

Core claim

KernelSOS can be applied to robot localization where it is competitive with existing SOS approaches that rely on heuristics and handcrafted reformulations, and in high-dimensional trajectory optimization with black-box simulators it can be combined with fast local solvers to uncover higher-quality solutions without compromising runtimes.

What carries the argument

Kernel Sum of Squares (KernelSOS) relaxation, which uses kernel methods to extend sums-of-squares guarantees from polynomial to non-polynomial objective and constraint functions in control problems.

If this is right

  • Robot localization tasks become solvable globally without manual conversion to polynomial form.
  • Trajectory optimization with black-box simulators gains access to better local minima through global relaxation steps.
  • Control and estimation problems in robotics can use semidefinite programming relaxations directly on non-polynomial models.
  • Hybrid global-local pipelines maintain theoretical soundness while scaling to higher dimensions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same practical toolkit could apply to other robotics estimation tasks such as simultaneous localization and mapping without new reformulations.
  • KernelSOS may reduce reliance on problem-specific heuristics across a wider range of optimal control settings.
  • Further scaling tests on dynamics with many contacts or contacts with uncertainty would clarify the current runtime-quality trade-off.

Load-bearing premise

Practical fixes for restarting, hyperparameter calibration, minimizer recovery, and hybrid local solving can be made without losing the theoretical guarantees of KernelSOS when the problems become non-parametric and high-dimensional.

What would settle it

Apply the method to a standard robot localization benchmark, recover the estimated pose, and check whether the achieved cost or localization error matches or beats handcrafted SOS baselines on the same instances.

Figures

Figures reproduced from arXiv: 2507.17572 by Antoine Groudiev, \'Elo\"ise Berthier, Fabian Schramm, Frederike D\"umbgen, Justin Carpentier.

Figure 1
Figure 1. Figure 1: Overview of the approach. This paper demonstrates the effectiveness of KernelSOS for optimization problems in estimation and control. Based on function evaluations only, KernelSOS can address non-polynomial and non-parametric problems beyond the reach of classic Sum of Squares methods. Each iteration solves a single semidefinite program, and multiple restarts yield an approximately globally optimal solutio… view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of KernelSOS with different kernels. Given samples (black crosses) of an arbitrary (possibly unknown) function 𝑓 (orange), KernelSOS minimizes a kernel-defined surrogate function (blue tones), by solving a simple SDP. When the kernel is chosen such that 𝑓 is in its Reproducing Kernel Hilbert Space (RKHS), a good estimate of the global minimum is found, even for a low number of samples. Here, 𝑓… view at source ↗
Figure 3
Figure 3. Figure 3: Calibration results for range-only localization. The localization error on a calibration dataset for different choices of kernel (Laplacian or Gaussian), kernel scale 𝜎, and regularization parameter 𝜆 is plotted. The baseline corresponds to picking the lowest-cost sample. While both kernel choices lead to similar best￾case errors, the performance of the Gaussian kernel is less sensitive to the correct choi… view at source ↗
Figure 4
Figure 4. Figure 4: Noise and time study for range-only localization. Top: Distance to ground truth as a function of the noise level in range-only localization, using the non-squared (left) and squared (right) formulation. The local solver often converges to local minima, while the (parametric) global EquationSOS and SampleSOS solvers perform consistently across noise levels and formulations. Notably, the (non-parametric) Ker… view at source ↗
Figure 5
Figure 5. Figure 5: Illustration of the surrogate cost and the benefit of restarts. The cost of the range-only problem is computed either using non-squared distances (left half) or squared distances (right half). In each block, we have on the left: real cost; center: surrogate function found by the first KernelSOS step; right: surrogate function found by the first restart (second step). Black crosses represent the known landm… view at source ↗
Figure 6
Figure 6. Figure 6: KernelSOS vs. CMA-ES in trajectory optimization. In both cases, the horizon 𝑇 is set to 4/0.005. KernelSOS results are averaged over 10 runs of the algorithm to evaluate the influence of the random samples. The shaded region represents the standard deviation for the randomness of the method. entire space from the start, while CMA-ES tends to explore the search space more incrementally. Both methods find tr… view at source ↗
Figure 7
Figure 7. Figure 7: Solution quality of local solver (FDDP) with different initializations. We compare the performance of FDDP for the double￾pendulum swing-up task, depending on the initialization. Dots are colored from yellow to blue depending on the number of iterations needed for FDDP to converge after initialization, yellow meaning lower number of iterations and therefore a better convergence. As seen in the left-most pl… view at source ↗
Figure 8
Figure 8. Figure 8: Overall convergence and runtime comparison of FDDP initialization. KernelSOS initialization reduces the number of iterations by 77% on average, leading to a similar total time as random and best-sample initialization despite the time required for KernelSOS to solve. while the problem has only two degrees of freedom, planning a trajectory requires optimizing the control inputs at each time step, resulting i… view at source ↗
read the original abstract

Global optimization has gained attraction over the past decades, thanks to the development of both theoretical foundations and efficient numerical routines. Among recent advances, Kernel Sum of Squares (KernelSOS) provides a powerful theoretical framework, combining the expressivity of kernel methods with the guarantees of SOS optimization. In this paper, we take KernelSOS from theory to practice and demonstrate its use on challenging control and robotics problems. We identify and address the practical considerations required to make the method work in applied settings: restarting strategies, systematic calibration of hyperparameters, methods for recovering minimizers, and the combination with fast local solvers. As a proof of concept, the application of KernelSOS to robot localization highlights its competitiveness with existing SOS approaches that rely on heuristics and handcrafted reformulations to render the problem polynomial. Even in the high-dimensional, non-parametric setting of trajectory optimization with simulators treated as black boxes, we demonstrate how KernelSOS can be combined with fast local solvers to uncover higher-quality solutions without compromising overall runtimes.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript applies Kernel Sum of Squares (KernelSOS) to global optimization in robotics and control. It identifies practical issues including restarting strategies, hyperparameter calibration, minimizer recovery, and hybrid use with local solvers. Demonstrations claim competitiveness with heuristic SOS methods on robot localization and, in high-dimensional black-box trajectory optimization, higher-quality solutions without runtime penalties.

Significance. If the empirical results and preservation of guarantees hold, the work could make KernelSOS a practical tool for non-convex global optimization in robotics, offering a theoretically grounded alternative to handcrafted polynomial reformulations and purely local solvers.

major comments (2)
  1. [Hybrid solver and practical considerations section] The section addressing hybrid combination with local solvers and black-box simulators does not demonstrate that restarting strategies, sampling, or hyperparameter choices preserve the tightness or validity of the underlying SDP relaxation and kernel representer theorem; this directly affects the central claim of uncovering higher-quality solutions while retaining global optimality properties.
  2. [Abstract and robot localization demonstration] Abstract and results summary provide no quantitative metrics, error bars, or explicit comparison baselines for the robot localization experiments; this makes the competitiveness claim difficult to evaluate and is load-bearing for the proof-of-concept assertion.
minor comments (1)
  1. Clarify the exact procedure for systematic hyperparameter calibration and how it avoids introducing effective degrees of freedom that could undermine parameter-free claims of the original KernelSOS framework.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their constructive comments on our manuscript. We address each of the major comments in detail below, indicating the revisions we plan to make to improve the clarity and strength of our claims.

read point-by-point responses

  1. Referee: [Hybrid solver and practical considerations section] The section addressing hybrid combination with local solvers and black-box simulators does not demonstrate that restarting strategies, sampling, or hyperparameter choices preserve the tightness or validity of the underlying SDP relaxation and kernel representer theorem; this directly affects the central claim of uncovering higher-quality solutions while retaining global optimality properties.

    Authors: We agree that the hybrid solver section would benefit from explicit discussion of how practical choices interact with the underlying theory. In the revised manuscript we will add a dedicated paragraph clarifying that restarts consist of repeated solves of the identical SDP relaxation under varied kernel hyperparameters (chosen to keep the kernel positive definite), sampling is applied only after the SDP solve for minimizer extraction via the representer theorem, and hyperparameter calibration is performed subject to the same positive-definiteness constraint. The local solver is invoked solely as a post-processing refinement step initialized from the KernelSOS candidate; the global optimality certificate therefore remains attached to the SDP solution itself. These additions will directly support the claim that higher-quality solutions are obtained without loss of the relaxation guarantees. revision: yes

  2. Referee: [Abstract and robot localization demonstration] Abstract and results summary provide no quantitative metrics, error bars, or explicit comparison baselines for the robot localization experiments; this makes the competitiveness claim difficult to evaluate and is load-bearing for the proof-of-concept assertion.

    Authors: We acknowledge that the abstract and high-level summary are currently qualitative. Although the body of the manuscript already reports quantitative localization errors, standard deviations, and direct comparisons against heuristic SOS baselines (see Section 5 and the associated figures), we will revise both the abstract and the results summary to include these specific metrics and baselines. This change will make the competitiveness statement immediately verifiable while preserving the manuscript's overall length. revision: yes

Circularity Check

0 steps flagged

No circularity: empirical application of KernelSOS with independent experimental validation

full rationale

The paper frames KernelSOS as an existing theoretical framework and focuses on practical extensions (restarting, hyperparameter calibration, minimizer recovery, hybrid local solvers) for robotics instances. Central claims rest on numerical demonstrations of competitiveness on robot localization and black-box trajectory optimization, not on algebraic identities or self-referential reductions. No load-bearing step equates a derived quantity to its own fitted input or prior self-citation by construction; results are presented as proof-of-concept on new problem instances with external benchmarks.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The work relies on the existing theoretical properties of KernelSOS and semidefinite programming; practical hyperparameters for restarting and calibration are introduced but not enumerated as fitted values in the abstract.

free parameters (1)
  • hyperparameters for KernelSOS calibration
    Systematic calibration of hyperparameters is listed as a required practical step; these values are chosen or tuned per problem instance.
axioms (1)
  • domain assumption KernelSOS provides theoretical guarantees when the problem can be cast in the required kernel form
    Invoked when applying the method to localization and trajectory problems without handcrafted polynomial reformulations.

pith-pipeline@v0.9.0 · 5715 in / 1349 out tokens · 28772 ms · 2026-05-21T23:46:54.365547+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. TinySDP: Real Time Semidefinite Optimization for Certifiable and Agile Edge Robotics

    cs.RO 2026-05 unverdicted novelty 8.0

    TinySDP is the first semidefinite programming solver designed for embedded systems, enabling real-time certifiable model predictive control with nonconvex geometric constraints on microcontrollers.

  2. KSOS-BO: Improving Sampling in Bayesian Optimization via Kernel Sum of Squares

    cs.CE 2026-05 unverdicted novelty 6.0

    KSOS-BO improves acquisition function optimization in Bayesian optimization by casting it as a kernel sum of squares semidefinite program, outperforming Sobol, DE, and CMA-ES baselines on 10/15 benchmarks with 81% ave...

Reference graph

Works this paper leans on

36 extracted references · 36 canonical work pages · cited by 2 Pith papers · 1 internal anchor

  1. [1]

    Global Optimization with Polynomials and the Problem of Moments,

    J. B. Lasserre, “Global Optimization with Polynomials and the Problem of Moments,” SIAM Journal on Optimization , vol. 11, no. 3, pp. 796–817, 2001

    work page 2001

  2. [2]

    Semidefinite programming relaxations for semialgebraic problems,

    P. A. Parrilo, “Semidefinite programming relaxations for semialgebraic problems,” Mathematical Programming, vol. 96, no. 2, pp. 293–320, 2003

    work page 2003

  3. [3]

    From coefficients to samples: A new approach to SOS optimization,

    J. Lofberg and P. Parrilo, “From coefficients to samples: A new approach to SOS optimization,” in IEEE CDC, 2004, pp. 3154–3159

    work page 2004

  4. [4]

    Exact and Approximate Solutions of Source Localization Problems,

    A. Beck, P. Stoica, and J. Li, “Exact and Approximate Solutions of Source Localization Problems,” IEEE T-SP, vol. 56, no. 5, pp. 1770– 1778, 2008

    work page 2008

  5. [5]

    The Riemannian Elevator for Certifiable Distance-based Localization,

    T. Halsted and M. Schwager, “The Riemannian Elevator for Certifiable Distance-based Localization,” Preprint, 2022

    work page 2022

  6. [6]

    Certifiably Optimal Rotation and Pose Estimation Based on the Cayley Map,

    T. D. Barfoot, C. Holmes, and F. Dümbgen, “Certifiably Optimal Rotation and Pose Estimation Based on the Cayley Map,” IJRR, 2024

    work page 2024

  7. [7]

    TEASER : Fast and certifiable point cloud registration,

    H. Yang, J. Shi, and L. Carlone, “TEASER : Fast and certifiable point cloud registration,” IEEE T-RO, vol. 32, no. 2, pp. 314–333, 2020

    work page 2020

  8. [8]

    Piecewise- Linear Motion Planning amidst Static, Moving, or Morphing Obsta- cles,

    B. E. Khadir, J. Bernard Lasserre, and V . Sindhwani, “Piecewise- Linear Motion Planning amidst Static, Moving, or Morphing Obsta- cles,” in IEEE ICRA, 2021, pp. 7802–7808

    work page 2021

  9. [9]

    Finding global minima via kernel approximations,

    A. Rudi, U. Marteau-Ferey, and F. Bach, “Finding global minima via kernel approximations,” Mathematical Programming, vol. 209, no. 1, pp. 703–784, 2025

    work page 2025

  10. [10]

    Optimal estimation of smooth transport maps with kernel sos,

    A. Vacher, B. Muzellec, F. Bach, F.-X. Vialard, and A. Rudi, “Optimal estimation of smooth transport maps with kernel sos,” SIAM Journal on Mathematics of Data Science , vol. 6, no. 2, pp. 311–342, 2024

    work page 2024

  11. [11]

    Safe and Smooth: Certified Continuous-Time Range-Only Localization,

    F. Dümbgen, C. Holmes, and T. D. Barfoot, “Safe and Smooth: Certified Continuous-Time Range-Only Localization,” IEEE RA-L, vol. 8, no. 2, pp. 1117–1124, 2023

    work page 2023

  12. [12]

    The CMA Evolution Strategy: A Tutorial

    N. Hansen, “The CMA Evolution Strategy: A Tutorial,” arXiv:1604.00772, 2023

    work page internal anchor Pith review Pith/arXiv arXiv 2023

  13. [13]

    Convex computation of the region of attraction of polynomial control systems,

    D. Henrion and M. Korda, “Convex computation of the region of attraction of polynomial control systems,” IEEE T-AC, vol. 59, no. 2, pp. 297–312, 2013

    work page 2013

  14. [14]

    LQR- trees: Feedback motion planning via sums-of-squares verification,

    R. Tedrake, I. R. Manchester, M. Tobenkin, and J. W. Roberts, “LQR- trees: Feedback motion planning via sums-of-squares verification,” IJRR, vol. 29, no. 8, pp. 1038–1052, 2010

    work page 2010

  15. [15]

    Nonlinear optimal control via occupation measures and LMI-relaxations,

    J. B. Lasserre, D. Henrion, C. Prieur, and E. Trélat, “Nonlinear optimal control via occupation measures and LMI-relaxations,” SIAM Journal on Control and Optimization , vol. 47, no. 4, pp. 1643–1666, 2008

    work page 2008

  16. [16]

    Infinite-dimensional sums-of-squares for optimal control,

    E. Berthier, J. Carpentier, A. Rudi, and F. Bach, “Infinite-dimensional sums-of-squares for optimal control,” in IEEE CDC, 2022, pp. 577– 582

    work page 2022

  17. [17]

    Convex Iteration for Distance-Geometric Inverse Kinematics,

    M. Giamou, F. Mari ´c, D. M. Rosen, et al. , “Convex Iteration for Distance-Geometric Inverse Kinematics,” IEEE RA-L, vol. 7, no. 2, pp. 1952–1959, 2022

    work page 1952

  18. [18]

    Certifiably Optimal Outlier-Robust Ge- ometric Perception: Semidefinite Relaxations and Scalable Global Optimization,

    H. Yang and L. Carlone, “Certifiably Optimal Outlier-Robust Ge- ometric Perception: Semidefinite Relaxations and Scalable Global Optimization,” IEEE T-PAMI, vol. 45, no. 3, pp. 2816–2834, 2023

    work page 2023

  19. [19]

    Rotation Averaging and Strong Duality,

    A. Eriksson, C. Olsson, F. Kahl, and T. -J. Chin, “Rotation Averaging and Strong Duality,” in IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2018, pp. 127–135

    work page 2018

  20. [20]

    SE-sync: A certifiably correct algorithm for synchronization over the special Euclidean group,

    D. M. Rosen, L. Carlone, A. S. Bandeira, and J. J. Leonard, “SE-sync: A certifiably correct algorithm for synchronization over the special Euclidean group,” IJRR, vol. 38, no. 2-3, pp. 95–125, 2019

    work page 2019

  21. [21]

    Duality-based verification techniques for 2D SLAM,

    L. Carlone and F. Dellaert, “Duality-based verification techniques for 2D SLAM,” in IEEE ICRA, 2015, pp. 4589–4596

    work page 2015

  22. [22]

    A New Method of Locating the Maximum Point of an Arbitrary Multipeak Curve in the Presence of Noise,

    H. J. Kushner, “A New Method of Locating the Maximum Point of an Arbitrary Multipeak Curve in the Presence of Noise,” Journal of Basic Engineering, vol. 86, no. 1, pp. 97–106, 1964

    work page 1964

  23. [23]

    Optimality conditions and finite convergence of Lasserre’s hierarchy,

    J. Nie, “Optimality conditions and finite convergence of Lasserre’s hierarchy,” Mathematical Programming, vol. 146, no. 1, pp. 97–121, 2014

    work page 2014

  24. [24]

    On the hardness of deciding the finite convergence of Lasserre hierarchies,

    L. F. Vargas, “On the hardness of deciding the finite convergence of Lasserre hierarchies,” AIMS Numerical Algebra, Control and Optimization, Jan. 2024

    work page 2024

  25. [25]

    A primer on kernel methods,

    J.-P. Vert, K. Tsuda, and B. Schölkopf, “A primer on kernel methods,” Kernel Methods in Computational Biology , vol. 47, pp. 35–70, 2004

    work page 2004

  26. [26]

    Non-parametric Models for Non-negative Functions,

    U. Marteau-Ferey, F. Bach, and A. Rudi, “Non-parametric Models for Non-negative Functions,” Advances in Neural Information Processing Systems (NeurIPS), 2020

    work page 2020

  27. [27]

    Bach, Learning Theory from First Principles

    F. Bach, Learning Theory from First Principles . MIT Press, 2024

    work page 2024

  28. [28]

    Optimal relative pose with unknown correspondences,

    J. Fredriksson, V . Larsson, C. Olsson, and F. Kahl, “Optimal relative pose with unknown correspondences,” in CVPR, 2016

    work page 2016

  29. [29]

    Sampling algebraic varieties for sum of squares programs,

    D. Cifuentes and P. A. Parrilo, “Sampling algebraic varieties for sum of squares programs,” SIAM Journal on Optimization , vol. 27, no. 4, pp. 2381–2404, 2017

    work page 2017

  30. [30]

    The Pinocchio C++ library: A fast and flexible implementation of rigid body dynamics algorithms and their analytical derivatives,

    J. Carpentier, G. Saurel, G. Buondonno, et al., “The Pinocchio C++ library: A fast and flexible implementation of rigid body dynamics algorithms and their analytical derivatives,” in SII, 2019, pp. 614–619

    work page 2019

  31. [31]

    Carpentier, F

    J. Carpentier, F. Valenza, N. Mansard, et al., Pinocchio: fast forward and inverse dynamics for poly-articulated systems, https : / / stack-of-tasks.github.io/pinocchio , 2015–2021

    work page 2015

  32. [32]

    Crocoddyl: An efficient and versatile framework for multi-contact optimal control,

    C. Mastalli, R. Budhiraja, W. Merkt, et al., “Crocoddyl: An efficient and versatile framework for multi-contact optimal control,” in IEEE ICRA, 2020, pp. 2536–2542

    work page 2020

  33. [33]

    ProxDDP: Proximal constrained trajectory optimization,

    W. Jallet, A. Bambade, E. Arlaud, S. El-Kazdadi, N. Mansard, and J. Carpentier, “ProxDDP: Proximal constrained trajectory optimization,” IEEE T-RO, vol. 41, pp. 2605–2624, 2025

    work page 2025

  34. [34]

    Jallet, A

    W. Jallet, A. Bambade, S. El Kazdadi, J. Carpentier, and N. Mansard, Aligator, https : / / github . com / Simple - Robotics / aligator

    work page

  35. [35]

    Boyd and L

    S. Boyd and L. Vandenberghe, Convex Optimization . Cambridge University Press, 2004

    work page 2004

  36. [36]

    Henrion, M

    D. Henrion, M. Korda, and J. B. Lasserre, The Moment-SOS Hierarchy - Lectures in Probability, Statistics, Computational Geometry, Control and Nonlinear PDEs . World Scientific, 2020. 8 APPENDIX I FINDING THE MINIMIZER VIA THE DUAL PROBLEM In this section, we provide intuition for the solution candidate given by (5). The dual problem of (4) is [35]: min 𝛼,...

    work page 2020