Use the infinity norm in steepest_descent(), update its comments, and simplify the...
authorMichael Orlitzky <michael@orlitzky.com>
Sat, 23 Mar 2013 02:26:56 +0000 (22:26 -0400)
committerMichael Orlitzky <michael@orlitzky.com>
Sat, 23 Mar 2013 02:26:56 +0000 (22:26 -0400)
optimization/steepest_descent.m

index 4fb332950b26c055a237ec34c1e04a9a249c0fd4..0a6475e4614c37822be1c36ce891c003aae6ca55 100644 (file)
@@ -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);