From 8ff5cc31794c0f0d2e7c4c5e8c9cb9552c4719d2 Mon Sep 17 00:00:00 2001 From: Michael Orlitzky Date: Fri, 22 Mar 2013 22:26:56 -0400 Subject: [PATCH] Use the infinity norm in steepest_descent(), update its comments, and simplify the main loop. --- optimization/steepest_descent.m | 29 +++++++++++++---------------- 1 file changed, 13 insertions(+), 16 deletions(-) diff --git a/optimization/steepest_descent.m b/optimization/steepest_descent.m index 4fb3329..0a6475e 100644 --- a/optimization/steepest_descent.m +++ b/optimization/steepest_descent.m @@ -1,12 +1,16 @@ -function [x, k] = steepest_descent(g, x0, step_size, tolerance, max_iterations) +function [x, k] = steepest_descent(g, ... + x0, ... + step_size, ... + tolerance, ... + max_iterations) % % An implementation of the steepest-descent algorithm, with the % search direction d_{k} = -\nabla f(x_{k}). % % We should terminate when either, % - % a) The 2-norm of the gradient at x_{k} is greater than - % ``tolerance``. + % a) The infinity-norm of the gradient at x_{k} is greater than + % ``tolerance``. % % b) We have performed ``max_iterations`` iterations. % @@ -24,17 +28,17 @@ function [x, k] = steepest_descent(g, x0, step_size, tolerance, max_iterations) % receive. % % * ``tolerance`` - the stopping tolerance. We stop when the norm - % of the gradient falls below this value. + % of the gradient falls below this value. % % * ``max_iterations`` - a safety net; we return x_{k} - % unconditionally if we exceed this number of iterations. + % unconditionally if we exceed this number of iterations. % % OUTPUT: % % * ``x`` - the solution at the final value of x_{k}. % % * ``k`` - the value of k when we stop; i.e. the number of - % iterations. + % iterations. % % NOTES: % @@ -48,16 +52,9 @@ function [x, k] = steepest_descent(g, x0, step_size, tolerance, max_iterations) xk = x0; gk = g(xk); - while (k <= max_iterations) - % Loop until either of our stopping conditions are met. If the - % loop finishes, we have implicitly met the second stopping - % condition (number of iterations). - - if (norm(gk) < tolerance) - % This catches the k=0 case, too. - x = xk; - return; - end + while (k <= max_iterations && norm(gk, 'inf') > tolerance) + % Loop until either of our stopping conditions are met. This + % should also work when x0 is a satisfactory point. dk = -gk; alpha_k = step_size(xk); -- 2.33.1