rbfopt_algorithm module

Main optimization algorithm.

This module contains a class that implements the main optimization algorithm. The class has a state so that optimization can be stopped and resumed at any time.

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

class rbfopt_algorithm.RbfoptAlgorithm(settings, black_box, init_node_pos=None, init_node_val=None, do_init_strategy=True)[source]

Bases: object

Optimization algorithm.

Implements the main optimization algorithm, and contains all its state variables so that the algorithm can be warm-started from a given state. Some of the logic of the algorithm is not inside this class, because it can be run in parallel and therefore should not modify the state.

Parameters
settingsrbfopt_settings.RbfoptSettings

Global and algorithmic settings.

black_boxrbfopt_black_box.RbfoptBlackBox

An object derived from class RbfoptBlackBox, that describes the problem.

init_node_pos2D numpy.ndarray[float] or None

Coordinates of points at which the function value is known. These points will be added to the points generated by the algorithm. If None, all the initial points will be generated by the algorithm.

init_node_val1D numpy.ndarray[float] or None

Function values corresponding to the points given in init_node_pos. Should be None if the previous argument is None. If init_node_pos is not None but init_node_val is None, the points in init_node_pos will be evaluated in the initialization phase of the algorithm.

do_init_strategybool

Perform initialization strategy. If True, the algorithm will generate an initial set of points on top of any user-provided points. If False, we will rely on user-provided points only. Notice that the algorithm may fail if not enough points are provided, and do_init_strategy is False. Default True.

Attributes
elapsed_timefloat

Elapsed CPU time up to the point where state was last saved.

best_local_rbf(string, float)

Best RBF type to construct model for local search, and the corresponding shape parameter.

best_global_rbf(string, float)

Best RBF type to construct model for global search, and the corresponding shape parameter.

nint

Dimension of the problem.

itercountint

Iteration number.

evalcountint

Total number of function evaluations in accurate mode.

noisy_evalcountint

Total number of function evaluations in noisy mode.

current_stepint

Identifier of the current step within the cyclic optimization strategy counter.

cyclecountint

Number of cycles.

num_cons_refinementint

Current number of consecutive refinement steps.

num_stalled_iterint

Number of consecutive iterations without improvement.

num_noisy_restartsint

Number of restarts in noisy mode.

discarded_iterscollections.deque

Rolling window to keep track of discarded iterations

do_init_strategybool

If True, perform initialization strategy on first cycle.

inf_stepint

Identifier of the InfStep.

local_search_stepint

Identifier of the LocalSearchStep.

refinement_stepint

Identifier of the Step.

cycle_lengthint

Length of an optimization cycle.

restoration_stepint

Identifier of the RestorationStep.

first_stepint

Identifier of the first step of an optimization cycle.

two_phase_optimizationbool

Is the fast but noisy objective function is available?

eval_modestring

Evaluation mode for the objective function at a given stage. Can be either ‘noisy’ or ‘accurate’.

node_pos2D numpy.ndarray[float]

Coordinates of the interpolation nodes (i.e. the points where the objective function has already been evaluated). The coordinates may be in the transformed space. This matrix only includes points since the last restart.

node_val1D numpy.ndarray[float]

Objective function value at the points in node_pos. This array only includes points since the last restart.

node_is_noisy1D numpy.ndarray[bool]

For each interpolation node in node_pos, was it evaluated in ‘noisy’ mode?

node_err_bounds2D 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.

all_node_pos2D numpy.ndarray[float]

Coordinates of the interpolation nodes. This matrix contains all evaluated points in the original space, and is persistent across restarts.

all_node_val1D numpy.ndarray[float]

Objective function value at the points in all_node_pos.

all_node_is_noisy2D numpy.ndarray[bool]

For each interpolation node in all_node_pos, was it evaluated in ‘noisy’ mode?

all_node_err_bounds2D numpy.ndarray[float]

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

num_nodes_at_restartint

Index of the first new node in all_node_pos after the latest restart.

l_lower1D numpy.ndarray[float]

Variable lower bounds in the transformed space.

l_upper1D numpy.ndarray[float]

Variable upper bounds in the transformed space.

fmin_indexint

Index of the minimum value among the nodes since last restart.

fminfloat

Minimum value among the nodes since last restart.

fmaxfloat

Maximum value among the nodes since last restart.

fmin_stall_checkfloat

Best function value at the beginning of the most recent optimization cycle.

fmin_last_refinefloat

Best function value at the most recent refinement step.

iter_last_refineint

Iteration number of the most recent refinement step.

fbest_indexint

Index in all_node_pos of the minimum value among all nodes.

fbestfloat

Minimum value among all nodes.

best_gap_shownfloat

Best gap shown on the log.

is_fmin_noisybool

