Scaling Methods in SOS and SDPs 24th September

Location

LR7, Department of Engineering Sciences, University of Oxford, Parks Road,
Oxford, OX1 3PJ

Registration

If you wish to attend the workshop please register using the form on this link.

If you would like to contribute to the workshop with a talk or a poster please email control@eng.ox.ac.uk

Schedule

Session Details

Giovanni Fantuzzi - Taming SOS optimization: the role of polynomial bases and non-symmetric algorithms

Moment-SOS hierarchies are a powerful framework for approximating polynomial optimization problems, but they often struggle with scalability and numerical stability as problem size grows. In this talk, I will show how choosing the right bases for different polynomial spaces lets us reformulate SOS programs as structured conic programs, which can be solved efficiently and stably with non-symmetric interior-point algorithms. I will demonstrate the effectiveness of this approach on challenging problems arising from the study of differential equations.

Morgan Jones - Randomization and Regularization for Scalable SOS Optimization

The scalability of Sum-of-Squares (SOS) optimisation is often limited by the cost of solving the resulting Semidefinite Programming (SDP) problems. Second-order interior-point methods are arguably the most common approach due to their accuracy, but their memory requirements can become prohibitive for large problems. First-order methods offer a scalable alternative. In the first part of this talk, we introduce a first-order method based on regularisation that handles quadratic SOS programming problems without requiring the introduction of additional variables that would lift the problem into a higher-dimensional conic formulation.

A recurring computational bottleneck in many first-order SDP solvers is projection onto the Positive Semidefinite (PSD) cone. In the second part of the talk, we present randomised approximations to PSD projection that can be used across many solvers. We explain why a direct randomised approach can produce poor approximations: directions associated with large negative eigenvalues can dominate the initial low-rank approximation, even though PSD projection ultimately discards them. We then show how a spectral shift and scaling make the largest positive eigenvalues correspond to the dominant singular values, allowing the randomised approximation to focus on the eigendirections that matter most for PSD projection.

Andrea Iannelli - SOS and SDPs for end-to-end data-driven control of bilinear systems

We discuss an end-to-end approach to indirect data-driven stabilization of bilinear systems. Finite and noisy data are mapped to a controller that stabilizes the system with a user-specified confidence level. Tools from statistical learning theory are used to derive finite sample identification error bounds suitable for robust control design. We derive a priori bounds, which show how sample complexity scales with problem size and signal-to-noise ratio, and data-dependent ones, which are tighter and used in practice for design. Finally, both Linear Matrix Inequalities and Sum-of-Squares programs are proposed for control synthesis. The two designs offer different trade-offs between computational complexity and conservatism, as also shown in the numerical examples.

Kate Wenqi Zhu - Scaling Sum-of-Squares via Regularization-Aware Reduced Cones

Sum-of-squares (SOS) optimization provides tractable certificates for polynomial nonnegativity, but its semidefinite representations can become prohibitively large as the dimension and degree increase. In this talk, I will discuss how the structure induced by regularization can be exploited to construct substantially smaller SOS certificates for polynomial models arising in high-order nonconvex optimization. Building on recent results showing that sufficiently regularized nonnegative polynomial models admit exact SOS representations, we develop a hierarchy of regularization-aware reduced SOS cones. These cones exploit the regularization strength, Hessian curvature, tensor support and interaction structure of the underlying Taylor model, rather than treating the polynomial as an unstructured collection of monomials. We further use a lightweight learning-based selector to predict the smallest suitable cone, followed by an SDP verification and deterministic fallback procedure, so that computational savings do not compromise certification. Preliminary experiments show increasingly large reductions in Gram-matrix size relative to generic sparsity-based SOS methods as the polynomial degree grows, together with substantial speedups on regularized high-order optimization subproblems. I will discuss these results and the broader potential of combining mathematical structure with learning to make SOS optimization more scalable.

Hank Heng Yang - A Field Theory of First-Order Methods for Linear Conic Optimization

First-order methods make large-scale conic optimization computationally accessible. Their convergence dynamics, however, remain poorly understood: some instances converge rapidly, others exhibit persistent slow progress, and still others pass through multiple plateaus before entering a fast local regime.

In this talk, I will present a unified framework for understanding these behaviors by viewing an algorithm’s one-step update as a vector field. The central concept is region-wise sharpness, which measures the strength of this field relative to the distance to the solution set. This framework yields four new results. First, strict complementarity guarantees local field sharpness around an individual solution and linear convergence of first-order methods for semidefinite programming, without requiring nondegeneracy or uniqueness. Second, at certain singular solutions, the field has vanishing first-order variation in directions that leave the solution set; second-order limit dynamics characterize the resulting slow motion and explain several empirical signatures. Third, a field rigidity principle establishes setwise sharpness around the entire solution set for a class of exact Boolean Moment–SOS relaxations, allowing local linear convergence even when the limiting solution fails strict complementarity. Fourth, an afterimage principle identifies slow regions through nearby optimization problems whose solution geometries differ substantially while their algorithmic fields remain close. These regions provide certificates of long convergence transients beyond the reach of local analysis.