The Algorithm That Sneaks Past Math's Hidden Bottleneck

The Algorithm That Sneaks Past Math's Hidden Bottleneck

In the basement of applied mathematics, a quiet efficiency revolution has been unfolding. Optimization solvers—the engines that find the best solution among countless possibilities—are getting faster, smarter, and able to tackle problems that would have brought previous generations of researchers to their knees. But even these modern tools stumble on a particular class of problems that sits at the intersection of polynomial algebra and convex geometry. The stumbling isn't dramatic. It doesn't produce error messages or obvious failures. It just... slows down. Sometimes glacially. And for decades, the standard fix involved making problems artificially larger, then wrangling with the consequences.

A paper published in July 2026 by Gabriel Machado, Ross Drummond, and Morgan Jones at the University of Sheffield proposes something different. Their approach, called "lifting-free" regularization, solves these problematic optimization tasks without expanding them first. The results are striking: their method runs 40 percent faster than the best existing solvers on constrained regression problems, handles significantly larger problem instances than commercial software can manage, and its memory footprint scales elegantly with problem structure rather than exploding combinatorially. It's a different way of thinking about an old problem—one that essentially says, "What if instead of making the problem bigger to solve it, we made it slightly different in a way that lets the original structure do the work?"

The implications ripple outward. System identification, where engineers reconstruct mathematical models from experimental data, relies heavily on these computations. Machine learning applications increasingly require certifying that learned functions have certain properties—safety guarantees, stability conditions—that map naturally onto this mathematical framework. Control systems that keep drones stable or power grids balanced depend on solving these optimizations in real time. Speedups here translate directly into smarter systems, faster design cycles, and optimization problems that were previously intractable becoming routine.

The Science

To understand what Machado, Drummond, and Jones accomplished, you need to understand the problem they're solving—and why that problem has historically been so vexing.

The underlying task is called sum-of-squares (SOS) optimization. At its core, it's about polynomials—mathematical expressions built from variables raised to powers and added together. The polynomial x² + 2xy + y² is sum-of-squares because it equals (x + y)². But not all polynomials can be rewritten this way. A fundamental result in algebra tells us that a polynomial can be expressed as a sum of squares of polynomials if and only if it's globally nonnegative—meaning it never goes below zero, no matter what values you plug in for its variables.

This connection between algebra and analysis became enormously useful when researchers realized that many engineering problems could be phrased as "find the safest polynomial," "find the most stable controller," or "find the smoothest function that satisfies these constraints." SOS optimization provides a computational framework for exactly these tasks. A polynomial is nonnegative if and only if it can be decomposed into sum-of-squares components, and decomposing a polynomial into sum-of-squares is itself an optimization problem—one that can be tackled with semidefinite programming, a well-studied class of convex optimization problems.

The standard approach works like this: you take your polynomial optimization problem, encode it as a semidefinite program (SDP), and then throw a solver at the SDP. The solver—usually an interior-point method—proceeds by constructing a sequence of increasingly accurate approximations to the optimal solution. At each step, it solves a large system of linear equations. The process is reliable and produces highly accurate answers, but it scales poorly. The memory required grows with the square of the problem dimension, and the computational cost grows even faster. For polynomial optimization problems with many variables or high-degree polynomials, the number of decision variables grows combinatorially—the classic curse of dimensionality—and the traditional approach buckles.

Now add a twist: what happens when your objective function—the thing you're trying to minimize—is itself quadratic? In many applications, you don't just want any polynomial that satisfies your constraints; you want one that also minimizes a quadratic penalty. Perhaps you want the smoothest function (penalizing large second derivatives) or the most energy-efficient controller (penalizing large control inputs). This creates a quadratic conic program (QCP)—a quadratic objective coupled with constraints on a cone of positive semidefinite matrices.

The traditional response to a quadratic objective has been to eliminate it through a process called lifting. The idea is to introduce an auxiliary variable—call it γ—and replace the quadratic term with a linear term in γ, subject to a new constraint that ensures the auxiliary variable tracks the quadratic objective. This transforms the problem into a linear conic program, which existing solvers can handle.

But the transformation has costs. In the second-order cone (SOCP) lifting, the new constraint defines a rotated cone in a higher-dimensional space. The linear systems that interior-point methods solve at each iteration become larger, and the iterative process can slow down significantly. In the Schur complement / semidefinite lifting, the constraint becomes a linear matrix inequality requiring a positive semidefinite matrix of size (n_f + 1) × (n_f + 1), where n_f is the number of free variables. Factorizing large dense matrices is computationally expensive, and the cost escalates rapidly as n_f grows.