Was the best known objective function since restart evaluated in noisy mode?

is_fbest_noisybool

Was the best known objective function evaluated in noisy mode?

fixed_varsList[(int, float)]

Indices and values of fixed variables. The indices are with respect to the vector of all variables.

ref_model_set1D numpy.ndarray[int]

Indices of nodes (in node_pos) that are used to build the linear model for the refinement phase.

ref_radiusfloat

Radius of the refinement region.

ref_iterate_indexint

Index of the node (in node_pos) that is the current iterate for the refinement method.

add_node(point, orig_point, value)[source]

Add a node to the all relevant data structures.

Given the data corresponding to a node, add it to all relevant places: the list of current nodes, the list of all nodes. Also, update function minimum and maximum.

Parameters
point1D numpy.ndarray[float]

Coordinates of the node.

orig_point1D numpy.ndarray[float]

The point coordinates in the original space.

valuefloat

Objective function value of the node

add_noisy_node(point, orig_point, value, err_l, err_u)[source]

Add a noisy node to the all relevant data structures.

Given the data corresponding to a node, add it to all relevant places: the list of current nodes, the list of all nodes. Also, update function minimum and maximum.

Parameters
point1D numpy.ndarray[float]

Coordinates of the node.

orig_point1D numpy.ndarray[float]

The point coordinates in the original space.

valuefloat

Objective function value of the node

err_lfloat

Lower variation for the error interval of the node.

err_ufloat

Upper variation for the error interval of the node

advance_step_counter()[source]

Advance the step counter of the optimization algorithm.

Advance the step counter of the optimization algorithm, and update cycle number.

classmethod load_from_file(filename)[source]

Load object from file, with its state.

Read the current state from file, and return an object of this class. The optimization can be resumed immediately. This function will attempt to set the random number generators to the state they were in. Note that the output stream is set to stdout, regardless of the output stream when the state was saved, so the caller may have to set the desired output stream.

Parameters
filenamestring

Name of the file from which the state will be read.

Returns
RbfoptAlgorithm

An object of this class.

optimize(pause_after_iters=9223372036854775807)[source]

Optimize a black-box function.

Optimize an unknown function over a box using an RBF-based algorithm. This function will select the serial or parallel version of the optimizer, depending on settings.

Parameters
pause_after_itersint

Number of iterations after which the optimization process should pause. This allows the user to do other activities and resume optimization at a later time. Default sys.maxsize, which is larger than any practical integer.

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

A quintuple (value, point, itercount, evalcount, noisy_evalcount) containing the objective function value of the best solution found, the corresponding value of the decision variables, the number of iterations of the algorithm, the total number of function evaluations, and the number of these evaluations that were performed in ‘noisy’ mode.

optimize_parallel(pause_after_iters=9223372036854775807)[source]

Optimize a black-box function using parallel evaluations.

Optimize an unknown function over a box using an RBF-based algorithm, using as many CPUs as requested.

Parameters
pause_after_itersint

Number of iterations after which the optimization process should pause. This allows the user to do other activities and resume optimization at a later time. Default sys.maxsize, which is larger than any practical integer.

optimize_serial(pause_after_iters=9223372036854775807)[source]

Optimize a black-box function. Serial engine.

Optimize an unknown function over a box using an RBF-based algorithm. This is the serial version of the optimization routine.

Parameters
pause_after_itersint

Number of iterations after which the optimization process should pause. Default sys.maxsize.

phase_update()[source]

Check if we should switch phase in two-phase optimization.

Check if we should switch to the second phase of two-phase optimization. The conditions for switching are: 1) Optimization in noisy mode restarted too many times. 2) We reached the limit of noisy mode iterations. If both are met, the switch is performed.

print_init_line()[source]

Print first line of the output, with headers.

print_summary_line(node_is_noisy, gap)[source]

Print summary line of the algorithm.

Parameters
node_is_noisybool

Is the objective function value to be printed associated with a node evaluated in noisy mode?

gapfloat

Relative distance from the optimum. This will be multiplied by 100 before printing.

refinement_update(model_impr, real_impr, to_replace, rank_deficient)[source]

Perform updates to refinement step and decide if continue.

Update the radius of the refinement region and the iterate for the refinement step. Also, decide if the next step should be another refinement step, or if we should go back to global search.

Parameters
model_imprfloat

Improvement in linear model value.

real_imprfloat

Improvement in the real function value.

to_replaceint

Index in ref_model_set of the point to replace.

rank_deficientbool

True if the points used to build the linear model do not span the space.

refinement_update_parallel(model_impr, real_impr, to_replace, rank_deficient)[source]

Perform updates to refinement step and decide if continue.

Update the radius of the refinement region and the iterate for the refinement step. This is the version that should be used for parallel computation, because the update phase is different.

