Optimization Utility and Helper Functions#

This subpackage provides various general-purpose utility and functions useful for optimization routines.

Utility functions for the optimization module. These are utility classes/functions for various optimization algorithms, but are not useful otherwise. Any utility function that is general will likely be moved to the utility module.

pseudo_random_binary_objective_function(x, scale=10.0, random_seed=1234)[source]#

A function that can be used to testing BinaryReinforceOptimizer The function creates a pseudo random number generator from a fixed seed. The passed binary state/vector x is transformed into an equivalent index which is one-to-one associated with the random number sequence generated by the random number generator

Parameters:

  • x – a binary vector state

  • scale (float) – a scalar quantity to magnify the range of the random values

  • random_seed – random seed for reproduction

Returns:

the value of the test function (deterministic) associated corresponding to the passed state

Return type:

float

backtracking_line_sesarch(x, f, g, max_step=1, d=None, tau=0.9, c=0.5, maxiter=10000)[source]#

Implement the backtracking line search algorithm

Parameters:

  • x – current state

  • f – objective function that accepts x, and return f(x)

  • g – the gradient function

  • max_step (float) – maximum step size. Default is 1.

  • d – search direction; if None, will be set to g

  • tau (float) – the reduction factor for the step size. Default is 0.9.

  • c (float) – the Armijo condition parameter. Default is 0.5.

  • maxiter (int) – maximum number of iterations. Default is 10000.

Raises:

AssertionError – if c and tau are not in the interval (0, 1)

Returns:

the step size satisfying Armijo condition

Return type:

float

box_projection(x, bounds=None)[source]#

Apply a projection operator \(P\), which maps an arbitrary point onto the feasible domain/region described by the box constraints. The box constraintsas can be defined by bounds by setting to bounds=(lb, ub) and,

\[\begin{split}P(x) := \\min\\{u,\\max\\{l,x\\}\\} = \\begin{cases} l, & \\text{if } x < l \\\\ x, & \\text{if } x \\in [l,u] \\\\ u, & \\text{if } x > u \\end{cases}\end{split}\]

Note

The bounds are standardized by calling standardize_domain_bounds

Parameters:

  • x (np.ndarray) – input point, \(x\), on which the projection operator is applied

  • l (None | Sequence) – bounds (lb, ub) or [(lb, ub), …, (lb, ub)]

Returns:

the projection \(P(x)\)

Return type:

np.ndarray

projected_gradient(init_x, grad, step_size, l=None, u=None, verbose=False)[source]#

Projection operator of the gradient g on bound constraints, given a state, gradient, and a step size. Initial implementation uses piecewise search of bended segments

Parameters:

  • init_x – current state

  • grad – direction

  • step_size (float) – (maximum) step size

  • l (float) – lower bounds. Default will be set to -infty

  • u (float) – upper bounds. Default will be set to +infty

  • verbose (bool) – print debug information. Default is False

Returns:

A tuple containing the following values

  • \(y = \text{init_x} - \text{step_size} * \text{grad}\)

  • \(\text{Proj}(y)\)

  • The breakpoints, i.e. the points \(x(t)\) inside or at the boundaries, projected into the feasible domain given the box constraints.

Return type:

tuple[np.ndarray, np.ndarray, list[np.ndarray]]

Warning

  • Both l, u, must be of the same type/size/shape as x, or None

  • Currently, the local minima is looked-up only at the kinks/breakpoints

Note

  • References: J. Nocedal and S. Write “Numerical Optimization 2nd. ed.” Sec 16.7

scale_gradient(x, grad, lb=0, ub=1)[source]#

Scaling gradient to the interval (if exceeds after added to x) lb=0, ub=1 with x being current point.

..note::

This is a projector that is applied to scale down a gradient grad if (when added to x) exceeds given bounds (lb, ub). Unlike pyoed.utility.truncate() which trims down the gradient vector at the bounds in all directions, this function scales the gradient by multiplying it with a scaling factor evaluated based on surplusses in all directions. If nothing is outside the domain, the scaling factor is 1. Otherwise, it is set to the number that makes the larges excess (beyond lb or ub) is brought does to the corresponding extremum (i.e., lb or ub respectively). This makes sure the gradient update (x+grad) lies within the bounds (lb, ub) and makes it much easier to tune the learning rate (timestep) of the optimizer.

Parameters:

  • x – the current state vector (e.g., target of optimization problem)

  • grad – the gradient of the optimization objective (same size as x)

  • lb – lower bound of the domain. This could be a scalar or 1d array of the same size as x (and grad)

  • ub – upper bound of the domain. This could be a scalar or 1d array of the same size as x (and grad)

