From 8ff5cc31794c0f0d2e7c4c5e8c9cb9552c4719d2 Mon Sep 17 00:00:00 2001
From: Michael Orlitzky <michael@orlitzky.com>
Date: Fri, 22 Mar 2013 22:26:56 -0400
Subject: [PATCH 1/1] 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.43.2