rbfopt_utils module

Utility functions.

This module contains a number of subroutines that are used by the other modules. In particular it contains most of the subroutines that do the calculations using numpy, as well as utility functions for various modules.

Licensed under Revised BSD license, see LICENSE. (C) Copyright Singapore University of Technology and Design 2014. (C) Copyright International Business Machines Corporation 2017.

rbfopt_utils.bulk_evaluate_rbf(settings, points, n, k, node_pos, rbf_lambda, rbf_h, return_distances=u'no')

Evaluate the RBF interpolant at all points in a given list.

Evaluate the RBF interpolant at all points in a given list. This version uses numpy and should be faster than individually evaluating the RBF at each single point, provided that the list of points is large enough. It also computes the distance or the minimum distance of each point from the interpolation nodes, if requested, since this comes almost for free.

Parameters:

settings : rbfopt_settings.RbfoptSettings.

Global and algorithmic settings.

points : 2D numpy.ndarray[float]

The list of points in R^n where we want to evaluate the interpolant.

n : int

Dimension of the problem, i.e. the size of the space.

k : int

Number of interpolation nodes.

node_pos : 2D numpy.ndarray[float]

List of coordinates of the interpolation points.

rbf_lambda : 1D numpy.ndarray[float]

The lambda coefficients of the RBF interpolant, corresponding to the radial basis functions. List of dimension k.

rbf_h : 1D numpy.ndarray[float]

The h coefficients of the RBF interpolant, corresponding to he polynomial. List of dimension given by get_size_P_matrix().

return_distances : string

If ‘no’, do nothing. If ‘min’, return the minimum distance of each point to interpolation nodes. If ‘all’, return the full distance matrix to the interpolation nodes.

Returns:

1D numpy.ndarray[float] or (1D numpy.ndarray[float], 1D numpy.ndarray[float])

Value of the RBF interpolant at each point; if compute_min_dist is True, additionally returns the minimum distance of each point from the interpolation nodes.

rbfopt_utils.bulk_get_min_distance(points, other_points)

Get the minimum distances between two sets of points.

Compute the minimum distance of each point in the first set to the points in the second set. This is faster than using get_min_distance repeatedly, for large sets of points.

Parameters:

points : 2D numpy.ndarray[float]

The points in R^n that we compute the distances from.

other_points : 2D numpy.ndarray[float]

The list of points we want to compute the distances to.

Returns:

1D numpy.ndarray[float]

Minimum distance between each point in points and the other_points.

See also

get_min_distance

rbfopt_utils.bulk_transform_domain(settings, var_lower, var_upper, points, reverse=False)

Rescale the domain.

Rescale the function domain according to the chosen strategy.

Parameters:

settings : rbfopt_settings.RbfoptSettings

Global and algorithmic settings.

var_lower : 1D numpy.ndarray[float]

List of lower bounds of the variables.

var_upper : 1D numpy.ndarray[float]

List of upper bounds of the variables.

points : 2D numpy.ndarray[float]

Point in the domain to be rescaled.

reverse : bool

False if we transform from the original domain to the transformed space, True if we want to apply the reverse.

Returns:

2D numpy.ndarray[float]

Rescaled points.

Raises:

ValueError

If the requested rescaling strategy is not implemented.

rbfopt_utils.compute_gap(settings, fmin)

Compute the optimality gap w.r.t. the target value.

Parameters:

settings : rbfopt_settings.RbfoptSettings

Global and algorithmic settings.

fmin : float

Best known function value discovered so far. Note that this value should already take into account possible noise at the best point.

Returns:

float

The current optimality gap, i.e. relative distance from target value.

rbfopt_utils.distance(p1, p2)

Compute Euclidean distance between two points.

Compute Euclidean distance between two points.

Parameters:

p1 : 1D numpy.ndarray[float]

First point.

p2 : 1D numpy.ndarray[float]

Second point.

Returns:

float

Euclidean distance.

rbfopt_utils.evaluate_rbf(settings, point, n, k, node_pos, rbf_lambda, rbf_h)

Evaluate the RBF interpolant at a given point.

Evaluate the RBF interpolant at a given point.

Parameters:

settings : rbfopt_settings.RbfoptSettings.

Global and algorithmic settings.

