rbfopt_aux_problems module¶

Auxiliary problems for the optimization process.

This module is responsible for constructing and solving all the auxiliary problems encountered during the optimization, such as the minimization of the surrogate model, of the bumpiness. The module acts as an interface between the high-level routines, the low-level PyOmo modules, and the search algorithms.

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

class rbfopt_aux_problems.GutmannHkObj(settings, n, k, node_pos, rbf_lambda, rbf_h, Amatinv, target_val)[source]¶

Objective function h_k for the Gutmann method.

This class computes the value of the h_k objective function for the Gutmann method. Lower values are better.

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.
node_pos : 2D numpy.ndarray[float]: List of coordinates of the nodes (one for each row).
rbf_lambda : 1D numpy.ndarray[float]: The lambda coefficients of the RBF interpolant, corresponding to the radial basis functions. List of dimension k. Can be None if dist_weight is equal to 1, in which case RBF values are not used.
rbf_h : 1D numpy.ndarray[float]: The h coefficients of the RBF interpolant, corresponding to the polynomial. List of dimension n+1. Can be None if dist_weight is equal to 1, in which case RBF values are not used.
Amatinv : 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.
target_val : float: Value f* that we want to find in the unknown objective function. Used by Gutmann’s RBF method only.

evaluate(points)[source]¶

Evaluate the objective for the Gutmann h_k objective.

Compute -1/(mu_k(x) [s_k(x) - f^st]^2)), where s_k is the value of the RBF interpolant, and f^st is the target value. This is because we want to maximize its negative.

Parameters:	points : 2D numpy.ndarray[float] Points at which we want to evaluate the objective function (one for each row).
Returns:	float The score for the h_k criterion (lower is better).

class rbfopt_aux_problems.GutmannMukObj(settings, n, k, node_pos, Amatinv)[source]¶

Objective function mu_k for the Gutmann method.

This class computes the value of the mu_k objective function for the Gutmann method. Lower values are better.

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.
node_pos : 2D numpy.ndarray[float]: List of coordinates of the nodes (one for each row).
Amatinv : numpy.matrix or None: 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.

evaluate(points)[source]¶

Evaluate the objective for the Gutmann mu objective.

Compute -1/mu_k(x), which we want to minimize.

Parameters:	points : 2D numpy.ndarray[float] Points at which we want to evaluate the objective function (one for each row).
Returns:	float The score for the mu_k criterion (lower is better).

class rbfopt_aux_problems.MaximinDistanceObj(settings, n, k, node_pos)[source]¶

Objective function for the Maximin Distance criterion.

This class facilitates the computation of the objective function for the Maximin Distance criterion. The objective function is the minimum distance from the closest point, multiplied by -1 so that lower values are better (we always minimize).

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. node_pos : 2D numpy.ndarray[float] List of coordinates of the nodes (one for each row).

evaluate(points)[source]¶

Evaluate the objective for Maximin Distance.

Evaluate the score of a set of points.

Parameters:	points : 2D numpy.ndarray[float] Points at which we want to evaluate the objective function (one for each row).
Returns:	float The score for Maximin Distance algorithm (lower is better).

class rbfopt_aux_problems.MetricSRSMObj(settings, n, k, node_pos, rbf_lambda, rbf_h, dist_weight)[source]¶

Objective function for the Metric SRM method.

This class facilitates the computation of the objective function for the Metric SRSM. The objective function combines the distance from the closest point, and the response surface (i.e. RBF interpolant) value. Lower values are better.

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.
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. Can be None if dist_weight is equal to 1, in which case RBF values are not used.
rbf_h : 1D numpy.ndarray[float]: The h coefficients of the RBF interpolant, corresponding to the polynomial. List of dimension n+1. Can be None if dist_weight is equal to 1, in which case RBF values are not used.
dist_weight : float: Relative weight of the distance and objective function value. A weight of 1.0 corresponds to using solely distance, 0.0 to objective function.

evaluate(points)[source]¶

Evaluate the objective for Metric SRSM.

Evaluate the score of a set of points.

Parameters:	points : 2D numpy.ndarray[float] Points at which we want to evaluate the objective function (one for each row).
Returns:	float The score for the Metric SRSM algorithm (lower is better).

rbfopt_aux_problems.ga_mate(father, mother)[source]¶

Generate offspring for genetic algorithm.

The offspring will get genes uniformly at random from the mother and the father.

Parameters:	father : 2D numpy.ndarray[float] First set of individuals for mating. mother : 2D numpy.ndarray[float] Second set of individuals for mating.
Returns:	2D numpy.ndarray(float) The offspring. Same size as mother and father.

rbfopt_aux_problems.ga_mutate(n, var_lower, var_upper, is_integer, individual, max_size_pert)[source]¶

