Documentation update.
Change-Id: Ica8681f4bb58c60349d0dae453c652f2522eebf6
diff --git a/docs/ceres-solver.tex b/docs/ceres-solver.tex
index cf5e52d..05cc021 100644
--- a/docs/ceres-solver.tex
+++ b/docs/ceres-solver.tex
@@ -1,7 +1,7 @@
%%% Build instructions
%%% pdflatex -shell-escape ceres && bibtex ceres && pdflatex -shell-escape ceres && pdflatex -shell-escape ceres
-\documentclass[11pt,letterpaper,oneside]{memoir}
+\documentclass[10pt,letterpaper,oneside]{memoir}
\usepackage{fouriernc}
\usepackage[T1]{fontenc}
\usepackage{minted,amsmath,amssymb,amsthm,url,booktabs}
@@ -63,9 +63,9 @@
\MakeLowercase{Ceres Solver: Tutorial \& Reference}
}
\author{
-\scshape\MakeLowercase{Sameer Agarwal} \\ \texttt{sameeragarwal@google.com}
-\and
-\scshape\MakeLowercase{Keir Mierle} \\ \texttt{ keir@google.com}
+\scshape\MakeLowercase{Sameer Agarwal} \\ \texttt{sameeragarwal@google.com}
+\and
+\scshape\MakeLowercase{Keir Mierle} \\ \texttt{ mierle@gmail.com}
}
\checkandfixthelayout
@@ -104,9 +104,9 @@
Building this pdf from source requires a relatively recent installation of \texttt{LaTeX}~\footnote{\url{http://www.tug.org/texlive/}}, \texttt{minted.sty}\footnote{\url{http://code.google.com/p/minted/}} and \texttt{pygments}\footnote{\url{http://pygments.org/}}.
Despite our best efforts, this manual remains a work in progress and the source code for Ceres Solver remains the ultimate reference.
-
\input{changes}
\input{introduction}
+\input{license}
\input{build}
%% Tutorial
diff --git a/docs/changes.tex b/docs/changes.tex
index 159340a..72f7950 100644
--- a/docs/changes.tex
+++ b/docs/changes.tex
@@ -1,6 +1,23 @@
%!TEX root = ceres-solver.tex
\chapter{Version History}
+\section*{1.5.0}
+\subsection{New Features}
+\begin{itemize}
+\item Ceres now supports Line search based optimization algorithms in addition to trust region algorithms. Currently there is support for gradient descent, non-linear conjugate gradient and LBFGS search directions.
+\item Speedup the robust loss function correction logic when residual is one dimensional.
+\item Changed \texttt{NumericDiffCostFunction} to take functors like \texttt{AutoDiffCostFunction}.
+\item Added support for mixing automatic, analytic and numeric differentiation. This is done by adding \texttt{CostFunctionToFunctor} and \texttt{NumericDiffFunctor} objects.
+\end{itemize}
+
+\subsection{Bug Fixes}
+\begin{itemize}
+\item Fixed varidic evaluation bug in \texttt{AutoDiff}.
+\item Fixed \texttt{SolverImpl} tests.
+\item Fixed a bug in \texttt{DenseSparseMatrix::ToDenseMatrix()}.
+\item Fixed an initialization bug in \texttt{ProgramEvaluator}.
+\end{itemize}
+
\section*{1.4.0}
\subsection{API Changes}
The new ordering API breaks existing code. Here the common case fixes.
diff --git a/docs/curvefitting.tex b/docs/curvefitting.tex
index 07ccd48..c4bacc2 100644
--- a/docs/curvefitting.tex
+++ b/docs/curvefitting.tex
@@ -17,7 +17,8 @@
template <typename T> bool operator()(const T* const m,
const T* const c,
T* residual) const {
- residual[0] = T(y_) - exp(m[0] * T(x_) + c[0]); // $y - e^{mx + c}$
+ // $y - e^{mx + c}$
+ residual[0] = T(y_) - exp(m[0] * T(x_) + c[0]);
return true;
}
diff --git a/docs/helloworld.tex b/docs/helloworld.tex
index 04b677a..938ecba 100644
--- a/docs/helloworld.tex
+++ b/docs/helloworld.tex
@@ -5,7 +5,7 @@
\begin{equation}
\frac{1}{2}(10 -x)^2.
\end{equation}
-This is a trivial problem, whose minimum is easy to see is located at $x = 10$, but it is a good place to start to illustrate the basics of solving a problem with Ceres\footnote{Full working code for this and other examples in this manual can be found in the \texttt{examples} directory. Code for this example can be found in \texttt{examples/quadratic.cc}}.
+This is a trivial problem, whose minimum is located at $x = 10$, but it is a good place to start to illustrate the basics of solving a problem with Ceres\footnote{Full working code for this and other examples in this manual can be found in the \texttt{examples} directory. Code for this example can be found in \texttt{examples/quadratic.cc}}.
Let us write this problem as a non-linear least squares problem by defining the scalar residual function $f_1(x) = 10 - x$. Then $F(x) = [f_1(x)]$ is a residual vector with exactly one component.
diff --git a/docs/introduction.tex b/docs/introduction.tex
index 65afef3..e9b845b 100644
--- a/docs/introduction.tex
+++ b/docs/introduction.tex
@@ -38,37 +38,3 @@
Nathan Wiegand contributed the MacOS port.
-\chapter{License}
-Ceres Solver is licensed under the New BSD license, whose terms are as follows.
-
-\begin{quotation}
-
-\noindent
-Copyright (c) 2010, 2011, 2012, Google Inc. All rights reserved.
-
-\noindent
-Redistribution and use in source and binary forms, with or without
-modification, are permitted provided that the following conditions are met:
-\begin{enumerate}
-\item Redistributions of source code must retain the above copyright notice,
- this list of conditions and the following disclaimer.
-\item Redistributions in binary form must reproduce the above copyright notice,
- this list of conditions and the following disclaimer in the documentation
- and/or other materials provided with the distribution.
-\item Neither the name of Google Inc., nor the names of its contributors may
- be used to endorse or promote products derived from this software without
- specific prior written permission.
-\end{enumerate}
-
-\noindent
-This software is provided by the copyright holders and contributors "AS IS" and
-any express or implied warranties, including, but not limited to, the implied
-warranties of merchantability and fitness for a particular purpose are
-disclaimed. In no event shall Google Inc. be liable for any direct, indirect,
-incidental, special, exemplary, or consequential damages (including, but not
-limited to, procurement of substitute goods or services; loss of use, data, or
-profits; or business interruption) however caused and on any theory of
-liability, whether in contract, strict liability, or tort (including negligence
-or otherwise) arising in any way out of the use of this software, even if
-advised of the possibility of such damage.
-\end{quotation}
diff --git a/docs/license.tex b/docs/license.tex
new file mode 100644
index 0000000..380e6e2
--- /dev/null
+++ b/docs/license.tex
@@ -0,0 +1,35 @@
+%!TEX root = ceres-solver.tex
+\chapter{License}
+Ceres Solver is licensed under the New BSD license, whose terms are as follows.
+
+\begin{quotation}
+
+\noindent
+Copyright (c) 2010, 2011, 2012, Google Inc. All rights reserved.
+
+\noindent
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+\begin{enumerate}
+\item Redistributions of source code must retain the above copyright notice,
+ this list of conditions and the following disclaimer.
+\item Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+\item Neither the name of Google Inc., nor the names of its contributors may
+ be used to endorse or promote products derived from this software without
+ specific prior written permission.
+\end{enumerate}
+
+\noindent
+This software is provided by the copyright holders and contributors "AS IS" and
+any express or implied warranties, including, but not limited to, the implied
+warranties of merchantability and fitness for a particular purpose are
+disclaimed. In no event shall Google Inc. be liable for any direct, indirect,
+incidental, special, exemplary, or consequential damages (including, but not
+limited to, procurement of substitute goods or services; loss of use, data, or
+profits; or business interruption) however caused and on any theory of
+liability, whether in contract, strict liability, or tort (including negligence
+or otherwise) arising in any way out of the use of this software, even if
+advised of the possibility of such damage.
+\end{quotation}
diff --git a/docs/modeling.tex b/docs/modeling.tex
index e6dce1f..40fc844 100644
--- a/docs/modeling.tex
+++ b/docs/modeling.tex
@@ -1,13 +1,33 @@
%!TEX root = ceres-solver.tex
\chapter{Modeling}
\label{chapter:api}
+
+\section{Introduction}
+Ceres solves robustified non-linear least squares problems of the form
+\begin{equation}
+\frac{1}{2}\sum_{i=1} \rho_i\left(\left\|f_i\left(x_{i_1},\hdots,x_{i_k}\right)\right\|^2\right).
+\label{eq:ceresproblem}
+\end{equation}
+The term
+$\rho_i\left(\left\|f_i\left(x_{i_1},\hdots,x_{i_k}\right)\right\|^2\right)$
+is known as a Residual Block, where $f_i(\cdot)$ is a cost function
+that depends on the parameter blocks $\left[x_{i_1}, \hdots ,
+ x_{i_k}\right]$ and $\rho_i$ is a loss function. In most
+optimization problems small groups of scalars occur together. For
+example the three components of a translation vector and the four
+components of the quaternion that define the pose of a camera. We
+refer to such a group of small scalars as a
+\texttt{ParameterBlock}. Of course a \texttt{ParameterBlock} can just
+have a single parameter.
+
\section{\texttt{CostFunction}}
+\label{sec:costfunction}
Given parameter blocks $\left[x_{i_1}, \hdots , x_{i_k}\right]$, a
\texttt{CostFunction} is responsible for computing
a vector of residuals and if asked a vector of Jacobian matrices, i.e., given $\left[x_{i_1}, \hdots , x_{i_k}\right]$, compute the vector $f_i\left(x_{i_1},\hdots,x_{i_k}\right)$ and the matrices
\begin{equation}
-J_{ij} = \frac{\partial}{\partial x_{j}}f_i\left(x_{i_1},\hdots,x_{i_k}\right),\quad \forall j \in \{i_1,\hdots, i_k\}
+J_{ij} = \frac{\partial}{\partial x_{i_j}}f_i\left(x_{i_1},\hdots,x_{i_k}\right),\quad \forall j \in \{i_1,\hdots, i_k\}
\end{equation}
\begin{minted}{c++}
class CostFunction {
@@ -460,19 +480,16 @@
\texttt{AddParameterBlock} explicitly adds a parameter block to the \texttt{Problem}. Optionally it allows the user to associate a LocalParameterization object with the parameter block too. Repeated calls with the same arguments are ignored. Repeated
calls with the same double pointer but a different size results in undefined behaviour.
-You can set any parameter block to be constant using
-
-\texttt{Problem::SetParameterBlockConstant}
-
-and undo this using
-
-\texttt{Problem::SetParameterBlockVariable}.
+You can set any parameter block to be constant using \texttt{SetParameterBlockConstant} and undo this using \texttt{SetParameterBlockVariable}.
In fact you can set any number of parameter blocks to be constant, and Ceres is smart enough to figure out what part of the problem you have constructed depends on the parameter blocks that are free to change and only spends time solving it. So for example if you constructed a problem with a million parameter blocks and 2 million residual blocks, but then set all but one parameter blocks to be constant and say only 10 residual blocks depend on this one non-constant parameter block. Then the computational effort Ceres spends in solving this problem will be the same if you had defined a problem with one parameter block and 10 residual blocks.
+\subsubsection{Ownership}
\texttt{Problem} by default takes ownership of the
\texttt{cost\_function}, \texttt{loss\_function} and \\ \texttt{local\_parameterization} pointers. These objects remain
live for the life of the \texttt{Problem} object. If the user wishes to
keep control over the destruction of these objects, then they can
- do this by setting the corresponding enums in the \texttt{Options} struct. Even though \texttt{Problem} takes ownership of these pointers, it does not preclude the user from re-using them in another residual or parameter block. The destructor takes care to call
+ do this by setting the corresponding enums in the \texttt{Options} struct.
+
+Even though \texttt{Problem} takes ownership of these pointers, it does not preclude the user from re-using them in another residual or parameter block. The destructor takes care to call
delete on each pointer only once.
diff --git a/docs/powell.tex b/docs/powell.tex
index 5ff6ddc..ad86a42 100644
--- a/docs/powell.tex
+++ b/docs/powell.tex
@@ -39,7 +39,7 @@
\section{Automatic Differentiation}
\label{sec:tutorial:autodiff}
With its automatic differentiation support, Ceres allows you to define templated objects/functors that will compute the residual and it takes care of computing the Jacobians as needed and filling the \texttt{jacobians} arrays with them. For example, for $f_4(x)$ we define
-\begin{minted}[frame=lines,mathescape]{c++}
+\begin{minted}[mathescape]{c++}
class F4 {
public:
template <typename T> bool operator()(const T* const x1,
@@ -63,7 +63,7 @@
\begin{minted}[mathescape]{c++}
double x1 = 3.0; double x2 = -1.0; double x3 = 0.0; double x4 = 1.0;
// Add residual terms to the problem using the using the autodiff
-// wrapper to get the derivatives automatically.
+// wrapper to get the derivatives automatically.
problem.AddResidualBlock(
new ceres::AutoDiffCostFunction<F1, 1, 1, 1>(new F1), NULL, &x1, &x2);
problem.AddResidualBlock(
@@ -100,9 +100,30 @@
It is easy to see that the optimal solution to this problem is at $x_1=0, x_2=0, x_3=0, x_4=0$ with an objective function value of $0$. In 10 iterations, Ceres finds a solution with an objective function value of $4\times 10^{-12}$.
\section{Numeric Differentiation}
-If a templated implementation is not possible then a \texttt{NumericDiffCostFunction} object can be used. The user defines a \texttt{CostFunction} object whose \texttt{Evaluate} method is only computes the residuals. A wrapper object \texttt{NumericDiffCostFunction} then uses it to compute the residuals and the Jacobian using finite differencing. \texttt{examples/quadratic\_numeric\_diff.cc} shows a numerically differentiated implementation of \texttt{examples/quadratic.cc}.
+In some cases, its not possible to define a templated cost functor. In such a situation, numerical differentiation can be used. The user defines a functor which computes the residual value and construct a \texttt{NumericDiffCostFunction} using it. e.g., for \texttt{F4}, the corresponding functor would be
+\begin{minted}[mathescape]{c++}
+class F4 {
+ public:
+ bool operator()(const double* const x1,
+ const double* const x4,
+ double* residual) const {
+ // $f_4 = \sqrt{10} * (x_1 - x_4)^2$
+ residual[0] = sqrt(10.0) * (x1[0] - x4[0]) * (x1[0] - x4[0]);
+ return true;
+ }
+};
+\end{minted}
-We recommend that if possible, automatic differentiation should be used. The use of
-C++ templates makes automatic differentiation extremely efficient,
+Which can then be wrapped \texttt{NumericDiffCostFunction} and added to the \texttt{Problem} object as follows
+
+\begin{minted}[mathescape]{c++}
+problem.AddResidualBlock(
+ new ceres::NumericDiffCostFunction<F4, ceres::CENTRAL, 1, 1, 1>(new F4), NULL, &x1, &x4);
+\end{minted}
+
+The construction looks almost identical to the used for automatic differentiation, except for an extra template parameter that indicates the kind of finite differencing scheme to be used for computing the numerical derivatives. \texttt{examples/quadratic\_numeric\_diff.cc} shows a numerically differentiated implementation of \texttt{examples/quadratic.cc}.
+
+\textbf{We recommend that if possible, automatic differentiation should be used. The use of
+\texttt{C++} templates makes automatic differentiation extremely efficient,
whereas numeric differentiation can be quite expensive, prone to
-numeric errors and leads to slower convergence.
\ No newline at end of file
+numeric errors and leads to slower convergence.}
diff --git a/docs/reference-overview.tex b/docs/reference-overview.tex
index dac0ef2..23ab82b 100644
--- a/docs/reference-overview.tex
+++ b/docs/reference-overview.tex
@@ -1,18 +1,18 @@
%!TEX root = ceres-solver.tex
\chapter{Overview}
\label{chapter:overview}
-Ceres solves robustified non-linear least squares problems of the form
-\begin{equation}
-\frac{1}{2}\sum_{i=1} \rho_i\left(\left\|f_i\left(x_{i_1},\hdots,x_{i_k}\right)\right\|^2\right).
-\label{eq:ceresproblem}
-\end{equation}
-Where $f_i(\cdot)$ is a cost function that depends on the parameter blocks $\left[x_{i_1}, \hdots , x_{i_k}\right]$ and $\rho_i$ is a loss function. In most optimization problems small groups of scalars occur together. For example the three components of a translation vector and the four components of the quaternion that define the pose of a camera. We refer to such a group of small scalars as a Parameter Block. Of course a parameter block can just have a single parameter.
-The term $ \rho_i\left(\left\|f_i\left(x_{i_1},\hdots,x_{i_k}\right)\right\|^2\right)$ is known as a Residual Block. A Ceres problem is a collection of residual blocks, each of which depends on a subset of the parameter blocks.
Solving problems using Ceres consists of two steps.
-\begin{enumerate}
-\item{Modeling} Define parameter blocks and residual blocks and build a \texttt{Problem} object containing them.
-\item{Solving} Configure and run the solver.
-\end{enumerate}
+\begin{description}
+\item{\textbf{Modeling}} Constructing an optimization problem by
+ specifying its parameters and the terms in the objective function.
+\item{\textbf{Solving}} Configuring and running the solver.
+\end{description}
-These two steps are mostly independent of each other. This is by design. Modeling the optimization problem should not depend on how the solver and the user should be able to switch between various solver settings and strategies without changing the way the problem is modeled. In the next two chapters we will consider each of these steps in detail.
\ No newline at end of file
+The two steps are mostly independent of each other. This is by
+design. Modeling the optimization problem should not depend on how the
+solver works. The user should be able model the problem once, and then
+switch between various solver settings and strategies without touching
+the problem.
+
+In the next two chapters we will consider each of these steps in detail.
diff --git a/examples/quadratic_auto_diff.cc b/examples/quadratic_auto_diff.cc
index ea7fae9..1e2f3ef 100644
--- a/examples/quadratic_auto_diff.cc
+++ b/examples/quadratic_auto_diff.cc
@@ -44,10 +44,11 @@
using ceres::Solver;
using ceres::Solve;
-// A templated cost function that implements the residual r = 10 - x. The method
-// Map is templated so that we can then use an automatic differentiation wrapper
-// around it to generate its derivatives.
-class QuadraticCostFunction {
+// A templated cost functor that implements the residual r = 10 -
+// x. The method operator() is templated so that we can then use an
+// automatic differentiation wrapper around it to generate its
+// derivatives.
+class QuadraticCostFunctor {
public:
template <typename T> bool operator()(const T* const x, T* residual) const {
residual[0] = T(10.0) - x[0];
@@ -69,8 +70,8 @@
// Set up the only cost function (also known as residual). This uses
// auto-differentiation to obtain the derivative (jacobian).
problem.AddResidualBlock(
- new AutoDiffCostFunction<QuadraticCostFunction, 1, 1>(
- new QuadraticCostFunction),
+ new AutoDiffCostFunction<QuadraticCostFunctor, 1, 1>(
+ new QuadraticCostFunctor),
NULL,
&x);
diff --git a/examples/quadratic_numeric_diff.cc b/examples/quadratic_numeric_diff.cc
index 8ec88ef..1082616 100644
--- a/examples/quadratic_numeric_diff.cc
+++ b/examples/quadratic_numeric_diff.cc
@@ -38,24 +38,16 @@
using ceres::NumericDiffCostFunction;
using ceres::CENTRAL;
-using ceres::SizedCostFunction;
using ceres::CostFunction;
using ceres::Problem;
using ceres::Solver;
using ceres::Solve;
-class ResidualWithNoDerivative
- : public SizedCostFunction<1 /* number of residuals */,
- 1 /* size of first parameter */> {
+// A cost functor that implements the residual r = 10 - x.
+class QuadraticCostFunctor {
public:
- virtual ~ResidualWithNoDerivative() {}
- virtual bool Evaluate(double const* const* parameters,
- double* residuals,
- double** jacobians) const {
- (void) jacobians; // Ignored; filled in by numeric differentiation.
-
- // f(x) = 10 - x.
- residuals[0] = 10 - parameters[0][0];
+ bool operator()(const double* const x, double* residual) const {
+ residual[0] = 10.0 - x[0];
return true;
}
};
@@ -71,8 +63,8 @@
// Set up the only cost function (also known as residual). This uses
// numeric differentiation to obtain the derivative (jacobian).
CostFunction* cost =
- new NumericDiffCostFunction<ResidualWithNoDerivative, CENTRAL, 1, 1> (
- new ResidualWithNoDerivative, ceres::TAKE_OWNERSHIP);
+ new NumericDiffCostFunction<QuadraticCostFunctor, CENTRAL, 1, 1> (
+ new QuadraticCostFunctor);
// Build the problem.
Problem problem;