point : 1D numpy.ndarray[float]

The point in R^n where we want to evaluate the interpolant.

n : int

Dimension of the problem, i.e. the size of the space.

k : int

Number of interpolation nodes.

node_pos : 2D numpy.ndarray[float]

List of coordinates of the interpolation points.

rbf_lambda : 1D numpy.ndarray[float]

The lambda coefficients of the RBF interpolant, corresponding to the radial basis functions. List of dimension k.

rbf_h : 1D numpy.ndarray[float]

The h coefficients of the RBF interpolant, corresponding to he polynomial. List of dimension given by get_size_P_matrix().

Returns:

float

Value of the RBF interpolant at the given point.

rbfopt_utils.get_all_corners(var_lower, var_upper)

Compute all corner points of a box.

Compute and return all the corner points of the given box. Note that this number is exponential in the dimension of the problem.

Parameters:

var_lower : 1D numpy.ndarray[float]

List of lower bounds of the variables.

var_upper : 1D numpy.ndarray[float]

List of upper bounds of the variables.

Returns:

2D numpy.ndarray[float]

All the corner points.

rbfopt_utils.get_best_rbf_model(settings, n, k, node_pos, node_val, num_nodes_to_check)

Compute which type of RBF yields the best model.

Compute which RBF interpolant yields the best surrogate model, using cross validation to determine the lowest leave-one-out error.

Parameters:

settings : rbfopt_settings.RbfoptSettings

Global and algorithmic settings.

n : int

Dimension of the problem, i.e. the space where the point lives.

k : int

Number of nodes, i.e. interpolation points.

node_pos : 2D numpy.ndarray[float]