Mutate an individual (point) for the genetic algorithm.

The mutation is performed in place.

Parameters:

n : int: The dimension of the problem, i.e. size of the space.
var_lower : 1D numpy.ndarray[float]: Vector of variable lower bounds.
var_upper : 1D numpy.ndarray[float]: Vector of variable upper bounds.
is_integer : 1D numpy.ndarray[bool]: List of size n, each element is True if the corresponding variable is integer.
individual : 1D numpy.ndarray[float]: Point to be mutated.
max_size_pert : int: Maximum size of the perturbation for the mutation, i.e. maximum number of coordinates that can change.

rbfopt_aux_problems.ga_optimize(settings, n, var_lower, var_upper, integer_vars, objfun)[source]¶

Compute and optimize a fitness function.

Use a simple genetic algorithm to quickly find a good solution for a minimization subproblem.

Parameters:

settings : rbfopt_settings.RbfoptSettings: Global and algorithmic settings.
n : int: The dimension of the problem, i.e. size of the space.
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.
objfun : Callable[2D numpy.ndarray[float]]: The objective function. This must be a callable function that can be applied to a list of points, and must return a list containing one fitness vale for each point, such that lower values are better.

Returns:

1D numpy.ndarray[float]: The best solution found.

rbfopt_aux_problems.generate_sample_points(settings, n, var_lower, var_upper, integer_vars, num_samples)[source]¶

Generate sample points uniformly at random.

Generate a given number of points uniformly at random in the bounding box, ensuring that integer variables take on integer values.

Parameters:

settings : rbfopt_settings.RbfoptSettings: Global and algorithmic settings.
n : int: The dimension of the problem, i.e. size of the space.
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.
num_samples : int: Number of samples to generate

Returns:

2D numpy.ndarray[float]: A list of sample points (one for each row).

rbfopt_aux_problems.get_bump_new_node(settings, n, k, node_pos, node_val, new_node, node_err_bounds, target_val)[source]¶

Compute the bumpiness with a new interpolation point.

Computes the bumpiness of the interpolant obtained by setting a new node in a specified location, at value target_val.

Parameters:

settings : rbfopt_settings.RbfoptSettings: Global and algorithmic settings.
n : int: Dimension of the problem, i.e. the space where the point lives.
k : int: Number of nodes, i.e. interpolation points.
node_pos : 2D numpy.ndarray[float]: Location of current interpolation nodes.
node_val : 1D numpy.ndarray[float]: List of values of the function at the nodes.
new_node : 1D numpy.ndarray[float]: Location of new interpolation node.
node_err_bounds : 2D numpy.ndarray[float]: Allowed deviation from node values for nodes affected by error. This is a matrix with rows (lower_deviation, upper_deviation).
target_val : float: Target function value at which we want to move the node.

Returns:

float: The bumpiness of the interpolant having a new node at the specified location, with value target_val.

rbfopt_aux_problems.get_min_bump_node(settings, n, k, Amat, node_val, node_err_bounds, target_val)[source]¶

Compute the bumpiness obtained by moving an interpolation point.

Compute the bumpiness of the interpolant obtained by moving a single node (the one that yields minimum bumpiness, which is determined by this function) within target_val plus or minus error, to target_val.

Parameters:

settings : rbfopt_settings.RbfoptSettings: Global and algorithmic settings.
n : int: Dimension of the problem, i.e. the space where the point lives.
k : int: Number of nodes, i.e. interpolation points.
Amat : numpy.matrix: The matrix A = [Phi P; P^T 0] of equation (3) in the paper by Costa and Nannicini.
node_val : 1D numpy.ndarray[float]: List of values of the function at the nodes.
node_err_bounds : 2D numpy.ndarray[float]: Allowed deviation from node values for nodes affected by error. This is a matrix with rows (lower_deviation, upper_deviation).
target_val : float: Target function value at which we want to move the node.

Returns:

(int, float): The index of the node and corresponding bumpiness value indicating the sought node in the list node_pos.

rbfopt_aux_problems.get_noisy_rbf_coefficients(settings, n, k, Phimat, Pmat, node_val, node_err_bounds, init_rbf_lambda=None, init_rbf_h=None)[source]¶

Obtain coefficients for the noisy RBF interpolant.

