PaperlayerView exact revision on arXiv

Source-linked AI summary

Advances in Global Solvers for 3D Vision

Zhenjun Zhao, Heng Yang, Bangyan Liao, Yingping Zeng, Shaocheng Yan, Yingdong Gu, Peidong Liu, Yi Zhou, Haoang Li, Javier Civera

arXiv:2602.14662v1cs.CVcs.RO

TL;DR

Nonconvex geometric optimization in 3D vision is difficult for local methods and lacks a unified account of global solvers. This survey organizes the field around BnB, CR, and GNC, reviews their theory and practical enhancements across ten tasks, and characterizes their optimality, robustness, and scalability trade-offs. It concludes that certifiable methods incur substantial computational cost, while continuation methods trade guarantees for efficiency, with scaling and deployment remaining important boundaries.

  • Problem

    Nonlinear and nonconvex vision problems are sensitive to initialization, while existing surveys provide no comprehensive account unifying global methods, trade-offs, applications, and open challenges.

  • Method

    The survey develops a taxonomy of Branch-and-Bound, Convex Relaxation, and Graduated Non-Convexity, reviewing their theoretical foundations, practical enhancements, and applications across ten 3D vision tasks.

  • Results

    The comparative analysis reveals that certifiable methods provide global guarantees at significant computational cost, whereas continuation approaches sacrifice guarantees for efficiency.

  • Takeaways & Limitations

    Global solvers provide a roadmap toward certifiable 3D perception by connecting theoretical guarantees, practical algorithms, and applications.

  • Takeaways & Limitations

    GNC lacks a priori global-optimality guarantees and can fail under extreme outlier ratios, adversarial configurations, or poor schedule tuning.

Abstract

from arXiv · show

Global solvers have emerged as a powerful paradigm for 3D vision, offering certifiable solutions to nonconvex geometric optimization problems traditionally addressed by local or heuristic methods. This survey presents the first systematic review of global solvers in geometric vision, unifying the field through a comprehensive taxonomy of three core paradigms: Branch-and-Bound (BnB), Convex Relaxation (CR), and Graduated Non-Convexity (GNC). We present their theoretical foundations, algorithmic designs, and practical enhancements for robustness and scalability, examining how each addresses the fundamental nonconvexity of geometric estimation problems. Our analysis spans ten core vision tasks, from Wahba problem to bundle adjustment, revealing the optimality-robustness-scalability trade-offs that govern solver selection. We identify critical future directions: scaling algorithms while maintaining guarantees, integrating data-driven priors with certifiable optimization, establishing standardized benchmarks, and addressing societal implications for safety-critical deployment. By consolidating theoretical foundations, practical advances, and broader impacts, this survey provides a unified perspective and roadmap toward certifiable, trustworthy perception for real-world applications. A continuously-updated literature summary and companion code tutorials are available at https://github.com/ericzzj1989/Awesome-Global-Solvers-for-3D-Vision.

1 INTRODUCTION

Global solvers address nonconvex geometric vision problems through three paradigms—Branch-and-Bound, Convex Relaxation, and Graduated Non-Convexity—while this survey unifies their theory, trade-offs, applications, and open challenges.

  • Motivation: Local methods for nonlinear, nonconvex vision problems are sensitive to initialization, motivating global optimization approaches.These problems support applications including localization, reconstruction, SLAM, SfM, autonomous driving, and medical imaging.
  • Solver paradigms: BnB explores and prunes the solution space, CR solves tractable convex surrogates, and GNC follows a homotopy from an easy convex problem to the original nonconvex one.BnB provides global-optimality guarantees; CR often yields tight or certifiable bounds; GNC often reaches near-global solutions in practice.
  • Survey gap: Existing surveys lack a comprehensive perspective that unifies methods, compares guarantees and practical trade-offs, covers diverse tasks, and identifies future directions.The paper presents the first systematic survey specifically dedicated to global solvers for 3D vision.
  • Unified taxonomy: The survey organizes global solvers into Branch-and-Bound, Convex Relaxation, and Graduated Non-Convexity.Convex Relaxation includes Shor’s relaxation, Moment-SOS hierarchies, and other specialized techniques.
  • Comparative analysis: The survey compares optimality guarantees, computational complexity and scalability, outlier robustness, and deployment considerations across method families and problem scales.It reviews core formulations, theoretical properties, and practical variants enhanced for robustness and scalability.
  • Tasks and resources: Coverage spans ten classical 3D vision problems, including pose estimation, registration, averaging, triangulation, pose graph optimization, and bundle adjustment.The survey also identifies open challenges and provides a continuously updated literature repository with implementation pointers and tutorial code.

2 BACKGROUND AND PROBLEM FORMULATION

Geometric vision estimation is commonly formulated as nonlinear least squares, but structural constraints and nonlinear residuals make these problems intrinsically nonconvex. Robust estimation addresses incomplete, noisy, and outlier-contaminated measurements through consensus maximization or M-estimation.

  • 2.1 Notation and Conventions: The section establishes notation for scalars, vectors, matrices, indexed submatrices, inner products, vectorization, Kronecker products, block concatenation, and geometric matrix sets.It defines conventions for SO(d), SE(d), PSD and PD matrices, spheres, triangular matrices, polynomials, monomial bases, and SOS representations.
  • 2.1 Notation and Conventions: Polynomials are represented using finite monomial bases, and a polynomial is SOS when a PSD Gram matrix certifies its global nonnegativity.The SOS form is q(x) = [x]F^T Q [x]F with Q ⪰ 0.
  • 2.2 Geometric Problem Formulation and Structure: Many geometric estimation tasks fit a nonlinear least-squares template that minimizes residual disagreement between model parameters and measurements.The template covers reprojection, epipolar, alignment, and distance-based costs across pose, triangulation, registration, averaging, and bundle adjustment.
  • 2.2 Geometric Problem Formulation and Structure: Nonconvexity arises from structural constraints such as SO(3), unit norms, low-rank or bilinear relations, discrete assignments, and nonlinear measurement models.Examples include perspective projection, essential or fundamental matrix restrictions, and subset or multi-structure assignment variables.
  • 2.3 Robust Estimation: Measurements are often incomplete, noisy, or contaminated by outliers, motivating robust strategies that preserve computational tractability.The section introduces consensus maximization and M-estimation as the two predominant robust-estimation paradigms.
  • 2.3 Robust Estimation: Consensus maximization selects parameters maximizing the number of measurements within threshold τ, but its formulation is combinatorial and NP-hard.The inlier count is expressed through an indicator function over measurement residuals.
  • 2.3 Robust Estimation: M-estimation replaces least squares with a subquadratic robust function ρ to reduce the influence of large residuals.Huber, Cauchy, Geman–McClure, and truncated least squares are listed as typical choices, while global optimization remains difficult because both ρ and X can be nonconvex.

3 GLOBAL SOLVER 1: BRANCH-AND-BOUND (BNB)