Parameters
model_imprfloat

Improvement in quadratic model value.

real_imprfloat

Improvement in the real function value.

to_replaceint

Index in the ref_model_set of the point to replace.

rank_deficientbool

True if the points used to build the linear model do not span the space.

remove_existing_nodes(node_pos)[source]

Remove from an array all previously evaluated points.

Check the all_node_ data structures to eliminate from node_pos every point that is already present in the data structures. Return a purged array of nodes, as well as lists with data for all points that were removed.

Parameters
settingsrbfopt_settings.RbfoptSettings.

Global and algorithmic settings.

node_pos2D numpy.ndarray[float]

List of coordinates of the nodes from which we will purge.

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

An updated 2D array of points (where all existing ones have been eliminated), the number of eliminated points, the list of eliminated points, the list of their values, the list of their is_noisy value, the list of their error bounds.

remove_node(index, all_node_shift=0)[source]

Remove a node from the lists of interpolation nodes.

Given the index of a node, remove its references from all relevant places.

Parameters
indexint

Index of the node to be removed, in the list self.node_pos

all_node_shiftint

A shift that has to be applied to the index to find the corresponding node in self.all_node_pos. Typically, this is the size of self.all_node_pos at the latest restart.

require_accurate_evaluation(noisy_val)[source]

Check if a given noisy value qualifies for accurate evaluation.

Verify if a point with the given objective function value in noisy mode qualifies for an immediate accurate re-evaluation.

Parameters
noisy_valfloat

Value of the point to be tested, in noisy mode.

Returns
bool

True if the point should be re-evaluated in accurate mode immediately.

restart(pool=None, remaining_eval=None)[source]

Perform a complete restart of the optimization.

Restart the optimization algorithm, i.e. discard the current RBF model, and select new sample points to start the algorithm from scratch. Previous point evaluations are ignored, but they are still recorded in the appropriate arrays.

Parameters
poolmultiprocessing.Pool()

A pool of workers to evaluate the initialization points in parallel. If None, parallel evaluation will not be performed.

remaining_evallist()

A list to which any outstanding initialization point evaluation is appended. If None, these evaluations will be discarded.

Raises
RuntimeError

If the routine does not find enough good initialization points.

Perform restoration step to repair RBF matrix.

Try to repair an ill-conditioned RBF matrix by selecting points far enough from current interpolation nodes, until numerical stability is restored.

Returns
1D numpy.ndarray[float] or None

The next point to be evaluated, or None if it cannot be found.

save_to_file(filename)[source]

Save object on file, with its state.

Saves the current state of the algorithm on file. The optimization can be subsequently resumed reading the state from file. This function will also attempt to save the state of the random number generators so that if resumed on the same machine, the optimization process is identical to an uninterrupted process.

Parameters
filenamestring

Name of the file that the state will be saved to.

set_output_stream(output_stream)[source]

Set output stream for the log.

Parameters
output_streamfile

Stream to be used for output. Must have a ‘write’ and a ‘flush’ method.

stalling_update()[source]

Check if the algorithm is stalling.

Check if the algorithm is stalling, and perform the corresponding updates.

unlimited_refinement_active()[source]

Should the usual limits of refinement phase be ignored?

Verify if, based on the unlimited_refinement_thresh parameter, the usual limitations on the refinement phase should be ignored.

Returns
bool

True if unlimited refinement is active, False otherwise.

update_log(tag, node_is_noisy=None, obj_value=None, gap=None)[source]

Print a single line in the log.

Update the program’s log, writing information about an iteration of the optimization algorithm, or a special message.

Parameters
tagstring

Iteration id tag, or unique message if at least one of the other arguments are None.

node_is_noisybool or None

Is the objective function value to be printed associated with a node evaluated in noisy mode?

obj_valuefloat or None

Objective function value to print.

gapfloat or None

Relative distance from the optimum. This will be multiplied by 100 before printing.

rbfopt_algorithm.global_step(settings, n, k, var_lower, var_upper, integer_vars, categorical_info, node_pos, rbf_lambda, rbf_h, tfv, Amatinv, fmin_index, current_step)[source]

Perform global search step.

Perform a global search step, with a different methodology depending on the algorithm chosen.

Parameters
settingsrbfopt_settings.RbfoptSettings

Global and algorithmic settings.

nint

The dimension of the problem, i.e. size of the space.

kint

Number of nodes, i.e. interpolation points.

var_lower1D numpy.ndarray[float]

Vector of variable lower bounds.

var_upper1D numpy.ndarray[float]

Vector of variable upper bounds.

integer_vars: 1D numpy.ndarray[int]

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

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

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

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).

node_pos2D numpy.ndarray[float]

List of coordinates of the nodes.

