Global Optimization via Polynomial System Solving

36 concepts27 papers1 proposal

Most optimization problems in machine learning and computer vision are solved using iterative, gradient-based methods. These algorithms, such as gradient descent or Expectation-Maximization, are "local" by nature: they start with an initial guess and move downhill. While efficient, they are notoriously prone to getting trapped in local minima—suboptimal solutions that look like the best option only in their immediate neighborhood.

A growing body of research proposes a different path: treating optimization as a problem of algebraic geometry. By reformulating the search for a global minimum as the task of finding all roots of a polynomial system, researchers can provide mathematical guarantees of global optimality that traditional iterative methods lack.

The Landscape as a System of Equations

The core intuition behind this approach is rooted in basic calculus. To find the minimum or maximum of a function, one typically looks for "stationary points" where the gradient is zero. In many real-world problems—ranging from point set registration (Ho et al.) to Maximum Likelihood Estimation (Drton)—the objective function can be expressed as, or approximated by, a multivariate polynomial.

When the objective is a polynomial, its derivatives are also polynomials. Finding all points where the gradient vanishes becomes a task of solving a system of polynomial equations. As Dreesen and De Moor argue, this shifts the problem from the domain of local search to the domain of systems theory and linear algebra. Instead of wandering the landscape, the goal becomes to exhaustively map every peak, valley, and saddle point.

Bypassing Local Minima via Algebraic Solvers

Once an optimization problem is framed as a polynomial system, several algebraic tools can be used to find the global optimum:

  • Gröbner Bases: These are a set of polynomials with particularly helpful properties that allow for the systematic elimination of variables, similar to Gaussian elimination but for non-linear equations. Ho et al. and Chen et al. use Gröbner bases to solve registration and reflectance problems, ensuring they find the absolute best transformation or surface normal without needing a good starting guess.
  • Eigenvalue Problems: Many polynomial systems can be transformed into a generalized eigenvalue problem. Batselier et al. demonstrate that finding the global maximum likelihood estimate for multinomial distributions is equivalent to finding eigenvalues. This is numerically stable and avoids the initialization sensitivity of algorithms like Expectation-Maximization.
  • Homotopy Methods: For complex models like subspace clustering, Nakajima shows that one can track the solutions of a simpler system as they deform into the solutions of the target system, effectively "proving" the global minimum.

By identifying every real-valued critical point, the researcher can simply evaluate the cost function at each one and pick the best. As Dreesen et al. explain, this exhaustive search is what provides the definitive solution to structured approximation problems that typically mislead local search algorithms.

Scaling and Practicality

While symbolic algebra can be computationally expensive, recent work focuses on making these global guarantees practical for real-time applications.

One strategy is to exploit specific geometric constraints. For example, Ding et al. use gravity priors from IMUs to simplify the polynomial systems involved in camera pose estimation. Another strategy is to use "iterative algebraic" methods. Kukelova and Larsson show that for camera triangulation, one can solve a sequence of simple univariate (single-variable) polynomials to reach the global optimum much faster than a full multivariate solver.

In high-dimensional Bayesian Optimization, Adebiyi et al. utilize Chebyshev polynomial approximations to identify all roots of a derivative, ensuring that the acquisition function is truly maximized. This suggests that even when the original problem isn't a simple polynomial, approximating it as one can unlock the benefits of global root-finding.

Applications in Computer Vision and Statistics

This algebraic shift has proven particularly transformative in fields where "close enough" isn't sufficient:

  • Geometry and Calibration: In computer vision, problems like the "Perspective-n-Point" (PnP) problem or camera self-calibration often suffer from "imaginary" or physically impossible solutions. Zheng and Kneip and Kocur and Kyselica use algebraic solvers to bypass these instabilities, finding the mathematically best fit for camera parameters directly.
  • Robustness to Noise: Paudel and Van Gool demonstrate that algebraic geometry can be combined with Branch-and-Bound search to "prove" when a data point is an outlier, allowing for robust calibration even when 90% of the data is noise.
  • Statistical Complexity: Gross and Petrović use these tools to quantify the "ML degree"—a measure of how many stationary points a likelihood function has—providing a roadmap for when algebraic methods are most necessary to avoid multimodal traps.

By moving from "searching" a landscape to "solving" its equations, this research direction provides a rigorous framework for global optimization, ensuring that the solutions found are not just local improvements, but the best possible answers allowed by the data.

Key Foundational Work

An algebraic approach to affine registration of point sets (2009) — contributed 3 concept elements to this direction.
Computing all roots of the likelihood equations of seemingly unrelated regressions (2005) — contributed 2 concept elements to this direction.
The geometric error for homographies (2005) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_global_polynomial_optimization_b9f3111a,
  title = {global polynomial optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-polynomial-optimization/rdr_b9f3111a234f45e6869cd7811a8d1fc8},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_global_polynomial_optimization_b9f3111a_v1,
  title = {global polynomial optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-polynomial-optimization/rdr_b9f3111a234f45e6869cd7811a8d1fc8/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake