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_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.
- settings :
-
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.
- settings :
-
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.
- settings :
-
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],
List[(int, float)])
A triple or list with three elements (black_box, point, fixed_vars) containing an object derived from class RbfoptBlackBox, that describes the problem, the point at which we want to apply the evaluate() method, 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.array[float],
List[(int, float)])
A triple or list with three elements (black_box, point, fixed_vars) containing an object derived from class RbfoptBlackBox, that describes the problem, the point at which we want to apply the evaluate() method, 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, node_pos, mat)[source]¶ Perform the pure global search step.
Parameters: - mat : numpy.matrix
The matrix necessary for the computation. This is the inverse of the matrix [Phi P; P^T 0]. Must be a square numpy.matrix of appropriate dimension.
- 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 : List[List[float]]
List of coordinates of the nodes
- mat : numpy.matrix
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 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, node_pos, tfv, h, b, rank_deficient, model_set, start_point_index, tr_radius)[source]¶ Perform a refinement step.
Perform a refinement step to locally improve the solution.
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.
- h : 1D numpy.ndarray[float]
Linear coefficients of the quadratic model.
- b : float
Constant term of the quadratic model.
- rank_deficient : bool
True if the points used to build the linear model do not span the space.
- 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.
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.
- settings :