Branch-and-Bound is a deterministic global-optimization framework that partitions a nonconvex search space, bounds each region, and prunes regions unable to contain the optimum. It provides certificates under suitable conditions, but its worst-case cost is exponential and practical scalability depends on bound quality, dimension, and outlier level.

  • BnB framework: BnB partitions the search space, computes provable objective bounds, and prunes regions that cannot contain the global optimum.Under valid bounds and sufficient refinement, it converges to a certified global optimum with ε-suboptimality guarantees.
  • Solver ingredients: A BnB solver requires a parameter domain, tight lower-bound functions, and branching or node-selection strategies.Domains may represent SO(3), R3, or SE(3); bounds can use Lipschitz continuity, interval arithmetic, convex relaxations, or geometric bounds.
  • BnB search process: The illustrated one-dimensional procedure branches into subregions, bounds them, prunes regions with lower bounds above the best feasible upper bound, and converges to a certified optimum.In the figure, X1 is pruned when L1 > U*, while X2 remains active when L2 < U*.
  • Solver ingredients: Tighter bounds enable earlier elimination of suboptimal regions and improve pruning effectiveness.Uniform bisection, adaptive splitting, and problem-specific heuristics can be paired with best-first, depth-first, or hybrid node selection.
  • Theoretical properties: Valid lower bounds and arbitrarily fine subdivision guarantee convergence because pruning cannot remove a region containing the true minimizer.A posteriori optimality certificates follow when the bound gap falls below a prescribed threshold.
  • Computational complexity: Worst-case BnB complexity is exponential in parameter dimension, with explored regions growing as O((D/δ)^d) for domain diameter D and resolution δ.Branching depth and node counts can become prohibitive, although smoothness, low intrinsic dimensionality, and tight bounds may reduce the explored tree.
  • Robust estimation: For robust consensus maximization, interval arithmetic supplies upper bounds on inlier counts and lower bounds from feasible points, enabling pruning and globally optimal inlier-set identification for moderate-scale problems.Regions whose upper bound falls below the current best lower bound are discarded.
  • Hybrid frameworks: Hybrid BnB frameworks combine coarse search or alternating local refinement with BnB to improve scalability, while potentially weakening strict global-optimality guarantees.Local updates tighten upper bounds and BnB refines lower bounds, progressively narrowing the bound gap.

4 GLOBAL SOLVER 2: CONVEX RELAXATION (CR)

Convex relaxation converts nonconvex geometric optimization into tractable convex programs, chiefly through Shor’s SDP and Moment-SOS hierarchies. These methods can provide global-optimality certificates, but scalability depends on relaxation size and problem structure.

  • Convex relaxation replaces nonconvex constraints with convex surrogates that yield globally solvable programs and certifiable bounds.
  • Shor’s Relaxation: Shor’s relaxation lifts QCQPs to a matrix variable and drops the nonconvex rank-one constraint to obtain an SDP.The lifted matrix is X = xx⊤, with positive-semidefinite and linear trace constraints.
  • Shor’s Relaxation: When the SDP solution has rank one, Shor’s relaxation recovers the globally optimal solution and certifies it through zero duality gap.Higher-rank solutions require rounding or local refinement, while dual certificates can still provide suboptimality bounds.
  • Moment-SOS Relaxation: Moment-SOS constructs a hierarchy of SDP relaxations whose lower bounds converge monotonically to the polynomial optimization optimum.Low-order relaxations, typically degree 2–4, often suffice for geometric vision problems.
  • Specialized quasi-convex, SOCP, QP, LP, and convex-hull approaches improve scalability and can retain provable optimality or tight approximations.These methods are suited to larger or real-time instances than generic SDP formulations.

5 GLOBAL SOLVER 3: GRADUATED NONCONVEXITY (GNC)

GNC solves robust nonconvex estimation by gradually deforming a convex surrogate into the target nonconvex objective while warm-starting successive subproblems. It is computationally efficient and empirically near-global, but lacks a priori global-optimality certificates and has identifiable failure conditions.

  • GNC Framework: GNC embeds a hard nonconvex objective in a parameterized family of increasingly nonconvex surrogates controlled by µ.Unlike BnB and convex relaxation, it uses homotopy deformation rather than exhaustive search or lifting.
  • Algorithm: At each continuation step, IRLS solves a weighted least-squares problem, updates µ, and warm-starts from the preceding estimate.A typical schedule uses µk+1 = αµk, with termination at µmin or when successive estimates stabilize.
  • Robustness: As µ decreases, weights progressively down-weight large residuals, providing deterministic outlier suppression without explicit inlier–outlier classification.This mechanism implements robust M-estimation through the continuation path.
  • Strengths: GNC often reaches near-global minima empirically and handles 30–50% outlier ratios reliably in practice.Its computational cost scales linearly with measurements, supporting large-scale robust estimation.
  • Variants and Extensions: Variants include GM and TLS penalties, adaptive annealing, minimally tuned termination, and hybrids that certify or refine GNC solutions with convex relaxation.These extensions target robustness, reduced tuning dependence, and improved reliability.
  • Limitations: GNC lacks a priori global-optimality guarantees and may fail above 50% outliers, under adversarial configurations, or with overly rapid µ schedules.Performance also depends on convex initialization and parameter tuning, although adaptive variants reduce sensitivity.

