项目作者: linesd

项目描述 :
Conjugate gradients minimization
高级语言: Python
项目地址: git://github.com/linesd/minimize.git
创建时间: 2019-08-23T00:46:43Z
项目社区:https://github.com/linesd/minimize

开源协议:Other

下载


minimize Python 3.5+

This repository is a Python implementation of C.E. Rasmussen’s minimize function which finds a (local) minimum of a (nonlinear) multivariate function. The function uses conjugate gradients and approximate linesearches based on polynomial interpolation with Wolfe-Powel conditions. The user supplies a function which returns the function value as well as the partial derivatives with respect to the variables to be minimized.

Notes:

  • Tested for python >= 3.5

Table of Contents:

  1. minimize usage
  2. check_grad usage
  3. Testing

minimize usage

The minimize function can be found at optimizer/minimize.py and is called according to the following definition.
An example of its usage follows.

  1. Xs, convergence, i = minimize(f, X, length, args=(), reduction=None, verbose=True)
  1. Parameters
  2. ----------
  3. f : function to minimize. The function must return the value
  4. of the function (float) and a numpy array of partial
  5. derivatives of shape (D,) with respect to X, where D is
  6. the dimensionality of the function.
  7. X : numpy array - Shape : (D, 1)
  8. initial guess.
  9. length : int
  10. The length of the run. If positive, length gives the maximum
  11. number of line searches, if negative its absolute value gives
  12. the maximum number of function evaluations.
  13. args : tuple
  14. Tuple of parameters to be passed to the function f.
  15. reduction : float
  16. The expected reduction in the function value in the first
  17. linesearch (if None, defaults to 1.0)
  18. verbose : bool
  19. If True - prints the progress of minimize. (default is True)
  20. concise : bool
  21. If True - returns concise convergence info, only the minimium function
  22. value (necessary when optimizing a large number of parameters)
  23. (default is False)
  24. Return
  25. ------
  26. Xs : numpy array - Shape : (D, 1)
  27. The found solution.
  28. convergence : numpy array - Shape : (i, D+1)
  29. Convergence information. The first column is the function values
  30. returned by the function being minimized. The next D columns are
  31. the guesses of X during the minimization process.
  32. If concise = True, convergence information is only the minimum
  33. function value. This is necessary only when optimizing a large number
  34. of parameters.
  35. i : int
  36. Number of line searches or function evaluations depending on which was selected.

Here the two-dimensional rosenbrock function is used to show how minimize works. The rosenbrock function returns the function value and the partial derivatives with respect to the variables to be minimized.

Starting from initial conditions X0 = np.array([[-1],[0]]) and length = 100 “linesearches”:

  1. >>> X, convergence, i = minimize(rosenbrock, X0, length=100)
  2. >>> X
  3. array([[1.],
  4. [1.]])
  5. >>> i
  6. 33

The minimum of the function occurs at X = [1., 1.] with a function value of 0 and is determined after 33 iterations. The convergence returned by minimize has the function evaluations in the first column, and the parameters being minimised in the following D columns. The figure below shows the convergence values plotted over the rosenbrock function. If the length parameter is set to a negative value then the algorithm is limited by function evaluations rather than linesearches.



check_grad usage

The check_grad function can be found at optimizer/test_grad.py and can be used to check that the function values
and partial derivatives are consistent. The check_grad function compares the values of the partial derivatives returned by the function with a finite difference approximation. check_grad prints a comparison of the partial derivatives and the finite difference approximation and returns the norm of the difference divided by the norm of the sum of the partial derivatives and finite differences.

  1. d = check_grad(f, X, e, args=())
  1. Parameters
  2. ----------
  3. f : function to minimize. The function must return the value
  4. of the function (float) and a numpy array of partial
  5. derivatives of shape (D,) with respect to X, where D is
  6. the dimensionality of the function.
  7. X : numpy array - Shape : (D, 1)
  8. argument for function f that the partial derivatives
  9. relate to.
  10. e : float
  11. size of the perturbation used for the finite differences.
  12. args : tuple
  13. Tuple of parameters to be passed to the function f.
  14. Return
  15. ------
  16. vec : numpy array of shape (D, 2)
  17. The first column is dy which is generated from the function
  18. partial derivatives. The second column is dh which is generated
  19. from the finite difference approximations.
  20. d : the norm of the difference divided by the norm of
  21. the sum.

It is used as follows:

  1. >>> np.random.seed(0)
  2. >>> X = np.random.normal(0, 1, size=(3,1))
  3. >>> vec, d = check_grad(rosenbrock, X, 1e-5)
  4. >>> print("Gradients vs finite difference:")
  5. >>> print(vec)
  6. Gradients vs finite difference:
  7. [[1914.97696491 1914.97696499]
  8. [-674.57380768 -674.57380767]
  9. [ 163.72243854 163.72243854]]
  10. >>> print("d : ", d)
  11. d : 1.9199773511233608e-11

Testing

Testing setup with pytest (requires installation). Should you want to check version
compatibility or make changes, you can check that original minimize functionality remains unaffected by executing
pytest -v in the test directory. You should see the following: