UGO

purpose

The ugo package aims to find the global minimizer of a univariate twice-continuously differentiable function \(f(x)\) of a single variable over the finite interval \(x^l <= x <= x^u\). Function and derivative values are provided via a subroutine call. Second derivatives may be used to advantage if they are available.

See Section 4 of $GALAHAD/doc/ugo.pdf for additional details.

method

The algorithm starts by splitting the interval \([x^l,x^u]\) into a specified number of subintervals \([x_i,x_{i+1}]\) of equal length, and evaluating \(f\) and its derivatives at each \(x_i\). A surrogate (approximating) lower bound function is constructed on each subinterval using the function and derivative values at each end, and an estimate of the first- and second-derivative Lipschitz constant. This surrogate is minimized, the true objective evaluated at the best predicted point, and the corresponding interval split again at this point. Any interval whose surrogate lower bound value exceeds an evaluated actual value is discarded. The method continues until only one interval of a maximum permitted width remains.

reference

Many ingredients in the algorithm are based on the paper

D. Lera and Ya. D. Sergeyev, “Acceleration of univariate global optimization algorithms working with Lipschitz functions and Lipschitz first derivatives” SIAM J. Optimization 23(1), (2013) 508–529

but adapted to use second derivatives.

functions

ugo.initialize()

Set default option values and initialize private data.

Returns:

optionsdict

dictionary containing default control options:

errorint

error and warning diagnostics occur on stream error.

outint

general output occurs on stream out.

print_levelint

the level of output required. Possible values are:

• <= 0

  no output

• 1

  a one-line summary for every improvement

• 2

  a summary of each iteration

• >= 3

  increasingly verbose (debugging) output.

start_printint

any printing will start on this iteration.

stop_printint

any printing will stop on this iteration.

print_gapint

the number of iterations between printing.

maxitint

the maximum number of iterations allowed.

initial_pointint

the number of initial (uniformly-spaced) evaluation points (<2 reset to 2).

storage_incrementint

incremenets of storage allocated (less that 1000 will be reset to 1000).

bufferint

unit for any out-of-core writing when expanding arrays.

lipschitz_estimate_usedint

what sort of Lipschitz constant estimate will be used:

• 1

  the global contant provided

• 2

  an estimated global contant

• 3

  estimated local costants.

next_interval_selectionint

how is the next interval for examination chosen:

• 1

  traditional

• 2

  local_improvement.

refine_with_newtonint

try refine_with_newton Newton steps from the vacinity of the global minimizer to try to improve the estimate.

alive_unitint

removal of the file alive_file from unit alive_unit terminates execution.

alive_filestr

see alive_unit.

stop_lengthfloat

overall convergence tolerances. The iteration will terminate when the step is less than stop_length.

small_g_for_newtonfloat

if the absolute value of the gradient is smaller than small_g_for_newton, the next evaluation point may be at a Newton estimate of a local minimizer.

small_gfloat

if the absolute value of the gradient at the end of the interval search is smaller than small_g, no Newton search is necessary.

obj_sufficientfloat

stop if the objective function is smaller than a specified value.

global_lipschitz_constantfloat

the global Lipschitz constant for the gradient (-ve means unknown).

reliability_parameterfloat

the reliability parameter that is used to boost insufficiently large estimates of the Lipschitz constant (-ve means that default values will be chosen depending on whether second derivatives are provided or not).

lipschitz_lower_boundfloat

a lower bound on the Lipschitz constant for the gradient (not zero unless the function is constant).

cpu_time_limitfloat

the maximum CPU time allowed (-ve means infinite).

clock_time_limitfloat

the maximum elapsed clock time allowed (-ve means infinite).

second_derivative_availablebool

if second_derivative_available is True, the user must provide them when requested. The package is generally more effective if second derivatives are available.

space_criticalbool

if space_critical is True, every effort will be made to use as little space as possible. This may result in longer computation time.

deallocate_error_fatalbool

if deallocate_error_fatal is True, any array/pointer deallocation error will terminate execution. Otherwise, computation will continue.

prefixstr

all output lines will be prefixed by the string contained in quotes within prefix, e.g. ‘word’ (note the qutoes) will result in the prefix word.

ugo.load(x_l, x_u, options=None)

