10ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Ceres Solver - A fast non-linear least squares minimizer 20ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Copyright 2012 Google Inc. All rights reserved. 30ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// http://code.google.com/p/ceres-solver/ 40ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 50ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Redistribution and use in source and binary forms, with or without 60ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// modification, are permitted provided that the following conditions are met: 70ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 80ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * Redistributions of source code must retain the above copyright notice, 90ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// this list of conditions and the following disclaimer. 100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * Redistributions in binary form must reproduce the above copyright notice, 110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// this list of conditions and the following disclaimer in the documentation 120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// and/or other materials provided with the distribution. 130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * Neither the name of Google Inc. nor the names of its contributors may be 140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// used to endorse or promote products derived from this software without 150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// specific prior written permission. 160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// POSSIBILITY OF SUCH DAMAGE. 280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Author: keir@google.com (Keir Mierle) 300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// sameeragarwal@google.com (Sameer Agarwal) 310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// This tests the TrustRegionMinimizer loop using a direct Evaluator 330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// implementation, rather than having a test that goes through all the 340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Program and Problem machinery. 350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include <cmath> 370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/cost_function.h" 380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/dense_qr_solver.h" 390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/dense_sparse_matrix.h" 400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/evaluator.h" 410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/internal/port.h" 420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/linear_solver.h" 430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/minimizer.h" 440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/problem.h" 450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/trust_region_minimizer.h" 460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/trust_region_strategy.h" 470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "gtest/gtest.h" 480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongnamespace ceres { 500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongnamespace internal { 510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Templated Evaluator for Powell's function. The template parameters 530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// indicate which of the four variables/columns of the jacobian are 540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// active. This is equivalent to constructing a problem and using the 550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// SubsetLocalParameterization. This allows us to test the support for 560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// the Evaluator::Plus operation besides checking for the basic 570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// performance of the trust region algorithm. 580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongtemplate <bool col1, bool col2, bool col3, bool col4> 590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongclass PowellEvaluator2 : public Evaluator { 600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong public: 610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong PowellEvaluator2() 620ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong : num_active_cols_( 630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong (col1 ? 1 : 0) + 640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong (col2 ? 1 : 0) + 650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong (col3 ? 1 : 0) + 660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong (col4 ? 1 : 0)) { 670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong VLOG(1) << "Columns: " 680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong << col1 << " " 690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong << col2 << " " 700ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong << col3 << " " 710ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong << col4; 720ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 730ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong virtual ~PowellEvaluator2() {} 750ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 760ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Implementation of Evaluator interface. 770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong virtual SparseMatrix* CreateJacobian() const { 780ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong CHECK(col1 || col2 || col3 || col4); 790ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong DenseSparseMatrix* dense_jacobian = 800ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong new DenseSparseMatrix(NumResiduals(), NumEffectiveParameters()); 810ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong dense_jacobian->SetZero(); 820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return dense_jacobian; 830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 840ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling virtual bool Evaluate(const Evaluator::EvaluateOptions& evaluate_options, 861d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double* state, 870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double* cost, 880ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double* residuals, 891d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling double* gradient, 900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong SparseMatrix* jacobian) { 911d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double x1 = state[0]; 921d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double x2 = state[1]; 931d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double x3 = state[2]; 941d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double x4 = state[3]; 950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong VLOG(1) << "State: " 970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong << "x1=" << x1 << ", " 980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong << "x2=" << x2 << ", " 990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong << "x3=" << x3 << ", " 1000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong << "x4=" << x4 << "."; 1010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1021d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double f1 = x1 + 10.0 * x2; 1031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double f2 = sqrt(5.0) * (x3 - x4); 1041d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double f3 = pow(x2 - 2.0 * x3, 2.0); 1051d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const double f4 = sqrt(10.0) * pow(x1 - x4, 2.0); 1060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong VLOG(1) << "Function: " 1080ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong << "f1=" << f1 << ", " 1090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong << "f2=" << f2 << ", " 1100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong << "f3=" << f3 << ", " 1110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong << "f4=" << f4 << "."; 1120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong *cost = (f1*f1 + f2*f2 + f3*f3 + f4*f4) / 2.0; 1140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong VLOG(1) << "Cost: " << *cost; 1160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (residuals != NULL) { 1180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong residuals[0] = f1; 1190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong residuals[1] = f2; 1200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong residuals[2] = f3; 1210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong residuals[3] = f4; 1220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 1230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (jacobian != NULL) { 1250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong DenseSparseMatrix* dense_jacobian; 1260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong dense_jacobian = down_cast<DenseSparseMatrix*>(jacobian); 1270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong dense_jacobian->SetZero(); 1280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1291d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ColMajorMatrixRef jacobian_matrix = dense_jacobian->mutable_matrix(); 1300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong CHECK_EQ(jacobian_matrix.cols(), num_active_cols_); 1310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int column_index = 0; 1330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (col1) { 1340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong jacobian_matrix.col(column_index++) << 1350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1.0, 1360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 0.0, 1370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 0.0, 1380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong sqrt(10.0) * 2.0 * (x1 - x4) * (1.0 - x4); 1390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 1400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (col2) { 1410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong jacobian_matrix.col(column_index++) << 1420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 10.0, 1430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 0.0, 1440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2.0*(x2 - 2.0*x3)*(1.0 - 2.0*x3), 1450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 0.0; 1460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 1470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (col3) { 1490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong jacobian_matrix.col(column_index++) << 1500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 0.0, 1510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong sqrt(5.0), 1520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2.0*(x2 - 2.0*x3)*(x2 - 2.0), 1530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 0.0; 1540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 1550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (col4) { 1570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong jacobian_matrix.col(column_index++) << 1580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 0.0, 1590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong -sqrt(5.0), 1600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 0.0, 1610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong sqrt(10.0) * 2.0 * (x1 - x4) * (x1 - 1.0); 1620ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 1630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong VLOG(1) << "\n" << jacobian_matrix; 1640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 1651d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1661d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (gradient != NULL) { 1671d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling int column_index = 0; 1681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (col1) { 1691d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling gradient[column_index++] = f1 + f4 * sqrt(10.0) * 2.0 * (x1 - x4); 1701d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 1711d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1721d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (col2) { 1731d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling gradient[column_index++] = f1 * 10.0 + f3 * 2.0 * (x2 - 2.0 * x3); 1741d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 1751d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1761d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (col3) { 1771d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling gradient[column_index++] = 1781d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling f2 * sqrt(5.0) + f3 * (2.0 * 2.0 * (2.0 * x3 - x2)); 1791d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 1801d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling if (col4) { 1821d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling gradient[column_index++] = 1831d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling -f2 * sqrt(5.0) + f4 * sqrt(10.0) * 2.0 * (x4 - x1); 1841d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 1851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 1861d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return true; 1880ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 1890ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong virtual bool Plus(const double* state, 1910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const double* delta, 1920ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double* state_plus_delta) const { 1930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int delta_index = 0; 1940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong state_plus_delta[0] = (col1 ? state[0] + delta[delta_index++] : state[0]); 1950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong state_plus_delta[1] = (col2 ? state[1] + delta[delta_index++] : state[1]); 1960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong state_plus_delta[2] = (col3 ? state[2] + delta[delta_index++] : state[2]); 1970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong state_plus_delta[3] = (col4 ? state[3] + delta[delta_index++] : state[3]); 1980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return true; 1990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 2000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong virtual int NumEffectiveParameters() const { return num_active_cols_; } 2020ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong virtual int NumParameters() const { return 4; } 2030ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong virtual int NumResiduals() const { return 4; } 2040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2050ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong private: 2060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const int num_active_cols_; 2070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong}; 2080ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Templated function to hold a subset of the columns fixed and check 2100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// if the solver converges to the optimal values or not. 2110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongtemplate<bool col1, bool col2, bool col3, bool col4> 2120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongvoid IsTrustRegionSolveSuccessful(TrustRegionStrategyType strategy_type) { 2130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Solver::Options solver_options; 2140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong LinearSolver::Options linear_solver_options; 2150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong DenseQRSolver linear_solver(linear_solver_options); 2160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double parameters[4] = { 3, -1, 0, 1.0 }; 2180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // If the column is inactive, then set its value to the optimal 2200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // value. 2210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong parameters[0] = (col1 ? parameters[0] : 0.0); 2220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong parameters[1] = (col2 ? parameters[1] : 0.0); 2230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong parameters[2] = (col3 ? parameters[2] : 0.0); 2240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong parameters[3] = (col4 ? parameters[3] : 0.0); 2250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong PowellEvaluator2<col1, col2, col3, col4> powell_evaluator; 2270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong scoped_ptr<SparseMatrix> jacobian(powell_evaluator.CreateJacobian()); 2280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Minimizer::Options minimizer_options(solver_options); 2300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong minimizer_options.gradient_tolerance = 1e-26; 2310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong minimizer_options.function_tolerance = 1e-26; 2320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong minimizer_options.parameter_tolerance = 1e-26; 2330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong minimizer_options.evaluator = &powell_evaluator; 2340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong minimizer_options.jacobian = jacobian.get(); 2350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong TrustRegionStrategy::Options trust_region_strategy_options; 2370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong trust_region_strategy_options.trust_region_strategy_type = strategy_type; 2380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong trust_region_strategy_options.linear_solver = &linear_solver; 2390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong trust_region_strategy_options.initial_radius = 1e4; 2400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong trust_region_strategy_options.max_radius = 1e20; 2411d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling trust_region_strategy_options.min_lm_diagonal = 1e-6; 2421d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling trust_region_strategy_options.max_lm_diagonal = 1e32; 2430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong scoped_ptr<TrustRegionStrategy> strategy( 2440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong TrustRegionStrategy::Create(trust_region_strategy_options)); 2450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong minimizer_options.trust_region_strategy = strategy.get(); 2460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong TrustRegionMinimizer minimizer; 2480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Solver::Summary summary; 2490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong minimizer.Minimize(minimizer_options, parameters, &summary); 2500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // The minimum is at x1 = x2 = x3 = x4 = 0. 2520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_NEAR(0.0, parameters[0], 0.001); 2530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_NEAR(0.0, parameters[1], 0.001); 2540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_NEAR(0.0, parameters[2], 0.001); 2550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_NEAR(0.0, parameters[3], 0.001); 2560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong}; 2570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus KongTEST(TrustRegionMinimizer, PowellsSingularFunctionUsingLevenbergMarquardt) { 2590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // This case is excluded because this has a local minimum and does 2600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // not find the optimum. This should not affect the correctness of 2610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // this test since we are testing all the other 14 combinations of 2620ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // column activations. 2630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 2640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // IsSolveSuccessful<true, true, false, true>(); 2650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const TrustRegionStrategyType kStrategy = LEVENBERG_MARQUARDT; 2670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<true, true, true, true >(kStrategy); 2680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<true, true, true, false>(kStrategy); 2690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<true, false, true, true >(kStrategy); 2700ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<false, true, true, true >(kStrategy); 2710ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<true, true, false, false>(kStrategy); 2720ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<true, false, true, false>(kStrategy); 2730ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<false, true, true, false>(kStrategy); 2740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<true, false, false, true >(kStrategy); 2750ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<false, true, false, true >(kStrategy); 2760ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<false, false, true, true >(kStrategy); 2770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<true, false, false, false>(kStrategy); 2780ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<false, true, false, false>(kStrategy); 2790ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<false, false, true, false>(kStrategy); 2800ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<false, false, false, true >(kStrategy); 2810ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} 2820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus KongTEST(TrustRegionMinimizer, PowellsSingularFunctionUsingDogleg) { 2841d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // The following two cases are excluded because they encounter a 2851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // local minimum. 2860ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 2870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // IsTrustRegionSolveSuccessful<true, true, false, true >(kStrategy); 2880ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // IsTrustRegionSolveSuccessful<true, true, true, true >(kStrategy); 2890ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 2900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const TrustRegionStrategyType kStrategy = DOGLEG; 2910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<true, true, true, false>(kStrategy); 2920ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<true, false, true, true >(kStrategy); 2930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<false, true, true, true >(kStrategy); 2940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<true, true, false, false>(kStrategy); 2950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<true, false, true, false>(kStrategy); 2960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<false, true, true, false>(kStrategy); 2970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<true, false, false, true >(kStrategy); 2980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<false, true, false, true >(kStrategy); 2990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<false, false, true, true >(kStrategy); 3000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<true, false, false, false>(kStrategy); 3010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<false, true, false, false>(kStrategy); 3020ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<false, false, true, false>(kStrategy); 3030ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong IsTrustRegionSolveSuccessful<false, false, false, true >(kStrategy); 3040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} 3050ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongclass CurveCostFunction : public CostFunction { 3080ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong public: 3090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong CurveCostFunction(int num_vertices, double target_length) 3100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong : num_vertices_(num_vertices), target_length_(target_length) { 3110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong set_num_residuals(1); 3120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong for (int i = 0; i < num_vertices_; ++i) { 3130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong mutable_parameter_block_sizes()->push_back(2); 3140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 3150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 3160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong bool Evaluate(double const* const* parameters, 3180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double* residuals, 3190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double** jacobians) const { 3200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong residuals[0] = target_length_; 3210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong for (int i = 0; i < num_vertices_; ++i) { 3230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int prev = (num_vertices_ + i - 1) % num_vertices_; 3240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double length = 0.0; 3250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong for (int dim = 0; dim < 2; dim++) { 3260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const double diff = parameters[prev][dim] - parameters[i][dim]; 3270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong length += diff * diff; 3280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 3290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong residuals[0] -= sqrt(length); 3300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 3310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (jacobians == NULL) { 3330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return true; 3340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 3350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong for (int i = 0; i < num_vertices_; ++i) { 3370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (jacobians[i] != NULL) { 3380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int prev = (num_vertices_ + i - 1) % num_vertices_; 3390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int next = (i + 1) % num_vertices_; 3400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double u[2], v[2]; 3420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double norm_u = 0., norm_v = 0.; 3430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong for (int dim = 0; dim < 2; dim++) { 3440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong u[dim] = parameters[i][dim] - parameters[prev][dim]; 3450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong norm_u += u[dim] * u[dim]; 3460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong v[dim] = parameters[next][dim] - parameters[i][dim]; 3470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong norm_v += v[dim] * v[dim]; 3480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 3490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong norm_u = sqrt(norm_u); 3510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong norm_v = sqrt(norm_v); 3520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong for (int dim = 0; dim < 2; dim++) { 3540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong jacobians[i][dim] = 0.; 3550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (norm_u > std::numeric_limits< double >::min()) { 3570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong jacobians[i][dim] -= u[dim] / norm_u; 3580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 3590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (norm_v > std::numeric_limits< double >::min()) { 3610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong jacobians[i][dim] += v[dim] / norm_v; 3620ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 3630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 3640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 3650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 3660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return true; 3680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 3690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3700ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong private: 3710ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int num_vertices_; 3720ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double target_length_; 3730ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong}; 3740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3750ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus KongTEST(TrustRegionMinimizer, JacobiScalingTest) { 3760ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int N = 6; 3770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong std::vector< double* > y(N); 3780ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const double pi = 3.1415926535897932384626433; 3790ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong for (int i = 0; i < N; i++) { 3800ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double theta = i * 2. * pi/ static_cast< double >(N); 3810ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong y[i] = new double[2]; 3820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong y[i][0] = cos(theta); 3830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong y[i][1] = sin(theta); 3840ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 3850ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3860ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Problem problem; 3870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong problem.AddResidualBlock(new CurveCostFunction(N, 10.), NULL, y); 3880ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Solver::Options options; 3890ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong options.linear_solver_type = ceres::DENSE_QR; 3900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Solver::Summary summary; 3910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Solve(options, &problem, &summary); 3920ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_LE(summary.final_cost, 1e-10); 3930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong for (int i = 0; i < N; i++) { 3951d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling delete []y[i]; 3960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 3970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} 3980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} // namespace internal 4000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} // namespace ceres 401