function [ x, it ] = opt_gradient_descent ( fp_string, x0, gamma )

%*****************************************************************************80
%
%% opt_gradient_descent seeks a local minimum using gradient descent.
%
%  Discussion:
%
%    Starting at x0, a formula for f'(x) and a stepsize factor gamma are used
%    to take a sequence of gradient descent steps.
%
%    The user enters a formula for f'(x), and the values of x0 and gamma.
%
%    The program can be invoked by a function call, in which case the
%    string specifying f'(x) must be quoted:
%      [ x, it ] = opt_gradient_descent ( '2*x', 1.5, 0.01 )
%    or as an interactive command with arguments:
%      [ x, it ] = opt_gradient_descent 2*x  1.5  0.01
%    or, if called with no arguments, it will request them:
%      [ x, it ] = opt_gradient_descent ( );
%      Enter derivative formula, like 2*x: x^2
%      Enter starting value x0: 1.5
%      Enter stepsize factor gamma: 0.01
%
%    The derivative function is specified as a string which is either:
%    * a MATLAB expression using the argument 'x', 
%    * the name of an M-file followed by the argument '(x)'.
%
%    The string should not contain any spaces between symbols, except
%    when it is passed as a function argument in quotes.
%
%    It is not necessary to use the "dot" notation for expressions involving
%    '*', '/', or '^', but it doesn't hurt either.
%
%    Examples of function specifications:
%
%      x^2
%      x.^2
%      3/(x^4+5*x-6)
%      sin(7*x)*sqrt(x)/8
%      wiggle(x)     <-- where "wiggle.m" is a user-provided M file.
%
%  Licensing:
%
%    This code is distributed under the GNU LGPL license.
%
%  Modified:
%
%    29 July 2019
%
%  Author:
%
%    John Burkardt
%
%  Input:
%
%    string fp_string: the derivative of the function to be minimized.
%
%    real x0: the starting point.
%
%    real gamma: the stepsize factor.  A value of 0.01 might be a good guess.
%
%  Output:
%
%    real x: the estimated location of the minimum.
%
%    integer it: the number of steps taken.
%

%
%  Get FP, X0, GAMMA.
%
  if ( nargin < 1 )
    fp_string = input ( 'Enter derivative formula, like 2*x: ', 's' );
  end
  fp_element = vector_to_element ( fp_string );
  fp = str2func ( [ '@(x)', '( ', fp_element, ' )' ] );

  if ( nargin < 2 )
    x0 = input ( 'Enter starting point x0: ' );
  elseif ( ischar ( x0 ) )
    x0 = str2num ( x0 );
  end

  if ( nargin < 3 )
    gamma = input ( 'Enter stepsize factor gamma: ' );
  elseif ( ischar ( gamma ) )
    gamma = str2num ( gamma );
  end

  precision = 0.0000001;
  it_max = 10000;

  x = x0;
  it = 0;

  for it = 1 : it_max
    x_old = x;
    x = x_old - gamma * fp ( x_old );
    if ( abs ( x - x_old ) <= precision )
      fprintf ( '  Reached a very small stepsize\n' );
      return;
    end
  end

  fprintf ( '  Reached limit on the number of steps.\n' );

  return
end
function f_element = vector_to_element ( f_vector )

%*****************************************************************************80
%
%% vector_to_element rewrites a MATLAB vector function elementwise.
%
%  Discussion:
%
%    In MATLAB, by default, the operators '*', '/', and '^' are interpreted
%    as linear algebraic operations.  In many cases, a user simply desired
%    the elementwise operation instead, which MATLAB indicates using a 
%    dotted notation: '.*', './', and '.^'.
%
%    This function converts a string to a form that uses dotted operators.
%
%  Licensing:
%
%    This code is distributed under the GNU LGPL license.
%
%  Modified:
%
%    29 June 2019
%
%  Author:
%
%    John Burkardt
%
%  Input:
%
%    string f_vector, a string presumably representing a MATLAB expression.
%
%  Output:
%
%    string f_element, a copy of f_vector in which all operators have been
%    replaced by their dotted (elementwise) form.
%
  n_vector = length ( f_vector );
  f_element = [''];

  c_prev = '';
  for iv = 1 : n_vector
    c = f_vector(iv);
    if ( ( c == '*' || c == '/' || c == '^' ) && ( c_prev ~= '.' ) )
      f_element = [ f_element, ' .', c, ' ' ];
    else
      f_element = [ f_element, c ];
    end
    c_prev = c;
  end

  return
end