Returns:

a scaled version of the gradient (a copy is created if the scaling factor is not 1.)

Raises:

ValueError if the lower bound(s) are not strictly less than upper bound(s).

Raises:

TypeError if x and grad (and ‘lb’, ub if arrays) are not of the same size.

Raises:

TypeError if lb and ub are not similar in type/shape. That is, an exception is raised if for example lb is a number and ub is an array. Mixing could be handled but for cleaneliness, we don’t allow it.

scale_down_gradient(x, grad, positive_direction=True, bounds=None)[source]#
stepsize_schedule(itr, def_step=1, method='constant')[source]#

Return a suitable step size at a given optimization iteration

Parameters:

  • itr (int) – iteration number

  • def_step (float) – default step size (see note). Default is 1.

  • method (str) – approach to choose the step size at a given iteration (see note). Default is ‘constant’.

Note

Step size is determined based on the selected method

  • ‘constant’: def_step is used at all iterations

  • ‘decay’: def_step/iter

Raises:

  • AssertionError – if the iteration number or if the default step size is not positive

  • ValueError – if the method is not recognized

Returns:

step size for the given iteration

Return type:

float

binary_bruteforce_objective(obj, size, num_active=None, objective_value_tracker=None, verbose=False)[source]#

Evaluate the value of the objective (obj) at all possible binary combinations;

Parameters:

  • obj – Objective function to evaluate.

  • size (int) – objective space dimension (design space)

  • num_active –

    If None, all sizes will be looped over, otherwise, it must be

    1. an integer <= size), only solutions with active subset (==1) equal to num_active will be calculated.

    2. list of integers (looped over as in (a) above)

  • objective_value_tracker (dict[int,float]) – an optional dictionary with partial information to lookup before evaluation. Keys are integer indexes of binary candidates.

  • verbose (bool) – print progress. Default is True.

Returns:

a dictionary holding an updated version (new if objective_value_tracker passed is None) of objective_value_tracker with additional results. If objective_value_tracker is passed, it will be updated (in-place).

Return type:

dict[int,float]

..note::

This is for testing and debugging only

binary_bruteforce_solution(obj, size, num_active=None, maximize=True, objective_value_tracker=None, verbose=False)[source]#

A wrapper around binary_bruteforce_objective() that Finds an optimal solution maximum/minimum of a binary optimization problem with optional budget constraints (described by num_active) by bruteforce search, that is by looking up all possible binary combination.

Parameters:

  • obj – Objective function to evaluate.

  • size (int) – objective space dimension (design space)

  • num_active –

    If None, all sizes will be looped over, otherwise, it must be

    1. an integer <= size), only solutions with active subset (==1) equal to num_active will be calculated.

    2. list of integers (looped over as in (a) above)

  • maximize (bool) – a flag that defines whther the maximum or the minimum is seeked.

  • objective_value_tracker (dict[int,float]) – an optional dictionary with partial information to lookup before evaluation. Keys are integer indexes of binary candidates.

  • verbose (bool) – print progress. Default is True.

Returns:

a list of optimal solutions (each is a numpy array of size size). If the global optimal solution is unique, the length of this list is 1.

Return type:

list[int]

..note::

This is for testing and debugging only

standardize_domain_bounds(size, bounds, min_lb=-inf, max_ub=inf, replace_none=True)[source]#

Standardize the bounds of a random variable of a given size.

Parameters:

  • size – dimension/size of the target variable (positiove integer)

  • bounds –

    desired bounds of the variable’s domain. The types/shapes allowed are as follows (otherwise a TypeError is raised):

    • None: In this case, the bounds are [(min_lb, max_ub), (min_lb, max_ub), …]

    • (lb, ub): In this case, the bounds are [(lb, ub), (lb, ub), …]

    • [(lb, ub)]: In this case, the bounds are [(lb, ub), (lb, ub), …]

    • [(lb_1, ub_1), (lb_2, ub_2), …]: the size is asserted, and a copy of the

      bounds (as a list of tuples) is returned

  • min_lb – smallest allowed lower bound; if not passed it is set to -inf

  • max_ub – largetst allowed upper bound; if not passed it is set to +inf

  • replace_none – If true, any bounds that is None is replaced with min_lb or max_ub for lb, ub, respectively.

Returns:

List of the form [(lb_1, ub_1), (lb_2, ub_2) , …] with length equal to size where (lb_i, ub_i) are the lower and upper bound of the ith entry of a given variable.

Note

If replace_none any `None value is replaced with proper bounds value so that it can be compared with float to test violation of bounds.