Solve a quadratic problem to compute the coefficients of the RBF interpolant that minimizes bumpiness and lets all points with deviate by a given amount from their value.

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.
Phimat : numpy.matrix: Matrix Phi, i.e. top left part of the standard RBF matrix.
Pmat : numpy.matrix: Matrix P, i.e. top right part of the standard RBF matrix.
node_val : 1D numpy.ndarray[float]: List of values of the function at the nodes.
node_err_bounds : 2D numpy.ndarray[float]: Allowed deviation from node values for nodes affected by error. This is a matrix with rows (lower_deviation, upper_deviation).
init_rbf_lambda : 1D numpy.ndarray[float] or None: Initial values that should be used for the lambda coefficients of the RBF. Can be None.
init_rbf_h : 1D numpy.ndarray[float] or None: Initial values that should be used for the h coefficients of the RBF. Can be None.
Returns
—
(1D numpy.ndarray[float], 1D numpy.ndarray[float]): Two vectors: lambda coefficients (for the radial basis functions), and h coefficients (for the polynomial). If initialization information was provided and was valid, then some values will always be returned. Otherwise, it will be None.

Raises:

ValueError: If some parameters are not supported.
RuntimeError: If the solver cannot be found.

rbfopt_aux_problems.global_search(settings, n, k, var_lower, var_upper, integer_vars, node_pos, rbf_lambda, rbf_h, mat, target_val, dist_weight, fmin, fmax)[source]¶

Global search that tries to balance exploration/exploitation.

If using Gutmann’s RBF method, compute the maximum of the h_k function, see equation (8) in the paper by Costa and Nannicini. If using the Metric SRSM, select a point based on a combination of distance and objective function value.

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. mat : 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, or None if using the MSRSM algorithm. target_val : float Value f* that we want to find in the unknown objective function. Used by Gutmann’s RBF method only. dist_weight : float Relative weight of the distance and objective function value, when selecting the next point with a sampling strategy. A weight of 1.0 corresponds to using solely distance, 0.0 to objective function. Used by Metric SRSM only. fmin : float Minimum value among the interpolation nodes. fmax : float Maximum value among the interpolation nodes.
Returns:	1D numpy.ndarray[float] A local optimum. It is difficult to do global optimization so typically this method returns a local optimum.
Raises:	ValueError If some parameters are not supported. RuntimeError If the solver cannot be found.

rbfopt_aux_problems.initialize_instance_variables(settings, instance, start_point=None)[source]¶

Initialize the variables of a problem instance.

Initialize the x variables of a problem instance, and set the corresponding values for the vectors $(u,\pi)$ . This helps the local search by starting at a feasible point.

Parameters:	settings : `rbfopt_settings.RbfoptSettings` Global and algorithmic settings. instance : pyomo.ConcreteModel A concrete instance of mathematical optimization model. start_point : 1D numpy.ndarray[float] or None The starting point for the local search, or None if it should be randomly generated.

rbfopt_aux_problems.initialize_msrsm_aux_variables(settings, instance)[source]¶

Initialize auxiliary variables for the MSRSM model.

Initialize the rbfval and mindist variables of a problem instance, using the values for for x and u_pi already given. This helps the local search by starting at a feasible point.

Parameters:	settings : `rbfopt_settings.RbfoptSettings` Global and algorithmic settings. instance : pyomo.ConcreteModel A concrete instance of mathematical optimization model.

rbfopt_aux_problems.minimize_rbf(settings, n, k, var_lower, var_upper, integer_vars, node_pos, rbf_lambda, rbf_h, best_node_pos)[source]¶

Compute the minimum of the RBF interpolant.

Compute the minimum of the RBF interpolant with a PyOmo model.

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. best_node_pos : 1D numpy.ndarray[float] Coordinates of the best interpolation point.
Returns:	1D numpy.ndarray[float] A minimizer. It is difficult to do global optimization so typically this method returns a local minimum.
Raises:	ValueError If some parameters are not supported. RuntimeError If the solver cannot be found.

rbfopt_aux_problems.pure_global_search(settings, n, k, var_lower, var_upper, integer_vars, node_pos, mat)[source]¶

Pure global search that disregards objective function.

If using Gutmann’s RBF method, Construct a PyOmo model to maximize :math: 1/mu. If using the Metric SRM, select a point purely based on distance.

See paper by Costa and Nannicini, equation (7) pag 4, and the references therein.

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. mat : 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 if given. Can be None when using the MSRSM algorithm.
Returns:	List[float] A maximizer. It is difficult to do global optimization so typically this method returns a local maximum.
Raises:	ValueError If some parameters are not supported. RuntimeError If the solver cannot be found.

rbfopt_aux_problems.set_minlp_solver_options(solver)[source]¶

Set MINLP solver options.

Set the options of the MINLP solver.

Parameters:	solver: pyomo.opt.SolverFactory The solver interface.

rbfopt_aux_problems.set_nlp_solver_options(solver)[source]¶

Set NLP solver options.

Set the options of the NLP solver.

Parameters:	solver: pyomo.opt.SolverFactory The solver interface.