Machado, Drummond, and Jones document this clearly: both liftings increase the decision variable dimension from n to n + 1, but the SOCP lifting introduces cone constraints of size O(n) while the SDP lifting introduces matrix constraints of size O(n²). For high-dimensional polynomial optimization, where n grows combinatorially with the number of variables and polynomial degree, "these liftings create computational bottlenecks."

Existing specialized solvers attempt to avoid explicit liftings by working directly with quadratic objectives. COSMO, SCS, and Clarabel can all handle quadratic costs without reformulating them away. But as the authors explain, these solvers still inherit structural limitations from the underlying SOS formulation. Enforcing positive semidefinite constraints on sum-of-squares variables requires introducing slack variables and repeatedly projecting onto cone constraints. The homogeneous self-dual embedding that SCS and Clarabel rely on has size that grows with the conic structure. As the number and dimension of SOS blocks increase, these operations scale poorly and performance becomes sensitive to problem conditioning and the sparsity patterns present in the data.

The paper's contribution is to step around this entire apparatus. Instead of lifting the problem or applying increasingly sophisticated solvers to the lifted representation, the authors add a carefully chosen regularization term to the objective function. This regularization consists of a quadratic penalty on the sum-of-squares variables, scaled by a parameter ρ > 0. The regularized problem replaces the original with:

$$\underset{\mathbf{\xi }}{\min }\frac{1}{2}{\mathbf{\xi }}_{\text{f}}^{\top }\mathbf{Q}{\mathbf{\xi }}_{\text{f}}+{\mathbf{w}}^{\top }\mathbf{\xi }+\frac{\rho }{2}\sum _{j=1}^{m_{\text{sos}}}\Vert {\mathbf{\xi }}_{\text{sos}}^{(j)}{\Vert }_2^2$$

subject to the same affine equality constraints and conic constraints on $\mathbf{\xi }$ as before.

This modest change in the problem formulation has profound consequences. The quadratic penalty on the SOS variables makes the Lagrangian subproblem—minimizing over the primal variables for a fixed dual iterate—strongly convex. Strong convexity ensures a unique minimizer. The authors show that this minimizer has a closed-form expression: the SOS variables are given by projecting the unconstrained minimizer onto the positive semidefinite cone, and the free variables are given by solving a linear system involving the matrix Q.

With closed-form solutions for all primal variables, the dual function—the function that gives the minimum of the Lagrangian as a function of the dual variables—becomes an explicit, concrete expression. The dual problem is then just maximizing this dual function over all real vectors. But there's more: the authors establish that this dual function is concave (meaning it has a single global maximum) and has a Lipschitz-continuous gradient (meaning it changes at a controlled rate). These properties make the dual problem ideally suited for first-order methods, a class of optimization algorithms that only require gradient information and scale gracefully to large problems.

The specific first-order method employed is Nesterov's accelerated gradient ascent. This algorithm, developed by Yurii Nesterov in the 1980s, achieves optimal convergence rates for smooth convex optimization: the distance to the optimum decreases as 1/k², where k is the iteration count. This is significantly faster than the 1/k rate achieved by ordinary gradient ascent. The authors adapt this method to their dual problem, and their Algorithm 1 provides the complete procedure.

The algorithm maintains three sequences: the current dual iterate ${\mathbf{\lambda }}^{(k)}$, an extrapolation point ${\mathbf{y}}^{(k)}$ used for momentum, and a scalar $t^{(k)}$ controlling the momentum weight. At each iteration, the gradient of the dual function is evaluated at the extrapolation point, and the dual iterate is updated by moving in the gradient direction with stepsize η = 1/L, where L is the Lipschitz constant of the dual gradient. The extrapolation point is then updated using Nesterov's momentum formula. The algorithm includes safeguards—a check that prevents momentum from destabilizing the iteration—and terminates when both primal and dual feasibility are satisfied to prescribed tolerances.

What They Found

The theoretical analysis in the paper establishes three main results. First, for any regularization parameter ρ > 0, the regularized problem has a unique solution. Second, as ρ approaches zero, the solution of the regularized problem converges to the solution of the original quadratic conic program. Third, the dual problem admits non-asymptotic convergence guarantees: after k iterations of the accelerated gradient method, the difference between the dual objective and its optimum is bounded by:

$$g({\mathbf{\lambda }}^{\ast })-g({\mathbf{y}}^{(k)})\le \frac{2L\Vert {\mathbf{\lambda }}^{\ast }{\Vert }_2^2}{t_k^2}$$

This bound tells us exactly how many iterations are needed to achieve a desired accuracy. If we want the dual objective to be within ε of the optimum, we need roughly $t_k\ge \sqrt{2L}\Vert {\mathbf{\lambda }}^{\ast }{\Vert }_2/\sqrt{\epsilon }$ iterations. The quantity $t_k$ grows like k, so the iteration complexity scales as O(1/√ε). This is optimal for first-order methods on smooth convex problems.

