Introduction
Optimization problems involving the sum of multiple rational functions—defined as fractions of polynomials—are ubiquitous in engineering and science. They appear frequently in computer vision tasks, such as triangulation and camera pose estimation, as well as in systems control. Despite their prevalence, these problems are notoriously difficult to solve globally due to their inherent non-convexity and the computational explosion that occurs when attempting to simplify them.
This paper introduces a robust framework for global optimization that transforms these non-convex problems into linear ones over measures. By leveraging the Generalized Moment Problem (GMP) and semidefinite programming (SDP) relaxations, the authors provide a method capable of solving high-dimensional problems—up to 1,000 variables—provided they possess a sparse structure.
The Challenge of Rational Sums
Standard optimization techniques face three primary hurdles when dealing with sums of rational functions:
- Non-convexity: Local solvers, such as Newton’s method, are easily trapped in local minima, failing to identify the true global optimum.
- Complexity Explosion: A common algebraic approach is to reduce all fractions to a single common denominator. However, for a sum of $N$ terms, the degree of the resulting polynomial becomes astronomical (e.g., 20 terms can lead to a degree of $20!$), making the problem numerically and computationally intractable.
- Dimensionality: Traditional global optimization methods scale poorly as the number of variables ($n$) and terms ($N$) increases.
A Measure-Theoretic Framework
The authors propose a Generalized Moment Problem (GMP) approach. Rather than searching for a single optimal point $x$ in a non-convex landscape, the problem is reformulated as a search for a set of Borel measures that represent the distribution of the optimal solution.
Key Technical Components
- Linear Reformulation: The authors prove that the original non-convex problem is equivalent to an infinite-dimensional linear program over measures. This transformation effectively "convexifies" the problem.
- Lasserre Hierarchy: To make the infinite-dimensional problem solvable, the authors apply a sequence of convex semidefinite programming (SDP) relaxations. As the "order" of the relaxation increases, the solution is guaranteed to converge to the true global minimum.
- Sparsity Exploitation: To combat the curse of dimensionality, the method utilizes the "Running Intersection Property." If the variables interact only within small, overlapping subsets, the SDP relaxations can be decomposed into smaller, manageable blocks. This allows the framework to handle problems with hundreds or thousands of variables.
- Implementation: The method is implemented using GloptiPoly 3, a Matlab-based tool for moment-SOS (Sum of Squares) optimization.
Experimental Validation
The framework was evaluated against several challenging benchmarks designed to test numerical stability and scalability:
- Wilkinson-like Rational Functions: In univariate problems where common denominator reduction fails due to massive coefficients, the GMP approach found the global minimum at the very first relaxation order ($k=0$).
- Modified Shekel’s Foxholes: This classic benchmark features many local minima. The proposed method found the global minimum for $n=5$ in under a minute and for $n=10$ in approximately 750 seconds.
- High-Dimensional Scalability: By exploiting structured sparsity, the authors successfully optimized a rational version of the Rosenbrock function with $n=1000$ variables in roughly 500 seconds.
- Comparison with Epigraph Methods: A common alternative is the "epigraph approach," which adds a new variable for every fraction. The authors demonstrate that their GMP approach is more efficient, often converging at a lower relaxation order and providing a numerical "certificate" of optimality where the epigraph approach fails.
Insights and Future Directions
The most significant insight of this work is that global optimization for $n=1000$ variables is achievable when structured sparsity is present. While general global optimization remains NP-hard, the use of measure-theoretic relaxations allows solvers to bypass traditional dimensionality constraints.
However, some limitations remain. The method requires the feasible set to be compact (bounded), and very high-degree problems can still encounter numerical precision issues within underlying SDP solvers. Future work is directed toward applying these techniques to specific real-world challenges in $H_2$ optimal control and geometric computer vision.
Summary updated