rbf_lambda1D numpy.ndarray[float]

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

rbf_h1D numpy.ndarray[float]

The h coefficients of the RBF interpolant, corresponding to the polynomial. List of dimension n+1.

tfv(List[float], float, float, List[(float, float)])

Transformed function values: scaled node values, scaled minimum, scaled maximum, and node error bounds.

Amatinv2D numpy.ndarray[float] or None

The matrix necessary for the computation. This is the inverse of the matrix [Phi P; P^T 0], see paper as cited above. Must be a square 2D numpy.ndarray[float] of appropriate dimension. Can be None if algorithm is MSRSM.

fmin_indexint

Index of the minimum value among the nodes.

current_stepint

Identifier of the current step within the cyclic optimization strategy counter.

Returns
1D numpy.ndarray[float] or None

The point to be evaluated next, or None if errors occurred.

rbfopt_algorithm.objfun(data)[source]

Call the evaluate() method of a RbfoptBlackBox object.

Apply the evaluate() method of the given RbfoptBlackBox object to the given point. This way of calling the method indirectly is necessary for parallelization.

Parameters
data(rbfopt_black_box.RbfoptBlackBox, 1D numpy.ndarray[float],
(1D numpy.ndarray[int], 1D numpy.ndarray[int],

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

List[(int, float)])

A quadruple or list with four elements (black_box, point, categorical_info, fixed_vars) containing an object derived from class RbfoptBlackBox, that describes the problem, the point at which we want to apply the evaluate() method, information on categorical variables, and a list of fixed variables given as pairs (index, value).

Returns
float

The value of the function evaluate() at the point.

rbfopt_algorithm.objfun_noisy(data)[source]

Call the evaluate_noisy() method of a RbfoptBlackBox object.

Apply the evaluate_noisy() method of the given RbfoptBlackBox object to the given point. This way of calling the method indirectly is necessary for parallelization.

Parameters
data(rbfopt_black_box.RbfoptBlackBox, 1D numpy.ndarray[float],
(1D numpy.ndarray[int], 1D numpy.ndarray[int],

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

List[(int, float)])

A quadruple or list with four elements (black_box, point, categorical_info, fixed_vars) containing an object derived from class RbfoptBlackBox, that describes the problem, the point at which we want to apply the evaluate() method, information on categorical variables, and a list of fixed variables given as pairs (index, value).

Returns
(float, float, float)

The value of the function evaluate_noisy() at the point, and the possible variation given as lower and upper variation.

rbfopt_algorithm.pure_global_step(settings, n, k, var_lower, var_upper, integer_vars, categorical_info, node_pos, mat)[source]

Perform the pure global search step.

Parameters
mat2D numpy.ndarray[float]

The matrix necessary for the computation. This is the inverse of the matrix [Phi P; P^T 0]. Must be a square 2D numpy.ndarray[float] of appropriate dimension.

settingsrbfopt_settings.RbfoptSettings

Global and algorithmic settings.

nint

The dimension of the problem, i.e. size of the space.

kint

Number of nodes, i.e. interpolation points.

var_lower1D numpy.ndarray[float]

Vector of variable lower bounds.

var_upper1D numpy.ndarray[float]

Vector of variable upper bounds.

integer_vars1D numpy.ndarray[int]

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

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

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

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).

node_posList[List[float]]

List of coordinates of the nodes

mat2D numpy.ndarray[float]

The matrix necessary for the computation. This is the inverse of the matrix [Phi P; P^T 0], see paper as cited above. Must be a square 2D numpy.ndarray[float] of appropriate dimension. Can be None when using the MSRSM algorithm.

Returns
List[float] or None

The point to be evaluated next, or None if errors occurred.

rbfopt_algorithm.refinement_step(settings, n, k, var_lower, var_upper, integer_vars, categorical_info, node_pos, tfv, h, b, rank_deficient, model_set, start_point_index, ref_radius)[source]

Perform a refinement step.

Perform a refinement step to locally improve the solution.

Parameters
settingsrbfopt_settings.RbfoptSettings

Global and algorithmic settings.

nint

The dimension of the problem, i.e. size of the space.

kint

Number of nodes, i.e. interpolation points.

var_lower1D numpy.ndarray[float]

Vector of variable lower bounds.

var_upper1D numpy.ndarray[float]

Vector of variable upper bounds.

integer_vars: 1D numpy.ndarray[int]

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

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

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

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).

node_pos2D numpy.ndarray[float]

List of coordinates of the nodes.

h1D numpy.ndarray[float]

Linear coefficients of the quadratic model.

bfloat

Constant term of the quadratic model.

rank_deficientbool

True if the points used to build the linear model do not span the space.

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

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

Next candidate point for the search, the corresponding model value difference, and the index in model_set of the point to replace.