rbfopt_refinement module

Routines for a local search to refine the solution.

This module contains all functions that are necessary to implement a local search to refine the solution quality. The local search exploits a linear model of the objective function.

Licensed under Revised BSD license, see LICENSE. (C) Copyright International Business Machines Corporation 2017.

rbfopt_refinement.get_candidate_point(settings, n, k, var_lower, var_upper, h, start_point, ref_radius)[source]

Compute the next candidate point of the refinement.

Starting from a given point, compute a descent direction and move in that direction to find the point with lowest value of the linear model, within the radius of the local search.

Parameters
settingsrbfopt_settings.RbfoptSettings.

Global and algorithmic settings.

nint

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

kint

Number of interpolation nodes.

var_lower1D numpy.ndarray[float]

Vector of variable lower bounds.

var_upper1D numpy.ndarray[float]

Vector of variable upper bounds.

h1D numpy.ndarray[float]

Linear coefficients of the linear model.

start_point1D numpy.ndarray[float]

Starting point for the descent.

ref_radiusfloat

Radius of the local search.

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

Next candidate point for the search, the corresponding model value difference, and the norm of the gradient at the current point.

rbfopt_refinement.get_integer_candidate(settings, n, k, h, start_point, ref_radius, candidate, integer_vars, categorical_info)[source]

Get integer candidate point from a fractional point.

Look for integer points around the given fractional point, trying to find one with a good value of the linear model.

Parameters
settingsrbfopt_settings.RbfoptSettings.

Global and algorithmic settings.

nint

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

kint

Number of interpolation nodes.

h1D numpy.ndarray[float]

Linear coefficients of the model.

start_point1D numpy.ndarray[float]

Starting point for the descent.

ref_radiusfloat

Radius of the local search.

candidate1D numpy.ndarray[float]

Fractional point to being the search.

integer_vars1D numpy.ndarray[int]

Indices of the integer variables.

categorical_info(1D numpy.ndarray[int], 1D numpy.ndarray[int],

List[(int, 1D numpy.ndarray[int])]) or None

Information on categorical variables: array of indices of categorical variables in original space, array of indices of noncategorical variables in original space, and expansion of each categorical variable, given as a tuple (original index, indices of expanded variables).

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

Next candidate point for the search, and the corresponding change in model value compared to the given point.

rbfopt_refinement.get_linear_model(settings, n, k, node_pos, node_val, model_set)[source]

Compute a linear model of the function.

Determine a linear model h^T x + b of the objective function in an area that is centered on the given node. The model is computed by solving a (not necessarily square) linear system, inducing sparsity.

Parameters
settingsrbfopt_settings.RbfoptSettings.

Global and algorithmic settings.

nint

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

kint

Number of interpolation nodes.

node_pos2D numpy.ndarray[float]

List of coordinates of the nodes.

node_val1D numpy.ndarray[float]

List of values of the function at the nodes.

model_set1D numpy.ndarray[int]

Indices of points in node_pos to be used to compute model.

Returns
1D numpy.ndarray[float], float, bool

Coefficients of the linear model h, b, and a boolean indicating if the linear model is underdetermined.

Raises
numpy.linalg.LinAlgError

If the matrix cannot be computed for numerical reasons.

rbfopt_refinement.get_model_improving_point(settings, n, k, var_lower, var_upper, node_pos, model_set, start_point_index, ref_radius, integer_vars, categorical_info)[source]

Compute a point to improve the model used in refinement.

Determine a point that improves the geometry of the set of points used to build the local search model. This point may not have a good objective function value, but it ensures that the model is well behaved.

Parameters
settingsrbfopt_settings.RbfoptSettings.

Global and algorithmic settings.

nint

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

kint

Number of interpolation nodes.

var_lower1D numpy.ndarray[float]

Vector of variable lower bounds.

var_upper1D numpy.ndarray[float]

Vector of variable upper bounds.

node_pos2D numpy.ndarray[float]

List of coordinates of the nodes.

model_set1D numpy.ndarray[int]

Indices of points in node_pos to be used to compute model.

start_point_indexint

Index in node_pos of the starting point for the descent.

ref_radiusfloat

Radius of the local search.

integer_vars1D numpy.ndarray[int]

Indices of the integer variables.

categorical_info(1D numpy.ndarray[int], 1D numpy.ndarray[int],

List[(int, 1D numpy.ndarray[int])]) or None

Information on categorical variables: array of indices of categorical variables in original space, array of indices of noncategorical variables in original space, and expansion of each categorical variable, given as a tuple (original index, indices of expanded variables).

Returns
(1D numpy.ndarray[float], bool, int)

Next candidate point to improve the model, a boolean indicating success, and the index of the point to replace if successful.

rbfopt_refinement.init_refinement(settings, n, k, node_pos, center)[source]

Initialize the local search model.

Determine which nodes should be used to create a linear model of the objective function, and determine the initial radius of the search.

Parameters
settingsrbfopt_settings.RbfoptSettings.

Global and algorithmic settings.

nint

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

kint

Number of interpolation nodes.

node_pos2D numpy.ndarray[float]

List of coordinates of the nodes.

center1D numpy.ndarray[float]

Node that acts as a center for the linear model.

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

Indices in node_pos of points to build the model, and initial radius of the local search.

Raises
numpy.linalg.LinAlgError

If the matrix cannot be computed for numerical reasons.

rbfopt_refinement.round_categorical(point, categorical, not_categorical, categorical_expansion)[source]

Round categorical variables of a fractional point.

Ensure categorical variables of fractional point are correctly rounded. Rounding is done in-place.

Parameters
points1D numpy.ndarray[float]

Point we want to round.

categorical1D numpy.ndarray[int]

Array of indices of categorical variables in original space.

not_categorical1D numpy.ndarray[int]

Array of indices of not categorical variables in original space.

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

Expansion of original categorical variables into binaries.

rbfopt_refinement.update_refinement_radius(settings, ref_radius, model_obj_diff, real_obj_diff)[source]

Update the radius fo refinement.

Compute the updated refinement radius based on the true objective function difference between the old point and the new point, and that of the linear model. Also, determine if the new iterate should be accepted.

Parameters
settingsrbfopt_settings.RbfoptSettings.

Global and algorithmic settings.

ref_radiusfloat

Current radius of the refinement region.

model_obj_difffloat

Difference in objective function value of the new point and the previous point, according to the linear model.

real_obj_difffloat

Difference in the real objective function value of the new point and the previous point.

Returns
(float, bool)

Updated radius of refinement, and whether the point should be accepted.