Location of current interpolation nodes (one on each row.

node_val : 1D numpy.ndarray[float]

List of values of the function at the nodes.

num_nodes_to_check : int

Number of nodes on which quality should be tested.

Returns:

str

The type of RBF that currently yields the best surrogate model, based on leave-one-out error. This will be one of the supported types of RBF.

rbfopt_utils.get_degree_polynomial(settings)

Compute the degree of the polynomial for the interpolant.

Return the degree of the polynomial that should be used in the RBF expression to ensure unisolvence and convergence of the optimization method.

Parameters:

settings : rbfopt_settings.RbfoptSettings

Global and algorithmic settings.

Returns:

int

Degree of the polynomial

Raises:

ValueError

If the matrix type is not implemented.

rbfopt_utils.get_fmax_current_iter(settings, n, k, current_step, node_val)

Compute the largest function value for target value computation.

Compute the largest function value used to determine the target value. This is given by the sorted value in position :math: sigma_n.

Parameters:

settings : rbfopt_settings.RbfoptSettings

Global and algorithmic settings.

n : int

Dimension of the problem, i.e. the space where the point lives.

k : int

Number of nodes, i.e. interpolation points.

current_step : int

The current step in the cyclic search strategy.

node_val : 1D numpy.ndarray[float]

List of function values.

Returns:

float

The value that should be used to determine the range of the function values when computing the target value.

See also

get_sigma_n

rbfopt_utils.get_lhd_corr_points(var_lower, var_upper, num_trials=50)

Compute a latin hypercube design with min correlation.

Compute a list of (n+1) points in the given box, where n is the dimension of the space. The selected points are picked according to a random latin hypercube design with minimum correlation criterion. This function relies on the library pyDOE.

Parameters:

var_lower : 1D numpy.ndarray[float]

List of lower bounds of the variables.

var_upper : 1D numpy.ndarray[float]

List of upper bounds of the variables.

num_trials : int

Maximum number of generated LHs to choose from.

Returns:

2D numpy.ndarray[float]

List of points in the latin hypercube design.

rbfopt_utils.get_lhd_maximin_points(var_lower, var_upper, num_trials=50)

Compute a latin hypercube design with maximin distance.

Compute an array of (n+1) points in the given box, where n is the dimension of the space. The selected points are picked according to a random latin hypercube design with maximin distance criterion.

Parameters:

var_lower : 1D numpy.ndarray[float]

List of lower bounds of the variables.

var_upper : 1D numpy.ndarray[float]

List of upper bounds of the variables.

num_trials : int

Maximum number of generated LHs to choose from.

Returns:

2D numpy.ndarray[float]

List of points in the latin hypercube design.

rbfopt_utils.get_lower_corners(var_lower, var_upper)

Compute the lower corner points of a box.

Compute a list of (n+1) corner points of the given box, where n is the dimension of the space. The selected points are the bottom left (i.e. corresponding to the origin in the 0-1 hypercube) and the n adjacent ones.

Parameters:

var_lower : 1D numpy.ndarray[float]

List of lower bounds of the variables.

var_upper : 1D numpy.ndarray[float]

List of upper bounds of the variables.

Returns:

2D numpy.ndarray[float]

The lower corner points.

rbfopt_utils.get_matrix_inverse(settings, Amat)

Compute the inverse of a matrix.

Compute the inverse of a given matrix, zeroing out small coefficients to improve sparsity.

Parameters:

settings : rbfopt_settings.RbfoptSettings

Global and algorithmic settings.

Amat : numpy.matrix

The matrix to invert.

Returns:

numpy.matrix

The matrix Amat^{-1}.

Raises:

numpy.linalg.LinAlgError

If the matrix cannot be inverted for numerical reasons.

rbfopt_utils.get_min_distance(point, other_points)

Compute minimum distance from a set of points.

Compute the minimum Euclidean distance between a given point and a list of points.

Parameters:

point : 1D numpy.ndarray[float]

The point we compute the distances from.

other_points : 2D numpy.ndarray[float]

The list of points we want to compute the distances to.

Returns:

float

Minimum distance between point and the other_points.

rbfopt_utils.get_min_distance_and_index(point, other_points)

Compute the distance and index of the point with minimum distance.

Compute the distance value and the index of the point in a matrix that achieves minimum Euclidean distance to a given point.

Parameters:

point : 1D numpy.ndarray[float]

The point we compute the distances from.

other_points : 2D numpy.ndarray[float]

The list of points we want to compute the distances to.

Returns:

(float, int)

The distance value and the index of the point in other_points that achieved minimum distance from point.

rbfopt_utils.get_model_quality_estimate(settings, n, k, node_pos, node_val, num_nodes_to_check)

Compute an estimate of model quality.

Computes an estimate of model quality, performing cross-validation. It only checks the best num_nodes_to_check nodes.

Parameters:

settings : rbfopt_settings.RbfoptSettings

Global and algorithmic settings.

n : int

Dimension of the problem, i.e. the space where the point lives.

k : int

Number of nodes, i.e. interpolation points.

node_pos : 2D numpy.ndarray[float]

Location of current interpolation nodes (one on each row).

node_val : 1D numpy.ndarray[float]

List of values of the function at the nodes.

num_nodes_to_check : int

Number of nodes on which quality should be tested.

Returns:

float

An estimate of the leave-one-out cross-validation error, which can be interpreted as a measure of model quality.

Raises:

ValueError

If the RBF type is not implemented.

rbfopt_utils.get_most_common_element(array, to_exclude=[])

Get most common element in a list.

Parameters:

array : List[any]

The list whose most common element is sought.

to_exclude : List[any]

A list of elements to exclude from the count.

Returns:

Any

The most common element, None if all elements were excluded.

rbfopt_utils.get_one_ready_index(results)

Get index of a single async computation result that is ready.

Given a list containing results of asynchronous computations dispatched to a worker pool, obtain the index of the last computation that has concluded. (Last is better to use the pop() function in the list.)

Parameters:

results : List[(multiprocessing.pool.AsyncResult, any)]

A list of tasks, where each task is a list and the first element is the output of a call to apply_async. The other elements of the list will never be scanned by this function, and they could be anything.

Returns:

int

Index of last computation that completed, or len(results) if no computation is ready.

rbfopt_utils.get_random_corners(var_lower, var_upper)

Compute some randomly selected corner points of the box.

Compute a list of (n+1) corner points of the given box, where n is the dimension of the space. The selected points are picked randomly.

Parameters:

var_lower : 1D numpy.ndarray[float]

List of lower bounds of the variables.

var_upper : 1D numpy.ndarray[float]

List of upper bounds of the variables.

Returns:

2D numpy.ndarray[float]

A List of random corner points.

rbfopt_utils.get_rbf_coefficients(settings, n, k, Amat, node_val)

Compute the coefficients of the RBF interpolant.

Solve a linear system to compute the coefficients of the RBF interpolant.

Parameters:

settings : rbfopt_settings.RbfoptSettings.

Global and algorithmic settings.

n : int

Dimension of the problem, i.e. the size of the space.

k : int

Number of interpolation nodes.

Amat : numpy.matrix

Matrix [Phi P; P^T 0] defining the linear system. Must be a square matrix of appropriate size.

node_val : 1D numpy.ndarray[float]

List of values of the function at the nodes.

Returns:

(1D numpy.ndarray[float], 1D numpy.ndarray[float])

Lambda coefficients (for the radial basis functions), and h coefficients (for the polynomial).

rbfopt_utils.get_rbf_function(settings)

Return a radial basis function.

Return the radial basis function appropriate function as indicated by the settings.

Parameters:

settings : rbfopt_settings.RbfoptSettings

Global and algorithmic settings.

Returns

—

Callable[numpy.ndarray]

A callable radial basis function that can be applied on floats and numpy.ndarray.

rbfopt_utils.get_rbf_matrix(settings, n, k, node_pos)

Compute the matrix for the RBF system.

Compute the matrix A = [Phi P; P^T 0] of equation (3) in the paper by Costa and Nannicini.

Parameters:

settings : rbfopt_settings.RbfoptSettings.

Global and algorithmic settings.

n : int

Dimension of the problem, i.e. the size of the space.

k : int

Number of interpolation nodes.

node_pos : 2D numpy.ndarray[float]

List of coordinates of the nodes.

Returns:

numpy.matrix

The matrix A = [Phi P; P^T 0].

Raises:

ValueError

If the type of RBF function is not supported.

rbfopt_utils.get_sigma_n(k, current_step, num_global_searches, num_initial_points)

Compute sigma_n.

Compute the index :math: sigma_n, where :math: sigma_n is a function described in the paper by Gutmann (2001). The same function is called :math: alpha_n in a paper of Regis & Shoemaker (2007).

Parameters:

k : int

Number of nodes, i.e. interpolation points.

current_step : int

The current step in the cyclic search strategy.

num_global_searches : int

The number of global searches in a cycle.

num_initial_points : int

Number of points for the initialization phase.

Returns:

int

The value of sigma_n.

rbfopt_utils.get_size_P_matrix(settings, n)

Compute size of the P part of the RBF matrix.

Return the number of columns in the P part of the matrix [Phi P; P^T 0] that is used through the algorithm.

Parameters:

settings : rbfopt_settings.RbfoptSettings

Global and algorithmic settings.

n : int

Dimension of the problem, i.e. number of variables.

Returns:

int

Number of columns in the matrix

Raises:

ValueError

If the matrix type is not implemented.

rbfopt_utils.get_uniform_lhs(n, num_samples)

Generate random Latin Hypercube samples.

Generate points using Latin Hypercube sampling from the uniform distribution in the unit hypercube.

Parameters:

n : int

Dimension of the space, i.e. number of variables.

num_samples : num_samples

Number of samples to be generated.

Returns:

2D numpy.ndarray[float]

A list of n-dimensional points in the unit hypercube.

rbfopt_utils.init_environment(settings)

Initialize the random seed and disable Pyomo output.

Parameters:

settings : rbfopt_settings.RbfoptSettings

Global and algorithmic settings.

rbfopt_utils.initialize_nodes(settings, var_lower, var_upper, integer_vars)

Compute the initial sample points.

Compute an initial list of nodes using the initialization strategy indicated in the algorithmic settings.

Parameters:

settings : rbfopt_settings.RbfoptSettings

Global and algorithmic settings.

var_lower : 1D numpy.ndarray[float]

List of lower bounds of the variables.

var_upper : 1D numpy.ndarray[float]

List of upper bounds of the variables.

integer_vars : 1D numpy.ndarray[int]

A List containing the indices of the integrality constrained variables. If empty, all variables are assumed to be continuous.

Returns:

2D numpy.ndarray[float]

Matrix containing at least n+1 corner points, one for each row, where n is the dimension of the space. The number and position of points depends on the chosen strategy.

Raises:

RuntimeError

If a set of feasible and linearly independent sample points cannot be computed within the prescribed number of iterations.

rbfopt_utils.norm(p)

Compute the L2-norm of a vector

Compute the L2 (Euclidean) norm.

Parameters:

p : 1D numpy.ndarray[float]

The point whose norm should be computed.

Returns:

float

The norm of the point.

rbfopt_utils.results_ready(results)

Check if some asynchronous results completed.

Given a list containing results of asynchronous computations dispatched to a worker pool, verify if some of them are ready for processing.

Parameters:

results : List[(multiprocessing.pool.AsyncResult, any)]

A list of tasks, where each task is a list and the first element is the output of a call to apply_async. The other elements of the list will never be scanned by this function, and they could be anything.

Returns:

bool

True if at least one result has completed.

rbfopt_utils.round_integer_bounds(var_lower, var_upper, integer_vars)

Round the variable bounds to integer values.

Round the values of the integer-constrained variable bounds, in the usual way: lower bounds are rounded up, upper bounds are rounded down.

Parameters:

var_lower : 1D numpy.ndarray[float]

List of lower bounds of the variables.

var_upper : 1D numpy.ndarray[float]

List of upper bounds of the variables.

integer_vars : 1D numpy.ndarray[int]

A list containing the indices of the integrality constrained variables. If empty, all variables are assumed to be continuous.

rbfopt_utils.round_integer_vars(point, integer_vars)

Round a point to the closest integer.

Round the values of the integer-constrained variables to the closest integer value. The values are rounded in-place.

Parameters:

point : 1D numpy.ndarray[float]

The point to be rounded.

integer_vars : 1D numpy.ndarray[int]

A list of indices of integer variables.

rbfopt_utils.transform_domain(settings, var_lower, var_upper, point, reverse=False)

Rescale the domain.

Rescale the function domain according to the chosen strategy.

Parameters:

settings : rbfopt_settings.RbfoptSettings

Global and algorithmic settings.

var_lower : 1D numpy.ndarray[float]

List of lower bounds of the variables.

var_upper : 1D numpy.ndarray[float]

List of upper bounds of the variables.

point : 1D numpy.ndarray[float]

Point in the domain to be rescaled.

reverse : bool

False if we transform from the original domain to the transformed space, True if we want to apply the reverse.

Returns:

1D numpy.ndarray[float]

Rescaled point.

Raises:

ValueError

If the requested rescaling strategy is not implemented.

rbfopt_utils.transform_domain_bounds(settings, var_lower, var_upper)

Rescale the variable bounds.

Rescale the bounds of the function domain according to the chosen strategy.

Parameters:

settings : rbfopt_settings.RbfoptSettings

Global and algorithmic settings.

var_lower : 1D numpy.ndarray[float]

List of lower bounds of the variables.

var_upper : 1D numpy.ndarray[float]

List of upper bounds of the variables.

Returns:

(1D numpy.ndarray[float], 1D numpy.ndarray[float])

Rescaled bounds as (lower, upper).

Raises:

ValueError

If the requested rescaling strategy is not implemented.

rbfopt_utils.transform_function_values(settings, node_val, fmin, fmax, node_err_bounds)

Rescale function values.

Rescale and adjust function values according to the chosen strategy and to the occurrence of large fluctuations (high dynamism). May not rescale at all if rescaling is off.

Parameters:

settings : rbfopt_settings.RbfoptSettings

Global and algorithmic settings.

node_val : 1D numpy.ndarray[float]

List of function values at the interpolation nodes.

fmin : float

Minimum function value found so far.

fmax : float

Maximum function value found so far.

node_err_bounds : 2D numpy.ndarray[float]

The lower and upper variation of the function value for the nodes in node_pos. The variation is assumed 0 for nodes evaluated in accurate mode.

Returns:

(1D numpy.ndarray[float], float, float, 2D numpy.ndarray[float],

Callable[float])

A tuple (scaled_function_values, scaled_fmin, scaled_fmax, scaled_error_bounds, rescale_function) containing a list of rescaled function values, the rescaled minimum, the rescaled maximum, the rescaled error bounds (one node per row), and a callable function to apply the same scaling to further function values if needed.

Raises:

ValueError

If the function scaling strategy requested is not implemented.