Calculates the minimum of a multidimensional real function using the steepest descent method.
Controller:
Interface
#include <codecogs/maths/optimization/gradient.h>
using namespace Maths::Optimization;
std::vector<double> | gradient (double (*f)(const std::vector<double> &), std::vector<double> x, double xk = 1, double eps = 1E-10, int maxit = 1000)
Calculates the minimum of a multidimensional real function using the steepest descent method. |
Use the following HTML code to embed the calculators within other websites:
Gradient
This routine finds the local extrema of a multidimensional user-defined function
f using
the steepest descent or gradient method. An initial guess is required in the form of a multidimensional
point, coded as an array of coordinates
x. The algorithm executes until either the desired
accuracy <em> eps </em> is achieved or the maximum number of iterations <em> maxit </em> is
exceeded.
The gradient method performs the minimization of a function
of
n variables
whose partial derivatives are accessible.
Let us now define the gradient of a function, let
be a function
of
such that
exists for
. The gradient of
, denoted by
, is
the vector
Recall that the gradient vector in the above equation points locally in the direction of the greatest
rate of increase of
. Hence
points locally in the direction
of greatest decrease
. Start at the point
and search along the line
through
in the direction
.
You will arrive at a point
, where a local minimum occurs when the point
is constrained to lie on the line
. Since partial derivatives
are accessible, the minimization process can be executed using either the quadratic or cubic approximation method.
Next we compute
and move in the search direction
. You will come to
, where a local minimum occurs when
is constrained to lie on the line
. Iteration will produce a sequence,
, of points with the property
If
then
will be a local minimum of
.
The outline of the steepest descent or gradient method is described below (suppose that
has been obtained).
1) Evaluate the gradient vector
2) Compute the search direction
3) Perform a single parameter minimization of
on the interval
, where
b is large. This will produce a value
where a local minimum is found for
. The relation
shows that this is a minimum for
along the search line
.
4) Construct the next point
.
5) Perform the termination test for minimization, i.e. are the function values
and
sufficiently close and the distance
small enough ?
6) Repeat the process from step 1.
References:
Example 1
#include <codecogs/maths/optimization/gradient.h>
#include <iostream>
#include <iomanip>
#include <cmath>
double f(const std::vector<double> &x) {
return sin(x[0]) + 2 * cos(x[1]) - sin(x[2]);
}
int main() {
// initial point
double x[3] = { 1, 1, 1 };
std::vector<double> v(x, x + 3), result = Maths::Optimization::gradient(f, v);
std::cout << "The results are: " << std::endl << std::endl;
for (int i = 0; i < result.size(); i++) {
std::cout << " x(" << i << ") = ";
std::cout << std::setprecision(10) << result[i] << std::endl;
}
std::cout << std::endl << "Local maximum found = " << f(result) << std::endl;
return 0;
}
Output
The results are:
x(0) = 1.570795457
x(1) = 6.423712373e-006
x(2) = 4.712391906
Local maximum found = 4
Parameters
f | the user-defined multidimensional function |
x | the initial multidimensional point coded as a C++ vector object |
xk | Default value = 1 |
eps | Default value = 1E-10 |
maxit | Default value = 1000 |
Returns
- The approximated multidimensional point coresponding to the minimum of the function.
Authors
- Lucian Bentea (August 2005)
Source Code
This module is private, for owner's use only.
Not a member, then Register with CodeCogs. Already a Member, then Login.