But theory is one thing; practice is another. The authors evaluate their method on constrained regression problems—a class of problems where you want to fit a polynomial model to data subject to sum-of-squares constraints ensuring the learned function has certain properties. They compare against SCS (Splitting Conic Solver, an operator-splitting method) and MOSEK (a commercial interior-point solver). The results demonstrate substantial practical advantages.

Performance Profiles: Solver Reliability vs. Computation Time

Label	Value
1	100
2	98
5	92
10	85
50	60
100	45

Performance profiles compare solver reliability across problem scales. The y-axis shows the fraction of problems solved within τ times the best time. Proposed method solves all problems; SCS plateaus below 100% at large τ; MOSEK fails on large problems.

The performance profiles in Figure 1 capture the behavior of the three solvers across different problem scales. Performance profile methodology, borrowed from the optimization benchmarking literature, plots the fraction of problems solved within a given multiple of the best solve time. A solver whose curve reaches 1.0 on the y-axis can solve every problem in the test set, while solvers that plateau below 1.0 failed on some problems. The horizontal axis shows τ, the multiple of the best time achieved by any solver.

The proposed method's curve climbs steeply and reaches 1.0, indicating it solves every test problem. SCS shows a slower climb and fails to reach 1.0, meaning it timed out or encountered numerical issues on a subset of problems. MOSEK's performance depends on problem size: it performs well on small instances but fails to solve larger problems, reflecting the memory and computation scaling challenges that motivate the paper.

The authors report that their method achieves a 40 percent speedup over SCS on the problems both solvers could solve. More importantly, it extends the frontier of tractable problem sizes. MOSEK failed on problems that their method handled routinely, suggesting that the lifting-free approach genuinely sidesteps bottlenecks that other methods cannot avoid.

The memory analysis is equally significant. The authors show that their method's memory requirements scale only with the number of equality constraints, O(m), rather than with the lifted conic dimension. This matters enormously for large-scale applications. A polynomial optimization problem with 10 variables and degree-4 polynomials might have hundreds of decision variables; with degree-6, that number balloons into thousands. Existing methods must allocate memory proportional to these large numbers. The lifting-free approach allocates memory proportional to only the constraints connecting variables, which often remains modest even as the decision variable count explodes.

Why This Changes Things

The significance of this work extends across several domains where quadratic sum-of-squares programming appears. To appreciate why, it helps to understand the applications that have been waiting for exactly this kind of improvement.

System identification reconstructs dynamical models from experimental data. When you have measurements of a system's inputs and outputs over time, you want to infer the differential equations or difference equations that govern its behavior. Sum-of-squares optimization appears when you want models that are not just accurate but also physically plausible—for instance, when the inferred model must be stable for all admissible inputs, or when the energy stored in the system must be nonnegative. These constraints naturally map onto SOS programs. The quadratic term in the objective might penalize model complexity (preferring simpler models that generalize better) or tracking error (preferring models that fit the data closely). Until now, solving these identification problems at the scales needed for modern engineering systems meant accepting either slow computation or restrictive problem sizes. The 40 percent speedup demonstrated in the paper, combined with the extended problem-size frontier, makes system identification with SOS constraints more practical across the board.

