title: Gradient descent optimization for multivariate scalar functions
body: <p>I attempted to test my gradient descent program on rosenbrock function. But no matter how I adjusted my learning rate (<code>step</code> argument), precision (<code>precision</code> argument) and number of iterations (<code>iteration</code> argument), I couldn't get a very close result.</p>
  
  <pre><code>import numpy as np
  
  def minimize(f, f_grad, x, step=1e-3, iterations=1e3, precision=1e-3):
      count = 0
      while True:
          last_x = x
          x = x - step * f_grad(x)
          count += 1
          if count &gt; iterations or np.linalg.norm(x - last_x) &lt; precision:
              break
      return x
  
  def rosenbrock(x):
      """The Rosenbrock function"""
      return sum(100.0*(x[1:]-x[:-1]**2.0)**2.0 + (1-x[:-1])**2.0)
  
  def rosenbrock_grad(x):
      """Gradient of Rosenbrock function"""
      xm = x[1:-1]
      xm_m1 = x[:-2]
      xm_p1 = x[2:]
      der = np.zeros_like(x)
      der[1:-1] = 200*(xm-xm_m1**2) - 400*(xm_p1 - xm**2)*xm - 2*(1-xm)
      der[0] = -400*x[0]*(x[1]-x[0]**2) - 2*(1-x[0])
      der[-1] = 200*(x[-1]-x[-2]**2)
      return der
  
  x0 = np.array([1.3, 0.7, 0.8, 1.9, 1.2])
  minimize(rosenbrock, rosenbrock_grad, x0, step=1e-6, iterations=1e4, precision=1e-6)
  </code></pre>
  
  <p>For example, code like above gives me <code>array([ 1.01723267,  1.03694999,  1.07870143,  1.16693184,  1.36404334])</code>. But if I use any built-in optimization methods in <code>scipy.optimize</code>, I can get very close answer or exactly equal <code>array([ 1.,  1.,  1.,  1.,  1.])</code> (this is the true answer).</p>
  
  <p>However, if I use very small <code>step</code>, <code>precision</code> and very large <code>iterations</code> in my program, the calculation just takes forever on my computer.</p>
  
  <p>I wonder if this is due to </p>
  
  <blockquote>
    <p>any bugs in my program</p>
  </blockquote>
  
  <p>or just because </p>
  
  <blockquote>
    <p>gradient descent is inefficient here and demands very small
    <code>step</code>, <code>precision</code> and very large <code>iterations</code> to yield a very close
    solution</p>
  </blockquote>
  
  <p>or because </p>
  
  <blockquote>
    <p>I need to do some special feature scaling.</p>
  </blockquote>
  
  <p><em>(Ps. I also tried to plot two-dimensional plot where value of function is on y axis and the number of iterations is on x axis to "debug" gradient descent, but even I get a nice-looking downsloping graph, the solution is still not very close.)</em></p>