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 $f(\vec{x})$ of n variables $\vec{x} = (x_1, x_2, \ldots , x_n)$ whose partial derivatives are accessible. Let us now define the gradient of a function, let $z = f(\vec{x})$ be a function of $\vec{x}$ such that $\frac {\partial f(\vec{x})} {\partial x_k}$ exists for $k = 1, 2, \ldots, n$. The gradient of $f(\vec{x})$, denoted by $\nabla f(\vec{x})$, is the vector

Recall that the gradient vector in the above equation points locally in the direction of the greatest rate of increase of $f(\vec{x})$. Hence $- \nabla f(\vec{x})$ points locally in the direction of greatest decrease $f(\vec{x})$. Start at the point $\vec{P_0}$ and search along the line through $\vec{P_0}$ in the direction $\vec{S_0} = - \nabla f(\vec{P_0}) / ||- \nabla f(\vec{P_0}) ||$. You will arrive at a point $\vec{P_1}$, where a local minimum occurs when the point $\vec{x}$ is constrained to lie on the line $\vec{x} = \vec{P_1} + \alpha \vec{S_0}$. Since partial derivatives are accessible, the minimization process can be executed using either the quadratic or cubic approximation method. Next we compute $- \nabla f(\vec{P_1})$ and move in the search direction $\vec{S_1} = - \nabla f(\vec{P_1}) / || - \nabla f(\vec{P_1}) ||$. You will come to $\vec{P_2}$, where a local minimum occurs when $\vec{x}$ is constrained to lie on the line $\vec{x} = \vec{P_1} + \nabla \vec{S_1}$. Iteration will produce a sequence, $\left( \vec{P_k} \right)_{k \geq 0}$, of points with the property

If

then $f(\vec{P})$ will be a local minimum of $f(\vec{x})$.

The outline of the steepest descent or gradient method is described below (suppose that $\vec{P_k}$ has been obtained).

1) Evaluate the gradient vector $\nabla f(\vec{P_k})$

2) Compute the search direction $\vec{S_k} = - \nabla f(\vec{P_k}) / || - \nabla f(\vec{P_k}) ||$

3) Perform a single parameter minimization of $\Phi(\alpha) = f(\vec{P_k} + \alpha \vec{S_k})$ on the interval $[0, b]$, where b is large. This will produce a value $\alpha = h_{min}$ where a local minimum is found for $\Phi(\alpha)$. The relation $\Phi(h_{min}) = f(\vec{P_k} + h_{min} \vec{S_k})$ shows that this is a minimum for $f(\vec{x})$ along the search line $\vec{x} = \vec{P_k} + \alpha \vec{S_k}$.

4) Construct the next point $\vec{P_{k + 1}} = \vec{P_k} + h_{min} \vec{S_k}$.

5) Perform the termination test for minimization, i.e. are the function values $f(\vec{P_k})$ and $f(\vec{P_{k + 1}})$ sufficiently close and the distance $|| \vec{P_{k + 1}} - \vec{P_k} ||$ small enough ?

6) Repeat the process from step 1.

References

• 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 minimum found = " << f(result) << std::endl;
    return 0;
}

The results are:
     x(0) = -1.570796649
     x(1) = -3.141598004
     x(2) = 1.570793644

Local minimum found = -4

Parameters

Returns