Brent 1D minimizer. More...

#include <vnl_brent_minimizer.h>

Inheritance diagram for vnl_brent_minimizer:

Public Types
enum	ReturnCodes { ERROR_FAILURE = -1, ERROR_DODGY_INPUT = 0, CONVERGED_FTOL = 1, CONVERGED_XTOL = 2, CONVERGED_XFTOL = 3, CONVERGED_GTOL = 4, FAILED_TOO_MANY_ITERATIONS = 5, TOO_MANY_ITERATIONS = FAILED_TOO_MANY_ITERATIONS, FAILED_FTOL_TOO_SMALL = 6, FAILED_XTOL_TOO_SMALL = 7, FAILED_GTOL_TOO_SMALL = 8, FAILED_USER_REQUEST = 9 }
	Some generic return codes that apply to all minimizers. More...
Public Member Functions
	vnl_brent_minimizer (vnl_cost_function &functor)
	~vnl_brent_minimizer ()
double	minimize (double ax)
	Find a minimum of f(x) near to ax.
double	f_at_last_minimum () const
	Function evaluation at value returned by minimize(x).
double	minimize_golden (double ax, double bx, double cx, double fa, double fb, double fc)
	Find the minimum x of f(x) within a<= x <= c using pure golden section.
double	minimize_given_bounds (double ax, double bx, double cx)
	Find the minimum value of f(x) within a<= x <= c.
double	minimize_given_bounds_and_one_f (double ax, double bx, double cx, double fb)
	Find the minimum value of f(x) within a<= x <= c.
double	minimize_given_bounds_and_all_f (double ax, double bx, double cx, double fa, double fb, double fc)
	Find the minimum value of f(x) within a<= x <= c.
void	set_f_tolerance (double v)
	Set the convergence tolerance on F (sum of squared residuals).
double	get_f_tolerance () const
void	set_x_tolerance (double v)
	Set the convergence tolerance on X.
double	get_x_tolerance () const
void	set_g_tolerance (double v)
	Set the convergence tolerance on Grad(F)' * F.
double	get_g_tolerance () const
void	set_max_function_evals (int v)
	Set the termination maximum number of iterations.
int	get_max_function_evals () const
void	set_epsilon_function (double v)
	Set the step length for FD Jacobian.
double	get_epsilon_function () const
void	set_trace (bool on)
	Turn on per-iteration printouts.
bool	get_trace () const
void	set_verbose (bool verb)
	Set verbose flag.
bool	get_verbose () const
void	set_check_derivatives (int cd)
	Set check_derivatives flag. Negative values may mean fewer checks.
int	get_check_derivatives () const
double	get_start_error () const
	Return the error of the function when it was evaluated at the start point of the last minimization.
double	get_end_error () const
	Return the best error that was achieved by the last minimization, corresponding to the returned x.
int	get_num_evaluations () const
	Return the total number of times the function was evaluated by the last minimization.
int	get_num_iterations () const
	Return the number of {iterations} in the last minimization.
bool	obj_value_reduced ()
	Whether the error reduced in the last minimization.
virtual vnl_matrix< double > const &	get_covariance ()
	Return the covariance of the estimate at the end.
virtual vcl_string	is_a () const
	Return the name of the class.
virtual bool	is_class (vcl_string const &s) const
	Return true if the name of the class matches the argument.
ReturnCodes	get_failure_code () const
	Return the failure code of the last minimization.
Protected Member Functions
void	reset ()
void	report_eval (double f)
	Called by derived classes after each function evaluation.
virtual bool	report_iter ()
	Called by derived classes after each iteration.
Protected Attributes
vnl_cost_function *	f_
double	f_at_last_minimum_
	Function evaluation at value returned by minimize(x).
double	xtol
	Termination tolerance on X (solution vector)
long	maxfev
	Termination maximum number of iterations.
double	ftol
	Termination tolerance on F (sum of squared residuals)
double	gtol
	Termination tolerance on Grad(F)' * F = 0.
double	epsfcn
	Step length for FD Jacobian.
unsigned	num_iterations_
long	num_evaluations_
double	start_error_
double	end_error_
bool	trace
bool	verbose_
int	check_derivatives_
ReturnCodes	failure_code_

Detailed Description