6 COMPARATIVE ANALYSIS

Global solver families trade optimality guarantees against computational efficiency, scalability, and outlier robustness. BnB offers the strongest certificates but highest worst-case cost, while GNC scales best and provides practical robustness without a priori certificates.

  • Global Optimality Guarantees: BnB guarantees global optimality with certificates upon convergence, but has exponential worst-case complexity.Its applicability is therefore limited primarily by computational cost.
  • Global Optimality Guarantees: Shor’s relaxation and Moment-SOS provide certificates when relaxations are tight, with Moment-SOS offering stronger hierarchical guarantees at greater cost.Other specialized relaxations can be exact for particular problem classes.
  • Computational Efficiency and Scalability: BnB is typically limited to fewer than 20 measurements, whereas Shor’s relaxation reaches medium-scale problems with O(n^3.5) complexity per SDP solve.These ranges assume the complexity conditions stated for the corresponding methods.
  • Computational Efficiency and Scalability: GNC has the best scalability, with O(Kn^2) complexity per iteration, enabling large-scale and real-time applications.Moment-SOS is typically effective below 100 measurements at low relaxation orders, while specialized SOCP, QP, LP, and convex-hull methods can handle thousands.
  • Robustness to Outliers: GNC handles 30–50% outlier ratios through progressive down-weighting without explicit inlier or outlier classification.This deterministic mechanism combines robustness with the method’s strong scalability.
  • Method Selection: Solver selection depends on scale and requirements: certified small problems favor BnB or tight relaxations, while large problems favor scalable methods such as GNC.Shor’s relaxation is presented as a balance for medium-scale problems when its relaxation is tight.

7 TASKS AND APPLICATIONS

The survey organizes global-solver research around ten geometric vision tasks and the solver families applied to them. It uses task formulations and representative methods to connect problem structure with BnB, convex-relaxation, and related approaches.

  • Scope and Organization: The task coverage spans single-view, two-view, multi-view, and large-scale multi-view geometry.The survey groups these domains across Sections 7.1–7.10 and uses Fig. 6 to visualize their setups and estimated variables.
  • Scope and Organization: Each task is presented through its formulation, local methods, analytical solutions, and global-solver developments.This consistent template supports comparisons across substantially different geometric structures and outlier conditions.
  • Wahba Problem: Wahba estimation recovers R∈SO(3) from vector correspondences and supports applications including attitude determination, image stitching, and 3D reconstruction.Its least-squares form is algebraically equivalent to maximizing trace(R^T M).
  • Wahba Problem: Outlier-free Wahba estimation has an exact globally optimal SVD solution, whereas local methods can lack global convergence guarantees and be sensitive to contaminated correspondences.The SVD solution uses R*=U diag(1,1,det(UV^T))V^T for M=USV^T.
  • Wahba Problem: BnB, Shor’s relaxation, alternative convex formulations, and robust preprocessing such as GORE provide complementary approaches to Wahba estimation.GORE provably discards correspondences outside the maximum consensus set while retaining all inliers.
  • Solver Taxonomy: Fig. 7 indexes representative works by task and solver family, including BnB, Shor’s, Moment-SOS, other convex methods, and GNC.The index is intended as a comprehensive map of global optimization methods for the ten tasks.

7.2 Vanishing Point Estimation

