rbfopt_refinement module

Routines for trust-region based local search.

This module contains all functions that are necessary to implement a trust-region based 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, tr_radius)

Compute the next candidate point of the trust region method.

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 trust region.

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.

var_lower : 1D numpy.ndarray[float]

Vector of variable lower bounds.

var_upper : 1D numpy.ndarray[float]

Vector of variable upper bounds.

h : 1D numpy.ndarray[float]

Linear coefficients of the quadratic model.

start_point : 1D numpy.ndarray[float]

Starting point for the descent.

tr_radius : float

Radius of the trust region.

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, tr_radius, candidate, integer_vars)

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 quadratic model.

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.

h : 1D numpy.ndarray[float]

Linear coefficients of the model.

start_point : 1D numpy.ndarray[float]

Starting point for the descent.

tr_radius : float

Radius of the trust region.

candidate : 1D numpy.ndarray[float]

Fractional point to being the search.

integer_vars : 1D numpy.ndarray[int]

Indices of the integer 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)

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:

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.

node_val : 1D numpy.ndarray[float]

List of values of the function at the nodes.

model_set : 1D 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, tr_radius, integer_vars)

Compute a point to improve the model used in the trust region.

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

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.

var_lower : 1D numpy.ndarray[float]

Vector of variable lower bounds.

var_upper : 1D numpy.ndarray[float]

Vector of variable upper bounds.

node_pos : 2D numpy.ndarray[float]

List of coordinates of the nodes.

model_set : 1D numpy.ndarray[int]

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

start_point_index : int

Index in node_pos of the starting point for the descent.

tr_radius : float

Radius of the trust region.

integer_vars : 1D numpy.ndarray[int]

Indices of the integer 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_trust_region(settings, n, k, node_pos, center)

Initialize the trust region.

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

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.

center : 1D numpy.ndarray[float]

Node that acts as a center for the quadratic model.

Returns:

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

Indices in node_pos of points to build the model, and initial radius of the trust region.

Raises:

numpy.linalg.LinAlgError

If the matrix cannot be computed for numerical reasons.

rbfopt_refinement.update_trust_region_radius(settings, tr_radius, model_obj_diff, real_obj_diff)

Update the radius of the trust region.

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

Parameters:

settings : rbfopt_settings.RbfoptSettings.

Global and algorithmic settings.

tr_radius : float

Current radius of the trust region.

model_obj_diff : float

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

real_obj_diff : float

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

Returns:

(float, bool)

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