Solver in Ceres Solver - I am Charmie

Ceres Solver divides non-linear optimization algorithms into two major categories [1]:

Trust region methods first choose a step size and then a step direction.
Line search methods first choose a step direction and then a step size.

This post clarifies the structure of these algorithms not the detail of them.

Trust region methods [2] Currently, ceres solver has two trust-region algorithms: Levenberg-Marquardt and Dogleg.

1.1. Levenberg-Marquardt [3] Ceres solver has two major classes of methods for a process in Levenberg-Marquardt algorithm: factorization and iterative. For factorization, exact step LM algorithm is used. For iterative linear solver, inexact step LM algorithm is used.

1.1.1. Linear Solver [6] Ceres solver has several solvers for solving linear least square problems in each iteration of the Levenberg-Marquardt algorithm..

DENSE_QR [7]: for small problems (a couple of hundred parameters and a few thousand residuals) with relatively dense Jacobians.
DENSE_NORMAL_CHOLESKY & SPARSE_NORMAL_CHOLESKY [8]: for both dense/sparse larger problems than DENSE_QR assumes.
DENSE_SCHUR & SPARSE_SCHUR [9]: for problems, e.g., bundle adjustment, that have a Hessian matrix with special structure.
CGNR [10]: for general sparse problems. CGNR is used if the problem is too large for CHOLMOD or a sparse linear algebra library is not linked into ceres solver.
ITERATIVE_SCHUR [11]: Another option for bundle adjustment like problems.

1.2. Dogleg [4] Dogleg method can only be used with the exact factorization based linear solvers contrast to LM algorithm.

Line search methods [5] (Note that the implementation of line search algorithms in ceres solver is beta quality) Ceres solver has several implementations of line search methods, each of which has different search direction decision + one dimensional optimization.

2.1. Search direction Currently, ceres solver supports three choices of search directions: Steepest descent, Nonlinear conjugate gradient, BFGS, and LBGFS. Ceres solver has several implementations of line search methods.