General Unconstrained Minimization

Ceres Solver besides being able to solve non-linear least squares problem can also solve general unconstrained problems using just their objective function value and gradients. In this chapter we will see how to do this.

Rosenbrock’s Function

Consider minimizing the famous Rosenbrock’s function [1].

The simplest way to minimize is to define a templated functor to evaluate the objective value of this function and then use Ceres Solver’s automatic differentiation to compute its derivatives.

We begin by defining a templated functor and then using AutoDiffFirstOrderFunction to construct an instance of the FirstOrderFunction interface. This is the object that is responsible for computing the objective function value and the gradient (if required). This is the analog of the CostFunction when defining non-linear least squares problems in Ceres.

// f(x,y) = (1-x)^2 + 100(y - x^2)^2;
struct Rosenbrock {
  template <typename T>
  bool operator()(const T* parameters, T* cost) const {
    const T x = parameters[0];
    const T y = parameters[1];
    cost[0] = (1.0 - x) * (1.0 - x) + 100.0 * (y - x * x) * (y - x * x);
    return true;
  }

  static ceres::FirstOrderFunction* Create() {
    constexpr int kNumParameters = 2;
    return new ceres::AutoDiffFirstOrderFunction<Rosenbrock, kNumParameters>();
  }
};

Minimizing it then is a straightforward matter of constructing a GradientProblem object and calling Solve() on it.

double parameters[2] = {-1.2, 1.0};

ceres::GradientProblem problem(Rosenbrock::Create());

ceres::GradientProblemSolver::Options options;
options.minimizer_progress_to_stdout = true;
ceres::GradientProblemSolver::Summary summary;
ceres::Solve(options, problem, parameters, &summary);

std::cout << summary.FullReport() << "\n";

Executing this code results, solve the problem using limited memory BFGS algorithm.

   0: f: 2.420000e+01 d: 0.00e+00 g: 2.16e+02 h: 0.00e+00 s: 0.00e+00 e:  0 it: 1.19e-05 tt: 1.19e-05
   1: f: 4.280493e+00 d: 1.99e+01 g: 1.52e+01 h: 2.01e-01 s: 8.62e-04 e:  2 it: 7.30e-05 tt: 1.72e-04
   2: f: 3.571154e+00 d: 7.09e-01 g: 1.35e+01 h: 3.78e-01 s: 1.34e-01 e:  3 it: 1.60e-05 tt: 1.93e-04
   3: f: 3.440869e+00 d: 1.30e-01 g: 1.73e+01 h: 1.36e-01 s: 1.00e+00 e:  1 it: 9.54e-07 tt: 1.97e-04
   4: f: 3.213597e+00 d: 2.27e-01 g: 1.55e+01 h: 1.06e-01 s: 4.59e-01 e:  1 it: 1.19e-06 tt: 2.00e-04
   5: f: 2.839723e+00 d: 3.74e-01 g: 1.05e+01 h: 1.34e-01 s: 5.24e-01 e:  1 it: 9.54e-07 tt: 2.03e-04
   6: f: 2.448490e+00 d: 3.91e-01 g: 1.29e+01 h: 3.04e-01 s: 1.00e+00 e:  1 it: 9.54e-07 tt: 2.05e-04
   7: f: 1.943019e+00 d: 5.05e-01 g: 4.00e+00 h: 8.81e-02 s: 7.43e-01 e:  1 it: 9.54e-07 tt: 2.08e-04
   8: f: 1.731469e+00 d: 2.12e-01 g: 7.36e+00 h: 1.71e-01 s: 4.60e-01 e:  2 it: 2.15e-06 tt: 2.11e-04
   9: f: 1.503267e+00 d: 2.28e-01 g: 6.47e+00 h: 8.66e-02 s: 1.00e+00 e:  1 it: 9.54e-07 tt: 2.14e-04
  10: f: 1.228331e+00 d: 2.75e-01 g: 2.00e+00 h: 7.70e-02 s: 7.90e-01 e:  1 it: 0.00e+00 tt: 2.16e-04
  11: f: 1.016523e+00 d: 2.12e-01 g: 5.15e+00 h: 1.39e-01 s: 3.76e-01 e:  2 it: 1.91e-06 tt: 2.25e-04
  12: f: 9.145773e-01 d: 1.02e-01 g: 6.74e+00 h: 7.98e-02 s: 1.00e+00 e:  1 it: 9.54e-07 tt: 2.28e-04
  13: f: 7.508302e-01 d: 1.64e-01 g: 3.88e+00 h: 5.76e-02 s: 4.93e-01 e:  1 it: 9.54e-07 tt: 2.30e-04
  14: f: 5.832378e-01 d: 1.68e-01 g: 5.56e+00 h: 1.42e-01 s: 1.00e+00 e:  1 it: 9.54e-07 tt: 2.33e-04
  15: f: 3.969581e-01 d: 1.86e-01 g: 1.64e+00 h: 1.17e-01 s: 1.00e+00 e:  1 it: 1.19e-06 tt: 2.36e-04
  16: f: 3.171557e-01 d: 7.98e-02 g: 3.84e+00 h: 1.18e-01 s: 3.97e-01 e:  2 it: 1.91e-06 tt: 2.39e-04
  17: f: 2.641257e-01 d: 5.30e-02 g: 3.27e+00 h: 6.14e-02 s: 1.00e+00 e:  1 it: 1.19e-06 tt: 2.42e-04
  18: f: 1.909730e-01 d: 7.32e-02 g: 5.29e-01 h: 8.55e-02 s: 6.82e-01 e:  1 it: 9.54e-07 tt: 2.45e-04
  19: f: 1.472012e-01 d: 4.38e-02 g: 3.11e+00 h: 1.20e-01 s: 3.47e-01 e:  2 it: 1.91e-06 tt: 2.49e-04
  20: f: 1.093558e-01 d: 3.78e-02 g: 2.97e+00 h: 8.43e-02 s: 1.00e+00 e:  1 it: 2.15e-06 tt: 2.52e-04
  21: f: 6.710346e-02 d: 4.23e-02 g: 1.42e+00 h: 9.64e-02 s: 8.85e-01 e:  1 it: 8.82e-06 tt: 2.81e-04
  22: f: 3.993377e-02 d: 2.72e-02 g: 2.30e+00 h: 1.29e-01 s: 4.63e-01 e:  2 it: 7.87e-06 tt: 2.96e-04
  23: f: 2.911794e-02 d: 1.08e-02 g: 2.55e+00 h: 6.55e-02 s: 1.00e+00 e:  1 it: 9.54e-07 tt: 3.00e-04
  24: f: 1.457683e-02 d: 1.45e-02 g: 2.77e-01 h: 6.37e-02 s: 6.14e-01 e:  1 it: 1.19e-06 tt: 3.03e-04
  25: f: 8.577515e-03 d: 6.00e-03 g: 2.86e+00 h: 1.40e-01 s: 1.00e+00 e:  1 it: 9.54e-07 tt: 3.06e-04
  26: f: 3.486574e-03 d: 5.09e-03 g: 1.76e-01 h: 1.23e-02 s: 1.00e+00 e:  1 it: 1.19e-06 tt: 3.09e-04
  27: f: 1.257570e-03 d: 2.23e-03 g: 1.39e-01 h: 5.08e-02 s: 1.00e+00 e:  1 it: 9.54e-07 tt: 3.12e-04
  28: f: 2.783568e-04 d: 9.79e-04 g: 6.20e-01 h: 6.47e-02 s: 1.00e+00 e:  1 it: 9.54e-07 tt: 3.15e-04
  29: f: 2.533399e-05 d: 2.53e-04 g: 1.68e-02 h: 1.98e-03 s: 1.00e+00 e:  1 it: 9.54e-07 tt: 3.17e-04
  30: f: 7.591572e-07 d: 2.46e-05 g: 5.40e-03 h: 9.27e-03 s: 1.00e+00 e:  1 it: 9.54e-07 tt: 3.20e-04
  31: f: 1.902460e-09 d: 7.57e-07 g: 1.62e-03 h: 1.89e-03 s: 1.00e+00 e:  1 it: 9.54e-07 tt: 3.23e-04
  32: f: 1.003030e-12 d: 1.90e-09 g: 3.50e-05 h: 3.52e-05 s: 1.00e+00 e:  1 it: 9.54e-07 tt: 3.26e-04
  33: f: 4.835994e-17 d: 1.00e-12 g: 1.05e-07 h: 1.13e-06 s: 1.00e+00 e:  1 it: 1.19e-06 tt: 3.34e-04
  34: f: 1.885250e-22 d: 4.84e-17 g: 2.69e-10 h: 1.45e-08 s: 1.00e+00 e:  1 it: 9.54e-07 tt: 3.37e-04

