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

(1)

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

(2)

If

(3)

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

• Jean-Pierre Moreau's Home Page, http://perso.wanadoo.fr/jean-pierre.moreau
• John H. Mathews, "Numerical analysis and numerical methods", http://math.fullerton.edu/mathews/n2003/GradientSearchMod.html

#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;
}

The results are:
     x(0) = 1.570795457
     x(1) = 6.423712373e-006
     x(2) = 4.712391906

Local maximum found = 4

Parameters

Returns