Brent 1D minimizer.

Minimizes a 1D function using a cunning combination of golden section and parabolic interpolation. It does not require derivatives to be supplied. It is guaranteed to find a minimum, and generally works efficiently - ie using few function evaluations.

This implementation is based on that described by R.P. Brent in Chapter 5 of "Algorithms for Minimization Without Derivatives", 1973. In particular, is a C++ translation of the ALGOL program given at the end of that chapter.

Example usage:

   // Create 1D cost function
   class my_cost_fn : public vnl_cost_function {
     my_cost_fn() : vnl_cost_function(1) {}
  
     double f(const vnl_vector<double>& x)
     { return (2 - x[0]) * (2 - x[0]) + 10; }
   };
  
     my_cost_fn f1;
     vnl_brent_minimizer brent(f1);
  
     double initial_x = 3.5;
    // Find the position of the minimum
     double x = brent.minimize(initial_x);
     double min_f = brent.f_at_last_minimum();

Definition at line 50 of file vnl_brent_minimizer.h.

Member Enumeration Documentation

enum vnl_nonlinear_minimizer::ReturnCodes [inherited]

Some generic return codes that apply to all minimizers.

Enumerator:

ERROR_FAILURE
ERROR_DODGY_INPUT
CONVERGED_FTOL
CONVERGED_XTOL
CONVERGED_XFTOL
CONVERGED_GTOL
FAILED_TOO_MANY_ITERATIONS
TOO_MANY_ITERATIONS
FAILED_FTOL_TOO_SMALL
FAILED_XTOL_TOO_SMALL
FAILED_GTOL_TOO_SMALL
FAILED_USER_REQUEST

Definition at line 102 of file vnl_nonlinear_minimizer.h.

Constructor & Destructor Documentation

vnl_brent_minimizer::vnl_brent_minimizer ( vnl_cost_function & functor )

Definition at line 33 of file vnl_brent_minimizer.cxx.

vnl_brent_minimizer::~vnl_brent_minimizer ( )

Definition at line 39 of file vnl_brent_minimizer.cxx.

Member Function Documentation

double vnl_brent_minimizer::f_at_last_minimum ( ) const [inline]

Function evaluation at value returned by minimize(x).

Definition at line 66 of file vnl_brent_minimizer.h.

int vnl_nonlinear_minimizer::get_check_derivatives ( ) const [inline, inherited]

Definition at line 82 of file vnl_nonlinear_minimizer.h.

vnl_matrix< double > const & vnl_nonlinear_minimizer::get_covariance ( ) [virtual, inherited]

Return the covariance of the estimate at the end.

Definition at line 35 of file vnl_nonlinear_minimizer.cxx.

double vnl_nonlinear_minimizer::get_end_error ( ) const [inline, inherited]

Return the best error that was achieved by the last minimization, corresponding to the returned x.

Definition at line 92 of file vnl_nonlinear_minimizer.h.

double vnl_nonlinear_minimizer::get_epsilon_function ( ) const [inline, inherited]

Definition at line 70 of file vnl_nonlinear_minimizer.h.

double vnl_nonlinear_minimizer::get_f_tolerance ( ) const [inline, inherited]

Definition at line 46 of file vnl_nonlinear_minimizer.h.

ReturnCodes vnl_nonlinear_minimizer::get_failure_code ( ) const [inline, inherited]

Return the failure code of the last minimization.

Definition at line 132 of file vnl_nonlinear_minimizer.h.

double vnl_nonlinear_minimizer::get_g_tolerance ( ) const [inline, inherited]

Definition at line 60 of file vnl_nonlinear_minimizer.h.

int vnl_nonlinear_minimizer::get_max_function_evals ( ) const [inline, inherited]

Definition at line 64 of file vnl_nonlinear_minimizer.h.

int vnl_nonlinear_minimizer::get_num_evaluations ( ) const [inline, inherited]

Return the total number of times the function was evaluated by the last minimization.

Definition at line 95 of file vnl_nonlinear_minimizer.h.

int vnl_nonlinear_minimizer::get_num_iterations ( ) const [inline, inherited]

Return the number of {iterations} in the last minimization.

Each iteration may have comprised several function evaluations.

Definition at line 99 of file vnl_nonlinear_minimizer.h.

