#! /usr/bin/env python3
#
def compass_search ( function_handle, m, x, delta_tol, delta, k_max ):

#*****************************************************************************80
#
## COMPASS_SEARCH carries out a direct search minimization algorithm.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    23 January 2015
#
#  Author:
#
#    John Burkardt
#
#  Reference:
#
#    Tamara Kolda, Robert Michael Lewis, Virginia Torczon,
#    Optimization by Direct Search: New Perspectives on Some Classical and Modern Methods,
#    SIAM Review,
#    Volume 45, Number 3, 2003, pages 385-482. 
#
#  Parameters:
#
#    Input, function handle FUNCTION_HANDLE ( M, X ), a handle for the function
#    to be minimized.
#
#    Input, integer M, the number of variables.
#
#    Input, real X(M), a starting estimate for the minimizer.
#
#    Input, real DELTA_TOL, the smallest step size that is allowed.
#
#    Input, real DELTA, the starting stepsize.  
#
#    Input, integer K_MAX, the maximum number of steps allowed.
#
#    Output, real X(M), the estimated minimizer.
#
#    Output, real FX, the function value at X.
#
#    Output, integer K, the number of steps taken.
#
  import numpy as np
  from sys import exit

  k = 0
  fx = function_handle ( m, x )

  if ( delta_tol <= 0 ):
    print ( '' )
    print ( 'COMPASS_SEARCH - Fatal error!' )
    print ( '  DELTA_TOL <= 0.0.' )
    exit ( 'COMPASS_SEARCH - Fatal error!' )

  if ( delta <= delta_tol ):
    print ( '' )
    print ( 'COMPASS_SEARCH - Fatal error!' )
    print ( '  DELTA < DELTA_TOL.' )
    exit ( 'COMPASS_SEARCH - Fatal error!' )

  while ( k < k_max ):

    k = k + 1
#
#  For each coordinate direction I, seek a lower function value
#  by increasing or decreasing X(I) by DELTA.
#
    decrease = False
    s = + 1.0
    i = 0

    for ii in range ( 0, 2 * m ):

      xd = x.copy ( )
      xd[i] = xd[i] + s * delta
      fxd = function_handle ( m, xd )
#
#  As soon as a decrease is noticed, accept the new point.
#
      if ( fxd < fx ):
        x = xd.copy ( )
        fx = fxd
        decrease = True
        break

      s = - s
      if ( s == + 1.0 ):
        i = i + 1
#
#  If no decrease occurred, reduce DELTA.
#
    if ( not decrease ):
      delta = delta / 2.0
      if ( delta < delta_tol ):
        break

  return x, fx, k

if ( __name__ == '__main__' ):
  from compass_search_test import compass_search_test
  compass_search_test ( )