1 function [x, k] = steepest_descent(g, x0, step_size, tolerance, max_iterations)
3 % An implementation of the steepest-descent algorithm, with the
4 % search direction d_{k} = -\nabla f(x_{k}).
6 % We should terminate when either,
8 % a) The 2-norm of the gradient at x_{k} is greater than
11 % b) We have performed ``max_iterations`` iterations.
15 % * ``g`` - the gradient of the function ``f`` we're minimizing.
17 % * ``x0`` - the starting point for the search.
19 % * ``step_size`` - a function of x which returns the optimal step
20 % size alpha_{k}. This will generally require more information
21 % than just x; for example it might need the function ``f`` or the
22 % gradient ``g``. However, our caller has this information so it
23 % should be incorporated into the step size algorithm that we
26 % * ``tolerance`` - the stopping tolerance. We stop when the norm
27 % of the gradient falls below this value.
29 % * ``max_iterations`` - a safety net; we return x_{k}
30 % unconditionally if we exceed this number of iterations.
34 % * ``x`` - the solution at the final value of x_{k}.
36 % * ``k`` - the value of k when we stop; i.e. the number of
41 % A specialized implementation for solving e.g. Qx=b can avoid one
42 % matrix-vector multiplication below.
45 % The initial gradient at x_{0} is not supplied, so we compute it
46 % here and begin the loop at k=1.
50 if (norm(g_k) < tolerance)
51 % If x_0 is close enough to a solution, there's nothing for us to
52 % do! We use g_k (the gradient of f at x_k) instead of d_k because
53 % their 2-norms will be the same, and g_k is already stored.
57 for k = [1 : max_iterations]
58 % Loop until either of our stopping conditions are met. If the
59 % loop finishes, we have implicitly met the second stopping
60 % condition (number of iterations).
62 alpha_k = step_size(x);
63 x = x + (alpha_k * d_k);
66 if (norm(g_k) < tolerance)
71 % If we make it to the end of the loop, that means we've executed the
72 % maximum allowed iterations. The caller should be able to examine the
73 % return value ``k`` to determine what happened.