Gradient Descent

GradientDescent is useful to minimize a function. It implements a gradient descent in which the step length is choosen automatically using Armijo’s inequality, that is if \(x_{k+1} = x_k - \alpha \nabla(f)(x_k)\), then \(\alpha\) must verify:

\[f(x_k - \alpha \nabla(f)(x_k)) \leq f(x_k) - c \times \alpha \times \| \nabla(f)(x_k) \| ^2\]

The constant \(c\) is \(10^{-4}\) by default, but it can be ajusted.

Exemple – Minimization of the Rosenbrock function

// Declare a function and its gradient
const int n = 8;

const auto rosenbrock = [](const Vect<double> &x) {
    const double a = 1;
    const double b = 100;

    double sum = 0.;

    for (int i = 0; i < n - 1; i++) {
        const double t = x(i + 1) - x(i)*x(i);
        sum += b * t * t;
        sum += (a - x(i)) * (a - x(i));
    }

    return sum;
};

const auto grad = ForwardGradient<decltype(rosenbrock)>(rosenbrock, 1e-7);

// Create a gradient descent
GradientDescent<decltype(rosenbrock), decltype(grad)> gradient_descent(rosenbrock, grad, Vect<double>(n));

// Optimize
gradient_descent.optimize(20000, 1e-6);

// Check the results
assert(gradient_descent.value() <= 1e-8);

for (int i = 0; i < n; i++) {
    assert(std::abs(gradient_descent.x()(i) - 1) <= 1e-4);
}

template<typename F, typename G>
class GradientDescent

Public Functions

inline GradientDescent(F f, G grad, const Vect<double> &startingPoint)

inline void setStartingPoint(const Vect<double> &x)

Sets the point at which the gradient descent will start.

void optimize(const int maxIterationsCount, const double tolerance, const double armijoCoef = 1e-4, const double updateFactor = 1.3)

Starts the optimization.

Parameters:

• maxIterationsCount – The maximal number of iterations that the algorithm can perform

• tolerance – Once the norm of the gradient is lower than this value, the gradient descent stops.

• armijoCoef – The value of c in the Armijo’s inequality.

• updateFactor – The value by which the step length is multiplied or divided

inline double value() const

Returns the current value of f.

inline const Vect<double> &x() const

Returns the current value of x (the position of the minimum)