Vanishing-point estimation is a nonconvex, sometimes combinatorial problem involving convergence points of parallel line families. The survey reviews globally optimal and convex-relaxation approaches motivated by the limitations of heuristic and local methods.

  • Problem Definition: Vanishing-point estimation recovers convergence points from families of image lines using normalized line and direction geometry.The direction is d_i=K^-1v_i, while the line normal is n_j=K^-Tℓ_j.
  • Properties and Local Methods: The problem is nonconvex on the projective plane and becomes combinatorial with multiple vanishing points.These properties make globally optimal estimation challenging.
  • Properties and Local Methods: Hough voting is efficient for coarse estimation but sensitive to discretization, while RANSAC is robust to outliers without global optimality guarantees.Least-squares and EM refinements improve accuracy but remain vulnerable to local minima and initialization.
  • Global Solvers: BnB is the dominant framework for globally optimal vanishing-point estimation, using parameterizations and tight bounds that guarantee convergence.The reviewed BnB methods operate over azimuth and elevation without requiring prior knowledge of horizontal frames.
  • Global Solvers: GlobustVP introduces a convex-relaxation framework for Manhattan-world vanishing-point estimation with truncated multi-selection error and soft line–vanishing-point association.This formulation addresses the association structure within a convex framework.

7.4 Relative Pose Estimation

Relative pose estimation recovers camera motion from two-view correspondences through fundamental- or essential-matrix formulations. The survey reviews their nonconvex constraints, analytical baselines, and certifiable global methods.

  • Problem Definition: Relative pose estimation seeks the camera transformation (R,t)∈SE(3) from 2D–2D correspondences and supports SfM, visual localization, and SLAM.Uncalibrated problems use the fundamental matrix, while calibrated problems use the essential matrix.
  • Problem Definition: The fundamental matrix has rank 2 and is defined up to scale, whereas E=[t]×R has rank 2 with two equal nonzero singular values.Pose recovery from F has projective ambiguity; recovery from E has cheirality ambiguity.
  • Properties and Local Methods: Both formulations are nonconvex because of rank constraints and, in calibrated settings, the orthogonality structure of SO(3).Classical local solvers are efficient but lack global optimality guarantees and are sensitive to initialization.
  • Analytical Methods: Minimal relative-pose formulations admit closed-form or analytical methods, including the 8-point fundamental-matrix and 5-point essential-matrix algorithms.The 8-point method enforces rank 2 through SVD, while the 5-point method exploits essential-matrix constraints.
  • Global Solvers: Global methods also exploit structural constraints, such as gravity direction or planar motion, to decouple relative rotation and translation.These reductions enable simplified bounding strategies for consensus maximization.
  • Global Solvers: Shor’s relaxations can certify global optimality when redundant constraints make the SDP tight, while Moment-SOS methods address the problems through hierarchical polynomial relaxations.Other approaches include SOCP solutions for specialized L∞ triangulation formulations.

7.6 Rotation Averaging

Rotation averaging estimates absolute camera orientations from noisy relative rotations on a measurement graph, but its manifold constraints and graph coupling make it nonconvex. Global approaches use convex relaxations and related formulations to obtain certifiable or globally optimal solutions, while local methods remain efficient but sensitive to noise and outliers.

  • Problem formulation: Rotation averaging estimates absolute camera orientations from noisy relative rotations, up to a global gauge.It minimizes discrepancies between measured and estimated relative rotations using distance functions on SO(3).
  • Properties and local methods: The problem is nonconvex because of SO(3) manifold constraints and coupling induced by the measurement graph.Classical IRLS, Weiszfeld-type, and related manifold methods are computationally efficient but sensitive to noise and outliers.
  • Convex relaxations: Shor’s relaxation lifts rotation variables into a matrix SDP formulation with block-orthonormality constraints.This provides a connection-Laplacian view of the maximum-likelihood rotation-averaging problem.
  • Practical global methods: Alternative formulations combine global guarantees with practical computation, including dual methods, adaptive dimension lifting, and specialized convex programs.Reported approaches include 1–2 orders of magnitude speedup over standard SDP solvers and SDP-derived global-optimality certificates.
  • Convex relaxations: Moment-SOS relaxations exploit the polynomial structure of rotation averaging to provide certifiably optimal solutions for small- to medium-scale instances.Rapid growth of moment matrices limits scalability.

7.7 Translation Averaging