double vnl_nonlinear_minimizer::get_start_error ( ) const [inline, inherited]

Return the error of the function when it was evaluated at the start point of the last minimization.

For minimizers driven by a vnl_least_squares_function (Levenberg-Marquardt) this is usually the RMS error. For those driven by a vnl_cost_function (CG, LBFGS, Amoeba) it is simply the value of the vnl_cost_function at the start (usually the sum of squared residuals).

Definition at line 89 of file vnl_nonlinear_minimizer.h.

bool vnl_nonlinear_minimizer::get_trace ( ) const [inline, inherited]

Definition at line 74 of file vnl_nonlinear_minimizer.h.

bool vnl_nonlinear_minimizer::get_verbose ( ) const [inline, inherited]

Definition at line 78 of file vnl_nonlinear_minimizer.h.

double vnl_nonlinear_minimizer::get_x_tolerance ( ) const [inline, inherited]

Definition at line 56 of file vnl_nonlinear_minimizer.h.

vcl_string vnl_nonlinear_minimizer::is_a ( ) const [virtual, inherited]

Return the name of the class.

Used by polymorphic IO

Definition at line 75 of file vnl_nonlinear_minimizer.cxx.

bool vnl_nonlinear_minimizer::is_class ( vcl_string const & s ) const [virtual, inherited]

Return true if the name of the class matches the argument.

Used by polymorphic IO

Definition at line 83 of file vnl_nonlinear_minimizer.cxx.

double vnl_brent_minimizer::minimize ( double ax )

Find a minimum of f(x) near to ax.

The evaluation of f(x) at the returned value can be obtained by a call to f_at_last_minimum();

Reimplemented in vnl_brent.

Definition at line 359 of file vnl_brent_minimizer.cxx.

double vnl_brent_minimizer::minimize_given_bounds	(	double	ax,
		double	bx,
		double	cx
	)

Find the minimum value of f(x) within a<= x <= c.

Return values:

