GALAHAD UGO package#
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.
introduction to function calls#
To solve a given problem, functions from the ugo package must be called in the following order:
ugo_initialize - provide default control parameters and set up initial data structures
ugo_read_specfile (optional) - override control values by reading replacement values from a file
ugo_import - set up problem data structures and fixed values
ugo_reset_control (optional) - possibly change control parameters if a sequence of problems are being solved
solve the problem by calling one of
ugo_solve_direct - solve using function calls to evaluate function and derivative values, or
ugo_solve_reverse - solve returning to the calling program to obtain function and derivative values
ugo_information (optional) - recover information about the solution and solution process
ugo_terminate - deallocate data structures
See the examples section for illustrations of use.
callable functions#
overview of functions provided#
// typedefs typedef float spc_; typedef double rpc_; typedef int ipc_; // structs struct ugo_control_type; struct ugo_inform_type; struct ugo_time_type; // function calls void ugo_initialize(void **data, struct ugo_control_type* control, ipc_ *status); void ugo_read_specfile(struct ugo_control_type* control, const char specfile[]); void ugo_import( struct ugo_control_type* control, void **data, ipc_ *status, const rpc_* x_l, const rpc_* x_u ); void ugo_reset_control( struct ugo_control_type* control, void **data, ipc_ *status ); void ugo_solve_direct( void **data, void *userdata, ipc_ *status, rpc_* x, rpc_* f, rpc_* g, rpc_* h, ipc_(*)(rpc_, rpc_*, rpc_*, rpc_*, const void*) eval_fgh ); void ugo_solve_reverse( void **data, ipc_ *status, ipc_ *eval_status, rpc_* x, rpc_* f, rpc_* g, rpc_* h ); void ugo_information(void **data, struct ugo_inform_type* inform, ipc_ *status); void ugo_terminate( void **data, struct ugo_control_type* control, struct ugo_inform_type* inform );
typedefs#
typedef float spc_
spc_ is real single precision
typedef double rpc_
rpc_ is the real working precision used, but may be changed to float by
defining the preprocessor variable SINGLE.
typedef int ipc_
ipc_ is the default integer word length used, but may be changed to
int64_t by defining the preprocessor variable INTEGER_64.
function calls#
void ugo_initialize(void **data, struct ugo_control_type* control, ipc_ *status)
Set default control values and initialize private data
Parameters:
data |
holds private internal data |
control |
is a struct containing control information (see ugo_control_type) |
status |
is a scalar variable of type ipc_, that gives the exit status from the package. Possible values are (currently):
|
void ugo_read_specfile(struct ugo_control_type* control, const char specfile[])
Read the content of a specification file, and assign values associated with given keywords to the corresponding control parameters. An in-depth discussion of specification files is available, and a detailed list of keywords with associated default values is provided in $GALAHAD/src/ugo/UGO.template. See also Table 2.1 in the Fortran documentation provided in $GALAHAD/doc/ugo.pdf for a list of how these keywords relate to the components of the control structure.
Parameters:
control |
is a struct containing control information (see ugo_control_type) |
specfile |
is a character string containing the name of the specification file |
void ugo_import( struct ugo_control_type* control, void **data, ipc_ *status, const rpc_* x_l, const rpc_* x_u )
Import problem data into internal storage prior to solution.
Parameters:
control |
is a struct whose members provide control paramters for the remaining prcedures (see ugo_control_type) |
data |
holds private internal data |
status |
is a scalar variable of type ipc_, that gives the exit status from the package. Possible values are:
|
x_l |
is a scalar variable of type rpc_, that holds the value \(x^l\) of the lower bound on the optimization variable \(x\). |
x_u |
is a scalar variable of type rpc_, that holds the value \(x^u\) of the upper bound on the optimization variable \(x\). |
void ugo_reset_control( struct ugo_control_type* control, void **data, ipc_ *status )
Reset control parameters after import if required.
Parameters:
control |
is a struct whose members provide control paramters for the remaining prcedures (see ugo_control_type) |
data |
holds private internal data |
status |
is a scalar variable of type ipc_, that gives the exit status from the package. Possible values are:
|
void ugo_solve_direct( void **data, void *userdata, ipc_ *status, rpc_* x, rpc_* f, rpc_* g, rpc_* h, ipc_(*)(rpc_, rpc_*, rpc_*, rpc_*, const void*) eval_fgh )
Find an approximation to the global minimizer of a given univariate function with a Lipschitz gradient in an interval.
This version is for the case where all function/derivative information is available by function calls.
Parameters:
data |
holds private internal data |
userdata |
is a structure that allows data to be passed into the function and derivative evaluation programs (see below). |
status |
is a scalar variable of type ipc_, that gives the entry and exit status from the package. On initial entry, status must be set to 1. Possible exit values are:
|
x |
is a scalar variable of type rpc_, that holds the value of the approximate global minimizer \(x\) after a successful (status = 0) call. |
f |
is a scalar variable of type rpc_, that holds the the value of the objective function \(f(x)\) at the approximate global minimizer \(x\) after a successful (status = 0) call. |
g |
is a scalar variable of type rpc_, that holds the the value of the gradient of the objective function \(f^{\prime}(x)\) at the approximate global minimizer \(x\) after a successful (status = 0) call. |
h |
is a scalar variable of type rpc_, that holds the the value of the second derivative of the objective function \(f^{\prime\prime}(x)\) at the approximate global minimizer \(x\) after a successful (status = 0) call. |
eval_fgh |
is a user-provided function that must have the following signature: ipc_ eval_fgh( rpc_ x, rpc_ *f, rpc_ *g, rpc_ *h, const void *userdata) The value of the objective function \(f(x)\) and its first derivative \(f^{\prime}(x)\) evaluated at x= \(x\) must be assigned to f and g respectively, and the function return value set to 0. In addition, if control.second_derivatives_available has been set to true, when calling ugo_import, the user must also assign the value of the second derivative \(f^{\prime\prime}(x)\) in h; it need not be assigned otherwise. If the evaluation is impossible at x, return should be set to a nonzero value. |
void ugo_solve_reverse( void **data, ipc_ *status, ipc_ *eval_status, rpc_* x, rpc_* f, rpc_* g, rpc_* h )
Find an approximation to the global minimizer of a given univariate function with a Lipschitz gradient in an interval.
This version is for the case where function/derivative information is only available by returning to the calling procedure.
Parameters:
data |
holds private internal data |
status |
is a scalar variable of type ipc_, that gives the entry and exit status from the package. On initial entry, status must be set to 1. Possible exit values are:
|
eval_status |
is a scalar variable of type ipc_, that is used to indicate if objective function and its derivatives can be provided (see above). |
x |
is a scalar variable of type rpc_, that holds the next value of \(x\) at which the user is required to evaluate the objective (and its derivatives) when status > 0, or the value of the approximate global minimizer when status = 0 |
f |
is a scalar variable of type rpc_, that must be set by the user to hold the value of \(f(x)\) if required by status > 0 (see above), and will return the value of the approximate global minimum when status = 0 |
g |
is a scalar variable of type rpc_, that must be set by the user to hold the value of \(f^{\prime}(x)\) if required by status > 0 (see above), and will return the value of the first derivative of \(f\) at the approximate global minimizer when status = 0 |
h |
is a scalar variable of type rpc_, that must be set by the user to hold the value of \(f^{\prime\prime}(x)\) if required by status > 0 (see above), and will return the value of the second derivative of \(f\) at the approximate global minimizer when status = 0 |
void ugo_information(void **data, struct ugo_inform_type* inform, ipc_ *status)
Provides output information
Parameters:
data |
holds private internal data |
inform |
is a struct containing output information (see ugo_inform_type) |
status |
is a scalar variable of type ipc_, that gives the exit status from the package. Possible values are (currently):
|
void ugo_terminate( void **data, struct ugo_control_type* control, struct ugo_inform_type* inform )
Deallocate all internal private storage
Parameters:
data |
holds private internal data |
control |
is a struct containing control information (see ugo_control_type) |
inform |
is a struct containing output information (see ugo_inform_type) |
available structures#
ugo_control_type structure#
#include <galahad_ugo.h> struct ugo_control_type { // components ipc_ error; ipc_ out; ipc_ print_level; ipc_ start_print; ipc_ stop_print; ipc_ print_gap; ipc_ maxit; ipc_ initial_points; ipc_ storage_increment; ipc_ buffer; ipc_ lipschitz_estimate_used; ipc_ next_interval_selection; ipc_ refine_with_newton; ipc_ alive_unit; char alive_file[31]; rpc_ stop_length; rpc_ small_g_for_newton; rpc_ small_g; rpc_ obj_sufficient; rpc_ global_lipschitz_constant; rpc_ reliability_parameter; rpc_ lipschitz_lower_bound; rpc_ cpu_time_limit; rpc_ clock_time_limit; bool second_derivative_available; bool space_critical; bool deallocate_error_fatal; char prefix[31]; };
detailed documentation#
control derived type as a C struct
components#
ipc_ error
error and warning diagnostics occur on stream error
ipc_ out
general output occurs on stream out
ipc_ print_level
the level of output required. Possible values are:
\(\leq\) 0 no output,
1 a one-line summary for every improvement
2 a summary of each iteration
\(\geq\) 3 increasingly verbose (debugging) output
ipc_ start_print
any printing will start on this iteration
ipc_ stop_print
any printing will stop on this iteration
ipc_ print_gap
the number of iterations between printing
ipc_ maxit
the maximum number of iterations allowed
ipc_ initial_points
the number of initial (uniformly-spaced) evaluation points (<2 reset to 2)
ipc_ storage_increment
incremenets of storage allocated (less that 1000 will be reset to 1000)
ipc_ buffer
unit for any out-of-core writing when expanding arrays
ipc_ lipschitz_estimate_used
what sort of Lipschitz constant estimate will be used:
1 = global contant provided
2 = global contant estimated
3 = local costants estimated
ipc_ next_interval_selection
how is the next interval for examination chosen:
1 = traditional
2 = local_improvement
ipc_ refine_with_newton
try refine_with_newton Newton steps from the vacinity of the global minimizer to try to improve the estimate
ipc_ alive_unit
removal of the file alive_file from unit alive_unit terminates execution
char alive_file[31]
see alive_unit
rpc_ stop_length
overall convergence tolerances. The iteration will terminate when the step is less than .stop_length
rpc_ small_g_for_newton
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
rpc_ small_g
if the absolute value of the gradient at the end of the interval search is smaller than small_g, no Newton serach is necessary
rpc_ obj_sufficient
stop if the objective function is smaller than a specified value
rpc_ global_lipschitz_constant
the global Lipschitz constant for the gradient (-ve means unknown)
rpc_ reliability_parameter
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)
rpc_ lipschitz_lower_bound
a lower bound on the Lipscitz constant for the gradient (not zero unless the function is constant)
rpc_ cpu_time_limit
the maximum CPU time allowed (-ve means infinite)
rpc_ clock_time_limit
the maximum elapsed clock time allowed (-ve means infinite)
bool second_derivative_available
if .second_derivative_available is true, the user must provide them when requested. The package is generally more effective if second derivatives are available.
bool space_critical
if .space_critical is true, every effort will be made to use as little space as possible. This may result in longer computation time
bool deallocate_error_fatal
if .deallocate_error_fatal is true, any array/pointer deallocation error will terminate execution. Otherwise, computation will continue
char prefix[31]
all output lines will be prefixed by .prefix(2:LEN(TRIM(.prefix))-1) where .prefix contains the required string enclosed in quotes, e.g. “string” or ‘string’
ugo_time_type structure#
#include <galahad_ugo.h> struct ugo_time_type { // components spc_ total; rpc_ clock_total; };
detailed documentation#
time derived type as a C struct
components#
spc_ total
the total CPU time spent in the package
rpc_ clock_total
the total clock time spent in the package
ugo_inform_type structure#
#include <galahad_ugo.h> struct ugo_inform_type { // components ipc_ status; ipc_ eval_status; ipc_ alloc_status; char bad_alloc[81]; ipc_ iter; ipc_ f_eval; ipc_ g_eval; ipc_ h_eval; struct ugo_time_type time; };
detailed documentation#
inform derived type as a C struct
components#
ipc_ status
return status. See UGO_solve for details
ipc_ eval_status
evaluation status for reverse communication interface
ipc_ alloc_status
the status of the last attempted allocation/deallocation
char bad_alloc[81]
the name of the array for which an allocation/deallocation error occurred
ipc_ iter
the total number of iterations performed
ipc_ f_eval
the total number of evaluations of the objective function
ipc_ g_eval
the total number of evaluations of the gradient of the objective function
ipc_ h_eval
the total number of evaluations of the Hessian of the objective function
struct ugo_time_type time
timings (see above)
example calls#
This is an example of how to use the package to minimize a univariate function; the code is available in $GALAHAD/src/ugo/C/ugot.c .
The floating-point type rpc_
is set in galahad_precision.h to double by default, but to float
if the preprocessor variable SINGLE is defined. Similarly, the integer
type ipc_ from galahad_precision.h is set to int by default,
but to int64_t if the preprocessor variable INTEGER_64 is defined.
/* ugo_test.c */
/* Simple code to test the UGO reverse communication C interface */
#include <stdio.h>
#include <math.h>
#include "galahad_precision.h"
#include "galahad_cfunctions.h"
#include "galahad_ugo.h"
#include <string.h>
// Test problem objective
rpc_ objf(rpc_ x){
rpc_ a = 10.0;
return x * x * cos( a*x );
}
// Test problem first derivative
rpc_ gradf(rpc_ x){
rpc_ a = 10.0;
return - a * x * x * sin( a*x ) + 2.0 * x * cos( a*x );
}
// Test problem second derivative
rpc_ hessf(rpc_ x){
rpc_ a = 10.0;
return - a * a* x * x * cos( a*x ) - 4.0 * a * x * sin( a*x )
+ 2.0 * cos( a*x );
}
int main(void) {
// Derived types
void *data;
struct ugo_control_type control;
struct ugo_inform_type inform;
// Initialize UGO
ipc_ status, eval_status;
ugo_initialize( &data, &control, &status );
// Set user-defined control options
control.print_level = 1;
//control.maxit = 100;
//control.lipschitz_estimate_used = 3;
strcpy(control.prefix, "'ugo: '");
// Read options from specfile
char specfile[] = "UGO.SPC";
ugo_read_specfile(&control, specfile);
// Test problem bounds
rpc_ x_l = -1.0;
rpc_ x_u = 2.0;
// Test problem objective, gradient, Hessian values
rpc_ x, f, g, h;
// import problem data
ugo_import( &control, &data, &status, &x_l, &x_u );
// Set for initial entry
status = 1;
// Solve the problem: min f(x), x_l <= x <= x_u
while(true){
// Call UGO_solve
ugo_solve_reverse(&data, &status, &eval_status, &x, &f, &g, &h );
// Evaluate f(x) and its derivatives as required
if(status >= 2){ // need objective
f = objf(x);
if(status >= 3){ // need first derivative
g = gradf(x);
if(status >= 4){ // need second derivative
h = hessf(x);
}
}
} else { // the solution has been found (or an error has occured)
break;
}
}
// Record solution information
ugo_information( &data, &inform, &status );
if(inform.status == 0){
printf("%" i_ipc_ "evaluations. Optimal objective value = %5.2f"
" status = %1" i_ipc_ "\n", inform.f_eval, f, inform.status);
}else{
printf("UGO_solve exit status = %1" i_ipc_ "\n", inform.status);
}
// Delete internal workspace
ugo_terminate( &data, &control, &inform );
return 0;
}