Control synthesis designs controllers that govern how systems behave. A drone's flight controller must maintain stability despite wind gusts and sensor noise; a power grid's controller must balance supply and demand while responding to failures. Sum-of-squares methods appear when synthesizing controllers that can be proven to work: you formulate the stability or performance requirement as an SOS constraint, solve for controller parameters that satisfy it, and obtain a certificate—a mathematical proof—that the controller will work as intended. The quadratic term in the objective might penalize aggressive control action (preferring smooth, energy-efficient control) or control effort (preferring controllers that don't demand too much from actuators). For real-time control, you need to solve these optimizations quickly—ideally in milliseconds or less. The closed-form primal updates that Machado, Drummond, and Jones derive mean that once the dual problem is solved, recovering the optimal controller parameters requires only evaluating a formula. Combined with the scalable first-order method for the dual, this makes fast SOS-based control synthesis more feasible.

Machine learning increasingly requires properties that SOS methods can guarantee. If you want a neural network that's provably robust to adversarial perturbations—small changes to its inputs that might cause misclassification—sum-of-squares techniques can compute certified lower bounds on robustness. If you want to learn a polynomial model with guaranteed stability or monotonicity properties, SOS constraints enforce these during training. The quadratic term in the objective might penalize overfitting (the usual L2 regularization that appears throughout machine learning) or encode domain-specific preferences. The extended problem sizes that this method enables matter here: modern learning problems can have thousands of features, and polynomial models that capture feature interactions become intractable for traditional methods.

Beyond these specific applications, the paper demonstrates a general principle: sometimes the right way to handle a computational bottleneck is not to throw more computing power at it or to develop increasingly sophisticated algorithms for the same formulation, but to change the formulation itself. The authors don't improve on existing interior-point methods or operator-splitting schemes. Instead, they identify that the root cause of the bottleneck—the lifting that increases conic dimension—and propose a regularization that lets them solve the problem directly without lifting. This is a conceptual contribution as much as a technical one.

The mathematical machinery behind this result connects to broader themes in optimization. Partial Lagrangian duality, where only some constraints are dualized, has a long history in convex optimization. Augmented Lagrangian methods and proximal methods also regularize to make subproblems easier, though they typically add quadratic terms to the Lagrangian rather than directly to the objective. The authors' approach is clean: by adding a norm-squared penalty on the SOS variables, they make the primal subproblem strongly convex with a known solution form, then leverage this structure to obtain a smooth concave dual. The fact that this dual is unconstrained and has a Lipschitz gradient places the problem squarely within the domain of Nesterov's optimal first-order methods.

The non-asymptotic convergence guarantee deserves special emphasis. Many optimization results say that a method converges in the limit—after infinitely many iterations, you get the exact solution. Practitioners care about finite-time behavior: after 100 iterations, or 1000, how close am I? The bound $g({\mathbf{\lambda }}^{\ast })-g({\mathbf{y}}^{(k)})\le 2L\Vert {\mathbf{\lambda }}^{\ast }{\Vert }_2^2/t_k^2$ tells you explicitly how many iterations are needed to achieve a target accuracy. If you need the dual objective to be within 0.01 of optimal, you can compute the required iteration count from problem data. This kind of explicit guarantee is valuable for implementation and for deciding when to stop iterating.

What's Next

The paper opens several avenues for future work. The convergence analysis assumes that the matrix Q in the quadratic objective is positive definite. Many applications have this property—penalizing a quadratic form typically uses a positive definite matrix—but cases where Q is only positive semidefinite (allowing some directions to be unpenalized) or indefinite (as in saddle-point problems) would require extensions. The authors note this as a limitation and a direction for future research.

The connection between the regularization parameter ρ and practical performance warrants further investigation. In theory, solutions of the regularized problem converge to solutions of the original as ρ → 0. In practice, choosing ρ involves tradeoffs: larger ρ makes the primal subproblem better conditioned (faster dual optimization) but introduces a larger perturbation from the original problem. The paper doesn't prescribe ρ selection procedures, and empirical guidance for different problem classes would be valuable.

Parallel and distributed implementations could amplify the speedups. The dual function evaluation decomposes additively across SOS blocks, and the gradient computation involves independent projections onto positive semidefinite cones. These structures suggest natural opportunities for parallelization. For very large problems—say, system identification with millions of data points—the ability to distribute computation across multiple processors or machines would further extend the tractable problem sizes.

Applications in verified neural network robustness are particularly promising. Recent work on certifying robustness of neural networks against adversarial examples uses SOS methods to compute certified lower bounds on the worst-case perturbation a network can survive. The polynomial models that arise in these certifications can have high degree and many variables (one for each input dimension and each layer). Extending the lifting-free approach to handle the specific structure of neural network certification problems—potentially involving multiple interconnected SOS constraints—would be a significant practical contribution.

The comparison with existing solvers invites benchmarking on a wider range of problem classes. The numerical experiments in the paper use constrained regression problems; comparing on system identification benchmarks, control synthesis benchmarks, and machine learning benchmarks would clarify where the lifting-free approach provides the most benefit. Problems with highly structured sparsity patterns, dense SOS constraints, or ill-conditioned data represent different stress tests for the method.

Finally, the software implementation matters for adoption. The authors have developed an implementation of Algorithm 1, but making it available as a well-documented, user-friendly solver would lower barriers to use. Integration with existing sum-of-squares toolboxes—YALMIP and GloptiPoly for polynomial optimization, SPOT and Tens Toolbox for control systems—would allow practitioners to apply the method without learning a new modeling interface.

The optimization problems at the heart of modern engineering and machine learning are growing larger and more complex. The techniques for solving them must grow alongside. By changing the problem rather than just the solver, Machado, Drummond, and Jones have opened a path that others will surely follow—exploring different regularization strategies, adapting the framework to new application domains, and pushing the frontier of what's tractable. The 40 percent speedup and extended problem sizes demonstrated here are concrete evidence that the path is worth following. What remains is to see how far it leads.