The	position,x, of the minimum x. You need to provide a bracket for the minimum (a<b<c s.t. f(a)>f(b)<f(c). The tolerance can be set using prior call to set_x_tolerance(tol). Use f_at_last_minimum() to get function evaluation at the returned minima.

The minimum x is the return value. You need to provide a bracket for the minimum (a<b<c s.t. f(a)>f(b)<f(c). The tolerance can be set using prior call to set_x_tolerance(tol). Use f_at_last_minimum() to get function evaluation at the returned minima.

Definition at line 131 of file vnl_brent_minimizer.cxx.

double vnl_brent_minimizer::minimize_given_bounds_and_all_f	(	double	ax,
		double	bx,
		double	cx,
		double	fa,
		double	fb,
		double	fc
	)

Find the minimum value of f(x) within a<= x <= c.

Return values:

The	position,x, of the minimum x. You need to provide a bracket for the minimum (a<b<c s.t. f(a)>f(b)<f(c)), and the values fa=f(a), fb=f(b), fc=f(c). This avoids recalculating them if you have them already. If you don't have them, it is probably better to use minimize_given_bounds(a,b,c).

The tolerance can be set using prior call to set_x_tolerance(tol). Use f_at_last_minimum() to get function evaluation at the returned minima.

The minimum x is the return value. You need to provide a bracket for the minimum (a<b<c s.t. f(a)>f(b)<f(c)), and the values fa=f(a), fb=f(b), fc=f(c). This avoids recalculating them if you have them already. The tolerance can be set using prior call to set_x_tolerance(tol). Use f_at_last_minimum() to get function evaluation at the returned minima.

Definition at line 255 of file vnl_brent_minimizer.cxx.

double vnl_brent_minimizer::minimize_given_bounds_and_one_f	(	double	ax,
		double	bx,
		double	cx,
		double	fb
	)

Find the minimum value of f(x) within a<= x <= c.

Return values:

The	position,x, of the minimum x. You need to provide a bracket for the minimum (a<b<c s.t. f(a)>f(b)<f(c), and the known value at b (fb=f(b)). The tolerance can be set using prior call to set_x_tolerance(tol). Use f_at_last_minimum() to get function evaluation at the returned minima.

The minimum x is the return value. You need to provide a bracket for the minimum (a<b<c s.t. f(a)>f(b)<f(c), and the known value at b (fb=f(b)). The tolerance can be set using prior call to set_x_tolerance(tol). Use f_at_last_minimum() to get function evaluation at the returned minima.

Definition at line 145 of file vnl_brent_minimizer.cxx.

double vnl_brent_minimizer::minimize_golden	(	double	a,
		double	b,
		double	c,
		double	fa,
		double	fb,
		double	fc
	)

Find the minimum x of f(x) within a<= x <= c using pure golden section.

Return values:

The	position,x, of the minimum x. You need to provide a bracket for the minimum (a<b<c s.t. f(a)>f(b)<f(c). The tolerance can be set using prior call to set_x_tolerance(tol). Use f_at_last_minimum() to get function evaluation at the returned minima.

The minimum x is the return value. You need to provide a bracket for the minimum (a<b<c s.t. f(a)>f(b)<f(c). The tolerance can be set using prior call to set_x_tolerance(tol). Use f_at_last_minimum() to get function evaluation at the returned minima.

Definition at line 48 of file vnl_brent_minimizer.cxx.

bool vnl_nonlinear_minimizer::obj_value_reduced ( ) [inline, inherited]

Whether the error reduced in the last minimization.

Definition at line 118 of file vnl_nonlinear_minimizer.h.

void vnl_nonlinear_minimizer::report_eval ( double f ) [protected, inherited]

Called by derived classes after each function evaluation.

Definition at line 50 of file vnl_nonlinear_minimizer.cxx.

bool vnl_nonlinear_minimizer::report_iter ( ) [protected, virtual, inherited]

Called by derived classes after each iteration.

When true is returned, minimizer should stop with code FAILED_USER_REQUEST. Derived classes can redefine this function to make the optimizer stop when a condition is satisfied.

Definition at line 63 of file vnl_nonlinear_minimizer.cxx.

void vnl_nonlinear_minimizer::reset ( ) [protected, inherited]

Definition at line 41 of file vnl_nonlinear_minimizer.cxx.

void vnl_nonlinear_minimizer::set_check_derivatives ( int cd ) [inline, inherited]

Set check_derivatives flag. Negative values may mean fewer checks.

Definition at line 81 of file vnl_nonlinear_minimizer.h.

void vnl_nonlinear_minimizer::set_epsilon_function ( double v ) [inline, inherited]

Set the step length for FD Jacobian.

Be aware that set_x_tolerance will reset this to xtol * 0.001. The default is 1e-11.

Definition at line 69 of file vnl_nonlinear_minimizer.h.

void vnl_nonlinear_minimizer::set_f_tolerance ( double v ) [inline, inherited]

Set the convergence tolerance on F (sum of squared residuals).

When the differences in successive RMS errors is less than this, the routine terminates. So this is effectively the desired precision of your minimization. Setting it too low wastes time, too high might cause early convergence. The default of 1e-9 is on the safe side, but if speed is an issue, you can try raising it.

Definition at line 45 of file vnl_nonlinear_minimizer.h.

void vnl_nonlinear_minimizer::set_g_tolerance ( double v ) [inline, inherited]

Set the convergence tolerance on Grad(F)' * F.

Definition at line 59 of file vnl_nonlinear_minimizer.h.

void vnl_nonlinear_minimizer::set_max_function_evals ( int v ) [inline, inherited]

Set the termination maximum number of iterations.

Definition at line 63 of file vnl_nonlinear_minimizer.h.

void vnl_nonlinear_minimizer::set_trace ( bool on ) [inline, inherited]

Turn on per-iteration printouts.

Definition at line 73 of file vnl_nonlinear_minimizer.h.

void vnl_nonlinear_minimizer::set_verbose ( bool verb ) [inline, inherited]

Set verbose flag.

Definition at line 77 of file vnl_nonlinear_minimizer.h.

void vnl_nonlinear_minimizer::set_x_tolerance ( double v ) [inline, inherited]

Set the convergence tolerance on X.

When the length of the steps taken in X are about this long, the routine terminates. The default is 1e-8, which should work for many problems, but if you can get away with 1e-4, say, minimizations will be much quicker.

Definition at line 52 of file vnl_nonlinear_minimizer.h.