Import problem data into internal storage prior to solution.

Parameters:

x_ldouble

holds the value \(x^l\) of the lower bound on the optimization variable \(x\).

x_udouble

holds the value \(x^u\) of the upper bound on the optimization variable \(x\).

optionsdict, optional

dictionary of control options (see ugo.initialize).

ugo.solve(eval_fgh)

Find an approximation to the global minimizer of a given univariate function with a Lipschitz gradient in an interval.

Parameters:

eval_fghcallable

a user-defined function that must have the signature:

f, g, h = eval_fgh(x)

The value of the objective function \(f(x)\) and its first derivative \(f'(x)\) evaluated at \(x\) must be assigned to f and g respectively. In addition, if options[‘second_derivatives_available’] has been set to True when calling ugo.load, the user must also assign the value of the second derivative \(f''(x)\) to h; it need not be assigned otherwise.

Returns:

xdouble

holds the value of the approximate global minimizer \(x\) after a successful call.

fdouble

holds the value of the objective function \(f(x)\) at the approximate global minimizer \(x\) after a successful call.

gdouble

holds the value of the gradient of the objective function \(f'(x)\) at the approximate global minimizer \(x\) after a successful call.

hdouble

holds the value of the second derivative of the objective function \(f''(x)\) at the approximate global minimizer \(x\) after a successful call.

[optional] ugo.information()

Provide optional output information.

Returns:

informdict

dictionary containing output information:

statusint

return status. Possible values are:

• 0

  The run was successful.

• -1

  An allocation error occurred. A message indicating the offending array is written on unit options[‘error’], and the returned allocation status and a string containing the name of the offending array are held in inform[‘alloc_status’] and inform[‘bad_alloc’] respectively.

• -2

  A deallocation error occurred. A message indicating the offending array is written on unit options[‘error’] and the returned allocation status and a string containing the name of the offending array are held in inform[‘alloc_status’] and inform[‘bad_alloc’] respectively.

• -7

  The objective function appears to be unbounded from below.

• -18

  Too many iterations have been performed. This may happen if options[‘maxit’] is too small, but may also be symptomatic of a badly scaled problem.

• -19

  The CPU time limit has been reached. This may happen if options[‘cpu_time_limit’] is too small, but may also be symptomatic of a badly scaled problem.

• -40

  The user has forced termination of the solver by removing the file named options[‘alive_file’] from unit options[‘alive_unit’].

alloc_statusint

the status of the last attempted internal array. allocation/deallocation

bad_allocstr

the name of the array for which an internal array allocation/deallocation error occurred.

iterint

the total number of iterations performed

f_evalint

the total number of evaluations of the objective function.

g_evalint

the total number of evaluations of the gradient of the objective function.

h_evalint

the total number of evaluations of the Hessian of the objective function.

timedict

dictionary containing tim information:

totalfloat

the total CPU time spent in the package.

clock_totalfloat

the total clock time spent in the package.

ugo.terminate()

Deallocate all internal private storage.

example code

from galahad import ugo
import numpy as np
np.set_printoptions(precision=4,suppress=True,floatmode='fixed')
print("\n** python test: ugo")

# allocate internal data and set default options
options = ugo.initialize()

# set some non-default options
options['print_level'] = 0
#print("options:", options)

# load data (and optionally non-default options)
x_l = -1
x_u = 2
ugo.load(x_l,x_u,options=options)

# define objective function
# NB python functions have access to external variables
# So no need for userdata like in C or Fortran
def eval_fgh(x):
   a = 10
   f = x * x * np.cos( a*x )
   g = - a * x * x * np.sin( a*x ) + 2.0 * x * np.cos( a*x )
   h = - a * a* x * x * np.cos( a*x ) - 4.0 * a * x * np.sin( a*x ) \
       + 2.0 * np.cos( a*x )
   return f, g, h


# find optimum
x, f, g, h = ugo.solve(eval_fgh)
print(" x: %.4f" % x)
print(" f: %.4f" % f)
print(" g: %.4f" % g)
print(" h: %.4f" % h)

# get information
inform = ugo.information()
print('** ugo exit status:', inform['status'])

# deallocate internal data
ugo.terminate()

This example code is available in $GALAHAD/src/ugo/Python/test_ugo.py .