Solver Summary (v 2.2.0-eigen-(3.4.0)-lapack-suitesparse-(7.1.0)-metis-(5.1.0)-acceleratesparse-eigensparse)

Parameters                                  2
Line search direction              LBFGS (20)
Line search type                  CUBIC WOLFE


Cost:
Initial                          2.420000e+01
Final                            1.955192e-27
Change                           2.420000e+01

Minimizer iterations                       36

Time (in seconds):

  Cost evaluation                    0.000000 (0)
  Gradient & cost evaluation         0.000000 (44)
  Polynomial minimization            0.000061
Total                                0.000438

Termination:                      CONVERGENCE (Parameter tolerance reached. Relative step_norm: 1.890726e-11 <= 1.000000e-08.)

Initial x: -1.2 y: 1
Final   x: 1 y: 1

If you are unable to use automatic differentiation for some reason (say because you need to call an external library), then you can use numeric differentiation. In that case the functor is defined as follows [2].

// f(x,y) = (1-x)^2 + 100(y - x^2)^2;
struct Rosenbrock {
  bool operator()(const double* parameters, double* cost) const {
    const double x = parameters[0];
    const double y = parameters[1];
    cost[0] = (1.0 - x) * (1.0 - x) + 100.0 * (y - x * x) * (y - x * x);
    return true;
  }

  static ceres::FirstOrderFunction* Create() {
    constexpr int kNumParameters = 2;
    return new ceres::NumericDiffFirstOrderFunction<Rosenbrock,
                                                    ceres::CENTRAL,
                                                    kNumParameters>();
  }
};

And finally, if you would rather compute the derivatives by hand (say because the size of the parameter vector is too large to be automatically differentiated). Then you should define an instance of FirstOrderFunction, which is the analog of CostFunction for non-linear least squares problems [3].

// f(x,y) = (1-x)^2 + 100(y - x^2)^2;
class Rosenbrock final  : public ceres::FirstOrderFunction {
  public:
    bool Evaluate(const double* parameters,
                           double* cost,
                           double* gradient) const override {
       const double x = parameters[0];
       const double y = parameters[1];

       cost[0] = (1.0 - x) * (1.0 - x) + 100.0 * (y - x * x) * (y - x * x);
       if (gradient) {
         gradient[0] = -2.0 * (1.0 - x) - 200.0 * (y - x * x) * 2.0 * x;
         gradient[1] = 200.0 * (y - x * x);
       }
      return true;
   }

   int NumParameters() const override { return 2; }
};

Footnotes