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]¶

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:

settings : rbfopt_settings.RbfoptSettings: Global and algorithmic settings.
black_box : rbfopt_black_box.BlackBox: An object derived from class BlackBox, that describes the problem.
init_node_pos : 2D 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_val : 1D 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_strategy : bool: 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_time : float: 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.
n : int: Dimension of the problem.
itercount : int: Iteration number.
evalcount : int: Total number of function evaluations in accurate mode.
noisy_evalcount : int: Total number of function evaluations in noisy mode.
current_step : int: Identifier of the current step within the cyclic optimization strategy counter.
cyclecount : int: Number of cycles.
num_cons_refinement : int: Current number of consecutive refinement steps.
num_stalled_iter : int: Number of consecutive iterations without improvement.
num_noisy_restarts : int: Number of restarts in noisy mode.
discarded_iters : collections.deque: Rolling window to keep track of discarded iterations
do_init_strategy : bool: If True, perform initialization strategy on first cycle.
inf_step : int: Identifier of the InfStep.
local_search_step : int: Identifier of the LocalSearchStep.
refinement_step : int: Identifier of the Step.
cycle_length : int: Length of an optimization cycle.
restoration_step : int: Identifier of the RestorationStep.
first_step : int: Identifier of the first step of an optimization cycle.
two_phase_optimization : bool: Is the fast but noisy objective function is available?
eval_mode : string: Evaluation mode for the objective function at a given stage. Can be either ‘noisy’ or ‘accurate’.
node_pos : 2D 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_val : 1D numpy.ndarray[float]: Objective function value at the points in node_pos. This array only includes points since the last restart.
node_is_noisy : 1D numpy.ndarray[bool]: For each interpolation node in node_pos, was it evaluated in ‘noisy’ mode?
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.
all_node_pos : 2D 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_val : 1D numpy.ndarray[float]: Objective function value at the points in all_node_pos.
all_node_is_noisy : 2D numpy.ndarray[bool]: For each interpolation node in all_node_pos, was it evaluated in ‘noisy’ mode?
all_node_err_bounds : 2D 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_restart : int: Index of the first new node in all_node_pos after the latest restart.
l_lower : 1D numpy.ndarray[float]: Variable lower bounds in the transformed space.
l_upper : 1D numpy.ndarray[float]: Variable upper bounds in the transformed space.
fmin_index : int: Index of the minimum value among the nodes since last restart.
fmin : float: Minimum value among the nodes since last restart.
fmax : float: Maximum value among the nodes since last restart.
fmin_stall_check : float: Best function value at the beginning of the most recent optimization cycle.
fmin_last_refine : float: Best function value at the most recent refinement step.
iter_last_refine : int: Iteration number of the most recent refinement step.
fbest_index : int: Index in all_node_pos of the minimum value among all nodes.
fbest : float: Minimum value among all nodes.
best_gap_shown : float: Best gap shown on the log.
is_fmin_noisy : bool: Was the best known objective function since restart evaluated in noisy mode?
is_fbest_noisy : bool: Was the best known objective function evaluated in noisy mode?
fixed_vars : List[(int, float)]: Indices and values of fixed variables. The indices are with respect to the vector of all variables.
tr_model_set : 1D numpy.ndarray[int]: Indices of nodes (in node_pos) that are used to build the linear model for the trust region refinement phase.
tr_radius : float: Radius of the trust region.
tr_iterate_index : int: Index of the node (in node_pos) that is the current iterate for the trust region 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:	point : 1D numpy.ndarray[float] Coordinates of the node. orig_point : 1D numpy.ndarray[float] The point coordinates in the original space. value : float 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:	point : 1D numpy.ndarray[float] Coordinates of the node. orig_point : 1D numpy.ndarray[float] The point coordinates in the original space. value : float Objective function value of the node err_l : float Lower variation for the error interval of the node. err_u : float 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:	filename : string 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_iters : int 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_iters : int 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_iters : int 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_noisy : bool Is the objective function value to be printed associated with a node evaluated in noisy mode? gap : float Relative distance from the optimum. This will be multiplied by 100 before printing.

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

