cblnsrch.cpp File Reference

Cubic line search algorithm for finding a minimum value of a function. More...

#include <cmath>
#include <climits>
#include <cfloat>
#include <SharkDefs.h>
#include <LinAlg/arrayoptimize.h>

Go to the source code of this file.

Functions

void cblnsrch (Array< double > &xold, double fold, Array< double > &g, Array< double > &p, Array< double > &x, double &f, double(*func)(const Array< double > &), double lambda)
 Does a cubic line search, i.e. given a nonlinear function, a starting point and a direction, a new point is calculated where the function has decreased "sufficiently".

Detailed Description

Cubic line search algorithm for finding a minimum value of a function.

Author:
M. Kreutz
Date:
1995
Copyright (c) 1998-2000:
Institut für Neuroinformatik
Ruhr-Universität Bochum
D-44780 Bochum, Germany
Phone: +49-234-32-25558
Fax: +49-234-32-14209
eMail: Shark-admin@neuroinformatik.ruhr-uni-bochum.de
www: http://www.neuroinformatik.ruhr-uni-bochum.de

Project:
LinAlg



This file is part of LinAlg. This library is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this library; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

Definition in file cblnsrch.cpp.

Function Documentation

void cblnsrch ( Array< double > &  xold,
double  fold,
Array< double > &  g,
Array< double > &  p,
Array< double > &  x,
double &  f,
double(*)(const Array< double > &)  func,
double  lambda 
)

Does a cubic line search, i.e. given a nonlinear function, a starting point and a direction, a new point is calculated where the function has decreased "sufficiently".

Does a cubic line search, i.e.

The line search algorithms are based on the Newton method of approximating root values of monotone decreasing functions. When the derivative $ f' $ of the function $ f $ at a starting point $ x $ on the X-axis can be calculated, the intersection $ x' $ of the tangent at point $ f(x) $ (with gradient $ f'(x) $) with the X-axis can be used to get a better approximation of the minima at $ x_{min} $.

This function is based on this idea: Given a nonlinear function $ f $, a n-dimensional starting point $ x_{old} $ and a direction $ p $ (known as Newton direction), a new point $ x_{new} $ is calculated as

$ x_{new} = x_{old} + \lambda p, \hspace{2em} 0 < \lambda \leq 1 $

in a way that $ f(x_{new})$ has decreased sufficiently. Sufficiently means that

$ f(x_{new}) \leq f(x_{old}) + \alpha \nabla f \cdot (x_{new} - x_{old}) $

where $ 0 < \alpha < 1 $ is a fraction of the initial rate of decrease $ \nabla f \cdot p $.

This function can be used for minimization or solving a set of nonlinear equations of the form $ F(x) = 0 $. Finding the root value (the x-value at which the related function will intersect the X-axis) will then solve the equations. In contrast to line search (lnsrch.cpp) the cubic line search interpolates four points to find the minimum value and is useful, when gradient information is already available or when more than three function evaluations have been calculated.

Parameters:
xold n-dimensional starting point.
fold The value of function func at point xold.
g The n-dimensional gradient of function func at point xold.
p n-dimensional point to specify the search direction (the Newton direction).
x New n-dimensional point along the direction p from xold where the function func decreases "sufficiently".
f The new function value for point x.
func Function to decrease.
lambda Controls the accuracy of line search, $ 0.25 $ is a good choice.
Returns:
none.

Please follow the link to view the source code of the example. The example can be executed in the example directory of package LinAlg.

Author:
M. Kreutz
Date:
1998
Changes
none
Status
stable
See also:
lnsrch.cpp
Examples:
cblnsrch_test.cpp.

Definition at line 163 of file cblnsrch.cpp.