Translation averaging estimates absolute camera locations from noisy pairwise directions, with unavoidable global translation and scale ambiguities. Its nonconvexity and sensitivity to outliers motivate certifiable SDP, SOCP, LP, and related global formulations, while triangulation extends these relaxation strategies to 3D point estimation.

  • Translation averaging: Translation averaging estimates absolute camera locations from pairwise direction measurements, up to global translation and scale.The objective can use angular or Euclidean discrepancies between estimated and observed directions.
  • Properties and local methods: Translation averaging is harder than rotation averaging because scale and gauge ambiguities combine with normalization, outliers, and degenerate camera configurations.Collinear arrangements are an example of a degenerate configuration.
  • Global methods: A convex SDP relaxation established a certifiably correct translation-averaging formulation using pairwise line measurements and parallel rigidity theory.An augmented Lagrangian dual algorithm was used to scale the SDP solver to large camera networks.
  • Global methods: Specialized SOCP, LP, and LUD formulations provide practical convex alternatives for translation averaging.Replacing SOCP with LP using simplified Euclidean-distance constraints yields substantial speedups in large-scale pipelines.
  • Triangulation: Triangulation estimates a 3D point from calibrated multiview projections and is nonconvex because of perspective projection.It is ill-conditioned under small baselines, large noise, and near-epipolar arrangements.
  • Triangulation: Global triangulation methods include polynomial closed-form procedures, BnB, SDP, moment-SOS, LP, and SOCP formulations.These methods support global optimality or certification, including robust handling of outliers in selected formulations.

7.9 Pose Graph Optimization

Pose graph optimization estimates globally consistent camera poses from noisy relative measurements and is a nonlinear, nonconvex back-end problem in SLAM and SfM. Global approaches center on SDP and SOS relaxations, with dual formulations and specialized initializers improving certification or practical refinement.

  • Problem formulation: Pose graph optimization estimates absolute camera poses that are maximally consistent with noisy relative pose constraints.It is formulated as maximum-likelihood estimation and is fundamental to SLAM and SfM.
  • Properties and local methods: PGO is nonconvex because of SO(3) constraints and rotation–translation coupling, while local solvers are sensitive to initialization and poor local minima.Gauss-Newton and Levenberg-Marquardt methods remain efficient backbones of modern SLAM libraries.
  • Convex relaxations: SDP relaxations provide certifiable PGO solutions through Lagrangian duality and synchronization-based formulations.Smaller dual SDPs support optimality verification, while dual-based initialization can remain useful when the relaxation is not tight.
  • Convex relaxations: SOS relaxations formulate Pose-Graph SLAM and Landmark SLAM as polynomial optimization problems solvable to global minima.Sparse bounded-degree SOS variants provide certifiable guarantees.
  • Other global methods: Other relaxations include convex-hull formulations over SO(d) and SCORE, an SOCP initializer for range-aided SLAM.SCORE is reported to improve PGO convergence and accuracy while providing a certifiable geometry-aware initialization.
  • Bundle adjustment context: PGO is part of a broader estimation pipeline in which camera poses and 3D structure are jointly refined by bundle adjustment.Bundle adjustment is highly nonconvex and can involve hundreds to tens of thousands of cameras and points, making certifiable global optimization especially difficult at scale.

8 OPEN CHALLENGES AND FUTURE DIRECTIONS