Perform updates to refinement step and decide if continue.

Update the radius of the trust 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_impr : float Improvement in quadratic model value. real_impr : float Improvement in the real function value. to_replace : int Index in tr_model_set of the point to replace.

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

Perform updates to refinement step and decide if continue.

Update the radius of the trust 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_impr : float Improvement in quadratic model value. real_impr : float Improvement in the real function value. to_replace : int Index in the tr_model_set of the point to replace.

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:	index : int Index of the node to be removed, in the list self.node_pos all_node_shift : int 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_val : float 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)[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:	pool : multiprocessing.Pool() A pool of workers to evaluate the initialization points in parallel. If None, parallel evaluation will not be performed.
Raises:	RuntimeError If the routine does not find enough good initialization points.

restoration_search()[source]¶

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:	filename : string 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_stream : file 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:

tag : string: Iteration id tag, or unique message if at least one of the other arguments are None.
node_is_noisy : bool or None: Is the objective function value to be printed associated with a node evaluated in noisy mode?
obj_value : float or None: Objective function value to print.
gap : float 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, 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:

settings : rbfopt_settings.RbfoptSettings: Global and algorithmic settings.
n : int: The dimension of the problem, i.e. size of the space.
k : int: Number of nodes, i.e. interpolation points.
var_lower : 1D numpy.ndarray[float]: Vector of variable lower bounds.
var_upper : 1D 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.
node_pos : 2D numpy.ndarray[float]: List of coordinates of the nodes.
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 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.
Amatinv : numpy.matrix 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 numpy.matrix of appropriate dimension. Can be None if algorithm is MSRSM.
fmin_index : int: Index of the minimum value among the nodes.
current_step : int: 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.local_step(settings, n, k, var_lower, var_upper, integer_vars, node_pos, rbf_lambda, rbf_h, tfv, Amat, Amatinv, fmin_index, two_phase_optimization, eval_mode, node_is_noisy)[source]¶

Perform local search step, possibly adjusted.

Perform a local search step. This typically accepts the minimum of the RBF model as the next point if it is a viable option; if this is not viable, it will perform an adjusted local search and try to generate a different candidate. It also verifies if it is better to evaluate a brand new point, or re-evaluate a previously known point. The test is based on bumpiness of the resulting interpolant.

Parameters:

settings : rbfopt_settings.RbfoptSettings: Global and algorithmic settings.
n : int: The dimension of the problem, i.e. size of the space.
k : int: Number of nodes, i.e. interpolation points.
var_lower : 1D numpy.ndarray[float]: Vector of variable lower bounds.
var_upper : 1D 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.
node_pos : 2D numpy.ndarray[float]: List of coordinates of the nodes.
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 the polynomial. List of dimension n+1.
tfv : (1D numpy.ndarray[float], float, float, 2D numpy.ndarray[float]): Transformed function values: scaled node values, scaled minimum, scaled maximum, scaled node error bounds.
Amat : numpy.matrix: RBF matrix, i.e. [Phi P; P^T 0].
Amatinv : numpy.matrix or None: Inverse of the RBF matrix, i.e. [Phi P; P^T 0]^{-1}. Can be None if the algorithm is MSRSM.
fmin_index : int: Index of the minimum value among the nodes.
two_phase_optimization : bool: Is the noisy but fast objective function is available?
eval_mode : string: Evaluation mode for the objective function at a given stage. Can be either ‘noisy’ or ‘accurate’.
node_is_noisy : List[bool]: For each interpolation node in node_pos, was it evaluated in ‘noisy’ mode?

Returns:

(bool, 1D numpy.ndarray[float] or None, int or None): A triple (adjusted, point, index) where adjusted is True if the local search was adjusted rather than a pure local search, point is the point to be evaluated next (or None if errors occurred), and index is the index that this point should replace, or None if the point should be appended.