Ceres Solver

  1 // Ceres Solver - A fast non-linear least squares minimizer
  2 // Copyright 2015 Google Inc. All rights reserved.
  3 // http://ceres-solver.org/
  4 //
  5 // Redistribution and use in source and binary forms, with or without
  6 // modification, are permitted provided that the following conditions are met:
  7 //
  8 // * Redistributions of source code must retain the above copyright notice,
  9 //   this list of conditions and the following disclaimer.
 10 // * Redistributions in binary form must reproduce the above copyright notice,
 11 //   this list of conditions and the following disclaimer in the documentation
 12 //   and/or other materials provided with the distribution.
 13 // * Neither the name of Google Inc. nor the names of its contributors may be
 14 //   used to endorse or promote products derived from this software without
 15 //   specific prior written permission.
 16 //
 17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 18 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 19 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 20 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 21 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 22 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 23 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 24 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 25 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 26 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 27 // POSSIBILITY OF SUCH DAMAGE.
 28 //
 29 // Author: sameeragarwal@google.com (Sameer Agarwal)
 30 //
 31 // An example program that minimizes Powell‘s singular function.
 32 //
 33 //   F = 1/2 (f1^2 + f2^2 + f3^2 + f4^2)
 34 //
 35 //   f1 = x1 + 10*x2;
 36 //   f2 = sqrt(5) * (x3 - x4)
 37 //   f3 = (x2 - 2*x3)^2
 38 //   f4 = sqrt(10) * (x1 - x4)^2
 39 //
 40 // The starting values are x1 = 3, x2 = -1, x3 = 0, x4 = 1.
 41 // The minimum is 0 at (x1, x2, x3, x4) = 0.
 42 //
 43 // From: Testing Unconstrained Optimization Software by Jorge J. More, Burton S.
 44 // Garbow and Kenneth E. Hillstrom in ACM Transactions on Mathematical Software,
 45 // Vol 7(1), March 1981.
 46 
 47 #include <vector>
 48 #include "ceres/ceres.h"
 49 #include "gflags/gflags.h"
 50 #include "glog/logging.h"
 51 
 52 using ceres::AutoDiffCostFunction;
 53 using ceres::CostFunction;
 54 using ceres::Problem;
 55 using ceres::Solver;
 56 using ceres::Solve;
 57 
 58 struct F1 {
 59   template <typename T> bool operator()(const T* const x1,
 60                                         const T* const x2,
 61                                         T* residual) const {
 62     // f1 = x1 + 10 * x2;
 63     residual[0] = x1[0] + 10.0 * x2[0];
 64     return true;
 65   }
 66 };
 67 
 68 struct F2 {
 69   template <typename T> bool operator()(const T* const x3,
 70                                         const T* const x4,
 71                                         T* residual) const {
 72     // f2 = sqrt(5) (x3 - x4)
 73     residual[0] = sqrt(5.0) * (x3[0] - x4[0]);
 74     return true;
 75   }
 76 };
 77 
 78 struct F3 {
 79   template <typename T> bool operator()(const T* const x2,
 80                                         const T* const x3,
 81                                         T* residual) const {
 82     // f3 = (x2 - 2 x3)^2
 83     residual[0] = (x2[0] - 2.0 * x3[0]) * (x2[0] - 2.0 * x3[0]);
 84     return true;
 85   }
 86 };
 87 
 88 struct F4 {
 89   template <typename T> bool operator()(const T* const x1,
 90                                         const T* const x4,
 91                                         T* residual) const {
 92     // f4 = sqrt(10) (x1 - x4)^2
 93     residual[0] = sqrt(10.0) * (x1[0] - x4[0]) * (x1[0] - x4[0]);
 94     return true;
 95   }
 96 };
 97 
 98 DEFINE_string(minimizer, "trust_region",
 99               "Minimizer type to use, choices are: line_search & trust_region");
100 
101 int main(int argc, char** argv) {
102   CERES_GFLAGS_NAMESPACE::ParseCommandLineFlags(&argc, &argv, true);
103   google::InitGoogleLogging(argv[0]);
104 
105   double x1 =  3.0;
106   double x2 = -1.0;
107   double x3 =  0.0;
108   double x4 =  1.0;
109 
110   Problem problem;
111   // Add residual terms to the problem using the using the autodiff
112   // wrapper to get the derivatives automatically. The parameters, x1 through
113   // x4, are modified in place.
114   problem.AddResidualBlock(new AutoDiffCostFunction<F1, 1, 1, 1>(new F1),
115                            NULL,
116                            &x1, &x2);
117   problem.AddResidualBlock(new AutoDiffCostFunction<F2, 1, 1, 1>(new F2),
118                            NULL,
119                            &x3, &x4);
120   problem.AddResidualBlock(new AutoDiffCostFunction<F3, 1, 1, 1>(new F3),
121                            NULL,
122                            &x2, &x3);
123   problem.AddResidualBlock(new AutoDiffCostFunction<F4, 1, 1, 1>(new F4),
124                            NULL,
125                            &x1, &x4);
126 
127   Solver::Options options;
128   LOG_IF(FATAL, !ceres::StringToMinimizerType(FLAGS_minimizer,
129                                               &options.minimizer_type))
130       << "Invalid minimizer: " << FLAGS_minimizer
131       << ", valid options are: trust_region and line_search.";
132 
133   options.max_num_iterations = 100;
134   options.linear_solver_type = ceres::DENSE_QR;
135   options.minimizer_progress_to_stdout = true;
136 
137   std::cout << "Initial x1 = " << x1
138             << ", x2 = " << x2
139             << ", x3 = " << x3
140             << ", x4 = " << x4
141             << "\n";
142 
143   // Run the solver!
144   Solver::Summary summary;
145   Solve(options, &problem, &summary);
146 
147   std::cout << summary.FullReport() << "\n";
148   std::cout << "Final x1 = " << x1
149             << ", x2 = " << x2
150             << ", x3 = " << x3
151             << ", x4 = " << x4
152             << "\n";
153   return 0;
154 }