Practical adoption of global solvers is constrained by scalability, limited integration with learned priors, and the absence of standardized evaluation. The survey therefore emphasizes scalable certifiable algorithms, optimization–learning integration, and multidimensional benchmarks that measure both solution quality and certification cost.

  • Scalability and algorithmic advances: Global optimality guarantees from BnB and convex relaxation often incur computational costs that become prohibitive for large-scale problems.Scaling methods while preserving certifiability remains a central challenge, especially for outlier-robust formulations.
  • Scalability and algorithmic advances: Potential scalability improvements include tighter bounds, adaptive branching, sparsity-aware decomposition, coordinate descent, random projections, distributed formulations, and GPU/TPU solvers.These strategies target runtime and memory demands while retaining global guarantees where possible.
  • Integration with deep learning: Deep learning can provide priors, warm starts, and search guidance while certifiable solvers verify or refine learned predictions.The survey frames learning as complementary to principled optimization rather than a replacement for it.
  • Integration with deep learning: Learned predictions may violate multiview geometric consistency and lack global-optimality certificates.Differentiable convex-relaxation layers and certifiable constraints are proposed as integration mechanisms.
  • Standardized evaluation: The field lacks standardized benchmarks and protocols for fair comparison across problem domains and scales.Current reliance on synthetic or small-scale evaluations limits insight into real-world performance.
  • Standardized evaluation: Evaluation should measure certified-optimality rates, certification success, relaxation gaps, runtime–accuracy curves, robustness, memory, and computational requirements.These dimensions capture the optimality–efficiency trade-off more fully than solution accuracy alone.
  • Standardized evaluation: Common data formats, reference implementations, public benchmarks, and evaluation scripts would enable reproducible comparisons and accelerate progress.The survey presents coordinated advances in scalability, learning integration, and evaluation as necessary for practical deployment.

9 SOCIAL IMPACTS

Global solvers raise societal questions alongside technical performance, particularly for safety, transparency, fairness, accessibility, environmental impact, and dual-use risks. Responsible deployment therefore requires validated hybrid designs, efficient algorithms, open evaluation, and institutional oversight.

  • 9.1 Safety-Critical Applications: Certifiable solvers support safety-critical perception by providing guarantees or explicitly signaling when guarantees cannot be provided.This supports fail-safe design in applications where errors can cause severe consequences.
  • 9.2 Trust, Transparency, and Accountability: Verifiable optimality certificates and explicit suboptimality bounds improve transparency, reproducibility, and accountability in automated decisions.These properties help practitioners assess solution quality and support auditing in regulated or liability-sensitive settings.
  • 9.3 Integration with Learning-Based Systems: Learned acceleration can improve scalability, but biased training data or distribution shifts may undermine performance on underrepresented or novel cases.Hybrid systems require validation, uncertainty-aware learning, robust verification, and documentation of training and deployment assumptions.
  • 9.4 Computational Resources and Accessibility: The computational intensity of global solvers can restrict access to well-resourced organizations and increase environmental costs at scale.Scalable algorithms and specialized hardware are identified as ways to reduce these barriers while retaining certification guarantees.
  • 9.5 Ethical and Dual-Use Considerations: Because these technologies are dual-use, beneficial applications must be weighed against risks of invasive surveillance, unauthorized tracking, and military targeting.The paper calls for transparency, engagement with ethicists and policymakers, and deployment guidance that respects rights and dignity.
  • 9.6 Responsible Advancement: Open-source implementations, transparent benchmarks, and educational resources can broaden access to certifiable perception beyond organizations with substantial computational infrastructure.Institutional and regulatory frameworks are also needed to align deployment with societal welfare.

10 CONCLUSION

The survey positions global solvers as practical tools for certifiable 3D perception and unifies them through a taxonomy spanning BnB, CR, and GNC. It concludes that deployment depends on balancing guarantees, efficiency, application needs, scalability, data integration, evaluation, and societal impacts.

  • 10 CONCLUSION: The survey organizes global solvers into Branch-and-Bound, Convex Relaxation, and Graduated Non-Convexity across ten geometric vision tasks.It examines their theoretical foundations, practical enhancements, and deployment from pose estimation to bundle adjustment.
  • 10 CONCLUSION: Certifiable methods provide global guarantees at significant computational cost, whereas continuation approaches sacrifice guarantees for efficiency.Solver choice depends on application requirements, problem structure, and deployment constraints.
  • 10 CONCLUSION: Future progress requires scalable algorithms, integration with data-driven methods, standardized evaluation protocols, and attention to societal impacts.The conclusion frames these advances as necessary for realizing global solvers’ potential in safety-critical applications.
Loading 2602.14662v1…