Minimization Methods :  Steepest Descent

Dr. Kalju Kahn
	UC Santa Barbara, 2006

The deepest descent minimization algorithm.attenpts to locate a minimum of a function by calculating the gradient of the function and following the the direction opposite to the direction of the gradient.  For example, consider a function 

Energy = (x^2) + 2  (y^2) 

in a three-dimensional Cartesian (Euclidean) space.  If we think of the Energy as the z-dimention, we see that the function takes a shape of an assymetric infinite bowl.

Remove["Global`*"]
Off [General::spell]

Energy  = 2  (x^2) +  (y^2);

To plot this three-dimensional function in Mathematica, we use the  Plot3D  function.

Plot3D[{Energy, 
          Hue[0.15*Energy]},  {x,  -2,  2},   {y,  -2,  2}, 
        PlotPoints  ->  100,  
        AxesLabel  ->  { "x", "y",  "Surface"},  
        Mesh ->  False];

The gradient of this function in the three-dimensional Cartesian space points to the direction of the steepest ascent.  Similarly, the direction excactly opposite to the gradient points to the steepest descent.   The gradient of a function Energy with two independent variables in the Cartesian space is given by 

∇ Energy=i ∂(Energy/∂)x+j∂(Energy/∂)y

where i and j are the unit vectors along the x and y axes, respectively and ∂(Energy/∂)x stands for the partial derivative of the Energy with respect to the coordinate x.  Partial differentiation of the function Energy = 2(x^2)  +  (y^2) with respect to x and y gives: 

∇ Energy=i 4  x+j 2  y. 

Let's say we start the search for the minimum at the point (-1, 1).  The gradient evaluates there to ∇ Energy=-4 i -2j, and the steepest descent algorithm suggest to go four small steps toward the positive direction of the x-axis and two small steps toward the positive direction of the y-axis to find a next point.  

If we use the step size of 0.1 units, then the next point (-0.6, -0.8) is closer to the minimum than a starting point but it is still far away.  The procedure must be repeated until the next point is close enought to the minimum.  The gradient at the minimum is zero and thus the algorithm can terminate if the maximum component of the gradient is close to zero.  

One possible way to inplement the Steepest Descent search in Mathematica is given below:

\(\(\(
\)\(<< \ Calculus`VectorAnalysis`

    \(SetCoordinates[Cartesian[x, y, z]];\)

    Energy = 2\ x^2 + y^2

    Step = 0.1

    StartPoint = {\(-1\), \(-1\)}

    EXY\  = 
      Energy\  /. \ {x -> StartPoint[\([1]\)], \ 
          y -> StartPoint[\([2]\)]}

    GXY\  = \ \(Grad[Energy]\)[\([{1, 2}]\)]\  /. \ {x -> 
            StartPoint[\([1]\)], \ y -> StartPoint[\([2]\)]}

    MaxForce = Max[Abs[GXY]]

    Print["  X  ", "  Y  ", "Energy", " ", "Force"]

    Print[StartPoint, " ", EXY, " ", MaxForce]\ 

    \(NextPoint\  = \ StartPoint;\)

    For[i = 1, i < 50, 
      i = i + 1, 
NextPoint = \ 
        NextPoint - Step*GXY; 
EXY\  = \ 
        Energy\  /. \ {x -> NextPoint[\([1]\)], \ 
            y -> 
              NextPoint[\([2]\)]}; 
GXY\  = \ \(Grad[
              Energy]\)[\([{1, 2}]\)]\  /. \ {x -> NextPoint[\([1]\)], \ 
            y -> NextPoint[\([2]\)]}; 
MaxForce = 
        Max[Abs[GXY]]; 
Print[NextPoint, " ", 
          EXY, " ", 
          MaxForce]\ 
If[\((MaxForce < 0.1)\), \ 
          Break[]\ , ]
]\)\)\)

We see that the minimum is very close to the point (0,0).  

Finally, we note that Mathematica has a powerful built-in function FindMinimum for locationg minima on functions that depend on one or many variables.  For example, to find the minimum of the function Energy with the built-in algorithm:

FindMinimum[
      Energy,  {x, -1}, {y, -1}]