<!DOCTYPE html>
<!--[if IE 8]><html class="no-js lt-ie9" lang="en" > <![endif]-->
<!--[if gt IE 8]><!--> <html class="no-js" lang="en" > <!--<![endif]-->
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>General Unconstrained Minimization — Ceres Solver</title>
<link rel="stylesheet" href="_static/css/theme.css" type="text/css" />
<link rel="top" title="Ceres Solver" href="index.html"/>
<link rel="up" title="Tutorial" href="tutorial.html"/>
<link rel="next" title="On Derivatives" href="derivatives.html"/>
<link rel="prev" title="Non-linear Least Squares" href="nnls_tutorial.html"/>
<script src="_static/js/modernizr.min.js"></script>
</head>
<body class="wy-body-for-nav" role="document">
<div class="wy-grid-for-nav">
<nav data-toggle="wy-nav-shift" class="wy-nav-side">
<div class="wy-side-scroll">
<div class="wy-side-nav-search">
<a href="index.html" class="icon icon-home"> Ceres Solver
</a>
<div class="version">
1.13
</div>
<div role="search">
<form id="rtd-search-form" class="wy-form" action="search.html" method="get">
<input type="text" name="q" placeholder="Search docs" />
<input type="hidden" name="check_keywords" value="yes" />
<input type="hidden" name="area" value="default" />
</form>
</div>
</div>
<div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="main navigation">
<ul class="current">
<li class="toctree-l1"><a class="reference internal" href="features.html">Why?</a></li>
<li class="toctree-l1"><a class="reference internal" href="installation.html">Installation</a></li>
<li class="toctree-l1 current"><a class="reference internal" href="tutorial.html">Tutorial</a><ul class="current">
<li class="toctree-l2"><a class="reference internal" href="nnls_tutorial.html">Non-linear Least Squares</a></li>
<li class="toctree-l2 current"><a class="current reference internal" href="#">General Unconstrained Minimization</a><ul>
<li class="toctree-l3"><a class="reference internal" href="#rosenbrock-s-function">Rosenbrock’s Function</a></li>
</ul>
</li>
</ul>
</li>
<li class="toctree-l1"><a class="reference internal" href="derivatives.html">On Derivatives</a></li>
<li class="toctree-l1"><a class="reference internal" href="nnls_modeling.html">Modeling Non-linear Least Squares</a></li>
<li class="toctree-l1"><a class="reference internal" href="nnls_solving.html">Solving Non-linear Least Squares</a></li>
<li class="toctree-l1"><a class="reference internal" href="nnls_covariance.html">Covariance Estimation</a></li>
<li class="toctree-l1"><a class="reference internal" href="gradient_solver.html">General Unconstrained Minimization</a></li>
<li class="toctree-l1"><a class="reference internal" href="faqs.html">FAQS, Tips & Tricks</a></li>
<li class="toctree-l1"><a class="reference internal" href="users.html">Users</a></li>
<li class="toctree-l1"><a class="reference internal" href="contributing.html">Contributing</a></li>
<li class="toctree-l1"><a class="reference internal" href="version_history.html">Version History</a></li>
<li class="toctree-l1"><a class="reference internal" href="bibliography.html">Bibliography</a></li>
<li class="toctree-l1"><a class="reference internal" href="license.html">License</a></li>
</ul>
</div>
</div>
</nav>
<section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">
<nav class="wy-nav-top" role="navigation" aria-label="top navigation">
<i data-toggle="wy-nav-top" class="fa fa-bars"></i>
<a href="index.html">Ceres Solver</a>
</nav>
<div class="wy-nav-content">
<div class="rst-content">
<div role="navigation" aria-label="breadcrumbs navigation">
<ul class="wy-breadcrumbs">
<li><a href="index.html">Docs</a> »</li>
<li><a href="tutorial.html">Tutorial</a> »</li>
<li>General Unconstrained Minimization</li>
<li class="wy-breadcrumbs-aside">
</li>
</ul>
<hr/>
</div>
<div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
<div itemprop="articleBody">
<div class="section" id="general-unconstrained-minimization">
<span id="chapter-gradient-tutorial"></span><h1>General Unconstrained Minimization<a class="headerlink" href="#general-unconstrained-minimization" title="Permalink to this headline">¶</a></h1>
<p>While much of Ceres Solver is devoted to solving non-linear least
squares problems, internally it contains a solver that can solve
general unconstrained optimization problems using just their objective
function value and gradients. The <code class="docutils literal"><span class="pre">GradientProblem</span></code> and
<code class="docutils literal"><span class="pre">GradientProblemSolver</span></code> objects give the user access to this solver.</p>
<p>So without much further ado, let us look at how one goes about using
them.</p>
<div class="section" id="rosenbrock-s-function">
<h2>Rosenbrock’s Function<a class="headerlink" href="#rosenbrock-s-function" title="Permalink to this headline">¶</a></h2>
<p>We consider the minimization of the famous <a class="reference external" href="http://en.wikipedia.org/wiki/Rosenbrock_function">Rosenbrock’s function</a> <a class="footnote-reference" href="#f1" id="id2">[1]</a>.</p>
<p>We begin by defining an instance of the <code class="docutils literal"><span class="pre">FirstOrderFunction</span></code>
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 <code class="xref cpp cpp-class docutils literal"><span class="pre">CostFunction</span></code> when defining non-linear least
squares problems in Ceres.</p>
<div class="code highlight-c++"><div class="highlight"><pre><span></span><span class="k">class</span> <span class="nc">Rosenbrock</span> <span class="o">:</span> <span class="k">public</span> <span class="n">ceres</span><span class="o">::</span><span class="n">FirstOrderFunction</span> <span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
<span class="k">virtual</span> <span class="kt">bool</span> <span class="n">Evaluate</span><span class="p">(</span><span class="k">const</span> <span class="kt">double</span><span class="o">*</span> <span class="n">parameters</span><span class="p">,</span>
<span class="kt">double</span><span class="o">*</span> <span class="n">cost</span><span class="p">,</span>
<span class="kt">double</span><span class="o">*</span> <span class="n">gradient</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span>
<span class="k">const</span> <span class="kt">double</span> <span class="n">x</span> <span class="o">=</span> <span class="n">parameters</span><span class="p">[</span><span class="mi">0</span><span class="p">];</span>
<span class="k">const</span> <span class="kt">double</span> <span class="n">y</span> <span class="o">=</span> <span class="n">parameters</span><span class="p">[</span><span class="mi">1</span><span class="p">];</span>
<span class="n">cost</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="p">(</span><span class="mf">1.0</span> <span class="o">-</span> <span class="n">x</span><span class="p">)</span> <span class="o">*</span> <span class="p">(</span><span class="mf">1.0</span> <span class="o">-</span> <span class="n">x</span><span class="p">)</span> <span class="o">+</span> <span class="mf">100.0</span> <span class="o">*</span> <span class="p">(</span><span class="n">y</span> <span class="o">-</span> <span class="n">x</span> <span class="o">*</span> <span class="n">x</span><span class="p">)</span> <span class="o">*</span> <span class="p">(</span><span class="n">y</span> <span class="o">-</span> <span class="n">x</span> <span class="o">*</span> <span class="n">x</span><span class="p">);</span>
<span class="k">if</span> <span class="p">(</span><span class="n">gradient</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">)</span> <span class="p">{</span>
<span class="n">gradient</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="o">-</span><span class="mf">2.0</span> <span class="o">*</span> <span class="p">(</span><span class="mf">1.0</span> <span class="o">-</span> <span class="n">x</span><span class="p">)</span> <span class="o">-</span> <span class="mf">200.0</span> <span class="o">*</span> <span class="p">(</span><span class="n">y</span> <span class="o">-</span> <span class="n">x</span> <span class="o">*</span> <span class="n">x</span><span class="p">)</span> <span class="o">*</span> <span class="mf">2.0</span> <span class="o">*</span> <span class="n">x</span><span class="p">;</span>
<span class="n">gradient</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="mf">200.0</span> <span class="o">*</span> <span class="p">(</span><span class="n">y</span> <span class="o">-</span> <span class="n">x</span> <span class="o">*</span> <span class="n">x</span><span class="p">);</span>
<span class="p">}</span>
<span class="k">return</span> <span class="nb">true</span><span class="p">;</span>
<span class="p">}</span>
<span class="k">virtual</span> <span class="kt">int</span> <span class="n">NumParameters</span><span class="p">()</span> <span class="k">const</span> <span class="p">{</span> <span class="k">return</span> <span class="mi">2</span><span class="p">;</span> <span class="p">}</span>
<span class="p">};</span>
</pre></div>
</div>
<p>Minimizing it then is a straightforward matter of constructing a
<a class="reference internal" href="gradient_solver.html#_CPPv215GradientProblem" title="GradientProblem"><code class="xref cpp cpp-class docutils literal"><span class="pre">GradientProblem</span></code></a> object and calling <a class="reference internal" href="gradient_solver.html#_CPPv25SolveRKN21GradientProblemSolver7OptionsERK15GradientProblemPdPN21GradientProblemSolver7SummaryE" title="Solve"><code class="xref cpp cpp-func docutils literal"><span class="pre">Solve()</span></code></a> on it.</p>
<div class="code highlight-c++"><div class="highlight"><pre><span></span><span class="kt">double</span> <span class="n">parameters</span><span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="o">=</span> <span class="p">{</span><span class="o">-</span><span class="mf">1.2</span><span class="p">,</span> <span class="mf">1.0</span><span class="p">};</span>
<span class="n">ceres</span><span class="o">::</span><span class="n">GradientProblem</span> <span class="n">problem</span><span class="p">(</span><span class="k">new</span> <span class="n">Rosenbrock</span><span class="p">());</span>
<span class="n">ceres</span><span class="o">::</span><span class="n">GradientProblemSolver</span><span class="o">::</span><span class="n">Options</span> <span class="n">options</span><span class="p">;</span>
<span class="n">options</span><span class="p">.</span><span class="n">minimizer_progress_to_stdout</span> <span class="o">=</span> <span class="nb">true</span><span class="p">;</span>
<span class="n">ceres</span><span class="o">::</span><span class="n">GradientProblemSolver</span><span class="o">::</span><span class="n">Summary</span> <span class="n">summary</span><span class="p">;</span>
<span class="n">ceres</span><span class="o">::</span><span class="n">Solve</span><span class="p">(</span><span class="n">options</span><span class="p">,</span> <span class="n">problem</span><span class="p">,</span> <span class="n">parameters</span><span class="p">,</span> <span class="o">&</span><span class="n">summary</span><span class="p">);</span>
<span class="n">std</span><span class="o">::</span><span class="n">cout</span> <span class="o"><<</span> <span class="n">summary</span><span class="p">.</span><span class="n">FullReport</span><span class="p">()</span> <span class="o"><<</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span>
</pre></div>
</div>
<p>Executing this code results, solve the problem using limited memory
<a class="reference external" href="http://en.wikipedia.org/wiki/Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm">BFGS</a>
algorithm.</p>
<div class="highlight-bash"><div class="highlight"><pre><span></span> 0: f: 2.420000e+01 d: 0.00e+00 g: 2.16e+02 h: 0.00e+00 s: 0.00e+00 e: <span class="m">0</span> it: 2.00e-05 tt: 2.00e-05
1: f: 4.280493e+00 d: 1.99e+01 g: 1.52e+01 h: 2.01e-01 s: 8.62e-04 e: <span class="m">2</span> it: 7.32e-05 tt: 2.19e-04
2: f: 3.571154e+00 d: 7.09e-01 g: 1.35e+01 h: 3.78e-01 s: 1.34e-01 e: <span class="m">3</span> it: 2.50e-05 tt: 2.68e-04
3: f: 3.440869e+00 d: 1.30e-01 g: 1.73e+01 h: 1.36e-01 s: 1.00e+00 e: <span class="m">1</span> it: 4.05e-06 tt: 2.92e-04
4: f: 3.213597e+00 d: 2.27e-01 g: 1.55e+01 h: 1.06e-01 s: 4.59e-01 e: <span class="m">1</span> it: 2.86e-06 tt: 3.14e-04
5: f: 2.839723e+00 d: 3.74e-01 g: 1.05e+01 h: 1.34e-01 s: 5.24e-01 e: <span class="m">1</span> it: 2.86e-06 tt: 3.36e-04
6: f: 2.448490e+00 d: 3.91e-01 g: 1.29e+01 h: 3.04e-01 s: 1.00e+00 e: <span class="m">1</span> it: 4.05e-06 tt: 3.58e-04
7: f: 1.943019e+00 d: 5.05e-01 g: 4.00e+00 h: 8.81e-02 s: 7.43e-01 e: <span class="m">1</span> it: 4.05e-06 tt: 3.79e-04
8: f: 1.731469e+00 d: 2.12e-01 g: 7.36e+00 h: 1.71e-01 s: 4.60e-01 e: <span class="m">2</span> it: 9.06e-06 tt: 4.06e-04
9: f: 1.503267e+00 d: 2.28e-01 g: 6.47e+00 h: 8.66e-02 s: 1.00e+00 e: <span class="m">1</span> it: 3.81e-06 tt: 4.33e-04
10: f: 1.228331e+00 d: 2.75e-01 g: 2.00e+00 h: 7.70e-02 s: 7.90e-01 e: <span class="m">1</span> it: 3.81e-06 tt: 4.54e-04
11: f: 1.016523e+00 d: 2.12e-01 g: 5.15e+00 h: 1.39e-01 s: 3.76e-01 e: <span class="m">2</span> it: 1.00e-05 tt: 4.82e-04
12: f: 9.145773e-01 d: 1.02e-01 g: 6.74e+00 h: 7.98e-02 s: 1.00e+00 e: <span class="m">1</span> it: 3.10e-06 tt: 5.03e-04
13: f: 7.508302e-01 d: 1.64e-01 g: 3.88e+00 h: 5.76e-02 s: 4.93e-01 e: <span class="m">1</span> it: 2.86e-06 tt: 5.25e-04
14: f: 5.832378e-01 d: 1.68e-01 g: 5.56e+00 h: 1.42e-01 s: 1.00e+00 e: <span class="m">1</span> it: 3.81e-06 tt: 5.47e-04
15: f: 3.969581e-01 d: 1.86e-01 g: 1.64e+00 h: 1.17e-01 s: 1.00e+00 e: <span class="m">1</span> it: 4.05e-06 tt: 5.68e-04
16: f: 3.171557e-01 d: 7.98e-02 g: 3.84e+00 h: 1.18e-01 s: 3.97e-01 e: <span class="m">2</span> it: 9.06e-06 tt: 5.94e-04
17: f: 2.641257e-01 d: 5.30e-02 g: 3.27e+00 h: 6.14e-02 s: 1.00e+00 e: <span class="m">1</span> it: 3.10e-06 tt: 6.16e-04
18: f: 1.909730e-01 d: 7.32e-02 g: 5.29e-01 h: 8.55e-02 s: 6.82e-01 e: <span class="m">1</span> it: 4.05e-06 tt: 6.42e-04
19: f: 1.472012e-01 d: 4.38e-02 g: 3.11e+00 h: 1.20e-01 s: 3.47e-01 e: <span class="m">2</span> it: 1.00e-05 tt: 6.69e-04
20: f: 1.093558e-01 d: 3.78e-02 g: 2.97e+00 h: 8.43e-02 s: 1.00e+00 e: <span class="m">1</span> it: 3.81e-06 tt: 6.91e-04
21: f: 6.710346e-02 d: 4.23e-02 g: 1.42e+00 h: 9.64e-02 s: 8.85e-01 e: <span class="m">1</span> it: 3.81e-06 tt: 7.12e-04
22: f: 3.993377e-02 d: 2.72e-02 g: 2.30e+00 h: 1.29e-01 s: 4.63e-01 e: <span class="m">2</span> it: 9.06e-06 tt: 7.39e-04
23: f: 2.911794e-02 d: 1.08e-02 g: 2.55e+00 h: 6.55e-02 s: 1.00e+00 e: <span class="m">1</span> it: 4.05e-06 tt: 7.62e-04
24: f: 1.457683e-02 d: 1.45e-02 g: 2.77e-01 h: 6.37e-02 s: 6.14e-01 e: <span class="m">1</span> it: 3.81e-06 tt: 7.84e-04
25: f: 8.577515e-03 d: 6.00e-03 g: 2.86e+00 h: 1.40e-01 s: 1.00e+00 e: <span class="m">1</span> it: 4.05e-06 tt: 8.05e-04
26: f: 3.486574e-03 d: 5.09e-03 g: 1.76e-01 h: 1.23e-02 s: 1.00e+00 e: <span class="m">1</span> it: 4.05e-06 tt: 8.27e-04
27: f: 1.257570e-03 d: 2.23e-03 g: 1.39e-01 h: 5.08e-02 s: 1.00e+00 e: <span class="m">1</span> it: 4.05e-06 tt: 8.48e-04
28: f: 2.783568e-04 d: 9.79e-04 g: 6.20e-01 h: 6.47e-02 s: 1.00e+00 e: <span class="m">1</span> it: 4.05e-06 tt: 8.69e-04
29: f: 2.533399e-05 d: 2.53e-04 g: 1.68e-02 h: 1.98e-03 s: 1.00e+00 e: <span class="m">1</span> it: 3.81e-06 tt: 8.91e-04
30: f: 7.591572e-07 d: 2.46e-05 g: 5.40e-03 h: 9.27e-03 s: 1.00e+00 e: <span class="m">1</span> it: 3.81e-06 tt: 9.12e-04
31: f: 1.902460e-09 d: 7.57e-07 g: 1.62e-03 h: 1.89e-03 s: 1.00e+00 e: <span class="m">1</span> it: 2.86e-06 tt: 9.33e-04
32: f: 1.003030e-12 d: 1.90e-09 g: 3.50e-05 h: 3.52e-05 s: 1.00e+00 e: <span class="m">1</span> it: 3.10e-06 tt: 9.54e-04
33: f: 4.835994e-17 d: 1.00e-12 g: 1.05e-07 h: 1.13e-06 s: 1.00e+00 e: <span class="m">1</span> it: 4.05e-06 tt: 9.81e-04
34: f: 1.885250e-22 d: 4.84e-17 g: 2.69e-10 h: 1.45e-08 s: 1.00e+00 e: <span class="m">1</span> it: 4.05e-06 tt: 1.00e-03
Solver Summary <span class="o">(</span>v 1.12.0-lapack-suitesparse-cxsparse-no_openmp<span class="o">)</span>
Parameters 2
Line search direction LBFGS <span class="o">(</span>20<span class="o">)</span>
Line search <span class="nb">type</span> CUBIC WOLFE
Cost:
Initial 2.420000e+01
Final 1.885250e-22
Change 2.420000e+01
Minimizer iterations 35
Time <span class="o">(</span>in seconds<span class="o">)</span>:
Cost evaluation 0.000
Gradient evaluation 0.000
Total 0.003
Termination: CONVERGENCE <span class="o">(</span>Gradient tolerance reached. Gradient max norm: 9.032775e-13 <<span class="o">=</span> 1.000000e-10<span class="o">)</span>
</pre></div>
</div>
<p class="rubric">Footnotes</p>
<table class="docutils footnote" frame="void" id="f1" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label"><a class="fn-backref" href="#id2">[1]</a></td><td><a class="reference external" href="https://ceres-solver.googlesource.com/ceres-solver/+/master/examples/rosenbrock.cc">examples/rosenbrock.cc</a></td></tr>
</tbody>
</table>
</div>
</div>
</div>
</div>
<footer>
<div class="rst-footer-buttons" role="navigation" aria-label="footer navigation">
<a href="derivatives.html" class="btn btn-neutral float-right" title="On Derivatives" accesskey="n">Next <span class="fa fa-arrow-circle-right"></span></a>
<a href="nnls_tutorial.html" class="btn btn-neutral" title="Non-linear Least Squares" accesskey="p"><span class="fa fa-arrow-circle-left"></span> Previous</a>
</div>
<hr/>
<div role="contentinfo">
<p>
© Copyright 2016 Google Inc.
</p>
</div>
</footer>
</div>
</div>
</section>
</div>
<script type="text/javascript">
var DOCUMENTATION_OPTIONS = {
URL_ROOT:'./',
VERSION:'1.13.0',
COLLAPSE_INDEX:false,
FILE_SUFFIX:'.html',
HAS_SOURCE: true
};
</script>
<script type="text/javascript" src="_static/jquery.js"></script>
<script type="text/javascript" src="_static/underscore.js"></script>
<script type="text/javascript" src="_static/doctools.js"></script>
<script type="text/javascript" src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML">
MathJax.Hub.Config({
"HTML-CSS": {
availableFonts: ["TeX"]
}
});
</script>
<script type="text/javascript" src="_static/js/theme.js"></script>
<script type="text/javascript">
jQuery(function () {
SphinxRtdTheme.StickyNav.enable();
});
</script>
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-49769510-1', 'ceres-solver.org');
ga('send', 'pageview');
</script>
</body>
</html>